from Interesting People: Record encryption puzzle cracked -- finally

[Perry E. Metzger]

Anyone know anything about this?

-- 
Perry Metzger   [EMAIL PROTECTED]
--
"Ask not what your country can force other people to do for you..."
--- Start of forwarded message ---
Date: Mon, 17 Apr 2000 07:03:27 -0400
From: David Farber <[EMAIL PROTECTED]>
Subject: IP: Record encryption puzzle cracked -- finally

>From: [EMAIL PROTECTED]
>Date: Mon, 17 Apr 2000 06:58:52 EDT
>Subject: Check out ZDNet: News: Record encryption puzzle cracked -- finally
>To: [EMAIL PROTECTED]
>
>  http://www.zdnet.com/zdnn/stories/news/0,4586,2542359,00.html">Click
>  here: ZDNet: News: Record encryption puzzle cracked -- finally


Record encryption puzzle cracked -- finally

The broken encryption method is widely expected to secure 
next-generation wireless devices. But is the break such bad news?


By Robert Lemos, ZDNet News

UPDATED April 14, 2000 7:06 AM PT

An encryption method widely expected to secure next-generation 
wireless phones and other devices succumbed to a brute-force 
collaborative effort to break it, a French research agency announced 
Thursday.

An international team of researchers -- led by crypto researcher 
Robert Harley of the French National Institute for Research in 
Computer Science and Control, or INRIA -- and other computer 
enthusiasts found the 108-bit key to a scrambled message after four 
months of number crunching by 9,500 computers worldwide.




--- End of forwarded message ---

Re: from Interesting People: Record encryption puzzle cracked -- finally

[Steven M. Bellovin]

In message <[EMAIL PROTECTED]>, "Perry E. Metzger" writes:
> 
> Anyone know anything about this?
> 
> -- 

See http://www.inria.fr/Presse/pre67-eng.html or 
http://www.inria.fr/Presse/pre67-fra.html -- it was an attack on an 
instance of elliptic curve cryptography.

--Steve Bellovin

Re: from Interesting People: Record encryption puzzle cracked -- finally

[Sandy Harris]

"Perry E. Metzger" wrote:
> 
> Anyone know anything about this?

It was a Certicom elliptic curve challenge. For details:
http://www.certicom.com/
 
> --
> Perry Metzger   [EMAIL PROTECTED]
> --
> "Ask not what your country can force other people to do for you..."
> --- Start of forwarded message ---
> Date: Mon, 17 Apr 2000 07:03:27 -0400
> From: David Farber <[EMAIL PROTECTED]>
> Subject: IP: Record encryption puzzle cracked -- finally
> 
> >From: [EMAIL PROTECTED]
> >Date: Mon, 17 Apr 2000 06:58:52 EDT
> >Subject: Check out ZDNet: News: Record encryption puzzle cracked -- finally
> >To: [EMAIL PROTECTED]
> >
> >  http://www.zdnet.com/zdnn/stories/news/0,4586,2542359,00.html">Click
> >  here: ZDNet: News: Record encryption puzzle cracked -- finally
> 
> Record encryption puzzle cracked -- finally
> 
> The broken encryption method is widely expected to secure
> next-generation wireless devices. But is the break such bad news?
> 
> By Robert Lemos, ZDNet News
> 
> UPDATED April 14, 2000 7:06 AM PT
> 
> An encryption method widely expected to secure next-generation
> wireless phones and other devices succumbed to a brute-force
> collaborative effort to break it, a French research agency announced
> Thursday.
> 
> An international team of researchers -- led by crypto researcher
> Robert Harley of the French National Institute for Research in
> Computer Science and Control, or INRIA -- and other computer
> enthusiasts found the 108-bit key to a scrambled message after four
> months of number crunching by 9,500 computers worldwide.
> 
> 
> 
> --- End of forwarded message ---

ECC2K-108 Cracked (Certicom Challenge)

[Vin McLellan]

At 03:28 PM 4/17/00 -0400, Perry E. Metzger wrote:
>
>Anyone know anything about this?

Hi Perry,

This brief compilation might help.  This has been an impressive
achievement.

The comments of Harley and Morain in the InRIA press release, below,
are striking, given Certicom's historic committment to particular (as
opposed to random) Elliptic Curves.  Other vendors (e.g., my friends at RSA)
sell ECC with random Elliptic Curves only, and have long argued that ECC
with particular curves is an unnecessarily risk.  Individual critics like
Len Adleman have been even more pointed in their remarks.

Surete,
_Vin

-

From the Elliptic Curve Discrete Logrithm (ECDL) Project webpage:



The biggest public-key crypto crack ever has just finished! Certicom
have confirmed that the solution is correct.

There is press coverage by Slashdot, National Post, ZDNet, Impress
(Japanese), Developer.com, Yahoo, Crypto-News (French), Punto Informatico
 (Italian).  [Links off the ECDL Project Website]  More soon!



A useful fact-sheet.



 A technical FAQ. 
>

Index

1. Why is this interesting? Is it all about cracking a code?
2. What is a discrete logarithm?
3. Remind me what a finite group is.
4. What is an elliptic curve and what is the group of points on it?
5. What is a finite field?
6. What is the ECC2K-108 problem?
7. What algorithm can we use to solve ECDL problems like ECC2K-108?
8. What are the iterations in "iterations per second"?
9. What are distinguished points?
10. What are the initial and current expectations?
11. How hard is the ECC2K-108 problem anyway?
12. How can I participate?



>From the 4K Associates Press Release 

PARIS -- 13th April 2000 -- Irish mathematician Robert Harley and three
colleagues at INRIA, the French National Institute for Research in Computer
Science and Control, announced the solution to the most difficult public key
cryptographic challenge ever solved after a huge calculation on close to
1 computers throughout the Internet. The challenge, called ECC2K-108,
was set by Canadian cryptographic company Certicom in 1997 to encourage
researchers to test the security of cryptography based on elliptic curves. 

   This extraordinary achievement demonstrates the high level of security
that ECC (elliptic-curve cryptography) can offer with much shorter keys than
RSA. It also highlights the relative weakness of some curves with special
properties and confirms that for optimal security one should pick random
curves with no special characteristics.




>From the InRIA press release at:
http://www.inria.fr/Presse/pre67-eng.html



Arjen Lenstra, vice president at Citibank's Corporate Technology
Office in
 New York and a participant in the project, noted "The amount of computation
 we did is more than what is needed to crack a secret-key system like DES and
 enough to crack a public-key system like RSA of at least 600 bits". 

Harley remarked "Even so, it was only about one tenth of what should 
normally be required for a 109-bit curve. That's because Certicom chose a 
particular curve with  some useful properties but we used those same 
properties to speed up our algorithm". 

He went on to say "This underlines the danger in adopting particular 
curves and the need to pick random ones with no special characteristics. I'm 
concerned about Koblitz curves and complex-multiplication curves, which 
some  people advocate using in order to avoid the point-counting problem".

François Morain, Professor of Computer Science at École Polytechnique, 
explained:

"To use a curve for ECC one first has to calculate the number of
points on it,
 which is quite a difficult task. To improve security one should use arbitrary 
curves picked at random and change them frequently, but currently most 
cryptosystems use fixed curves chosen to have particular properties which 
make it easy to compute the cardinality. These very properties could one day 
endanger them, as happened with super-singular curves. There have been 
dramatic improvements in point-counting algorithms and good 
implementations are now becoming available. Recent progress should soon 
undermine any remaining argument in favour of special curves". 




>From the Cericom Press Release at:
http://www.certicom.com/news/00/apr1700.html

Hayward, Calif., April 17, 2000 - Dr. Scott Vanstone, Chief
Cryptographer 
for Certicom Corp., is pleased to announce that a team of researchers led by 
Robert Harley, Damien Doligez, Danie

NTRU Public Key Cryptosystem

[Joseph Silverman]

[This is very salesy, but there is enough meat that I'm forwarding it
anyway. --Perry]


>From: "Salz, Rich" <[EMAIL PROTECTED]>
>To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
>Subject: www.ntru.com
>Date: Tue, 11 Apr 2000 13:53:06 -0400
>Sender: [EMAIL PROTECTED]
>
>I forget -- has NTRU been discussed here? In light of the recent Fortune
>article, someone mentioned http://www.ntru.com to me. A new fast public
>key crypto system. Just got $11M in funding. :)

Hi, Rich,

There has been discussion of NTRU on sci.crypt, but I'm not sure if
we've been mentioned on this mailing list. Let me first introduce myself.
My name is Joe Silverman, VP for R&D at NTRU Cryptosystems.  With Jeff
Hoffstein and Jill Pipher -- all of us members of the Mathematics faculty
at Brown University -- I'm also one of the inventors of NTRU.

NTRU is indeed a fast public key cryptosystem, but it is not all
that new. It was first announced at the Crypto '96 rump session, where Jeff
Hoffstein distributed numerous copies of our paper giving the complete
details of the algorithm. At Crypto '96, and thereafter, we have received
critical feedback from many cryptographers, including many of the top
people in the field, which we used to establish NTRU's parameters and
define appropriate security levels for our commercial cryptosystem.

I want to stress that a full detailed description of the NTRU
algorithm has been available for analysis by the cryptographic community
since 1996; and that it has been the subject of much study. This is in
marked contrast to some companies that have tried to sell "secret"
cryptographic algorithms. It is generally accepted that no cryptographic
algorithm can be considered secure until it has been subject to public
scrutiny by the cryptographic community.

Our technology is new in the commercial OEM world, but we have been
actively developing it, exploring its architectural implications, and
debating its importance in academic and professional forums for a much
longer period. Obviously, there are alternative PKCs which are better known
and which have some advantage in the sheer number of years they have been
studied. On the other hand, NTRU offers some extraordinary performance
characteristics which many hope will open up wholly new markets for
crypto-enhanced products and services.

After four years of intense and welcome scrutiny of NTRU by many
querilous and skeptical cryptographers, we (and others) have also grown
increasingly confident in our algorithm.

NTRU picked up an early supporter in Sony Corporation, which
invested in our initial development venture two years ago. Last week --
after an extended evaluation of our technology -- Sony chose to
significantly expand its equity investment in NTRU in our second round of
financing.

(In addition to its prominent role in consumer electronics, Sony is
also a pioneer in home networking and owns one of the world's largest
libraries of copyrighted multimedia. I'm doubtless a little biased, but I
believe Sony has a very sophisticated grasp of the potential demand for
crypto with NTRU's unique mix of performance characteristics, configuration
options, and power requirements.)

The recent Fortune article cited above describes an apparently
failed commercial crypto venture, TriStrata, from the point of view of its
venture capitalists. According to the article, TriStrata's VCs invested
millions without even an independent (let along public) peer review of
TriStrata's proprietary and unpublished cryptography. I suspect this is a
fairly rare occurance;-)   NTRU's recent experience with our leading VCs --
Sony and Greylock -- was quite different, I assure you.

We have a lot of technical data on our web site, including my FAQ
on NTRU's performance characteristics
;
tutorials describing the NTRU algorithm at some depth; details of the NTRU
Challenge problems; and information about the Tumbler SDK developed by the
Tao Group, Ltd., in the UK. (We are now developing a VHDL implementation of
NTRU, adapted for efficiency in silicon.)

I'm not sure how much information the List would like on the
security of NTRU, and I don't want to impose, so I will just make a few
additional comments.

Anyone who studies our technology quickly realizes that NTRU is
very fast, very easy to implement, and has a very small footprint. To bring
home this point, some of our advertising declares that NTRU is "100 times
faster than other leading systems." Let me forestall some likely criticism
and acknowledge now that a headline like this is obviously an
oversimplification, since different security levels and different protocols
will have different operating characteristics. (I append below two notes
from my recent private exchange with David Wagner concerning NTRU's claims
and their potential implications. David has given me permission to post his

Re: NTRU Public Key Cryptosystem

[dmolnar]

On Mon, 17 Apr 2000, Joseph Silverman wrote:

Hi,

> The hard problem underlying the NTRU cryptosystem is called the
> "Shortest Vector Problem" (or SVP), which is the problem of finding the
> shortest nonzero vector in a lattice.

Is it known how tightly related NTRU is to the shortest vector problem? Is
there a reduction known yet from SVP to NTRU, or is it still in a
position analagous to RSA and factoring?

Not that a reduction would necessarily be a good thing, as Ajtai and Dwork
found out the hard way... :-)

Seriously, is anything known about how "good an approximation" would be
needed to break NTRU? Apologies if this is already answered in the
Coppersmith paper or someplace else; just point me there. 

Thanks, 
-David Molnar