Contest Ideals & Cryptanalysis (WAS: RE: [HARDWARE] ongoing work)

Matthew Smart mcsmart at engin.umich.edu
Sun May 2 14:52:48 EDT 1999


There is no CRC value in the RC5 algorithm.

mattSMART


-----Original Message-----
From: owner-hardware at lists.distributed.net
[mailto:owner-hardware at lists.distributed.net]On Behalf Of Paul Williams
Sent: Sunday, May 02, 1999 5:18 AM
To: hardware at lists.distributed.net
Subject: Contest Ideals & Cryptanalysis (WAS: RE: [HARDWARE] ongoing
work)


Sorry for my tardiness in reply to this subject...

I think the point of this Contest is to prove the weakness of the encryption
algorithm.  Any weakness, not just by brute force.  So the idea would be to
try any trick you can to throw out extraneous possibilities.  Anyway, The
Contest gives no specific rules on how the encryption must be broken -- they
don't care, just as long as you can break it.

I have actually given some thought to the cryptanalyis ideas, but I am  not
a mathematician, and am as such unclear as to the possibility of using such
an analysis against RC5.

I know that some cyphers you can test against a sample subset of the
keyspace, compare with some known value, and if anything reasonable comes of
it then you can reduce the whole keyspace...  Somewhere in the RC5 cypher, I
believe, a CRC value is embedded (to check for message validity)... Could
keys which produce a valid CRC value be related mathematically to each other
to reduce the possible keyspace?

Paul Williams -------------------------------
Programs Coded, Web Content Provided,
Images Traced, Raytraced, and Retraced
PGP Key ID: 0xF3467A30 (Others exist, but this is me...)



> -----Original Message-----
> From: owner-hardware at lists.distributed.net
> [mailto:owner-hardware at lists.distributed.net]On Behalf Of Totermann
> Sent: Tuesday, April 27, 1999 4:45 PM
> To: hardware at lists.distributed.net
> Subject: Re: [HARDWARE] ongoing work
>
>
> There's only one probem with that... As I believe it, this
> competition is about
> doing it via the "Brute Force" method, without using any special
> tricks.  This shows
> the *minimum* average time required to crack a given code.  This
> time is then used
> to intimidate cypher designers to come up with bigger & better cyphers.
>
> Robert Norton wrote:
>
> > Hi Matt,
> >
> > I'm guessing the first 64 bits would be "The unkn" if 8 bit bytes are
> > being used.  I think the big flaw in trying to go backwards is that
> > you can know that A exclusive-or'ed with B is a 1, and still not
> > know what either A or B is.
> >
> > Still, I had an idea somewhat along those lines.  If RC5 is a giant
> > mix master of the bits, it does so by going along many steps of
> > blending.  If you could run backwards from the final one step, and
> > still know some of the bits, say maybe 20 of the 64, then you could
> > do a encoding pass up to just befoe the last step, and check only
> > those 20 bits that are known.
> >
> > If the thing matches, then you have a code worth doing all the way,
> > you will only have to redo going all the way once per million tries
> > on the average, and all the other 999,999 tries will be shorter by
> > one step, thus speeding up the process as a whole.
> >
> > Possible?  Comments?
> >
> > Bob Norton.
> >
> > Matthew Smart wrote:
> >
> > > But RC5 is a symmetric algorithm, so decrypting is just as easy as
> > > encrypting.  And you only need to decrypt/encrypt the first
> block (64 bits)
> > > and compare it against the ASCII representation of "The ",
> which is the
> > > first part of "The unknown message is: ".
> > >
> > > So encrypting "The " and comparing against the given
> cyphertext should be
> > > the same as decrypting the first block of the cyphertext and comparing
> > > against "The ".
> > >
> > > mattSMART
> > >
> > > -----Original Message-----
> > > From: owner-hardware at lists.distributed.net
> > > [mailto:owner-hardware at lists.distributed.net]On Behalf Of Darxus
> > > Sent: Tuesday, April 27, 1999 2:13 PM
> > > To: hardware at lists.distributed.net
> > > Subject: Re: [HARDWARE] ongoing work
> > >
> > > On Tue, 27 Apr 1999, Matthew Smart wrote:
> > >
> > > > I just subscribed to this list.  Are there any people who
> are actually
> > > > running RC5 cracking hardware they created?  Are there
> ongoing projects?
> > > >
> > > > I'm currently working with another grad student to create a
> Verilog model
> > > of
> > > > an RC5-32/12/x encrypt/decrypt engine.
> > >
> > > http://www-inst.eecs.berkeley.edu/~barrel/rc5.html
> > >
> > > > One more question: from the client source code it looks
> like the clients
> > > do
> > > > encryption then compare instead of doing decryption.  Any
> specific reason
> > > > why?
> > >
> > > These are all one way encryption.  Unless you break it (which to our
> > > knowledge has not been done), it can not be decrypted.
> > >
> > > Your are correct in your interpretation of the code.
> > > __________________________________________________________________
> > > PGP fingerprint = 03 5B 9B A0 16 33 91 2F  A5 77 BC EE 43 71 98 D4
> > >             darxus at op.net / http://www.op.net/~darxus
> > >                         Pain makes you real.
> > >
> > > --
> > > To unsubscribe, send 'unsubscribe hardware' to
> > > majordomo at lists.distributed.net
> > >
> > > --
> > > To unsubscribe, send 'unsubscribe hardware' to
> majordomo at lists.distributed.net
>
> --
> To unsubscribe, send 'unsubscribe hardware' to
> majordomo at lists.distributed.net
>

--
To unsubscribe, send 'unsubscribe hardware' to
majordomo at lists.distributed.net

--
To unsubscribe, send 'unsubscribe hardware' to majordomo at lists.distributed.net



More information about the Hardware mailing list