[Cryptography] Made a modification to RC4

[Jerry Leichter]

On Aug 30, 2014, at 4:17 AM, Ryan Carboni <ryacko at gmail.com> wrote:

> Feed RC4 through a transposition cipher... essentially a single round 2048-bit block cipher.
> 
> S1: 256 permuted bytes, serves as the PRGA
> S2: 256 permuted bytes, serves as the transposition cipher
> S3: 256 empty values, serves as the output array
> S4: 256 empty values, serves as the output array to rescramble the transposition cipher
> 
> i := 0 (S1)
> j := 0 (S1)
> while GeneratingOutput:
>     i := i + 1
>     j := (j + S1[i]) mod 256
>     swap values of S1[i] and S1[j]
>     K := S1[(S1[i] + S1[j]) mod 256]
>     output K to position S2[i] in S3
>     XOR K and S4[i]
>     if i = 255
>         output S3
>         while i > 0
>             swap values of S2[i] and S2[S4[i]]
>             i := i - 1
> endwhile
> 
> 
> This should flatten the biases in the first 256 bytes of RC4.
The biases were initially found by running some simple counting programs.  Rather than saying "should" ... have you run the same tests?

Of course, if all you are concerned about is biases in the first 256 values, you can simply discard them, keeping the security properties (such as they are) of RC4 unchanged.  This has been discussed for years and has even been named:  RC4drop-n, which drops the first n outputs (n=768 seems popular).  Other attacks - correlation between successive outputs - are a more significant problem as they persist no matter how much of the output you drop.

How does this compare - in space and time required, and in security against the known attacks - to simply running two copies of RC4 in parallel (use some kind of good key splitting to initialize them with different keys) and XOR the results?  Or do something that's proven effective for LFSR-like stream ciphers: Use the output of each to force an occasional extra "stutter" on the other (e.g., generate two value V1 and V2 from the two instances; if V1 == 255, run the second generator a second time (keeping V2); if V2 == 255, run the first generator a second time (replacing V1); return V1 XOR V2.  (The reason for the "replacing" the second time is that otherwise when the output is not 0, the attacker knows for certain that no extra step was taken.  On the other hand, if you also replace V2 times, you bias the output slightly away from 0.)

It's easy to propose new algorithms.  Showing they are better than what they've replace - much less that they are secure *at all* - is harder.  Three proposed improvements have been published widely enough to have made it into the Wikipedia article on RC4:  RC4A (proposed by Paul and Preneel, who published a general distinguishing attack against RC4), VMPC, and RC4+.  RC4A and VMPC have been attacked - ironically, there's a distinguishing attack against RC4A! - while RC4+, which is considerably slower than RC4, apparently hasn't seen much analysis.
                                                        -- Jerry


> It should also reduce the relationship between byte values and the internal state. 
> 
> I call this XARC4.
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography