Desgràcia (solution)

Desgràcia (solution)

back to puzzle

This challenge refers to three historical cryptographic challenges created by RSA Labs in the late 1990s, known as DES-I, DES-II-1, and DES-II-2. These challenges called on the public to crack the U.S. Data Encryption Standard, most likely by brute force, which was within the realm of possibility at that time because DES used only 56-bit keys. (Famously, the U.S. National Security Agency had modified the design of DES, originally proposed by IBM, in two ways: one of these modifications strengthened DES against a then-classified attack known as differential cryptanalysis, while one of them weakened DES against the initially-expensive hardware-intensive brute force attack, by reducing the key length from 64 bits to 56 bits. That tended to make DES harder to crack for adversaries with a lot of mathematical expertise, but easier for adversaries with a lot of hardware and/or money.)

RSA Labs hoped to show that DES was terribly insecure and needed to be replaced. This was demonstrated by the success of three different teams in carrying out the brute force attack—first the DESChall volunteer distributed computing project, next the distributed.net project, and next—in an upset victory—EFF, which had secretly created a specialized DES cracking device called Deep Crack. This demonstration helped accelerate the standardization and adoption of AES to replace DES.

Information about these challenges and their solutions is less readily available on the Internet today than it used to be, but the solutions to DES-I, DES-II-1, and DES-II-2 can ultimately still be found online. More about the history of DES and EFF's role in getting it replaced can be found in EFF's book Cracking DES, Steven Levy's book Crypto, or other historical sources and retrospectives.

For this challenge, you need to locate those three key values (which are written as 64-bit values due to the presence of parity-check bits), and XOR then:

DES-I    85 58 89 1A B0 C8 51 B6, [DESChall]        
DES-II-1 76 9E 8C D9 F2 2F 5D EA, [distributed.net]
DES-II-2 3E CD A1 5E 70 4F B3 1C, [EFF]
         ------------------------
	 CD 0B A4 9D 32 A8 BF 40  [this challenge]

This key will work to decrypt the challenge, giving ANS= followed by the four byte values DE, C0, DE, and D1. So the answer is DEC0DED1.

A sample Python 2 program [since it relies on .decode("hex")] to perform this decryption is

#!/usr/bin/env python

from Crypto.Cipher import DES
from Crypto.Util.strxor import strxor

DESI="8558891AB0C851B6"
DESII1="769E8CD9F22F5DEA"
DESII2="3ECDA15E704FB31C"
plain = "ANS="+"dec0ded1".decode("hex")

keys = [x.decode("hex") for x in (DESI, DESII1, DESII2)]
for key in keys:
    print(key.encode("hex"))
print("--"*8)
print(reduce(strxor, keys).encode("hex"))

des_combined = DES.new(key = reduce(strxor, keys), mode=DES.MODE_ECB)

print(plain, des_combined.encrypt(plain), des_combined.encrypt(plain).encode("hex"))
print(des_combined.decrypt("31830541f70b8900".decode("hex")))

The word "desgràcia" is Catalan for "misfortune", like English "disgrace", which is what the continued used of DES was shown to be by the DES challenges. Today, there is a commercial cloud-based DES cracking service which will use its own hardware to perform a brute-force DES crack for you (though hopefully people solving this challenge didn't need to pay for that service).