COMMAND

	RSA and Diffie-Hellman keys are broken up to 1024bits in seconds

SYSTEMS AFFECTED

	 HTTPS

	 SSH

	 IPSec

	 S/MIME

	 PGP

	 Credit cards

	 ...

PROBLEM

	Lucky Green [shamrock@cypherpunks.to] says :
	

	As those of you who have discussed RSA keys size  requirements  with  me
	over the years will attest to, I always  held  that  1024-bit  RSA  keys
	could not be factored by anyone, including the NSA, unless the  opponent
	had  devised  novel  improvements  to  the  theory  of  factoring  large
	composites unknown in the open  literature.  I  considered  this  to  be
	possible, but  highly  unlikely.  In  short,  I  believed  that  users\'
	desires for keys larger than 1024-bits were mostly  driven  by  a  vague
	feeling that \"larger must be better\" in some cases, and  by  downright
	paranoia in other cases. I was mistaken.
	

	Based upon requests voiced by a number  of  attendees  to  this  year\'s
	Financial Cryptography conference  <http:/www.fc02.ai>,  I  assembled
	and moderated  a  panel  titled  \"RSA  Factoring:  Do  We  Need  Larger
	Keys?\". The panel explored  the  implications  of  Bernstein\'s  widely
	discussed  \"Circuits   for   Integer   Factorization:   a   Proposal\".
	http://cr.yp.to/papers.html#nfscircuit
	

	Although the full implications of  the  proposal  were  not  necessarily
	immediately apparent  in  the  first  few  days  following  Bernstein\'s
	publication, the incremental improvements to parts of  NFS  outlined  in
	the  proposal  turn  out  to  carry   significant   practical   security
	implications impacting the overwhelming  majority  of  deployed  systems
	utilizing RSA or DH as the public key algorithms.
	

	Coincidentally, the day before the panel, Nicko  van  Someren  announced
	at the FC02 rump session that his team  had  built  software  which  can
	factor 512-bit RSA keys in 6 weeks using only hardware they already  had
	in the office.
	

	A very interesting result, indeed. (While 512-bit keys had  been  broken
	before, the feasibility of factoring 512-bit keys on just the  computers
	sitting around an office was news at least to me).
	

	The panel, consisting of Ian Goldberg and Nicko van Someren,  put  forth
	the following rough first estimates:
	

	While   the   interconnections   required   by   Bernstein\'s   proposed
	architecture add a non-trivial level of complexity,  as  Bruce  Schneier
	correctly pointed out in his latest CRYPTOGRAM  newsletter,  a  1024-bit
	RSA factoring  device  can  likely  be  built  using  only  commercially
	available technology for  a  price  range  of  several  hundred  million
	dollars to about 1 billion dollars. Costs may well  drop  lower  if  one
	has the use of a chip fab. It is a matter of public record that the  NSA
	as well as the Chinese, Russian, French,  and  many  other  intelligence
	agencies all operate their own fabs.
	

	Some may consider a price tag potentially reaching $1B prohibitive.  One
	should keep in mind that the NRO regularly  launches  SIGINT  satellites
	costing close to $2B each. Would the NSA have built  a  device  at  less
	than half the cost of one of their satellites to  be  able  to  decipher
	the interception data obtained via many such satellites? The  NSA  would
	have to be derelict of duty to not have done so.
	

	Bernstein\'s machine, once built, will have power  requirements  in  the
	MW to operate, but in return will be able to break a 1024-bit RSA or  DH
	key in seconds to minutes. Even under the most optimistic estimates  for
	present-day PKI adoption, the inescapable conclusion is  that  the  NSA,
	its major foreign intelligence counterparts, and any foreign  commercial
	competitors provided with  commercial  intelligence  by  their  national
	intelligence services have the ability to break on demand  any  and  all
	1024-bit public keys.
	

	The security implications of a practical breakability  of  1024-bit  RSA
	and DH keys are staggering, since of the following systems as  currently
	deployed tend to utilize keys larger than 1024-bits:
	

	- HTTPS

	- SSH

	- IPSec

	- S/MIME

	- PGP

	

	An opponent capable of breaking all of the above  will  have  access  to
	virtually any corporate or private communications and services that  are
	connected to the Internet.
	

	The most sensible recommendation in response to these findings  at  this
	time is to upgraded your security  infrastructure  to  utilize  2048-bit
	user keys at the next convenient  opportunity.  Certificate  Authorities
	may wish to investigate larger keys as appropriate. Some CA\'s, such  as
	those used to protect digital satellite content in Europe, have  already
	moved to 4096-bit root keys.
	

	Undoubtedly, many vendors and their captive  security  consultants  will
	rush to publish countless \"reasons\" why nobody is able to  build  such
	a device, would ever want to build such a device, could never  obtain  a
	sufficient number of chips for such a device, or simply should use  that
	vendor\'s \"unbreakable virtual onetime pad\" technology instead.
	

	While  the  latter  doesn\'t  warrant  comment,  one  question  to   ask
	spokespersons pitching the former is \"what key size is the majority  of
	your customers using with your  security  product\"?  Having  worked  in
	this industry for over a decade, I can state without qualification  that
	anybody other than perhaps some of the HSM vendors would be  misinformed
	if they claimed that the majority - or even  a  sizable  minority  -  of
	their customers have deployed key sizes larger  than  1024-bits  through
	their  organization.  Which  is  not  surprising,  since   many   vendor
	offerings fail to support larger keys.
	

	In light of the above, I reluctantly revoked all  my  personal  1024-bit
	PGP keys and the large web-of-trust that these keys have  acquired  over
	time. The keys should be considered compromised. The  revoked  keys  and
	my new keys are attached below.
	

	

SOLUTION

	 Editor\'s note

	 =============

	

	About PGP : Before you revoke your PGP key to  move  to  a  bigger  one,
	maybe you should consider using the original  Phil  Zimmerman  pgp2.6.3i
	or maybe gnupgp. Who knows how good is NAI/Mc  Affee  implementation  of
	RSA, the NSA ? How good is the entropy of the original prime numbers ?