Cryptography-Digest Digest #821, Volume #12 Tue, 3 Oct 00 03:13:01 EDT
Contents:
Re: Choice of public exponent in RSA signatures (David Wagner)
Re: It's Rijndael (David Blackman)
Re: Idea for Twofish and Serpent Teams (David Blackman)
Re: Choice of public exponent in RSA signatures ("John A.Malley")
Re: It's Rijndael ("Scott Fluhrer")
Re: Advanced Encryption Standard - winner is Rijndael (SCOTT19U.ZIP_GUY)
Re: is NIST just nuts? (David Blackman)
Re: My Theory... ("Scott Fluhrer")
Another Rijndael/AES rumor (Paul Rubin)
Re: is NIST just nuts? (Mok-Kong Shen)
Re: On block encrpytion processing with intermediate permutations (Mok-Kong Shen)
Re: Another Rijndael/AES rumor ("Paul Pires")
Re: is NIST just nuts? ("Herbie T. Mac")
Re: Comments on the AES winner (Mok-Kong Shen)
Re: Comments on the AES winner (Mok-Kong Shen)
Re: It's Rijndael (Arturo)
Re: is NIST just nuts? (Arturo)
Re: Idea for Twofish and Serpent Teams (Arturo)
Re: Advanced Encryption Standard - winner is Rijndael (Arturo)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Choice of public exponent in RSA signatures
Date: 3 Oct 2000 04:33:33 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Yes, I am familiar with those attacks. As I said, with proper use of
random padding (e.g., OAEP), the attacks do not apply. Thus, I do not
see why they should provide a justification to prefer e>3.
And, in real life, everyone uses random padding, and the random padding is
large enough to avoid Coppersmith's attack. Hastad's and Coppersmith's
attack are of great theoretical interest, but they do not apply to any
real-world implementation that I know of.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Date: Tue, 03 Oct 2000 15:51:44 +1100
John Savard wrote:
>
> MARS, RC6, E2, and DFC all required multiplications, which would have
> tended to slow them somewhat: but both Rijndael and Twofish require
> GF(8) multiplications: as these aren't a standard instruction, I would
> have thought them even worse.
In most implementations of Rijndael and Twofish the GF multiplications
will disappear into the SBOX lookups.
For the others with integer multiplications, that optimisation isn't
practical.
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: Idea for Twofish and Serpent Teams
Date: Tue, 03 Oct 2000 15:56:38 +1100
Andru Luvisi wrote:
>
> Tom St Denis <[EMAIL PROTECTED]> writes:
> [snip]
> > Try saying that to Mr Schneier or Dr. Biham....
> [snip]
>
> Mr. Schneier said "It would be really cool to win, but mostly it's
> just been a *lot* of FUN!"
>
> *You* seem to be the one who is sore about the whole thing...
>
> Andru
> --
> Andru Luvisi, Programmer/Analyst
I think this result gives both Schneier and Biham even more fun than if
they won themselves. Both these guys are among the best cryptanalists
who can publish. Now they have a single target that stands out above all
others. And that target looks somewhat breakeable ...
------------------------------
From: "John A.Malley" <[EMAIL PROTECTED]>
Subject: Re: Choice of public exponent in RSA signatures
Date: Mon, 02 Oct 2000 21:55:57 -0700
David Wagner wrote:
>
> Yes, I am familiar with those attacks. As I said, with proper use of
> random padding (e.g., OAEP), the attacks do not apply. Thus, I do not
> see why they should provide a justification to prefer e>3.
I no nothing about OAEP and thus cannot respond. I will go and read up
on it - there should be papers at the Counterpane crypto on-line
library.
Is there a "must-read" paper or a set of "must-read" papers on OAEP you
recommend?
>
> And, in real life, everyone uses random padding, and the random padding is
> large enough to avoid Coppersmith's attack.
With e = 65537 the padding can be smaller than the padding required for
e = 3 while maintaining resistance against Coppersmith's Short Pad
Attack. Since less bits in the string to encrypt must be random pad
more bits in the string can be message bits - and thus there is more
bandwidth for the message. Isn't this a point in favor of using e =
65537?
> Hastad's and Coppersmith's
> attack are of great theoretical interest, but they do not apply to any
> real-world implementation that I know of.
Attacks like these lead to better crypto algorithms - these attacks
inspired the use of random padding in the real-world RSA implementations
of which we speak.
TIA for any pointers to info on OAEP,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Date: Mon, 2 Oct 2000 21:47:12 -0700
David Schwartz <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> John Savard wrote:
> >
> > On Tue, 03 Oct 2000 00:19:38 +0100, David Hopwood
> > <[EMAIL PROTECTED]> wrote, in part:
> >
> > >Yes; assuming Rijndael behaves similarly to a random cipher, there are
> > >expected to be 2^64 192-bit keys, and 2^128 256-bit keys that would
> > >satisfy this. However, it would require on the order of 2^128
encryptions
> > >to find such a key.
> >
> > And, of course, being able to find it is equivalent to being able to
> > crack Rijndael, so finding it would *not* be happy news.
>
> How do you figure?
>
> As an imperfect analogy to show why this is not so, think of a one time
> pad. If you know the first X bytes of plaintext and the first X bytes of
> ciphertext, you can produce a key that would produce that ciphertext for
> that plaintext. However, that key is no more likely than any other to
> correctly decrypt the next byte.
However, it's not a one time pad. Assuming that you do find such a 256 bit
key in rather less than 2^128 work, and further assuming (as per David
Hopwood) there are about 2^128 such keys, then you have found the correct
key with probability 2^-128, and with less than 2^128 work, this is better
than brute force...
--
poncho
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Crossposted-To: alt.security.scramdisk
Subject: Re: Advanced Encryption Standard - winner is Rijndael
Date: 3 Oct 2000 05:08:00 GMT
[EMAIL PROTECTED] (jungle) wrote in <[EMAIL PROTECTED]>:
>read again my press note, it is there ...
>
>additionally it is in Published in the January 2, 1997 issue of the
>Federal Register: DEPARTMENT OF COMMERCE National Institute of Standards
>and Technology [Docket No. 960924272-6272-01] RIN 0693-ZA13 document ...
>
>"It is intended that the AES ... algorithm capable of protecting
>sensitive government information ..."
>
>David Schwartz wrote:
>>
>> "SCOTT19U.ZIP_GUY" wrote:
>>
>> > Also the US does not consider it secure encough
>> > for classed information.
>>
>> Do you have a reference for this claim?
>
>
>
Your own quote it is intended that AES ... protecting
sensitive government information. Sensitive is not even
considered classifed. It is below confidential info and
is to low to be considered classifed.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: David Blackman <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Date: Tue, 03 Oct 2000 16:50:07 +1100
Tom St Denis wrote:
> They said "Rijndael performs well on a variety of platforms" but from
> what I have seen Twofish does just as well. What is their
> justification for not picking Twofish?
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
In custom hardware, Rijndael requires a lot less gates than Twofish and
runs somewhat faster. One of the guys doing hardware evaluation of the
finalists said something like "As a hardware guy, i really like
Rijndael. As a crypto guy, i've got my doubts." (It's on the AES
website, somewhere :-)
I think Rijndael might be a bit faster in software than Twofish, if you
do the same extreme optimisations the Twofish team did. I don't know of
anyone who's tried this yet, but it will certainly happen now.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: My Theory...
Date: Mon, 2 Oct 2000 22:43:09 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:8rb78n$ijl$[EMAIL PROTECTED]...
> In article <[EMAIL PROTECTED]>,
> Cornelius Sybrandy <[EMAIL PROTECTED]> wrote:
> > > > Well, that's my theory. Do I believe that Rijndael is a suitable
> AES
> > > > winner? Yes. Do I believe it needs more rounds? From the
> evidence
> > > > I've seen, yes. I honestly believe that the standard should
> increase
> > > > the number of rounds especially since it appears it will not have
> a
> > > > great affect on the performance of the cipher on the up and coming
> > > > 64-bit processors.
> > >
> > > This is true.
> > >
> > > So what? The primary concern is security, not speed.
> > >
> > > Tom
> > >
> > > Sent via Deja.com http://www.deja.com/
> > > Before you buy.
> >
> > What I was trying to say was that because of the scalability of
> Rijndael you
> > can increase the rounds without causing a significant detriment to
> speed on
> > the up and coming PC platforms. We all know, of course, that 64-bit
> chips
> > have been around for years, though I think I alluded to the fact that
> they
> > are new in my prior text. I never said that security was not the
> primary
> > concern, I was only trying to paint a better picture of what their
> train of
> > thought migh have been.
>
> So the millions of 32-bit i386+ chips are not included in this
> thought? Also how slow is Twofish on a ia64 anyways?
Since I happen to have on hand the figures from a paper presented at AES3:
On an IA-64 simulator (an actual CPU was not available), Twofish used 182
cycles to encrypt or decrypt a single block (fully expanded key schedule).
In constrast, Rijndael used 124/125 cycles to encrypt/decrypt a single
block. In both cases, 128 bit keys were used (larger keys would slow
Rijndael down more than Twofish, because it does additional rounds).
--
poncho
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Another Rijndael/AES rumor
Date: 02 Oct 2000 23:31:26 -0700
This came through an anonymous remailer to the cyphperpunks list a
few days ago:
At 9:50 PM +0200 9/30/2000, Nomen Nescio wrote:
>
>Though NIST is being very secretive regarding the AES announcement,
>they let the following rumors leak:
>
>1. There is a single winner.
>2. It is not an American design.
>
>If so, this rules out MARS, RC6, and Twofish. But now comes the
>third rumor:
>
>3. The winner is not covered by any patent or patent claim
>identified or disclosed to NIST by interested parties.
>
>Assuming this is true, there is only one algorithm that is not
>explicitly mentioned in Hitachi's claim: Rijndael.
This makes it plausible that staying away from patents was a factor in
Rijndael's selection.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Date: Tue, 03 Oct 2000 08:48:57 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >
> > Tom St Denis wrote:
> > >
> > > As if that was picked... From what I understand it's not at all
> close
> > > to the securest block cipher. Will aes specify that cipher with
> more
> > > rounds? What a shame...
> > >
> > > I demand a recount! Twofish should have won!
> >
> > I guess that there are lots of people at NIST having
> > superior crypto knowledge than you. If they are nuts .....
>
> Oh shut up. Rijndael has had more rounds broken then any of the other
> finalists. And when you give Rijndael the 18 rounds it requires it's
> no better performance wise then Twofish.
>
> Granted the attack against Rijndael doesn't break all the rounds and is
> in no way practical, but then again when NBS decided on DES they
> thought 56 bit keys were ok. Am I the only one to notice a pattern
> here?
I see that the vanity of persons is without limits.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On block encrpytion processing with intermediate permutations
Date: Tue, 03 Oct 2000 08:57:18 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
>
> > > I see nothing about how the sender and receiver syncronize,
> > > only that the key for the permutation should be independent
> > > of the key to the block cipher.
>
> > Each session uses a (different) secret seed for the PRNG.
> > (I use effectively more key material, as said in a previous
> > follow-up.)
>
> Does your method requires a separate secure channel for
> transporting the per-message keys? How do the sender
> and receiver know which key to use?
They get the material with the same channel at the
same time. Send some longer material, one part for the
encryption key, the other part for the seed. That
seed is for the whole session, which may consist of
a number of messages. The PRNG is not reset during the
session. Whether you like to change key for each message
is independent of my scheme.
>
> [...]
> > > Hard to sell exposing the key as a good thing.
> >
> > Sorry, the above sentence is difficult for me (foreigner)
> > to understand.
>
> Hard to take that seriously.
Does that constitute a concrete answer that I requested
(see the part you snipped)?? (A yes/no is anyway needed.
And some explanations.)
M. K. Shen
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Another Rijndael/AES rumor
Date: Mon, 2 Oct 2000 23:41:27 -0700
Paul Rubin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> This came through an anonymous remailer to the cyphperpunks list a
> few days ago:
>
> At 9:50 PM +0200 9/30/2000, Nomen Nescio wrote:
> >
> >Though NIST is being very secretive regarding the AES announcement,
> >they let the following rumors leak:
> >
> >1. There is a single winner.
> >2. It is not an American design.
> >
> >If so, this rules out MARS, RC6, and Twofish. But now comes the
> >third rumor:
> >
> >3. The winner is not covered by any patent or patent claim
> >identified or disclosed to NIST by interested parties.
I read this to mean that NIST was not notified that Rijndel was infringing on
any known patent.
> >
> >Assuming this is true, there is only one algorithm that is not
> >explicitly mentioned in Hitachi's claim: Rijndael.
>
> This makes it plausible that staying away from patents was a factor in
> Rijndael's selection.
If the above interpretation is used, this says nothing about "staying away
from patents was a factor in Rijndael's selection.".
Paul
------------------------------
From: "Herbie T. Mac" <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 03 Oct 2000 01:49:45 -0500
Actually Mark is right.
There are two reasons why conspiracy theorists such as our friend Scott
believe that the NSA weakened DES. First is the changing of S-Boxes.
Mark is correct to point out that this strengthened DES against an attack
(differential) which would not be publicly known for another 15 years.
In this manner, they made it *more* difficult for them to break and
additionally, perhaps more importantly, more difficult for others to break
when we actually figured out this differential cryptanalysis.
As far as shortening the key length from 64 to 56 bits, that too
*strengthened* the algorithm with respect to DES' differential
vulnerability. 64-bit DES is equally as difficult to crack using
differential cryptanalysis as 56-bit. The change made DES faster
(encryption) while not compromising the intended security or reducing the
time it took the NSA to crack it (assuming they ever bothered).
They did us a tremendous favor, given the absurd amount of time the DES
has been used.
herbie
In article <[EMAIL PROTECTED]>, "SCOTT19U.ZIP_GUY"
<[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Mark Carroll) wrote in
> <8rb042$23d$[EMAIL PROTECTED]>:
>
>>In article <[EMAIL PROTECTED]>, SCOTT19U.ZIP_GUY
>><[EMAIL PROTECTED]> wrote:
>>(snip)
>>>little to do with the contest. I am not sure two fish is secure but the
>>>government has to pick a cipher the NSA could break or they would not
>>>allow it to be used. I just hope it modivates him to find
>>(snip)
>>
>>Uh? That's why they made DES more resistant to differential
>>cryptanalysis by changing the S-boxes even though leaving it as it was
>>would have given the NSA an advantage over the public in breaking it, as
>>differential attacks weren't public knowledge then?
>>
>>-- Mark
>
> They may have cleaned come some things up. But are your forgetting the
> key size was lowered to be 56 bits. That alone made it easy for them to
> break.
>
>
> David A. Scott
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Comments on the AES winner
Date: Tue, 03 Oct 2000 09:11:57 +0200
"Douglas A. Gwyn" wrote:
>
> Anton Stiglic wrote:
> > In a rump session talk at Crypto 2000, N. Ferguson
> > (I believe it was) came up with an equation, in GF(2^8)
> > I believe, stating that if one can solve this equation
> > one can break Rijndael encryption. ...
> > Someone knows what the equation was?
>
> What's the point? *Any* block cipher can be expressed in
> such an equation. It doesn't imply practical solvability.
The possibility could not a priori excluded, I suppose,
that Rijndael could be expressed in a comparatively
simpler form of equation(s), even if it is hard to tackle.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Comments on the AES winner
Date: Tue, 03 Oct 2000 09:13:22 +0200
JCA wrote:
>
> I understand that the original Rijndael (i.e. with 10
> rounds) seemed to be dangerously close to be broken,
> in the sense that an 8 round Rijndael has already been
> broken. I have been unable to find information in this
> respect so I assume that the are no additional rounds
> in the newly-elected AES.
The number of rounds, in my humble view, is a topic that
should be discussed (also in case another candidate were
selected instead). I personally wish that there could be
provided, if possible, a user choosable variable number of
rounds with a minimum number of rounds that is prescribed.
That can adapt to special user desires (including
psychological matters) and future technological changes.
M. K. Shen
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Subject: Re: It's Rijndael
Date: Tue, 03 Oct 2000 08:32:04 +0200
On Mon, 02 Oct 2000 19:50:12 -0700, David Schwartz <[EMAIL PROTECTED]> wrote:
>
>John Savard wrote:
>
>> given that all the algorithms were of satisfactory security.
>
> Yes, but the lesson of DES is that "satisfactory" security is not good
>enough.
>
What lesson? DES has proved to be extremely resistance to
cryptanalysis. It only fell out of favor because its limited keysize makes it
vulnerable to brute-force attacks.
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Subject: Re: is NIST just nuts?
Date: Tue, 03 Oct 2000 08:44:38 +0200
On Mon, 02 Oct 2000 19:34:36 -0400, Cornelius Sybrandy <[EMAIL PROTECTED]>
wrote:
>> They may have cleaned come some things up. But are your forgetting the
>> key size was lowered to be 56 bits. That alone made it easy for
>> them to break.
>>
Agreed. But back in the 70�s, 128 bits might have seemed overkill. 56
bits would be more adequate for the use in the kind of computers available then.
And they did sttrengthen the original design to prevent linear/differential
cryptanalysis (unknown then to civilian scientists).
>You are assuming, of course, they had the computing power back then to
>break a 56-bit key. I doubt that they did and if so they only used it to
>break messages that were designated as being very important. I doubt the
>CRAY's back then were anything like the combined effort of distributed.net
>and a specialized compter by IBM that took just over 22 hours to crack a
>DES key.
>
I did some calculations (similar to those of Lenstra and Verheul in
http://www.cryptosavvy.com/cryptosizes.pdf) and found out that by the first DES
revision (1982), the NSA could break a DES message in a couple of days. Seems
like them made sure that they alone -if anybody- could brute-force DES. And
they strengthened it against cryptanalysis, as I said before.
But now there are many crypto researchers outside Fort Meade. If NSA
approved an AES (remember, they didn�t even design it) which later on was found
to be insecure, that would do more harm than good to international e-trade. We
are a long way since Vigenere breaking was state-of-the-art cryptanalysis.
I would worry more if the AES had been proposed, or amended, by the MIB.
But if they, along with the rest of the crypto community, give their blessing to
Rijndael, that sounds good.
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Subject: Re: Idea for Twofish and Serpent Teams
Date: Tue, 03 Oct 2000 08:48:56 +0200
On Mon, 02 Oct 2000 18:15:57 GMT, Tom St Denis <[EMAIL PROTECTED]> wrote:
>Do what RSA did and make your own "Symmetric Cipher Standards" and
>ignore the govt.
>
That�s exactly what the GSM gang did, and see the results: an
easy-to-break cipher.
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Crossposted-To: alt.security.scramdisk
Subject: Re: Advanced Encryption Standard - winner is Rijndael
Date: Tue, 03 Oct 2000 08:54:52 +0200
On 3 Oct 2000 05:08:00 GMT, [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
wrote:
>[EMAIL PROTECTED] (jungle) wrote in <[EMAIL PROTECTED]>:
>
>
> Your own quote it is intended that AES ... protecting
>sensitive government information. Sensitive is not even
>considered classifed. It is below confidential info and
>is to low to be considered classifed.
>
I think it�s just a mine-does-it-better syndrome. Either NSA is so
paranoic it doesn�t trust AES, or it needs some excuse to keep a zillion+
mathematicians/cryptographers on its payroll. But anyway, DES was intended to
protect sensitive, non-classified information. And it fared well.
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
