# Strict Avalanche Criterion (SAC)

I would like to know the step by step method to construct the SAC dependence matrix for AES S-Box. Can someone help me?

• define SAC dependence matrix – kodlu Jul 4 '18 at 8:46
• @kodlu it is an $n$x$n$ matrix filled with the sum of bitmasks for each boolean function of the s-box – Richie Frame Jul 4 '18 at 20:49

This is a condensed explanation, but should be enough to get you to the result.

First you must generate the intermediate data.

For each boolean function and bitmask, you run through a loop, $i$ from 0 to 255:

testval = sbox(i) XOR sbox(i XOR mask)
bitval = testval AND 1


The bitval is the low bit of the test result on the s-box input $i$. The results is the sum of all the bitvals for the given mask and boolean function, in this case boolean function 0.

For the other boolean functions, you must rightshift the test value, as you are testing the other bits rather than the low bit:

divisor = 2^booleanfunction
testval = sbox(i) XOR sbox(i XOR mask)
bitval = (testval / divisor) AND 1


The loop for the single bit mask are from 0 to 7, as that is how many there are for an s-box with 8 input bits, the mask is $2^{loop}$. The loop for the boolean function is from 0 to 7, as that is how many there are for an s-box with 8 output bits. Here is an optimized loop to calculate the results

m = 0 to 7      [loop for masks]
i = 0 to 255    [s-box input entries]
n = 0 to 7      [boolean functions]

for m:
for i:
testval = sbox(i) XOR sbox(i XOR mask)
for n:
divisor = 2^n
bitval = (testval / divisor) AND 1
results(m,n) += bitval


Now that you have the results calculated, you simply display them as a matrix:

             boolean function
7   6   5   4   3   2   1   0
0  128 116 124 116 144 116 132 132
1  136 128 116 124 128 144 124 120
m  2  128 136 128 144 120 128 132 132
a  3  140 128 136 128 116 120 136 136
s  4  136 140 128 128 132 116 128 116
k  5  136 136 140 120 120 132 132 116
6  124 136 136 120 132 120 136 136
7  132 124 136 124 136 132 144 132


This is for SAC with a single bit mask (1st order SAC) for other orders, the bitmask calculation is different, and there will be more masks, 2nd order has 28 masks for example.

• You put the line > bitval = (testval / divisor) AND 1 My question is what us the operation of "/" sign and "AND" means the logical and or bitwise and? is it a way to get the last bit of the division and AND operation? I have implemented this code, but failed to get the desired results. – Irfan Babar Jul 31 '19 at 19:54
• As an extension, it might be useful to normalise the table against expectation or do a global mean +/- standard error. – Paul Uszak Jul 31 '19 at 22:28
• @IrfanBabar yes it is to get the last bit, the / operation is division that returns an integer, however the divisor is a multiple of 2, so you can replace that part with shift of n bits to the right – Richie Frame Aug 1 '19 at 1:29