implem-sbox

A tool for finding good side-channel-protected circuits implementing small functions (cryptographic S-box).

This tool and its purpose are described in more detailed in the TCHES article (link will be provided soon). A file containing the look-up-tables of all the S-boxes studied in the article is given in list_of_test_luts.txt.

Required Tools

To build and run this program, ensure the following tools are installed:

• g++ (GNU C++ Compiler)
• make

The build process uses OpenMP for parallelization. Ensure your compiler supports it.

We give instructions for linux-based distribution, we expect it should work for windows also.

Install instructions

• clone the repository
• build the program: cd Code make

Then, download the precomputation files. It may take up to a few hours to download the complete dataset, but you may download only files for a specific S-box size.

-Option 1: Download all precomputation files (total size ~50GB): wget -r -np -nH --cut-dirs=1 -A txt https://caramba.loria.fr/sbox/precomputation_files/

-Option 2: Download files for a specific S-box size (replace n_bits with the desired size, e.g., 5_bits): wget -r -np -nH --cut-dirs=1 -A txt https://caramba.loria.fr/sbox/precomputation_files/5_bits/

-Special Case for 6 bits: If your function has degree 5, you must download both the 6_bits folder and the additional 6_bits_degree_5 folder : wget -r -np -nH --cut-dirs=1 -A txt https://caramba.loria.fr/sbox/precomputation_files/6_bits_degree_5/

4_bits: ~18.2 KB

5_bits: ~0.9 MB

6_bits: ~446 MB

6_bits_degree_5: ~47.5 GB

7_bits: ~2.1 GB

-Option 3: If you do not have a complete wget, you can access the url https://caramba.loria.fr/sbox/precomputation_files/ and download files manually. They should be put into a new directory called 'precomputation_files' inside the 'Code' directory.

Program manual

• The option '--lut' or '-l' requires the values of the LUT separated by ','
• For example: '-l 0,1,5,4,8,3,7,2'
• The number of values must be a power of 2 between 16 and 64
• The option ' --andmax' or '-a' allows you to choose a maximum for the number of AND gates wanted in the implementation
• The option '--solmax' or '-s' (optional) allows you to choose the number of different solutions wanted, by default the program will try to find all of them

Example execution

This execution gives an implementation of the S-box corresponding to the inverse of the Q2256 representative (6 bits, degree 3), with at most 15 AND gates. This should run around 30 seconds on a laptop (in some unlucky cases, it may take a few minutes).

./implem --lut 0,1,2,3,4,7,5,6,8,16,32,58,9,19,61,37,10,17,50,43,11,18,45,54,41,52,63,34,47,48,56,39,12,29,62,49,53,57,31,13,20,27,55,36,51,33,23,25,59,42,24,21,26,22,60,44,30,14,40,38,35,46,15,28 --andmax 15 -s 1
ANF is given by :
y0 = x0 ^ x1x2 ^ x0x3 ^ x2x3 ^ x1x2x3 ^ x2x4 ^ x1x2x4 ^ x3x4 ^ x0x3x4 ^ x2x5 ^ x0x2x5 ^ x1x2x5 ^ x0x3x5 ^ x1x3x5 ^ x2x3x5 ^ x4x5 ^ x1x4x5 ^ x2x4x5
y1 = x1 ^ x0x2 ^ x1x2 ^ x1x3 ^ x0x1x3 ^ x1x2x3 ^ x4 ^ x0x4 ^ x1x4 ^ x0x1x4 ^ x3x4 ^ x0x3x4 ^ x2x3x4 ^ x0x1x5 ^ x0x2x5 ^ x1x2x5 ^ x0x3x5 ^ x1x3x5 ^ x2x3x5 ^ x0x4x5 ^ x1x4x5 ^ x3x4x5
y2 = x2 ^ x2x3 ^ x1x2x3 ^ x2x4 ^ x1x2x4 ^ x0x3x4 ^ x1x3x4 ^ x5 ^ x0x1x5 ^ x2x5 ^ x0x2x5 ^ x0x3x5 ^ x4x5 ^ x2x4x5 ^ x3x4x5
y3 = x3 ^ x0x3 ^ x1x3 ^ x1x2x3 ^ x4 ^ x0x4 ^ x1x4 ^ x1x2x4 ^ x3x4 ^ x0x3x4 ^ x5 ^ x0x1x5 ^ x2x5 ^ x0x2x5 ^ x1x2x5 ^ x1x3x5 ^ x2x3x5 ^ x4x5 ^ x0x4x5 ^ x1x4x5 ^ x2x4x5
y4 = x0x3 ^ x1x2x3 ^ x0x4 ^ x1x4 ^ x1x2x4 ^ x0x3x4 ^ x0x5 ^ x1x5 ^ x0x1x5 ^ x2x5 ^ x0x2x5 ^ x1x2x5 ^ x3x5 ^ x1x3x5 ^ x2x3x5 ^ x4x5 ^ x0x4x5 ^ x2x4x5 ^ x3x4x5
y5 = x1x3 ^ x1x4 ^ x3x4 ^ x1x5 ^ x2x5 ^ x1x3x5 ^ x4x5 ^ x1x4x5
The given s-box can be implemented by :

uint32_t Sbox(uint32_t X, uint8_t size) {
	uint32_t x[size];
	for(uint8_t b=0; b<size; b++)  {
		x[b] = X&1ul;
		X >>= 1;
	}
	uint32_t y[size];
	uint32_t l2 = x[5];
	uint32_t l3 = x[3] ^ x[4];
	uint32_t l0 = x[5] ^ l3;
	uint32_t l4 = x[2] ^ x[4];
	uint32_t l5 = x[2];
	uint32_t l6 = x[1] ^ x[4];
	uint32_t l1 = x[5] ^ l6;
	uint32_t l7 = x[4] ^ x[5];
	uint32_t l8 = l6 ^ l7;
	uint32_t l9 = x[0] ^ x[2];
	uint32_t l10 = x[0] ^ l1;
	uint32_t l11 = x[2] ^ l6;
	uint32_t l13 = x[2] ^ l0;
	uint32_t l14 = x[4] ^ l10;
	uint32_t l15 = l10 ^ l13;
	uint32_t l16 = l9 ^ l10;
	uint32_t l17 = l9 ^ l14;
	uint32_t l12 = 1 ^ l17;
	uint32_t q0 = x[4] & x[5];
	uint32_t q1 = l2 & l3;
	uint32_t q2 = l2 & l4;
	uint32_t q3 = l5 & l0;
	uint32_t q4 = l6 & l7 ^ x[4];
	uint32_t q5 = l5 & l8;
	uint32_t q6 = x[0] & x[5];
	uint32_t q7 = x[0] & x[4];
	uint32_t q8 = l9 & l3;
	uint32_t q9 = q1 ^ q3;
	uint32_t q16 = q0 ^ q8;
	uint32_t q17 = q2 ^ q8;
	uint32_t tq0 = q0 ^ q6;
	uint32_t q10 = q2 ^ tq0;
	uint32_t q11 = q3 ^ q10;
	uint32_t q12 = q9 ^ q10;
	uint32_t q13 = q7 ^ tq0;
	uint32_t q14 = q4 ^ q13;
	uint32_t q15 = q5 ^ q13;
	uint32_t q18 = q17 ^ tq0;
	uint32_t q19 = q1 ^ q18;
	uint32_t ty3 = ((q4) ^ (x[3])) & ((q15) ^ (l10)) ^ (q14);
	uint32_t ty4 = ((q19) ^ (l11)) & ((q12) ^ (l12)) ^ (q10);
	uint32_t ty0 = ((q16) ^ (l5)) & ((l1)) ^ (q18);
	uint32_t ty1 = ty4 ^ ((q0) ^ (l13)) & ((q6) ^ (l14)) ^ (q7);
	uint32_t ty5 = ((q1) ^ (l0)) & ((l15)) ^ (q17);
	uint32_t ty2 = ((q19) ^ (l16)) & ((q11) ^ (l17)) ^ (q10);
	y[3] = ty3 ^ l0;
	y[4] = ty4 ^ x[4];
	y[0] = ty0 ^ x[0];
	y[1] = ty1 ^ l1;
	y[5] = ty5 ^ x[3];
	y[2] = ty2 ^ x[1];
	uint32_t Y = 0;
	for(uint8_t b=0; b<size; b++) {
		Y ^= ((Y>>b) ^ y[b]) << b;
	}
	return Y;
}
Nb_and = 15
Nb_xor = 52

Expected timings

Degree 4 on 6 bits takes half an hour, degree 5 on 6 bits takes around a day, degree 3 on 7 bits takes few hours, all other results are obtained within seconds on a laptop.