0
$\begingroup$

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.

$\endgroup$

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.