Posted by: jmclaugh
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...