Subject: Re: OpenSSH key size
To: Alistair Crooks <agc@pkgsrc.org>
From: Steven M. Bellovin <smb@cs.columbia.edu>
List: tech-security
Date: 09/14/2005 17:57:01
In message <20050914213627.GM8666@nef.pbox.org>, Alistair Crooks writes:
>
>--fXStkuK2IQBfcDe+
>Content-Type: text/plain; charset=us-ascii
>Content-Disposition: inline
>
>On Wed, Sep 14, 2005 at 02:07:28PM +0000, Charles M. Hannum wrote:
>> There is a talk being presented at MIT today that shows clearly that 1Kb 
>> public keys can be factored fairly easily on cheap custom hardware.  It is 
>> long past time for SSH keys to be at least 2Kb by default.
>
>You are quite right.
>
>Have I missed anything out of the attached diff?
>
>And can you give us a summary of the talk, please? It sounds interesting.
>

I obtained the following abstract:

   Open to the Public
                                                                                   
   DATE:    TODAY * TODAY * TODAY * WEDNESDAY, Sept. 14 2005
   TIME:    4:00 p.m. - 5:30 p.m.
   PLACE:   32-G575, Stata Center, 32 Vassar Street
   TITLE:   Special-Purpose Hardware for Integer Factoring
   SPEAKER: Eran Tromer, Weizmann Institute
                                                                                   
   Factoring of large integers is of considerable interest in
   cryptography and algorithmic number theory. In the quest for
   factorization of larger integers, the present bottleneck lies in the
   sieving and matrix steps of the Number Field Sieve algorithm. In a
   series of works, several special-purpose hardware architectures for
   these steps were proposed and evaluated.
                                                                                   
   The use of custom hardware, as opposed to the traditional RAM model,
   offers major benefits (beyond plain reduction of overheads): the
   possibility of vast fine-grained parallelism, and the chance to
   identify and exploit technological tradeoffs at the algorithmic level.
                                                                                   
   Taken together, these works have reduced the cost of factoring by many
   orders of magnitude, making it feasible, for example, to factor
   1024-bit integers within one year at the cost of about US$1M (as
   opposed to the trillions of US$ forecasted previously). This talk will
   survey these results, emphasizing the underlying general ideas.
                                                                                   
   Joint works with Adi Shamir, Arjen Lenstra, Willi Geiselmann, Rainer
   Steinwandt, Hubert K?pfer, Jim Tomlinson, Wil Kortsmit, Bruce Dodson,
   James Hughes and Paul Leyland.
   
   
Google found Tromer's web page; there are several talks and papers there
on the topic.  My conclusion is that there's no rush.  Yes, the change
is good, but it's still very expensive for each solution.