CSc 8370 fall '02
Stream Ciphers Part 2
Stream ciphers are an approximation to one time ciphers where the key is derived by a pseudo-random algorithm rather than a truly random source. The more random the initialization of the pseudo-random source, the better the cipher will be. (Chapter 10 in Viega and McGraw describes some of these issues.) However, if a truly random key is used (i.e. the number of microseconds mod 2^64 since January 1 1970) then it has to be saved and communicated as part of the key.
The key stream is combined with the clear text (the message) using a simple and invertible operation. The most common operation is XOR, but modular addition will work just as well.
There are two serious problems with stream ciphers
If the plain text is known, then the key stream is available.
The message can be altered without decryption.
For example, suppose that a message could be originated from a bank saying to pay an account a certain amount of money. If this message was encoded with a stream cipher it might go from "PAY ACCOUNT #123456 0000010 cents" to some random looking string. None the less a clever crook who knew the format could change a few bits and cause the decryption to change to "PAY ACCOUNT #123456 1000010 cents" or change the account number.
The ability to forge messages is a serious drawback for these schemes, and one reason block ciphers like DES and AES are still used. The generic solution is to add some sort of message authentication code (or MAC) to the message. If the code checks out, the message can be accepted as valid. MAC's are generated by cryptographic hash functions like SHA and MD5. We will cover the structure of these later. (Viega & McGraw 457-462 describe these and their use).
Security Issues for a MAC
There are four basic way's a MAC could be used
Message MAC on Encryption
Message MAC on clear
Message + MAC on clear
Message + MAC on clear MAC on Encryption
These do not give equivalent security. Why?
Class experiment #2.
The file classcipher2 is encrypted with the program defined by rc4.cpp. There is a subtle bug in the implementation that makes it weak. What is it?
The key may be in the file /usr/share/lib/dict/words. If the text is English, define a strategy to test these possible keys.
Implement this strategy. (there are only 25,000 or so words in /usr/share/lib/dict/words) There are two versions of the file in dst32.
classcipher2.linux, and classcipher2.sun will decrypt on the respective machines. (word order differences make the cipher engines not quite equivalent).
C++ on Yamacraw.
Mr. Hundewale told me how to compile C++ on Yamacraw.
g++ -m64 -R /usr/local/lib/sparcv9 file.cpp
if you use -m64 LD_LIBRARY_PATH_64 needs to be set to /usr/local/lib/sparcv9
in sh LD_LIBRARY_PATH_64=/usr/local/lib/sparcv9
followed by export LD_LIBRARY_PATH_64
in sh PATH=$PATH:/usr/local/bin
followed by export PATH
in tcsh or csh use setenv
/*
// RC4.cpp
\\
// rc4 classes for a generator
\\
// not a really good implementation (64 bit limit with long)
\\ but good enough for CSc8370 where we're going to play with
// shorter keys anyway.
\\
//
\\ there is a subtle bug in this code, so don't use it for production
// (at least until you've fixed it!!!!)
\\
// (c) 2002 Robert W. Harrison
*/
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
/*
// yes these are the C IO libraries
\\ yes i know about streamio
// no i don't like it.
*/
using namespace std; // DUH
class rc4
{
// private space
unsigned char *S; // the keyspace
unsigned char icount,jcount; // ok i could use byte
public:
rc4( long seed);
~rc4( void );
unsigned char next( void );
};
rc4::rc4( long seed)
{
int i,j;
unsigned char *K;
K = new unsigned char[256];
S = new unsigned char[256];
union {
unsigned char bytes[8];
unsigned long lseed;
} ;
lseed = (unsigned long) seed;
for( i=0; i< 256; i+= 8)
{
//
// this loop is written out so the code will be faster
// not much faster, but it will help if
// we do a keysearch
//
K[i ] = bytes[0];
K[i+1] = bytes[1];
K[i+2] = bytes[2];
K[i+3] = bytes[3];
K[i+4] = bytes[4];
K[i+5] = bytes[5];
K[i+6] = bytes[6];
K[i+7] = bytes[7];
}
for( i=0; i< 256; i++)
{
S[i] = i;
}
j = 0;
for( i=0; i< 256; i++)
{
j = (j + S[i] + K[i])%256;
unsigned char x;
x = S[i];
S[i] = S[j];
S[j] = x;
}
icount = 0;
jcount = 0;
delete [] K; // no memory leaks, right?
}
rc4::~rc4(void)
{
int i;
// before we free the S buffer we need to ensure that it is wiped
// (paranoid, well maybe)
for( i=0; i< 256; i++)
S[i] = 0;
icount = 0;
jcount = 0;
delete [] S;
}
unsigned char rc4::next(void)
{
icount = (icount+1)%256;
jcount = (jcount+S[icount])%256;
unsigned char x;
x = S[icount];
S[icount] = S[jcount];
S[jcount] = x;
int t;
t = (S[icount] + S[jcount])%256;
return S[t];
}
// end of class definition
int main( int argc, char *argv[])
{
int i; // i tend to still declare these to make the code portable
if( argc < 2)
{
fprintf(stderr," Usage is rc4 key < file > file\n");
exit(0);
}
union {
unsigned char key[8];
long seed;
};
for( i=0; i< 8; i++)
{
key[i] = 0;
}
for( i=0; i< 8; i++)
{
char *cp ;
cp = argv[1];
if( cp[i] > '\0')
key[i] = cp[i];
else
break;
}
rc4 *a_stream;
a_stream = new rc4( seed );
unsigned char achar;
while( (i = fgetc(stdin)) != EOF)
{
achar = i;
achar = achar ^ a_stream->next();
fputc( achar, stdout);
}
}// end of main */
/* again in C because of G++ problems on yamacraw
*
* DIGRAM adfgvx to mono, check for scrambled
*
*/
#include <stdio.h>
#include <stdlib.h>
/* we have to use this in-elegant construct here
* could use the const construct as well, but this (although depricated)
* is more portable
*/
#define MAXIMUM 10000
main()
{
int i,j,stride;
int in_message;
char message[MAXIMUM];
char unscramble[MAXIMUM];
float phi1( char *, int);
float phi2( char *, int);
float phi3( char *, int);
char *trans = "adfgvx";
/* translate from a-x to 0-5 */
in_message = 0;
while( ( i = fgetc(stdin)) != EOF)
{
if( i == 0 ) continue;
/* NULL terminated strings end in 0 */
for( j=0; j<6; j++)
if( i == trans[j]) { break;}
if( j > 5) {printf("%c %d\n",i,i); exit(0);}
message[ in_message++] = j;
}
/* ok now for each number from 1 to in_message/2
* perform the unscramble
* then calculate phi
*/
for( stride = 1; stride < in_message/2; stride++)
{
int lll = 0;
for( j=0; j< stride; j++)
for( i=0; i< in_message; i+= stride)
{
int l;
l = i + j;
if( l >= in_message) continue;
if( lll >= in_message) continue;
unscramble[l] = message[lll++];
}
/* dump_message(unscramble, in_message); */
printf(" %d %f %f %f ", stride, phi1( unscramble, in_message),phi2(unscramble, in_message), phi3(unscramble,in_message));
printf(" %f %f %f \n", 36.*phi1( unscramble, in_message),36.*36.*phi2(unscramble, in_message), 36.*36.*36.*phi3(unscramble,in_message));
}/* stride */
}
int dump_message( char *m, int in)
{
int i,j;
char *trans = "adfgvx";
j = 0;
for( i=0; i< in; i++)
{
printf("%c",trans[m[i]]);
if( j %80 == 0) printf("\n");
j++;
}
printf("\n");
}
float phi1(char *mess, int in_it)
{
int count[36];
int icount;
int i,j,k;
int aletter;
float phi;
/* yes there is a way do to this at initialization time */
for( i=0; i< 36; i++)
{
count[i] = 0;
}
for( icount = 0; icount < in_it; icount += 2)
{
aletter = mess[icount]*6 + mess[icount+1];
count[aletter]++;
}
/* so now have the raw 1,2,3mer counts */
/* now to make the phi functions */
phi = 0.;
aletter = 0;
for( i=0; i< 36; i++)
{
aletter += count[i];
phi += count[i]*(count[i] -1);
}
return phi/(aletter*(aletter-1));
}/* end of phi1 */
float phi2(char *mess, int in_it)
{
int count[36],count2[36][36],count3[36][36][36];
int icount;
int i,j,k;
int aletter;
int bletter;
int cletter;
float phi;
/* this is a little bit wasteful because i'm repeating code that
* isn't necessary
*
* tough cookies, stale cheese and all that.
*/
/* yes there is a way do to this at initialization time */
for( i=0; i< 36; i++)
{
count[i] = 0;
for( j=0; j< 36; j++)
{
count2[i][j] = 0;
for( k=0; k< 36; k++)
{
count3[i][j][k] = 0;
}
}
}
bletter = -1;
cletter = -1;
for( icount = 0; icount < in_it; icount += 2)
{
aletter = mess[icount]*6 + mess[icount+1];
count[aletter]++;
if( bletter >= 0)
{
count2[aletter][bletter] ++;
if( cletter >= 0)
{
count3[aletter][bletter][cletter]++;
}
}
/* right shift (ugly ain't it?) */
cletter = bletter;
bletter = aletter;
}
/* so now have the raw 1,2,3mer counts */
/* now to make the phi functions */
phi = 0.;
aletter = 0;
for( j=0; j< 36; j++)
for( i=0; i< 36; i++)
{
aletter += count2[i][j];
phi += count2[i][j]*(count2[i][j] -1);
}
return phi/((aletter-1)*aletter);
}/* end of phi2 */
float phi3(char *mess, int in_it)
{
int count[36],count2[36][36],count3[36][36][36];
int icount;
int i,j,k;
int aletter;
int bletter;
int cletter;
float phi;
/* this is a little bit wasteful because i'm repeating code that
* isn't necessary
*
* tough cookies, stale cheese and all that.
*/
/* yes there is a way do to this at initialization time */
for( i=0; i< 36; i++)
{
count[i] = 0;
for( j=0; j< 36; j++)
{
count2[i][j] = 0;
for( k=0; k< 36; k++)
{
count3[i][j][k] = 0;
}
}
}
bletter = -1;
cletter = -1;
for( icount = 0; icount < in_it; icount += 2)
{
aletter = mess[icount]*6 + mess[icount+1];
count[aletter]++;
if( bletter >= 0)
{
count2[aletter][bletter] ++;
if( cletter >= 0)
{
count3[aletter][bletter][cletter]++;
}
}
/* right shift (ugly ain't it?) */
cletter = bletter;
bletter = aletter;
}
/* so now have the raw 1,2,3mer counts */
/* now to make the phi functions */
phi = 0.;
aletter = 0;
for( k=0; k< 36; k++)
for( j=0; j< 36; j++)
for( i=0; i< 36; i++)
{
aletter += count3[i][j][k];
phi += count3[i][j][k]*(count3[i][j][k] -1);
}
return phi/((aletter-1)*aletter);
}/* end of main */
scramble, phi_monomer, dimer, trimer, normalized monomer, dimer, trimer
1 0.031475 0.001035 0.000033 1.133102 1.341032 1.523306
2 0.029548 0.000933 0.000015 1.063737 1.209743 0.677025
3 0.031176 0.001064 0.000054 1.122321 1.378544 2.538844
4 0.029869 0.000829 0.000015 1.075298 1.073764 0.677025
5 0.029602 0.000915 0.000029 1.065685 1.186298 1.354050
6 0.029721 0.000883 0.000015 1.069972 1.144098 0.677025
7 0.031230 0.000948 0.000025 1.124269 1.228498 1.184794
8 0.029595 0.000904 0.000029 1.065425 1.172231 1.354050
9 0.029476 0.000832 0.000025 1.061139 1.078453 1.184794
10 0.029476 0.000847 0.000029 1.061139 1.097208 1.354050
11 0.029851 0.000785 0.000025 1.074648 1.017497 1.184794
<<<<<<<<<
13 0.063336 0.007149 0.001629 2.280104 9.265315 75.996068
14 0.030093 0.000829 0.000033 1.083351 1.073764 1.523306
15 0.029721 0.000894 0.000040 1.069972 1.158164 1.861819
16 0.029426 0.000785 0.000004 1.059320 1.017497 0.169256
17 0.029458 0.000876 0.000018 1.060489 1.134720 0.846281
18 0.029866 0.000955 0.000022 1.075168 1.237876 1.015538
19 0.030108 0.000970 0.000011 1.083871 1.256632 0.507769
20 0.029541 0.000879 0.000018 1.063477 1.139409 0.846281
21 0.030710 0.000890 0.000029 1.105564 1.153475 1.354050
22 0.029494 0.000904 0.000029 1.061788 1.172231 1.354050
23 0.030252 0.000980 0.000025 1.089067 1.270699 1.184794
24 0.029368 0.000836 0.000004 1.057242 1.083142 0.169256
25 0.029862 0.000876 0.000036 1.075038 1.134720 1.692563
26 0.029909 0.000952 0.000018 1.076727 1.233187 0.846281
27 0.029718 0.000901 0.000025 1.069842 1.167542 1.184794
28 0.029678 0.000933 0.000025 1.068413 1.209743 1.184794
29 0.029617 0.000904 0.000029 1.066205 1.172231 1.354050