Re: Securing ARC4

"Bill Cox" <bill@xxxxxxxxxxxxx> writes:


David Wagner wrote:
Bill Cox wrote:
Randomization is simple, given an array R of 256 truely random bytes:

for i = 0 to 255
swap(S[i], S[R[i]]

Where does the key come in? Is this applied before the normal RC4
key schedule? after? something else?

On second thought, never mind, don't bother answering those questions.
It doesn't matter: I won't have time to perform a careful analysis of
this RC4 variation in any event. At a high level, you are changing the
RC4 algorithm. Any such changes have to be evaluated very carefully,
because they can introduce insecurity. Your changes could easily
introduce security problems.

I know you said that you've completely randomized S, so you don't see
how a security problem could arise, but think about this. The array R
is public knowledge. Say you generate one S-table with key K and array
R and use that to encrypt the first message; then you generate another
S-table with key K and array R' and use that to encrypt the second
message. You've essentially got a related-key condition. This might
help an attacker to recover K. How do you know that cannot happen?
Even worse, depending upon the surrounding protocol, it may be possible
for the attacker to choose or control R in some way. If that is possible,
it may open up another avenue for attacks. That's why these changes to
the internal details of algorithms have to be carefully analyzed.

Crypto primitives are hard to evaluate. It takes a lot of work and
expertise to get a sense about whether the crypto primitive is likely to
be secure or not. Tweaking the innards of a primitive is not something
to be done lightly. I encourage you to resist the urge to tweak the
algorithms (no matter how fun it may be).

I agree. I haven't taken time to import SHA-1 into tinycrypt yet, but
I will. Even if I fix the randomization problem other's pointed out,
when /dev/urandom runs is forced to switch to SRNG mode, the cypher

Nuts. That is NOT a problem. Your problems are far worse than any weakness
in urandom ( of which none have been found which would allow you to predict
the future output purely from the past output of the generator. )

This is like discussing cancer and worrying about your hangnail.


could suffer. Is there any reasonable alternative to SHA-1 that is
simpler? Since I'll only use it to hash the key and nonce, speed
counts than complexity. -- Thanks.


Note that your swapping does NOT randomize the permutation. Some
permutations are more probable than others under your procedure.
( The number choises of R is n^n while the number of permutations is n!.
The second does not divide the first, which says that some permutations
must be more probable than others.
Doing is for n=3, half the permutations have probability 4/27 and half
5/27 under your procedure. --ie random R does not imply random permutation)


.

Relevant Pages