3. Using the library¶
This chapter describes how to compile programs that use VBF and how to evaluate new algorithms.
3.1. An Example Program¶
The following program demonstrates the use of the library to analyze Vector Boolean Functions represented in decimal representation of its Truth Table.
#include <iostream>
#include <fstream>
#include "VBF.h"
int main(int argc, char *argv[])
{
using namespace VBFNS;
VBF F;
NTL::vec_long vec_F;
NTL::vec_ZZ c;
NTL::mat_GF2 A, T;
NTL::mat_ZZ W, LP, DP;
NTL::mat_ZZ Ac;
long a;
int n;
char file[33];
// Load VBF definitions
sprintf(file,"%s.dec",argv[1]);
ifstream input(file);
if(!input) {
cerr << "Error opening " << file << endl;
return 0;
}
input >> vec_F;
n = atoi(argv[2]);
F.putDecTT(vec_F,n);
input.close();
sprintf(file,"%s.anf",argv[1]);
ofstream output(file);
if(!output) {
cerr << "Error opening " << file << endl;
return 0;
}
A = ANF(F);
cout << "Argument Dimension = " << F.n() << endl;
cout << "Argument space has " << F.spacen() << " elements."<< endl;
cout << "Image Dimension = " << F.m() << endl;
cout << "Image space has " << F.spacem() << " elements." << endl << endl;
cout << "Writing Algebraic Normal Form to file: " << file << endl;
cout << "[Columns = Image components]" << endl;
output << A << endl;
output.close();
sprintf(file,"%s.tt",argv[1]);
ofstream output1(file);
if(!output1) {
cerr << "Error opening " << file << endl;
return 0;
}
T = TT(F);
cout << endl << "Writing Truth Table to file: " << file << endl;
cout << "[Columns = Image components]" << endl;
output1 << T << endl;
output1.close();
sprintf(file,"%s.wal",argv[1]);
ofstream output2(file);
if(!output2) {
cerr << "Error opening " << file << endl;
return 0;
}
W = Walsh(F);
cout << endl << "Writing Walsh Spectrum to file: " << file <<endl;
output2 << W << endl;
output2.close();
sprintf(file,"%s.lp",argv[1]);
ofstream output3(file);
if(!output3) {
cerr << "Error opening " << file << endl;
return 0;
}
LP = LAT(F);
cout << endl << "Writing Linear Profile to file: " << file << endl;
cout << "[To normalize divide by " << LP[0][0] << "]" << endl;
output3 << LP << endl;
output3.close();
sprintf(file,"%s.dp",argv[1]);
ofstream output4(file);
if(!output4) {
cerr << "Error opening " << file << endl;
return 0;
}
DP = DAT(F);
cout << endl << "Writing Differential Profile to file: " << file << endl;
cout << "[To normalize divide by " << DP[0][0] << "]" << endl;
output4 << DP << endl;
output4.close();
sprintf(file,"%s.pol",argv[1]);
ofstream output5(file);
if(!output5) {
cerr << "Error opening " << file << endl;
return 0;
}
cout << endl << "Writing the polynomials in ANF to file: " << file << endl;
Pol(output5,F);
output5.close();
sprintf(file,"%s.ls",argv[1]);
ofstream output6(file);
if(!output6) {
cerr << "Error opening " << file << endl;
return 0;
}
cout << endl << "Writing Linear structures to file: " << file << endl;
LS(output6,F);
output6.close();
sprintf(file,"%s.ac",argv[1]);
ofstream output7(file);
if(!output7) {
cerr << "Error opening " << file << endl;
return 0;
}
Ac = AC(F);
cout << endl << "Writing Autocorrelation Spectrum to file: " << file << endl;
output7 << Ac << endl;
output7.close();
sprintf(file,"%s.cy",argv[1]);
ofstream output8(file);
if(!output8) {
cerr << "Error opening " << file << endl;
return 0;
}
cout << endl << "Writing Cycle Structure to file: " << file << endl;
printCycle(output8,F);
output8.close();
cout << endl << "Nonlinearity: " << nl(F) << endl;
nlr(a,F,2);
cout << "Second order Nonlinearity: " << a << endl;
cout << "Linearity distance: " << ld(F) << endl;
cout << "Algebraic degree: " << deg(F) << endl;
cout << "Algebraic immunity: " << AI(F) << endl;
cout << "Absolute indicator: " << maxAC(F) << endl;
cout << "Sum-of-squares indicator: " << sigma(F) << endl;
cout << "Linear potential: " << lp(F) << endl;
cout << "Differential potential: " << dp(F) << endl;
cout << "Maximum Nonlinearity (if n is even): " << nlmax(F) << endl;
cout << "Maximum Linearity distance: " << ldmax(F) << endl;
int type;
typenl(type, F);
if (type == BENT) {
cout << "It is a bent function" << endl;
} else if (type == ALMOST_BENT) {
cout << "It is an almost bent function" << endl;
} else if (type == LINEAR) {
cout << "It is a linear function" << endl;
}
cout << "The fixed points are: " << endl;
cout << fixedpoints(F) << endl;
cout << "The negated fixed points are: " << endl;
cout << negatedfixedpoints(F) << endl;
cout << "Correlation immunity: " << CI(F) << endl;
if (Bal(F))
{
cout << "It is a balanced function" << endl;
} else
{
cout << "It is a non-balanced function" << endl;
}
cout << "The function is PC of degree " << PC(F) << endl;
return 0;
}
A set of files associated with the decimal representation of KASUMI S-boxes (S7.dec and S9.dec) are in the “Example” directory. If we use as input of the program above “S7.dec” (S7 Decimal representation), the output files would be:
- S7.ac (Autocorrelation Spectrum)
- S7.anf (ANF Table)
- S7.cy (Cycle structure)
- S7.dp (Differential Profile)
- S7.lp (Linear Profile)
- S7.ls (Linear structures): It is an empty vector because there is no linear structures
- S7.pol (Polynomial representation)
- S7.tt (Truth Table)
- S7.wal (Walsh Spectrum)
The same applies to S9 S-box analysis.
3.2. Compiling¶
There is only one library header files called “VBF.h”. You should include a statement like this in the program that make use of VBF library,
#include "VBF.h"
If the directory is not installed on the standard search path of your compiler you will also need to provide its location to the preprocessor as a command line flag. The default location of the ‘NTL’ directory is ‘/usr/local/include/NTL’. A typical compilation command for a source file ‘ex.cpp’ with the GNU C++ compiler g++ included in a Makefile is,
GPP=g++
LIBS=-lntl
NTLINC= -I/usr/local/include -L/usr/local/lib
ex: ex.cpp VBF.h
$(GPP) $(NTLINC) -Wall ex.cpp -o ex.exe $(LIBS)
This results in an executable file ‘ex.exe’ if the following command is executed:
$ make ex
In order to execute the example program included in the “Example” program with S7.dec and S9.dec, the following commands must be executed:
$ ./ex.exe S7 7
$ ./ex.exe S9 9
3.3. How to evaluate new algorithms¶
In order to evaluate an algorithm, we need to obtain a representation of this algorithm that can be used to initialize a VBF class. These representations are the Truth Table, Hexadecimal representation (only for Boolean functions), Decimal representation of its Truth Table, its trace together with the irreducible polynomial, Polynomials in ANF, ANF Table, Characteristic Function, Walsh Spectrum, permutation representation, Expansion and Compression DES vector representation, DES S-Box representation.
As an example we are going to describe the procedure followed to evaluate FI function in KASUMI algorithm. We used an implementation of KASUMI in c as you can see below:
/*-----------------------------------------------------------------------
* Kasumi.c
*-----------------------------------------------------------------------
*
* A sample implementation of KASUMI, the core algorithm for the
* 3GPP Confidentiality and Integrity algorithms.
*
* This has been coded for clarity, not necessarily for efficiency.
*
* This will compile and run correctly on both Intel (little endian)
* and Sparc (big endian) machines. (Compilers used supported 32-bit ints).
*
* Version 1.1 08 May 2000
*
*-----------------------------------------------------------------------*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include "VBF.h"
#include "Kasumi.h"
/*--------- 16 bit rotate left ------------------------------------------*/
#define ROL16(a,b) (u16)((a<<b)|(a>>(16-b)))
/*------- unions: used to remove "endian" issues ------------------------*/
typedef union {
u32 b32;
u16 b16[2];
u8 b8[4];
} DWORD;
typedef union {
u16 b16;
u8 b8[2];
} WORD;
/*-------- globals: The subkey arrays -----------------------------------*/
static u16 KLi1[8], KLi2[8];
static u16 KOi1[8], KOi2[8], KOi3[8];
static u16 KIi1[8], KIi2[8], KIi3[8];
/*---------------------------------------------------------------------
* FI()
* The FI function (fig 3). It includes the S7 and S9 tables.
* Transforms a 16-bit value.
*---------------------------------------------------------------------*/
static u16 FI( u16 in, u16 subkey )
{
u16 nine, seven;
static u16 S7[] = {
54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33,
55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,
53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,
20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98,
117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87,
112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66,
102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,
64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3};
static u16 S9[] = {
167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397,
183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,
175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400,
95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,
165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,
501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,
232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,
344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,
487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,
475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,
363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,
439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,
465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282,
173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,
280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,
132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374,
35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285,
50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32,
72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,
185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190,
1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,
336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18,
47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,
414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,
266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,
311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,
485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,
312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398,
284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451,
97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,
438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380,
43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461};
/* The sixteen bit input is split into two unequal halves, *
* nine bits and seven bits - as is the subkey */
nine = (u16)(in>>7);
seven = (u16)(in&0x7F);
/* Now run the various operations */
nine = (u16)(S9[nine] ^ seven);
seven = (u16)(S7[seven] ^ (nine & 0x7F));
seven ^= (subkey>>9);
nine ^= (subkey&0x1FF);
nine = (u16)(S9[nine] ^ seven);
seven = (u16)(S7[seven] ^ (nine & 0x7F));
in = (u16)((seven<<9) + nine);
return( in );
}
/*---------------------------------------------------------------------
* FO()
* The FO() function.
* Transforms a 32-bit value. Uses <index> to identify the
* appropriate subkeys to use.
*---------------------------------------------------------------------*/
static u32 FO( u32 in, int index )
{
u16 left, right;
u16 l,r;
/* Split the input into two 16-bit words */
left = (u16)(in>>16);
right = (u16) in;
l = left;
r = right;
/* Now apply the same basic transformation three times */
left ^= KOi1[index];
left = FI( left, KIi1[index] );
left ^= right;
right ^= KOi2[index];
right = FI( right, KIi2[index] );
right ^= left;
left ^= KOi3[index];
left = FI( left, KIi3[index] );
left ^= right;
in = (((u32)right)<<16)+left;
return( in );
}
/*---------------------------------------------------------------------
* FL()
* The FL() function.
* Transforms a 32-bit value. Uses <index> to identify the
* appropriate subkeys to use.
*---------------------------------------------------------------------*/
static u32 FL( u32 in, int index )
{
u16 l, r, a, b;
/* split out the left and right halves */
l = (u16)(in>>16);
r = (u16)(in);
/* do the FL() operations */
a = (u16) (l & KLi1[index]);
r ^= ROL16(a,1);
b = (u16)(r | KLi2[index]);
l ^= ROL16(b,1);
/* put the two halves back together */
in = (((u32)l)<<16) + r;
return( in );
}
/*---------------------------------------------------------------------
* Kasumi()
* the Main algorithm (fig 1). Apply the same pair of operations
* four times. Transforms the 64-bit input.
*---------------------------------------------------------------------*/
void Kasumi( u8 *data )
{
u32 left, right, temp;
DWORD *d;
int n;
/* Start by getting the data into two 32-bit words (endian correct) */
d = (DWORD*)data;
left = (((u32)d[0].b8[0])<<24)+(((u32)d[0].b8[1])<<16)
+(d[0].b8[2]<<8)+(d[0].b8[3]);
right = (((u32)d[1].b8[0])<<24)+(((u32)d[1].b8[1])<<16)
+(d[1].b8[2]<<8)+(d[1].b8[3]);
n = 0;
do{
temp = FL( left, n );
temp = FO( temp, n++ );
right ^= temp;
temp = FO( right, n );
temp = FL( temp, n++ );
left ^= temp;
}while( n<=7 );
/* return the correct endian result */
d[0].b8[0] = (u8)(left>>24); d[1].b8[0] = (u8)(right>>24);
d[0].b8[1] = (u8)(left>>16); d[1].b8[1] = (u8)(right>>16);
d[0].b8[2] = (u8)(left>>8); d[1].b8[2] = (u8)(right>>8);
d[0].b8[3] = (u8)(left); d[1].b8[3] = (u8)(right);
}
/*---------------------------------------------------------------------
* KeySchedule()
* Build the key schedule. Most "key" operations use 16-bit
* subkeys so we build u16-sized arrays that are "endian" correct.
*---------------------------------------------------------------------*/
void KeySchedule( u8 *k )
{
static u16 C[] = {
0x0123,0x4567,0x89AB,0xCDEF, 0xFEDC,0xBA98,0x7654,0x3210 };
u16 key[8], Kprime[8];
WORD *k16;
int n;
/* Start by ensuring the subkeys are endian correct on a 16-bit basis */
k16 = (WORD *)k;
for( n=0; n<8; ++n )
key[n] = (u16)((k16[n].b8[0]<<8) + (k16[n].b8[1]));
/* Now build the K'[] keys */
for( n=0; n<8; ++n )
Kprime[n] = (u16)(key[n] ^ C[n]);
/* Finally construct the various sub keys */
for( n=0; n<8; ++n )
{
KLi1[n] = ROL16(key[n],1);
KLi2[n] = Kprime[(n+2)&0x7];
KOi1[n] = ROL16(key[(n+1)&0x7],5);
KOi2[n] = ROL16(key[(n+5)&0x7],8);
KOi3[n] = ROL16(key[(n+6)&0x7],13);
KIi1[n] = Kprime[(n+4)&0x7];
KIi2[n] = Kprime[(n+3)&0x7];
KIi3[n] = Kprime[(n+7)&0x7];
}
}
In the main procedure, we defined an algorithm to obtain the Truth Table of FI function for the key values that are between “first” and “last” parameters.
int main(int argc, char *argv[])
{
using namespace VBFNS;
u16 l,k;
long i,j,first,last;
std::stringstream number;
char file[33];
NTL::vec_GF2 vn,vs;
first = atoi(argv[1]);
last = atoi(argv[2]);
for (i = first; i <= last; i++)
{
sprintf(file,"%ld.tt",i);
ofstream output(file);
if(!output)
{
cerr << "Error opening " << file << endl;
return 0;
}
output << "[";
number << i;
number >> std::hex >> k;
for (j = 0; j < 65536; j++)
{
number << j;
number >> std::hex >> l;
l = FI( l, k );
vn = to_vecGF2(l,16);
output << vn << endl;
}
output << "]" << endl;
output.close();
}
}