Score:0

Linear approximation table of AES S-Box

it flag

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)+" ");
            }
            bw.write("\n");
        }
        bw.close();
    }
}

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?

Score:1
ru flag

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.

Cat Dragon avatar
it flag
I have tried but still not getting the desired result.
Daniel S avatar
ru flag
Did you do the same for `i&k` ?
Cat Dragon avatar
it flag
Oops, I got it, thank you
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.