RC4 variants RC4

1 rc4 variants

1.1 rc4a
1.2 vmpc
1.3 rc4
1.4 spritz

rc4 variants

as mentioned above, important weakness of rc4 comes insufficient key schedule; first bytes of output reveal information key. can corrected discarding initial portion of output stream. known rc4-dropn, n typically multiple of 256, such 768 or 1024.

a number of attempts have been made strengthen rc4, notably spritz, rc4a, vmpc, , rc4+.

rc4a

souradyuti paul , bart preneel have proposed rc4 variant, call rc4a.

rc4a uses 2 state arrays s1 , s2, , 2 indexes j1 , j2. each time incremented, 2 bytes generated:

thus, algorithm is:

all arithmetic performed modulo 256
i := 0
j1 := 0
j2 := 0
while generatingoutput:
:= + 1
j1 := j1 + s1[i]
swap values of s1[i] , s1[j1]
output s2[s1[i] + s1[j1]]
j2 := j2 + s2[i]
swap values of s2[i] , s2[j2]
output s1[s2[i] + s2[j2]]
endwhile

although algorithm required same number of operations per output byte, there greater parallelism rc4, providing possible speed improvement.

although stronger rc4, algorithm has been attacked, alexander maximov , team nec developing ways distinguish output random sequence.

vmpc

variably modified permutation composition (vmpc) rc4 variant. uses similar key schedule rc4, j := s[(j + s[i] + key[i mod keylength]) mod 256] iterating 3 x 256 = 768 times rather 256, , optional additional 768 iterations incorporate initial vector. output generation function operates follows:

all arithmetic performed modulo 256.
i := 0
while generatingoutput:
:= s[i]
j := s[j + a]

output s[s[s[j] + 1]
swap s[i] , s[j] (b := s[j]; s[i] := b; s[j] := a))

:= + 1
endwhile

this attacked in same papers rc4a, , can distinguished within 2 output bytes.

rc4

rc4 modified version of rc4 more complex three-phase key schedule (taking 3× long rc4, or same rc4-drop512), , more complex output function performs 4 additional lookups in s array each byte output, taking approximately 1.7× long basic rc4.

all arithmetic modulo 256. << , >> left , right shift, ⊕ exclusive or
while generatingoutput:
:= + 1
:= s[i]
j := j + a

swap s[i] , s[j] (b := s[j]; s[i] := b; s[j] := a)

c := s[i<<5 ⊕ j>>3] + s[j<<5 ⊕ i>>3]
output (s[a+b] + s[c⊕0xaa]) ⊕ s[j+b]
endwhile

this algorithm has not been analyzed significantly.

spritz

ron rivest , jacob schuldt have proposed replacing rc4 improved , modified version dubbed spritz:

all arithmetic performed modulo 256
while generatingoutput:
:= + w
j := k + s[j + s[i]]
k := k + + s[j]
swap values of s[i] , s[j]
output z := s[j + s[i + s[z + k]]]
endwhile

the value w, relatively prime size of s array. after 256 iterations of inner loop, value (incremented w every iteration) has taken on possible values 0..255, , every byte in s array has been swapped @ least once.

like other sponge functions, spritz can used build cryptographic hash function, deterministic random bit generator (drbg), encryption algorithm supports authenticated encryption associated data (aead), etc.

spritz broken banik , isobe.