Stream Ciphers

Introduction

Stream ciphers encrypt data one bit or one byte at a time. The confusion sequence is created at encryption time and is combined with the plaintext to form the ciphertext stream. Likewise, during decryption, the key allows the recreation of the confusion sequence for recreation of the plaintext at the receiving end. The advantage of a stream cipher is its speed in that it only depends on the algorithm and not the operation of receiving more plaintext. Also, the stream cipher has a low error propagation rate. However, the disadvantages of a stream cipher are that it has low diffusion where a cryptanalyst can use language frequency distribution techniques to break it, which also can lead to message fabrication.

Synchronous Stream Cipher

Synchronous stream cipher keys are generated at a different time than during the encryption process. Keys are generated independently of the plaintext or ciphertext. The sender and receiver need to be in synchrony with the state of the key. As stated above any bit that has been changed due to corruption or unintentional modification does not affect the deciphering of other bits. However, when ciphertext characters are deleted or inserted then synchronization is lost. An example of this can occur in a DES stream in the OFB mode.

Asynchronous Stream Cipher

Asynchronous stream ciphers generate key streams as a function of the key and a set number of former ciphertext bits. The advantage is that if ciphertext bits are inserted or deleted the decipher stream can self-heal by re-synchronization, which results in only a loss of possibly a few characters. Furthermore, asynchronous stream ciphers have better diffusion statistically than synchronous stream ciphers. An example of this is a DES stream in the CFB mode. A5 is an example of a stream cipher for GSM that's used in cellular phones.

RC4

RC4 is named after Ron Rivest of RSA Security. The RC4 symmetric key stream cipher is an OFB mode stream cipher with a variable key size ranging from 1 to 255 bytes. The key stream can be developed independently of the plaintext. RC4 can also be used as a pseudo-random number generator. RC4, which is ten times faster than DES, generates a random character that is Xor'ed with a plaintext character to produce a ciphertext character. There are two parts to RC4: (1) Key setup, which produces an encrypting variable and (2) Ciphering process, which Xors a plaintext character with a random element of the encrypting variable. The RC4 algorithm is as follows:

Key Setup Phase:
 
For I from 0 to 255 do
 S[I]  I 
 
J  0
 
For I from 0 to 255 do 
J  (J + S[I] + key[I mod key_length]) mod 256
 Swap S[I] with S[J]
Ciphering Phase:
 
I  0
J  0
 
Loop until every character C is encrypted
 I  (I + 1) mod 256
 J  (J + S[I]) mod 256
 Swap S[I] with S[J]
 K  (S[I] + S[J]) mod 256
 
 Send S[K]  C
 

With each iteration in the second for loop in the Key Setup Phase and the loop in the Ciphering Phase, the state array s[] undergoes a permutation via the Swap method. We implement this algorithm below in C. We use three files to show the original message, the ciphertext and the decrypted plaintext (that are not a part of RC4):

 

#include <stdlib.h>

#include <stdio.h>

#include <time.h>

 

// Constants

#define STATE_SIZE 256 // Size of the state (in bytes)

#define KEY_SIZE 32 // Size of the key (in bytes)

 

void Swap(short *x, short *y);

void SetupKey();

void CryptoStream();

 

// Globals

FILE *pReadStream;

FILE *pEncryptStream;

FILE *pDecryptStream;

short state[STATE_SIZE];

short key[KEY_SIZE];

short nStIndex = 0;

short n = 0;

 

int main()

{

pReadStream = fopen("message.txt", "r");

pEncryptStream = fopen("ciphertext.txt", "w");

pDecryptStream = fopen("plaintext.txt", "w");

 

SetupKey(); // Step One

CryptoStream(); // Step Two

 

fclose(pReadStream);

fclose(pEncryptStream);

fclose(pDecryptStream);

 

return 0;

}

 

// Alice and Bob must first agree on the initial state and key

void SetupKey()

{

// Initialize state

for (short nStates = 0; nStates < STATE_SIZE; nStates++)

state[nStates] = nStates;

srand((unsigned) time(NULL));

 

// This is our initial input key

for (short nKey = 0; nKey < KEY_SIZE; nKey++)

key[nKey] = rand();

 

// Set up the state from the initial input key

while (n < STATE_SIZE)

{

nStIndex = (nStIndex + state[n] + key[n % KEY_SIZE]) %

STATE_SIZE;

Swap(&state[n], &state[nStIndex]);

n++;

}

}

 

// Randomly select a state and Xor it with the next character

void CryptoStream()

{

short nChar = 0;

char cEncrypt = 0;

short nRandomIndex = 0;

n = nStIndex = 0;

 

// Read each character of the original message

while ((nChar = getc(pReadStream)) != EOF)

{

// Randomization

n = (n + 1) % STATE_SIZE;

nStIndex = (nStIndex + state[n]) % STATE_SIZE;

Swap(&state[n], &state[nStIndex]);

// Produce the random index for the state array

nRandomIndex = (state[n] + state[nStIndex]) % STATE_SIZE;

 

// Xor a random state with the next character from the

// stream

cEncrypt = (char) (state[nRandomIndex] ^ nChar);

// Put it into a file (actually sent to Bob)

putc(cEncrypt, pEncryptStream);

// Decryption via reverse Xor (performed by a remote Bob)

putc(((char) (state[nRandomIndex] ^ cEncrypt)),

pDecryptStream);

}

}

 

 

 

 

 

 

void Swap(short *x, short *y)

{

int temp = *x;

*x = *y;

*y = temp;

}

"It is not the critic who counts. Not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly. Who errs and comes short again and again, because there is no effort without errors and shortcomings but who does actually strive to do the deeds, who spends himself in a worthy cause. Who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly. So that his place shall never be with those cold and timid souls who know neither victory nor defeat." - Theodore Roosevelt, President of the United States, 1901 - 1908.
 
Original message:

 

 

 

 

տ)AXއg`Mek{>HXE'Pg)pJQYNų"~Rԭ(ToҩU9,V mߑfk ho"\ٕ\Ş=|=.*.' 8_‑CVX[1][
rTdRLDJAg7` DₘnC%HE%q說/OV*`/Hבڧa焲nm,$hY@{1ɔAvWGnt &ZAvRO$!osRT~

DߐWT(Dv[1]XD+U<:T."'0c%9zE |dHv΄\]6AsӔfBї[qfc
[\@&

X;?㶃~'g/UnZ

+Yf(78_ݟ
fz})"-&[1])V|7a'=

O
7**GEvRI2,@SQ؟*cb

 x?Nj
mBI4'R؝gA=H>lUqL1

d\^Ʃ
,ʋyz[`S_ /[]?

љԄ?U
aXP3eTK4~
RrHPqC$)!ܱ7?q@%Yi)EcyA\(ϴ*Ea
 
Resulting ciphertext:

 

 

 

 

 

 

 

 

 

"It is not the critic who counts. Not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly. Who errs and comes short again and again, because there is no effort without errors and shortcomings but who does actually strive to do the deeds, who spends himself in a worthy cause. Who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly. So that his place shall never be with those cold and timid souls who know neither victory nor defeat." - Theodore Roosevelt, President of the United States, 1901 - 1908.
 
Decrypted plaintext:

 

 

 

 

 

The RC4 process has 256! x 2562 or 21700 possible states. RC4 is strong against differential and linear cryptanalysis. Currently, RC4 is used in some Oracle products, Cellular Digital Packet data and Lotus Notes, and RC4 can simply be used as a pseudo-random number generator.

Links

http://www.rsasecurity.com/rsalabs/faq/3-6-3.html
http://www.wisdom.weizmann.ac.il/~itsik/RC4/rc4.html

http://en.wikipedia.org/wiki/Stream_cipher

http://en.wikipedia.org/wiki/Linear_feedback_shift_register

http://www.ncat.edu/~grogans/algorithm_history_and_descriptio.htm