Is it possible to deduce the plaintext block or the key, given only a Simplified-DES ciphertext block (e.g. c=01110110)? I'm reading Cryptography And Network Security, by William Stallings and I'm bit confused.

  • 1
    $\begingroup$ You can probably brute force both, but only if you have enough information regarding the plain text. If the plain text is just random bits then you have no way of determining if your brute force attack succeeded... $\endgroup$
    – Maarten Bodewes
    Apr 16 '13 at 23:56
  • $\begingroup$ I have no information regarding the plaintext. I only know the ciphertext c. Why I can't brute force both, and compare their ciphertext output with the ciphertext c? $\endgroup$
    – user6519
    Apr 17 '13 at 1:14
  • $\begingroup$ Because there will be $2^{56}$ possible solutions. $\:$ $\endgroup$
    – user991
    Apr 17 '13 at 1:37
  • $\begingroup$ Why? I think there will be $2^{18}$ possible solutions because all possible keys are $2^{10}$ and all possible plaintexts are $2^8$. Am I right? So... can I bruteforce both plaintext and key? $\endgroup$
    – user6519
    Apr 17 '13 at 10:20

Simplified DES is a toy Feistel cipher with 16-bit 8-bit block and 10-bit key, and only two rounds, intended for educational purposes. Here is a preview of the original paper, and an implementation; another; yet another.

If one knows one block of ciphertext, but nothing about the plaintext and key, the plaintext can not be guessed entirely: each of the $2^{10}$ key will lead to a plaintext. Most plaintext will be reached several times, but a few plaintext might be excluded. If S-DES was a perfect toy cipher, it seems that any particular plaintext would have odds about $(1-2^{-8})^{10}\approx1.8\%$ to be impossible (it turns out odds are much higher for S-DES with two rounds, which is far from a good cipher); this in itself would constitutes a practical attack in some contexts (e.g. when one is content to exclude that the plaintext is "OK" or "NO", with some sizable odds). An adversary can also assign odds to each possible plaintext, and is at a sizable advantage over a random guess of the plaintext.

If one knows enough blocks of ciphertext, and something about the plaintext, even so vague as "it is mostly text", then an attack is easy: decipher with all the possible keys, and have a human look at the $1024=2^{10}$ resulting plaintexts, formatted with one line per candidate key. Most likely the right plaintext will be spotted by naked eye+brain within seconds. This can be helped by ordering the candidates according to how well they compress with LZW or similar. Success depends on the length of the known ciphertext, and redundancy in the plaintext. If some bits of the plaintext are known, then very little ciphertext is enough (e.g. about 5 blocks if 2 bits per plaintext blocks are known to be 0, which is the case for ASCII).

  • $\begingroup$ Thanks! Why trying all possible (plaintext, key) pairs ($2^{18}$) and checking whether their S-DES output equals c is wrong? Two different (plaintext, key) pairs could give the same output? $\endgroup$
    – user6519
    Apr 17 '13 at 14:03
  • 3
    $\begingroup$ That would work, but there is something requiring $2^8$ less effort, using the decryption function. This will not get you a single correct plaintext and key. However you will be able to rule out some plaintext. For S-DES with only 2 rounds, and your c changed to 01110100 you can deduce that 26 plaintexts are impossible, including 00010001 and 11110001. $\endgroup$
    – fgrieu
    Apr 17 '13 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy