RSA's RC5-64 Secret Key Challenge has been solved.

[Trei, Peter]

> Ralf-P. Weinmann[SMTP:weinmann at cdc.informatik.tu-darmstadt.de] wrote:
> 
> 
> On Thu, Sep 26, 2002 at 02:45:12PM -0700, John Gilmore wrote:
> > [...]
> > 
> > After getting that getting started, though, I suggest beginning a
> > brute-force attack on the GSM cellphone encryption algorithm.  That's
> > in use in hundreds of millions of devices worldwide, protecting (or
> > failing to protect) the privacy of billions of phone calls a day.
> 
> Is A5/3 deployed yet? If not, a brute force attack is not needed, for A5/1
> and
> A5/2 more efficient tools exist to cryptanalyse it. Even in real-time,
> although
> you might need to invest in some hard disk space before being able to
> eavesdrop
> and intercept. See the following paper for more information:
> 
> "A. Biryukov, A. Shamir and D. Wagner, Real Time Cryptanalysis of A5/1 on
> a PC"
> 
> As for A5/3, I'm not really sure what key length network operators
> are/will be
> using, 64-128 bits are allowed in the design requirements documentation.
> The
> specification should be available on the 3GPP website. A5/3 is based on
> Kasumi.
> 
> Cheers,
> Ralf
> 
I spoke to David McNett (nugget at distributed.net) yesterday. He told me that
they intend to fire up a the RC5-72 challenge, hoping to get lucky and find
the key near the beginning.

I think they're open to other suggestions, however. Factoring may or may not
be reasonable. While RC5, DES, etc require minimal memory and storage,
and can so run unobtrusively in the spare cycles of almost any machine,
factoring,
- even the seiving step - has large memory and storage requirements. The
matrix reduction step at the end does not have any efficient distributed
implementation
I'm aware of.

I think the lower RSA factoring challenges *may* be possible - RSA-576 is
still
standing, with a $10k prize. Other factoring challenges have up to $200k
prizes.

Challenges need to be carefully set up. It must be legal - hacking a
deployed
system in the face of the objections of the owner won't fly. It must be
credible,
in that there must be no reason to suspect collaboration between the 
challenger and the attacker. It must be realistic - it should model a
real-world
use closely enough to show that changes need to be made (the RSA secret
key challenges where designed with IPSEC headers in mind - the single DES
option was deprecated as soon as we showed that to be weak).

This is an exciting time. With RC5-64 fallen, there are a lot of options for
what
to do next. The most interesting thing may not involve cryptanalysis.

Peter Trei



---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com