Script started on Thu May 30 21:51:28 2002
[crandaj@node52-60
cryptanalysis]$ cat pc.cpp
/******************************
*
* pc.cpp
* Jedidiah Crandall, crandaj@erau.edu
* Generates plaintext/ciphertext pairs in a modified version of S-DES
* which has three rounds and no initial or final permutation
*
*******************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdlib.h>
#define BYTE unsigned char
char key[25];
char *K1 = &key[0];
char *K2 = &key[8];
char *K3 = &key[16];
void SetKey(unsigned long int SetMe)
{
int i;
unsigned long int n;
for (i = 0, n = 0x800000; i <= 31; i++, n /= 2)
{
if (SetMe & n)
key[i] = '1';
else
key[i] = '0';
}
key[32] = '\0';
}
int SBox0[4][4] =
{
{1, 0, 3, 2},
{3, 2, 1, 0},
{0, 2, 1, 3},
{3, 1, 3, 2}
};
int SBox1[4][4] =
{
{0, 1, 2, 3},
{2, 0, 1, 3},
{3, 0, 1, 0},
{2, 1, 0, 3}
};
BYTE BinaryToByte(char *Binary)
{
int n, i;
BYTE ReturnMe = 0;
for (i = 0, n = 128; i <= 7; i++, n /= 2)
{
switch(Binary[i])
{
case '0': break;
case '1':
ReturnMe += n;
break;
default:
puts("BinaryToByte failed");
exit(0);
break;
}
}
return ReturnMe;
}
void ByteToBinary(char *pBinary, BYTE TheByte)
{
int i;
BYTE n;
for (i = 0, n = 0x80; i <= 7; i++, n >>= 1)
{
if (TheByte & n)
pBinary[i] = '1';
else
pBinary[i] = '0';
}
pBinary[8] = '\0';
}
void S0(char *pDest, char *pSrc)
{
int Row = (pSrc[0] - '0') * 2 + (pSrc[3] - '0');
int Col = (pSrc[1] - '0') * 2 + (pSrc[2] - '0');
BYTE LookUp = SBox0[Row][Col];
pDest[0] = '0' + ((LookUp & 0x02) >> 1);
pDest[1] = '0' + (LookUp & 0x01);
pDest[2] = '\0';
}
void S1(char *pDest, char *pSrc)
{
int Row = (pSrc[0] - '0') * 2 + (pSrc[3] - '0');
int Col = (pSrc[1] - '0') * 2 + (pSrc[2] - '0');
BYTE LookUp = SBox1[Row][Col];
pDest[0] = '0' + ((LookUp & 0x02) >> 1);
pDest[1] = '0' + (LookUp & 0x01);
pDest[2] = '\0';
}
void P4(char *pDest, char *pS0Output, char *pS1Output)
{
pDest[0] = pS0Output[1];
pDest[1] = pS1Output[1];
pDest[2] = pS1Output[0];
pDest[3] = pS0Output[0];
pDest[4] = '\0';
}
void XOR4(char *pDest, char *Operand1, char *Operand2)
{
int i;
BYTE a, b;
for (i = 0; i <= 3; i++)
{
a = Operand1[i] - '0';
b = Operand2[i] - '0';
pDest[i] = '0' + (a ^ b);
}
pDest[4] = '\0';
}
void EP(char *pDest, char *pSrc)
{
pDest[0] = pSrc[3];
pDest[1] = pSrc[0];
pDest[2] = pSrc[1];
pDest[3] = pSrc[2];
pDest[4] = pSrc[1];
pDest[5] = pSrc[2];
pDest[6] = pSrc[3];
pDest[7] = pSrc[0];
pDest[8] = '\0';
}
void f(char *pDest, char *pSrc, char *Subkey)
{
char *pLeft = &pSrc[0], *pRight = &pSrc[4];
char OutputFromEP[9];
char OutputFromXOR8[9];
BYTE XOR8Result;
char *pS0Input = &OutputFromXOR8[0];
char *pS1Input = &OutputFromXOR8[4];
char S0Output[3];
char S1Output[3];
char P4Output[5];
char XOR4Output[5];
EP(OutputFromEP, pRight);
XOR8Result = BinaryToByte(OutputFromEP) ^ BinaryToByte(Subkey);
ByteToBinary(OutputFromXOR8, XOR8Result);
S0(S0Output, pS0Input);
S1(S1Output, pS1Input);
P4(P4Output, S0Output, S1Output);
XOR4(XOR4Output, P4Output, pLeft);
memcpy(pDest, XOR4Output, 4);
memcpy(&pDest[4], pRight, 4);
pDest[8] = '\0';
}
void SW(char *pDest, char *pSrc)
{
pDest[0] = pSrc[4];
pDest[1] = pSrc[5];
pDest[2] = pSrc[6];
pDest[3] = pSrc[7];
pDest[4] = pSrc[0];
pDest[5] = pSrc[1];
pDest[6] = pSrc[2];
pDest[7] = pSrc[3];
pDest[8] = '\0';
}
BYTE SDES(BYTE nPlaintext)
{
BYTE nCiphertext;
char Plaintext[9];
char OutOffK1[9];
char IntofK2[9];
char OutOffK2[9];
char IntofK3[9];
char OutOffK3[9];
ByteToBinary(Plaintext, nPlaintext);
f(OutOffK1, Plaintext, K1);
SW(IntofK2, OutOffK1);
f(OutOffK2, IntofK2, K2);
SW(IntofK3, OutOffK2);
f(OutOffK3, IntofK3, K3);
nCiphertext = BinaryToByte(OutOffK3);
return nCiphertext;
}
int main()
{
unsigned int DidItAlready[256];
unsigned int Plaintext;
unsigned int NumberDone;
unsigned long int TheKey;
memset(DidItAlready, 0, 256 * sizeof(unsigned int));
fprintf(stderr, "You must enter a hexadecimal key, such as 22B8FA\n");
fprintf(stderr, "The last two hex digits (FA) are the 8-bit subkey for the last round.\n");
fprintf(stderr, "Please enter the key you'd like to use:\n");
scanf("%x", &TheKey);
SetKey(TheKey);
srand(2233);
NumberDone = 0;
while (NumberDone < 100)
{
Plaintext = rand() % 256;
if (!DidItAlready[Plaintext])
{
DidItAlready[Plaintext] = 1;
printf("%d\t%d\n", Plaintext, SDES(Plaintext));
NumberDone++;
}
}
printf("\n");
return 0;
}
[crandaj@node52-60
cryptanalysis]$ cat linear.cpp
/****************************************
* linear.cpp
* Jedidiah Crandall, crandaj@erau.edu
* Does linear cryptanalysis on plaintext/ciphertext pairs created with pc.cpp
*****************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#include <stdlib.h>
#define BYTE unsigned char
int SBox0[4][4] =
{
{1, 0, 3, 2},
{3, 2, 1, 0},
{0, 2, 1, 3},
{3, 1, 3, 2}
};
int SBox1[4][4] =
{
{0, 1, 2, 3},
{2, 0, 1, 3},
{3, 0, 1, 0},
{2, 1, 0, 3}
};
BYTE BinaryToByte(char *Binary)
{
int n, i;
BYTE ReturnMe = 0;
for (i = 0, n = 128; i <= 7; i++, n /= 2)
{
switch(Binary[i])
{
case '0': break;
case '1':
ReturnMe += n;
break;
default:
puts("BinaryToByte failed");
exit(0);
break;
}
}
return ReturnMe;
}
void ByteToBinary(char *pBinary, BYTE TheByte)
{
int i;
BYTE n;
for (i = 0, n = 0x80; i <= 7; i++, n >>= 1)
{
if (TheByte & n)
pBinary[i] = '1';
else
pBinary[i] = '0';
}
pBinary[8] = '\0';
}
void S0(char *pDest, char *pSrc)
{
int Row = (pSrc[0] - '0') * 2 + (pSrc[3] - '0');
int Col = (pSrc[1] - '0') * 2 + (pSrc[2] - '0');
BYTE LookUp = SBox0[Row][Col];
pDest[0] = '0' + ((LookUp & 0x02) >> 1);
pDest[1] = '0' + (LookUp & 0x01);
pDest[2] = '\0';
}
void S1(char *pDest, char *pSrc)
{
int Row = (pSrc[0] - '0') * 2 + (pSrc[3] - '0');
int Col = (pSrc[1] - '0') * 2 + (pSrc[2] - '0');
BYTE LookUp = SBox1[Row][Col];
pDest[0] = '0' + ((LookUp & 0x02) >> 1);
pDest[1] = '0' + (LookUp & 0x01);
pDest[2] = '\0';
}
void P4(char *pDest, char *pS0Output, char *pS1Output)
{
pDest[0] = pS0Output[1];
pDest[1] = pS1Output[1];
pDest[2] = pS1Output[0];
pDest[3] = pS0Output[0];
pDest[4] = '\0';
}
void XOR4(char *pDest, char *Operand1, char *Operand2)
{
int i;
BYTE a, b;
for (i = 0; i <= 3; i++)
{
a = Operand1[i] - '0';
b = Operand2[i] - '0';
pDest[i] = '0' + (a ^ b);
}
pDest[4] = '\0';
}
void EP(char *pDest, char *pSrc)
{
pDest[0] = pSrc[3];
pDest[1] = pSrc[0];
pDest[2] = pSrc[1];
pDest[3] = pSrc[2];
pDest[4] = pSrc[1];
pDest[5] = pSrc[2];
pDest[6] = pSrc[3];
pDest[7] = pSrc[0];
pDest[8] = '\0';
}
unsigned int Parity(BYTE n)
{
unsigned int NumberOfOnes = 0;
unsigned int Bitmask;
for (Bitmask = 0x01; Bitmask <= 0x80; Bitmask *= 2)
{
if (n & Bitmask)
NumberOfOnes++;
}
return NumberOfOnes % 2;
}
struct t_PCPair
{
unsigned int Plaintext;
unsigned int Ciphertext;
};
t_PCPair PCPairs[100];
struct t_Candidate
{
unsigned int Subkey;
unsigned int Deviation;
};
t_Candidate Candidates[256];
void BubbleSort()
{
unsigned int i, j;
t_Candidate Temp;
for (i = 0; i <= 255; i++)
for (j = i; j <= 255; j++)
{
if (Candidates[i].Deviation < Candidates[j].Deviation)
{
Temp = Candidates[i];
Candidates[i] = Candidates[j];
Candidates[j] = Temp;
}
}
}
int main()
{
unsigned int Loop;
unsigned int Subkey;
unsigned int Q;
unsigned int S;
unsigned int RightHalfOfCiphertext;
unsigned int RightHalfOfPlaintext;
unsigned int Arrange1, Arrange2;
unsigned int LeftHalfOfCiphertext;
char sRightHalfOfCiphertext[9];
char sEPOutput[9];
char sOutputFromXOR8[9];
BYTE XOR8Result;
char *pS0Input = &sOutputFromXOR8[0];
char *pS1Input = &sOutputFromXOR8[4];
char sS0Output[3];
char sS1Output[3];
char sP4Output[9];
char sLeftHalfOfCiphertext[9];
char sEPInput[5];
unsigned int S0Input;
unsigned int S0Output;
unsigned int S1Input;
unsigned int S1Output;
// These are the linear approximations of the S-boxes
// They are of the form:
// {4-bit bitmask for S-box input, 2-bit bitmask for S-box output, what it should equal}
// So {0xa, 0x1, 1} means that the input bits masked by 0xa (1010 - the first and the
// third) added with the output bits masked by 0x1 (01 -just the second one) modulo 2
// should equal 1 more than 50% of the time
unsigned int S0Approx[16][3] =
{
{0xf, 0x3, 1},
{0x2, 0x1, 1},
{0xa, 0x1, 1},
{0xb, 0x2, 1},
{0xd, 0x1, 1},
{0x3, 0x3, 1},
{0x7, 0x3, 1},
{0xa, 0x3, 1},
{0xf, 0x1, 0},
{0x2, 0x3, 0},
{0x6, 0x3, 0},
{0xb, 0x3, 0},
{0x3, 0x2, 0},
{0x5, 0x1, 0},
{0x5, 0x2, 0},
{0xd, 0x2, 0}
};
unsigned int S1Approx[16][3] =
{
{0x6, 0x2, 1},
{0x2, 0x3, 1},
{0xd, 0x3, 1},
{0x3, 0x1, 1},
{0x5, 0x1, 1},
{0xd, 0x1, 1},
{0x2, 0x2, 1},
{0x3, 0x2, 1},
{0x5, 0x3, 0},
{0x6, 0x3, 0},
{0x7, 0x2, 0},
{0x7, 0x3, 0},
{0xb, 0x3, 0},
{0xc, 0x2, 0},
{0xd, 0x2, 0},
{0xb, 0x1, 0}
};
unsigned int TryEquation;
unsigned int Good;
char sPlaintext[4], sCiphertext[4];
// First, we want to read in 100 plaintext/ciphertext pairs
for (Loop = 0; Loop < 100; Loop++)
{
scanf("%s\t%s", sPlaintext, sCiphertext);
PCPairs[Loop].Plaintext = atoi(sPlaintext);
PCPairs[Loop].Ciphertext = atoi(sCiphertext);
}
// Now, for every possible third-round subkey we want to know how often our linear
// approximations for the S-boxes in the second round hold
for (Subkey = 0; Subkey <= 255; Subkey++)
{
Good = 0;
for (Loop = 0; Loop < 100; Loop++)
{
// Q is the output of the S-boxes in the second round
// We can determine this from the right half of the plaintext
// and the right half of the ciphertext
RightHalfOfCiphertext = PCPairs[Loop].Ciphertext & 0x0f;
RightHalfOfPlaintext = PCPairs[Loop].Plaintext & 0x0f;
Arrange1 = (RightHalfOfCiphertext & 0x01) << 3;
Arrange1 |= (RightHalfOfCiphertext & 0x08) >> 1;
Arrange1 |= (RightHalfOfCiphertext & 0x02);
Arrange1 |= (RightHalfOfCiphertext & 0x04) >> 2;
Arrange2 = (RightHalfOfPlaintext & 0x01) << 3;
Arrange2 |= (RightHalfOfPlaintext & 0x08) >> 1;
Arrange2 |= (RightHalfOfPlaintext & 0x02);
Arrange2 |= (RightHalfOfPlaintext & 0x04) >> 2;
Q = Arrange1 ^ Arrange2;
// S is supposed to be the input to the XOR8 in the second round
// which we can make a guess at by guessing the subkey for round 3.
// If we guessed the right subkey for round 3 then we have the actual
// input to the XOR8 in round 2 (S) and the output (Q) of the S-boxes so
// we would expect our linear approximations to hold either true or false
// more than half the time. If we have made a bad guess for the subkey
// in the third round then our S and Q in the second round won't make any
// sense so our linear approximations will hold about half the time, just
// as if we had selected S and Q randomly.
LeftHalfOfCiphertext = PCPairs[Loop].Ciphertext & 0xf0;
ByteToBinary(sRightHalfOfCiphertext, RightHalfOfCiphertext);
EP(sEPOutput, &sRightHalfOfCiphertext[4]);
XOR8Result = BinaryToByte(sEPOutput) ^ Subkey;
ByteToBinary(sOutputFromXOR8, XOR8Result);
S0(sS0Output, pS0Input);
S1(sS1Output, pS1Input);
sP4Output[0] = '0';
sP4Output[1] = '0';
sP4Output[2] = '0';
sP4Output[3] = '0';
P4(&sP4Output[4], sS0Output, sS1Output);
ByteToBinary(sLeftHalfOfCiphertext, LeftHalfOfCiphertext);
XOR4(sEPInput, &sP4Output[4], sLeftHalfOfCiphertext);
EP(sEPOutput, sEPInput);
S = BinaryToByte(sEPOutput);
S0Input = (S & 0xf0) >> 4;
S1Input = (S & 0x0f);
S0Output = (Q & 0x0C) >> 2;
S1Output = (Q & 0x03);
for (TryEquation = 0; TryEquation <= 15; TryEquation++)
{
// Now we want to isolate the correct bits for each equation and add them all up
// modulo 2. This parity stuff is just a fancy way of doing this.
if ((Parity(S0Input ^ S0Approx[TryEquation][0]) ^ Parity(S0Output ^
S0Approx[TryEquation][1])) == S0Approx[TryEquation][2])
Good++;
if ((Parity(S1Input ^ S1Approx[TryEquation][0]) ^ Parity(S1Output ^
S1Approx[TryEquation][1])) == S1Approx[TryEquation][2])
Good++;
}
}
Candidates[Subkey].Subkey = Subkey;
Candidates[Subkey].Deviation = abs(1600 - Good);
}
// The good candidates for a subkey K3 are the ones with high deviations
BubbleSort();
printf("Likely candidates for subkey K3:\n\n");
printf("Subkey\tDeviation\n-----------------\n");
for (Loop = 0; Loop <= 4; Loop++)
{
printf("%02x\t%d\n", Candidates[Loop].Subkey, Candidates[Loop].Deviation);
}
return 0;
}
[crandaj@node52-60
cryptanalysis]$ ./pc > pcout.txt
You must enter a hexadecimal key, such as 22B8FA
The last two hex digits (FA) are the 8-bit subkey for the last round.
Please enter the key you'd like to use:
b2669c
[crandaj@node52-60
cryptanalysis]$ cat pcout.txt
77 48
200 72
100 239
82 54
167 127
63 30
40 217
181 28
96 49
87 242
34 238
231 163
58 100
56 124
1 186
127 130
90 123
61 8
50 155
20 226
86 250
246 157
81 216
103 182
242 36
37 165
140 128
157 108
88 209
234 129
32 141
60 113
199 208
153 51
124 205
249 57
188 196
158 225
224 132
214 198
225 90
117 3
48 43
31 105
168 210
68 116
254 101
59 227
198 88
101 64
45 91
236 93
241 188
202 235
180 240
65 61
240 161
43 212
219 237
85 4
212 45
17 22
69 175
7 41
27 34
150 19
76 121
36 14
144 12
42 122
203 46
135 254
221 18
120 176
195 94
33 224
95 81
133 218
161 107
104 55
176 111
189 6
80 229
206 138
156 53
5 78
213 177
183 232
3 103
118 153
148 131
109 67
74 96
28 162
107 154
248 149
252 184
160 248
21 120
186 195
[crandaj@node52-60
cryptanalysis]$ cat pcout.txt |
./linear
Likely candidates for subkey K3:
Subkey Deviation
-----------------
9c 336
bc 336
1b 212
3b 212
4c 186
[crandaj@node52-60
cryptanalysis]$ exit
exit
Script done on Thu May 30 21:52:43 2002
This was created as part of the Cryptography Module
of NSF Award No. 0113627: "Increasing
Security Expertise in Aviation-oriented Computing Education: A Modular Approach",
at Embry-Riddle Aeronautical University in Prescott, Arizona.
