Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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... –  owlstead Apr 16 '13 at 23:56
    
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? –  Stavros Apr 17 '13 at 1:14
    
Because there will be $2^{56}$ possible solutions. $\:$ –  Ricky Demer Apr 17 '13 at 1:37
    
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? –  Stavros Apr 17 '13 at 10:20

1 Answer 1

up vote 3 down vote accepted

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).

share|improve this answer
    
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? –  Stavros Apr 17 '13 at 14:03
3  
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. –  fgrieu Apr 17 '13 at 15:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.