WEBVTT
00:00:08.965 --> 00:00:11.637
Today we have Daniel J. Bernstein,
00:00:11.637 --> 00:00:14.538
Nadia Heninger,
00:00:14.538 --> 00:00:16.889
and Tanja Lange.
00:00:16.889 --> 00:00:20.402
And they will talk about RSA factorization in the real world.
00:00:20.402 --> 00:00:22.289
Talk is called FactHacks.
00:00:22.289 --> 00:00:29.905
applause
00:00:29.905 --> 00:00:31.591
Nadia: Thank you.
00:00:31.591 --> 00:00:37.091
So we're going to start with a crypto lecture in 5 minutes.
00:00:37.091 --> 00:00:40.557
So, just to begin, since we're talking about RSA.
00:00:40.557 --> 00:00:43.678
Here is a picture of RSA for you.
00:00:43.678 --> 00:00:48.605
RSA is the first published public-key cryptosystem.
00:00:48.605 --> 00:00:51.222
So by a public-key cryptosystem, what I mean is
00:00:51.222 --> 00:00:54.169
a cryptosystem that has two keys intead of just having
00:00:54.169 --> 00:00:56.886
one key. You might think "ok you encrypt a message
00:00:56.886 --> 00:00:59.035
to that key and you decrypt a message to that key"
00:00:59.035 --> 00:01:01.402
That is a symmetric cryptosystem.
00:01:01.402 --> 00:01:03.194
A public-key cryptosystem has two keys.
00:01:03.194 --> 00:01:06.042
One is the public key and one is the private key.
00:01:06.042 --> 00:01:07.688
The public key you publish to the world and
00:01:07.688 --> 00:01:09.509
anyone can use that key to encrypt a message,
00:01:09.509 --> 00:01:10.806
especially to you.
00:01:10.806 --> 00:01:14.102
And only you, who have the private key, can decrypt that.
00:01:14.102 --> 00:01:18.739
So the RSA paper was the first published public-key cryptosystem.
00:01:18.739 --> 00:01:20.501
That was in 1977.
00:01:20.501 --> 00:01:22.757
This revolutionized cryptography and enabled
00:01:22.757 --> 00:01:25.542
the development of the Internet.
00:01:25.542 --> 00:01:31.568
So 35 years later RSA is still the most commonly used public-key cryptosystem.
00:01:31.568 --> 00:01:35.870
If you ever use the Internet, you probably use it every day.
00:01:35.870 --> 00:01:42.154
So here is a sample SSL certificate which uses RSA.
00:01:42.154 --> 00:01:45.241
If you use SSH you probably have an SSH key
00:01:45.241 --> 00:01:48.440
which probably is RSA.
00:01:48.440 --> 00:01:51.858
Before I launch into the math
00:01:51.858 --> 00:01:54.676
I want to explain what we're doing here.
00:01:54.676 --> 00:01:56.742
We wanted to, since you guys are hackers,
00:01:56.742 --> 00:01:59.874
you like code instead of formulas
00:01:59.874 --> 00:02:02.784
so we wanted to give you formulas in code.
00:02:02.784 --> 00:02:05.455
So what we're giving you is working Python code for
00:02:05.455 --> 00:02:07.720
all the math that we're going to do.
00:02:07.720 --> 00:02:09.976
And in order to do that we're going to use
00:02:09.976 --> 00:02:12.643
some software you call Sage.
00:02:12.643 --> 00:02:15.970
Sage is free open-source mathematics software.
00:02:15.970 --> 00:02:20.160
It is available at this URL sagemath.org.
00:02:20.160 --> 00:02:22.093
It's based off of Python
00:02:22.093 --> 00:02:24.190
so it's very simple if you know Python.
00:02:24.190 --> 00:02:27.904
It has a nice sort of interpreter
00:02:27.904 --> 00:02:29.622
that you can use just like Python.
00:02:29.622 --> 00:02:32.493
Here an example, 2*3=6.
00:02:32.493 --> 00:02:34.890
But there are some differences.
00:02:34.890 --> 00:02:38.202
For example the caret instead of in Python it's XOR
00:02:38.202 --> 00:02:40.155
in Sage it's exponentiation.
00:02:40.155 --> 00:02:43.869
So 2^3 is 8 in Sage.
00:02:43.869 --> 00:02:47.351
The other nice thing about Sage is that
00:02:47.351 --> 00:02:49.703
it has lots of useful mathematical libraries.
00:02:49.703 --> 00:02:53.029
For example if I, in the Sage interpreter, say factor(15)
00:02:53.029 --> 00:02:55.512
it helpfully tells me 3*5.
00:02:55.512 --> 00:02:56.513
That's pretty great.
00:02:56.513 --> 00:02:59.152
It also does a lot more advanced things, for example
00:02:59.152 --> 00:03:00.467
it can represent polynomials.
00:03:00.467 --> 00:03:03.498
I can say factor the polynomial x^2-1
00:03:03.498 --> 00:03:08.127
and it helpfully tells me the answer to that.
00:03:08.127 --> 00:03:12.819
So now that we've gone through what is Sage,
00:03:12.819 --> 00:03:17.443
I want to explain how to do RSA.
00:03:17.443 --> 00:03:21.065
Perhaps some of you have seen this before.
00:03:21.065 --> 00:03:24.677
In order to generate an RSA key, the first thing that you do
00:03:24.677 --> 00:03:27.435
is you generate two large random primes.
00:03:27.435 --> 00:03:30.441
So if we want a 1024 bit RSA key
00:03:30.441 --> 00:03:34.779
we generate two primes of size 2^512,
00:03:34.779 --> 00:03:38.515
so 512 bit primes, p and q.
00:03:38.515 --> 00:03:41.697
In order to generate the public key
00:03:41.697 --> 00:03:44.900
I multiply together p and q and you get some N.
00:03:44.900 --> 00:03:46.433
N has 1024 bits.
00:03:46.433 --> 00:03:49.915
And then you have what's known as the public exponent
00:03:49.915 --> 00:03:54.435
which you can choose 3 or 65537 or 35.
00:03:54.435 --> 00:03:56.300
It really doesn't matter what you choose.
00:03:56.300 --> 00:03:59.117
These are some of the most commonly used values.
00:03:59.117 --> 00:04:03.129
Now in order to generate a private key
00:04:03.129 --> 00:04:07.695
you choose d, the decryption exponent,
00:04:07.695 --> 00:04:12.936
to be the modular inverse of e mod (p-1)*(q-1)
00:04:12.936 --> 00:04:15.394
It doesn't matter why so much, for this talk
00:04:15.394 --> 00:04:17.276
but here is the formula
00:04:17.276 --> 00:04:20.295
or here is the command to do this in Sage.
00:04:20.295 --> 00:04:23.150
So now we have a public key and a private key
00:04:23.150 --> 00:04:24.508
that are pairs.
00:04:24.508 --> 00:04:27.948
And in RSA if you want to enrypt a message
00:04:27.948 --> 00:04:31.547
you raise your message to the e'th power mod n
00:04:31.547 --> 00:04:34.753
so you can do that with your public key here.
00:04:34.753 --> 00:04:36.776
And similarly decryption,
00:04:36.776 --> 00:04:39.998
you raise the ciphertext to the d'th power mod n
00:04:39.998 --> 00:04:42.835
and that will give you the message back out again.
00:04:42.835 --> 00:04:45.748
Fairly simple.
00:04:45.748 --> 00:04:48.731
Now I'm lying to you slightly.
00:04:48.731 --> 00:04:51.088
If you read this talk do not
00:04:51.088 --> 00:04:53.181
absolutely do not implement RSA this way.
00:04:53.181 --> 00:04:54.757
You must pad your message.
00:04:54.757 --> 00:04:57.186
This is a public service warning.
00:04:57.186 --> 00:05:00.662
We offered to tell you about factoring.
00:05:00.662 --> 00:05:03.941
What is the relationship between RSA and factoring?
00:05:03.941 --> 00:05:08.972
Now you can see easily from the formula
00:05:08.972 --> 00:05:11.760
from the private key here
00:05:11.760 --> 00:05:16.337
that if you know how to factor N into its prime factors p and q
00:05:16.337 --> 00:05:19.496
then you can just compute d, the decryption exponent
00:05:19.496 --> 00:05:20.812
of your private key.
00:05:20.812 --> 00:05:24.395
Clearly, if you can factor N you can compute the private key.
00:05:24.395 --> 00:05:28.930
But we don't actually know that factoring is the only way to break RSA.
00:05:28.930 --> 00:05:34.163
There might be some way that you can compute messages from ciphertexts
00:05:34.163 --> 00:05:36.877
that doesn't actually reveal the private key.
00:05:36.877 --> 00:05:41.545
And there's no proof either way that this is or is not possible.
00:05:41.545 --> 00:05:43.478
The last thing that I want to mention here
00:05:43.478 --> 00:05:45.458
just to clarify things
00:05:45.458 --> 00:05:46.830
some of you who might have taken
00:05:46.830 --> 00:05:51.527
complexity or algorithms courses or a beginning CS course
00:05:51.527 --> 00:05:55.874
you might have heard of NP-hardness, the P vs. NP problem.
00:05:55.874 --> 00:06:00.904
And I just want to clarify that factoring is not known to be NP-hard.
00:06:00.904 --> 00:06:05.092
Every computer scientist will love it if we could actually generate
00:06:05.092 --> 00:06:11.139
a cryptosystem which is known to be based of average case NP-hardness.
00:06:11.139 --> 00:06:13.573
We don't know how to do that.
00:06:13.573 --> 00:06:16.992
RSA is not doing that.
00:06:16.992 --> 00:06:22.309
In addition the factoring problem is probably not NP-hard.
00:06:22.309 --> 00:06:25.892
The question is: how hard is factoring?
00:06:25.892 --> 00:06:27.474
Since factoring is the best way that we know
00:06:27.474 --> 00:06:31.227
to break the most commonly used public-key cryptosystem on the Internet.
00:06:31.227 --> 00:06:32.935
Well I showed you some examples before
00:06:32.935 --> 00:06:37.243
where Sage had this helpful little factor function.
00:06:37.243 --> 00:06:39.164
So how well does it work?
00:06:39.164 --> 00:06:41.181
How long do people think this takes?
00:06:41.181 --> 00:06:46.149
two 32 bit integers multiplied together.
00:06:46.149 --> 00:06:48.850
I heard it'll go a couple of seconds.
00:06:48.850 --> 00:06:50.098
0.01 seconds.
00:06:50.098 --> 00:06:55.108
This is on this computer.
00:06:55.108 --> 00:06:57.869
How about 64 bit integers, two of them multiplied together?
00:06:57.869 --> 00:07:01.289
So this is a 128 bit RSA modulus.
00:07:01.289 --> 00:07:04.382
Any guesses?
00:07:04.382 --> 00:07:05.464
One minute?
00:07:05.464 --> 00:07:08.235
Nope, 0.1 seconds.
00:07:08.235 --> 00:07:14.521
How about two 96 bit integers multiplied together?
00:07:14.521 --> 00:07:15.939
A couple of minutes?
00:07:15.939 --> 00:07:18.105
4 seconds.
00:07:18.105 --> 00:07:21.965
How about two 128 bit integers multiplied together?
00:07:21.965 --> 00:07:28.255
This is a 256 bit RSA modulus.
00:07:28.255 --> 00:07:29.300
No guesses? Alright.
00:07:29.300 --> 00:07:30.430
500 seconds.
00:07:30.430 --> 00:07:32.791
So at this point it's starting to get a little bit iffy if I'm
00:07:32.791 --> 00:07:36.327
sitting on a plane trying to do this on battery power.
00:07:36.327 --> 00:07:39.248
laughter
00:07:39.248 --> 00:07:43.764
Clearly this is growing faster than linear in the size of the key.
00:07:43.764 --> 00:07:45.597
So what is actually going on?
00:07:45.597 --> 00:07:49.066
Well.
00:07:49.066 --> 00:07:50.734
Dan: Ok.
00:07:50.734 --> 00:07:52.794
Turns out these factoring functions
00:07:52.794 --> 00:07:54.597
they do look like they're getting pretty slow but
00:07:54.597 --> 00:07:56.835
wait a minute.
00:07:56.835 --> 00:07:59.814
Do we actually have to use this factor function
00:07:59.814 --> 00:08:00.866
if it's getting really slow?
00:08:00.866 --> 00:08:04.302
Maybe instead of trying to use Sage's factor function
00:08:04.302 --> 00:08:08.710
maybe we could just guess what the prime was.
00:08:08.710 --> 00:08:12.350
Now as an RSA user you might not think that this is a threat
00:08:12.350 --> 00:08:13.928
having somebody guess your prime
00:08:13.928 --> 00:08:17.114
because there is some way to count the number of primes,
00:08:17.114 --> 00:08:18.719
number of 512 bit primes and there's
00:08:18.719 --> 00:08:22.185
more than 2^500 512 bit primes.
00:08:22.185 --> 00:08:24.011
And if your random number generator is giving you
00:08:24.011 --> 00:08:27.097
any of those 512 bit primes with the same chance
00:08:27.097 --> 00:08:30.829
then any particular prime that the attacker guesses
00:08:30.829 --> 00:08:32.845
and just tries dividing n by that,
00:08:32.845 --> 00:08:35.061
see if it's evenly divisable, well
00:08:35.061 --> 00:08:39.417
any particular prime has only a 2^(-500) chance
00:08:39.417 --> 00:08:41.312
of being guessed by the attacker.
00:08:41.312 --> 00:08:43.319
And even if the attacker tries a huge number of times
00:08:43.319 --> 00:08:44.897
he'll never guess your prime
00:08:44.897 --> 00:08:47.621
except what if your random number generator
00:08:47.621 --> 00:08:52.031
is working really really badly and doesn't give you 2^500 different primes?
00:08:52.031 --> 00:08:55.902
What if it only gives you, say, 2^40 different primes?
00:08:55.902 --> 00:08:58.055
And then suddenly the attacker could, well,
00:08:58.055 --> 00:09:01.248
try figuring out what those primes are.
00:09:01.248 --> 00:09:03.237
So here's how the attacker looks at this.
00:09:03.237 --> 00:09:05.819
The attacker says: ok I'm gonna target your public key.
00:09:05.819 --> 00:09:08.884
I'm gonna take your big N which is your secret...
00:09:08.884 --> 00:09:10.912
sorry, public key is big N,
00:09:10.912 --> 00:09:13.666
your secret key p times your secret key q,
00:09:13.666 --> 00:09:14.920
your private p and q.
00:09:14.920 --> 00:09:16.764
He's trying to figure out the p and q, given N.
00:09:16.764 --> 00:09:20.169
So what he does, he takes a bunch of devices that are out there
00:09:20.169 --> 00:09:22.902
and he looks at how they work
00:09:22.902 --> 00:09:25.281
or downloads a bunch of software which generates keys
00:09:25.281 --> 00:09:28.904
and then using that software, using those devices
00:09:28.904 --> 00:09:32.216
he tries generating a bunch of p's and q's for himself
00:09:32.216 --> 00:09:34.516
using whatever the random number generator is
00:09:34.516 --> 00:09:36.932
in that device or in that software.
00:09:36.932 --> 00:09:38.400
And then that's something which
00:09:38.400 --> 00:09:40.682
maybe the random number generator works really badly
00:09:40.682 --> 00:09:42.832
and maybe you're using that device, too.
00:09:42.832 --> 00:09:45.765
So the attacker tries each of the primes that he see's
00:09:45.765 --> 00:09:46.918
from this device
00:09:46.918 --> 00:09:50.129
and tries seeing does that prime divide your N.
00:09:50.129 --> 00:09:51.400
If you were using that device
00:09:51.400 --> 00:09:52.932
and it doesn't generate very many primes
00:09:52.932 --> 00:09:55.835
then maybe he gets lucky and finds your prime
00:09:55.835 --> 00:09:57.968
because the device has generated the same prime for him
00:09:57.968 --> 00:09:59.618
that it generated for you.
00:09:59.618 --> 00:10:03.216
Now does anybody actually build devices which
00:10:03.216 --> 00:10:07.005
screw up random numbers this badly?
00:10:07.005 --> 00:10:08.519
laughter
00:10:08.519 --> 00:10:11.538
As a matter of fact, yes, bears do shit in the woods.
00:10:11.538 --> 00:10:13.543
So there are some famous examples.
00:10:13.543 --> 00:10:16.952
We don't have a huge number of historical discussions in this talk
00:10:16.952 --> 00:10:18.539
but just a few examples here.
00:10:18.539 --> 00:10:22.401
Goldberg&Wagner totally broke the original Netscape
00:10:22.401 --> 00:10:23.989
generation of public keys.
00:10:23.989 --> 00:10:26.921
There are only something like 2^47 possible keys
00:10:26.921 --> 00:10:29.216
which is a countable numbers.
00:10:29.216 --> 00:10:31.077
So they could figure out all the possible keys
00:10:31.077 --> 00:10:34.139
that Netscape could generate if they you knew when you generated a key
00:10:34.139 --> 00:10:35.802
which was often very predictable.
00:10:35.802 --> 00:10:37.724
Another example: the Debian bug,
00:10:37.724 --> 00:10:40.974
the horrendous failure for SSH and lots of other applications
00:10:40.974 --> 00:10:42.418
from a few years ago.
00:10:42.418 --> 00:10:45.692
Debian and Ubuntu for a year and half were generating only
00:10:45.692 --> 00:10:48.773
well, fewer than a million possible public keys.
00:10:48.773 --> 00:10:51.421
So complete disasters of random number generation.
00:10:51.421 --> 00:10:53.826
But if you want to add to this list,
00:10:53.826 --> 00:10:55.202
if you want to do more and more of these
00:10:55.202 --> 00:10:56.974
find bad random number generators
00:10:56.974 --> 00:11:00.518
you have to say "ok what's the next device out there
00:11:00.518 --> 00:11:01.858
that might have been screwed up."
00:11:01.858 --> 00:11:03.422
"Let's look at it, look at the code."
00:11:03.422 --> 00:11:05.039
"See what kind of primes it generates."
00:11:05.039 --> 00:11:06.571
"Does it do badly?"
00:11:06.571 --> 00:11:09.424
It takes some real work to figure this out.
00:11:09.424 --> 00:11:11.801
Wouldn't it be nice if there was a systematic way
00:11:11.801 --> 00:11:14.586
to just without having to do a lot of work,
00:11:14.586 --> 00:11:16.576
to look at each device, each piece of software,
00:11:16.576 --> 00:11:18.403
wouldn't it be nice to just figure out
00:11:18.403 --> 00:11:21.568
"oh yeah, let's just magically figure out
00:11:21.568 --> 00:11:23.726
if there's any primes out there generated
00:11:23.726 --> 00:11:25.507
from bad random number generators."
00:11:25.507 --> 00:11:28.020
You could imagine here's the easy attack.
00:11:28.020 --> 00:11:29.622
Here's the systematic way to do this.
00:11:29.622 --> 00:11:34.052
You take two users, so you and you.
00:11:34.052 --> 00:11:35.442
And you each have a public key.
00:11:35.442 --> 00:11:37.178
We're gonna grab those public keys
00:11:37.178 --> 00:11:41.681
N1 and N2
00:11:41.681 --> 00:11:46.983
and then hope that this N1 and N2 share a prime.
00:11:46.983 --> 00:11:54.130
N1 is some prime p times some q1 and N2 is some same prime p times a different q2.
00:11:54.130 --> 00:11:55.663
Now this could happen, you could have
00:11:55.663 --> 00:11:59.100
N1 and N2 sharing both primes.
00:11:59.100 --> 00:12:02.101
That would be legitimate that two people who are actually
00:12:02.101 --> 00:12:05.645
the same webserver sharing their keys, sharing their certificates,
00:12:05.645 --> 00:12:06.843
they know they're doing this,
00:12:06.843 --> 00:12:09.281
you can get the same public key from two places.
00:12:09.281 --> 00:12:12.183
Google has their keys copied to tens of thousands of servers,
00:12:12.183 --> 00:12:13.399
that's not a surprise.
00:12:13.399 --> 00:12:15.395
But if there's a different...
00:12:15.395 --> 00:12:16.999
If you have two different public keys
00:12:16.999 --> 00:12:18.430
they shouldn't be sharing primes.
00:12:18.430 --> 00:12:19.582
What if they do?
00:12:19.582 --> 00:12:21.979
Well, here's this magic Euclid's algorithm
00:12:21.979 --> 00:12:24.744
which will just print out the shared prime p.
00:12:24.744 --> 00:12:26.066
This is a very simple algorithm.
00:12:26.066 --> 00:12:28.495
It just takes one of the numbers, say N1
00:12:28.495 --> 00:12:31.961
and let's say N1 is the smaller one and N2 is the bigger one,
00:12:31.961 --> 00:12:34.142
it divides N2 by N1
00:12:34.142 --> 00:12:37.512
and replaces N2 by the remainder and then switches the numbers
00:12:37.512 --> 00:12:39.593
and that's exactly what this code does.
00:12:39.593 --> 00:12:43.111
The N2 % N1 that's again the N2 mod N1
00:12:43.111 --> 00:12:45.543
the least remainder when you divide N2 by N1.
00:12:45.543 --> 00:12:49.414
And then the result once one of the numbers gets down to zero
00:12:49.414 --> 00:12:52.292
the other number is exactly the shared prime.
00:12:52.292 --> 00:12:54.149
So this amazing algorithm,
00:12:54.149 --> 00:12:57.051
here's just a little manual example
00:12:57.051 --> 00:12:59.898
not with big 512, 1024 bit keys
00:12:59.898 --> 00:13:04.143
this is with just tiny little I guess 8 bit primes
00:13:04.143 --> 00:13:07.625
16 bit... well looks more like 13 bit keys.
00:13:07.625 --> 00:13:12.375
So two numbers coming in and one is 4187 and two is 5989.
00:13:12.375 --> 00:13:14.879
You can see if you keep dividing one number by the other,
00:13:14.879 --> 00:13:16.162
replacing it by the remainder,
00:13:16.162 --> 00:13:19.411
do that a few times, you quickly get down to zero.
00:13:19.411 --> 00:13:22.774
And the number right before the zero in the middle of the slide is 53.
00:13:22.774 --> 00:13:27.172
Now 53 is a shared prime between these two small keys.
00:13:27.172 --> 00:13:28.772
If you scale this up,
00:13:28.772 --> 00:13:32.256
if you do this computation for bigger numbers
00:13:32.256 --> 00:13:34.176
then here's another timing example.
00:13:34.176 --> 00:13:36.673
It's still really really fast, in the middle of the slide.
00:13:36.673 --> 00:13:40.359
This is doing 1024 bit keys that share a 512 bit prime.
00:13:40.359 --> 00:13:44.554
You can figure out this 512 bit prime so quickly that the timing
00:13:44.554 --> 00:13:48.848
there is 0.00 seconds, can't even see how fast it is.
00:13:48.848 --> 00:13:51.094
Ok, so that's Euclid's algorithm.
00:13:51.094 --> 00:13:53.676
Now you can actually do this for tons and tons of keys.
00:13:53.676 --> 00:13:57.695
You download, say, millions, tens of millions of keys from the Internet,
00:13:57.695 --> 00:14:01.011
all the different SSL servers, maybe go for some SSH keys,
00:14:01.011 --> 00:14:03.891
you download tons and tons of public keys and then
00:14:03.891 --> 00:14:06.590
you try all the pairs with Euclid's algorithm.
00:14:06.590 --> 00:14:09.406
And it's so fast that you can do this but actually
00:14:09.406 --> 00:14:10.848
you can do better.
00:14:10.848 --> 00:14:13.927
So there's an algorithm: batch GCD algorithm
00:14:13.927 --> 00:14:15.396
which takes a whole bunch of keys
00:14:15.396 --> 00:14:19.822
and figures out which of those keys share primes with the others.
00:14:19.822 --> 00:14:22.525
Much much faster than trying every pair.
00:14:22.525 --> 00:14:23.909
So you don't have to try every pair.
00:14:23.909 --> 00:14:26.973
It's kind of like sorting, it's about that kind of speed
00:14:26.973 --> 00:14:29.065
instead of having to try every pair.
00:14:29.065 --> 00:14:30.811
If you have tens of millions you don't have to do
00:14:30.811 --> 00:14:33.156
tens of millions times tens of millions of pairs.
00:14:33.156 --> 00:14:35.739
You just have to pretty much reap through the whole list once.
00:14:35.739 --> 00:14:38.877
So what does this batch GCD algorithm do?
00:14:38.877 --> 00:14:41.447
It's figuring out for the first N1,
00:14:41.447 --> 00:14:44.029
instead of computing the greatest common divisor,
00:14:44.029 --> 00:14:45.908
the Euclid result for N1 and N2
00:14:45.908 --> 00:14:47.846
and for N1 and N3 and so on,
00:14:47.846 --> 00:14:52.340
it figures out the product of N2, N3, N4 and so on,
00:14:52.340 --> 00:14:55.257
takes the greatest common divisor of that with N1,
00:14:55.257 --> 00:14:57.191
applies Euclid's algorithm to that
00:14:57.191 --> 00:15:00.874
and then does a similar thing for N2 and for N3 and so on.
00:15:00.874 --> 00:15:05.656
Each of those is gonna show you whether N1 or N2 or N3,
00:15:05.656 --> 00:15:08.148
it's gonna show you whether they share some prime
00:15:08.148 --> 00:15:10.246
with any of the other N's.
00:15:10.246 --> 00:15:13.326
If you did exactly the computation
00:15:13.326 --> 00:15:15.248
shown on the slide in the math formulas
00:15:15.248 --> 00:15:16.617
it would still be too slow.
00:15:16.617 --> 00:15:20.457
But the batch GCD algorithm finds redundancies
00:15:20.457 --> 00:15:23.218
in these GCDs, and here's exactly what it does:
00:15:23.218 --> 00:15:25.620
It figures out the product of all of the keys.
00:15:25.620 --> 00:15:29.923
So you take, say, a million keys and you multiply them all together.
00:15:29.923 --> 00:15:33.534
And that's done with the code here where you do...
00:15:33.534 --> 00:15:35.120
maybe I'll just skip to the bottom.
00:15:35.120 --> 00:15:37.474
You see numbers 10, 20, 30, 40.
00:15:37.474 --> 00:15:39.356
You build a product tree.
00:15:39.356 --> 00:15:42.210
So you take 10 times 20, compute 200.
00:15:42.210 --> 00:15:44.687
Take the next pair 30 times 40, compute 1200.
00:15:44.687 --> 00:15:47.889
The take the pair of products 200 times 1200.
00:15:47.889 --> 00:15:50.378
If you have more numbers, you have more levels in the tree.
00:15:50.378 --> 00:15:55.227
And that's exactly what the Sage code does here.
00:15:55.227 --> 00:15:58.924
And then the last step of the algorithm is
00:15:58.924 --> 00:16:02.847
kind of going down the tree, building a remainder tree.
00:16:02.847 --> 00:16:06.515
So what's happening here to figure out the greatest common divisor
00:16:06.515 --> 00:16:10.013
of N1 with the product of all the other keys,
00:16:10.013 --> 00:16:12.846
the idea is to take this product
00:16:12.846 --> 00:16:15.807
which is called big R on this slide,
00:16:15.807 --> 00:16:23.160
take the product of all the keys and then divide that by N1^2
00:16:23.160 --> 00:16:26.291
and then take the remainders, so R mod N1^2,
00:16:26.291 --> 00:16:31.148
divide by N1 and then compute the greatest common divisor of N1 mod N.
00:16:31.148 --> 00:16:33.124
And the amazing effect is that it's exactly the
00:16:33.124 --> 00:16:35.047
greatest common divisor we were looking for.
00:16:35.047 --> 00:16:37.629
And what this little Sage script does is that it takes
00:16:37.629 --> 00:16:42.282
R and divides R by, well a bunch of N's in a really fast way,
00:16:42.282 --> 00:16:43.960
and then at the bottom, once it has figured out
00:16:43.960 --> 00:16:47.227
all mod N1^2, all mod N2^2 and so on,
00:16:47.227 --> 00:16:49.308
divides those by N1 and N2,
00:16:49.308 --> 00:16:52.177
takes the greatest common divisor with N1 and N2
00:16:52.177 --> 00:16:54.824
and that's exactly telling you, the outputs here
00:16:54.824 --> 00:16:57.063
that are different from 1, are exactly telling you
00:16:57.063 --> 00:17:00.398
which N's share a prime with some others.
00:17:00.398 --> 00:17:04.048
This very remarkably short little script does work quite well.
00:17:04.048 --> 00:17:06.524
Here's how fast these are.
00:17:06.524 --> 00:17:10.248
So I'm on some 800 MHz core.
00:17:10.248 --> 00:17:13.442
If you try this for, say, a hundred numbers,
00:17:13.442 --> 00:17:16.608
just hundred random 1024 bit numbers,
00:17:16.608 --> 00:17:20.917
it doesn't matter what the numbers are, they always run at the same speed,
00:17:20.917 --> 00:17:23.198
then that takes 0.05 seconds.
00:17:23.198 --> 00:17:27.249
If you have 10 times as many numbers it takes about 20 times as long.
00:17:27.249 --> 00:17:31.229
And if you have another 10 times as many numbers it takes about 20 times as long.
00:17:31.229 --> 00:17:33.247
And it keeps scaling up like that.
00:17:33.247 --> 00:17:35.948
So you can get to millions or tens of millions of numbers
00:17:35.948 --> 00:17:38.582
and it still finishes in a reasonable amount of time.
00:17:38.582 --> 00:17:40.068
So, amazingly fast algorithm.
00:17:40.068 --> 00:17:43.810
You don't have to scale this up to like 2^50 or 2^100 keys.
00:17:43.810 --> 00:17:46.059
There's only, say, tens of millions of keys out there
00:17:46.059 --> 00:17:48.330
and this runs reasonably fast.
00:17:48.330 --> 00:17:50.626
Ok.
00:17:50.626 --> 00:17:52.416
Can you actually hope for this to work?
00:17:52.416 --> 00:17:54.629
Are random number generators really this bad?
00:17:54.629 --> 00:17:55.866
Well...
00:17:55.866 --> 00:18:00.478
laughs
00:18:00.478 --> 00:18:03.435
There's a 2012 paper from Heninger
00:18:03.435 --> 00:18:04.926
that's the same Heninger we have sitting here
00:18:04.926 --> 00:18:06.300
and Durumeric, Wustrow, Halderman,
00:18:06.300 --> 00:18:09.881
that's got the best paper award at USENIX Security 2012.
00:18:09.881 --> 00:18:14.678
What they did was they tried exactly this on tens of millions of keys out there
00:18:14.678 --> 00:18:18.276
and factored tens of thousands of keys.
00:18:18.276 --> 00:18:22.677
Admittely they used a C version of this instead of this
00:18:22.677 --> 00:18:24.061
Sage script but
00:18:24.061 --> 00:18:25.827
the Sage script will go up to millions.
00:18:25.827 --> 00:18:28.359
It's just when you get beyond that you want to write it in C
00:18:28.359 --> 00:18:31.009
to deal with using a lot of memory.
00:18:31.009 --> 00:18:34.887
But you can use exactly this script for pretty large chunks of keys.
00:18:34.887 --> 00:18:37.951
And so they factored tens of thousands of keys and said
00:18:37.951 --> 00:18:42.235
that these keys are typically not your bank keys.
00:18:42.235 --> 00:18:44.909
They gonna be, say, keys for your home router.
00:18:44.909 --> 00:18:47.639
So the vulnerable devices are not gonna be,
00:18:47.639 --> 00:18:49.893
say, a big server out there.
00:18:49.893 --> 00:18:53.902
The vulnerable devices will be your FRITZ!Box.
00:18:53.902 --> 00:18:57.340
applause
00:18:57.340 --> 00:18:59.838
Thank you, Nadia.
00:18:59.838 --> 00:19:06.525
It's good to read the paper, go to factorable.net
00:19:06.525 --> 00:19:09.073
and you get tons of analyses of why this happened
00:19:09.073 --> 00:19:12.520
and why these devices are generated guessable numbers.
00:19:12.520 --> 00:19:15.020
I mean numbers that are so non-random that they get
00:19:15.020 --> 00:19:18.370
repeated between a lot of keys out there.
00:19:18.370 --> 00:19:20.308
There was at the same time another team that
00:19:20.308 --> 00:19:23.559
like within days announced the same result.
00:19:23.559 --> 00:19:27.071
They independently did the same computation.
00:19:27.071 --> 00:19:28.883
They said "yeah, we've also downloaded
00:19:28.883 --> 00:19:31.352
a bunch of keys and factored as many as we could"
00:19:31.352 --> 00:19:32.869
with basically the same algorithm.
00:19:32.869 --> 00:19:35.198
At the end of it "yeah we factored
00:19:35.198 --> 00:19:36.629
tens of thousands of keys."
00:19:36.629 --> 00:19:38.882
That paper has no analysis.
00:19:38.882 --> 00:19:41.582
They're like "yeah, there's keys"
00:19:41.582 --> 00:19:43.267
"they share primes for some reason"
00:19:43.267 --> 00:19:45.915
"I guess ecommerce is dead"
00:19:45.915 --> 00:19:47.536
"go out, change your bank keys"
00:19:47.536 --> 00:19:48.846
"call the New York Times"
00:19:48.846 --> 00:19:50.553
There's the New York Times article:
00:19:50.553 --> 00:19:52.601
"Flaw Found in an Online Encryption Method"
00:19:52.601 --> 00:19:54.860
I also like the advertising on the side here.
00:19:54.860 --> 00:19:57.151
Like iron key on the top and then:
00:19:57.151 --> 00:20:01.168
"Encrypt, decrypt & access my secret data in real time"
00:20:01.168 --> 00:20:03.135
"try it free for 30 days."
00:20:03.135 --> 00:20:05.199
"I secured my cloud data. Have you?"
00:20:05.199 --> 00:20:06.878
Awesome advertising there.
00:20:06.878 --> 00:20:12.480
Once you found that there's a problem like this
00:20:12.480 --> 00:20:14.919
then of course you start looking around for more and more places
00:20:14.919 --> 00:20:17.435
where you might have some bad randomness.
00:20:17.435 --> 00:20:22.795
For example there is a paper, or at least slides,
00:20:22.795 --> 00:20:25.395
by Chou in Taiwan, saying
00:20:25.395 --> 00:20:31.857
they took two million Taiwan Citizen Digital Certificates
00:20:31.857 --> 00:20:34.327
and did some GCDs
00:20:34.327 --> 00:20:36.626
and found that a 103 of those were
00:20:36.626 --> 00:20:37.995
factorable.
00:20:37.995 --> 00:20:40.052
So anybody who downloaded these certificates
00:20:40.052 --> 00:20:43.177
which apparently are used in Taiwan for like paying your taxes,
00:20:43.177 --> 00:20:44.393
talking to banks I don't know,
00:20:44.393 --> 00:20:46.677
but paying taxes is one that I've checked.
00:20:46.677 --> 00:20:49.537
So a 103 people out there have these Taiwan
00:20:49.537 --> 00:20:51.011
Citizen Digital Certificates where
00:20:51.011 --> 00:20:54.121
you're supposed to have in this database things like
00:20:54.121 --> 00:20:57.122
the names of the people and their ID numbers
00:20:57.122 --> 00:20:59.576
but you aren't supposed to have their secret keys.
00:20:59.576 --> 00:21:01.543
The whole point is those are supposed to be private
00:21:01.543 --> 00:21:03.938
kept on some smartcards that are issued to the citizens
00:21:03.938 --> 00:21:05.295
in Taiwan.
00:21:05.295 --> 00:21:08.706
And the randomness generation is so bad that
00:21:08.706 --> 00:21:13.169
103 of those keys have now been factored.
00:21:13.169 --> 00:21:15.451
The smartcard manufacturer, I also like this quote,
00:21:15.451 --> 00:21:18.674
it's a company based in Munich called
00:21:18.674 --> 00:21:22.315
Giesecke & Devrient and their motto is:
00:21:22.315 --> 00:21:24.753
"Creating Confidence"
00:21:24.753 --> 00:21:35.270
applause
00:21:35.270 --> 00:21:37.698
Tanja: There's gonna be more of Dan, don't worry.
00:21:37.698 --> 00:21:39.835
But we promised a bit more than just factoring
00:21:39.835 --> 00:21:43.309
bad keys or the keys with their primes.
00:21:43.309 --> 00:21:46.956
If you find another number like this one.
00:21:46.956 --> 00:21:49.686
So here's coming some more of math stuff.
00:21:49.686 --> 00:21:52.555
So if you see a number like this and you
00:21:52.555 --> 00:21:56.427
observe this last digit, then yes.
00:21:56.427 --> 00:21:58.738
It's very easy for you to see it's divisable by 5.
00:21:58.738 --> 00:22:01.385
So if you find such a key that is easy to break
00:22:01.385 --> 00:22:03.226
and you are a computer rather than a human being
00:22:03.226 --> 00:22:05.324
you look at lots of those numbers.
00:22:05.324 --> 00:22:07.076
You have a list of small primes stored
00:22:07.076 --> 00:22:10.037
and what you're gonna do is just trial division.
00:22:10.037 --> 00:22:11.987
So if there's any small factor
00:22:11.987 --> 00:22:14.092
it's very easy to find this trial division.
00:22:14.092 --> 00:22:16.708
Or what Dan showed was the remainder trees.
00:22:16.708 --> 00:22:20.222
You can also do this for batch trial division.
00:22:20.222 --> 00:22:23.728
So assuming that you're looking for a prime p somewhere
00:22:23.728 --> 00:22:26.735
then you go linearly all the way up to the p
00:22:26.735 --> 00:22:30.442
and there are about p/log(p) many primes
00:22:30.442 --> 00:22:32.094
before you find this p.
00:22:32.094 --> 00:22:33.969
For each of them you just do exact division.
00:22:33.969 --> 00:22:36.558
If it works, fine you found a factor, otherwise not.
00:22:36.558 --> 00:22:39.459
Now this is not going to work against your normal keys.
00:22:39.459 --> 00:22:43.624
I know that in the example that Dan mentioned by Wagner&Goldberg
00:22:43.624 --> 00:22:46.625
that they found one factor which had a 9 in there
00:22:46.625 --> 00:22:49.975
but usually your keys don't have a 9.
00:22:49.975 --> 00:22:54.687
For slightly larger numbers there is a method due to Pollard.
00:22:54.687 --> 00:22:57.460
So if you see the respectful number here,
00:22:57.460 --> 00:22:59.887
there is no obvious divisability of this one.
00:22:59.887 --> 00:23:03.091
One thing you can try is
00:23:03.091 --> 00:23:06.660
a walk, well we call this a walk.
00:23:06.660 --> 00:23:10.404
You start with some random number smaller than N
00:23:10.404 --> 00:23:12.902
and some offset here.
00:23:12.902 --> 00:23:17.277
I should also say, all those scripts are available at this URL.
00:23:17.277 --> 00:23:22.087
So if you go to facthacks.cr.yp.to then you'll find all the scripts
00:23:22.087 --> 00:23:23.879
if you want to play with it at the same time,
00:23:23.879 --> 00:23:26.625
including this one with some explanations and such.
00:23:26.625 --> 00:23:31.092
So what you do is you start off two different numbers,
00:23:31.092 --> 00:23:34.788
one at each step squares it and adds c.
00:23:34.788 --> 00:23:37.226
And the other one squares it, adds c,
00:23:37.226 --> 00:23:39.886
and squares it again and adds the c.
00:23:39.886 --> 00:23:41.455
Each time computing mod N.
00:23:41.455 --> 00:23:44.102
So you have two sequences running around,
00:23:44.102 --> 00:23:46.023
one is twice the speed as the other.
00:23:46.023 --> 00:23:50.953
At every step you check with the GCD of this number N
00:23:50.953 --> 00:23:52.757
and the difference between the two walks
00:23:52.757 --> 00:23:55.006
hasn't anything interesting now.
00:23:55.006 --> 00:23:57.390
N is an RSA modulus, the only thing interesting
00:23:57.390 --> 00:23:59.675
could either be p or q.
00:23:59.675 --> 00:24:03.009
So for this particular number
00:24:03.009 --> 00:24:04.270
when I run this
00:24:04.270 --> 00:24:08.894
I find 2053 after a few milliseconds.
00:24:08.894 --> 00:24:10.642
So this is again a cooked up example.
00:24:10.642 --> 00:24:13.307
You won't find such a small factor if you're trying
00:24:13.307 --> 00:24:16.173
a general RSA factor, otherwise your numbers
00:24:16.173 --> 00:24:17.830
would be totally busted but
00:24:17.830 --> 00:24:20.604
this shows if you have a small number in there
00:24:20.604 --> 00:24:21.857
it's very easy to find.
00:24:21.857 --> 00:24:24.357
All later on when Dan is talking about the number field sieve
00:24:24.357 --> 00:24:26.157
this is an interesting subroutine.
00:24:26.157 --> 00:24:28.089
So if you ever need to find small numbers
00:24:28.089 --> 00:24:31.020
then, sure trial division is very easy for
00:24:31.020 --> 00:24:34.080
really small numbers taking this long,
00:24:34.080 --> 00:24:38.352
this one squared with p is much faster already.
00:24:38.352 --> 00:24:42.070
Now even faster than that, also due to Pollard,
00:24:42.070 --> 00:24:45.378
called Pollard's p-1 method.
00:24:45.378 --> 00:24:47.904
Here is again an innocent looking number N.
00:24:47.904 --> 00:24:49.842
You see the numbers get larger.
00:24:49.842 --> 00:24:52.176
This is a 256 bit number.
00:24:52.176 --> 00:24:56.744
In order to deal with such a number there is one step
00:24:56.744 --> 00:24:59.342
which is expensive but you would do it only once
00:24:59.342 --> 00:25:01.208
for all different numbers you want to try,
00:25:01.208 --> 00:25:05.238
namely compute a big integer which has lots of little factors.
00:25:05.238 --> 00:25:06.985
So you take the least common multiple
00:25:06.985 --> 00:25:09.788
from 1, 2, 3, 4, 5...
00:25:09.788 --> 00:25:12.203
Ok, once you hit the 4 you have another 2 in there.
00:25:12.203 --> 00:25:13.808
So there's lots and lots of powers of 2,
00:25:13.808 --> 00:25:15.408
lots and lots of powers of 3.
00:25:15.408 --> 00:25:19.390
And then the larger primes only appear like once.
00:25:19.390 --> 00:25:23.161
But you're not going up to 256 or 128 anywhere.
00:25:23.161 --> 00:25:27.005
You're sticking here at 22 bits
00:25:27.005 --> 00:25:29.059
and then use the same function that Nadia explained
00:25:31.023 --> 00:25:32.987
in the RSA computation, namely the modular exponentiation.
00:25:32.987 --> 00:25:36.576
So you take the 2^y,
00:25:36.576 --> 00:25:38.241
this huge number,
00:25:38.241 --> 00:25:40.486
but the whole computation mod N.
00:25:40.486 --> 00:25:44.633
So this whole thing never grows beyond this 256 bit number.
00:25:44.633 --> 00:25:47.939
Or for a real world example it would be a 1000 bit number.
00:25:47.939 --> 00:25:52.518
And then you compute the GCD of this number and N.
00:25:52.518 --> 00:25:55.091
For this particular one, again it's a cooked up example,
00:25:55.091 --> 00:25:56.390
you get a factor.
00:25:56.390 --> 00:25:59.791
Now this factor is actually 120 bits.
00:25:59.791 --> 00:26:02.369
This is not a small factor.
00:26:02.369 --> 00:26:05.688
So if you were using 256 bit numbers
00:26:05.688 --> 00:26:07.856
this is something that could happen to you
00:26:07.856 --> 00:26:11.305
and nevertheless this method would find it.
00:26:11.305 --> 00:26:13.522
So this finds much larger factors than trial division
00:26:13.522 --> 00:26:15.484
or the Rho method in the same amount of time.
00:26:15.484 --> 00:26:17.376
But it doesn't work for all primes.
00:26:17.376 --> 00:26:20.066
It works for primes which are kind of special.
00:26:20.066 --> 00:26:23.859
Now what's special about this prime or the other factor?
00:26:23.859 --> 00:26:29.553
If you take p and subtract -1, hence the name p-1 method,
00:26:29.553 --> 00:26:31.660
and factor that thing,
00:26:31.660 --> 00:26:35.272
that has lots, lots of small numbers.
00:26:35.272 --> 00:26:36.937
So that's something we call smooth.
00:26:36.937 --> 00:26:40.342
So a smooth number doesn't have big factors.
00:26:40.342 --> 00:26:43.868
So a prime is like the least smooth number you can imagine.
00:26:43.868 --> 00:26:47.367
And 2 to the power large is the most smooth number,
00:26:47.367 --> 00:26:50.007
so lots of little factors means smooth.
00:26:50.007 --> 00:26:55.568
This largest factor happens to be 21.7 bits
00:26:55.568 --> 00:26:58.355
which is why I chose the 22 bits here.
00:26:58.355 --> 00:27:03.702
So as soon I run over the largest prime in p-1
00:27:03.702 --> 00:27:06.127
with this exponent y here
00:27:06.127 --> 00:27:08.653
then I do find this factor.
00:27:08.653 --> 00:27:10.851
Now if you thought this was math
00:27:10.851 --> 00:27:12.322
there is even more scary math
00:27:12.322 --> 00:27:15.893
namely there are methods which are generalizing
00:27:15.893 --> 00:27:19.319
this p-1 method using elliptic curves.
00:27:19.319 --> 00:27:21.569
If you listen to the crypto advertisement
00:27:21.569 --> 00:27:23.472
elliptic curves are usually something very good,
00:27:23.472 --> 00:27:25.005
something you should have on your smartcard.
00:27:25.005 --> 00:27:27.245
It's faster than RSA and so on.
00:27:27.245 --> 00:27:29.385
That's the same type of elliptic curve
00:27:29.385 --> 00:27:32.342
but here elliptic curves come in as an attack tool.
00:27:32.342 --> 00:27:35.088
There is a method called the elliptic curve method ECM
00:27:35.088 --> 00:27:41.255
which is a generalization of this p-1 method and does not need anything special,
00:27:41.255 --> 00:27:44.708
I mean avoiding such primes is easy.
00:27:44.708 --> 00:27:46.325
If you look into older standards
00:27:46.325 --> 00:27:49.852
they all warn about "make sure to use strong primes"
00:27:49.852 --> 00:27:53.174
"make sure to check that your p-1 is not smooth"
00:27:53.174 --> 00:27:55.301
And of course you don't want your p-1 to be smooth
00:27:55.301 --> 00:27:57.670
because otherwise this attack works.
00:27:57.670 --> 00:28:00.760
But if I have some elliptic curve
00:28:00.760 --> 00:28:03.492
a different type of prime is weak for that curve
00:28:03.492 --> 00:28:06.351
and I have many, many, many elliptic curves.
00:28:06.351 --> 00:28:08.617
For each of the curves some primes are weak.
00:28:08.617 --> 00:28:11.161
You can't exclude this method.
00:28:11.161 --> 00:28:13.573
So the only thing you can do is just, well,
00:28:13.573 --> 00:28:18.035
choose your prime large enough and hope, well,
00:28:18.035 --> 00:28:20.436
make sure p-1 doesn't get it and hope
00:28:20.436 --> 00:28:22.601
that the next elliptic curves won't get it.
00:28:22.601 --> 00:28:24.855
So elliptic curves are good for attacking.
00:28:24.855 --> 00:28:27.624
It's still not the fastest method out there
00:28:27.624 --> 00:28:33.185
but it's a good method for random factoring.
00:28:33.185 --> 00:28:35.917
It's not the best method for finding RSA factors
00:28:35.917 --> 00:28:38.366
but if you have a number which is most likely
00:28:38.366 --> 00:28:44.532
not too non-smooth then it's a good method.
00:28:44.532 --> 00:28:47.234
Now this is what you do for finding small factors.
00:28:47.234 --> 00:28:50.509
To show some method for big factors,
00:28:50.509 --> 00:28:53.994
now here that is a big number.
00:28:53.994 --> 00:28:58.978
But this is what I would call factorization by inspection.
00:28:58.978 --> 00:29:07.876
What's wrong with this number?
00:29:07.876 --> 00:29:10.129
I mean this number is not small and
00:29:10.129 --> 00:29:13.162
it won't have small factors, I promise you this.
00:29:13.162 --> 00:29:19.835
So it's a decimal representation, so 9 is the digit before 0.
00:29:19.835 --> 00:29:23.246
This looks very close to the power of 10.
00:29:23.246 --> 00:29:28.253
Actually this is very close to 10^340.
00:29:28.253 --> 00:29:30.292
If you take the square root of it
00:29:30.292 --> 00:29:34.150
then you almost exactly hit 10^170.
00:29:34.150 --> 00:29:37.113
This example was cooked up as taking two primes
00:29:37.113 --> 00:29:46.646
namely 10^170-33 and 10^170+63 and multiplying them.
00:29:46.646 --> 00:29:48.667
So if you see lots of 0's and lots of 9's
00:29:48.667 --> 00:29:50.934
then you know that you are very close to a certain power.
00:29:50.934 --> 00:29:53.464
Now in real life this wouldn't be a power of 10,
00:29:53.464 --> 00:29:54.817
it would be a power of 2.
00:29:54.817 --> 00:29:56.179
And there actually are some examples.
00:29:56.179 --> 00:29:58.817
There's a famous story of a letter bomber in Austria
00:29:58.817 --> 00:30:02.650
who wanted his message to be crackable
00:30:02.650 --> 00:30:06.047
and he sent a message, well he was some right-wing asshole
00:30:06.047 --> 00:30:08.332
that was letter-bombing people
00:30:08.332 --> 00:30:10.813
and then he sent an encrypted message to the police.
00:30:10.813 --> 00:30:14.642
And the police tried to factor it and tried to decipher it
00:30:14.642 --> 00:30:18.568
hoping it would be the list of the next victims.
00:30:18.568 --> 00:30:20.980
In the end it was not but
00:30:20.980 --> 00:30:24.419
this person was actually using very close to a power of 2
00:30:24.419 --> 00:30:26.211
in order to have people crack it.
00:30:26.211 --> 00:30:27.769
In the end it was just some propaganda,
00:30:27.769 --> 00:30:29.462
some right-wing stuff as well.
00:30:29.462 --> 00:30:32.783
So there are people using this for breakability.
00:30:32.783 --> 00:30:35.499
I'm not aware of people actually using this as an accident.
00:30:35.499 --> 00:30:40.437
But what can happen to you is not using close to the power of 2
00:30:40.437 --> 00:30:46.200
but saying "ok I learned I shouldn't be close to the power of 2
00:30:46.200 --> 00:30:48.848
so I take some offset and take the next prime."
00:30:48.848 --> 00:30:51.130
Next prime just means, add 1, check is it prime,
00:30:51.130 --> 00:30:53.798
add next one, add 2, add 3
00:30:53.798 --> 00:30:57.082
Just check primes linearly from then on.
00:30:57.082 --> 00:30:59.261
Now if we jump to this where we finally find our prime p
00:30:59.261 --> 00:31:00.966
it's a good prime.
00:31:00.966 --> 00:31:03.869
It's not anywhere close to the power of 2 because my c was large enough.
00:31:03.869 --> 00:31:07.130
Made it, good.
00:31:07.130 --> 00:31:08.562
Now on q.
00:31:08.562 --> 00:31:10.776
So again call the next_prime().
00:31:10.776 --> 00:31:14.445
So I do p+1, p+2 until I find a prime.
00:31:14.445 --> 00:31:17.215
That means that if you take the product of the two
00:31:17.215 --> 00:31:19.469
then this N is very close to a square.
00:31:19.469 --> 00:31:22.920
So this N is cooked up with this method.
00:31:22.920 --> 00:31:24.412
You don't see anything on the end,
00:31:24.412 --> 00:31:26.678
there's nothing wrong there.
00:31:26.678 --> 00:31:29.650
But when you compute the square root of it
00:31:29.650 --> 00:31:33.156
it is almost an integer, it's .99999...
00:31:33.156 --> 00:31:35.208
and then some dirt here.
00:31:35.208 --> 00:31:39.288
So then you'll know that your primes were too small.
00:31:39.288 --> 00:31:42.286
Sorry, not too small, too close to each other.
00:31:42.286 --> 00:31:45.483
So if you ever take an RSA factor modulus
00:31:45.483 --> 00:31:46.841
and you compute the square root
00:31:46.841 --> 00:31:47.991
and you see something like this
00:31:47.991 --> 00:31:51.885
then you know: that user did this method.
00:31:51.885 --> 00:31:53.661
You could just say, I take the number,
00:31:53.661 --> 00:31:56.549
subtract 1, subtract 2, just go off from the square root.
00:31:56.549 --> 00:32:02.022
All you can check how far away is it from being a square.
00:32:02.022 --> 00:32:03.701
So you take the seeding,
00:32:03.701 --> 00:32:07.950
that means the closest integer counting upwards.
00:32:07.950 --> 00:32:11.817
Just round it to this two, here's 57, is there a 56?
00:32:11.817 --> 00:32:14.520
Compute the square of that and subtract N.
00:32:14.520 --> 00:32:17.987
Now in this example that is 4096
00:32:17.987 --> 00:32:22.595
which itself is a square.
00:32:22.595 --> 00:32:26.636
So the difference of N and a^2 is a square.
00:32:26.636 --> 00:32:30.915
Then I take this 64, take a-64, divide N,
00:32:30.915 --> 00:32:34.413
it's an exact division, so I found one of the factors.
00:32:34.413 --> 00:32:37.200
And then there's the other factor.
00:32:37.200 --> 00:32:39.738
It doesn't matter whether it's a power of 2 or a power of 10.
00:32:39.738 --> 00:32:42.569
What matters is that the numbers are too close.
00:32:42.569 --> 00:32:44.712
Now this method actually works surprisingly well
00:32:44.712 --> 00:32:47.436
even if we don't do next_prime().
00:32:47.436 --> 00:32:50.332
So here's another example where I didn't do the next_prime()
00:32:50.332 --> 00:32:52.281
but did something larger
00:32:52.281 --> 00:32:55.114
so this is not really close to a square.
00:32:55.114 --> 00:32:57.731
Some 9's but not too many.
00:32:57.731 --> 00:33:00.053
What we did before we wrote it as a difference of squares
00:33:00.053 --> 00:33:04.614
and then divided N by one of these two factors.
00:33:04.614 --> 00:33:10.050
Now in this case here I would not start as a^2-N
00:33:10.050 --> 00:33:12.255
but I say, well, if a^2-N is not a square
00:33:12.255 --> 00:33:15.997
I try the next one, I do (a+1)^2, (a+2)^2
00:33:15.997 --> 00:33:20.777
each time subtract N and check when this is a square.
00:33:20.777 --> 00:33:24.170
Now for this example I get lucky after 2.
00:33:24.170 --> 00:33:26.331
And this actually took me a long time to cook up this example
00:33:26.331 --> 00:33:28.613
because I was starting at something which was
00:33:28.613 --> 00:33:31.669
half of the bits of p were changed.
00:33:31.669 --> 00:33:35.872
So I was actually starting with a cube quite a distance away.
00:33:35.872 --> 00:33:38.216
Still, most of those were just giving a square.
00:33:38.216 --> 00:33:42.070
They were not giving me anything larger than zero here.
00:33:42.070 --> 00:33:45.598
Now for general numbers if I wouldn't do like next_number()
00:33:45.598 --> 00:33:48.786
but just, well, random prime, another random prime.
00:33:48.786 --> 00:33:52.687
It still works but takes a long time
00:33:52.687 --> 00:33:55.488
because I can always write it this way.
00:33:55.488 --> 00:33:56.786
This is a, this is b.
00:33:56.786 --> 00:34:00.603
But then usually it would take about square root of N
00:34:00.603 --> 00:34:03.752
which is the same size as p until I get there.
00:34:03.752 --> 00:34:07.352
This is a nice method if it looks like lots of
00:34:07.352 --> 00:34:13.386
9999 and otherwise do something better as Dan will tell now.
00:34:13.386 --> 00:34:13.955
Dan: Ok.
00:34:13.955 --> 00:34:21.508
applause
00:34:21.508 --> 00:34:23.662
Alright, so it's bad to have p and q
00:34:23.662 --> 00:34:24.805
too close to each other
00:34:24.805 --> 00:34:28.640
or have a small p or to have p and q non-random.
00:34:28.640 --> 00:34:31.010
So let's do everything right.
00:34:31.010 --> 00:34:34.236
Let's make just independently choose some big p
00:34:34.236 --> 00:34:37.033
between 2^511 and 2^512
00:34:37.033 --> 00:34:38.667
and choose some big q
00:34:38.667 --> 00:34:42.586
without being like the next prime or anywhere in the ballpark of p.
00:34:42.586 --> 00:34:47.859
You could maybe say q has to be between 2^509 and 2^510
00:34:47.859 --> 00:34:49.522
and then it's definitely nowhere near p.
00:34:49.522 --> 00:34:52.539
Now you got this public key and p times q
00:34:52.539 --> 00:34:54.473
which is a 1024 bit RSA key.
00:34:54.473 --> 00:34:58.745
If nothing has gone wrong with your randomness generation
00:34:58.745 --> 00:35:00.153
then what does the attacker do?
00:35:00.153 --> 00:35:04.472
Well, we don't know anything fast.
00:35:04.472 --> 00:35:06.840
So this is gonna be the one part of the talk
00:35:06.840 --> 00:35:08.495
where there's these big powers of 2
00:35:08.495 --> 00:35:09.778
for how fast things are
00:35:09.778 --> 00:35:11.139
because they're not really fast.
00:35:11.139 --> 00:35:14.624
You have to think about how much something like 2^80 is.
00:35:14.624 --> 00:35:15.938
There's all these different methods,
00:35:15.938 --> 00:35:17.944
I'll just skip down to the last two.
00:35:17.944 --> 00:35:19.999
There's the quadratic sieve (QS),
00:35:19.999 --> 00:35:22.114
the number field sieve (NFS).
00:35:22.114 --> 00:35:24.109
These have been around since, well,
00:35:24.109 --> 00:35:29.192
QS since the 80th, NFS since the early 90th.
00:35:29.192 --> 00:35:32.327
The NFS, the general consensus is
00:35:32.327 --> 00:35:35.197
it takes something like 2^80 operations.
00:35:35.197 --> 00:35:36.675
Now here's something fun to try.
00:35:36.675 --> 00:35:38.844
If somebody says 2^80 operations
00:35:38.844 --> 00:35:41.473
and there's some cryptographer talking about the security or something,
00:35:41.473 --> 00:35:44.244
ask them: what do you mean by an operation?
00:35:44.244 --> 00:35:45.996
How fast is this operation?
00:35:45.996 --> 00:35:47.480
And then most of the people saying this
00:35:47.480 --> 00:35:48.624
will go running screaming like:
00:35:48.624 --> 00:35:49.850
I don't know what an operation is,
00:35:49.850 --> 00:35:51.193
don't ask me that question.
00:35:51.193 --> 00:35:53.382
But still people will confidently tell you
00:35:53.382 --> 00:35:56.230
that the NFS takes 2^80 operations
00:35:56.230 --> 00:36:00.347
to break any 1024 bit RSA key
00:36:00.347 --> 00:36:02.237
even if the user hasn't done anything wrong,
00:36:02.237 --> 00:36:04.047
the implementor hasn't done anything wrong.
00:36:04.047 --> 00:36:05.631
And this number, this 2^80
00:36:05.631 --> 00:36:07.618
if you pin down what those operations are,
00:36:07.618 --> 00:36:11.100
this is something which is doable today
00:36:11.100 --> 00:36:15.746
by people with a big botnet or people with a big computer cluster.
00:36:15.746 --> 00:36:18.611
I'll give some details what I mean, the size is there.
00:36:18.611 --> 00:36:21.797
As your computers get cheaper and cheaper,
00:36:21.797 --> 00:36:23.720
somehow chips aren't going up in clockspeed
00:36:23.720 --> 00:36:25.149
but they're still getting cheaper.
00:36:25.149 --> 00:36:27.636
You can get a really cheap ARM which is doing
00:36:27.636 --> 00:36:28.904
the same kind of computations
00:36:28.904 --> 00:36:31.501
that a pretty big CPU was doing several years ago.
00:36:31.501 --> 00:36:33.181
And chips are gonna continue getting cheaper
00:36:33.181 --> 00:36:36.604
for a while. These attacks against RSA 1024
00:36:36.604 --> 00:36:39.568
are going to be common doable for more and more people.
00:36:39.568 --> 00:36:43.119
How do these methods work?
00:36:43.119 --> 00:36:47.210
I'll give one example and then one little Sage script.
00:36:47.210 --> 00:36:50.169
Let's try just a really small number.
00:36:50.169 --> 00:36:51.717
This will be with the quadratic sieve
00:36:51.717 --> 00:36:53.727
which is not as fancy as the number field sieve
00:36:53.727 --> 00:36:56.395
but it will give you some idea of how these methods work.
00:36:56.395 --> 00:36:59.978
The QS starts with that Fermat method you heard about.
00:36:59.978 --> 00:37:04.066
Remember, the idea there was to try to find a square
00:37:04.066 --> 00:37:08.574
as a^2-N, so a was like the square root of N
00:37:08.574 --> 00:37:10.525
or maybe the plus 1, plus 2 and so on
00:37:10.525 --> 00:37:13.333
and you keep searching for a+1 and so on,
00:37:13.333 --> 00:37:15.933
search for numbers that if you square them and subtract N
00:37:15.933 --> 00:37:17.056
then you get a square.
00:37:17.056 --> 00:37:20.708
So let's try that for 50=2759 which is not very big.
00:37:20.708 --> 00:37:23.975
Then you try, 53 was the ceiling of the square root,
00:37:23.975 --> 00:37:27.673
square that, subtract 2759, you get 50.
00:37:27.673 --> 00:37:31.171
Well 25 would be a square, but 50 is not a square
00:37:31.171 --> 00:37:33.309
it's 2 times 25, 2 times 5^2.
00:37:33.309 --> 00:37:37.208
And then you try another number, 54^2-2759
00:37:37.208 --> 00:37:39.911
umm 157, that's too complicated
00:37:39.911 --> 00:37:42.707
I don't remember that being a square so let's just skip it.
00:37:42.707 --> 00:37:45.687
And then you keep going like this, 266, 377,
00:37:45.687 --> 00:37:48.223
490. I remember 49 is a square
00:37:48.223 --> 00:37:50.354
but that doesn't mean that 490 is a square
00:37:50.354 --> 00:37:52.372
cause 10, 2 times 5, that's not a square.
00:37:52.372 --> 00:37:55.871
And 605, you can try...
00:37:55.871 --> 00:37:58.640
We remember how to take out the 5
00:37:58.640 --> 00:38:01.275
and then 60... 605 divided by 5.
00:38:01.275 --> 00:38:03.588
You can figure out it's 5 times 11^2.
00:38:03.588 --> 00:38:05.158
It's almost a square.
00:38:05.158 --> 00:38:06.774
You keep doing this for a while
00:38:06.774 --> 00:38:10.534
and it seems like Fermat's method is actually working pretty badly.
00:38:10.534 --> 00:38:13.754
It does work eventually but it's taking quite a while.
00:38:13.754 --> 00:38:16.671
Here's what the quadratic sieve does.
00:38:16.671 --> 00:38:19.527
From the same computation you look at these
00:38:19.527 --> 00:38:21.585
numbers that were not exactly squares
00:38:21.585 --> 00:38:23.634
50 and 490 and 605
00:38:23.634 --> 00:38:27.056
and you notice if you multiple them together
00:38:27.056 --> 00:38:28.472
50 was 2 times 5^2
00:38:28.472 --> 00:38:30.756
490 is 2 times 5 times 7^2
00:38:30.756 --> 00:38:33.068
605 is 5 times 11^2
00:38:33.068 --> 00:38:34.585
and then you multiply those together
00:38:34.585 --> 00:38:38.524
you get 2^2 and 5^4 and 7^2 and 11^2
00:38:38.524 --> 00:38:41.123
and that's exactly the square of something.
00:38:41.123 --> 00:38:44.592
The square of 2^1 times 5^2 times 7 times 11.
00:38:44.592 --> 00:38:48.175
Then the quadratic sieve is taking the square root of that number
00:38:48.175 --> 00:38:52.553
and subtracting that from the product of the fifty-somethings
00:38:52.553 --> 00:38:53.953
that were on the left side
00:38:53.953 --> 00:38:56.826
and taking the greatest common divisor of that with N
00:38:56.826 --> 00:38:59.787
and amazingly that produces a factor of N.
00:38:59.787 --> 00:39:02.289
And it's not just some random accident that
00:39:02.289 --> 00:39:04.370
if you had tried the greatest common divisor of
00:39:04.370 --> 00:39:06.085
"write down some hocuspocus then"
00:39:06.085 --> 00:39:08.803
"you eventually get 31 coming out"
00:39:08.803 --> 00:39:10.576
"every 31 times you write down a random number"
00:39:10.576 --> 00:39:13.020
"it will have this 31 dividing it"
00:39:13.020 --> 00:39:15.347
No, you can try this for bigger and bigger numbers
00:39:15.347 --> 00:39:17.038
and actually this keeps working.
00:39:17.038 --> 00:39:18.663
As soon as you find a square product
00:39:18.663 --> 00:39:23.212
then half of those square products are gonna factor N.
00:39:23.212 --> 00:39:25.365
So that's how the quadratic sieve works.
00:39:25.365 --> 00:39:28.915
Here's a more systematic script with a much bigger number
00:39:28.915 --> 00:39:31.300
which if it were just hocuspocus this wouldn't work.
00:39:31.300 --> 00:39:32.616
But this does work.
00:39:32.616 --> 00:39:36.834
So there's a number from my computer's random number generator
00:39:36.834 --> 00:39:41.661
31415926... laughter
00:39:41.661 --> 00:39:45.099
You try writing down a bunch of squares...
00:39:45.099 --> 00:39:48.285
maybe I should get my computer's random number generator checked.
00:39:48.285 --> 00:39:50.636
It is this two year old laptop you heard about before
00:39:50.636 --> 00:39:52.202
so I'm not sure it's working properly.
00:39:52.202 --> 00:39:55.599
You take a bunch of a^2-N and then
00:39:55.599 --> 00:39:57.414
let's make a list of those called X.
00:39:57.414 --> 00:40:00.752
You can see the range, there is up to 500.000 numbers.
00:40:00.752 --> 00:40:02.948
It's a pretty big list we're talking about.
00:40:02.948 --> 00:40:05.749
And then search through those elements,
00:40:05.749 --> 00:40:08.538
search through those a^2-N, those differences,
00:40:08.538 --> 00:40:09.504
the elements in this list,
00:40:09.504 --> 00:40:12.985
to see which ones have easy factorizations.
00:40:12.985 --> 00:40:15.445
Now a lot of numbers like that 157
00:40:15.445 --> 00:40:16.970
I know what the factorization of that is
00:40:16.970 --> 00:40:19.846
but there is function which you can find on our website
00:40:19.846 --> 00:40:22.696
easyfactorizations() which looks through the list X
00:40:22.696 --> 00:40:25.251
and if it finds numbers that are easy to factor
00:40:25.251 --> 00:40:27.935
then it quickly writes down the factorizations
00:40:27.935 --> 00:40:30.482
using the small prime techniques you heard about.
00:40:30.482 --> 00:40:33.169
And then makes a list of those easy factorizations,
00:40:33.169 --> 00:40:34.396
puts those into F.
00:40:34.396 --> 00:40:37.600
And then there's a big chunk which I won't try to explain
00:40:37.600 --> 00:40:39.986
which is called linear algebra mod 2.
00:40:39.986 --> 00:40:42.586
And that somehow figures out a square
00:40:42.586 --> 00:40:45.697
that comes from the factorizations,
00:40:45.697 --> 00:40:48.363
somehow looks through this list of factorizations
00:40:48.363 --> 00:40:50.803
and magically applies some linear algebra stuff.
00:40:50.803 --> 00:40:52.612
Well ok, I won't go through that.
00:40:52.612 --> 00:40:54.071
It's something doable
00:40:54.071 --> 00:40:58.604
and this is using some standard Sage functions to do it pretty easily.
00:40:58.604 --> 00:41:01.738
There's all sorts of things that
00:41:01.738 --> 00:41:03.664
in the interest of time I won't get into
00:41:03.664 --> 00:41:05.867
like how this easyfactorizations() works.
00:41:05.867 --> 00:41:07.603
And this is something where people write papers
00:41:07.603 --> 00:41:09.801
and papers and papers talking about trying to make this
00:41:09.801 --> 00:41:11.603
go as quickly as possible.
00:41:11.603 --> 00:41:14.737
I do want to emphasize one fact about these methods:
00:41:14.737 --> 00:41:17.484
the bold-faced **very small memory requirements**.
00:41:17.484 --> 00:41:20.038
You can use the elliptic curve method
00:41:20.038 --> 00:41:21.531
that you heard about before
00:41:21.531 --> 00:41:24.882
you can use that to figure out easy factorizations
00:41:24.882 --> 00:41:27.063
using very little memory.
00:41:27.063 --> 00:41:28.503
That means you can build a chip
00:41:28.503 --> 00:41:30.471
like a FPGA, a special purpose ASIC,
00:41:30.471 --> 00:41:33.285
you can have thousands of little ECM units
00:41:33.285 --> 00:41:35.066
running in parallel, so you can really
00:41:35.066 --> 00:41:38.153
massively parallelize this easyfactorizations() function.
00:41:38.153 --> 00:41:40.187
So if people tell you "oh you need tons of
00:41:40.187 --> 00:41:43.386
memory for sieving to find easy factorizations"
00:41:43.386 --> 00:41:45.868
then you should tell them "no no, that's not true"
00:41:45.868 --> 00:41:47.979
"ECM you can do with very little memory
00:41:47.979 --> 00:41:50.351
running massively parallelizable"
00:41:50.351 --> 00:41:52.802
And then there's other things which,
00:41:52.802 --> 00:41:54.490
I suppose if we had another hour
00:41:54.490 --> 00:41:56.432
then we could get into all these details
00:41:56.432 --> 00:41:59.117
of like how the number field sieve goes beyond this.
00:41:59.117 --> 00:42:01.970
It's a similar kind of method but gets more complicated.
00:42:01.970 --> 00:42:05.181
I do want to emphasize again thing in bold-face here
00:42:05.181 --> 00:42:06.946
which is that if somebody tells you
00:42:06.946 --> 00:42:10.438
"oh 2^80 operations, the attacker wouldn't do
00:42:10.438 --> 00:42:13.796
that because the target isn't worth that much to them"
00:42:13.796 --> 00:42:18.284
Well, **Batch NFS** is a way to take a bunch of N's
00:42:18.284 --> 00:42:20.566
and like the batch techniques before
00:42:20.566 --> 00:42:23.516
there's some magic ways to find redundancies
00:42:23.516 --> 00:42:25.884
between doing factorizations of those N's.
00:42:25.884 --> 00:42:26.937
So somebody tells you:
00:42:26.937 --> 00:42:30.000
"oh 2^80, that isn't worth it for the attacker."
00:42:30.000 --> 00:42:33.296
Well, **Batch NFS** reduces the cost quite a bit
00:42:33.296 --> 00:42:34.821
for factoring each key.
00:42:34.821 --> 00:42:36.846
If the attacker has a lot of keys to target
00:42:36.846 --> 00:42:39.852
they can factor all of them in not much more cost
00:42:39.852 --> 00:42:41.396
than just factoring one.
00:42:41.396 --> 00:42:43.734
So don't believe people who take an economic view
00:42:43.734 --> 00:42:46.987
how much the number field sieve is worth.
00:42:46.987 --> 00:42:49.416
Alright, what does this mean?
00:42:49.416 --> 00:42:52.118
Can the attacker actually do the NFS
00:42:52.118 --> 00:42:54.134
once they've put in all these optimizations?
00:42:54.134 --> 00:42:59.064
Well if you look carefully at the analyses of the NFS
00:42:59.064 --> 00:43:02.416
there are only about 2^70 differences.
00:43:02.416 --> 00:43:04.149
Things like these a^2-N's.
00:43:04.149 --> 00:43:08.862
If you look through 2^70 of those and scan them properly,
00:43:08.862 --> 00:43:10.773
find easy factorizations, do linear algebra,
00:43:10.773 --> 00:43:13.669
you will factor any 1024 bit key.
00:43:13.669 --> 00:43:16.314
And 2^70, how big is that number?
00:43:16.314 --> 00:43:20.820
It's actually small enough that you can do this computation on
00:43:20.820 --> 00:43:22.469
your favorite botnet.
00:43:22.469 --> 00:43:25.749
Say, Conficker is shrinking, still
00:43:25.749 --> 00:43:27.947
and it will probably be wiped out at some point
00:43:27.947 --> 00:43:29.488
but it's an example of what you can do
00:43:29.488 --> 00:43:32.468
using any of these security problems that are deployed
00:43:32.468 --> 00:43:33.632
on enough machines.
00:43:33.632 --> 00:43:35.398
You can break into a bunch of machines,
00:43:35.398 --> 00:43:36.521
millions of machines.
00:43:36.521 --> 00:43:40.296
Conficker estimates vary between 7 million and 12 million machines.
00:43:40.296 --> 00:43:44.320
So use your, say, 2^23, that's 8 million machines.
00:43:44.320 --> 00:43:46.519
Count how many seconds there are in a year
00:43:46.519 --> 00:43:48.553
and then, say, ok that means we have to do
00:43:48.553 --> 00:43:52.070
2^22 differences per second machine.
00:43:52.070 --> 00:43:56.902
And that is slower than state of the art factorization code already runs.
00:43:56.902 --> 00:43:59.231
So it's actually a pretty easy computation.
00:43:59.231 --> 00:44:02.334
You don't even need that many millions of computers to do this.
00:44:02.334 --> 00:44:04.470
If people tell you "wait a minute"
00:44:04.470 --> 00:44:06.120
"you can't just use a bunch of machines"
00:44:06.120 --> 00:44:08.073
"there's all this work for linear algebra"
00:44:08.073 --> 00:44:09.966
Then I'll just skip this.
00:44:09.966 --> 00:44:12.882
Be aware that linear algebra is not as much of a problem
00:44:12.882 --> 00:44:15.334
as some people would say.
00:44:15.334 --> 00:44:18.872
If you use a big botnet there's one little problem.
00:44:18.872 --> 00:44:21.053
For an attacker who breaks into a bunch of machines
00:44:21.053 --> 00:44:23.903
and then starts spinning them up, heating up the CPU,
00:44:23.903 --> 00:44:25.921
the fan starts running, the user starts wondering
00:44:25.921 --> 00:44:28.017
"why is my machine running so slowly?"
00:44:28.017 --> 00:44:30.133
Maybe only use half of the CPU
00:44:30.133 --> 00:44:33.570
but still it has still got a good chance of getting you detected
00:44:33.570 --> 00:44:35.202
and kicked off the machines.
00:44:35.202 --> 00:44:37.266
Users are gonna shut you down if you're doing a
00:44:37.266 --> 00:44:39.463
say, year of computation on your botnet.
00:44:39.463 --> 00:44:42.883
So what do you do instead?
00:44:42.883 --> 00:44:45.021
Well you build a little computer cluster.
00:44:45.021 --> 00:44:49.354
Now yesterday we heard about a big building
00:44:49.354 --> 00:44:51.164
in Bluffdale, Utah, that apparently
00:44:51.164 --> 00:44:54.832
is going to store all of the data collected by
00:44:54.832 --> 00:44:57.171
the NSA for the next hundred years
00:44:57.171 --> 00:44:58.854
or maybe forever.
00:44:58.854 --> 00:45:00.914
But something that I didn't hear emphasized yesterday
00:45:00.914 --> 00:45:04.916
was that this building also has a new power substation
00:45:04.916 --> 00:45:08.150
which is drawing 65 megawatts,
00:45:08.150 --> 00:45:10.155
well generating 65 megawatts.
00:45:10.155 --> 00:45:13.999
Now what are we doing with 65 megawatts?
00:45:13.999 --> 00:45:15.308
Is that the kind of power that you need to
00:45:15.308 --> 00:45:17.490
store a bunch of data on tapes?
00:45:17.490 --> 00:45:21.175
No, that's the kind of power you need to do computations.
00:45:21.175 --> 00:45:24.725
So what is NSA doing with 2^26 watts?
00:45:24.725 --> 00:45:26.955
Or maybe even with more watts.
00:45:26.955 --> 00:45:30.909
You shouldn't actually think that 2^26 is such a big number.
00:45:30.909 --> 00:45:33.526
Here's a little table with, well,
00:45:33.526 --> 00:45:36.573
2^57 admittedly is pushing it a little bit.
00:45:36.573 --> 00:45:40.620
This is the total power that the earth gets from the sun
00:45:40.620 --> 00:45:43.207
of which about half gets to the earth's surface.
00:45:43.207 --> 00:45:47.610
2^44 is the amount the human is using right now.
00:45:47.610 --> 00:45:50.888
Varies a little bit but I mean this is the average power
00:45:50.888 --> 00:45:53.427
including cars and such.
00:45:53.427 --> 00:45:56.446
If you have the botnet that breaks into millions of machines
00:45:56.446 --> 00:45:59.944
and runs in flat-out that's about 2^30 watts.
00:45:59.944 --> 00:46:01.610
And actually if you think about it, wait a minute,
00:46:01.610 --> 00:46:02.575
there's a lot of machines out there.
00:46:02.575 --> 00:46:07.270
This means the 2^26 is not actually that much power.
00:46:07.270 --> 00:46:11.456
It's just one dinky little Bluffdale 65 MW computer center
00:46:11.456 --> 00:46:14.594
and actually if you're a government agency
00:46:14.594 --> 00:46:16.138
you probably have more than one of those.
00:46:16.138 --> 00:46:19.273
As you heard yesterday in the context of data storage
00:46:19.273 --> 00:46:21.292
but again, it's not just data storage.
00:46:21.292 --> 00:46:26.492
You don't make a 65 MW power station to just store data.
00:46:26.492 --> 00:46:30.207
Ok, if you just take standard graphics processing units
00:46:30.207 --> 00:46:33.223
and run 2^26 watts to those that will do about
00:46:33.223 --> 00:46:36.446
2^84 floating point multiplications per year.
00:46:36.446 --> 00:46:39.827
You have to figure out, ok, what are exactly the operations involved here.
00:46:39.827 --> 00:46:44.829
This should be enough to break 1024 bit RSA
00:46:44.829 --> 00:46:48.088
and if NSA is not just buying GPU's off-the-shelves
00:46:48.088 --> 00:46:50.226
but really tuning chips that they build
00:46:50.226 --> 00:46:57.409
using IBM to manufacture their chips at the moment.
00:46:57.409 --> 00:47:01.626
Apparently it wasn't cost-effective for NSA to manufacture their own chips
00:47:01.626 --> 00:47:04.475
so in 2005 they started subcontracting for IBM
00:47:04.475 --> 00:47:08.153
but presumably through that fabrication IBM is building chips
00:47:08.153 --> 00:47:11.073
that NSA wants and those should be about 10 times faster
00:47:11.073 --> 00:47:13.025
than what GPU's can do.
00:47:13.025 --> 00:47:18.362
So it should be possible with this little 65 MW computer cluster
00:47:18.362 --> 00:47:21.476
to factor at least 1, maybe even 10,
00:47:21.476 --> 00:47:23.478
and then with batch NFS maybe even more
00:47:23.478 --> 00:47:30.010
1024 bit RSA keys in a year.
00:47:30.010 --> 00:47:38.229
applause
00:47:38.229 --> 00:47:41.130
Nadia: So to conclude things up here I want to
00:47:41.130 --> 00:47:43.290
explain how you can use
00:47:43.290 --> 00:47:46.057
from the comfort of your very own home
00:47:46.057 --> 00:47:52.242
a distributed, a massive scale distributed cloud computing service
00:47:52.242 --> 00:47:57.142
to calculate private keys on your own.
00:47:57.142 --> 00:48:00.313
So many of you may be familiar with Amazon EC2
00:48:00.313 --> 00:48:04.635
but it turns out Google also has a large amount of computing infrastructure
00:48:04.635 --> 00:48:07.339
and they actually have a very convenient web interface
00:48:07.339 --> 00:48:08.446
to access it.
00:48:08.446 --> 00:48:12.978
laugther
00:48:12.978 --> 00:48:21.677
applause
00:48:21.677 --> 00:48:23.961
It's amazing what you can find on the Internet.
00:48:23.961 --> 00:48:26.143
laughter
00:48:26.143 --> 00:48:29.393
So ok, here's some keys except, you know,
00:48:29.393 --> 00:48:30.578
if you look at these carefully
00:48:30.578 --> 00:48:33.277
not all of these are sort of obviously RSA keys.
00:48:33.277 --> 00:48:35.204
There are some problems here
00:48:35.204 --> 00:48:40.704
like the second to last one on the bottom.
00:48:40.704 --> 00:48:41.688
So...
00:48:41.688 --> 00:48:43.338
laughter
00:48:43.338 --> 00:48:49.820
After doing this search we found this key and
00:48:49.820 --> 00:48:55.279
someone seems to have pasted a private key into pastebin
00:48:55.279 --> 00:49:00.491
and someone came along and interrupted part of it
00:49:00.491 --> 00:49:04.759
with some profanity.
00:49:04.759 --> 00:49:07.387
This is an interesting problem.
00:49:07.387 --> 00:49:08.812
What do we do with this key?
00:49:08.812 --> 00:49:12.310
Clearly this is an interesting key, we must have this key.
00:49:12.310 --> 00:49:14.204
laughter
00:49:14.204 --> 00:49:24.847
applause
00:49:24.847 --> 00:49:26.046
Step 1... yeah?
00:49:26.046 --> 00:49:29.572
Male: Did you see the easter egg in row 1?
00:49:29.572 --> 00:49:31.204
Nadia: Well, we'll discuss this.
00:49:31.204 --> 00:49:34.308
Angel: Questions will be later, after the talk please.
00:49:34.308 --> 00:49:39.368
Nadia: So yeah, we've removed the obvious problems here.
00:49:39.368 --> 00:49:41.636
But there's still an issue which is that
00:49:41.636 --> 00:49:43.844
we're missing hundreds and hundreds of bits of key.
00:49:43.844 --> 00:49:45.940
We can't brute force-this.
00:49:45.940 --> 00:49:47.658
What are we gonna do?
00:49:47.658 --> 00:49:51.327
Well, let's look at what RSA keys actually are.
00:49:51.327 --> 00:49:53.509
I introduced RSA keys and I was, like,
00:49:53.509 --> 00:49:56.786
it's a d and d has like a thosand of bits.
00:49:56.786 --> 00:50:00.671
And if we don't know p and q
00:50:00.671 --> 00:50:02.608
how are we gonna get this d?
00:50:02.608 --> 00:50:07.923
Here is the storage format for an RSA key.
00:50:07.923 --> 00:50:11.258
Public key is the modulus N, the public exponent e.
00:50:11.258 --> 00:50:14.710
Ok, private key has version, N, e,
00:50:14.710 --> 00:50:16.536
d the decryption exponent,
00:50:16.536 --> 00:50:20.273
p, q, d mod (p-1), d mod (q-1),
00:50:20.273 --> 00:50:22.975
the inverse of q mod p,
00:50:22.975 --> 00:50:25.305
this is all useful information if you want to
00:50:25.305 --> 00:50:26.960
speed up your calculation and not have to
00:50:26.960 --> 00:50:29.405
compute everything every time you use your key.
00:50:29.405 --> 00:50:32.493
Okay.
00:50:32.493 --> 00:50:35.952
What did we see here then?
00:50:35.952 --> 00:50:40.975
Here is the key broken up into all of the difference pieces.
00:50:40.975 --> 00:50:44.804
So we have: the red bit is approximately where N is sitting.
00:50:44.804 --> 00:50:46.754
We've got e in orange.
00:50:46.754 --> 00:50:50.569
We've got part of d in yellow.
00:50:50.569 --> 00:50:52.372
We seem to be missing p
00:50:52.372 --> 00:50:54.656
but we've got part of q
00:50:54.656 --> 00:50:56.791
and then here's d mod p-1
00:50:56.791 --> 00:51:02.408
and d mod q-1 and q inverse mod p.
00:51:02.408 --> 00:51:07.712
There's also a little problem before the red here
00:51:07.712 --> 00:51:08.436
laughter
00:51:08.436 --> 00:51:10.504
in addition.
00:51:10.504 --> 00:51:13.561
You might call this the private part of the private key.
00:51:13.561 --> 00:51:15.936
laughter
00:51:15.936 --> 00:51:21.391
applause
00:51:21.391 --> 00:51:23.859
Fortunately this is just sitting in an encoding of the length
00:51:23.859 --> 00:51:30.275
and the version. laughter
00:51:30.275 --> 00:51:33.151
Alright, so what do we do with this information?
00:51:33.151 --> 00:51:36.673
Basically given any part of this private key
00:51:36.673 --> 00:51:38.910
we can easily compute all of the other parts.
00:51:38.910 --> 00:51:40.257
Simple formulas:
00:51:40.257 --> 00:51:48.938
q will be 2^(e times d mod p-1) - 1 and GCD that with N
00:51:48.938 --> 00:51:51.872
then we get q and then
00:51:51.872 --> 00:51:54.455
we can figure out what p was by dividing
00:51:54.455 --> 00:51:56.393
and figure out what d is
00:51:56.393 --> 00:51:57.953
and so on and so forth.
00:51:57.953 --> 00:52:02.460
You can do this even if you have a part of a single value
00:52:02.460 --> 00:52:04.109
from the private key.
00:52:04.109 --> 00:52:08.195
You can still compute the rest of the private key from that.
00:52:08.195 --> 00:52:12.338
We don't have time to get into this but it's online.
00:52:12.338 --> 00:52:16.557
You've seen a little bit of math.
00:52:16.557 --> 00:52:18.060
Single formulas, typed into Sage.
00:52:18.060 --> 00:52:22.591
We can reconstruct the private key here.
00:52:22.591 --> 00:52:29.487
applause
00:52:29.487 --> 00:52:32.941
So, what are the lessons that we can learn
00:52:32.941 --> 00:52:35.554
from everything that we've done today.
00:52:35.554 --> 00:52:38.945
The first one is: stop using 1024 bit RSA
00:52:38.945 --> 00:52:41.010
if you haven't already.
00:52:41.010 --> 00:52:43.386
I have looked at the keys that are out there on the Internet
00:52:43.386 --> 00:52:45.941
and you are still using 1024 bit RSA.
00:52:45.941 --> 00:52:48.463
laughter
00:52:48.463 --> 00:52:51.790
Second: make sure your primes are big enough.
00:52:51.790 --> 00:52:54.227
Don't try to be clever about how you're generating them.
00:52:54.227 --> 00:52:58.025
Make sure your primes are random.
00:52:58.025 --> 00:52:59.303
You guys have some problems
00:52:59.303 --> 00:53:01.394
especially in hardware.
00:53:01.394 --> 00:53:03.621
Also...
00:53:03.621 --> 00:53:04.921
laughter
00:53:04.921 --> 00:53:09.091
"FUCK A DUCK" is not good crypto.
00:53:09.091 --> 00:53:11.545
Pastebin is not a secure cloud store.
00:53:11.545 --> 00:53:13.874
laughter
00:53:13.874 --> 00:53:20.289
applause
00:53:20.289 --> 00:53:22.657
And you probably shouldn't put your private key
00:53:22.657 --> 00:53:24.778
in a secure cloud store anyway.
00:53:24.778 --> 00:53:25.862
laughter
00:53:25.862 --> 00:53:31.396
applause
00:53:31.396 --> 00:53:32.577
And lastly...
00:53:32.577 --> 00:53:34.211
laughter
00:53:34.211 --> 00:53:40.427
applause
00:53:40.427 --> 00:53:41.625
Thank you.
00:53:41.625 --> 00:53:43.894
applause
00:53:43.894 --> 00:53:44.804
Angel: Give them an applause.
00:53:44.804 --> 00:54:05.937
applause
00:54:05.937 --> 00:54:11.379
Angel: So questions will be taken at the numbered microphones.
00:54:11.379 --> 00:54:14.962
So anyone who has a question please line up at a microphone
00:54:14.962 --> 00:54:16.959
and we will start by the signal angel
00:54:16.959 --> 00:54:19.528
who has a question from IRC.
00:54:19.528 --> 00:54:23.628
*Signal Angel*: IRC has a lot of punch lines involving penisses
00:54:23.628 --> 00:54:26.040
and some questions.
00:54:26.040 --> 00:54:31.445
First question is: would you recommend more using
00:54:31.445 --> 00:54:37.640
elliptic curves or RSA with multiple primes...
00:54:37.640 --> 00:54:41.659
using proper primes.
00:54:41.659 --> 00:54:47.192
Dan: There are ways to do elliptic curves wrong,
00:54:47.192 --> 00:54:48.854
there are ways to do RSA wrong.
00:54:48.854 --> 00:54:53.806
In general if you've got a particular performance requirement
00:54:53.806 --> 00:54:55.625
then elliptic curves are gonna meet that
00:54:55.625 --> 00:54:57.861
with a much higher security level
00:54:57.861 --> 00:55:00.208
than RSA is gonna meet that.
00:55:00.208 --> 00:55:03.005
Of course you can do RSA securely,
00:55:03.005 --> 00:55:04.928
you can do elliptic curves securely
00:55:04.928 --> 00:55:07.153
but if you've got some performance limitation
00:55:07.153 --> 00:55:08.613
as many applications do
00:55:08.613 --> 00:55:13.043
then elliptic curves tend to be a better choice.
00:55:13.043 --> 00:55:14.429
Nadia: I also want to clarify
00:55:14.429 --> 00:55:17.826
the other most commonly used public-key cryptosystem
00:55:17.826 --> 00:55:19.979
is DSA, the Digital Signature Algorithm.
00:55:19.979 --> 00:55:21.426
There's also elliptic curve DSA
00:55:21.426 --> 00:55:23.291
which is probably what you're thinking about
00:55:23.291 --> 00:55:25.570
with elliptic curve cryptography.
00:55:25.570 --> 00:55:31.207
DSA is in my opinion actually much worse
00:55:31.207 --> 00:55:34.395
than RSA in terms of randomness failures.
00:55:34.395 --> 00:55:36.246
In the paper that Dan referenced
00:55:36.246 --> 00:55:39.377
we also talk about randomness failures in DSA
00:55:39.377 --> 00:55:40.993
and it's horrifying.
00:55:40.993 --> 00:55:44.521
If you ever ever screw up randomness in a single signature
00:55:44.521 --> 00:55:48.354
your entire public key is lost.
00:55:48.354 --> 00:55:50.761
Angel: We will take the next question from microphone nr 4
00:55:50.761 --> 00:55:53.072
to the right of the seat.
00:55:53.072 --> 00:55:53.824
Jake: Hey guys.
00:55:53.824 --> 00:55:56.277
Sorry I didn't mention the computing power of Bluffdale.
00:55:56.277 --> 00:56:02.072
That said, when we want to transition from 1024 bit RSA
00:56:02.072 --> 00:56:05.339
to something else, what do you think is a good idea?
00:56:05.339 --> 00:56:10.028
So for example, in Tor we do use 1024 bit RSA for TLS.
00:56:10.028 --> 00:56:12.528
laughter Yeah I know, right?
00:56:12.528 --> 00:56:15.592
So the thing is we're working on changing these things
00:56:15.592 --> 00:56:17.079
but what is...
00:56:17.079 --> 00:56:19.766
I mean Zooko has this 100 year crypto project.
00:56:19.766 --> 00:56:21.806
What is the real thing that we should,
00:56:21.806 --> 00:56:23.910
like if we could switch tomorrow to something,
00:56:23.910 --> 00:56:26.595
what's the useful that we can live with for 5 or 10 years?
00:56:26.595 --> 00:56:28.795
Is 2048 going to be useful?
00:56:28.795 --> 00:56:31.179
Is 4096 where we should go tomorrow?
00:56:31.179 --> 00:56:32.780
Cause there is a trade-off between
00:56:32.780 --> 00:56:34.588
performance and forward secrecy
00:56:34.588 --> 00:56:37.962
and there are a lot of things to think about.
00:56:37.962 --> 00:56:40.078
Tanja: If you tell me 5 to 10 years
00:56:40.078 --> 00:56:42.360
I would be still comfortable with elliptic curves.
00:56:42.360 --> 00:56:44.773
If you talk 100 years
00:56:44.773 --> 00:56:47.691
and then there's all these worse quantum computers around
00:56:47.691 --> 00:56:51.143
then I would go for something which is worse in performance
00:56:51.143 --> 00:56:52.829
like code-based cryptography
00:56:52.829 --> 00:56:54.043
or for signatures hashing
00:56:54.043 --> 00:56:55.738
but if you'd say in 5 to 10 years
00:56:55.738 --> 00:56:57.411
I'm very comfortable recommending to you
00:56:57.411 --> 00:56:59.941
elliptic curves with 256 bits.
00:56:59.941 --> 00:57:02.160
Jake: Ok, thanks.
00:57:02.160 --> 00:57:04.878
Angel: Signal angel?
00:57:04.878 --> 00:57:07.190
*Signal Angel*: Yeah, another question from IRC.
00:57:07.190 --> 00:57:11.028
If you avoid all the easy primes
00:57:11.028 --> 00:57:14.227
does this shrink the search space such that
00:57:14.227 --> 00:57:17.862
it becomes easier to crack the remaining keys?
00:57:17.862 --> 00:57:20.161
Or asked another way:
00:57:20.161 --> 00:57:25.146
can you quantify the ratio of easy primes versus hard primes?
00:57:25.146 --> 00:57:26.287
Dan: Yeah, that's a good question.
00:57:26.287 --> 00:57:28.573
The answer is: yes, it can be quantified
00:57:28.573 --> 00:57:32.829
and once you're up to about to the 1024 bit RSA key level
00:57:32.829 --> 00:57:35.306
then there's very very few weak primes.
00:57:35.306 --> 00:57:37.078
So if you have a random number,
00:57:37.078 --> 00:57:38.593
you just generate a random prime
00:57:38.593 --> 00:57:40.238
then your chance of bumping into something weak
00:57:40.238 --> 00:57:42.793
is so small that you just don't have to worry about it.
00:57:42.793 --> 00:57:44.862
It is one of those much less frequent than
00:57:44.862 --> 00:57:46.580
being hit by a lightning kind of events.
00:57:46.580 --> 00:57:49.210
It is something that have been quantified
00:57:49.210 --> 00:57:52.244
and it is an issue for smaller RSA keys
00:57:52.244 --> 00:57:54.872
back when people were using, say, 512 bit RSA
00:57:54.872 --> 00:57:56.754
then it was actually a noticable issue.
00:57:56.754 --> 00:57:59.123
But once you're at 1024 or above then
00:57:59.123 --> 00:58:00.694
the issue is basically gone.
00:58:00.694 --> 00:58:03.831
It's something where you can and you should
00:58:03.831 --> 00:58:06.097
look at exactly what the chance is of bumping into a weak
00:58:06.097 --> 00:58:08.828
but it's not reallistically something
00:58:08.828 --> 00:58:13.259
you're gonna encounter with 1024 bit RSA.
00:58:13.259 --> 00:58:16.542
Angel: We're gonna take the next question from nr 1.
00:58:16.542 --> 00:58:19.313
Just one notice: we don't have a lot of time left
00:58:19.313 --> 00:58:23.546
so even though there is a talk in one hour
00:58:23.546 --> 00:58:25.078
just ask.
00:58:25.078 --> 00:58:28.165
Male: There is a devastating attack that can break AES,
00:58:28.165 --> 00:58:31.872
SHA2, most probably SHA3 and DES.
00:58:31.872 --> 00:58:33.758
It's called a biclique attack.
00:58:33.758 --> 00:58:35.664
Are you concerned that it might break RSA
00:58:35.664 --> 00:58:37.281
with any key size and even ECC
00:58:37.281 --> 00:58:39.988
and even any public-key crypto?
00:58:39.988 --> 00:58:41.660
Dan: No.
00:58:41.660 --> 00:58:43.594
laughter
00:58:43.594 --> 00:58:46.675
Bicliques are something which are certainly interesting
00:58:46.675 --> 00:58:49.590
and I think about it as a way to speed up brute force
00:58:49.590 --> 00:58:52.508
and it speeds up brute force by a noticable factor,
00:58:52.508 --> 00:58:55.148
often makes attacks, say, twice as fast.
00:58:55.148 --> 00:58:58.523
But with public-key crypto we have attacks which are
00:58:58.523 --> 00:59:00.760
much much faster than brute force to begin with
00:59:00.760 --> 00:59:04.209
so that kind of speed-up of brute force won't be competitive
00:59:04.209 --> 00:59:08.226
with things like the number field sieve.
00:59:08.226 --> 00:59:12.964
Angel: Next is from number 3.
00:59:12.964 --> 00:59:16.824
Male: Me not coming from the dark side of mathematics,
00:59:16.824 --> 00:59:20.923
how do I know that my random number generators are fine
00:59:20.923 --> 00:59:23.661
for generating keys?
00:59:23.661 --> 00:59:26.223
laughter
00:59:26.223 --> 00:59:31.354
Nadia: Seed them.
00:59:31.354 --> 00:59:37.042
Basically the things that are out there if you're using
00:59:37.042 --> 00:59:40.613
a standard random number generator like in Linux,
00:59:40.613 --> 00:59:44.441
actually Linux has added patches to the kernel
00:59:44.441 --> 00:59:48.022
to fix some of the problems that we've found.
00:59:48.022 --> 00:59:50.431
If you want to know that you're keys are good:
00:59:50.431 --> 00:59:54.694
if you generate them on a general purpose computer
00:59:54.694 --> 00:59:56.600
after it has been running for a long time
00:59:56.600 --> 00:59:59.559
you're probably fine.
00:59:59.559 --> 01:00:04.793
I would not generate very important or long-term keys
01:00:04.793 --> 01:00:09.707
on low-power hardware devices where you can't tell...
01:00:09.707 --> 01:00:11.910
laughter
01:00:11.910 --> 01:00:15.758
Male: Thank you.
01:00:15.758 --> 01:00:18.341
Angel: Next question will be taken from number 4.
01:00:18.341 --> 01:00:19.394
Male: Hi.
01:00:19.394 --> 01:00:23.690
It's just a remark, not really a question.
01:00:23.690 --> 01:00:25.407
I work in high performance computing.
01:00:25.407 --> 01:00:26.910
I was at the supercomputing conference
01:00:26.910 --> 01:00:29.376
a couple of weeks ago.
01:00:29.376 --> 01:00:31.931
They're presenting large-scale installations
01:00:31.931 --> 01:00:35.863
and dealing with problems of power.
01:00:35.863 --> 01:00:38.927
They want to build petaflops and exaflops systems
01:00:38.927 --> 01:00:42.262
that are in a range of 20 MW.
01:00:42.262 --> 01:00:47.316
So I'm wondering what NSA is doing with 53 megawatts
01:00:47.316 --> 01:00:53.815
in a data center because no storage takes that much capacity.
01:00:53.815 --> 01:00:58.976
I think it's really something we should think about.
01:00:58.976 --> 01:01:03.266
So thanks, nice talk.
01:01:03.266 --> 01:01:04.883
Angel: Next question from...
01:01:04.883 --> 01:01:06.961
does the signal angel have one?
01:01:06.961 --> 01:01:08.679
*Signal angel*: Ok, another question is:
01:01:08.679 --> 01:01:11.845
How big do you estimate the effort to
01:01:11.845 --> 01:01:17.308
exchange keys and certificates involving 1024 bit primes
01:01:17.308 --> 01:01:22.782
let's say worldwide at the moment?
01:01:22.782 --> 01:01:24.502
Dan: I wasn't getting what the question was.
01:01:24.502 --> 01:01:25.642
Could you repeat the question?
01:01:25.642 --> 01:01:27.344
*Signal angel*: I don't really understand it myself.
01:01:27.344 --> 01:01:28.875
laughter
01:01:28.875 --> 01:01:33.181
Angel: Ok, let's switch to 1.
01:01:33.181 --> 01:01:37.009
Male: My question goes back to the idea
01:01:37.009 --> 01:01:42.876
of how can we know how good the private keys are?
01:01:42.876 --> 01:01:50.227
Is there something like a keygen evaluation tool?
01:01:50.227 --> 01:01:56.567
Or can the quality of a key generator be estimated
01:01:56.567 --> 01:01:58.544
from a sample of keys?
01:01:58.544 --> 01:02:01.827
Like a public tool that you can throw keys on
01:02:01.827 --> 01:02:05.565
and it will tell me a bias of my keygen?
01:02:05.565 --> 01:02:09.091
Nadia: If you go to factorable.net
01:02:09.091 --> 01:02:12.574
my co-authors and I have made a key check tool
01:02:12.574 --> 01:02:14.728
which will tell you if your key is in the
01:02:14.728 --> 01:02:17.528
list of keys that we scraped off the Internet
01:02:17.528 --> 01:02:19.296
that we were able to compromise.
01:02:19.296 --> 01:02:21.249
That's a first check.
01:02:21.249 --> 01:02:24.449
It's not a positive verification that your key is good
01:02:24.449 --> 01:02:26.544
but it will tell you if it is very bad.
01:02:26.544 --> 01:02:28.863
laughter
01:02:28.863 --> 01:02:36.811
If you want to check your generator,
01:02:36.811 --> 01:02:40.827
if you're worried about the factorization problems
01:02:40.827 --> 01:02:43.242
we have fast code on the website in C
01:02:43.242 --> 01:02:45.715
that will do the GCD calculation for you
01:02:45.715 --> 01:02:50.201
if you just dump a gigantic collection of keys at it.
01:02:50.201 --> 01:02:54.375
If you might have other problems like you are
01:02:54.375 --> 01:02:56.993
not sure whether it's factorable like those don't come up
01:02:56.993 --> 01:03:00.497
the experiment that you might want to do is
01:03:00.497 --> 01:03:04.211
sort of restart the process in realistic conditions
01:03:04.211 --> 01:03:06.179
and generate a gigantic quantity of keys
01:03:06.179 --> 01:03:08.981
and just check for repeats.
01:03:08.981 --> 01:03:12.378
The sort of obvious stress testings.
01:03:12.378 --> 01:03:16.375
If you have a device you want to boot it up in realistic conditions
01:03:16.375 --> 01:03:18.048
and then check them
01:03:18.048 --> 01:03:19.798
and this is painstaking work
01:03:19.798 --> 01:03:22.327
but I don't think there's any realistic way
01:03:22.327 --> 01:03:25.546
of doing better than that.
01:03:25.546 --> 01:03:28.396
Or inspect the code, the obvious thing.
01:03:28.396 --> 01:03:30.924
Make sure you're seeding anything.
01:03:30.924 --> 01:03:33.463
Male: Ok, thank you.
01:03:33.463 --> 01:03:35.993
Angel: Next question will be from mic number 4.
01:03:35.993 --> 01:03:37.045
Male: Hi.
01:03:37.045 --> 01:03:40.745
If I got your numbers correctly so you said something like
01:03:40.745 --> 01:03:45.450
it would take 8 million machines a year to factor 1024
01:03:45.450 --> 01:03:48.976
so I was wondering what if I would like to factor like
01:03:48.976 --> 01:03:52.243
800 bits or 900 bits which is,
01:03:52.243 --> 01:03:55.149
as I understand, way easier than 1024
01:03:55.149 --> 01:03:57.042
but was never done publicly.
01:03:57.042 --> 01:04:00.259
So are you saying that would take like a day or something?
01:04:00.259 --> 01:04:02.581
Dan: It depends on the size of cluster you have.
01:04:02.581 --> 01:04:07.064
The RSA 768 factorization a couple of years ago
01:04:07.064 --> 01:04:11.423
used something on the scale of a 1500 computers
01:04:11.423 --> 01:04:14.130
for a year.
01:04:14.130 --> 01:04:15.729
And those were normal kind of computers,
01:04:15.729 --> 01:04:19.475
Desktop kind of computers with, I think, typically 2 cores.
01:04:19.475 --> 01:04:24.240
Nowadays, if you have some faster, say, 3 GHz 4-core machines,
01:04:24.240 --> 01:04:27.446
I think those were typically 2 GHZ 2-core, nowadays...
01:04:27.446 --> 01:04:30.582
Tanja's mentioning you of course want to use GPUs
01:04:30.582 --> 01:04:31.725
to speed things up.
01:04:31.725 --> 01:04:33.397
And there's many ways to take advantage of
01:04:33.397 --> 01:04:35.393
computer technology moving forward.
01:04:35.393 --> 01:04:39.998
To get careful estimates: for going from 768 to 800,
01:04:39.998 --> 01:04:42.192
that's a short enough extrapolation
01:04:42.192 --> 01:04:44.113
that people are pretty confident about that.
01:04:44.113 --> 01:04:48.014
Getting to 900 starts getting iffy what exactly the cost would be
01:04:48.014 --> 01:04:50.951
and 1024 there's a fair amount of guess works.
01:04:50.951 --> 01:04:53.796
There is some consensus on rougly what the costs are
01:04:53.796 --> 01:04:55.429
but it's hard to say exactly.
01:04:55.429 --> 01:04:58.059
But again, to give you a scale of it:
01:04:58.059 --> 01:04:59.675
you were saying like 900 or 800.
01:04:59.675 --> 01:05:03.213
Well, 768 RSA challenge was done
01:05:03.213 --> 01:05:07.228
and that one was 1500 machine years.
01:05:07.228 --> 01:05:08.501
Male: Ok, thank you.
01:05:08.501 --> 01:05:10.260
Angel: We'll take four more questions.
01:05:10.260 --> 01:05:12.357
Signal angel first.
01:05:12.357 --> 01:05:16.676
*Signal angel*: It's a clarification of the question I asked before.
01:05:16.676 --> 01:05:22.278
The actual question is: how big will be the effort
01:05:22.278 --> 01:05:32.129
to upgrade existing keys from 1024 bits to 4K or 8K bits?
01:05:32.129 --> 01:05:35.984
Considering that the keys are currently in use
01:05:35.984 --> 01:05:37.910
how much effort worldwide would it be to
01:05:37.910 --> 01:05:41.608
upgrade all that to something more secure?
01:05:41.608 --> 01:05:43.559
Tanja: I mean, for the private user if you're running
01:05:43.559 --> 01:05:46.447
SSH on the laptop you can just generate a new key.
01:05:46.447 --> 01:05:47.876
Doesn't take you much time.
01:05:47.876 --> 01:05:50.345
You will notice maybe some degradation of performance
01:05:50.345 --> 01:05:52.193
if you're running it on a netbook
01:05:52.193 --> 01:05:54.755
but going to 2048 is not a big deal.
01:05:54.755 --> 01:05:57.710
However, there is a recommendation of the
01:05:57.710 --> 01:06:01.932
US government to stop using 1024 bit RSA as of 2010
01:06:01.932 --> 01:06:05.211
and we still see it everywhere.
01:06:05.211 --> 01:06:07.563
Apparently it is bigger effort than just
01:06:07.563 --> 01:06:10.743
everybody spending 10 minutes on the laptop.
01:06:10.743 --> 01:06:13.635
Dan: Maybe part of the problem is things like
01:06:13.635 --> 01:06:16.997
everybody says "yeah, use 2048 or bigger"
01:06:16.997 --> 01:06:18.884
and there's some financial standard
01:06:18.884 --> 01:06:21.157
which says you can use any key size you want
01:06:21.157 --> 01:06:23.943
up to 1984 bits.
01:06:23.943 --> 01:06:25.631
I have no idea how they came up with this
01:06:25.631 --> 01:06:27.208
but then they run into some other standard
01:06:27.208 --> 01:06:29.284
which says use 2048 and they just can't
01:06:29.284 --> 01:06:33.345
implement it on the smartcards which only support up to 1984.
01:06:33.345 --> 01:06:36.467
Now if you get the standards people talking to each other for several years
01:06:36.467 --> 01:06:39.258
then they agree on using 1984.
01:06:39.258 --> 01:06:41.796
It's just about as good as 2048
01:06:41.796 --> 01:06:44.746
but realistically when you have these conflicts
01:06:44.746 --> 01:06:47.128
in standards then it takes a while to work out.
01:06:47.128 --> 01:06:48.742
And when you have a busy server
01:06:48.742 --> 01:06:51.233
that's trying to do 2048 bit RSA
01:06:51.233 --> 01:06:53.126
it doesn't matter what the standard says
01:06:53.126 --> 01:06:55.449
if you got a ton of load you just can't handle that load
01:06:55.449 --> 01:06:58.341
if you're spending a ton of time on cryptography.
01:06:58.341 --> 01:07:00.460
And that again is where we like elliptic curves
01:07:00.460 --> 01:07:02.560
because they give you for whatever your
01:07:02.560 --> 01:07:05.341
performance constraints are much better security.
01:07:05.341 --> 01:07:07.309
So if you're trying a given security level
01:07:07.309 --> 01:07:09.831
the speed is much better.
01:07:09.831 --> 01:07:12.807
Angel: Next question will be from number 2.
01:07:12.807 --> 01:07:14.642
Female: So you've had two developers stand up
01:07:14.642 --> 01:07:17.459
and ask how to verify whether or not their
01:07:17.459 --> 01:07:19.726
key generation is correct and whether or not their
01:07:19.726 --> 01:07:21.490
random numbers are correct.
01:07:21.490 --> 01:07:23.887
And I think it's great that you give coding recommendations
01:07:23.887 --> 01:07:27.441
like seed rand() but coming from the development
01:07:27.441 --> 01:07:29.539
perspective I like to unit test my code
01:07:29.539 --> 01:07:31.789
and specifically I like to write my unit tests
01:07:31.789 --> 01:07:33.043
before I write my code,
01:07:33.043 --> 01:07:34.709
it's called test-driven development.
01:07:34.709 --> 01:07:38.175
So if I'm going about creating an algorithm to
01:07:38.175 --> 01:07:39.994
encrypt something or whatever
01:07:39.994 --> 01:07:42.771
what are the steps that I need to do
01:07:42.771 --> 01:07:46.653
when I'm writing my unit test?
01:07:46.653 --> 01:07:51.939
Has there been some kind of effort in that way
01:07:51.939 --> 01:07:54.911
like what goes into unit test for determining that
01:07:54.911 --> 01:07:56.606
your random number is correct?
01:07:56.606 --> 01:07:59.091
I mean there's algorithms for determining
01:07:59.091 --> 01:08:00.562
whether your random number generator is
01:08:00.562 --> 01:08:02.773
operating correctly, right?
01:08:02.773 --> 01:08:05.160
Dan: This is something where there is,
01:08:05.160 --> 01:08:07.775
if you look at how the random number generators work,
01:08:07.775 --> 01:08:10.209
there was just a NIST workshop
01:08:10.209 --> 01:08:11.975
and there's some NIST standards
01:08:11.975 --> 01:08:12.742
which are telling you
01:08:12.742 --> 01:08:15.709
here's what to do to test your random number generators.
01:08:15.709 --> 01:08:17.796
So you have a hardware random number generator,
01:08:17.796 --> 01:08:19.589
some post-processing, and they say
01:08:19.589 --> 01:08:22.406
"ok here's the standard for how to test those pieces"
01:08:22.406 --> 01:08:24.704
Now that's not the same as testing the cryptography
01:08:24.704 --> 01:08:26.335
that's using those pieces
01:08:26.335 --> 01:08:28.994
and it's very helpful if there's a clear separation there.
01:08:28.994 --> 01:08:30.463
So you have your cryptography
01:08:30.463 --> 01:08:32.746
which is doing deterministic stuff
01:08:32.746 --> 01:08:34.452
and says you have to have some randomness coming
01:08:34.452 --> 01:08:37.806
from a totally separate unit where the only job
01:08:37.806 --> 01:08:40.460
of that separate unit is do the randomness properly.
01:08:40.460 --> 01:08:42.146
And then the NIST test will tell you
01:08:42.146 --> 01:08:43.324
what the randomness does
01:08:43.324 --> 01:08:45.938
and then deterministic cryptographic testing
01:08:45.938 --> 01:08:48.391
will tell you that the other pieces are working correctly
01:08:48.391 --> 01:08:50.211
for all sorts of inputs.
01:08:50.211 --> 01:08:53.892
Where it goes wrong is something like the ECDSA standard
01:08:53.892 --> 01:08:55.394
that Nadia was mentioning before
01:08:55.394 --> 01:08:56.696
and that's one that says that
01:08:56.696 --> 01:08:59.210
you don't just deterministically generate a signature
01:08:59.210 --> 01:09:01.410
you make some new randomness every time you generate
01:09:01.410 --> 01:09:03.705
a signature and that's what goes horribly wrong.
01:09:03.705 --> 01:09:05.670
So that's something where we need new standards
01:09:05.670 --> 01:09:07.790
which say instead of doing what ECDSA does
01:09:07.790 --> 01:09:09.741
we have a clear separation between
01:09:09.741 --> 01:09:12.192
the cryptography always does the same thing
01:09:12.192 --> 01:09:15.043
making it testable, and then randomness is centralized
01:09:15.043 --> 01:09:17.541
in one spot which hopefully the NIST standards
01:09:17.541 --> 01:09:19.840
do a good enough job of testing.
01:09:19.840 --> 01:09:23.508
Female: So there's something that says here's what determines...
01:09:23.508 --> 01:09:26.946
I guess what I'm asking is do you know of any algorithms
01:09:26.946 --> 01:09:30.139
that can be used for determining whether something
01:09:30.139 --> 01:09:32.248
is a good random number and whether your random
01:09:32.248 --> 01:09:34.525
number generator is generating things properly?
01:09:34.525 --> 01:09:37.027
Tanja: Well, there are a bunch of tests for.
01:09:37.027 --> 01:09:39.307
There's hardware random number generators
01:09:39.307 --> 01:09:42.126
you can run them through the diehard tests.
01:09:42.126 --> 01:09:44.710
There's certificates by FIPS.
01:09:44.710 --> 01:09:48.526
In general I would recommend implementing all those steps
01:09:48.526 --> 01:09:50.811
but the smartcards that have been mentioned by Dan earlier
01:09:50.811 --> 01:09:52.742
from the Taiwan citizen card
01:09:52.742 --> 01:09:55.445
those are actually FIPS-certified.
01:09:55.445 --> 01:09:58.942
So even though, these go through what is the industry standard
01:09:58.942 --> 01:10:00.922
of doing random number generation on smartcards
01:10:00.922 --> 01:10:03.622
which everybody thought was good enough,
01:10:03.622 --> 01:10:04.979
apparently they're not.
01:10:04.979 --> 01:10:06.477
So randomness is a total mess.
01:10:06.477 --> 01:10:08.613
I mean after the paper by Nadia and
01:10:08.613 --> 01:10:10.410
also when the paper by the Lausanne team came out,
01:10:10.410 --> 01:10:12.692
there is no some more movement in finding
01:10:12.692 --> 01:10:14.023
better random number generators.
01:10:14.023 --> 01:10:18.659
At this moment, well, hope for the best.
01:10:18.659 --> 01:10:20.625
laughter
01:10:20.625 --> 01:10:22.178
Implement the standards, yes.
01:10:22.178 --> 01:10:24.672
If you have some source of randomness
01:10:24.672 --> 01:10:28.424
try to stretch it with a stream cipher or something like that.
01:10:28.424 --> 01:10:31.296
Nadia: I want to tell a little story.
01:10:31.296 --> 01:10:33.227
After we published the paper
01:10:33.227 --> 01:10:35.643
I heard some very interesting things from some of the vendors.
01:10:35.643 --> 01:10:39.329
I think one of the things that makes randomness
01:10:39.329 --> 01:10:42.206
and cryptography a difficult problem is that
01:10:42.206 --> 01:10:44.612
this kind of issue is something that
01:10:44.612 --> 01:10:46.808
crosses a lot of the abstraction boundaries
01:10:46.808 --> 01:10:48.546
that you're used to in coding.
01:10:48.546 --> 01:10:50.525
You want to have the clean unit test that you know
01:10:50.525 --> 01:10:52.343
that this piece works, and this piece works,
01:10:52.343 --> 01:10:53.923
and this piece works, and this piece works,
01:10:53.923 --> 01:10:57.777
and you put them all together and it will all work flawlessly.
01:10:57.777 --> 01:11:00.297
Somehow this kind of problem is something that
01:11:00.297 --> 01:11:02.898
happens at the boundaries of each unit test.
01:11:02.898 --> 01:11:05.223
We know that the operating system is like
01:11:05.223 --> 01:11:08.431
"ok I'm getting my proper inputs from the hardware
01:11:08.431 --> 01:11:11.297
and I'm correctly generating my randomness from there"
01:11:11.297 --> 01:11:12.840
and then the application says
01:11:12.840 --> 01:11:15.023
"I'm getting my randomness from the operating system,
01:11:15.023 --> 01:11:16.310
it's good randomness"
01:11:16.310 --> 01:11:19.605
and then the application uses the correct crypto algorithms
01:11:19.605 --> 01:11:21.927
to then do good cryptography.
01:11:21.927 --> 01:11:24.495
And at the very beginning of that stage
01:11:24.495 --> 01:11:27.777
there was something broken and it translated all the way
01:11:27.777 --> 01:11:29.526
through all of these pieces of software
01:11:29.526 --> 01:11:31.532
that were working correctly.
01:11:31.532 --> 01:11:35.415
Testing this holistically was the only way
01:11:35.415 --> 01:11:37.312
to find this kind of error.
01:11:37.312 --> 01:11:41.241
One story that I heard from a vendor was that
01:11:41.241 --> 01:11:43.911
they ran into randomness problems.
01:11:43.911 --> 01:11:45.745
They developed some device.
01:11:45.745 --> 01:11:47.325
It was working perfectly
01:11:47.325 --> 01:11:51.478
and on the assembly line they were being turned on
01:11:51.478 --> 01:11:55.497
and run through the checks.
01:11:55.497 --> 01:11:57.807
You boot it up it checks the integrity
01:11:57.807 --> 01:12:00.641
on the assembly line and it was continuing on.
01:12:00.641 --> 01:12:06.390
If you exactly booted them up at the exact same time
01:12:06.390 --> 01:12:10.129
in the exact same conditions
01:12:10.129 --> 01:12:13.221
then all of the inputs to the random number generator
01:12:13.221 --> 01:12:16.323
would be the same and they would generate the same keys
01:12:16.323 --> 01:12:17.743
and then these keys would be,
01:12:17.743 --> 01:12:19.721
you know, they already generated the keys,
01:12:19.721 --> 01:12:21.197
so they wouldn't generate them again after
01:12:21.197 --> 01:12:25.397
they went to the consumer.
01:12:25.397 --> 01:12:27.145
I don't know how to unit test that
01:12:27.145 --> 01:12:29.976
except take the entire device, turn it on,
01:12:29.976 --> 01:12:32.589
and take multiple of them and make sure the devices
01:12:32.589 --> 01:12:35.396
as they're coming out of the production process
01:12:35.396 --> 01:12:39.596
are working correctly.
01:12:39.596 --> 01:12:41.477
Angel: So we will take 2 more questions.
01:12:41.477 --> 01:12:46.692
One from number 4 first and then number 1 at the last.
01:12:46.692 --> 01:12:48.005
Male: How good, do you think,
01:12:48.005 --> 01:12:52.544
hardware-supported random number generators are
01:12:52.544 --> 01:12:53.432
after what you've just said?
01:12:53.432 --> 01:12:55.806
I think they're probably not good anymore?
01:12:55.806 --> 01:13:01.566
Dan: Intel has their RdRand instruction in some of the newer chips
01:13:01.566 --> 01:13:04.979
and they say that they've gone through
01:13:04.979 --> 01:13:06.957
a reasonable number of evaluation steps.
01:13:06.957 --> 01:13:09.442
It sounds like they're trying.
01:13:09.442 --> 01:13:11.826
Whether they're successful is a different question.
01:13:11.826 --> 01:13:13.661
Something I don't like about the API is
01:13:13.661 --> 01:13:16.392
RdRand gives you no way to test the pieces.
01:13:16.392 --> 01:13:18.798
You can only test the post-processed output.
01:13:18.798 --> 01:13:22.157
So nobody else is able to test the actual
01:13:22.157 --> 01:13:24.276
randomness generation part of the hardware.
01:13:24.276 --> 01:13:26.543
You can only get a filtered version of that.
01:13:26.543 --> 01:13:29.245
So Intel and people who are contracted by Intel
01:13:29.245 --> 01:13:30.628
to see what's going on inside
01:13:30.628 --> 01:13:32.829
are the only people who can run these tests.
01:13:32.829 --> 01:13:35.874
It's not open in a way that allows the community
01:13:35.874 --> 01:13:37.377
to see if there's further problems.
01:13:37.377 --> 01:13:38.756
But at least they're trying
01:13:38.756 --> 01:13:41.423
and maybe with enough effort the hardware manufacturers
01:13:41.423 --> 01:13:43.458
will get randomness generation right.
01:13:43.458 --> 01:13:47.579
Of course if you can generate any sort of secret once
01:13:47.579 --> 01:13:50.462
if you have enough of a secret to start with
01:13:50.462 --> 01:13:52.328
then you can use things like AES to
01:13:52.328 --> 01:13:53.944
generate any number of secrets
01:13:53.944 --> 01:13:55.494
and you can put those secrets into
01:13:55.494 --> 01:13:57.296
any number of devices that you want.
01:13:57.296 --> 01:13:59.594
If you use AES in counter mode with
01:13:59.594 --> 01:14:02.123
encrypting 1, encrypting 2, encrypting 3...
01:14:02.123 --> 01:14:04.981
you get totally unpredictable, unrelated outputs
01:14:04.981 --> 01:14:07.378
and then use those, burn those into some hardware.
01:14:07.378 --> 01:14:09.979
But where do you get that initial randomness from?
01:14:09.979 --> 01:14:12.830
Are you going through a trustworthy process there?
01:14:12.830 --> 01:14:16.308
It's a hard problem.
01:14:16.308 --> 01:14:18.198
Angel: Next question from number 1.
01:14:18.198 --> 01:14:19.729
And that's the last question.
01:14:19.729 --> 01:14:21.379
Male: You said something about
01:14:21.379 --> 01:14:24.799
you dropped this group-based cryptography word.
01:14:24.799 --> 01:14:28.111
Most of the stuff I've encountered under that heading
01:14:28.111 --> 01:14:30.008
kind of sounded like snake oil
01:14:30.008 --> 01:14:32.898
just cause they're using non-abelian groups and stuff.
01:14:32.898 --> 01:14:35.832
Is there anything here that isn't?
01:14:35.832 --> 01:14:38.280
Tanja: Ok, I did not say group-based crypto.
01:14:38.280 --> 01:14:38.914
Male: Ok.
01:14:38.914 --> 01:14:40.259
Tanja: I said code-based cryptography.
01:14:40.259 --> 01:14:41.241
Male: Sorry, thanks.
01:14:41.241 --> 01:14:42.773
Tanja: So there is a class of cryptosystems
01:14:42.773 --> 01:14:44.826
which are fine against quantum computers.
01:14:44.826 --> 01:14:50.148
For all crypto it's always up to what we know.
01:14:50.148 --> 01:14:51.959
Next day, there could be somebody with a
01:14:51.959 --> 01:14:54.009
polynomial-time factor algorithm and so on.
01:14:54.009 --> 01:14:56.723
Now there's also a group of people doing
01:14:56.723 --> 01:14:59.357
braid group cryptography, doing non-abelian groups,
01:14:59.357 --> 01:15:01.764
most of these systems have been broken.
01:15:01.764 --> 01:15:07.083
If they weren't broken by classical computers
01:15:07.083 --> 01:15:10.911
maybe they would remain secure against quantum computers.
01:15:10.911 --> 01:15:13.828
It's lots of "would"s there.
01:15:13.828 --> 01:15:17.612
Yes, they might have this on their flags as well
01:15:17.612 --> 01:15:20.547
but I wouldn't count this as a secure system.
01:15:20.547 --> 01:15:23.027
Whereas code-based cryptography or lattice-based cryptography
01:15:23.027 --> 01:15:26.480
are systems which should be fine.
01:15:26.480 --> 01:15:28.646
Dan: Maybe just a URL if you're interested
01:15:28.646 --> 01:15:31.939
in post-quantum cryptography is pqcrypto.org
01:15:31.939 --> 01:15:34.513
and that keeps track of papers on the various types
01:15:34.513 --> 01:15:37.227
of cryptography that should survive for a 100 years
01:15:37.227 --> 01:15:41.448
and in particular against quantum computers.
01:15:41.448 --> 01:15:42.444
Angel: Ladies and gentleman, please give
01:15:42.444 --> 01:15:46.546
Nadia, Tanja and Daniel a big round of applause.
01:15:46.546 --> 01:15:47.714
Thank you so much.
01:15:47.714 --> 01:15:56.643
applause