A few suggestions about PC1Cipher

I've been messing around with PC1Cipher a bit over the last few days, and
have a few suggestions and observations.

PC1, in case you don't know, is an alias for RC4 (the name "RC4" is
trademarked).  It is  a stream cypher that works by effectively XOR-ing the
plaintext with the output from crypo-quality psuedo-random number generator
seeded with the key.  Which, incidently, makes it very easy to misuse --
search the web for "WEP" and "weakness" for example (WEP is the
"security" -- or lack of it -- in the current generation of wireless
networking products).

-----------------

I suggest that the method PC1Cipher class>>withStrength: be removed, or at
least renamed.  It claims to answer an instance with <bits> strength of key,
but in fact the result only has 31 bits of randomness since it uses an
instance of Random seeded with:
    Delay millisecondClockValue bitOr: 1
So there are only 2**31 possible random streams.  (Actually the resultant
cypher has
    31 + (bits log: 2) - 3
bits of strength if the numher of bits used is also hidden, since the number
of times around the loop will also affect the resultant cypher).  Since my
650Mz laptop can do an exhaustive search of 2**31 keys in around 3 weeks,
and I estimate that a fast modern desktop (with a bit of C) could do the
same thing over the weekend, PC1Cipher class>>withStrength: could fairly be
described as very weak.  (BTW, the results of the brute force scan that I
mentioned could be saved and used as many times as needed -- at some cost in
disk space -- so the 3week/2day estimate for breaking it only applies the
first time, thereafter it's effectively instantaneous.)

Using PC1Cipher class>>withStrength: to create a crypto-quality PRNG is fine
and legitimate, but the name of the method promises something that it
doesn't deliver.

-----------------

If the key used in a cypher is provided by a person typing it in, then
it is likely to be short (say less than a dozen characters) and use only
a small subset of the character range.  One technique for using such
passkeys is to create an MP5 hash of the original key string and then use
that hash as the key in the cipher.  That doesn't add any strength as such,
but it does ensure that the keys used by the cypher are randomly
distributed, rather than heavily clustered around english (or whatever)
text.

Anyway, if you try that with the implementation of PC1 in Dolphin, then it
*seems* to work,
    password := 'Guess Me'.
    hash := MD5 hashMessage: password.
    cypher := PC1Cipher withKey: hash.
    cypher cipherString: 'Read Me'.
but unfortunately the cipher is only using 32 bits of key strength (and so
is very vunerable to brute force, as above).  This is because
PC1Cipher>>reset uses:
    key size
where <key> is the 16-byte LargeInteger hash, and LargeInteger>>size answers
the number of 32-bit dwords it is made of (in this case 4), not the number
of bytes, so the loop in #reset only ever uses the first 4 bytes of the
hash.  One fix would be to change #reset to use #byteSize instead of #size.
I suggest, though, that a better fix would be to define
SmallInteger>>asByteArray and LargeInteger>>asByteArray (which would be
useful for other reasons too), and then change PC1Cipher to send
#asByteArray to its key.

Incidently, PC1Cipher class>withKey: should probably be changed to make it
clearer that the key is meant to be a ByteArray (or similar) not an integer
as it currently implies.

-----------------

A PC1Cipher>>cipherBytes: method (paralleling #cipherString:, but without
the Character<->integer conversions) would be a useful addition.  Easy for
me to add, of course.

-----------------

    -- chris

[Well, nobody has followed up on this, so I suppose I'll just have to do it
myself ;-) ]

I wrote:

> Since my
> 650Mz laptop can do an exhaustive search of 2**31 keys in around 3 weeks,
> and I estimate that a fast modern desktop (with a bit of C) could do the
> same thing over the weekend, PC1Cipher class>>withStrength: could fairly
be
> described as very weak.

and:

> Anyway, if you try that with the implementation of PC1 in Dolphin, then it
> *seems* to work,
>     password := 'Guess Me'.
>     hash := MD5 hashMessage: password.
>     cypher := PC1Cipher withKey: hash.
>     cypher cipherString: 'Read Me'.
> but unfortunately the cipher is only using 32 bits of key strength (and so
> is very vunerable to brute force, as above).

Allow me to correct myself.  I had underestimated the effect of a rewrite
into C and it makes a much greater relative difference than I'd expected (I
think because the code and data all fit into L1 cache).  On the above
machine I can scan at around 100K keys/second.  So doing a complete scan of
a 32-bit keyspace takes 12 hours.   I'd guess 3 hours on a current midrange
desktop machine.

If you have used PC1Cipher (aka RC4) in a way that reduces your real key
strength to 31 or 32 bits then your security should not so much be described
as "very weak", as "nonexistant".  The bugs I mentioned have just that
effect.

    -- chris

Chris,

Thanks for pointing all this out. As a result, for the next patch release,
we have re-implemented PC1Cipher class>>withStrength: to (hopefully)
correctly generate and use n-bit random numbers. The algorithm we use is
take from Applied Cryptography (Scheier) p427 except that we use SHA for the
hash rather than MD5. The algorithm is a bit like the one you suggest below
except that it uses several "mix and merge" hashes seeded off a real world
random number driven by random events. Hopefully it will improve the
security somewhat.

Best Regards,

Andy Bower
Dolphin Support
http://www.object-arts.com
---
Are you trying too hard?
http://www.object-arts.com/Relax.htm
---

"Chris Uppal" <[hidden email]> wrote in message
news:[hidden email]...
> [Well, nobody has followed up on this, so I suppose I'll just have to do
it
> myself ;-) ]
>
> I wrote:
>
> > Since my
> > 650Mz laptop can do an exhaustive search of 2**31 keys in around 3
weeks,
> > and I estimate that a fast modern desktop (with a bit of C) could do the
> > same thing over the weekend, PC1Cipher class>>withStrength: could fairly
> be
> > described as very weak.
>
> and:
>
> > Anyway, if you try that with the implementation of PC1 in Dolphin, then
it
> > *seems* to work,
> >     password := 'Guess Me'.
> >     hash := MD5 hashMessage: password.
> >     cypher := PC1Cipher withKey: hash.
> >     cypher cipherString: 'Read Me'.
> > but unfortunately the cipher is only using 32 bits of key strength (and
so
> > is very vunerable to brute force, as above).
>
> Allow me to correct myself.  I had underestimated the effect of a rewrite
> into C and it makes a much greater relative difference than I'd expected
(I
> think because the code and data all fit into L1 cache).  On the above
> machine I can scan at around 100K keys/second.  So doing a complete scan
of
> a 32-bit keyspace takes 12 hours.   I'd guess 3 hours on a current
midrange
> desktop machine.
>
> If you have used PC1Cipher (aka RC4) in a way that reduces your real key
> strength to 31 or 32 bits then your security should not so much be
described
> as "very weak", as "nonexistant".  The bugs I mentioned have just that
> effect.
>
>     -- chris
>
>
>