Back to Homepage

Finney states


Hal Finney found a theoretical class of internal states of the RC4 stream cipher which fall into a short cycle of length 65280 (255*256) by swapping P[n]=1 element of the internal permutation in each step. This class is diagnosed by n+1=s and P[n+1]=1 at the start of the state-transformation function of RC4 defined as:

1. n=n+1
2. s=s+P[n]
3. Swap P[n] with P[s]

Such phenomena is possible because step 2 (s=s+P[n]) retains the linear structure of P[n]=1 in variable s and increments s by 1 in each step. With n being incremented by 1 in each step too and with n+1=s, each swap is made between P[n] and P[n+1] where P[n+1]=1. As a result permutation P returns to its initial state after 65280 steps which makes the RC4 output fall into a 65280-byte short cycle.

The VMPC Stream Cipher uses an additional table-lookup in step 2 (s=P[ s+P[n] ]), which corrupts a possible linear structure of P[n] or s and prevents situations analogous to the Finney states from occurring.

by Bartosz Zoltak

Copyright © 1999-2018 by Bartosz Zoltak