Strict Avalanche Criterion (SAC)

Question

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

Answer 1

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
results(mask,0) += bitval

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
results(mask,booleanfunction) += bitval

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:
  mask = 2^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.