FactHacks [29c3]

0:09  0:12Today we have Daniel J. Bernstein,

0:12  0:15Nadia Heninger,

0:15  0:17and Tanja Lange.

0:17  0:20And they will talk about RSA factorization in the real world.

0:20  0:22Talk is called FactHacks.

0:22  0:30applause

0:30  0:32Nadia: Thank you.

0:32  0:37So we're going to start with a crypto lecture in 5 minutes.

0:37  0:41So, just to begin, since we're talking about RSA.

0:41  0:44Here is a picture of RSA for you.

0:44  0:49RSA is the first published publickey cryptosystem.

0:49  0:51So by a publickey cryptosystem, what I mean is

0:51  0:54a cryptosystem that has two keys intead of just having

0:54  0:57one key. You might think "ok you encrypt a message

0:57  0:59to that key and you decrypt a message to that key"

0:59  1:01That is a symmetric cryptosystem.

1:01  1:03A publickey cryptosystem has two keys.

1:03  1:06One is the public key and one is the private key.

1:06  1:08The public key you publish to the world and

1:08  1:10anyone can use that key to encrypt a message,

1:10  1:11especially to you.

1:11  1:14And only you, who have the private key, can decrypt that.

1:14  1:19So the RSA paper was the first published publickey cryptosystem.

1:19  1:21That was in 1977.

1:21  1:23This revolutionized cryptography and enabled

1:23  1:26the development of the Internet.

1:26  1:32So 35 years later RSA is still the most commonly used publickey cryptosystem.

1:32  1:36If you ever use the Internet, you probably use it every day.

1:36  1:42So here is a sample SSL certificate which uses RSA.

1:42  1:45If you use SSH you probably have an SSH key

1:45  1:48which probably is RSA.

1:48  1:52Before I launch into the math

1:52  1:55I want to explain what we're doing here.

1:55  1:57We wanted to, since you guys are hackers,

1:57  2:00you like code instead of formulas

2:00  2:03so we wanted to give you formulas in code.

2:03  2:05So what we're giving you is working Python code for

2:05  2:08all the math that we're going to do.

2:08  2:10And in order to do that we're going to use

2:10  2:13some software you call Sage.

2:13  2:16Sage is free opensource mathematics software.

2:16  2:20It is available at this URL sagemath.org.

2:20  2:22It's based off of Python

2:22  2:24so it's very simple if you know Python.

2:24  2:28It has a nice sort of interpreter

2:28  2:30that you can use just like Python.

2:30  2:32Here an example, 2*3=6.

2:32  2:35But there are some differences.

2:35  2:38For example the caret instead of in Python it's XOR

2:38  2:40in Sage it's exponentiation.

2:40  2:44So 2^3 is 8 in Sage.

2:44  2:47The other nice thing about Sage is that

2:47  2:50it has lots of useful mathematical libraries.

2:50  2:53For example if I, in the Sage interpreter, say factor(15)

2:53  2:56it helpfully tells me 3*5.

2:56  2:57That's pretty great.

2:57  2:59It also does a lot more advanced things, for example

2:59  3:00it can represent polynomials.

3:00  3:03I can say factor the polynomial x^21

3:03  3:08and it helpfully tells me the answer to that.

3:08  3:13So now that we've gone through what is Sage,

3:13  3:17I want to explain how to do RSA.

3:17  3:21Perhaps some of you have seen this before.

3:21  3:25In order to generate an RSA key, the first thing that you do

3:25  3:27is you generate two large random primes.

3:27  3:30So if we want a 1024 bit RSA key

3:30  3:35we generate two primes of size 2^512,

3:35  3:39so 512 bit primes, p and q.

3:39  3:42In order to generate the public key

3:42  3:45I multiply together p and q and you get some N.

3:45  3:46N has 1024 bits.

3:46  3:50And then you have what's known as the public exponent

3:50  3:54which you can choose 3 or 65537 or 35.

3:54  3:56It really doesn't matter what you choose.

3:56  3:59These are some of the most commonly used values.

3:59  4:03Now in order to generate a private key

4:03  4:08you choose d, the decryption exponent,

4:08  4:13to be the modular inverse of e mod (p1)*(q1)

4:13  4:15It doesn't matter why so much, for this talk

4:15  4:17but here is the formula

4:17  4:20or here is the command to do this in Sage.

4:20  4:23So now we have a public key and a private key

4:23  4:25that are pairs.

4:25  4:28And in RSA if you want to enrypt a message

4:28  4:32you raise your message to the e'th power mod n

4:32  4:35so you can do that with your public key here.

4:35  4:37And similarly decryption,

4:37  4:40you raise the ciphertext to the d'th power mod n

4:40  4:43and that will give you the message back out again.

4:43  4:46Fairly simple.

4:46  4:49Now I'm lying to you slightly.

4:49  4:51If you read this talk do not

4:51  4:53absolutely do not implement RSA this way.

4:53  4:55You must pad your message.

4:55  4:57This is a public service warning.

4:57  5:01We offered to tell you about factoring.

5:01  5:04What is the relationship between RSA and factoring?

5:04  5:09Now you can see easily from the formula

5:09  5:12from the private key here

5:12  5:16that if you know how to factor N into its prime factors p and q

5:16  5:19then you can just compute d, the decryption exponent

5:19  5:21of your private key.

5:21  5:24Clearly, if you can factor N you can compute the private key.

5:24  5:29But we don't actually know that factoring is the only way to break RSA.

5:29  5:34There might be some way that you can compute messages from ciphertexts

5:34  5:37that doesn't actually reveal the private key.

5:37  5:42And there's no proof either way that this is or is not possible.

5:42  5:43The last thing that I want to mention here

5:43  5:45just to clarify things

5:45  5:47some of you who might have taken

5:47  5:52complexity or algorithms courses or a beginning CS course

5:52  5:56you might have heard of NPhardness, the P vs. NP problem.

5:56  6:01And I just want to clarify that factoring is not known to be NPhard.

6:01  6:05Every computer scientist will love it if we could actually generate

6:05  6:11a cryptosystem which is known to be based of average case NPhardness.

6:11  6:14We don't know how to do that.

6:14  6:17RSA is not doing that.

6:17  6:22In addition the factoring problem is probably not NPhard.

6:22  6:26The question is: how hard is factoring?

6:26  6:27Since factoring is the best way that we know

6:27  6:31to break the most commonly used publickey cryptosystem on the Internet.

6:31  6:33Well I showed you some examples before

6:33  6:37where Sage had this helpful little factor function.

6:37  6:39So how well does it work?

6:39  6:41How long do people think this takes?

6:41  6:46two 32 bit integers multiplied together.

6:46  6:49I heard it'll go a couple of seconds.

6:49  6:500.01 seconds.

6:50  6:55This is on this computer.

6:55  6:58How about 64 bit integers, two of them multiplied together?

6:58  7:01So this is a 128 bit RSA modulus.

7:01  7:04Any guesses?

7:04  7:05One minute?

7:05  7:08Nope, 0.1 seconds.

7:08  7:15How about two 96 bit integers multiplied together?

7:15  7:16A couple of minutes?

7:16  7:184 seconds.

7:18  7:22How about two 128 bit integers multiplied together?

7:22  7:28This is a 256 bit RSA modulus.

7:28  7:29No guesses? Alright.

7:29  7:30500 seconds.

7:30  7:33So at this point it's starting to get a little bit iffy if I'm

7:33  7:36sitting on a plane trying to do this on battery power.

7:36  7:39laughter

7:39  7:44Clearly this is growing faster than linear in the size of the key.

7:44  7:46So what is actually going on?

7:46  7:49Well.

7:49  7:51Dan: Ok.

7:51  7:53Turns out these factoring functions

7:53  7:55they do look like they're getting pretty slow but

7:55  7:57wait a minute.

7:57  8:00Do we actually have to use this factor function

8:00  8:01if it's getting really slow?

8:01  8:04Maybe instead of trying to use Sage's factor function

8:04  8:09maybe we could just guess what the prime was.

8:09  8:12Now as an RSA user you might not think that this is a threat

8:12  8:14having somebody guess your prime

8:14  8:17because there is some way to count the number of primes,

8:17  8:19number of 512 bit primes and there's

8:19  8:22more than 2^500 512 bit primes.

8:22  8:24And if your random number generator is giving you

8:24  8:27any of those 512 bit primes with the same chance

8:27  8:31then any particular prime that the attacker guesses

8:31  8:33and just tries dividing n by that,

8:33  8:35see if it's evenly divisable, well

8:35  8:39any particular prime has only a 2^(500) chance

8:39  8:41of being guessed by the attacker.

8:41  8:43And even if the attacker tries a huge number of times

8:43  8:45he'll never guess your prime

8:45  8:48except what if your random number generator

8:48  8:52is working really really badly and doesn't give you 2^500 different primes?

8:52  8:56What if it only gives you, say, 2^40 different primes?

8:56  8:58And then suddenly the attacker could, well,

8:58  9:01try figuring out what those primes are.

9:01  9:03So here's how the attacker looks at this.

9:03  9:06The attacker says: ok I'm gonna target your public key.

9:06  9:09I'm gonna take your big N which is your secret...

9:09  9:11sorry, public key is big N,

9:11  9:14your secret key p times your secret key q,

9:14  9:15your private p and q.

9:15  9:17He's trying to figure out the p and q, given N.

9:17  9:20So what he does, he takes a bunch of devices that are out there

9:20  9:23and he looks at how they work

9:23  9:25or downloads a bunch of software which generates keys

9:25  9:29and then using that software, using those devices

9:29  9:32he tries generating a bunch of p's and q's for himself

9:32  9:35using whatever the random number generator is

9:35  9:37in that device or in that software.

9:37  9:38And then that's something which

9:38  9:41maybe the random number generator works really badly

9:41  9:43and maybe you're using that device, too.

9:43  9:46So the attacker tries each of the primes that he see's

9:46  9:47from this device

9:47  9:50and tries seeing does that prime divide your N.

9:50  9:51If you were using that device

9:51  9:53and it doesn't generate very many primes

9:53  9:56then maybe he gets lucky and finds your prime

9:56  9:58because the device has generated the same prime for him

9:58  10:00that it generated for you.

10:00  10:03Now does anybody actually build devices which

10:03  10:07screw up random numbers this badly?

10:07  10:09laughter

10:09  10:12As a matter of fact, yes, bears do shit in the woods.

10:12  10:14So there are some famous examples.

10:14  10:17We don't have a huge number of historical discussions in this talk

10:17  10:19but just a few examples here.

10:19  10:22Goldberg&Wagner totally broke the original Netscape

10:22  10:24generation of public keys.

10:24  10:27There are only something like 2^47 possible keys

10:27  10:29which is a countable numbers.

10:29  10:31So they could figure out all the possible keys

10:31  10:34that Netscape could generate if they you knew when you generated a key

10:34  10:36which was often very predictable.

10:36  10:38Another example: the Debian bug,

10:38  10:41the horrendous failure for SSH and lots of other applications

10:41  10:42from a few years ago.

10:42  10:46Debian and Ubuntu for a year and half were generating only

10:46  10:49well, fewer than a million possible public keys.

10:49  10:51So complete disasters of random number generation.

10:51  10:54But if you want to add to this list,

10:54  10:55if you want to do more and more of these

10:55  10:57find bad random number generators

10:57  11:01you have to say "ok what's the next device out there

11:01  11:02that might have been screwed up."

11:02  11:03"Let's look at it, look at the code."

11:03  11:05"See what kind of primes it generates."

11:05  11:07"Does it do badly?"

11:07  11:09It takes some real work to figure this out.

11:09  11:12Wouldn't it be nice if there was a systematic way

11:12  11:15to just without having to do a lot of work,

11:15  11:17to look at each device, each piece of software,

11:17  11:18wouldn't it be nice to just figure out

11:18  11:22"oh yeah, let's just magically figure out

11:22  11:24if there's any primes out there generated

11:24  11:26from bad random number generators."

11:26  11:28You could imagine here's the easy attack.

11:28  11:30Here's the systematic way to do this.

11:30  11:34You take two users, so you and you.

11:34  11:35And you each have a public key.

11:35  11:37We're gonna grab those public keys

11:37  11:42N1 and N2

11:42  11:47and then hope that this N1 and N2 share a prime.

11:47  11:54N1 is some prime p times some q1 and N2 is some same prime p times a different q2.

11:54  11:56Now this could happen, you could have

11:56  11:59N1 and N2 sharing both primes.

11:59  12:02That would be legitimate that two people who are actually

12:02  12:06the same webserver sharing their keys, sharing their certificates,

12:06  12:07they know they're doing this,

12:07  12:09you can get the same public key from two places.

12:09  12:12Google has their keys copied to tens of thousands of servers,

12:12  12:13that's not a surprise.

12:13  12:15But if there's a different...

12:15  12:17If you have two different public keys

12:17  12:18they shouldn't be sharing primes.

12:18  12:20What if they do?

12:20  12:22Well, here's this magic Euclid's algorithm

12:22  12:25which will just print out the shared prime p.

12:25  12:26This is a very simple algorithm.

12:26  12:28It just takes one of the numbers, say N1

12:28  12:32and let's say N1 is the smaller one and N2 is the bigger one,

12:32  12:34it divides N2 by N1

12:34  12:38and replaces N2 by the remainder and then switches the numbers

12:38  12:40and that's exactly what this code does.

12:40  12:43The N2 % N1 that's again the N2 mod N1

12:43  12:46the least remainder when you divide N2 by N1.

12:46  12:49And then the result once one of the numbers gets down to zero

12:49  12:52the other number is exactly the shared prime.

12:52  12:54So this amazing algorithm,

12:54  12:57here's just a little manual example

12:57  13:00not with big 512, 1024 bit keys

13:00  13:04this is with just tiny little I guess 8 bit primes

13:04  13:0816 bit... well looks more like 13 bit keys.

13:08  13:12So two numbers coming in and one is 4187 and two is 5989.

13:12  13:15You can see if you keep dividing one number by the other,

13:15  13:16replacing it by the remainder,

13:16  13:19do that a few times, you quickly get down to zero.

13:19  13:23And the number right before the zero in the middle of the slide is 53.

13:23  13:27Now 53 is a shared prime between these two small keys.

13:27  13:29If you scale this up,

13:29  13:32if you do this computation for bigger numbers

13:32  13:34then here's another timing example.

13:34  13:37It's still really really fast, in the middle of the slide.

13:37  13:40This is doing 1024 bit keys that share a 512 bit prime.

13:40  13:45You can figure out this 512 bit prime so quickly that the timing

13:45  13:49there is 0.00 seconds, can't even see how fast it is.

13:49  13:51Ok, so that's Euclid's algorithm.

13:51  13:54Now you can actually do this for tons and tons of keys.

13:54  13:58You download, say, millions, tens of millions of keys from the Internet,

13:58  14:01all the different SSL servers, maybe go for some SSH keys,

14:01  14:04you download tons and tons of public keys and then

14:04  14:07you try all the pairs with Euclid's algorithm.

14:07  14:09And it's so fast that you can do this but actually

14:09  14:11you can do better.

14:11  14:14So there's an algorithm: batch GCD algorithm

14:14  14:15which takes a whole bunch of keys

14:15  14:20and figures out which of those keys share primes with the others.

14:20  14:23Much much faster than trying every pair.

14:23  14:24So you don't have to try every pair.

14:24  14:27It's kind of like sorting, it's about that kind of speed

14:27  14:29instead of having to try every pair.

14:29  14:31If you have tens of millions you don't have to do

14:31  14:33tens of millions times tens of millions of pairs.

14:33  14:36You just have to pretty much reap through the whole list once.

14:36  14:39So what does this batch GCD algorithm do?

14:39  14:41It's figuring out for the first N1,

14:41  14:44instead of computing the greatest common divisor,

14:44  14:46the Euclid result for N1 and N2

14:46  14:48and for N1 and N3 and so on,

14:48  14:52it figures out the product of N2, N3, N4 and so on,

14:52  14:55takes the greatest common divisor of that with N1,

14:55  14:57applies Euclid's algorithm to that

14:57  15:01and then does a similar thing for N2 and for N3 and so on.

15:01  15:06Each of those is gonna show you whether N1 or N2 or N3,

15:06  15:08it's gonna show you whether they share some prime

15:08  15:10with any of the other N's.

15:10  15:13If you did exactly the computation

15:13  15:15shown on the slide in the math formulas

15:15  15:17it would still be too slow.

15:17  15:20But the batch GCD algorithm finds redundancies

15:20  15:23in these GCDs, and here's exactly what it does:

15:23  15:26It figures out the product of all of the keys.

15:26  15:30So you take, say, a million keys and you multiply them all together.

15:30  15:34And that's done with the code here where you do...

15:34  15:35maybe I'll just skip to the bottom.

15:35  15:37You see numbers 10, 20, 30, 40.

15:37  15:39You build a product tree.

15:39  15:42So you take 10 times 20, compute 200.

15:42  15:45Take the next pair 30 times 40, compute 1200.

15:45  15:48The take the pair of products 200 times 1200.

15:48  15:50If you have more numbers, you have more levels in the tree.

15:50  15:55And that's exactly what the Sage code does here.

15:55  15:59And then the last step of the algorithm is

15:59  16:03kind of going down the tree, building a remainder tree.

16:03  16:07So what's happening here to figure out the greatest common divisor

16:07  16:10of N1 with the product of all the other keys,

16:10  16:13the idea is to take this product

16:13  16:16which is called big R on this slide,

16:16  16:23take the product of all the keys and then divide that by N1^2

16:23  16:26and then take the remainders, so R mod N1^2,

16:26  16:31divide by N1 and then compute the greatest common divisor of N1 mod N.

16:31  16:33And the amazing effect is that it's exactly the

16:33  16:35greatest common divisor we were looking for.

16:35  16:38And what this little Sage script does is that it takes

16:38  16:42R and divides R by, well a bunch of N's in a really fast way,

16:42  16:44and then at the bottom, once it has figured out

16:44  16:47all mod N1^2, all mod N2^2 and so on,

16:47  16:49divides those by N1 and N2,

16:49  16:52takes the greatest common divisor with N1 and N2

16:52  16:55and that's exactly telling you, the outputs here

16:55  16:57that are different from 1, are exactly telling you

16:57  17:00which N's share a prime with some others.

17:00  17:04This very remarkably short little script does work quite well.

17:04  17:07Here's how fast these are.

17:07  17:10So I'm on some 800 MHz core.

17:10  17:13If you try this for, say, a hundred numbers,

17:13  17:17just hundred random 1024 bit numbers,

17:17  17:21it doesn't matter what the numbers are, they always run at the same speed,

17:21  17:23then that takes 0.05 seconds.

17:23  17:27If you have 10 times as many numbers it takes about 20 times as long.

17:27  17:31And if you have another 10 times as many numbers it takes about 20 times as long.

17:31  17:33And it keeps scaling up like that.

17:33  17:36So you can get to millions or tens of millions of numbers

17:36  17:39and it still finishes in a reasonable amount of time.

17:39  17:40So, amazingly fast algorithm.

17:40  17:44You don't have to scale this up to like 2^50 or 2^100 keys.

17:44  17:46There's only, say, tens of millions of keys out there

17:46  17:48and this runs reasonably fast.

17:48  17:51Ok.

17:51  17:52Can you actually hope for this to work?

17:52  17:55Are random number generators really this bad?

17:55  17:56Well...

17:56  18:00laughs

18:00  18:03There's a 2012 paper from Heninger

18:03  18:05that's the same Heninger we have sitting here

18:05  18:06and Durumeric, Wustrow, Halderman,

18:06  18:10that's got the best paper award at USENIX Security 2012.

18:10  18:15What they did was they tried exactly this on tens of millions of keys out there

18:15  18:18and factored tens of thousands of keys.

18:18  18:23Admittely they used a C version of this instead of this

18:23  18:24Sage script but

18:24  18:26the Sage script will go up to millions.

18:26  18:28It's just when you get beyond that you want to write it in C

18:28  18:31to deal with using a lot of memory.

18:31  18:35But you can use exactly this script for pretty large chunks of keys.

18:35  18:38And so they factored tens of thousands of keys and said

18:38  18:42that these keys are typically not your bank keys.

18:42  18:45They gonna be, say, keys for your home router.

18:45  18:48So the vulnerable devices are not gonna be,

18:48  18:50say, a big server out there.

18:50  18:54The vulnerable devices will be your FRITZ!Box.

18:54  18:57applause

18:57  19:00Thank you, Nadia.

19:00  19:07It's good to read the paper, go to factorable.net

19:07  19:09and you get tons of analyses of why this happened

19:09  19:13and why these devices are generated guessable numbers.

19:13  19:15I mean numbers that are so nonrandom that they get

19:15  19:18repeated between a lot of keys out there.

19:18  19:20There was at the same time another team that

19:20  19:24like within days announced the same result.

19:24  19:27They independently did the same computation.

19:27  19:29They said "yeah, we've also downloaded

19:29  19:31a bunch of keys and factored as many as we could"

19:31  19:33with basically the same algorithm.

19:33  19:35At the end of it "yeah we factored

19:35  19:37tens of thousands of keys."

19:37  19:39That paper has no analysis.

19:39  19:42They're like "yeah, there's keys"

19:42  19:43"they share primes for some reason"

19:43  19:46"I guess ecommerce is dead"

19:46  19:48"go out, change your bank keys"

19:48  19:49"call the New York Times"

19:49  19:51There's the New York Times article:

19:51  19:53"Flaw Found in an Online Encryption Method"

19:53  19:55I also like the advertising on the side here.

19:55  19:57Like iron key on the top and then:

19:57  20:01"Encrypt, decrypt & access my secret data in real time"

20:01  20:03"try it free for 30 days."

20:03  20:05"I secured my cloud data. Have you?"

20:05  20:07Awesome advertising there.

20:07  20:12Once you found that there's a problem like this

20:12  20:15then of course you start looking around for more and more places

20:15  20:17where you might have some bad randomness.

20:17  20:23For example there is a paper, or at least slides,

20:23  20:25by Chou in Taiwan, saying

20:25  20:32they took two million Taiwan Citizen Digital Certificates

20:32  20:34and did some GCDs

20:34  20:37and found that a 103 of those were

20:37  20:38factorable.

20:38  20:40So anybody who downloaded these certificates

20:40  20:43which apparently are used in Taiwan for like paying your taxes,

20:43  20:44talking to banks I don't know,

20:44  20:47but paying taxes is one that I've checked.

20:47  20:50So a 103 people out there have these Taiwan

20:50  20:51Citizen Digital Certificates where

20:51  20:54you're supposed to have in this database things like

20:54  20:57the names of the people and their ID numbers

20:57  21:00but you aren't supposed to have their secret keys.

21:00  21:02The whole point is those are supposed to be private

21:02  21:04kept on some smartcards that are issued to the citizens

21:04  21:05in Taiwan.

21:05  21:09And the randomness generation is so bad that

21:09  21:13103 of those keys have now been factored.

21:13  21:15The smartcard manufacturer, I also like this quote,

21:15  21:19it's a company based in Munich called

21:19  21:22Giesecke & Devrient and their motto is:

21:22  21:25"Creating Confidence"

21:25  21:35applause

21:35  21:38Tanja: There's gonna be more of Dan, don't worry.

21:38  21:40But we promised a bit more than just factoring

21:40  21:43bad keys or the keys with their primes.

21:43  21:47If you find another number like this one.

21:47  21:50So here's coming some more of math stuff.

21:50  21:53So if you see a number like this and you

21:53  21:56observe this last digit, then yes.

21:56  21:59It's very easy for you to see it's divisable by 5.

21:59  22:01So if you find such a key that is easy to break

22:01  22:03and you are a computer rather than a human being

22:03  22:05you look at lots of those numbers.

22:05  22:07You have a list of small primes stored

22:07  22:10and what you're gonna do is just trial division.

22:10  22:12So if there's any small factor

22:12  22:14it's very easy to find this trial division.

22:14  22:17Or what Dan showed was the remainder trees.

22:17  22:20You can also do this for batch trial division.

22:20  22:24So assuming that you're looking for a prime p somewhere

22:24  22:27then you go linearly all the way up to the p

22:27  22:30and there are about p/log(p) many primes

22:30  22:32before you find this p.

22:32  22:34For each of them you just do exact division.

22:34  22:37If it works, fine you found a factor, otherwise not.

22:37  22:39Now this is not going to work against your normal keys.

22:39  22:44I know that in the example that Dan mentioned by Wagner&Goldberg

22:44  22:47that they found one factor which had a 9 in there

22:47  22:50but usually your keys don't have a 9.

22:50  22:55For slightly larger numbers there is a method due to Pollard.

22:55  22:57So if you see the respectful number here,

22:57  23:00there is no obvious divisability of this one.

23:00  23:03One thing you can try is

23:03  23:07a walk, well we call this a walk.

23:07  23:10You start with some random number smaller than N

23:10  23:13and some offset here.

23:13  23:17I should also say, all those scripts are available at this URL.

23:17  23:22So if you go to facthacks.cr.yp.to then you'll find all the scripts

23:22  23:24if you want to play with it at the same time,

23:24  23:27including this one with some explanations and such.

23:27  23:31So what you do is you start off two different numbers,

23:31  23:35one at each step squares it and adds c.

23:35  23:37And the other one squares it, adds c,

23:37  23:40and squares it again and adds the c.

23:40  23:41Each time computing mod N.

23:41  23:44So you have two sequences running around,

23:44  23:46one is twice the speed as the other.

23:46  23:51At every step you check with the GCD of this number N

23:51  23:53and the difference between the two walks

23:53  23:55hasn't anything interesting now.

23:55  23:57N is an RSA modulus, the only thing interesting

23:57  24:00could either be p or q.

24:00  24:03So for this particular number

24:03  24:04when I run this

24:04  24:09I find 2053 after a few milliseconds.

24:09  24:11So this is again a cooked up example.

24:11  24:13You won't find such a small factor if you're trying

24:13  24:16a general RSA factor, otherwise your numbers

24:16  24:18would be totally busted but

24:18  24:21this shows if you have a small number in there

24:21  24:22it's very easy to find.

24:22  24:24All later on when Dan is talking about the number field sieve

24:24  24:26this is an interesting subroutine.

24:26  24:28So if you ever need to find small numbers

24:28  24:31then, sure trial division is very easy for

24:31  24:34really small numbers taking this long,

24:34  24:38this one squared with p is much faster already.

24:38  24:42Now even faster than that, also due to Pollard,

24:42  24:45called Pollard's p1 method.

24:45  24:48Here is again an innocent looking number N.

24:48  24:50You see the numbers get larger.

24:50  24:52This is a 256 bit number.

24:52  24:57In order to deal with such a number there is one step

24:57  24:59which is expensive but you would do it only once

24:59  25:01for all different numbers you want to try,

25:01  25:05namely compute a big integer which has lots of little factors.

25:05  25:07So you take the least common multiple

25:07  25:10from 1, 2, 3, 4, 5...

25:10  25:12Ok, once you hit the 4 you have another 2 in there.

25:12  25:14So there's lots and lots of powers of 2,

25:14  25:15lots and lots of powers of 3.

25:15  25:19And then the larger primes only appear like once.

25:19  25:23But you're not going up to 256 or 128 anywhere.

25:23  25:27You're sticking here at 22 bits

25:27  25:29and then use the same function that Nadia explained

25:31  25:33in the RSA computation, namely the modular exponentiation.

25:33  25:37So you take the 2^y,

25:37  25:38this huge number,

25:38  25:40but the whole computation mod N.

25:40  25:45So this whole thing never grows beyond this 256 bit number.

25:45  25:48Or for a real world example it would be a 1000 bit number.

25:48  25:53And then you compute the GCD of this number and N.

25:53  25:55For this particular one, again it's a cooked up example,

25:55  25:56you get a factor.

25:56  26:00Now this factor is actually 120 bits.

26:00  26:02This is not a small factor.

26:02  26:06So if you were using 256 bit numbers

26:06  26:08this is something that could happen to you

26:08  26:11and nevertheless this method would find it.

26:11  26:14So this finds much larger factors than trial division

26:14  26:15or the Rho method in the same amount of time.

26:15  26:17But it doesn't work for all primes.

26:17  26:20It works for primes which are kind of special.

26:20  26:24Now what's special about this prime or the other factor?

26:24  26:30If you take p and subtract 1, hence the name p1 method,

26:30  26:32and factor that thing,

26:32  26:35that has lots, lots of small numbers.

26:35  26:37So that's something we call smooth.

26:37  26:40So a smooth number doesn't have big factors.

26:40  26:44So a prime is like the least smooth number you can imagine.

26:44  26:47And 2 to the power large is the most smooth number,

26:47  26:50so lots of little factors means smooth.

26:50  26:56This largest factor happens to be 21.7 bits

26:56  26:58which is why I chose the 22 bits here.

26:58  27:04So as soon I run over the largest prime in p1

27:04  27:06with this exponent y here

27:06  27:09then I do find this factor.

27:09  27:11Now if you thought this was math

27:11  27:12there is even more scary math

27:12  27:16namely there are methods which are generalizing

27:16  27:19this p1 method using elliptic curves.

27:19  27:22If you listen to the crypto advertisement

27:22  27:23elliptic curves are usually something very good,

27:23  27:25something you should have on your smartcard.

27:25  27:27It's faster than RSA and so on.

27:27  27:29That's the same type of elliptic curve

27:29  27:32but here elliptic curves come in as an attack tool.

27:32  27:35There is a method called the elliptic curve method ECM

27:35  27:41which is a generalization of this p1 method and does not need anything special,

27:41  27:45I mean avoiding such primes is easy.

27:45  27:46If you look into older standards

27:46  27:50they all warn about "make sure to use strong primes"

27:50  27:53"make sure to check that your p1 is not smooth"

27:53  27:55And of course you don't want your p1 to be smooth

27:55  27:58because otherwise this attack works.

27:58  28:01But if I have some elliptic curve

28:01  28:03a different type of prime is weak for that curve

28:03  28:06and I have many, many, many elliptic curves.

28:06  28:09For each of the curves some primes are weak.

28:09  28:11You can't exclude this method.

28:11  28:14So the only thing you can do is just, well,

28:14  28:18choose your prime large enough and hope, well,

28:18  28:20make sure p1 doesn't get it and hope

28:20  28:23that the next elliptic curves won't get it.

28:23  28:25So elliptic curves are good for attacking.

28:25  28:28It's still not the fastest method out there

28:28  28:33but it's a good method for random factoring.

28:33  28:36It's not the best method for finding RSA factors

28:36  28:38but if you have a number which is most likely

28:38  28:45not too nonsmooth then it's a good method.

28:45  28:47Now this is what you do for finding small factors.

28:47  28:51To show some method for big factors,

28:51  28:54now here that is a big number.

28:54  28:59But this is what I would call factorization by inspection.

28:59  29:08What's wrong with this number?

29:08  29:10I mean this number is not small and

29:10  29:13it won't have small factors, I promise you this.

29:13  29:20So it's a decimal representation, so 9 is the digit before 0.

29:20  29:23This looks very close to the power of 10.

29:23  29:28Actually this is very close to 10^340.

29:28  29:30If you take the square root of it

29:30  29:34then you almost exactly hit 10^170.

29:34  29:37This example was cooked up as taking two primes

29:37  29:47namely 10^17033 and 10^170+63 and multiplying them.

29:47  29:49So if you see lots of 0's and lots of 9's

29:49  29:51then you know that you are very close to a certain power.

29:51  29:53Now in real life this wouldn't be a power of 10,

29:53  29:55it would be a power of 2.

29:55  29:56And there actually are some examples.

29:56  29:59There's a famous story of a letter bomber in Austria

29:59  30:03who wanted his message to be crackable

30:03  30:06and he sent a message, well he was some rightwing asshole

30:06  30:08that was letterbombing people

30:08  30:11and then he sent an encrypted message to the police.

30:11  30:15And the police tried to factor it and tried to decipher it

30:15  30:19hoping it would be the list of the next victims.

30:19  30:21In the end it was not but

30:21  30:24this person was actually using very close to a power of 2

30:24  30:26in order to have people crack it.

30:26  30:28In the end it was just some propaganda,

30:28  30:29some rightwing stuff as well.

30:29  30:33So there are people using this for breakability.

30:33  30:35I'm not aware of people actually using this as an accident.

30:35  30:40But what can happen to you is not using close to the power of 2

30:40  30:46but saying "ok I learned I shouldn't be close to the power of 2

30:46  30:49so I take some offset and take the next prime."

30:49  30:51Next prime just means, add 1, check is it prime,

30:51  30:54add next one, add 2, add 3

30:54  30:57Just check primes linearly from then on.

30:57  30:59Now if we jump to this where we finally find our prime p

30:59  31:01it's a good prime.

31:01  31:04It's not anywhere close to the power of 2 because my c was large enough.

31:04  31:07Made it, good.

31:07  31:09Now on q.

31:09  31:11So again call the next_prime().

31:11  31:14So I do p+1, p+2 until I find a prime.

31:14  31:17That means that if you take the product of the two

31:17  31:19then this N is very close to a square.

31:19  31:23So this N is cooked up with this method.

31:23  31:24You don't see anything on the end,

31:24  31:27there's nothing wrong there.

31:27  31:30But when you compute the square root of it

31:30  31:33it is almost an integer, it's .99999...

31:33  31:35and then some dirt here.

31:35  31:39So then you'll know that your primes were too small.

31:39  31:42Sorry, not too small, too close to each other.

31:42  31:45So if you ever take an RSA factor modulus

31:45  31:47and you compute the square root

31:47  31:48and you see something like this

31:48  31:52then you know: that user did this method.

31:52  31:54You could just say, I take the number,

31:54  31:57subtract 1, subtract 2, just go off from the square root.

31:57  32:02All you can check how far away is it from being a square.

32:02  32:04So you take the seeding,

32:04  32:08that means the closest integer counting upwards.

32:08  32:12Just round it to this two, here's 57, is there a 56?

32:12  32:15Compute the square of that and subtract N.

32:15  32:18Now in this example that is 4096

32:18  32:23which itself is a square.

32:23  32:27So the difference of N and a^2 is a square.

32:27  32:31Then I take this 64, take a64, divide N,

32:31  32:34it's an exact division, so I found one of the factors.

32:34  32:37And then there's the other factor.

32:37  32:40It doesn't matter whether it's a power of 2 or a power of 10.

32:40  32:43What matters is that the numbers are too close.

32:43  32:45Now this method actually works surprisingly well

32:45  32:47even if we don't do next_prime().

32:47  32:50So here's another example where I didn't do the next_prime()

32:50  32:52but did something larger

32:52  32:55so this is not really close to a square.

32:55  32:58Some 9's but not too many.

32:58  33:00What we did before we wrote it as a difference of squares

33:00  33:05and then divided N by one of these two factors.

33:05  33:10Now in this case here I would not start as a^2N

33:10  33:12but I say, well, if a^2N is not a square

33:12  33:16I try the next one, I do (a+1)^2, (a+2)^2

33:16  33:21each time subtract N and check when this is a square.

33:21  33:24Now for this example I get lucky after 2.

33:24  33:26And this actually took me a long time to cook up this example

33:26  33:29because I was starting at something which was

33:29  33:32half of the bits of p were changed.

33:32  33:36So I was actually starting with a cube quite a distance away.

33:36  33:38Still, most of those were just giving a square.

33:38  33:42They were not giving me anything larger than zero here.

33:42  33:46Now for general numbers if I wouldn't do like next_number()

33:46  33:49but just, well, random prime, another random prime.

33:49  33:53It still works but takes a long time

33:53  33:55because I can always write it this way.

33:55  33:57This is a, this is b.

33:57  34:01But then usually it would take about square root of N

34:01  34:04which is the same size as p until I get there.

34:04  34:07This is a nice method if it looks like lots of

34:07  34:139999 and otherwise do something better as Dan will tell now.

34:13  34:14Dan: Ok.

34:14  34:22applause

34:22  34:24Alright, so it's bad to have p and q

34:24  34:25too close to each other

34:25  34:29or have a small p or to have p and q nonrandom.

34:29  34:31So let's do everything right.

34:31  34:34Let's make just independently choose some big p

34:34  34:37between 2^511 and 2^512

34:37  34:39and choose some big q

34:39  34:43without being like the next prime or anywhere in the ballpark of p.

34:43  34:48You could maybe say q has to be between 2^509 and 2^510

34:48  34:50and then it's definitely nowhere near p.

34:50  34:53Now you got this public key and p times q

34:53  34:54which is a 1024 bit RSA key.

34:54  34:59If nothing has gone wrong with your randomness generation

34:59  35:00then what does the attacker do?

35:00  35:04Well, we don't know anything fast.

35:04  35:07So this is gonna be the one part of the talk

35:07  35:08where there's these big powers of 2

35:08  35:10for how fast things are

35:10  35:11because they're not really fast.

35:11  35:15You have to think about how much something like 2^80 is.

35:15  35:16There's all these different methods,

35:16  35:18I'll just skip down to the last two.

35:18  35:20There's the quadratic sieve (QS),

35:20  35:22the number field sieve (NFS).

35:22  35:24These have been around since, well,

35:24  35:29QS since the 80th, NFS since the early 90th.

35:29  35:32The NFS, the general consensus is

35:32  35:35it takes something like 2^80 operations.

35:35  35:37Now here's something fun to try.

35:37  35:39If somebody says 2^80 operations

35:39  35:41and there's some cryptographer talking about the security or something,

35:41  35:44ask them: what do you mean by an operation?

35:44  35:46How fast is this operation?

35:46  35:47And then most of the people saying this

35:47  35:49will go running screaming like:

35:49  35:50I don't know what an operation is,

35:50  35:51don't ask me that question.

35:51  35:53But still people will confidently tell you

35:53  35:56that the NFS takes 2^80 operations

35:56  36:00to break any 1024 bit RSA key

36:00  36:02even if the user hasn't done anything wrong,

36:02  36:04the implementor hasn't done anything wrong.

36:04  36:06And this number, this 2^80

36:06  36:08if you pin down what those operations are,

36:08  36:11this is something which is doable today

36:11  36:16by people with a big botnet or people with a big computer cluster.

36:16  36:19I'll give some details what I mean, the size is there.

36:19  36:22As your computers get cheaper and cheaper,

36:22  36:24somehow chips aren't going up in clockspeed

36:24  36:25but they're still getting cheaper.

36:25  36:28You can get a really cheap ARM which is doing

36:28  36:29the same kind of computations

36:29  36:32that a pretty big CPU was doing several years ago.

36:32  36:33And chips are gonna continue getting cheaper

36:33  36:37for a while. These attacks against RSA 1024

36:37  36:40are going to be common doable for more and more people.

36:40  36:43How do these methods work?

36:43  36:47I'll give one example and then one little Sage script.

36:47  36:50Let's try just a really small number.

36:50  36:52This will be with the quadratic sieve

36:52  36:54which is not as fancy as the number field sieve

36:54  36:56but it will give you some idea of how these methods work.

36:56  37:00The QS starts with that Fermat method you heard about.

37:00  37:04Remember, the idea there was to try to find a square

37:04  37:09as a^2N, so a was like the square root of N

37:09  37:11or maybe the plus 1, plus 2 and so on

37:11  37:13and you keep searching for a+1 and so on,

37:13  37:16search for numbers that if you square them and subtract N

37:16  37:17then you get a square.

37:17  37:21So let's try that for 50=2759 which is not very big.

37:21  37:24Then you try, 53 was the ceiling of the square root,

37:24  37:28square that, subtract 2759, you get 50.

37:28  37:31Well 25 would be a square, but 50 is not a square

37:31  37:33it's 2 times 25, 2 times 5^2.

37:33  37:37And then you try another number, 54^22759

37:37  37:40umm 157, that's too complicated

37:40  37:43I don't remember that being a square so let's just skip it.

37:43  37:46And then you keep going like this, 266, 377,

37:46  37:48490. I remember 49 is a square

37:48  37:50but that doesn't mean that 490 is a square

37:50  37:52cause 10, 2 times 5, that's not a square.

37:52  37:56And 605, you can try...

37:56  37:59We remember how to take out the 5

37:59  38:01and then 60... 605 divided by 5.

38:01  38:04You can figure out it's 5 times 11^2.

38:04  38:05It's almost a square.

38:05  38:07You keep doing this for a while

38:07  38:11and it seems like Fermat's method is actually working pretty badly.

38:11  38:14It does work eventually but it's taking quite a while.

38:14  38:17Here's what the quadratic sieve does.

38:17  38:20From the same computation you look at these

38:20  38:22numbers that were not exactly squares

38:22  38:2450 and 490 and 605

38:24  38:27and you notice if you multiple them together

38:27  38:2850 was 2 times 5^2

38:28  38:31490 is 2 times 5 times 7^2

38:31  38:33605 is 5 times 11^2

38:33  38:35and then you multiply those together

38:35  38:39you get 2^2 and 5^4 and 7^2 and 11^2

38:39  38:41and that's exactly the square of something.

38:41  38:45The square of 2^1 times 5^2 times 7 times 11.

38:45  38:48Then the quadratic sieve is taking the square root of that number

38:48  38:53and subtracting that from the product of the fiftysomethings

38:53  38:54that were on the left side

38:54  38:57and taking the greatest common divisor of that with N

38:57  39:00and amazingly that produces a factor of N.

39:00  39:02And it's not just some random accident that

39:02  39:04if you had tried the greatest common divisor of

39:04  39:06"write down some hocuspocus then"

39:06  39:09"you eventually get 31 coming out"

39:09  39:11"every 31 times you write down a random number"

39:11  39:13"it will have this 31 dividing it"

39:13  39:15No, you can try this for bigger and bigger numbers

39:15  39:17and actually this keeps working.

39:17  39:19As soon as you find a square product

39:19  39:23then half of those square products are gonna factor N.

39:23  39:25So that's how the quadratic sieve works.

39:25  39:29Here's a more systematic script with a much bigger number

39:29  39:31which if it were just hocuspocus this wouldn't work.

39:31  39:33But this does work.

39:33  39:37So there's a number from my computer's random number generator

39:37  39:4231415926... laughter

39:42  39:45You try writing down a bunch of squares...

39:45  39:48maybe I should get my computer's random number generator checked.

39:48  39:51It is this two year old laptop you heard about before

39:51  39:52so I'm not sure it's working properly.

39:52  39:56You take a bunch of a^2N and then

39:56  39:57let's make a list of those called X.

39:57  40:01You can see the range, there is up to 500.000 numbers.

40:01  40:03It's a pretty big list we're talking about.

40:03  40:06And then search through those elements,

40:06  40:09search through those a^2N, those differences,

40:09  40:10the elements in this list,

40:10  40:13to see which ones have easy factorizations.

40:13  40:15Now a lot of numbers like that 157

40:15  40:17I know what the factorization of that is

40:17  40:20but there is function which you can find on our website

40:20  40:23easyfactorizations() which looks through the list X

40:23  40:25and if it finds numbers that are easy to factor

40:25  40:28then it quickly writes down the factorizations

40:28  40:30using the small prime techniques you heard about.

40:30  40:33And then makes a list of those easy factorizations,

40:33  40:34puts those into F.

40:34  40:38And then there's a big chunk which I won't try to explain

40:38  40:40which is called linear algebra mod 2.

40:40  40:43And that somehow figures out a square

40:43  40:46that comes from the factorizations,

40:46  40:48somehow looks through this list of factorizations

40:48  40:51and magically applies some linear algebra stuff.

40:51  40:53Well ok, I won't go through that.

40:53  40:54It's something doable

40:54  40:59and this is using some standard Sage functions to do it pretty easily.

40:59  41:02There's all sorts of things that

41:02  41:04in the interest of time I won't get into

41:04  41:06like how this easyfactorizations() works.

41:06  41:08And this is something where people write papers

41:08  41:10and papers and papers talking about trying to make this

41:10  41:12go as quickly as possible.

41:12  41:15I do want to emphasize one fact about these methods:

41:15  41:17the boldfaced **very small memory requirements**.

41:17  41:20You can use the elliptic curve method

41:20  41:22that you heard about before

41:22  41:25you can use that to figure out easy factorizations

41:25  41:27using very little memory.

41:27  41:29That means you can build a chip

41:29  41:30like a FPGA, a special purpose ASIC,

41:30  41:33you can have thousands of little ECM units

41:33  41:35running in parallel, so you can really

41:35  41:38massively parallelize this easyfactorizations() function.

41:38  41:40So if people tell you "oh you need tons of

41:40  41:43memory for sieving to find easy factorizations"

41:43  41:46then you should tell them "no no, that's not true"

41:46  41:48"ECM you can do with very little memory

41:48  41:50running massively parallelizable"

41:50  41:53And then there's other things which,

41:53  41:54I suppose if we had another hour

41:54  41:56then we could get into all these details

41:56  41:59of like how the number field sieve goes beyond this.

41:59  42:02It's a similar kind of method but gets more complicated.

42:02  42:05I do want to emphasize again thing in boldface here

42:05  42:07which is that if somebody tells you

42:07  42:10"oh 2^80 operations, the attacker wouldn't do

42:10  42:14that because the target isn't worth that much to them"

42:14  42:18Well, **Batch NFS** is a way to take a bunch of N's

42:18  42:21and like the batch techniques before

42:21  42:24there's some magic ways to find redundancies

42:24  42:26between doing factorizations of those N's.

42:26  42:27So somebody tells you:

42:27  42:30"oh 2^80, that isn't worth it for the attacker."

42:30  42:33Well, **Batch NFS** reduces the cost quite a bit

42:33  42:35for factoring each key.

42:35  42:37If the attacker has a lot of keys to target

42:37  42:40they can factor all of them in not much more cost

42:40  42:41than just factoring one.

42:41  42:44So don't believe people who take an economic view

42:44  42:47how much the number field sieve is worth.

42:47  42:49Alright, what does this mean?

42:49  42:52Can the attacker actually do the NFS

42:52  42:54once they've put in all these optimizations?

42:54  42:59Well if you look carefully at the analyses of the NFS

42:59  43:02there are only about 2^70 differences.

43:02  43:04Things like these a^2N's.

43:04  43:09If you look through 2^70 of those and scan them properly,

43:09  43:11find easy factorizations, do linear algebra,

43:11  43:14you will factor any 1024 bit key.

43:14  43:16And 2^70, how big is that number?

43:16  43:21It's actually small enough that you can do this computation on

43:21  43:22your favorite botnet.

43:22  43:26Say, Conficker is shrinking, still

43:26  43:28and it will probably be wiped out at some point

43:28  43:29but it's an example of what you can do

43:29  43:32using any of these security problems that are deployed

43:32  43:34on enough machines.

43:34  43:35You can break into a bunch of machines,

43:35  43:37millions of machines.

43:37  43:40Conficker estimates vary between 7 million and 12 million machines.

43:40  43:44So use your, say, 2^23, that's 8 million machines.

43:44  43:47Count how many seconds there are in a year

43:47  43:49and then, say, ok that means we have to do

43:49  43:522^22 differences per second machine.

43:52  43:57And that is slower than state of the art factorization code already runs.

43:57  43:59So it's actually a pretty easy computation.

43:59  44:02You don't even need that many millions of computers to do this.

44:02  44:04If people tell you "wait a minute"

44:04  44:06"you can't just use a bunch of machines"

44:06  44:08"there's all this work for linear algebra"

44:08  44:10Then I'll just skip this.

44:10  44:13Be aware that linear algebra is not as much of a problem

44:13  44:15as some people would say.

44:15  44:19If you use a big botnet there's one little problem.

44:19  44:21For an attacker who breaks into a bunch of machines

44:21  44:24and then starts spinning them up, heating up the CPU,

44:24  44:26the fan starts running, the user starts wondering

44:26  44:28"why is my machine running so slowly?"

44:28  44:30Maybe only use half of the CPU

44:30  44:34but still it has still got a good chance of getting you detected

44:34  44:35and kicked off the machines.

44:35  44:37Users are gonna shut you down if you're doing a

44:37  44:39say, year of computation on your botnet.

44:39  44:43So what do you do instead?

44:43  44:45Well you build a little computer cluster.

44:45  44:49Now yesterday we heard about a big building

44:49  44:51in Bluffdale, Utah, that apparently

44:51  44:55is going to store all of the data collected by

44:55  44:57the NSA for the next hundred years

44:57  44:59or maybe forever.

44:59  45:01But something that I didn't hear emphasized yesterday

45:01  45:05was that this building also has a new power substation

45:05  45:08which is drawing 65 megawatts,

45:08  45:10well generating 65 megawatts.

45:10  45:14Now what are we doing with 65 megawatts?

45:14  45:15Is that the kind of power that you need to

45:15  45:17store a bunch of data on tapes?

45:17  45:21No, that's the kind of power you need to do computations.

45:21  45:25So what is NSA doing with 2^26 watts?

45:25  45:27Or maybe even with more watts.

45:27  45:31You shouldn't actually think that 2^26 is such a big number.

45:31  45:34Here's a little table with, well,

45:34  45:372^57 admittedly is pushing it a little bit.

45:37  45:41This is the total power that the earth gets from the sun

45:41  45:43of which about half gets to the earth's surface.

45:43  45:482^44 is the amount the human is using right now.

45:48  45:51Varies a little bit but I mean this is the average power

45:51  45:53including cars and such.

45:53  45:56If you have the botnet that breaks into millions of machines

45:56  46:00and runs in flatout that's about 2^30 watts.

46:00  46:02And actually if you think about it, wait a minute,

46:02  46:03there's a lot of machines out there.

46:03  46:07This means the 2^26 is not actually that much power.

46:07  46:11It's just one dinky little Bluffdale 65 MW computer center

46:11  46:15and actually if you're a government agency

46:15  46:16you probably have more than one of those.

46:16  46:19As you heard yesterday in the context of data storage

46:19  46:21but again, it's not just data storage.

46:21  46:26You don't make a 65 MW power station to just store data.

46:26  46:30Ok, if you just take standard graphics processing units

46:30  46:33and run 2^26 watts to those that will do about

46:33  46:362^84 floating point multiplications per year.

46:36  46:40You have to figure out, ok, what are exactly the operations involved here.

46:40  46:45This should be enough to break 1024 bit RSA

46:45  46:48and if NSA is not just buying GPU's offtheshelves

46:48  46:50but really tuning chips that they build

46:50  46:57using IBM to manufacture their chips at the moment.

46:57  47:02Apparently it wasn't costeffective for NSA to manufacture their own chips

47:02  47:04so in 2005 they started subcontracting for IBM

47:04  47:08but presumably through that fabrication IBM is building chips

47:08  47:11that NSA wants and those should be about 10 times faster

47:11  47:13than what GPU's can do.

47:13  47:18So it should be possible with this little 65 MW computer cluster

47:18  47:21to factor at least 1, maybe even 10,

47:21  47:23and then with batch NFS maybe even more

47:23  47:301024 bit RSA keys in a year.

47:30  47:38applause

47:38  47:41Nadia: So to conclude things up here I want to

47:41  47:43explain how you can use

47:43  47:46from the comfort of your very own home

47:46  47:52a distributed, a massive scale distributed cloud computing service

47:52  47:57to calculate private keys on your own.

47:57  48:00So many of you may be familiar with Amazon EC2

48:00  48:05but it turns out Google also has a large amount of computing infrastructure

48:05  48:07and they actually have a very convenient web interface

48:07  48:08to access it.

48:08  48:13laugther

48:13  48:22applause

48:22  48:24It's amazing what you can find on the Internet.

48:24  48:26laughter

48:26  48:29So ok, here's some keys except, you know,

48:29  48:31if you look at these carefully

48:31  48:33not all of these are sort of obviously RSA keys.

48:33  48:35There are some problems here

48:35  48:41like the second to last one on the bottom.

48:41  48:42So...

48:42  48:43laughter

48:43  48:50After doing this search we found this key and

48:50  48:55someone seems to have pasted a private key into pastebin

48:55  49:00and someone came along and interrupted part of it

49:00  49:05with some profanity.

49:05  49:07This is an interesting problem.

49:07  49:09What do we do with this key?

49:09  49:12Clearly this is an interesting key, we must have this key.

49:12  49:14laughter

49:14  49:25applause

49:25  49:26Step 1... yeah?

49:26  49:30Male: Did you see the easter egg in row 1?

49:30  49:31Nadia: Well, we'll discuss this.

49:31  49:34Angel: Questions will be later, after the talk please.

49:34  49:39Nadia: So yeah, we've removed the obvious problems here.

49:39  49:42But there's still an issue which is that

49:42  49:44we're missing hundreds and hundreds of bits of key.

49:44  49:46We can't brute forcethis.

49:46  49:48What are we gonna do?

49:48  49:51Well, let's look at what RSA keys actually are.

49:51  49:54I introduced RSA keys and I was, like,

49:54  49:57it's a d and d has like a thosand of bits.

49:57  50:01And if we don't know p and q

50:01  50:03how are we gonna get this d?

50:03  50:08Here is the storage format for an RSA key.

50:08  50:11Public key is the modulus N, the public exponent e.

50:11  50:15Ok, private key has version, N, e,

50:15  50:17d the decryption exponent,

50:17  50:20p, q, d mod (p1), d mod (q1),

50:20  50:23the inverse of q mod p,

50:23  50:25this is all useful information if you want to

50:25  50:27speed up your calculation and not have to

50:27  50:29compute everything every time you use your key.

50:29  50:32Okay.

50:32  50:36What did we see here then?

50:36  50:41Here is the key broken up into all of the difference pieces.

50:41  50:45So we have: the red bit is approximately where N is sitting.

50:45  50:47We've got e in orange.

50:47  50:51We've got part of d in yellow.

50:51  50:52We seem to be missing p

50:52  50:55but we've got part of q

50:55  50:57and then here's d mod p1

50:57  51:02and d mod q1 and q inverse mod p.

51:02  51:08There's also a little problem before the red here

51:08  51:08laughter

51:08  51:11in addition.

51:11  51:14You might call this the private part of the private key.

51:14  51:16laughter

51:16  51:21applause

51:21  51:24Fortunately this is just sitting in an encoding of the length

51:24  51:30and the version. laughter

51:30  51:33Alright, so what do we do with this information?

51:33  51:37Basically given any part of this private key

51:37  51:39we can easily compute all of the other parts.

51:39  51:40Simple formulas:

51:40  51:49q will be 2^(e times d mod p1)  1 and GCD that with N

51:49  51:52then we get q and then

51:52  51:54we can figure out what p was by dividing

51:54  51:56and figure out what d is

51:56  51:58and so on and so forth.

51:58  52:02You can do this even if you have a part of a single value

52:02  52:04from the private key.

52:04  52:08You can still compute the rest of the private key from that.

52:08  52:12We don't have time to get into this but it's online.

52:12  52:17You've seen a little bit of math.

52:17  52:18Single formulas, typed into Sage.

52:18  52:23We can reconstruct the private key here.

52:23  52:29applause

52:29  52:33So, what are the lessons that we can learn

52:33  52:36from everything that we've done today.

52:36  52:39The first one is: stop using 1024 bit RSA

52:39  52:41if you haven't already.

52:41  52:43I have looked at the keys that are out there on the Internet

52:43  52:46and you are still using 1024 bit RSA.

52:46  52:48laughter

52:48  52:52Second: make sure your primes are big enough.

52:52  52:54Don't try to be clever about how you're generating them.

52:54  52:58Make sure your primes are random.

52:58  52:59You guys have some problems

52:59  53:01especially in hardware.

53:01  53:04Also...

53:04  53:05laughter

53:05  53:09"FUCK A DUCK" is not good crypto.

53:09  53:12Pastebin is not a secure cloud store.

53:12  53:14laughter

53:14  53:20applause

53:20  53:23And you probably shouldn't put your private key

53:23  53:25in a secure cloud store anyway.

53:25  53:26laughter

53:26  53:31applause

53:31  53:33And lastly...

53:33  53:34laughter

53:34  53:40applause

53:40  53:42Thank you.

53:42  53:44applause

53:44  53:45Angel: Give them an applause.

53:45  54:06applause

54:06  54:11Angel: So questions will be taken at the numbered microphones.

54:11  54:15So anyone who has a question please line up at a microphone

54:15  54:17and we will start by the signal angel

54:17  54:20who has a question from IRC.

54:20  54:24*Signal Angel*: IRC has a lot of punch lines involving penisses

54:24  54:26and some questions.

54:26  54:31First question is: would you recommend more using

54:31  54:38elliptic curves or RSA with multiple primes...

54:38  54:42using proper primes.

54:42  54:47Dan: There are ways to do elliptic curves wrong,

54:47  54:49there are ways to do RSA wrong.

54:49  54:54In general if you've got a particular performance requirement

54:54  54:56then elliptic curves are gonna meet that

54:56  54:58with a much higher security level

54:58  55:00than RSA is gonna meet that.

55:00  55:03Of course you can do RSA securely,

55:03  55:05you can do elliptic curves securely

55:05  55:07but if you've got some performance limitation

55:07  55:09as many applications do

55:09  55:13then elliptic curves tend to be a better choice.

55:13  55:14Nadia: I also want to clarify

55:14  55:18the other most commonly used publickey cryptosystem

55:18  55:20is DSA, the Digital Signature Algorithm.

55:20  55:21There's also elliptic curve DSA

55:21  55:23which is probably what you're thinking about

55:23  55:26with elliptic curve cryptography.

55:26  55:31DSA is in my opinion actually much worse

55:31  55:34than RSA in terms of randomness failures.

55:34  55:36In the paper that Dan referenced

55:36  55:39we also talk about randomness failures in DSA

55:39  55:41and it's horrifying.

55:41  55:45If you ever ever screw up randomness in a single signature

55:45  55:48your entire public key is lost.

55:48  55:51Angel: We will take the next question from microphone nr 4

55:51  55:53to the right of the seat.

55:53  55:54Jake: Hey guys.

55:54  55:56Sorry I didn't mention the computing power of Bluffdale.

55:56  56:02That said, when we want to transition from 1024 bit RSA

56:02  56:05to something else, what do you think is a good idea?

56:05  56:10So for example, in Tor we do use 1024 bit RSA for TLS.

56:10  56:13laughter Yeah I know, right?

56:13  56:16So the thing is we're working on changing these things

56:16  56:17but what is...

56:17  56:20I mean Zooko has this 100 year crypto project.

56:20  56:22What is the real thing that we should,

56:22  56:24like if we could switch tomorrow to something,

56:24  56:27what's the useful that we can live with for 5 or 10 years?

56:27  56:29Is 2048 going to be useful?

56:29  56:31Is 4096 where we should go tomorrow?

56:31  56:33Cause there is a tradeoff between

56:33  56:35performance and forward secrecy

56:35  56:38and there are a lot of things to think about.

56:38  56:40Tanja: If you tell me 5 to 10 years

56:40  56:42I would be still comfortable with elliptic curves.

56:42  56:45If you talk 100 years

56:45  56:48and then there's all these worse quantum computers around

56:48  56:51then I would go for something which is worse in performance

56:51  56:53like codebased cryptography

56:53  56:54or for signatures hashing

56:54  56:56but if you'd say in 5 to 10 years

56:56  56:57I'm very comfortable recommending to you

56:57  57:00elliptic curves with 256 bits.

57:00  57:02Jake: Ok, thanks.

57:02  57:05Angel: Signal angel?

57:05  57:07*Signal Angel*: Yeah, another question from IRC.

57:07  57:11If you avoid all the easy primes

57:11  57:14does this shrink the search space such that

57:14  57:18it becomes easier to crack the remaining keys?

57:18  57:20Or asked another way:

57:20  57:25can you quantify the ratio of easy primes versus hard primes?

57:25  57:26Dan: Yeah, that's a good question.

57:26  57:29The answer is: yes, it can be quantified

57:29  57:33and once you're up to about to the 1024 bit RSA key level

57:33  57:35then there's very very few weak primes.

57:35  57:37So if you have a random number,

57:37  57:39you just generate a random prime

57:39  57:40then your chance of bumping into something weak

57:40  57:43is so small that you just don't have to worry about it.

57:43  57:45It is one of those much less frequent than

57:45  57:47being hit by a lightning kind of events.

57:47  57:49It is something that have been quantified

57:49  57:52and it is an issue for smaller RSA keys

57:52  57:55back when people were using, say, 512 bit RSA

57:55  57:57then it was actually a noticable issue.

57:57  57:59But once you're at 1024 or above then

57:59  58:01the issue is basically gone.

58:01  58:04It's something where you can and you should

58:04  58:06look at exactly what the chance is of bumping into a weak

58:06  58:09but it's not reallistically something

58:09  58:13you're gonna encounter with 1024 bit RSA.

58:13  58:17Angel: We're gonna take the next question from nr 1.

58:17  58:19Just one notice: we don't have a lot of time left

58:19  58:24so even though there is a talk in one hour

58:24  58:25just ask.

58:25  58:28Male: There is a devastating attack that can break AES,

58:28  58:32SHA2, most probably SHA3 and DES.

58:32  58:34It's called a biclique attack.

58:34  58:36Are you concerned that it might break RSA

58:36  58:37with any key size and even ECC

58:37  58:40and even any publickey crypto?

58:40  58:42Dan: No.

58:42  58:44laughter

58:44  58:47Bicliques are something which are certainly interesting

58:47  58:50and I think about it as a way to speed up brute force

58:50  58:53and it speeds up brute force by a noticable factor,

58:53  58:55often makes attacks, say, twice as fast.

58:55  58:59But with publickey crypto we have attacks which are

58:59  59:01much much faster than brute force to begin with

59:01  59:04so that kind of speedup of brute force won't be competitive

59:04  59:08with things like the number field sieve.

59:08  59:13Angel: Next is from number 3.

59:13  59:17Male: Me not coming from the dark side of mathematics,

59:17  59:21how do I know that my random number generators are fine

59:21  59:24for generating keys?

59:24  59:26laughter

59:26  59:31Nadia: Seed them.

59:31  59:37Basically the things that are out there if you're using

59:37  59:41a standard random number generator like in Linux,

59:41  59:44actually Linux has added patches to the kernel

59:44  59:48to fix some of the problems that we've found.

59:48  59:50If you want to know that you're keys are good:

59:50  59:55if you generate them on a general purpose computer

59:55  59:57after it has been running for a long time

59:57  60:00you're probably fine.

60:00  60:05I would not generate very important or longterm keys

60:05  60:10on lowpower hardware devices where you can't tell...

60:10  60:12laughter

60:12  60:16Male: Thank you.

60:16  60:18Angel: Next question will be taken from number 4.

60:18  60:19Male: Hi.

60:19  60:24It's just a remark, not really a question.

60:24  60:25I work in high performance computing.

60:25  60:27I was at the supercomputing conference

60:27  60:29a couple of weeks ago.

60:29  60:32They're presenting largescale installations

60:32  60:36and dealing with problems of power.

60:36  60:39They want to build petaflops and exaflops systems

60:39  60:42that are in a range of 20 MW.

60:42  60:47So I'm wondering what NSA is doing with 53 megawatts

60:47  60:54in a data center because no storage takes that much capacity.

60:54  60:59I think it's really something we should think about.

60:59  61:03So thanks, nice talk.

61:03  61:05Angel: Next question from...

61:05  61:07does the signal angel have one?

61:07  61:09*Signal angel*: Ok, another question is:

61:09  61:12How big do you estimate the effort to

61:12  61:17exchange keys and certificates involving 1024 bit primes

61:17  61:23let's say worldwide at the moment?

61:23  61:25Dan: I wasn't getting what the question was.

61:25  61:26Could you repeat the question?

61:26  61:27*Signal angel*: I don't really understand it myself.

61:27  61:29laughter

61:29  61:33Angel: Ok, let's switch to 1.

61:33  61:37Male: My question goes back to the idea

61:37  61:43of how can we know how good the private keys are?

61:43  61:50Is there something like a keygen evaluation tool?

61:50  61:57Or can the quality of a key generator be estimated

61:57  61:59from a sample of keys?

61:59  62:02Like a public tool that you can throw keys on

62:02  62:06and it will tell me a bias of my keygen?

62:06  62:09Nadia: If you go to factorable.net

62:09  62:13my coauthors and I have made a key check tool

62:13  62:15which will tell you if your key is in the

62:15  62:18list of keys that we scraped off the Internet

62:18  62:19that we were able to compromise.

62:19  62:21That's a first check.

62:21  62:24It's not a positive verification that your key is good

62:24  62:27but it will tell you if it is very bad.

62:27  62:29laughter

62:29  62:37If you want to check your generator,

62:37  62:41if you're worried about the factorization problems

62:41  62:43we have fast code on the website in C

62:43  62:46that will do the GCD calculation for you

62:46  62:50if you just dump a gigantic collection of keys at it.

62:50  62:54If you might have other problems like you are

62:54  62:57not sure whether it's factorable like those don't come up

62:57  63:00the experiment that you might want to do is

63:00  63:04sort of restart the process in realistic conditions

63:04  63:06and generate a gigantic quantity of keys

63:06  63:09and just check for repeats.

63:09  63:12The sort of obvious stress testings.

63:12  63:16If you have a device you want to boot it up in realistic conditions

63:16  63:18and then check them

63:18  63:20and this is painstaking work

63:20  63:22but I don't think there's any realistic way

63:22  63:26of doing better than that.

63:26  63:28Or inspect the code, the obvious thing.

63:28  63:31Make sure you're seeding anything.

63:31  63:33Male: Ok, thank you.

63:33  63:36Angel: Next question will be from mic number 4.

63:36  63:37Male: Hi.

63:37  63:41If I got your numbers correctly so you said something like

63:41  63:45it would take 8 million machines a year to factor 1024

63:45  63:49so I was wondering what if I would like to factor like

63:49  63:52800 bits or 900 bits which is,

63:52  63:55as I understand, way easier than 1024

63:55  63:57but was never done publicly.

63:57  64:00So are you saying that would take like a day or something?

64:00  64:03Dan: It depends on the size of cluster you have.

64:03  64:07The RSA 768 factorization a couple of years ago

64:07  64:11used something on the scale of a 1500 computers

64:11  64:14for a year.

64:14  64:16And those were normal kind of computers,

64:16  64:19Desktop kind of computers with, I think, typically 2 cores.

64:19  64:24Nowadays, if you have some faster, say, 3 GHz 4core machines,

64:24  64:27I think those were typically 2 GHZ 2core, nowadays...

64:27  64:31Tanja's mentioning you of course want to use GPUs

64:31  64:32to speed things up.

64:32  64:33And there's many ways to take advantage of

64:33  64:35computer technology moving forward.

64:35  64:40To get careful estimates: for going from 768 to 800,

64:40  64:42that's a short enough extrapolation

64:42  64:44that people are pretty confident about that.

64:44  64:48Getting to 900 starts getting iffy what exactly the cost would be

64:48  64:51and 1024 there's a fair amount of guess works.

64:51  64:54There is some consensus on rougly what the costs are

64:54  64:55but it's hard to say exactly.

64:55  64:58But again, to give you a scale of it:

64:58  65:00you were saying like 900 or 800.

65:00  65:03Well, 768 RSA challenge was done

65:03  65:07and that one was 1500 machine years.

65:07  65:09Male: Ok, thank you.

65:09  65:10Angel: We'll take four more questions.

65:10  65:12Signal angel first.

65:12  65:17*Signal angel*: It's a clarification of the question I asked before.

65:17  65:22The actual question is: how big will be the effort

65:22  65:32to upgrade existing keys from 1024 bits to 4K or 8K bits?

65:32  65:36Considering that the keys are currently in use

65:36  65:38how much effort worldwide would it be to

65:38  65:42upgrade all that to something more secure?

65:42  65:44Tanja: I mean, for the private user if you're running

65:44  65:46SSH on the laptop you can just generate a new key.

65:46  65:48Doesn't take you much time.

65:48  65:50You will notice maybe some degradation of performance

65:50  65:52if you're running it on a netbook

65:52  65:55but going to 2048 is not a big deal.

65:55  65:58However, there is a recommendation of the

65:58  66:02US government to stop using 1024 bit RSA as of 2010

66:02  66:05and we still see it everywhere.

66:05  66:08Apparently it is bigger effort than just

66:08  66:11everybody spending 10 minutes on the laptop.

66:11  66:14Dan: Maybe part of the problem is things like

66:14  66:17everybody says "yeah, use 2048 or bigger"

66:17  66:19and there's some financial standard

66:19  66:21which says you can use any key size you want

66:21  66:24up to 1984 bits.

66:24  66:26I have no idea how they came up with this

66:26  66:27but then they run into some other standard

66:27  66:29which says use 2048 and they just can't

66:29  66:33implement it on the smartcards which only support up to 1984.

66:33  66:36Now if you get the standards people talking to each other for several years

66:36  66:39then they agree on using 1984.

66:39  66:42It's just about as good as 2048

66:42  66:45but realistically when you have these conflicts

66:45  66:47in standards then it takes a while to work out.

66:47  66:49And when you have a busy server

66:49  66:51that's trying to do 2048 bit RSA

66:51  66:53it doesn't matter what the standard says

66:53  66:55if you got a ton of load you just can't handle that load

66:55  66:58if you're spending a ton of time on cryptography.

66:58  67:00And that again is where we like elliptic curves

67:00  67:03because they give you for whatever your

67:03  67:05performance constraints are much better security.

67:05  67:07So if you're trying a given security level

67:07  67:10the speed is much better.

67:10  67:13Angel: Next question will be from number 2.

67:13  67:15Female: So you've had two developers stand up

67:15  67:17and ask how to verify whether or not their

67:17  67:20key generation is correct and whether or not their

67:20  67:21random numbers are correct.

67:21  67:24And I think it's great that you give coding recommendations

67:24  67:27like seed rand() but coming from the development

67:27  67:30perspective I like to unit test my code

67:30  67:32and specifically I like to write my unit tests

67:32  67:33before I write my code,

67:33  67:35it's called testdriven development.

67:35  67:38So if I'm going about creating an algorithm to

67:38  67:40encrypt something or whatever

67:40  67:43what are the steps that I need to do

67:43  67:47when I'm writing my unit test?

67:47  67:52Has there been some kind of effort in that way

67:52  67:55like what goes into unit test for determining that

67:55  67:57your random number is correct?

67:57  67:59I mean there's algorithms for determining

67:59  68:01whether your random number generator is

68:01  68:03operating correctly, right?

68:03  68:05Dan: This is something where there is,

68:05  68:08if you look at how the random number generators work,

68:08  68:10there was just a NIST workshop

68:10  68:12and there's some NIST standards

68:12  68:13which are telling you

68:13  68:16here's what to do to test your random number generators.

68:16  68:18So you have a hardware random number generator,

68:18  68:20some postprocessing, and they say

68:20  68:22"ok here's the standard for how to test those pieces"

68:22  68:25Now that's not the same as testing the cryptography

68:25  68:26that's using those pieces

68:26  68:29and it's very helpful if there's a clear separation there.

68:29  68:30So you have your cryptography

68:30  68:33which is doing deterministic stuff

68:33  68:34and says you have to have some randomness coming

68:34  68:38from a totally separate unit where the only job

68:38  68:40of that separate unit is do the randomness properly.

68:40  68:42And then the NIST test will tell you

68:42  68:43what the randomness does

68:43  68:46and then deterministic cryptographic testing

68:46  68:48will tell you that the other pieces are working correctly

68:48  68:50for all sorts of inputs.

68:50  68:54Where it goes wrong is something like the ECDSA standard

68:54  68:55that Nadia was mentioning before

68:55  68:57and that's one that says that

68:57  68:59you don't just deterministically generate a signature

68:59  69:01you make some new randomness every time you generate

69:01  69:04a signature and that's what goes horribly wrong.

69:04  69:06So that's something where we need new standards

69:06  69:08which say instead of doing what ECDSA does

69:08  69:10we have a clear separation between

69:10  69:12the cryptography always does the same thing

69:12  69:15making it testable, and then randomness is centralized

69:15  69:18in one spot which hopefully the NIST standards

69:18  69:20do a good enough job of testing.

69:20  69:24Female: So there's something that says here's what determines...

69:24  69:27I guess what I'm asking is do you know of any algorithms

69:27  69:30that can be used for determining whether something

69:30  69:32is a good random number and whether your random

69:32  69:35number generator is generating things properly?

69:35  69:37Tanja: Well, there are a bunch of tests for.

69:37  69:39There's hardware random number generators

69:39  69:42you can run them through the diehard tests.

69:42  69:45There's certificates by FIPS.

69:45  69:49In general I would recommend implementing all those steps

69:49  69:51but the smartcards that have been mentioned by Dan earlier

69:51  69:53from the Taiwan citizen card

69:53  69:55those are actually FIPScertified.

69:55  69:59So even though, these go through what is the industry standard

69:59  70:01of doing random number generation on smartcards

70:01  70:04which everybody thought was good enough,

70:04  70:05apparently they're not.

70:05  70:06So randomness is a total mess.

70:06  70:09I mean after the paper by Nadia and

70:09  70:10also when the paper by the Lausanne team came out,

70:10  70:13there is no some more movement in finding

70:13  70:14better random number generators.

70:14  70:19At this moment, well, hope for the best.

70:19  70:21laughter

70:21  70:22Implement the standards, yes.

70:22  70:25If you have some source of randomness

70:25  70:28try to stretch it with a stream cipher or something like that.

70:28  70:31Nadia: I want to tell a little story.

70:31  70:33After we published the paper

70:33  70:36I heard some very interesting things from some of the vendors.

70:36  70:39I think one of the things that makes randomness

70:39  70:42and cryptography a difficult problem is that

70:42  70:45this kind of issue is something that

70:45  70:47crosses a lot of the abstraction boundaries

70:47  70:49that you're used to in coding.

70:49  70:51You want to have the clean unit test that you know

70:51  70:52that this piece works, and this piece works,

70:52  70:54and this piece works, and this piece works,

70:54  70:58and you put them all together and it will all work flawlessly.

70:58  71:00Somehow this kind of problem is something that

71:00  71:03happens at the boundaries of each unit test.

71:03  71:05We know that the operating system is like

71:05  71:08"ok I'm getting my proper inputs from the hardware

71:08  71:11and I'm correctly generating my randomness from there"

71:11  71:13and then the application says

71:13  71:15"I'm getting my randomness from the operating system,

71:15  71:16it's good randomness"

71:16  71:20and then the application uses the correct crypto algorithms

71:20  71:22to then do good cryptography.

71:22  71:24And at the very beginning of that stage

71:24  71:28there was something broken and it translated all the way

71:28  71:30through all of these pieces of software

71:30  71:32that were working correctly.

71:32  71:35Testing this holistically was the only way

71:35  71:37to find this kind of error.

71:37  71:41One story that I heard from a vendor was that

71:41  71:44they ran into randomness problems.

71:44  71:46They developed some device.

71:46  71:47It was working perfectly

71:47  71:51and on the assembly line they were being turned on

71:51  71:55and run through the checks.

71:55  71:58You boot it up it checks the integrity

71:58  72:01on the assembly line and it was continuing on.

72:01  72:06If you exactly booted them up at the exact same time

72:06  72:10in the exact same conditions

72:10  72:13then all of the inputs to the random number generator

72:13  72:16would be the same and they would generate the same keys

72:16  72:18and then these keys would be,

72:18  72:20you know, they already generated the keys,

72:20  72:21so they wouldn't generate them again after

72:21  72:25they went to the consumer.

72:25  72:27I don't know how to unit test that

72:27  72:30except take the entire device, turn it on,

72:30  72:33and take multiple of them and make sure the devices

72:33  72:35as they're coming out of the production process

72:35  72:40are working correctly.

72:40  72:41Angel: So we will take 2 more questions.

72:41  72:47One from number 4 first and then number 1 at the last.

72:47  72:48Male: How good, do you think,

72:48  72:53hardwaresupported random number generators are

72:53  72:53after what you've just said?

72:53  72:56I think they're probably not good anymore?

72:56  73:02Dan: Intel has their RdRand instruction in some of the newer chips

73:02  73:05and they say that they've gone through

73:05  73:07a reasonable number of evaluation steps.

73:07  73:09It sounds like they're trying.

73:09  73:12Whether they're successful is a different question.

73:12  73:14Something I don't like about the API is

73:14  73:16RdRand gives you no way to test the pieces.

73:16  73:19You can only test the postprocessed output.

73:19  73:22So nobody else is able to test the actual

73:22  73:24randomness generation part of the hardware.

73:24  73:27You can only get a filtered version of that.

73:27  73:29So Intel and people who are contracted by Intel

73:29  73:31to see what's going on inside

73:31  73:33are the only people who can run these tests.

73:33  73:36It's not open in a way that allows the community

73:36  73:37to see if there's further problems.

73:37  73:39But at least they're trying

73:39  73:41and maybe with enough effort the hardware manufacturers

73:41  73:43will get randomness generation right.

73:43  73:48Of course if you can generate any sort of secret once

73:48  73:50if you have enough of a secret to start with

73:50  73:52then you can use things like AES to

73:52  73:54generate any number of secrets

73:54  73:55and you can put those secrets into

73:55  73:57any number of devices that you want.

73:57  74:00If you use AES in counter mode with

74:00  74:02encrypting 1, encrypting 2, encrypting 3...

74:02  74:05you get totally unpredictable, unrelated outputs

74:05  74:07and then use those, burn those into some hardware.

74:07  74:10But where do you get that initial randomness from?

74:10  74:13Are you going through a trustworthy process there?

74:13  74:16It's a hard problem.

74:16  74:18Angel: Next question from number 1.

74:18  74:20And that's the last question.

74:20  74:21Male: You said something about

74:21  74:25you dropped this groupbased cryptography word.

74:25  74:28Most of the stuff I've encountered under that heading

74:28  74:30kind of sounded like snake oil

74:30  74:33just cause they're using nonabelian groups and stuff.

74:33  74:36Is there anything here that isn't?

74:36  74:38Tanja: Ok, I did not say groupbased crypto.

74:38  74:39Male: Ok.

74:39  74:40Tanja: I said codebased cryptography.

74:40  74:41Male: Sorry, thanks.

74:41  74:43Tanja: So there is a class of cryptosystems

74:43  74:45which are fine against quantum computers.

74:45  74:50For all crypto it's always up to what we know.

74:50  74:52Next day, there could be somebody with a

74:52  74:54polynomialtime factor algorithm and so on.

74:54  74:57Now there's also a group of people doing

74:57  74:59braid group cryptography, doing nonabelian groups,

74:59  75:02most of these systems have been broken.

75:02  75:07If they weren't broken by classical computers

75:07  75:11maybe they would remain secure against quantum computers.

75:11  75:14It's lots of "would"s there.

75:14  75:18Yes, they might have this on their flags as well

75:18  75:21but I wouldn't count this as a secure system.

75:21  75:23Whereas codebased cryptography or latticebased cryptography

75:23  75:26are systems which should be fine.

75:26  75:29Dan: Maybe just a URL if you're interested

75:29  75:32in postquantum cryptography is pqcrypto.org

75:32  75:35and that keeps track of papers on the various types

75:35  75:37of cryptography that should survive for a 100 years

75:37  75:41and in particular against quantum computers.

75:41  75:42Angel: Ladies and gentleman, please give

75:42  75:47Nadia, Tanja and Daniel a big round of applause.

75:47  75:48Thank you so much.

75:48  75:57applause
 Title:
 FactHacks [29c3]
 Description:

FactHacks
RSA factorization in the real worldRSA is the dominant publickey 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 1024bit RSA public key is a product of two secret 512bit 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 512bit 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 1024bit RSA? There are several different reasons that a realworld attacker doesn't have to play by the rules of an academic challenge. Sometimes users have bad randomnumber 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 65megawatt data center in Utah or Tianjin. This talk will assess the realworld threat to RSA1024, 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.
Speaker: djb, Nadia Heninger, Tanja Lange
EventID: 5275
Event: 29th Chaos Communication Congress [29c3] by the Chaos Computer Club [CCC]
Location: Congress Centrum Hamburg (CCH); Am Dammtor; Marseiller Straße; 20355 Hamburg; Germany
Language: english
Begin: 12/28/2012 18:30:00 +01:00
Lizenz: CCbyncsa  Video Language:
 English
 Duration:
 01:16:10
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3]  
mw edited English subtitles for FactHacks [29c3] 