Thor Lancelot Simon wrote:
> On Mon, Aug 07, 2006 at 08:21:12AM -0700, Garrett D'Amore wrote:
>   
>> Joerg Sonnenberger wrote:
>>     
>>> If you want something simple, at least use a secure cipher. AES and
>>> Blowfish are in the kernel already, so use them. RC4 is as well, but
>>> considered weak now. DES is just not worth the effort.
>>>
>>> Joerg
>>>       
>> I'm not aware of any cryptographers that consider RC4 weak.  RC4 is fast
>> and simple, and it is a stream cipher.  I think RC4 has gotten a bad
>> name because it was misused in WEP.  The usage created the weakness --
>> properly used RC4 should be pretty strong.
>>     
>
> I disagree.  There is a long history of work, going back about a decade
> now, that, if nothing else, demonstrates that RC4 fails to meet what are
> thought of as good design requirements for a stream cipher -- its output
> can be all too easily distinguished from a random bitstream, to begin
> with.  This has come up a couple of times on the cryptography list in the
> past few months and certainly my sense of it is that very few people would
> endorse the use of RC4 for new designs now.
>
> There's also a considerable problem with using RC4 for encryption of data
> like disk blocks: because the output of RC4 is so non-random when it first
> starts up after rekeying, you do a significant amount of wasted work just
> to get the cipher to a "safe" state, then use it to encrypt only 512 bytes.
>   

These sound minor problems to me -- understanding how to use RC4
properly is part of the problem.  And pre-encrypting some initial data
with RC4 shouldn't be a problem from a performance standpoint, because
I'm not aware of anything that even comes close to RC4 performance.  (We
skipped hardware acceleration of RC4 at my last project, primarily
because the cost of DMA setup and teardown on SPARC hardware didn't
compete very favorably against just running the algorithm in software. 
It was on the order of ~4 cycles per byte on sparcv9 hardware if I
recall correctly.  We had some custom assembly optimizations though.) 
I'm also not aware of any suitable replacement stream ciphers.  However,
I've not been as involved with crypto for the past few years (I left the
crypto group at Sun about 4 years ago), so maybe things have changed.

I agree with your synopsis below that RC4 is probably not well suited to
this particular use.  Again, I don't think this is necessarily a problem
with RC4 itself, but it may be a problem where any stream cipher is not
really well suited to this particular use.

One of the nice things that RC4 has over its block cipher competition is
a potentially very, very large key space.  Generally most folks don't
use it with keys larger than 128 bits, but IIRC the key space can be as
large as 256 bytes (i.e. 2048 bit).  And when running with these longer
keys, RC4 performance is unchanged relative to a shorter key size. 
(AES, by comparison runs somewhat slower as the key size increases from
128 to 192, and then again to 256 bits.)

Of course, many implementations of RC4 may not allow the use of these
larger keys.  But that is an implementation defect, not a limitation of
the algorithm itself.

    -- Garrett
> Finally, there is the highly questionable notion of using a stream cipher,
> with its easy susceptibility to bit-flipping, to encrypt data in persistent
> storage on disk: yes, we do know attacks that allow modification of the
> decrypted plaintext under block cipher modes like CBC, but stream ciphers
> make it trivial, and surely that is not a good thing.  To use RC4 for this
> purpose would require that it be used with a keyed MAC, and at that point
> any speed advantage disappears.
>
> In general I am opposed to adding encryption code to vnd and question
> whether adding compression code was a good idea, either: it seems to
> me the _only reason_ we would find it convenient to add encryption to
> vnd now is that compression was added to it instead of being implemented
> as a separate compressing device layer, which would have allowed the
> stacking of the encryption and compression transforms in the right order.
>
> Thor
>   


-- 
Garrett D'Amore, Principal Software Engineer
Tadpole Computer / Computing Technologies Division,
General Dynamics C4 Systems
http://www.tadpolecomputer.com/
Phone: 951 325-2134  Fax: 951 325-2191