In the RSA DES challenges, how did the contestants know they had found the right key considering they weren't given any plaintext?

Question

If the contestants were given both the plaintext and ciphertext, it's straightforward. Just bruteforce all 56-bit keys until you find one that maps the given plaintext to the given ciphertext.

But from what I understand, the contestants were given only the ciphertext and the initialization vector. I'm confused as to how they cracked the challenge without any plaintext.

What I imagine they did was:

1. Ok, we know the plaintext is less than or equal to the size of the ciphertext.
2. Calculate all possible plaintext from 1 bit up to the bit size of the ciphertext.
3. Calculate all possible 56-bit keys.
4. Run each plaintext through all 56-bit keys until they found a mapping.

But this doesn't make sense given the sheer size of the possibilities.

So since they weren't given any plaintext, how did they know they'd found the right plaintext/key combination?

Answer 1

One can still access the challenge rules from the archive.org

Each contest is based on a specified cipher. A brief piece of printable ASCII text (containing byte values in hexadecimal notation from 0x20 to 0x7e) will be appended to the fixed 24-character string "The unknown message is:". The result will be padded and then encrypted with the associated cipher under a randomly-generated key.

The message is also padded by PKCS#5 padding. Thus, the attacker has three options to test their results;

1. Check the beginning of the message; it must start with "The unknown message is:"
2. A valid PKCS#5 padding at he the end.
3. And, one general rule when only ciphertexts are given; one can check the result is valid (English) language. For this, one block may not be enough, since there are many valid words in the 64-bit block. One block will result in many keys. To narrow the keys, additional ciphertexts are required. This approach can be work even 1. and 2. cases are not known. For this specific challenge the range of the characters given between 0x20 and 0x7e, i.e. between and ~

---

distributed.net found this message in DES Challenge II-1;

• The secret message is: Many hands make light work.

---

Note : It is interesting that the Wikipedia says; The secret message is: where the source is lists.distributed.net, however, the RSA archives says The unknown message is:.