Cryptography-Digest Digest #344, Volume #14 Sat, 12 May 01 16:13:00 EDT
Contents:
Re: OAP-L3: "The absurd weakness." (Anthony Stephen Szopa)
Re: DES Crypto Myth?? ([EMAIL PROTECTED])
Re: DES Crypto Myth?? ("Simon Johnson")
Re: Is Differential Cryptanalysis practical? ([EMAIL PROTECTED])
Re: Comparison of Diff. Cryptanalysis countermeasures ([EMAIL PROTECTED])
Re: Is Differential Cryptanalysis practical? ("Tom St Denis")
Re: Comparison of Diff. Cryptanalysis countermeasures ("Tom St Denis")
Re: Comparison of Diff. Cryptanalysis countermeasures (SCOTT19U.ZIP_GUY)
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
(SCOTT19U.ZIP_GUY)
Re: Comparison of Diff. Cryptanalysis countermeasures (SCOTT19U.ZIP_GUY)
Re: Is Differential Cryptanalysis practical? (David Wagner)
Re: DES Crypto Myth?? (David Wagner)
Re: DES Crypto Myth?? ("Roger Schlafly")
Re: Comparison of Diff. Cryptanalysis countermeasures (David Wagner)
----------------------------------------------------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker,talk.politics.crypto
Subject: Re: OAP-L3: "The absurd weakness."
Date: Sat, 12 May 2001 12:13:41 -0700
Xcott Craver wrote:
>
> Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> >Xcott Craver wrote:
> >>
> >> You might be under the false impression that people respond
> >> to your posts out of interest in your cipher, when in fact
> >> they only do so to inform 3rd parties, who may have recently
> >> taken a peek into sci.crypt, that you are one of the regular
> >> crackpots.
> >
> >Anyone who would let you do their thinking for them deserves
> >no better.
>
> Look, if you think you know so fricking much about crypto,
> I'll be happy to challenge you with some basic questions
> about permutation groups. Your cipher is based so much
> on permutations, after all, that if you can't answer some
> basic Qs about permutations, then you are unmasked as a
> con-man. Game? Agree? Disagree?
>
> I'm going to go out on a limb, and accuse you of hawking
> a cipher you just hobbled together with no actual
> mathematical or cryptological expertise. I would like
> to see you prove me wrong. For instance, how about a
> proof of the orbit counting lemma? Do you even know what
> the orbit counting lemma is?
> -S
>
> [That's actually an easy one, 'cos you can look it up.]
I am sorry that OAP-L3 has confounded you to the point that you must
now pursue fleeting rabbits of diversion and distraction.
Can't you give us the slightest reason why OAP-L3 might be insecure
and support such an assertion with a specific and a demonstration
instead of hand waving and venting?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: DES Crypto Myth??
Date: Sat, 12 May 2001 10:20:24 -0800
DJohn37050 wrote:
>
> Versions of other ciphers that were JUST invented were broken when diffl.
> cryptanalysis came out, but NOT DES. This cannot be by coinkydinky. And
> Coppersmith says it was not, but was deliberate in his paper published in IBM
> JRD. So the designers knew about it, but did not disclose it as it was not
> generally known and why tell bad guys how to do things?
> Don Johnson
One thing still bothers me...The account I read said that the NSA
modified
the S-boxes that the IBM team developed, and that these boxes were
magically
resistant to diff. cryptanalysis. If the NSA optimized the S-boxes, it
seems
to indicate that the IBM teams were less than optimal.
Can anyone clear this up?
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: DES Crypto Myth??
Date: Sat, 12 May 2001 20:19:54 +0100
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:rv7L6.72860$[EMAIL PROTECTED]...
>
> <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> >
> > I've been reading through papers on differential cryptanalysis and s-box
> > generation and I seem to have uncovered a myth regarding DES that I've
> > run across several times (i.e. _Applied Cryptography_, posts on this
> > newsgroup, etc.).
> >
> > The myth is that the DES team knew about differential cryptanalysis (I
> > think
> > Coppersmith makes this claim) esp. iterative characteristics, and
> > specifically
> > designed the S-boxes to be resistant ("robust") to differential
> > cryptanalysis.
> > I've also read in several different places that the changes that the NSA
> > made
> > to the S-boxes were intended to increase their resistance to
> > differential
> > cryptanalysis.
> >
> >
> > The problem with this "common crypto knowledge" is that the DES S-boxes
> > aren't
> > very robust! According to Seberry, Zhang, and Zheng in "Systematic
> > Generation
> > of Cryptographically Robust S-boxes" (1994) the robustness of the DES
> > S-boxes
> > range from 0.316 and 0.469 which is much lower than the upper bound of
> > 0.861
> > for 6x4 S-boxes.
> >
> > It seems to me that either the claim that the DES team knew about
> > differential
> > cryptanalysis isn't true, or they didn't understand it well enough to
> > design
> > S-boxes with close to optimal robustness.
> >
> > Am I missing something?
>
> Actually for DES the sboxes they picked were about as good as you can use.
> In general it's true you can pick more nonlinear less differential
sboxes...
> such as
>
> const unsigned sbox[1][64] = {
> { 3, 1, 2, 5, 7, 6, 4, 12, 15, 11, 8, 10, 13, 9, 0, 14,
> 15, 7, 11, 3, 2, 13, 14, 8, 12, 5, 4, 10, 9, 0, 6, 1,
> 4, 14, 15, 10, 13, 8, 0, 3, 5, 11, 6, 2, 9, 12, 7, 1,
> 3, 14, 0, 13, 1, 10, 11, 9, 5, 15, 12, 6, 2, 8, 7, 4 } };
>
> (lpmax is 10/64, dpmax is 12/64)
>
> But this sbox would probably suck in DES since it doesn't follow the
> required design.
>
> So I would believe that they knew about the attacks.
>
> Tom
What Tom is touching on, was that the DES team knew about Differential
Cryptanalysis... but they did not know about linear cryptanalysis... so
however your robustness quantity is defined it probably includes resistance
to linear cryptanalysis which would explain how it strayed so far from the
optimal.
Simon.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is Differential Cryptanalysis practical?
Date: Sat, 12 May 2001 10:25:39 -0800
Simon Johnson wrote:
>
> >
>
> I agree, that kind of break is impractical... however, its existence is
> still _useful_.. We can use this break to suggest a key change every 2^49
> plain-texts is prudent. In a way, the academic breaks are useful because
> they allow us to compare the relative securities of ciphers.
>
> Simon.
I fully agree that it is very useful, and the technique itself was fun
to study
...it was downright fascinating! I wonder what set Biham and Shamir down
that path
to begin with?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 10:32:16 -0800
Tom St Denis wrote:
> > > b) Not all attacks are based on specific differences.
> >
> > Enlighten me.
> >
> > The differential attacks that I've been able to study are based on being
> > able to assign a probability of a diff round output for a diff round
> > input.
> > If you don't know the S-box contents, how can you do that by looking at
> > the diff input and diff output of the entire algo? If you don't know the
> > probability for a round, you can't determine the probability for the
> > full round cipher.
> > If you don't know the probability for the full round cipher, how do you
> > distinguish the key?
>
> Not all attacks are based on saying "an input diff of 0x55BB leads to an
> output difference of 0x1234". They could say "an input difference of
> (0,0,x,y) leads to (a,b,0,0) where x,y,a,b are nonzero".
>
> Tom
Ok, but does that eliminate the necessity of finding a round probability
for these non-zero input / output diffs?
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Is Differential Cryptanalysis practical?
Date: Sat, 12 May 2001 19:29:55 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Simon Johnson wrote:
> >
>
> > >
> >
> > I agree, that kind of break is impractical... however, its existence is
> > still _useful_.. We can use this break to suggest a key change every
2^49
> > plain-texts is prudent. In a way, the academic breaks are useful because
> > they allow us to compare the relative securities of ciphers.
> >
> > Simon.
>
>
> I fully agree that it is very useful, and the technique itself was fun
> to study
> ...it was downright fascinating! I wonder what set Biham and Shamir down
> that path
> to begin with?
Probably they looked at statistical analysis (I think that occured first)
and modified it.... Differential attacks were used before Biham on FEAL-4 by
Sean Murphy which according to AC2 is the first published
differential-cryptanalysis attack.
See "S.Murphy, "The Cryptanalaysis of FEAL-4 with 20 chosen plaintexts,"
Journal of Cryptology V.2, n.3 1990, pp 145-154".
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: Sat, 12 May 2001 19:32:22 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
>
> > > > b) Not all attacks are based on specific differences.
> > >
> > > Enlighten me.
> > >
> > > The differential attacks that I've been able to study are based on
being
> > > able to assign a probability of a diff round output for a diff round
> > > input.
> > > If you don't know the S-box contents, how can you do that by looking
at
> > > the diff input and diff output of the entire algo? If you don't know
the
> > > probability for a round, you can't determine the probability for the
> > > full round cipher.
> > > If you don't know the probability for the full round cipher, how do
you
> > > distinguish the key?
> >
> > Not all attacks are based on saying "an input diff of 0x55BB leads to an
> > output difference of 0x1234". They could say "an input difference of
> > (0,0,x,y) leads to (a,b,0,0) where x,y,a,b are nonzero".
> >
> > Tom
>
> Ok, but does that eliminate the necessity of finding a round probability
> for these non-zero input / output diffs?
Let's say you have a 32-bit function that works on 8-bit units i.e
(x1,x2,x3,x4) => (y1,y2,y3,y4). There are 2^32 - 1 possible output
differences and if the function is random then some difference like
(0,0,x1,x2) => (y1,y2,0,0) should occur each with a prob of 1/(2^32 - 1).
Let's say that differential holds with a prob of 1/(2^-14) instead. We
don't know the values of x1/x2/y1/y2 other than they are non-zero.
I can now use that differential to distinguish the cipher from random and in
turn find the key through elimination.
Tom
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: 12 May 2001 19:43:10 GMT
[EMAIL PROTECTED] (Mok-Kong Shen) wrote in <3AFD7937.16BE2AA2@t-
online.de>:
>
>
>"SCOTT19U.ZIP_GUY" wrote:
>>
>[snip]
>> One way the way I choose was to use a bigger S-box like 16X16
>> or 19X19. And then made the key selelct from a very large class
>> of S-boxes. I choose S-boxes so that any single cycle permutaion
>> would be allowed. Then tested what the output characteristics
>> of the simplest weakest single cycle S-boxes were used. Namely
>> sequential ones like a = a +1. Very simple but not very likeely
>> and then exaimed the ouputs of different types of files using
>> DIEHARD. Of course if you pick any small subset of S-boxes it would
>> then it would be easy to break. But in reality no matter what you
>> pick every key could be considered weak in the sense that an attacker
>> need only check for that key.
>[snip]
>
>How many 19*19 S-boxes would you in general use? I mean
>wouldn't the storage requirement be quite excessive and
>the generation time also be quite substantial? Thanks.
>
>M. K. Shen
Well I use only one in forward and reverse.
But code is such that any possible single cycle
S box could have been used in case there is some
you really like.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: 12 May 2001 19:48:12 GMT
Jim D (Jim D) wrote in <[EMAIL PROTECTED]>:
>On 11 May 2001 17:37:34 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
>wrote:
>> Hell when I was a kid
>>I took a gun to school. My NRA safety class required you to bring
>>your own 22. Now adays people shit in there pants when a kid takes
>>a gun to school. The view is different because the liberals have
>>fucked it up and destroyed values.
>
>Isn't America a wonderful place? ! Rather you than me, pal!
>
Well it still can be a wonderful place is long is the liberals
don't force communsium on us. At least we still have part of our
freedoms in place. But they are slipping away. I hope that if
you like the current UK government so much. Maybe when Clinton
gets knighted you folks can elect him to run your country.
And then maybe what he has done to us he can do to you.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: 12 May 2001 19:40:58 GMT
[EMAIL PROTECTED] wrote in <[EMAIL PROTECTED]>:
>
>This brings up a related question that's been bothering me. I've studied
>how redundancy in language allows the cryptanalyst to determine if a
>randomly chosen decryption key is correct because keys that give
>meaningless decryptions can be eliminated. The probability of obtaining
>a meaningful message with a randomly chosen decryption key is small, so
>if a meaningful message is obtained, the decryption key used is almost
>certainly the right key.
>
>I'm not sure how this applies to a digital system, esp. a block cipher.
>Is there any redundancy, i.e. are there "meaningless" 64-bit values
>(for a 64-bit block cipher) and if so how does the cryptanalyst
>distinguish meaningless values from meaningful values? For ASCII it
>should be fairly easy, but not everything is ASCII.
>
>Redundancy pops up in several equations (unicity distance, for example)
>so it's an important concept, but I'm not sure what redundancy in
>a digital system really is.
>
>How can one tell that a 64-bit block is "meaningful" or "meaningless"?
>
You bring up an interesting point. Most files are not ascii. So
how does one tell if the 64-bit block is "meaningful or meanginless".
In isolation you can't and any is possible. But in the real world
crypto systems like PGP. When its time to actaully encrypt the data
two things are usually done to it to make it easier to break. One
is that PGP puts a partial check to see if your decrypting with
correct key. This mechanism is desinged so one could elminate most
the keys right aways as being bad. The second major weakness is that
nonbijective compression is done to the data before encryption so
that if one even tries to test a wrong key it would either fail the
key test or fail to decompress correctly. That way even if the file
your encrypting with something like PGP was 100% random. There is likely
only one key that can pass both the key test and the decompression
correctly.
I think PGP and the like are designed with these flaws so the
NSA can still easily read messages. Of course to keep people using
them they have to espose other flaws now and then so they can fix
them and keep people hooked.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Is Differential Cryptanalysis practical?
Date: 12 May 2001 20:04:45 GMT
Noone ever claimed that the differential cryptanalytic attack
was practical (except possibly in some special circumstances).
Indeed, DES can be viewed as surprisingly strong against d.c.,
when compared to other ciphers designed before discovery of d.c.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES Crypto Myth??
Date: 12 May 2001 20:07:19 GMT
>The myth is that the DES team knew about differential cryptanalysis
Why do you think it's a myth? All available evidence says they
knew about it and did a very good job designing for strength against
it, given the constraints.
>The problem with this "common crypto knowledge" is that the DES S-boxes
>aren't very robust!
Who cares? The properties of the S-boxes on their own don't matter
diddly squat -- it's the properties of the DES cipher as a whole that
matter.
You *really* need to read Coppersmith's paper before coming to any
conclusions on this topic.
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: DES Crypto Myth??
Date: Sat, 12 May 2001 19:08:29 GMT
<[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> It seems to me that either the claim that the DES team knew about
> differential
> cryptanalysis isn't true, or they didn't understand it well enough to
> design S-boxes with close to optimal robustness.
I think you are right that the claim is exaggerated. Coppersmith only
claims that the team had leaked info that it was good to test the cipher
on inputs that differ by a small amount, and compare the difference
of the outputs. Apparently that influenced which S-boxes were chosen.
But even if they had understood differential cryptanalysis well, they
still might not have regarded "optimal robustness" as a necessity.
After all, the best attack on DES is still brute force.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of Diff. Cryptanalysis countermeasures
Date: 12 May 2001 20:09:00 GMT
>Differential analysis assumes that you know the contents of the S-boxes.
Not always, not necessarily.
(although often key-dependent S-boxes seem to be more resistant
to differential cryptanalysis)
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
