14 RC4

epgp books

 

 

 

Objectives

  • To understand Verman one-time pad
  • To discuss about Random Number generator and its properties.
  • To learn about the Stream cipher and RC4 algorithm.

Introduction

 

Here we are considering Verman one-time pad and discuss about Random Number generator and its properties. The working of Stream cipher and RC4 algorithm is also explained in detail.

 

One-Time Pad

 

Developed by Gilbert Vernam in 1918, another name for one time pad is Vernam Cipher.

It is based on a truly random sequence of 0’s and 1’s and has the same length as the message. Another important property is one-time pad use one time only.

 

Let  mi be plain-text bits, ki is key (key-stream ) bits and ci is cipher-text bits.

 

Then the encryption is :

Decryption is:

 

It is clear that the encryption is adding the key to the message modulo 2, bit by bit.

For example,

Suppose the plaintext is : 1001001 1000110 and

 

Key is             : 1010110 0110001 , then

 

Ciphertext  : 0011111 1110110

 

Corresponding Decryption is as follows:

 

 

Practical problem with One-Time pad is that key-stream should be as long as plain-text.so it results difficulty in Key distribution and management. Stream ciphers are the solution to this problem. In stream cipher, key-stream is generated in pseudo-random fashion form relatively short secret key

 

Stream Cipher Model

Output function appears random

Here, Si  : state of the cipher at time t = i.

  • F : state function. G : output function

Initial state, output and state functions are controlled by the secret key.

Random Numbers

 

Random numbers play an important role in the use of encryption for various network security applications. In this section, we provide a brief overview of the use of random numbers in cryptography and network security and then focus on the principles of pseudorandom number generation. Getting good random numbers is important, but difficult. You don’t want someone guessing the key you’re using to protect your communications because your “random numbers” weren’t (as happened in an early release of Netscape SSL). Traditionally, the concern in the generation of a sequence of allegedly random numbers has been that the sequence of numbers be random in some well-defined statistical sense (with uniform distribution & independent).

In applications such as reciprocal authentication, session key generation, and stream ciphers, the requirement is not just that the sequence of numbers be statistically random but that the successive members of the sequence are unpredictable (so that it is not possible to predict future values having observed previous values). With “true” random sequences, each number is statistically independent of other numbers in the sequence and therefore unpredictable. However, as is discussed shortly, true random numbers are seldom used; rather, sequences of numbers that appear to be random are generated by some algorithm.

 

Pseudorandom Number Generators (PRNGs)

 

Often use deterministic algorithmic techniques to create “random numbers”.

Although they are not truly random, they can pass many tests of “randomness”.

It also known as “Pseudorandom Numbers” and created by “Pseudorandom Number Generators (PRNGs)”.

 

 

Figure 2 : Random Number generator

The figure 2a,2b and 2c contrasts a true random number generator (TRNG) with two forms of pseudorandom number generators. A TRNG takes as input a source that is effectively random; the source is often referred to as an entropy source. In contrast, a PRNG takes as input a fixed value, called the seed, and produces a sequence of output bits using a deterministic algorithm. Typically, as shown, there is some feedback path by which some of the results of the algorithm are fed back as input as additional output bits are produced. The important thing to note is that the output bit stream is determined solely by the input value or values, so that an adversary who knows the algorithm and the seed can reproduce the entire bit stream.

 

The two different forms of PRNGs, based on application is explained as follows:

  • Pseudorandom number generator PRNG: An algorithm that is used to produce an open-ended sequence of bits is referred to as a PRNG. A common application for an open-ended sequence of bits is as input to a symmetric stream cipher.
  • Pseudorandom function (PRF): A PRF is used to produce a pseudorandom string of bits of some fixed length. Examples are the symmetric encryption keys and nonces. Typically, the PRF takes as input a seed plus some context specific values, such as a user ID or an application ID.

The following are the PRNG Requirements

 

  • Randomness
    • PRNG should have uniformity, scalability, and consistency in generating random numbers.
  • Unpredictability
    • The third party should not predict the values before and after the use of random numbers and it should use same tests to check.

Characteristics of the seed also have importance in PRNG requirements. That is, the seed must be secure: if the seed is known adversary can determine output. So it must be random or pseudorandom number.

Using Block Ciphers as PRNGs

 

A popular approach to PRNG construction is to use a symmetric block cipher as the heart of the PRNG mechanism. For any block of plaintext, a symmetric block cipher produces an output block that is apparently random. That is, there are no patterns or regularities in the cipher text that provide information that can be used to deduce the plaintext. Thus, a symmetric block cipher is a good candidate for building a pseudorandom number generator. If an established, standardized block cipher is used, such as DES or AES, then the security characteristics of the PRNG can be established. Further, many applications already make use of DES or AES, so the inclusion of the block cipher as part of the PRNG algorithm is straightforward. Two approaches that use a block cipher to build a PNRG have gained widespread acceptance: the CTR mode and the OFB mode. The CTR mode is recommended in SP 800-90, in the ANSI standard X9.82 (Random Number Generation), and RFC 4086. The OFB mode is recommended in X9.82 and RFC 4086.

Figure 3 Modes of operation

The figure 3 illustrates the two modes of operations. In each case, the seed consists of two parts: the encryption key value and a value V that will be updated after each block of pseudorandom numbers is generated. In the CTR case, the value of V is incremented by 1 after each encryption. In the case of OFV, the value of V is updated to equal the value of the preceding PRNG block. In both cases, pseudorandom bits are produced on block at a time.

 

In CTR,

Xi = EK[Vi]

   In OFB ,

 

Xi = EK[Xi-1]

 

Stream Ciphers

 

A typical stream cipher encrypts plaintext one byte at a time, although a stream cipher may be designed to operate on one bit at a time or on units larger than a byte at a time. In a stream cipher, a key is input to a pseudorandom bit generator that produces a stream of 8-bit numbers that are apparently random. The output of the generator, called a keystream, is combined one byte at a time with the plaintext stream using the bitwise exclusive-OR (XOR) operation. The stream cipher is similar to the one-time pad. The difference is that a one-time pad uses a genuine random number stream, whereas a stream cipher uses a pseudorandom number stream. But rely on the randomness of stream key completely destroys statistically properties in message.

 

Stream Cipher Structure

Figure 4: Stream cipher structure

The figure 4 illustrates the general structure of a stream cipher, where a key is input to a pseudorandom bit generator that produces an apparently random keystream of bits, and which are XOR’d with message to encrypt it, and XOR’d again to decrypt it by the receiver.

During encryption, using a secret key generate the RC4 keystream using the KSA and PRGA.Then read the file and xor each byte of the file with the corresponding keystream byte.Write this encrypted output to a file. After that transmit file over an insecure channel.

 

Decryption also uses the same secret key that is used to encrypt generate the RC4 keystream. Then read the encrypted file and Xor every byte of this encrypted stream with the corresponding byte of the keystream.This will yield the original plaintext.

 

The following list gives important design considerations for a stream cipher:

  1. The encryption sequence should have a large period, the longer the period of repeat the more difficult it will be to do cryptanalysis.
  2. The keystream should approximate the properties of a true random number stream as close as possible, the more random-appearing the keystream is, the more randomized the ciphertext is, making cryptanalysis more difficult.
  3. To guard against brute-force attacks, the key needs to be sufficiently long. The same considerations as apply for block ciphers are valid here .Thus, with current technology, a key length of at least 128 bits is desirable.

With a properly designed pseudorandom number generator, a stream cipher can be as secure as block cipher of comparable key length. The primary advantage of a stream cipher is that stream ciphers are almost always faster and use far less code than do block ciphers. A stream cipher can be constructed with any cryptographically strong PRNG.

 

RC4 Basics

RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security. It is a variable key-size stream cipher with byte-oriented operations. The algorithm is based on the use of a random permutation. Analysis shows that the period of the cipher is overwhelmingly likely to be greater than 10^100. Eight to sixteen machine operations are required per output byte, and the cipher can be expected to run very quickly in software. RC4 is probably the most widely used stream cipher. It is used in the SSL/TLS secure web protocol, & in the WEP & WPA wireless LAN security protocols. RC4 was kept as a trade secret by RSA Security, but in September 1994 was anonymously posted on the Internet on the Cypherpunks anonymous remailers list. In brief, the RC4 key is ued to form a random permutation of all 8-bit values, it then uses that permutation to scramble input info processed a byte at a time.

 

RC4-based Usage

 

  • WEP
  • WPA default
  • Bit Torrent Protocol Encryption
    • Microsoft Point-to-Point Encryption
    • SSL (optionally)
  • SSH (optionally)
    • Remote Desktop Protocol
    • Kerberos (optionally)

RC4 Block Diagram

 

RC4 consists of 2 parts:

  1. Key Scheduling Algorithm (KSA)
  2. Pseudo-Random Generation Algorithm (PRGA)

Key scheduling algorithm generates state array .PRGA on the KSA generate keystream.XOR keystream with the data to generate encrypted stream.

 

Key Scheduling Algorithm

 

Use the secret key to initialize and permutation of state vector S, done in two steps.

 

Step 1:                      for i = 0 to 255 do

 

S[i] = i;

 

T[i] = K[i mod(|K|)]);

 

   [S], S is set equal to the values from 0 to 255

 

S[0]=0, S[1]=1,…, S[255]=255

 

[T] is a temporary vector

[K], Array of bytes of secret key

 

|K| = Keylen, Length of (K).

 

Step 2:                         j = 0;

 

fori = 0 to 255 do

 

j = (j+S[i]+T[i])(mod 256)

 

swap (S[i], S[j])

 

Use T to produce initial permutation of S. The only operation on S is a swap and S still contains number from 0 to 255 .

 

After KSA, the input key and the temporary vector T will be no longer used

 

Pseudo-Random Generation Algorithm

 

i = j = 0;

 

While (more_byte_to_encrypt)

 

i = (i + 1) (mod 256);

 

j = (j + S[i]) (mod 256);

 

swap(S[i], S[j]);//Sum of shuffled pair selects “stream key” value from permutation

 

k = (S[i] + S[j]) (mod 256); //Generate key stream k , one by one

 

Ci = Mi XOR S[k];// XOR S[k] with next byte of message to encrypt/decrypt

The output byte is selected by looking up the values of S[i] and S[j], adding them together modulo 256, and then looking up the sum in S .

 

S [S[i] + S[j]] is used as a byte of the key stream, K.

i = j = 0;

 

While (more_byte_to_encrypt)

 

i = (i + 1) (mod 256);

 

j = (j + S[i]) (mod 256);

 

swap(S[i], S[j]);

 

k = (S[i] + S[j]) (mod 256);

 

Ci = Mi XOR S[k];

 

Detailed diagram is shown below

 

Figure 4 : Steps in RC4

 

Figure 4 describes the detailed operation of RC4 with initial state of S and followed by initial permutation, and finally stream generation.

 

The figure 5 explains the overall operation of  RC4 algorithm .

Figure 5: Operation of RC4

 

Figure 5 explains about the encryption phase. Keystream is generated by running the KSA and PRGA. XOR keystream with the plain text to generate cipher text.

 

Decryption using RC4

 

Decryption uses the same secret key as during the encryption phase. Keystream is generated by running the KSA and PRGA.

 

XOR keystream with the encrypted text gives the plain text.

 

Logic is simple :

(A xor B) xor B = A

 

Where    A = Plain Text or Data and B = KeyStream

 

RC4 and WEP

 

WEP is a protocol using RC4 to encrypt packets for transmission over IEEE 802.11 wireless LAN.

WEP requires each packet to be encrypted with a separate RC4 key. The RC4 key for each packet is a concatenation of a 24-bit IV (initialization vector) and a 40 or 104-bit long-term key.

RC4 key:

IV Long-term key (40 or 10)
(24)

Summary

 

We have learnt about

  • Verman one-time pad
  • Random Number generator and its properties.
  • the Stream cipher and RC4 algorithm.
you can view video on RC4