rotor alternative?

[Paul Rubin]

aaron at reportlab.com (Aaron Watters) writes:
> > At first glance that function looks awful (no offense intended), and
> > the implementation looks very slow.  I'd strongly advise against doing
> > anything serious with it.  If you want a pure-Python cipher, please try
> > 
> >   http://www.nightsong.com/phr/crypto/p3.py
> 
> Offense taken :(.  Please explain (offline if you like).
> It's okay to call my stuff awful, but I require a bit of
> constructive criticism to go with it.

I don't want to spend time analyzing the algorithms when there are
already perfectly good ciphers available and it's better to just stick
with them.  But without making any real attempt to figure out what
your cipher is doing, several things are immediately obvious:

    1) There is no attempt to provide any randomness in the output.  If
    you encrypt the same plaintext twice with the same key, you get the
    same ciphertext.  That is a security failure in many applications.

    2) What's more, the cipher is a one-character-at-a-time stream cipher
    so if you encrypt two different plaintexts that begin with a common
    prefix, it looks to me like the ciphertexts will also have a common
    prefix, another security failure.

    3) No authentication is provided.  An attacker who intercepts a
    ciphertext in transmission can change it and the decryption side
    will have no idea that anything has happened.  All kinds of real-world
    systems have made that same mistake and suffered for it.

    4) It's almost certain that the cipher is vulnerable to
    related-key attacks (as RC4 is), and from the way the cipher
    feedback works, it may be easy to spot related plaintexts
    (not just common prefix) by looking at the ciphertext.

> FWIW it was loosely inspired by RC4 and it seems to scramble
> things up nicely. 

Being loosely inspired by RC4 is unreassuring on several grounds.

First of all, RC4 was designed very carefully by a knowledgeable
cryptographer who did a lot of studies and statistical experiments on
RC4 variants before settling on RC4.  Don't be fooled by RC4's
simplicity, since just about every attempt to tweak it has in fact
made it worse.  If you want an RC4-like cipher, use RC4, not a
"loosely-inspired" home-cooked variant that hasn't withstood a lot of
cryptanalysis attempts.

Second, RC4 itself doesn't have such good properties.  RC4 can only be
used securely if key selection and authentication are done properly,
which takes knowledge.  Take a look at IEEE 802.11 WEP to see what
happens if you use RC4 improperly but still in a way a reasonable
non-stupid engineer might expect it to work.  The
Fluhrer-Shamir-Mantin attack uses RC4's internal structure to break
WEP with a very limited amount of captured traffic.  Since WEP is
deployed in millions of Wifi cards, corporations all over the place
are spewing secret data over their wireless networks where they can be
intercepted by any malicious cretin driving past their building with a
wifi-equipped laptop.  WEP would be much more secure if it had used
AES instead of RC4.  

Third, even if RC4 is used properly, there are distinguishing attacks
that can tell that the RC4 keystream is not random given a few
gigabytes (maybe a lot less).  That itself can be a security failure
in some applications like encrypting a hard drive.  RC4 really
shouldn't be used in new applications.  Use AES instead.

> Regarding speed: for small blocks it should
> be reasonably fast for a pure python module which doesn't
> use any extension modules, and it is also suitable for conversion
> into a very small self contained C function, which was the intent.
>
> But yours is much faster of course, since it uses an extension module
> for the critical loop.  For larger blocks more than an order of
> magnitude faster. 

Coding either of those algorithms as a C function would be a big
mistake.  Once you have a way to use C functions, it's better to use
AES.  However, coding RC4 in pure Python should run about midway
between Pulverizer and p3 in speed.

> The two are not precisely comparable, I think, because as far as I can
> tell you just encrypt a single string, whereas mine encrypts a sequence
> of strings progressively, unless I'm missing something.

Yes correct, p3.py encrypts a single string like rotor does.  Bryan
Olson did a reference implementation of an earlier version of p3, that
can be used for stream encryption.  It's in this post:

http://groups.google.com/groups?selm=3CC7889D.2080002%40nowhere.org