6
$\begingroup$

I'm trying to attack a very simple cipher using differential cryptanalysis as a way of becoming familiar with this method. The cipher is so simple that I've found a differential which I can trace through all the rounds of the cipher with 100% probability (it is not 0 of course).

I've read/watched a few tutorials and if I've understood them correctly recovering the last subkey works as follows:

  • Find $\Delta_X$ which you can trace with high probability.
  • Choose two plaintexts such $X_1$ and $X_2$ that $X_1 \oplus X_2 = \Delta_X$
  • Encrypt them, getting $Y_1$ and $Y_2$.
  • Try to brute force last round's key. For each key: Decrypt the last round for both ciphertexts, getting $Z_1$ and $Z_2$. If $\Delta_Z=Z_1 \oplus Z_2$ is the same as you predicted form $\Delta_X$ the key can be correct. It gets one point.
  • Repeat it for different plaintext pairs.
  • The key that has the highest score is probably the correct one.

Maybe I've misunderstood something about DC, if so, the remainder of this question is probably nonsense. That's why I've described what I think differential cryptanalysis is.

But if it's correct:

Key doesn't influence the differential (it holds with 100% prob.) so whatever key I try while decrypting the last round, the differential on it's input is always as expected. Thus I can't eliminate any keys.

This seems suspicious to me - if a differential holds with 100% prob. the cipher is weak, right? Can a cipher be so weak that some attack doesn't work on it? It seems quite strange...

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

Usually differential cryptanalysis relies on something called the "wrong key randomization hypothesis", which is the assumption that decryption of the last round with the wrong key results in a random difference at the beginning of the last round, while decryption with the correct key will result in the expected difference with the probability of the differential (which hopefully is sufficiently high or low as to be distinguishable from a random difference). However, if there is a probability one differential going through the entire cipher then by definition that means that decryption with any key will lead to the same difference.

You might try linear cryptanalysis instead. A probability 1 linear characteristic through the entire cipher will give you 1 bit of the key with just a single known plaintext (Edit to add: poncho adds a good clarification - the probability 1 linear characteristic must involve at least one key bit to be useful for Matsui's algorithm one). If for some reason there is no linear characteristic through the entire cipher, then you could try differential-linear cryptanalysis using that probability 1 differential through most of the cipher and a short linear characteristic at the end.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Nit: a probability 1 linear characteristic will give you a key bit only if the characteristic is 'input bits XOR output bits XOR some key bits'. If it doesn't involve the key, such as 'copy bit 0 of the plaintext to bit 0 of the ciphertext', the obvious linear characteristic doesn't tell you anything about the key... $\endgroup$
    – poncho
    Jul 2, 2016 at 16:26
0
$\begingroup$

You can still use differential cryptanalysis. Let $r$ be the number of rounds.

If the differential characteristic has probability 1 through the whole cipher, it also has probability one at the output of any intermediate round. Use the characteristic through $r-1$ rounds and decrypt the ciphertext backwards through the last round, subject to hypotheses on the last round key and pick the last round key that gives highest differential probability.

See also the answer here as well as "A Tutorial on Linear and Differential Cryptanalysis" by Heys, easily found online.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Except that all tested keys will decrypt to the same $r-1$ difference, because the differential characteristic has probability 1. So the correct key guess cannot be distinguished from the incorrect key guesses. $\endgroup$
    – J.D.
    Jul 3, 2016 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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