Disclaimer

The contents of this page are experimental and unvalidated. The program is presented as an invitation for those interested to test if the encryption provided is secure. At this stage, the program provided should not be used to encrypt anything serious. The author denies responsibility and liability for any and all consiquences of using the contents of this page.

Feedback

This page presents an experimental approach to modify the basic RC4 encryption algorithm to overcome its known vulnerability. All readers are invited to test this program, to see if the encryption can be analysed. The author would be grateful for any feedback, which can be sent via the Contact StatsToDo page.

The source code, with a brief explanation, is also posted to Github so that comments and suggestions can also be posted there

Introduction

RC4 is a simple method of encryption using symmetrical keys (same key to encrypt and decipher), and able to stream (once set up, can repeatedly encrypt or decipher large volumn of content continuously) When RC4 became available in 1980s, it was greeted with enthusiasm because of its simplicity, security, speed, and streaming. It was widely adopted, especially for encrypting messages that are sent over the Internet. Unfortunately, a vulnerablility was discovered after some years, and RC4 is no longer widely used.

This page discusses this vulnerability, and explain an attempt to overcome it. The contents are divided into 6 panels

• Introduction: This panel
• Technical Issues: Technical discussions on why and how of modifying RC4
• Program: Javascript program for standard and modified RC4 encryption
• Algorithm: Discuss the Javascript code of modified RC4 according to its functions

Password: Key board characters of any length, to be used for both encryption and deciphering MyPassword Plain Text: Text consisting of keyboard characters to be encrypted The quick brown fox jumps over the lazy dog      Cipher Text: Characters 0-9 and a-f or A-F representing Hex values of encrypted cipher text

Replace default example password and text with user's own. Note password is for both to encrypt and to decipher Buttons on left runs the standard RC4 algorithm. Buttons on right runs the modified algorithm

Please be warned: the discussion on this panel is based on my current understanding and thinking, the information may contain errors and omissions, and the logic of arguments may sometimes be flawed.

The Basic RC4 Encryption Algorithm

RC4 is well described in Wikipedia, and a very brief summary is presented here as the basis for subsequent descussions. RC4 consists of the following components

• The S array, usually with 256 values (0 to 255) to represent all possible values of a byte. The values are arranged using the password, and so are specific to the password
• The Pseudo Random Generation Algorithm (PRGA). This is a method of selecting the value from the S array to encode (encrypt or decipher) the incoming data. A feature of this method is that the values are not accessed sequentially from the array, but each value determines the next value to be accessed.
• Encoding is by the "exclusive or" (xor) operation between the value from the S array and the data. This means that encrytion and deciphering uses the same process. This makes the algorithm simple, but it requires the same password being used for both processes (symmetrical key)

As the arrangements of the S array depends on the password, and the sequence of access depends on the arrangements of the array, encryption proceeds in a deterministic manner, but unpredictable unless the password is known. RC4 was therefore described as symmetric key, streamable, fast, and secure.

When RC4 became available in the late 1980s, it was rapidly incorporated into many applications, and for encrypting messages to send over the Internet. After a few years of extensive use however, a vulnerability in RC4 was discovered. Although RC4 remains secure if the password is used only once, repeated use of the same password was found to be insecure, so that RC4 is no longer being used in communications. The vulnerability is caused by the following sequence of reasons

1. The relationship between the plain text and cipher text depends on the password.
2. This relationship is invariant. The same plain text and the same password will produce the same ciphertext
3. By analysing many messages using the same passwords, a pattern of relationship can be found
4. By statistically exploring this relationship, the password can be revealed
5. Once the password is known, all messages encrypted with that password become transparent.

RC4 Modification

Although there are many more secure encryption algorithms available, RC4 remains an important encryption method because it is a stream cipher that is low cost, simple and fast, and it can be embedded easily into other applications without licence or complex APIs. It is therefore worth while to attempt to overcome the vulnerability discovered.

The approach to modification on this page is based on the following assumptions

• that RC4 is essentially secure except the pattern of relationship between plain and cipher text for any password
• The relationship can be explored because the same password/plain text will produce the same cipher test.
• If the same password / plain text combination produces a different set of cipher text every time it is sent, and that difference is random, then the vulnerability can be remedied.

The principles of modifications on this page are therefore as follow

• The basic processes of initialization the S array and the Pseudo-random generation algorithm (PRGA) method of selecting the code and indeces should remain the same.
• In addition, a randomly generated scrambler is introduced, which will make the cipher text randomly different by 3 mechanisms.
  • By shuffling the S array again, so that the S array is different each time
  • By creating a hash table so that the hashed values are encrypted to the cipher text. Each hash table is also different
  • The scrambler scrambles each incoming byte before it is processed. The hashed result is then used as the scrambler for the next byte. The scrambler for each byte therefore depends on the initial one and all the prior text encountered
• The randomly scrambler will need to be incorporated into the cipher text so it is available to the deciphering algorithm. The scambler is also encrypted by the password, but using a different path, so that there is no relationship between the S array and the scrambler

If successful, the modified RC4 should achieve the following

• The security achieved by the basic RC4 remains intact
• For each combination of password and plain text, the cipher text is different each time the encryption is carried out. Each cipher text should be random, with no perceived pattern, regardless of the size of the password, and the frequency of any pattern in the plain text
• The randomly generated scrambler is 2 bytes, so it can be guessed even though it is encrypted in the cipher text. However, correct guessing of the scrambler should not allow re-engineering to find the password
• All together, the modified RC4 should be no easier to analyse than by brute force analysis (guessing of the password).

The concept of the algorithm is shown in the flow chart to the right. The upper portion is the standard RC4, and the bottom portion thth the modifications included.

Standard RC4

The S array is modified by the password, then both to encrypt or decipher uses the same encoding process

Modified RC4 Preparation

For Encryption

1. The S array is modified by the passwdrd
2. A random integer is created
3. The random interger is encrypted by the password and stored as 2 bytes

For deciphering

1. The first 2 bytes (4 hex chrs) of cipher text is deciphered by the password as bytes
2. The bytes are combined to re-create the random integer

With the random integer

1. Create An array of random bytes to modify the S array
2. Create the hash array
3. Create the scrambling byte

Modified RC4 Encryption and deciphering

Encryption and deciphering use the same process but in reverse directions

1. A plain byte is scrambled with the random scrmbler
2. The scrambled byte is hashed
3. The hashed byte is encrypt using code from S array
4. The encrypted byte is added to the cipher text as hex characters
5. The hashed byte is then used as the scrambling byte for the next byte

This panel comments on the Javascript in the source code of this page. The codes are divided into 3 classes to cluster separate sets of functions.

ClassRandomGen

The is the ran3 random number generator, as copied from the textbook (see reference) and translated to Javascript. The original algorithm is separated into functions

• SowSeed allows the random seed to be used, so that the same sequence of random number can be re-generated
• RRandom produces random number between 0 and 1 following the seeds sown

Two additional functions are added

• NextIntegerValue converts the random real number into an integer according to the minimum value and the range required
• ShuffleArray tskes an input array and shuffles it according to the random number genrated

Referece: Press WH, Flannery BP,Teukolsky SA, Vetterling WT (1994). Numerical recipes in Pascal Ed. 1, IBSN 0-521-37516-9. p.221

ClassRC4

This presents the original basic RC4, as obtained from github, but with the following modifications

• The S array (sAr) is set as a public class variable, so that it can be accessed and modified by the class RC4Mod later
• a constant (numberOfCycles) is added, which allows the programmer to set the number of cycles that the password array modifies the s array. The default is set at 1, to conform with the original algorithm. The higher the number, the more secure the encryption, but also the longer computing time required.
• The creating and modification of the s array is separated into 2 functions
  • The MakeSArray function creates the initial S array, converts the password into an array of bytes, and calls the ShuffleSArray function
  • The ShuffleSarray function is essentially the same as the original except for the following modifications
    • It is a public function, so that the S array can be shuffled from outside the class
    • In the original algorithm, the password is assumed to be no more than 256 charcters. The algorithm is modified so that it can cope with an array of any size
    • It shuffles the S array a number of times as determined by the value of numberOfCycles set by the programmer (default=1)
• the GetNextCipher function is the same as the original PRGA algorithm. It is a public function so that it can be accessed from outside of the class

ClassRC4Mod

This is the modified RC4 class, and incorporates the previous 2 classes. It has 2 utility functions and 4 main functions

The ulilty functions are

• ResizeArray takes an array of bytes and stretches or shrinks it to the new size required. The method alters the values in a reproducible but unpredictable manner, and cannot be re-engineered, as stretching and shrinking uses different arithematics. The method is intended for transforming passwords into encryption codes. For example, a 6 character password can be shrunk to a 2 byte array for encrypting a random integer
• Obfuscate is really an encryption/decipher function, but use the term obfuscate so as not to confuse it with RC4. It takes an array to be obfuscated (inputAr) and a password (obfStr). The obfStr is converted into an array of bytes, resize it to the length of inputAr, and the two arrays are exclusive ored (xor) to produce the resulting array. This function is used to encrypt and decipher the random integer that is used for scrambling the cipher text

The 4 main functions are:

• SetUp actives classRC4 as rc4 and prime the its S array
• MakeHashAndResuffleRC4 uses the random integer to create the hash array, and gives the S array in rc4 (already created and shuffled by the password) an extra shuffle using random numbers
• Encrypt does the encrypting.
  • It first prepares the engine
    1. It runs SetUp, this creating the S array from the password
    2. It creates a ranfom integer, encrypt it as the first 2 bytes (4 hex chrs) of the cipher text
    3. It uses the random integer to create the hash and unhash tables, and gives the S array an extra shuffle with random numbers
    4. It then creates the scrambler byte
  • It then encrypts. For each character in the plain text:
    1. converts to a byte
    2. Scrambles the byte with the scrambler
    3. Hash the scrambled byte
    4. Encryptes the hashed byte with rc4
    5. Converts the encrypted byte to a 2 chr hex string and adds this to the cipher string
    6. Use the hashed byte as the scrambler byte for the next byte
• Decipher does the deciphering.
  • It first prepares the engine
    1. It runs SetUp, this creating the S array from the password
    2. It reads the first 2 bytes (4 hex chrs) of the cipher text and decipher it to the random integer
    3. It uses the random integer to create the hash and unhash tables, and gives the S array an extra shuffle with random numbers
    4. It then creates the scrambler byte
  • It then deciphers. For each 2 hex character in the cipher text:
    1. converts to a byte
    2. deciphers the byte with rc4
    3. Unhash the deciphered byte
    4. Unscramble the unhashed byte eith the random scrambler
    5. convert the unscrambled byte to ascii character and adds this to the plain text
    6. Pass the deciphered (thus hashed) byte as the scrambler byte for the next byte

Testing in progress

References

Contents of G:6