i am studying about differential cryptanalysis, and found one metric to measure the resistance of a sbox to it, but to use it, it is necessary to build a difference distribution table, like the one in this link, this is is the table of sobox s1 of des, how do I build the table for AES sbox for example?
-
1$\begingroup$ FYI, the differential uniformity of the AES s-box is 4, with 255 table entries holding that value. All s-boxes generated by finite field inversion in $GF(2^8)$ have the same differential uniformity $\endgroup$– Richie FrameOct 29, 2015 at 21:03
2 Answers
Those tables are fairly easy to build conceptually but require quite some work to actually carry out.
Note that: The columns show the XOR for the in-going pairs and the rows show the number of pairs that had the specified XOR afterwards.
This pseudo-code generates the table:
InLength; // input length of the S-Box in bits
OutLengh; // output length of the S-Box in bits
Table[In][Out]; // the table, In is the XOR of the in-going pair, Out is the resulting XOR, the table returns the number of occurences
// Initialize the table:
for(in = 0;in<2^InLength;in++)
{
for(out = 0;out<2^OutLength;out++)
{
Table[in][out] = 0;
}
}
// this makes us go through all the possible value of p1
for(p1 = 0;p1<2^InLength;p1++)
{
// this makes us go through all the possible value of p2
for(p2 = 0;p2<2^InLength;p2++)
{
XOR_IN = p1 XOR p2;
XOR_OUT = SBOX(p1) XOR SBOX(p2);
Table[XOR_IN][XOR_OUT]++;
}
}
What this does is basically build each possible input pair of the S-Box, calculate its XOR, runs both through the S-Box and calculates the XOR of the result and increments the value at this position.
This table would be too complex to show here for AES as it would be a 256x256 table. For the actual AES S-Box refer to the Wikipedia article.
-
$\begingroup$ thank you very much for your answer, but still, it isn't quite clear to me. "What this does is basically build each possible input pair of the S-Box" is this input pair the ciphertext XOR plaintext? for example, for input 00, should the pair be 63? (input 00, result from sbox = 63; 00 XOR 63 = 63). "calculate its XOR" what do I XOR the pair with? $\endgroup$ Oct 30, 2015 at 1:33
-
1$\begingroup$ @YuriWaki, what you do is you build every possible pair (p1,p2) that can be given to the S-Box, f.ex. (00,00). You calculate the XOR of every pair (p1 XOR p2) 00, look up the transformed values (c1=S-BOX(p1),c2=S-BOX(p2)) (63,63) and calculate the XOR (c1 XOR c2) (00) of this output pair and then increment the value in the row (p1 XOR p2) and the column (c1 XOR c2) to reflect that this input difference lead to this output difference. $\endgroup$– SEJPMOct 30, 2015 at 12:54
-
$\begingroup$ thank you very much, I wrote this python script to generate the table. pastebin.com/pFWLBh7x i think it is right, but if you see something wrong, please tell me :) $\endgroup$ Oct 30, 2015 at 17:50
-
$\begingroup$ @YuriWaki, I'm no expert in Python, but this looks right :) $\endgroup$– SEJPMOct 30, 2015 at 17:59
-
$\begingroup$ @YuriWaki I updated the code, I think this version is slightly easier to understand. It is not optimized but that does not really matter in this case. $\endgroup$– BivJul 8, 2017 at 10:41
I needed a package which can provide me some basic functionality to analyse sboxes and boolean functions, so I started building my own, it maybe able to help you, checkout ZYPTO, the code is written in JULIA, but it's actually quite simple and you can understand the algorithm, I used the following algorithm
function ddt(sbox,n,m)
range = all_bool(n)
res = zeros(Int,2^n,2^m)
for x1 in range
for x2 in range
ix1 = bool2int(x1)
ix2 = bool2int(x2)
iy1 = sbox[ix1+1]
iy2 = sbox[ix2+1]
res[ix1$ix2+1,iy1$iy2+1] += 1
end
end
res
end
for n X m sbox run over all possible combination of two inputs, calculate the corresponding output and increment the frequency corresponding to that input difference-output difference by one.
The github page shows AES-128 example as well.