I am struggling to understand the DS-MITM attack on AES (Original Paper). Especially the 4-rounds distinguisher by Gilbert and Minier (section 3).

I get the basic idea that we check exactly on which input-bytes and key-bytes the first entry of the AES-State after three rounds $C_{11}^{(3)}$ depends. So we have a function $f: a_{11} \longrightarrow C_{11}^{(3)}$ (where $a_{11}$ is the first plaintext-byte) that is entirely determined by 9 one-byte-values {$c_1,\ldots,c_8,K_{11}^{(3)}$}.

Now I don't understand at all how this is used to define a distinguisher for 4-round AES. It states that the basic idea is to find a collision of this functions but I can't make out how this suffices for a distinguisher.
The proposition to define this distinguisher states the following:

Consider a set of 256 plaintexts where the entry $a_{11}$ is active and all the other entries are passive. Apply 4 rounds of AES to this set. Let the function $S^{−1}$ denote the inverse of the AES s-box and $k^{(4)}$ denote $0E · K^{(4)}_{11} + 0B · K^{(4)}_{21} + 0D · K^{(4)}_{31} + 09 · K^{(4)}_{41} .$ Then
$S^{-1}[0E · C^{(4)}_{11} + 0B · C^{(4)}_{21} + 0D · C^{(4)}_{31} + 09 · C^{(4)}_{41} +k^{(4)}]$
is a function of $a_{11}$ determined entirely by 1 key byte and 8 bytes that depend on the key and the passive entries. Thus,
$0E · C^{(4)}_{11} + 0B · C^{(4)}_{21} + 0D · C^{(4)}_{31} + 09 · C^{(4)}_{41}$
is a function of $a_11$ determined entirely by 10 constant bytes.

So long story short, I have 2 questions:

  1. Where does this function with coefficients $0E, 0B$, etc. come from?
  2. How does this property define a distinguisher on AES?

Edit: Regarding question 1, found out that it derives from the inverse polynomial that defines MixColumns.


Your Answer

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

Browse other questions tagged or ask your own question.