Visualizing RC4 Key Initialization

Recently, I was curious about what the key initialization for RC4 key stream would look like visually. If you are unfamiliar with RC4 I would recommend Wikipedia's article. What I'm focusing on in this post is the key scheduling algorithm.

Key scheduling algorithm:
for i from 0 to 255
    S[i] := i

endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]

endfor

What I found interesting about this algorithm is it originally starts with a 256 bytes array/list in sequential order (0,1,2,3,4...253,254,255). This range could be represented in the form of a gradient. The above image is the visual representation of each loop of the key stream. The bottom left hand corner from left to right is the initial sequential list. The loop iterates 256 times. Each time the loop iterates the key stream is modified.


Another image with the char 'B' as the key. The very top row is the complete key stream from the key-scheduling algorithm.
 
Another image with the char 'Z' as the key. The above image was created in Python using matplotlib. The code will iterate through chars from 'A' to 'Z'. The images will be saved with a file name of example-char.png.
 
import matplotlib.pyplot as plt
import numpy as np
import random
import sys

def rc4_init(key):
    # creates a list of the stream for each loop of the key stream 
    c = 0
    k = range(256)
    j = 0
    x = []
    x = x + k
    for i in range(256):
        j = (j + k[i] + ord(key[i % len(key)])) % 256
        k[i], k[j] = k[j], k[i]
        x = x + k

    return x

def createImage(key):
    # get list of RC4 key values size (256*257)
    data = np.array(rc4_init(key))
    data.shape = (257,256)
    # use heat map 
    plt.hot()
    plt.ylabel('Loop Iteration')
    plt.xlabel('Array Value 0-256')
    plt.title('RC4 Key Initialize with Value of ' + '\'' + str(key) + '\'')    
    plt.axis([0,256,0,257])
    plt.pcolormesh(data)
    plt.colorbar()
    #plt.show()
    plt.savefig('example-' + str(key) + '.png')
    plt.close()


def main(argv):
    for x in range(65,91):
        createImage(chr(x))


if __name__== '__main__':
        main(sys.argv[1:])

Visually I think this is pretty cool. I decided to take it a step further and create an animated gif. The .gif displays the image with value keys of 'A' through 'Z'. Warning the .gif is over 2MBs in size. LINK Odds are my terminology is off in some of the description of the algorithm. Please feel free to leave comments if you see one.

2 comments:

  1. Thanks for your post. However, I don't understand how you could exploit that ? What are your conclusions about that ?

    Thanks

    ReplyDelete
  2. Thanks. This post was more about exploration rather than exploitation. I'm not a cryptanalyst but I do not believe anything can be exploited from this. The images were a way to see how the keys are initialized and how it would appear visually.

    ReplyDelete