29C3 - Version 1.9

F/a{hr-p).l//a,n
2.9/C-3

Speakers
djb
Nadia Heninger
Tanja Lange
Schedule
Day Day 2 - 2012-12-28
Room Saal 1
Start time 18:30
Duration 01:00
Info
ID 5275
Event type Lecture
Language used for presentation English
Feedback

FactHacks

RSA factorization in the real world

RSA is the dominant public-key cryptosystem on the Internet. This talk will explain the state of the art in techniques for the attacker to figure out your secret RSA keys.

A typical 1024-bit RSA public key is a product of two secret 512-bit primes. The security of the cryptosystem relies on an attacker being unable to compute the user's secret primes. The attacker can try guessing one of the secret primes and checking whether it divides the user's public key, but this is very unlikely to work: there are more than 2^500 512-bit primes, far beyond the number of atoms in the universe.

Fortunately for the attacker, there are much faster ways to figure out the secret primes. Some of the danger is visible in public announcements of factorization records by academic teams; the largest publicly factored RSA key, announced in 2009, has 768 bits. But what does this mean for the security of 1024-bit RSA?

There are several different reasons that a real-world attacker doesn't have to play by the rules of an academic challenge. Sometimes users have bad random-number generators; sometimes users generate both primes from a single search; sometimes users choose special primes to try to make RSA run faster; sometimes users leak secret bits through side channels; sometimes the attacker has a botnet, or a 65-megawatt data center in Utah or Tianjin.

This talk will assess the real-world threat to RSA-1024, explaining what the best attacks can do and how you can replicate them in your very own home or local GPU farm. Attack algorithms will be presented as Python code snippets and will already be online before the talk.

This is a joint presentation by Daniel J. Bernstein, Nadia Heninger, and Tanja Lange, surveying work by many people.