calculate linear approximation tables for Sboxes

linear_approx_table.py

import sys

# sbox from the tutorial
#sbox = [0xe, 4, 0xd, 1, 2, 0xf, 0xb, 8, 3, 0xa, 6, 0xc, 5, 9, 0, 7]
sbox = [0xf, 3, 0xa, 6, 4, 1, 0xb, 9, 0xe, 5, 0, 0xd, 2, 0xc, 7, 8]
SIZE_SBOX = len(sbox)

# compute the linear approximation for a given "input = output" equation
def linearApprox(input_int, output_int):
    total = 0
    # range over the input
    for ii in range(SIZE_SBOX):
        # get input and output of our equations
        input_masked = ii & input_int
        output_masked = sbox[ii] & output_int
        # same result?
        if (bin(input_masked).count("1") - bin(output_masked).count("1")) % 2 == 0:
            total += 1 
    # get the number of results compared to 8/16
    result = total - (SIZE_SBOX//2)
    if result > 0:
        result = "+" + str(result)
    else:
        result = str(result)

    return result

def main():
    # rows
    sys.stdout.write( "    | ")
    for i in range(SIZE_SBOX):
        sys.stdout.write(hex(i)[2:].rjust(3) + " ")
    print ""
    print " " + "-" * (SIZE_SBOX * 4 + 4)
    for row in range(SIZE_SBOX):
        sys.stdout.write(hex(row)[2:].rjust(3) +  " | ")
        # cols
        for col in range(SIZE_SBOX):
            # print the linear approx
            sys.stdout.write( linearApprox(row, col).rjust(3) + " ")

        print ""

if __name__ == "__main__":
    main()

Can you explain the meaning of the output table. What will be the Linear approximation value for a strong S-box?

May I know what formula you refer to to be able to calculate linear approximation tables ? I read a few articles that mentioned formulas to calculate linear approximation tables, one of them was Dynamic S-Box Design Using a Novel Square Polynomial Transformation and Permutation (page 7), namely x * t_x = B(x) * t_y (* is AND operator, B is SBox), so in line 17 will be if(input_mask == output_masks) total +=1. Can you explain what your "if" condition is for?