I am trying to create linear approximation table of AES SBox to better understand linear cryptanalysis, I have followed the formula in this paper (page 7 of pdf file) to be able to generate the linear approximation table of AES S-Box, specifically that is $$\frac{\#\{x\in R|x \cdot t_x=B(x)\cdot t_y\}}{2^8} -\frac{1}{2}.$$ This is equivalent to $$\frac{\#\{x\in R|x \cdot t_x=B(x)\cdot t_y\}}{2^8} -\frac{2^7}{2^8},$$ so for each pair $ t_x $, $ t_y $ of the linear approximation table will be calculated as $ x\in R|x \cdot t_x=B(x)\cdot t_y\ - 2^7 $ (with # symbol denotes cardinality). Once I got the formula I wrote the following code:

import java.io.BufferedWriter;
import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class LinearProbabilityV2 {
    public static void main(String[] args) throws IOException {
        File file=new File("Result_Linear_approximation_table.txt");
        FileWriter fw=new FileWriter(file);
        BufferedWriter bw=new BufferedWriter(fw);
        int SBox[] = { 0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
                        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 
                        0xc0, 0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 
                        0x31, 0x15, 0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 
                        0x27, 0xb2, 0x75, 0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 
                        0x29, 0xe3, 0x2f, 0x84, 0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 
                        0x39, 0x4a, 0x4c, 0x58, 0xcf, 0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 
                        0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8, 0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 
                        0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2, 0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 
                        0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73, 0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 
                        0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb, 0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 
                        0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79, 0xe7, 0xc8, 0x37, 0x6d, 0x8d, 
                        0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08, 0xba, 0x78, 0x25, 0x2e, 
                        0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a, 0x70, 0x3e, 0xb5, 
                        0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e, 0xe1, 0xf8, 
                        0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf, 0x8c, 
                        0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16};
        for (int k = 0; k < 256; k++) { // input mask
            for (int j = 0; j < 256; j++) { // output mask
                int count = 0;
                for (int i = 0; i < 256; i++) {
//                  Calculating the right side: S(x) AND O_y (O_y là output mask)
                    int result_side_right = SBox[i] & j;
//                  Calculating the left side" x AND I_y (I_x là input mask)
                    int result_side_left = i & k;
                    if (result_side_left==result_side_right) {
                        count += 1;
                bw.write((count -128)+" ");

where int result_side_right = SBox[i] & j to calculate $ B(x)\cdot t_y $, int result_side_left = i & k to calculate $ x \cdot t_x $ and count is the result corresponding to each pair $ t_x, t_y $. The output from the above program will look like this, but according to sagemath the result should look like this. Did I misunderstand something here?


1 Answer 1


At issue here is the fact that SBox[i] & j does not compute $B(x)\cdot t_y$. The latter is a 0 or 1 value and the former is an 8-bit value. Instead you must calculate poppar(SBox[i] & j) where poppar is the population parity function that returns 0 if the input has an even number of bits set and 1 if it has an odd number of bits set. This is equal to the $\mathbf F_2$ sum of the masked bits and hence the dot product.

  • $\begingroup$ I have tried but still not getting the desired result. $\endgroup$
    – Cat Dragon
    Jun 5, 2023 at 9:10
  • $\begingroup$ Did you do the same for i&k ? $\endgroup$
    – Daniel S
    Jun 5, 2023 at 11:14
  • $\begingroup$ Oops, I got it, thank you $\endgroup$
    – Cat Dragon
    Jun 5, 2023 at 12:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.