Cryptography-Digest Digest #835, Volume #12 Wed, 4 Oct 00 07:13:00 EDT
Contents:
Re: Comments on the AES winner (Volker Hetzer)
Re: Looking Closely at Rijndael, the new AES (Tim Tyler)
Re: Democrats, Republicans, AES... (Tim Tyler)
Re: Democrats, Republicans, AES... (Tim Tyler)
Re: Requirements of AES (Tim Tyler)
Re: My Theory... (Thomas Pornin)
Re: My Theory... (Thomas Pornin)
Re: Mr. Zimmermann, Mr. Price when can we expect this feature ? (jungle)
Re: Any products using Rijndael? (Thomas Pornin)
Re: is NIST just nuts? (Tim Tyler)
Re: Requirements of AES (Volker Hetzer)
Re: Mr. Zimmermann, Mr. Price when can we expect this feature ? (Tom McCune)
Rijndael cracked by Biham! ([EMAIL PROTECTED])
Re: It's Rijndael (Tim Tyler)
Re: Advanced Encryption Standard - winner is Rijndael (Tim Tyler)
Re: It's Rijndael (Tim Tyler)
Sheeesh... (Rijndael cracked by Biham!) (Paul Rubin)
----------------------------------------------------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Comments on the AES winner
Date: Wed, 04 Oct 2000 11:18:29 +0200
Anton Stiglic wrote:
>
> "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.
>
> It was a *nice looking* equation, that nicely fitted in one
> slide, and looked like something you would
> normaly be able to solve using Mathematica.
> That's the point.
Does it exists somewhere on the web?
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Looking Closely at Rijndael, the new AES
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 09:16:55 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
:> I don't think any small fast cipher can really be secure [...]
: Why can't a fast cipher be secure? [...]
My 2p: Fast cyphers /can/ be secure - provided you measure speed in terms
of throughput - and can exploit parallelism.
If you measure speed in terms of time taken for an input to produce an
output, then "fast cypher" necessarily translates to "small cypher" - or
to "simple cypher".
Scott said "small fast cypher" in the first place. A small secure cypher
would be a sort of cryptographic magic bullet. I don't think it exists -
you need a certain degree of complexity to poroduce enough confusion to
properly resist analysis.
These terms are all relative. If you think all the AES candidates are
"small" and "fast", then different baselines for measurement are in use.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Democrats, Republicans, AES...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 09:26:30 GMT
Albert Yang <[EMAIL PROTECTED]> wrote:
: this does NOT give me warm fuzzies [...]
As a historical query, does anyone know if "warm, fuzzy feelings" were
linked to cryptography before the publication of "Applied Cryptography"?
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Democrats, Republicans, AES...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 09:32:30 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: I have many times suggested allowing variable number of rounds.
One problem that springs to my mind on this front is hardware
implementation. Since I believe more rounds equates to more area,
hardware implementations that could read all Rijndael traffic would
commonly occupy an area corresponding to the maximum possible number of
rounds - probably not a desirable scenario.
: Another way is to go like 3DES.
Also probably not a desirable scenario.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Requirements of AES
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 09:51:32 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote:
:> Twofish has a related key attack on 11 rounds. The best practical
:> attack is on 6 rounds. 16/6 is a good margin, but 16/11 is more like a
:> Rijndael margin, actually worse.
: What attack on Twofish has a 16/11 advantage? [...]
According to 3.2.1.5 of the NIST report they know of no such attack.
They reference:
http://csrc.nist.gov/encryption/aes/round2/comments/20000501-nferguson-1.pdf
"A Twofish Retreat: Related-Key Attacks Against Reduced-Round Twofish"
Niels Ferguson, John Kelsey, Bruce Schneier and Doug Whiting - for the
best known related key attack on Twofish.
There /was/ a 10-round attack suggested in the original Twofish paper.
Apparently it fails to work.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: My Theory...
Date: 4 Oct 2000 10:10:19 GMT
According to Tom St Denis <[EMAIL PROTECTED]>:
> True, but remember that those subtle flaws in Rijndael parallel the
> flaws in using a 56-bit DES key 30 years ago.
The situation is different. 30 years ago, an exhaustive search on a
56-bit DES key was already doable by mankind, with the technology
known by that day. It was sure expensive, but yet within the reach
of a wealthy agency, at least in the next five years. And this was
well known.
The NSA did bet, 25 years ago, on the fact that they could build a
DES-cracker before anyone else. On the other hand, they strengthened
DES with regards to other cryptanalysis, so that only brute-force would
be practical. This allowed the long-awaited complete quantification of
security: it could be expressed in dollars.
Introducing a backdoor, or letting it go, is a dangerous game. A smart
guy can discover it, and use it. The NSA would not do this: too risky.
A good backdoor is a plain one, that everybody sees. The 56-bit key
in DES is the DES backdoor.
Nowadays, cryptography is no more a problem of CIA knights fighting
against evil KGB terrorists. James Bond can retire. Modern spying is
between corporations: Sony against Toshiba, Texaco against Shell, Boeing
against Airbus. Those corporations are richer than the NSA. Therefore no
evident backdoor could be added by the NSA: this would be a losing game.
So they chose a rock solid algorithm. Something that would, at least,
protect US companies against the rest of the world.
And here we are: brute-force on a 128-bit key is not doable by mankind
nowadays, and will probably not be until 2050 or so. This is a margin
really much better than for DES. For DES, the margin was a few dozen
million dollars. For AES, it is an infinite number of dollars.
Obviously, the purpose is not identical; the selection process is
not identical either: the NIST really wanted full disclosure. The
problem is no more producing an algorithm that some well-targeted
organization will be able to break. The problem is having good people
use an algorithm that bad people will not be able to break. A marketing
goal rather than a cryptographic goal. Rijndael, being the most popular
and cost-effective algorithm among the five finalists, was the best
algorithm for this marketing goal.
In the security point of view, all 15 candidates were equivalent.
All future practical breaks on the 15 (including those described as
"completely broken") will be utterly irrelevant. In 2015, we will have
X-ray scanners that will see through walls. In 2020, one will hide a
video camera inside the branches of my glasses. The algorithm will not
be the weak point, so it is pointless to require more security than
that, especially now. In fifty years, maybe, a 128-bit key will become
again the weakest part. Then it will be time to design a new AES. The
purpose of the AES is to get rid of the cryptographic problem from the
security equation.
The relevant research goal now, is to enhance security analysis tools
(especially mathematical ones), so that one could build faster ciphers
with adequate security. We now know how to make secure ciphers that
encrypt 1 bit every two clock cycles on a computer cpu. We need ciphers
faster than that. We do not need to look for ciphers more secure,
because there is no such thing as "more secure than unbreakable".
We also need to convince industrials that current state-of-the-art
algorithms ARE secure. And that homemade secret algorithm, often, are
NOT secure.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: My Theory...
Date: 4 Oct 2000 10:18:27 GMT
According to John Savard <[EMAIL PROTECTED]>:
> One or two of the 15 initial applicants were less than secure, I had
> thought.
They are still unbreakable. But they are not academically secure, and
therefore fail to convince people that they are unbreakable. It is all a
matter of trust.
The point of academic attacks is not exhibitting practical breaks; the
point is that only a trained cryptgrapher can tell whether a given
algorithm is secure or not. The author of an algorithm says: "My cipher
is secure, and trust me, I am an expert at this. And to prove that I
am a real good expert, I challenge other experts to find even the most
impractical, academic flaw in my cipher".
Just like glue. Commercial ads state that the foobar glue can stick an
elephant to the ceiling. Who needs to stick an elephant to the ceiling ?
But if it can do that, people will trust its sticking strength.
--Thomas Pornin
------------------------------
From: jungle <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,alt.security.scramdisk
Subject: Re: Mr. Zimmermann, Mr. Price when can we expect this feature ?
Date: Wed, 04 Oct 2000 06:20:58 -0400
if you really need it,
it is much slower then 2k version, specially key generation,
get it from http://members.aol.com/EJNBell/pgp263ig.zip
it will handle 4k RSA ...
if I will have 1,000 MHz intel processor, it could be a different story ...
the key generation is extremely slow, about 15 min ...
the decryption of 20 kB text file about 5 seconds ...
the encryption of 20 kB text file very fast ...
I will stay with 2k max ...
pgp651 wrote:
>
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Mr. Zimmermann, Mr. Price when can we expect this feature ?
>
> After RSA patent hoopla is over, isn't now the time to implement 4k RSA keys
> into PGP v262 ? The maximum size of 2k is little bit lower than corresponding
> 128 bits key strength from symmetric cipher.
>
> The introduction of 4k RSA will be in line with Twofish introduction.
>
> We need 3k RSA keys to create balance between symmetric & asymmetric ciphers.
> When can we expect this feature ?
>
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Any products using Rijndael?
Date: 4 Oct 2000 10:23:15 GMT
According to Tom St Denis <[EMAIL PROTECTED]>:
> I heard that trimming the DES key from 112 bits to 56 was ok... cause
> nobody can guess a 56 bit key in 10 quadrillion billion years.
Whoever told that, even 25 years ago, was either drunk or incompetent.
The cost of a 56-bit key search has been well estimated and anticipated
since the early seventies.
--Thomas Pornin
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: is NIST just nuts?
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 10:15:50 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: Tim Tyler <[EMAIL PROTECTED]> wrote, in part:
:>I believe there's some argument that the effective strength was only at
:>about the 56-bit level anyway.
: Yes, but so far the strength level is 65 bits, at least as of AC, 2nd
: ed., so a 64-bit key would not have stretched things too far. [...]
"It was not until 1990 that two Israli mathematicians, Biham and Shamir,
discovered differential cryptanalysis, a technique that put to rest the
question of [DES's] key length. [...]" - A.C. p.284.
It goes on to mention a 2^55 known plaintext differential attack on DES.
Where do you get the 65-bit figure from?
: And a trivial fix - putting the IP and IIP where they could do some
: good, after rounds 4 and 12 - would likely allow DES to support longer
: keys and give back strength in return.
Yes - I don't doubt that the algorithm could be relatively easily adjusted
to provide greater strength.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Requirements of AES
Date: Wed, 04 Oct 2000 12:31:10 +0200
Tom St Denis wrote:
> Why wasn't Serpent or Twofish picked?
My 2 cents:
Remember, they wanted an algo for non classified data.
That means, they didn't *have* to choose some ultra safe
and technologically over-ripe candidate.
Perhaps one of the reasons was that Rijndael is new and
nice to analyze so one can learn more about cipher design?
And if it gets broken, hey, you were not supposed to encrypt
secret stuff with it anyway!
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
Crossposted-To: alt.security.pgp
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: Mr. Zimmermann, Mr. Price when can we expect this feature ?
Date: Wed, 04 Oct 2000 10:32:00 GMT
=====BEGIN PGP SIGNED MESSAGE=====
In article <x5xC5.80180$[EMAIL PROTECTED]>, Jacques
Therrien <[EMAIL PROTECTED]> wrote:
>> On a modern computer, it takes no additionally noticeable time to
>> encrypt or decrypt to a 4096 bit RSA key, than it does to a 1024 bit
>> RSA key. So although it isn't really necessary to use the maximum
>> potential of PGP by using a key larger than 3000 bits, there isn't
>> really harm in doing so (except for backwards compatibility). I'm
>> surprised that this
>> performance myth continues.
>
>Tom,
>
>There are however incompatibilities with 4096-bit RSA keys. For
>instance in PGP 6.x., those RSA keys cannot be used for encryption.
>
>I am not sure what would happen if one tried to verify a message signed
>with such an RSA key -- I would assume that would not work either.
>
>Someone with a 4096-bit RSA key, send a signed message to this
>newsgroup. We will find out.
>
>Those keys can be imported on the keyring, however if one cannot do
>anything with them, that is pretty useless.
That is why I said " there isn't really harm in doing so
(except for backwards compatibility)." That is what backwards
compatibility is all about.
But a 4096 bit RSA key, is still far more backwards compatible than a
new format (v4) RSA key, because it can be used by many 2.6.x users, all
5.5.x users (that have RSA support), and all CKT users.
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.5.8
Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
iQEVAwUBOdsHwTYk/PXew/BzAQET5AgAi4LM5KNSSWQxoh556EAcysAQePxhqDhe
CEkEEZfQBdE5La5xn+WVppcBMLi2zKSF9pt54tZtrpcjPnDakXpj1wcuKuWkJBZq
DwNOWpjxnLWf8oT9kI6psvp62rvJOnC+9TbqcZ+QSGCwTsSKflkaRcnug8MJvRFN
E7Jz8c/rN/WYDeAu4d0TWN9wzla5W0Y/GBUWs99dnoVaPnEuYr7GibjVikaz35OC
5odTeG5d3dLq+TIqZ1WuHWFJv5GXHhhyU36PijY5JZ5wauJKY5mrrcPb0MIFKL7I
PGCgAUvHU559f0R32Yg0mkYsZSILPn70WIRsWHE2lLlzqmoXxUSl7g==
=wH2O
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Rijndael cracked by Biham!
Date: Wed, 04 Oct 2000 10:44:22 GMT
The article on :
http://sectedesax.ctw.cc
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 10:29:57 GMT
John Savard <[EMAIL PROTECTED]> gets quoted as saying:
: It *helps* if the computers of the world all use the U.S. designed
: Microsoft Windows operating system [...]
This is "helps" in the sense of "hinders", I presume ;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Destroy Microsoft.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Advanced Encryption Standard - winner is Rijndael
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 10:40:17 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: jungle wrote:
: I see no evidence that the U.S. government ever reached the conclusion
: that Rijndael is not suitable for protecting classified information.
That's not what it's *for*, according to
http://csrc.nist.gov/encryption/aes/round2/r2report.pdf
Classified information is likely to be protected by classified algorithms.
Whether or not Rijndael is "suitable" it seems unlikely to get much use in
that context.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: It's Rijndael
Reply-To: [EMAIL PROTECTED]
Date: Wed, 4 Oct 2000 10:48:38 GMT
David Schwartz <[EMAIL PROTECTED]> wrote:
: Scott Fluhrer wrote:
:> 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...
: However that assumption was not stated, in fact David Hopwood
: specifically stated the opposite of that assumption. Finding a key that
: produces such an encryption is 2^128 easier than actually finding the
: correct key. So doing that would not be equivalent to breaking Rijndael.
: Read David Hopwood's original post and John Savard's response. David
: Hopwood is correct and John Savard is incorrect (if you take him
: literally).
I think that actually locating the correct key from a 128 bit space would
be a good indication that you had found a break - i.e. John's post looked
OK to me ;-)
What are the chances of a *128*-bit key existing that performs this map?
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Sheeesh... (Rijndael cracked by Biham!)
Date: 04 Oct 2000 04:09:37 -0700
Silly prank. The text there is an article in French about a UFO
cult. There's links to some .exe files with further stuff but
there's no way I'm going to download...
------------------------------
** 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
******************************
