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:
- Where does this function with coefficients $0E, 0B$, etc. come from?
- 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.
