Introduction
RC4 and Modification
Python Code
D
E
F
G
Disclaimer
Readers are strongly advised to rely on commercially available and tested products of encryption to protect their privacy. This page should be viewed for interest only, and the algorithms presented should not be considered as secure against a determined hacker.
This page has 2 sections.
- The first is a description of the attempt to modify the common and popular RC4 encryption algorithm in an attempt to overcome its vulnerability. This is accompanied by a Javascript program to perform encryption using the standard and modified RC4 algorithms
- The second displays a selection of Python codes for encryption, a convenient reference for those wishing to develop their own encryption algorithms.
RC4
Modified RC4
Javascript Program
RC4 is well described in Wikipedia, and only a very brief summary is presented here as the basis for subsequent descussions.
Description of RC4
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.
Vulnerability of RC4
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 vulnerable. The vulnerability is caused by the following sequence of reasons
- The relationship between the plain text and cipher text depends on the password.
- This relationship is invariant. The same plain text and the same password will produce the same ciphertext
- By analysing many messages using the same passwords, a pattern of relationship can be found
- By statistically exploring this relationship, the password can be revealed
- Once the password is known, all messages encrypted with that password become transparent.
Because of this vulnerability, RC4 is no longer commonly used to encrypt messages for electronic communications.
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. Repeated medifications of the basic RC4 algorithms have therefore been made as attempts to address this vulnerability (see Wikipedia). Next panel describes an tattempt by the author of this page.
The modification od RC4 presented 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 the same message is sent
- By creating a hash table so that the hashed values are encrypted to the cipher text. Each hash table is also different each time a message is sent
- 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 have a random 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
- The S array is modified by the passwdrd
- A random integer is created
- The random interger is encrypted by the password and stored as 2 bytes
For deciphering
- The first 2 bytes (4 hex chrs) of cipher text is deciphered by the password as bytes
- The bytes are combined to re-create the random integer
With the random integer
- Create An array of random bytes to modify the S array
- Create the hash array
- Create the scrambling byte
Modified RC4 Encryption and deciphering
Encryption and deciphering use the same process but in reverse directions
- A plain byte is scrambled with the random scrmbler
- The scrambled byte is hashed
- The hashed byte is encrypt using code from S array
- The encrypted byte is added to the cipher text as hex characters
- The hashed byte is then used as the scrambling byte for the next byte
The 2 buttons on the left encrypts and deciphers using the standard RC4 algorith, The 2 buttons on the right encrypts and decipher using the modified RC4 algorithm
- The top text area contains the password. The same password is used to both encrypt and decipher
- The second text area contains the plain text and the third text area the cipher text
- On clicking the Encrypt button, the program encrypts the plain text and place the result in the cipher text area
- On clicking the Decipher button the program deceypts the cipher text and places the results in the plain text area
- The text areas contains default example password and plain text. Users should replace these with this/her own
- The program uses Javascript and runs on the user's computer. Not information is transmitted to the server
- The program code is in the source code of the page, and can be viewed and copied
The following program is RC4 and modified RC4 written as classes in Python.
- The algorithm for RC4 is the same as that in the Javascript program, and the encrypted cypher text produced by either program can be deciphered by both
- The RC4Mod is different to that in the Javascript program, as it uses Python's system random number generator while the RAN3 algorithm is used in the Javascript ptogram. cypher text produced by one can therefore cannot be deciphered by the other.
# -*- coding: utf-8 -*-
"""
Created on 24/Mar 2021
RC4Mod
@author: Allan Chang
"""
import math
import random as rnd # seeded random
from random import SystemRandom
srnd = SystemRandom() # unseeded random
class RC4:
"""
RC4 is the original standard RC4 encryption program. This program is adapted
from source code from Github:
farhadi / rc4.js in Instantly share code, notes, and snippets.
https://gist.github.com/farhadi/2185197
Changes made are:
1. Separating the creation of S array from its shuffle, so that the
S array can be shuffled from outside, using an array of bytes
2. Allowing the shuffling array (password converted to bytes) of
any length, even exceeding 256 cells
3. Making the S array and its indeces (ii and jj) global variables so
they can be accessed for both encryption and deciphering
"""
def __init__(self):
self.sAr = [] # the S array for rc4
self.ii = 0 # array indeces
self.jj = 0
self.numberOfCycles = 1 # number of cycles for reshuffling.
# More cycles = more secure but takes longer
# default set at 1. Programmer can set this value
def ShuffleSArray(self, keyAr):
""" Shuffles the S array using an integer array """
leng = len(keyAr) # length of keyAr
lengthOfCycle = 256 # set length to sAr at 256
if(leng>256):
lengthOfCycle = leng # change to len if len greater
# start shuffling Modified from standard algorithm to cater to
# key array of any length
j = 0
for n in range(self.numberOfCycles):
for i in range(lengthOfCycle):
si = i%256 # index of S array
ki = i%leng # index of key array
j = (j + self.sAr[si] + keyAr[ki]) % 256
x = self.sAr[si]
self.sAr[si] = self.sAr[j]
self.sAr[j] = x
def MakeSArray(self, password):
""" creates the S array with string passwords """
self.sAr = [n for n in range(256)] # fill initial S array
#for i in range(256): sAr.append(i) # fill initial S array
# convert password to key array of bytes
keyAr = []
for i in range(len(password)): keyAr.append(ord(password[i]))
self.ShuffleSArray(keyAr)
self.ii = 0
self.jj = 0
def GetNextCipher(self):
""" GetNextCipher uses the Pseudo-random generation algorithm (PRGA) """
self.ii = (self.ii + 1) % 256
self.jj = (self.jj + self.sAr[self.ii]) % 256
tmp = self.sAr[self.ii]
self.sAr[self.ii] = self.sAr[self.jj]
self.sAr[self.jj] = tmp
tmp = (self.sAr[self.ii] + self.sAr[self.jj]) % 256
return self.sAr[tmp]
def DecToHex(self, i, c):
""" decimal to hex : i=integer, c=number of character """
fStr = '{:0' + str(c) + 'x}'
return fStr.format(i)
def HexToDec(self, h):
return int(h,16)
def Encrypt(self, plainText, password):
""" encrypt plainText with password """
self.MakeSArray(password) # creates the S array and set ii
cipherText = ""
for i in range(len(plainText)):
a = ord(plainText[i]) # character -> byte
e = a ^ self.GetNextCipher() # encrypted byte
cipherText += self.DecToHex(e,2) # append to cipherText
return cipherText
def Decipher(self, cipherText, password):
""" decipher cipherText with password """
self.MakeSArray(password) # creates the S array and set ii
plainText = ""
i = 0
while(i<len(cipherText)):
e = self.HexToDec(cipherText[i:i+2]) # hex -> byte
a = e ^ self.GetNextCipher() # decipher byte
plainText += chr(a) # byte ->chr, add to plainText
i += 2
return plainText
# end class RC4
class RC4Mod:
"""
RC4Mod uses the original RC4 algorithm as the engine, and alter its function
by introducing randomly generated values as scramblers, so that the same
passwrd/plain text pair will produce different cipher text everytime the
program runs
1. It creates a random integer as a seed to create an array of 256 random
bytes. This is used to scramble once more the S array of RC4 which has
already been scrambled by the password. It then creates a hash array
to obfuscate the values before they are encrypted by RC4
2. The random integer is condensed to a scrambler byte, which further
obfuscate the values of the plain text byte before it is processed
3. The random integer is encrypted and included in the cipher text so the
process can be reverse during deciphering.
4. Although this random integer is not crytographic grade, guessing its value
does not compromise the encryption, as the security rests with the original
RC4 algorithm, and the random integer is not used again
"""
def __init__(self):
self.rc4 = RC4() #class RC4
self.hAr = [] #hash array
self.uAr = [] #unhash array
def ResizeArray(self, ar,newSize):
"""
ResizeArray resized an array of numbers (in this pgm bytes) to a new size
Expanding the array uses a different calculation than the reverse of
shrinking an array. this means An array expanded then shrunk to the
original size will no longer be the same array
"""
oldSize = len(ar)
if(oldSize==newSize): return ar # array right size, returned unchanged
# array too short, append array by combination of existing values
if(oldSize<newSize):
i = 1
while(len(ar)<newSize):
ar.append(ar[i] ^ ((ar[i-1] * i) % 256))
i += 1
return ar # array lengthened to newSize
# array too long, prograssively shorten by combining existing values
while(len(ar)>newSize): # repeating until the right size
tmpAr = ar.copy() # copy to tmpAr
ar = []
for i in range(1,len(tmpAr)): #combine and shrinks by 1 each time
ar.append(tmpAr[i] ^ ((tmpAr[i-1] * i) % 256))
return ar # array shrunk to newSize
def Obfuscate(self, obfStr, inputAr):
"""
Obfuscate alters the values of the inputarray inputAr using a text
string and in this pgm the password.
The obfuscated array can be unobfuscated by running the same function
obfStr = obfuscating text string
inputAr = array of numbers (bytes) to be obfuscated
"""
obfAr = []
for i in range(len(obfStr)): obfAr.append(ord(obfStr[i]))
n = len(inputAr) # length of inputAr
obfAr = self.ResizeArray(obfAr,n)
resAr = [] # obfuscating by xor the two arrays
for i in range(n): resAr.append(obfAr[i] ^ inputAr[i])
return resAr # obfuscated array
def MakeHashAndReshuffleRC4(self, randomInt):
"""
MakeHashAndReshuffleRC4 uses an integer as a random seed in RandomGen,
then creates an array of 256 random bytes. The array is then used to
reshufflethe S array of the RC4 algorithm, then to create the hash
and unhash arrays for obscuring the values
"""
self.hAr = self.rc4.sAr.copy() # copy RC4 S array
rnd.seed(randomInt) # seeding generator randomInt
rnd.shuffle(self.hAr) # shuffle rc4 S array to hash array
self.uAr = self.hAr.copy() # mirror image unhash array
for i in range(256): self.uAr[self.hAr[i]] = i
# reshuffle rc4 S array with an array of 256 random bytes
keyAr = []
for i in range(256): keyAr.append(rnd.randint(0,256))
self.rc4.ShuffleSArray(keyAr) # re-shuffles rc4 S array
def Encrypt(self, plainText, password):
""" Encrypts plainText using password """
self.rc4.MakeSArray(password) # initialize RC4 S array
cipherText = ""
# Create random scrambler
sByteAr = [] # create array of 2 random bytes
for i in range(2): sByteAr.append(math.floor(srnd.random()*256))
# 2 random bytes
randomInt = sByteAr[0] * 256 + sByteAr[1] # random 16 bit integer
sByte = sByteAr[0] ^ sByteAr[1] # xor the two bytes to scrambler byte
# scrambler disguised and stored in first 4 hex of cipherText
sByteAr = self.Obfuscate(password, sByteAr) # obfuscate 2 byte in array
# first 2 bytes (4 hex chrs) are obfuscated x bytes
for i in range(2): cipherText = cipherText + rc4.DecToHex(sByteAr[i],2)
# make hash table and Reshuffles S array
self.MakeHashAndReshuffleRC4(randomInt)
# encryption begins
for i in range(len(plainText)):
asc = ord(plainText[i]) # character to ascii
scrambledByte = sByte ^ asc # scramble to sByte
hByte = self.hAr[scrambledByte] # hash to hByte
eByte = hByte ^ self.rc4.GetNextCipher() # encrypt to eByte
cipherText += self.rc4.DecToHex(eByte,2) # adds to cipherStr
sByte = hByte # pass hByte on as scrambler for next ascii
return cipherText
def Decipher(self, cipherText, password):
""" deciphers cipherText using password """
self.rc4.MakeSArray(password) # initialize RC4 S array
# Retrieve first 4 hex chr (2 bytes) from cipherStr
sByteAr = [] # retrieve the 2 byte scrambler
for i in range(2): # get first 2 bytes (4 hex chrs) obfuscated bytes
j = i * 2 # hex ->encrypted byte
sByteAr.append(self.rc4.HexToDec(cipherText[j:j+2]))
# de-obfuscate 2 byte by password
sByteAr = self.Obfuscate(password, sByteAr)
# re-creates random integer and random byte
randomInt = sByteAr[0] * 256 + sByteAr[1] # re-create random integer
sByte = sByteAr[0] ^ sByteAr[1] # re-creates random scrambler sByte
#make hash table and Reshuffles S array
self.MakeHashAndReshuffleRC4(randomInt)
# Deciphering
plainText = "" # decipher begins
i = 4 # starting 4th chr
while(i<len(cipherText)):
eByte = self.rc4.HexToDec(cipherText[i:i+2]) # hex to encrypted byte
hByte = eByte ^ self.rc4.GetNextCipher() # decipher to hashed byte
scrambledByte = self.uAr[hByte] # unhashed to scrambled byte
asc = sByte ^ scrambledByte # unscramble to ascii
sByte = hByte # pass hByte to sByte for next decipher
plainText += chr(asc)# transform ascii to char and add to plainText
i += 2
return plainText
# end class RC4Mod
if __name__ == "__main__":
""" Testing both classes """
pw = "AA"
pt = "xxx"
rc4 = RC4()
ct = rc4.Encrypt(pt, pw)
print(ct)
dt = rc4.Decipher(ct, pw)
print(dt)
rc4Mod = RC4Mod()
ct = rc4Mod.Encrypt(pt, pw)
print(ct)
dt = rc4Mod.Decipher(ct, pw)
print(dt)
bab39e
xxx
9e2bf01fb2
xxx
D
E
F
G
|
