2010 Reports : Cryptology ePrint Archive Forum

**2010/337**

**Re: 2010/337**

Discussion forum for Cryptology ePrint Archive reports posted in 2010.
Please put the report number in the subject.

2010/337

Posted by: **Orr** (IP Logged)

Date: 14 June 2010 09:29

Without entering to the question whether the related-subkey model is "legitimate", the attack of 2010/337 assumes that the adversary is given two plaintexts which are related in a very strong manner (and not two subkeys which are related in a very strong manner).

Of course, if you can identify two plaintexts which have a very strong relation, you could deduce information concerning the key (if you could identify the plaintext which is encrypted after one round to the all zero value, you could deduce the key easily). The problem is how to identify these two plaintexts, a fact which is not communicated in the paper. Of course, one can take many plaintexts, and try about 2^128 such pairs, ...

Of course, if you can identify two plaintexts which have a very strong relation, you could deduce information concerning the key (if you could identify the plaintext which is encrypted after one round to the all zero value, you could deduce the key easily). The problem is how to identify these two plaintexts, a fact which is not communicated in the paper. Of course, one can take many plaintexts, and try about 2^128 such pairs, ...

Posted by: **dsds** (IP Logged)

Date: 15 June 2010 15:19

I think this new attak could be seen as a special kind of differential fault analysis on AES-128, where the adversary can choose a special concrete value of the fault (\delta) in an appropriate position. In fact, in this situation, such attack could be mounted in either the encryption or decryption direction.

For example, in the decryption procedure, as the author described, the key point is the following differential equation:

R_k(P)+R_k(P*) = \delta,

which is equivalent to

SB(P+k)+SB(P*+k)=SR^{-1}\circ MC^{-1}(\delte)=\epsilon.

Now, assume the fault is \delta, such that after applying the inverse transformation InvMixColumns, all bytes of the result valuse are non-zero. Then, once \delta is known for the adversary, by applying the differential attack to each s-box independently, he could obtain at most 4^16=2^32 possible round key candidates.

Edited 2 time(s). Last edit at 15-Jun-2010 15:30 by dsds.

For example, in the decryption procedure, as the author described, the key point is the following differential equation:

R_k(P)+R_k(P*) = \delta,

which is equivalent to

SB(P+k)+SB(P*+k)=SR^{-1}\circ MC^{-1}(\delte)=\epsilon.

Now, assume the fault is \delta, such that after applying the inverse transformation InvMixColumns, all bytes of the result valuse are non-zero. Then, once \delta is known for the adversary, by applying the differential attack to each s-box independently, he could obtain at most 4^16=2^32 possible round key candidates.

Edited 2 time(s). Last edit at 15-Jun-2010 15:30 by dsds.

Posted by: **jmclaugh** (IP Logged)

Date: 17 June 2010 20:19

I'm afraid I don't follow all of dsds's post above.

dsds, are you describing a modified attack model where the attacker does not need to know \delta, but does need to be able to xor it with the post-round-1 state several times, and in which the attack's effectiveness is reduced if any bytes of \epsilon are zero?

If so, you don't explain how the adversary can deduce the value of \delta, so noting that you attack each S-box independently, I'd like to borrow some ideas from integral cryptanalysis to suggest the following:

Step 0. Given any p, the adversary obtains p* by, as described, xoring the value \delta with the state after the first round, and then reversing the first round.

Step 1. Adversary chooses p.

(The adversary not knowing \delta may correspond to it being a block of data situated somewhere else on the target machine that the adversary had a limited amount of access to, I don't know. It doesn't sound very plausible if I'm honest.)

2. For each of the sixteen S-boxes in turn:

2.1 The adversary chooses a set of plaintexts p_i (0 <= i < 256) such that p_i has value i in the byte corresponding to the current S-box, and is identical to p in all other bytes.

2.2 The adversary generates, for each p_i in turn, the corresponding p*_i by applying Step 0. (Obviously the adversary doesn't need to do this for a p_i that's already appeared as a p*_j for j != i)

2.3 If all values \alpha_i = (p_i \oplus p*_i) are zero, the corresponding byte of \epsilon was zero, this part of the attack fails and the adversary should move on to the next S-box.

(However, the probability that none of the bytes of \epsilon are zero is 0.939298096, so the odds are in the adversary's favour.)

2.4 If this is not the case, precisely one of the values \alpha_i will have been (p_i \oplus p*_i) and (p_j \oplus p*_j) for some p_j not equal to p_i or p*_i. (This follows from the fact that every non-trivial row, and every non-trivial column, of the AES S-box's difference distribution table has precisely one 4 in it.)

Knowledge of this value is sufficient to identify the byte of \epsilon corresponding to the current S-box, and to narrow down the number of possible candidates for the corresponding byte of the round key to four.

2.5 This leaves us with the number of possible first-round-keys reduced to:

(2^2)^(|s-boxes for which the attack succeeded|)*(2^8)^(|s-boxes for which the attack failed|). Since the attack will succeed for all the S-boxes with high probability, the adversary will probably be left with precisely 2^32 candidate values for the first round key.

In spite of all that, though, the overall attack model (adversary is able to modify interim data after the first round and then use oracle access to obtain the corresponding plaintext) does seem to give the adversary an enormous amount of power - is it really plausible? I have my doubts and rather suspect it isn't, but could be wrong...

dsds, are you describing a modified attack model where the attacker does not need to know \delta, but does need to be able to xor it with the post-round-1 state several times, and in which the attack's effectiveness is reduced if any bytes of \epsilon are zero?

If so, you don't explain how the adversary can deduce the value of \delta, so noting that you attack each S-box independently, I'd like to borrow some ideas from integral cryptanalysis to suggest the following:

Step 0. Given any p, the adversary obtains p* by, as described, xoring the value \delta with the state after the first round, and then reversing the first round.

Step 1. Adversary chooses p.

(The adversary not knowing \delta may correspond to it being a block of data situated somewhere else on the target machine that the adversary had a limited amount of access to, I don't know. It doesn't sound very plausible if I'm honest.)

2. For each of the sixteen S-boxes in turn:

2.1 The adversary chooses a set of plaintexts p_i (0 <= i < 256) such that p_i has value i in the byte corresponding to the current S-box, and is identical to p in all other bytes.

2.2 The adversary generates, for each p_i in turn, the corresponding p*_i by applying Step 0. (Obviously the adversary doesn't need to do this for a p_i that's already appeared as a p*_j for j != i)

2.3 If all values \alpha_i = (p_i \oplus p*_i) are zero, the corresponding byte of \epsilon was zero, this part of the attack fails and the adversary should move on to the next S-box.

(However, the probability that none of the bytes of \epsilon are zero is 0.939298096, so the odds are in the adversary's favour.)

2.4 If this is not the case, precisely one of the values \alpha_i will have been (p_i \oplus p*_i) and (p_j \oplus p*_j) for some p_j not equal to p_i or p*_i. (This follows from the fact that every non-trivial row, and every non-trivial column, of the AES S-box's difference distribution table has precisely one 4 in it.)

Knowledge of this value is sufficient to identify the byte of \epsilon corresponding to the current S-box, and to narrow down the number of possible candidates for the corresponding byte of the round key to four.

2.5 This leaves us with the number of possible first-round-keys reduced to:

(2^2)^(|s-boxes for which the attack succeeded|)*(2^8)^(|s-boxes for which the attack failed|). Since the attack will succeed for all the S-boxes with high probability, the adversary will probably be left with precisely 2^32 candidate values for the first round key.

In spite of all that, though, the overall attack model (adversary is able to modify interim data after the first round and then use oracle access to obtain the corresponding plaintext) does seem to give the adversary an enormous amount of power - is it really plausible? I have my doubts and rather suspect it isn't, but could be wrong...

Please log in for posting a message. Only registered users may post in this forum.