Cryptography-Digest Digest #652, Volume #10 Tue, 30 Nov 99 13:13:01 EST
Contents:
Re: Elliptic Curve Public-Key Cryptography (DJohn37050)
Re: The $10,000.00 contesta (Tom St Denis)
Re: more about the random number generator (Brian Chase)
Re: cryptography control? (wtshaw)
Re: AES cyphers leak information like sieves (Paul Crowley)
Re: NSA should do a cryptoanalysis of AES (Kenneth Almquist)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Elliptic Curve Public-Key Cryptography
Date: 30 Nov 1999 16:42:06 GMT
I have a few quick comments, inserted in the text and prefixed with *. A more
comprehensive response is being worked on.
>Subject: Elliptic Curve Public-Key Cryptography
>From: [EMAIL PROTECTED] (Bruce Schneier)
>Date: Mon, 29 November 1999 11:30 AM EST
>Message-id: <[EMAIL PROTECTED]>
>
>(This is reprinted from the November Crypto-Gram newsletter.)
>
>
>In September of this year, nearly 200 people using 740 computers
>managed to crack a message encrypted with 97-bit elliptic curve
>cryptography. The process took 16,000 MIPS-years of computing, about
>twice as much as used by the team that recently cracked a 512-bit RSA
>encryption key. Certicom, the company who sponsored this challenge,
>has offered this result as evidence that elliptic curve cryptography
>is stronger than RSA.
>
* True.
>Let's take a look at this claim a little more closely.
>
>All public-key algorithms, whether for key exchange, encryption, or
>digital signatures, are based on one of two problems: the factoring
>problem or the discrete logarithm problem. (There are other
>algorithms in academic circles, but they're too unwieldy to use in the
>real world.)
* Better wording might be all public key algorithms "in wide use" or some such.
>The security of RSA comes from the difficulty of
>factoring large numbers. Strong RSA-based systems use 1024-bit
>numbers, or even larger.
>
>The security of most other public-key algorithms -- ElGamal, DSA, etc.
>-- is based on the discrete logarithm problem. The two problems are
>very similar, and all of the modern factoring algorithms can be used
>to calculate discrete logarithms in the multiplicative group of a
>finite field. To a rough approximation, factoring a number of a
>certain size and calculating the discrete logarithm of numbers the
>same size takes the same amount of work. This means that for a given
>key size, RSA, ElGamal, DSA, etc. are approximately equally secure.
>(This isn't strictly true, but it's a good enough approximation for
>this essay.)
>
* True, this is the estimate that NIST and ANSI X9 uses, for example.
>All of these algorithms require the use of something called an
>"algebraic group." When public-key cryptography was invented, the
>algorithms were all implemented in the simplest algebraic group: the
>numbers modulo n. For example, RSA encryption is m^e mod n, and a
>Diffie-Hellman public key is g^y mod n. As it turns out, any
>algebraic group will do. Elliptic curves are simply another algebraic
>group.
* This is true as far as it goes. What it does not mention is that using the
multiplicative group of a finite field means there is the "extra" additive
group. This is not really used or desired by the secure user but (in effect)
can be exploited by a bad guy. Elliptic curves only have one group operation,
there is no "extra" group operation that the good guys do not want.
>
>In elliptic curve cryptography, public keys and private keys are
>defined as points along a mathematical object called an elliptic
>curve. (Don't worry; it doesn't really matter what that means.)
>Addition is an operation that combines two points and produces a third
>point. The algorithms look the same, but the detailed math is very
>different.
* True, but it is all "just" algebra. IEEE P1363 has descriptions of the
algebra for the interested.
>
>But if any algebraic group will do, why is anyone bothering with
>elliptic curves? It turns out that for discrete-logarithm elliptic
>curve algorithms, perhaps we can get by with smaller keys. (This is
>not true for RSA, which is why you never see elliptic curve RSA
>variants).
* Actually, there are EC RSA variants. There does not appear to be any
performance advantage, so they are not discussed much.
>
>All of the fastest algorithms for calculating discrete logs -- the
>number field sieve and the quadratic sieve -- make use of something
>called index calculus and a property of the numbers mod n called
>smoothness.
* Smoothness means that a number factors into small numbers, all the factors
are below a certain size, the smoothness bound. The notion of below a certain
size (smallness) is related to the existence of addition in the field. One can
try to find small numbers (2, 3, 5, etc.) that might factor a big number.
>In the elliptic curve group, there is no definition of
>smoothness, and hence in order to break elliptic curve algorithms you
>have to use older methods: Pollard's rho, for example. So we only
>have to use keys long enough to be secure against these older, slower,
>methods. Therefor, our keys can be shorter.
>
* As there is only one group operation, the notion of "small" do not really
exist in an EC group like it does in a finite field. So finding "small" points
has a fundamention problem from the get-go.
* The relevant distinction is not that Pollard rho is older, it is that Pollard
rho is more general and works on any group. The association seems to be
Pollard rho is older and therefore slower. Pollard rho is a more fundamental
method and uses less assumptions about the group, this is why it is slower.
>And they can be significantly shorter. In the wake of the recent
>break, Certicom recommends 163-bit keys. Compare this to the
>recommended key lengths for conventional discrete-logarithm
>algorithms, which are at least 1024 bits.
>
* It is not only Certicom. NIST and ANSI X9 also recommend these key sizes for
minimums.
>Whether this recommendation makes sense depends on whether the faster
>algorithms can ever be made to work with elliptic curves. The
>question to ask is: "Is this lack of smoothness a fundamental
>property of elliptic curves, or is it a hole in our knowledge about
>elliptic curves?" Or, more generally: "Are elliptic curves
>inherently harder to calculate discrete logs in, or will we eventually
>figure out a way to do it as efficiently as we can in the numbers mod
>n?"
>
>If you believe the former, elliptic curves will always be more secure
>-- for the same key lengths -- than the numbers mod n. If you believe
>the latter, it's only a matter of time before they are broken.
>
* Some very smart people have looked at EC and have come up short. Silverman
came up with the Xedni calculus which might have broken all public key, but
turns out to be much too impractical. Anyone wishing details could consider
attending Waterloo's ECC conference, where all this was/is discussed.
>Certicom very much wants you to believe the former. They say things
>like: "Elliptic curves as algebraic/geometric entities have been
>studied extensively for the past 150 years, and from these studies has
>emerged a rich and deep theory." They conclude that because of this,
>we can gain good confidence that new algorithmic advances won't be too
>devastating.
>
>To me, this is a lot of wishful thinking. It would be nice if we had
>150 years of work on the cryptographic properties of elliptic curves.
>But we don't; instead, we have 150 years of work on the properties of
>elliptic curves that mathematicians care about, almost all of it only
>incidentally touching on what cryptographers care about. Elliptic
>curve cryptography was invented only in 1985, and has only been really
>studied seriously for a few years.
* This statement can be made for all public key and in fact for all theory of
computation. All of this is recent stuff, computers did not really exist until
WWII.
>
>Even today, most of the work on elliptic curves in the typical
>university math department is pretty irrelevant to us cryptographers.
>Sure, some of their results might occasionally help us understand the
>strength of elliptic curve algorithms; but that's almost never been
>the goal of the mathematicians' research studies. This is changing
>now, but slowly.
* Whatever point is being made is true for all of public key. Many experts
looking at factoring could care less about RSA and try to factor numbers that
are not appropriate for use as an RSA modulus.
>
>Furthermore, work on efficient algorithms for elliptic curves is very
>new. The whole notion of efficient algorithms didn't even appear until
>about the 1960s or 1970s, and algorithmic number theory has only
>become popular in the past two decades. It just wasn't relevant
>before computers.
* Yes, but substitute any hard problem on which any public key system is based.
>
>The real answer to the question is "we don't know." We don't know if
>there are efficient ways to calculate discrete logarithms in elliptic
>curve groups. We don't know if there is a definition of smoothness
>that will allow us to apply the number field sieve to elliptic curves.
>We don't know if, in the long run, you can use shorter keys with
>elliptic curve algorithms.
* We do not have lower bounds on any hard problem, including factoring. What
we do know is what the best methods available today are.
>
>In the short run, Certicom's recommendations are reasonable. Today,
>we can't calculate discrete logs in elliptic curves as efficiently as
>we can in the numbers mod n. Systems can use shorter keys with
>elliptic curves. But in the long run, we don't know.
>
>There are other differences to consider, too. Checking elliptic curve
>signatures is still a big pain compared to checking RSA signatures.
* This is an overbroad generalization that is simply false. And it depends
greatly on what might be causing the pain.
If the pain is due to performance, it is true that use of low exponent RSA can
lead to faster sig. ver.; but Dan Boneh has given some evidence that low
exponent RSA may not be equivalent to factoring.
* If the pain is due to signature size, then EC sigs are shorter, if the pain
is due to key size, then EC keys are shorter, if the pain is due to certificate
size, then EC certificate are shorter. If the pain is due to key gen time or
complexity, then EC key is MUCH faster than RSA and also simpler, given a
suitable set of domain parameters.
* If the pain is due to sig. gen. time, then EC sig. gen. is faster. If the
pain is due to symmetric key establishment time, then there are EC methods that
are faster and achieve more security properties. If the pain is due to the
need to validate your public key (to detect bogus key attacks), then ECC
specifies how to do this while it is a research topic for RSA.
* Mentioning sig ver. while not mentioning all the other possible concerns is
strange.
>And all users of an elliptic curve system have to share the same
>curve. (If you don't do this, you lose most of the size benefits of
>the elliptic curve keys.) This has security implications: it is
>easier to break a key of a random user on a system than it is to break
>a specific user's key. I'd like to see more analysis of this aspect
>of elliptic curve systems.
>
>My recommendation is that if you're working in a constrained
>environment where longer keys just won't fit -- smart cards, some
>cellphones or pagers, etc. -- consider elliptic curves. If the choice
>is elliptic curves or no public-key algorithm at all, use elliptic
>curves. If you don't have performance constraints, use RSA. If you
>are concerned about security over the decades (almost no systems are),
>use RSA.
* I agree with all the suggested uses of ECC.
* Regarding high security, my statement is if you are concerned about super
high security ("over decades"), use BOTH RSA and ECC sigs. My paper on future
resiliency at PKS '99 said this.
>
>Realize, though, that someday -- next year, in ten years, in a century
>-- someone may figure out how to define smoothness, or something even
>more useful, in elliptic curves. If that happens, you will have to
>use the same key lengths as you would with conventional discrete
>logarithm algorithms, and there will be no reason to ever use elliptic
>curves.
* Yes, who knows the future? This is true about all public key systems.
However, as Lenstra points out at cryptosavvy, factoring has seen a steady
advance in capability, while the ECDLP is basically still stuck.
>
>Postscript: This same analysis applies to factoring (and the basic
>discrete log problem). RSA Security, Inc. likes to talk about the
>long mathematical history of the factoring problem, and how that gives
>us confidence about the security of RSA. Yes, it has been studied for
>centuries, but only recently has that study been even remotely related
>to cryptography. Moreover, working on factoring hasn't been a
>respectable area of study until very recently; before that, it was
>considered an eccentric hobby. And efficient algorithms for factoring
>have only been studied for the past couple of decades. We really have
>no idea how hard factoring truly is.
>
>The truth is that companies have a tendency to advertise their
>products. Before making a decision about cryptographic algorithms,
>customers should try to get a variety of independent opinions (from
>parties not financially involved in the outcome of the decision) about
>what they are buying.
>
>News on the recent elliptic curve cracking effort:
>http://www.computerworld.com/home/news.nsf/all/9909282ellip
>http://www.certicom.com/press/99/sept2899.htm
>
>An excellent mathematical introduction to elliptic curves:
>http://www.certicom.com/ecc/enter/index.htm
>
>An excellent discussion on comparative key lengths, including RSA and
>elliptic curves: http://www.cryptosavvy.com
* It is interesting that you give this reference and call it "excellent" as
some of its conclusions differ from yours greatly. As a brief summary, it
says ECC is stronger than Certicom, NIST and ANSI X9 currently say and that RSA
is weaker than RSA Labs and ANSI X9 currently say. It says to not use 768-bit
keys and that 1024-bit keys are good to protect data until 2002, given the
assumptions in its model.
>
>**********************************************************************
>Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
>101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
Don Johnson
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: The $10,000.00 contesta
Date: Tue, 30 Nov 1999 17:43:41 GMT
In article <820jut$rl0$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> As people should well know I ran a contest for over a year. It
> was a black and white contest where the solution is easy to
> verify. Mr BS run a contest that was not Black and White
> but offered to give ten thousand dollats to whoever give him
> the best crypto analysis of Two Fish during Round 1 of AES.
> What ever happened to this money. Or did he did he decide
> no one was worthy.Note the contest was such that the best
> would win. This means of the analysis sucked if only dumb
> comments where entered that there should be a winner.
You have some issues to work out, i would suggest a good doctor for you.
Seriously, what is your problem? If you don't like the world why make
everyone else know about it? You hate the govt, you hate AES, you
probably even hate me.
This is a group geared towards SCIENTIFIC discussion of CRYPTOGRAPHY.
Not your insane rants that never go anywhere but into flame fests.
Seriously just get a life.
BTW Why would anyone keep their attacks private on Twofish? If I for
example broke Twofish and BS said 'nah I don't like that' I would make
a fuss and make him look foolish. Perhaps though, just maybe, Twofish
was not broken... I dunno..The current best attack is against five
rounds [I believe] and requires insane amounts of work. Maybe that's a
good indication that it's a worthy cipher.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Brian Chase)
Subject: Re: more about the random number generator
Date: Tue, 30 Nov 1999 17:52:30 GMT
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
>Tom St Denis wrote:
>> Optimum compression would reduce the size
>> of this 417792 bit file by 0 percent.
>This comes directly from the entropy result.
Naive question here. Let's say you had access to some "optimum
compressor" which would take arbitrary data sets distill them into their
most compact form. By definition, the resulting data must have no
predictable redundancies, yes? Could you use optimally compressed data
sets as sources for random numbers?
It also seems like you could evaluate the effectiveness of current
compression schemes using this same sort of entropy calculation. Maybe
it's already common practice, but I can't say that I'm up to date on
either random number generation, cryptography. or data compression. It
just seemed like you could run the process sort of backwards.
I think it would be an interesting excercise to figure out how well the
best lossless compression utilities are at producing pseudo-random
numbers. :-)
-brian.
--
--- Brian Chase | [EMAIL PROTECTED] | http://world.std.com/~bdc/ -----
It was powered by one AA battery from Radio Shack, in other words, half
a normal AA battery. -- K.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: cryptography control?
Date: Tue, 30 Nov 1999 12:24:39 -0600
In article <81uo29$16a$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Keith A Monahan) wrote:
> Douglas A. Gwyn ([EMAIL PROTECTED]) wrote:
> : wtshaw wrote:
> : >> The only true raw ingredients required in crypto are imagination and
> : > insight; both are most difficult to outlaw.
>
> : You don't outlaw them; instead, you control the educational system
> : and make sure that imagination and insight are suppressed.
>
> Hence Outcomes Based Education
>
I'm back to my statement above. Learning requires internalizing concepts,
i.e., extending your imagination to include ideas with what you aready
know in a way that you understand the relationship, insight. When bum
thoughts are on the table, it's so much harder to that.
When ideas are relevant and rich in truth, it is much easier to comprehend
and extend your understanding of the world to include them. This is the
basis of a liberal education, in it's true sense, to open and expand minds
to incredible awareness of nature. A good crypto education fills lots of
voids, bringing lots of basic relationsips into there true relationship;
the same can be said of other areas.
When ever propaganda is pushed over truth, lots of folks are not fooled,
but, lots are; this is a crime if done, surely if by government.
--
Love is blind, or at least figure that it has astigmatism.
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: AES cyphers leak information like sieves
Date: 30 Nov 1999 08:17:20 -0000
"Trevor Jackson, III" <[EMAIL PROTECTED]> writes:
> Hmmm. Are the participants in sci.crypt the kind of people that one
> sells to, or the kind that one reasons with?
When presenting a new cipher, the former, with good reason.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: NSA should do a cryptoanalysis of AES
Date: 30 Nov 1999 17:56:29 GMT
albert <[EMAIL PROTECTED]> wrote:
> The problem I'm seeing is that NIST is going to have to parse the information
> that NSA gives to them, internalize it, have it influence their decision, and
> then not let us know about it. That seems like a difficult thing to do in my
> book.
My guess is that the information from the NSA which influences the
AES selection will be made public, because as you point out, keeping
the information secret would be difficult. On the other hand, some
of the information that we would like to know might be classified.
For example, if the NSA breaks one of the finalists, the fact that
the encryption algorithm had been broken would rule it out of
consideration. The specific attack used to break the algorithm
would not matter to NIST. So I would expect us to learn that the
algorithm had been broken, but not necessarily how.
Kenneth Almquist
------------------------------
** 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
******************************
