[Script Info] Title: [Events] Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text Dialogue: 0,0:00:08.96,0:00:11.64,Default,,0000,0000,0000,,Today we have Daniel J. Bernstein, Dialogue: 0,0:00:11.64,0:00:14.54,Default,,0000,0000,0000,,Nadia Heninger, Dialogue: 0,0:00:14.54,0:00:16.89,Default,,0000,0000,0000,,and Tanja Lange. Dialogue: 0,0:00:16.89,0:00:20.40,Default,,0000,0000,0000,,And they will talk about RSA factorization in the real world. Dialogue: 0,0:00:20.40,0:00:22.29,Default,,0000,0000,0000,,Talk is called FactHacks. Dialogue: 0,0:00:22.29,0:00:29.90,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:00:29.90,0:00:31.59,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: Thank you. Dialogue: 0,0:00:31.59,0:00:37.09,Default,,0000,0000,0000,,So we're going to start with a crypto lecture in 5 minutes. Dialogue: 0,0:00:37.09,0:00:40.56,Default,,0000,0000,0000,,So, just to begin, since we're talking about RSA. Dialogue: 0,0:00:40.56,0:00:43.68,Default,,0000,0000,0000,,Here is a picture of RSA for you. Dialogue: 0,0:00:43.68,0:00:48.60,Default,,0000,0000,0000,,RSA is the first published public-key cryptosystem. Dialogue: 0,0:00:48.60,0:00:51.22,Default,,0000,0000,0000,,So by a public-key cryptosystem, what I mean is Dialogue: 0,0:00:51.22,0:00:54.17,Default,,0000,0000,0000,,a cryptosystem that has two keys intead of just having Dialogue: 0,0:00:54.17,0:00:56.89,Default,,0000,0000,0000,,one key. You might think "ok you encrypt a message Dialogue: 0,0:00:56.89,0:00:59.04,Default,,0000,0000,0000,,to that key and you decrypt a message to that key" Dialogue: 0,0:00:59.04,0:01:01.40,Default,,0000,0000,0000,,That is a symmetric cryptosystem. Dialogue: 0,0:01:01.40,0:01:03.19,Default,,0000,0000,0000,,A public-key cryptosystem has two keys. Dialogue: 0,0:01:03.19,0:01:06.04,Default,,0000,0000,0000,,One is the public key and one is the private key. Dialogue: 0,0:01:06.04,0:01:07.69,Default,,0000,0000,0000,,The public key you publish to the world and Dialogue: 0,0:01:07.69,0:01:09.51,Default,,0000,0000,0000,,anyone can use that key to encrypt a message, Dialogue: 0,0:01:09.51,0:01:10.81,Default,,0000,0000,0000,,especially to you. Dialogue: 0,0:01:10.81,0:01:14.10,Default,,0000,0000,0000,,And only you, who have the private key, can decrypt that. Dialogue: 0,0:01:14.10,0:01:18.74,Default,,0000,0000,0000,,So the RSA paper was the first published public-key cryptosystem. Dialogue: 0,0:01:18.74,0:01:20.50,Default,,0000,0000,0000,,That was in 1977. Dialogue: 0,0:01:20.50,0:01:22.76,Default,,0000,0000,0000,,This revolutionized cryptography and enabled Dialogue: 0,0:01:22.76,0:01:25.54,Default,,0000,0000,0000,,the development of the Internet. Dialogue: 0,0:01:25.54,0:01:31.57,Default,,0000,0000,0000,,So 35 years later RSA is still the most commonly used public-key cryptosystem. Dialogue: 0,0:01:31.57,0:01:35.87,Default,,0000,0000,0000,,If you ever use the Internet, you probably use it every day. Dialogue: 0,0:01:35.87,0:01:42.15,Default,,0000,0000,0000,,So here is a sample SSL certificate which uses RSA. Dialogue: 0,0:01:42.15,0:01:45.24,Default,,0000,0000,0000,,If you use SSH you probably have an SSH key Dialogue: 0,0:01:45.24,0:01:48.44,Default,,0000,0000,0000,,which probably is RSA. Dialogue: 0,0:01:48.44,0:01:51.86,Default,,0000,0000,0000,,Before I launch into the math Dialogue: 0,0:01:51.86,0:01:54.68,Default,,0000,0000,0000,,I want to explain what we're doing here. Dialogue: 0,0:01:54.68,0:01:56.74,Default,,0000,0000,0000,,We wanted to, since you guys are hackers, Dialogue: 0,0:01:56.74,0:01:59.87,Default,,0000,0000,0000,,you like code instead of formulas Dialogue: 0,0:01:59.87,0:02:02.78,Default,,0000,0000,0000,,so we wanted to give you formulas in code. Dialogue: 0,0:02:02.78,0:02:05.46,Default,,0000,0000,0000,,So what we're giving you is working Python code for Dialogue: 0,0:02:05.46,0:02:07.72,Default,,0000,0000,0000,,all the math that we're going to do. Dialogue: 0,0:02:07.72,0:02:09.98,Default,,0000,0000,0000,,And in order to do that we're going to use Dialogue: 0,0:02:09.98,0:02:12.64,Default,,0000,0000,0000,,some software you call Sage. Dialogue: 0,0:02:12.64,0:02:15.97,Default,,0000,0000,0000,,Sage is free open-source mathematics software. Dialogue: 0,0:02:15.97,0:02:20.16,Default,,0000,0000,0000,,It is available at this URL sagemath.org. Dialogue: 0,0:02:20.16,0:02:22.09,Default,,0000,0000,0000,,It's based off of Python Dialogue: 0,0:02:22.09,0:02:24.19,Default,,0000,0000,0000,,so it's very simple if you know Python. Dialogue: 0,0:02:24.19,0:02:27.90,Default,,0000,0000,0000,,It has a nice sort of interpreter Dialogue: 0,0:02:27.90,0:02:29.62,Default,,0000,0000,0000,,that you can use just like Python. Dialogue: 0,0:02:29.62,0:02:32.49,Default,,0000,0000,0000,,Here an example, 2*3=6. Dialogue: 0,0:02:32.49,0:02:34.89,Default,,0000,0000,0000,,But there are some differences. Dialogue: 0,0:02:34.89,0:02:38.20,Default,,0000,0000,0000,,For example the caret instead of in Python it's XOR Dialogue: 0,0:02:38.20,0:02:40.16,Default,,0000,0000,0000,,in Sage it's exponentiation. Dialogue: 0,0:02:40.16,0:02:43.87,Default,,0000,0000,0000,,So 2^3 is 8 in Sage. Dialogue: 0,0:02:43.87,0:02:47.35,Default,,0000,0000,0000,,The other nice thing about Sage is that Dialogue: 0,0:02:47.35,0:02:49.70,Default,,0000,0000,0000,,it has lots of useful mathematical libraries. Dialogue: 0,0:02:49.70,0:02:53.03,Default,,0000,0000,0000,,For example if I, in the Sage interpreter, say factor(15) Dialogue: 0,0:02:53.03,0:02:55.51,Default,,0000,0000,0000,,it helpfully tells me 3*5. Dialogue: 0,0:02:55.51,0:02:56.51,Default,,0000,0000,0000,,That's pretty great. Dialogue: 0,0:02:56.51,0:02:59.15,Default,,0000,0000,0000,,It also does a lot more advanced things, for example Dialogue: 0,0:02:59.15,0:03:00.47,Default,,0000,0000,0000,,it can represent polynomials. Dialogue: 0,0:03:00.47,0:03:03.50,Default,,0000,0000,0000,,I can say factor the polynomial x^2-1 Dialogue: 0,0:03:03.50,0:03:08.13,Default,,0000,0000,0000,,and it helpfully tells me the answer to that. Dialogue: 0,0:03:08.13,0:03:12.82,Default,,0000,0000,0000,,So now that we've gone through what is Sage, Dialogue: 0,0:03:12.82,0:03:17.44,Default,,0000,0000,0000,,I want to explain how to do RSA. Dialogue: 0,0:03:17.44,0:03:21.06,Default,,0000,0000,0000,,Perhaps some of you have seen this before. Dialogue: 0,0:03:21.06,0:03:24.68,Default,,0000,0000,0000,,In order to generate an RSA key, the first thing that you do Dialogue: 0,0:03:24.68,0:03:27.44,Default,,0000,0000,0000,,is you generate two large random primes. Dialogue: 0,0:03:27.44,0:03:30.44,Default,,0000,0000,0000,,So if we want a 1024 bit RSA key Dialogue: 0,0:03:30.44,0:03:34.78,Default,,0000,0000,0000,,we generate two primes of size 2^512, Dialogue: 0,0:03:34.78,0:03:38.52,Default,,0000,0000,0000,,so 512 bit primes, p and q. Dialogue: 0,0:03:38.52,0:03:41.70,Default,,0000,0000,0000,,In order to generate the public key Dialogue: 0,0:03:41.70,0:03:44.90,Default,,0000,0000,0000,,I multiply together p and q and you get some N. Dialogue: 0,0:03:44.90,0:03:46.43,Default,,0000,0000,0000,,N has 1024 bits. Dialogue: 0,0:03:46.43,0:03:49.92,Default,,0000,0000,0000,,And then you have what's known as the public exponent Dialogue: 0,0:03:49.92,0:03:54.44,Default,,0000,0000,0000,,which you can choose 3 or 65537 or 35. Dialogue: 0,0:03:54.44,0:03:56.30,Default,,0000,0000,0000,,It really doesn't matter what you choose. Dialogue: 0,0:03:56.30,0:03:59.12,Default,,0000,0000,0000,,These are some of the most commonly used values. Dialogue: 0,0:03:59.12,0:04:03.13,Default,,0000,0000,0000,,Now in order to generate a private key Dialogue: 0,0:04:03.13,0:04:07.70,Default,,0000,0000,0000,,you choose d, the decryption exponent, Dialogue: 0,0:04:07.70,0:04:12.94,Default,,0000,0000,0000,,to be the modular inverse of e mod (p-1)*(q-1) Dialogue: 0,0:04:12.94,0:04:15.39,Default,,0000,0000,0000,,It doesn't matter why so much, for this talk Dialogue: 0,0:04:15.39,0:04:17.28,Default,,0000,0000,0000,,but here is the formula Dialogue: 0,0:04:17.28,0:04:20.30,Default,,0000,0000,0000,,or here is the command to do this in Sage. Dialogue: 0,0:04:20.30,0:04:23.15,Default,,0000,0000,0000,,So now we have a public key and a private key Dialogue: 0,0:04:23.15,0:04:24.51,Default,,0000,0000,0000,,that are pairs. Dialogue: 0,0:04:24.51,0:04:27.95,Default,,0000,0000,0000,,And in RSA if you want to enrypt a message Dialogue: 0,0:04:27.95,0:04:31.55,Default,,0000,0000,0000,,you raise your message to the e'th power mod n Dialogue: 0,0:04:31.55,0:04:34.75,Default,,0000,0000,0000,,so you can do that with your public key here. Dialogue: 0,0:04:34.75,0:04:36.78,Default,,0000,0000,0000,,And similarly decryption, Dialogue: 0,0:04:36.78,0:04:39.100,Default,,0000,0000,0000,,you raise the ciphertext to the d'th power mod n Dialogue: 0,0:04:39.100,0:04:42.84,Default,,0000,0000,0000,,and that will give you the message back out again. Dialogue: 0,0:04:42.84,0:04:45.75,Default,,0000,0000,0000,,Fairly simple. Dialogue: 0,0:04:45.75,0:04:48.73,Default,,0000,0000,0000,,Now I'm lying to you slightly. Dialogue: 0,0:04:48.73,0:04:51.09,Default,,0000,0000,0000,,If you read this talk do not Dialogue: 0,0:04:51.09,0:04:53.18,Default,,0000,0000,0000,,absolutely do {\b1}not{\b0} implement RSA this way. Dialogue: 0,0:04:53.18,0:04:54.76,Default,,0000,0000,0000,,You {\b1}must{\b0} pad your message. Dialogue: 0,0:04:54.76,0:04:57.19,Default,,0000,0000,0000,,This is a public service warning. Dialogue: 0,0:04:57.19,0:05:00.66,Default,,0000,0000,0000,,We offered to tell you about factoring. Dialogue: 0,0:05:00.66,0:05:03.94,Default,,0000,0000,0000,,What is the relationship between RSA and factoring? Dialogue: 0,0:05:03.94,0:05:08.97,Default,,0000,0000,0000,,Now you can see easily from the formula Dialogue: 0,0:05:08.97,0:05:11.76,Default,,0000,0000,0000,,from the private key here Dialogue: 0,0:05:11.76,0:05:16.34,Default,,0000,0000,0000,,that if you know how to factor N into its prime factors p and q Dialogue: 0,0:05:16.34,0:05:19.50,Default,,0000,0000,0000,,then you can just compute d, the decryption exponent Dialogue: 0,0:05:19.50,0:05:20.81,Default,,0000,0000,0000,,of your private key. Dialogue: 0,0:05:20.81,0:05:24.40,Default,,0000,0000,0000,,Clearly, if you can factor N you can compute the private key. Dialogue: 0,0:05:24.40,0:05:28.93,Default,,0000,0000,0000,,But we don't actually know that factoring is the only way to break RSA. Dialogue: 0,0:05:28.93,0:05:34.16,Default,,0000,0000,0000,,There might be some way that you can compute messages from ciphertexts Dialogue: 0,0:05:34.16,0:05:36.88,Default,,0000,0000,0000,,that doesn't actually reveal the private key. Dialogue: 0,0:05:36.88,0:05:41.54,Default,,0000,0000,0000,,And there's no proof either way that this is or is not possible. Dialogue: 0,0:05:41.54,0:05:43.48,Default,,0000,0000,0000,,The last thing that I want to mention here Dialogue: 0,0:05:43.48,0:05:45.46,Default,,0000,0000,0000,,just to clarify things Dialogue: 0,0:05:45.46,0:05:46.83,Default,,0000,0000,0000,,some of you who might have taken Dialogue: 0,0:05:46.83,0:05:51.53,Default,,0000,0000,0000,,complexity or algorithms courses or a beginning CS course Dialogue: 0,0:05:51.53,0:05:55.87,Default,,0000,0000,0000,,you might have heard of NP-hardness, the P vs. NP problem. Dialogue: 0,0:05:55.87,0:06:00.90,Default,,0000,0000,0000,,And I just want to clarify that factoring is not known to be NP-hard. Dialogue: 0,0:06:00.90,0:06:05.09,Default,,0000,0000,0000,,Every computer scientist will love it if we could actually generate Dialogue: 0,0:06:05.09,0:06:11.14,Default,,0000,0000,0000,,a cryptosystem which is known to be based of average case NP-hardness. Dialogue: 0,0:06:11.14,0:06:13.57,Default,,0000,0000,0000,,We don't know how to do that. Dialogue: 0,0:06:13.57,0:06:16.99,Default,,0000,0000,0000,,RSA is not doing that. Dialogue: 0,0:06:16.99,0:06:22.31,Default,,0000,0000,0000,,In addition the factoring problem is probably not NP-hard. Dialogue: 0,0:06:22.31,0:06:25.89,Default,,0000,0000,0000,,The question is: how hard {\b1}is{\b0} factoring? Dialogue: 0,0:06:25.89,0:06:27.47,Default,,0000,0000,0000,,Since factoring is the best way that we know Dialogue: 0,0:06:27.47,0:06:31.23,Default,,0000,0000,0000,,to break the most commonly used public-key cryptosystem on the Internet. Dialogue: 0,0:06:31.23,0:06:32.94,Default,,0000,0000,0000,,Well I showed you some examples before Dialogue: 0,0:06:32.94,0:06:37.24,Default,,0000,0000,0000,,where Sage had this helpful little factor function. Dialogue: 0,0:06:37.24,0:06:39.16,Default,,0000,0000,0000,,So how well does it work? Dialogue: 0,0:06:39.16,0:06:41.18,Default,,0000,0000,0000,,How long do people think this takes? Dialogue: 0,0:06:41.18,0:06:46.15,Default,,0000,0000,0000,,two 32 bit integers multiplied together. Dialogue: 0,0:06:46.15,0:06:48.85,Default,,0000,0000,0000,,I heard it'll go a couple of seconds. Dialogue: 0,0:06:48.85,0:06:50.10,Default,,0000,0000,0000,,0.01 seconds. Dialogue: 0,0:06:50.10,0:06:55.11,Default,,0000,0000,0000,,This is on {\i1}this{\i0} computer. Dialogue: 0,0:06:55.11,0:06:57.87,Default,,0000,0000,0000,,How about 64 bit integers, two of them multiplied together? Dialogue: 0,0:06:57.87,0:07:01.29,Default,,0000,0000,0000,,So this is a 128 bit RSA modulus. Dialogue: 0,0:07:01.29,0:07:04.38,Default,,0000,0000,0000,,Any guesses? Dialogue: 0,0:07:04.38,0:07:05.46,Default,,0000,0000,0000,,One minute? Dialogue: 0,0:07:05.46,0:07:08.24,Default,,0000,0000,0000,,Nope, 0.1 seconds. Dialogue: 0,0:07:08.24,0:07:14.52,Default,,0000,0000,0000,,How about two 96 bit integers multiplied together? Dialogue: 0,0:07:14.52,0:07:15.94,Default,,0000,0000,0000,,A couple of minutes? Dialogue: 0,0:07:15.94,0:07:18.10,Default,,0000,0000,0000,,4 seconds. Dialogue: 0,0:07:18.10,0:07:21.96,Default,,0000,0000,0000,,How about two 128 bit integers multiplied together? Dialogue: 0,0:07:21.96,0:07:28.26,Default,,0000,0000,0000,,This is a 256 bit RSA modulus. Dialogue: 0,0:07:28.26,0:07:29.30,Default,,0000,0000,0000,,No guesses? Alright. Dialogue: 0,0:07:29.30,0:07:30.43,Default,,0000,0000,0000,,500 seconds. Dialogue: 0,0:07:30.43,0:07:32.79,Default,,0000,0000,0000,,So at this point it's starting to get a little bit iffy if I'm Dialogue: 0,0:07:32.79,0:07:36.33,Default,,0000,0000,0000,,sitting on a plane trying to do this on battery power. Dialogue: 0,0:07:36.33,0:07:39.25,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:07:39.25,0:07:43.76,Default,,0000,0000,0000,,Clearly this is growing faster than linear in the size of the key. Dialogue: 0,0:07:43.76,0:07:45.60,Default,,0000,0000,0000,,So what is actually going on? Dialogue: 0,0:07:45.60,0:07:49.07,Default,,0000,0000,0000,,Well. Dialogue: 0,0:07:49.07,0:07:50.73,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Ok. Dialogue: 0,0:07:50.73,0:07:52.79,Default,,0000,0000,0000,,Turns out these factoring functions Dialogue: 0,0:07:52.79,0:07:54.60,Default,,0000,0000,0000,,they do look like they're getting pretty slow but Dialogue: 0,0:07:54.60,0:07:56.84,Default,,0000,0000,0000,,wait a minute. Dialogue: 0,0:07:56.84,0:07:59.81,Default,,0000,0000,0000,,Do we actually have to use this factor function Dialogue: 0,0:07:59.81,0:08:00.87,Default,,0000,0000,0000,,if it's getting really slow? Dialogue: 0,0:08:00.87,0:08:04.30,Default,,0000,0000,0000,,Maybe instead of trying to use Sage's factor function Dialogue: 0,0:08:04.30,0:08:08.71,Default,,0000,0000,0000,,maybe we could just guess what the prime was. Dialogue: 0,0:08:08.71,0:08:12.35,Default,,0000,0000,0000,,Now as an RSA user you might not think that this is a threat Dialogue: 0,0:08:12.35,0:08:13.93,Default,,0000,0000,0000,,having somebody guess your prime Dialogue: 0,0:08:13.93,0:08:17.11,Default,,0000,0000,0000,,because there is some way to count the number of primes, Dialogue: 0,0:08:17.11,0:08:18.72,Default,,0000,0000,0000,,number of 512 bit primes and there's Dialogue: 0,0:08:18.72,0:08:22.18,Default,,0000,0000,0000,,more than 2^500 512 bit primes. Dialogue: 0,0:08:22.18,0:08:24.01,Default,,0000,0000,0000,,And if your random number generator is giving you Dialogue: 0,0:08:24.01,0:08:27.10,Default,,0000,0000,0000,,any of those 512 bit primes with the same chance Dialogue: 0,0:08:27.10,0:08:30.83,Default,,0000,0000,0000,,then any particular prime that the attacker guesses Dialogue: 0,0:08:30.83,0:08:32.84,Default,,0000,0000,0000,,and just tries dividing n by that, Dialogue: 0,0:08:32.84,0:08:35.06,Default,,0000,0000,0000,,see if it's evenly divisable, well Dialogue: 0,0:08:35.06,0:08:39.42,Default,,0000,0000,0000,,any particular prime has only a 2^(-500) chance Dialogue: 0,0:08:39.42,0:08:41.31,Default,,0000,0000,0000,,of being guessed by the attacker. Dialogue: 0,0:08:41.31,0:08:43.32,Default,,0000,0000,0000,,And even if the attacker tries a huge number of times Dialogue: 0,0:08:43.32,0:08:44.90,Default,,0000,0000,0000,,he'll never guess your prime Dialogue: 0,0:08:44.90,0:08:47.62,Default,,0000,0000,0000,,except what if your random number generator Dialogue: 0,0:08:47.62,0:08:52.03,Default,,0000,0000,0000,,is working really really badly and doesn't give you 2^500 different primes? Dialogue: 0,0:08:52.03,0:08:55.90,Default,,0000,0000,0000,,What if it only gives you, say, 2^40 different primes? Dialogue: 0,0:08:55.90,0:08:58.06,Default,,0000,0000,0000,,And then suddenly the attacker could, well, Dialogue: 0,0:08:58.06,0:09:01.25,Default,,0000,0000,0000,,try figuring out what those primes are. Dialogue: 0,0:09:01.25,0:09:03.24,Default,,0000,0000,0000,,So here's how the attacker looks at this. Dialogue: 0,0:09:03.24,0:09:05.82,Default,,0000,0000,0000,,The attacker says: ok I'm gonna target your public key. Dialogue: 0,0:09:05.82,0:09:08.88,Default,,0000,0000,0000,,I'm gonna take your big N which is your secret... Dialogue: 0,0:09:08.88,0:09:10.91,Default,,0000,0000,0000,,sorry, public key is big N, Dialogue: 0,0:09:10.91,0:09:13.67,Default,,0000,0000,0000,,your secret key p times your secret key q, Dialogue: 0,0:09:13.67,0:09:14.92,Default,,0000,0000,0000,,your private p and q. Dialogue: 0,0:09:14.92,0:09:16.76,Default,,0000,0000,0000,,He's trying to figure out the p and q, given N. Dialogue: 0,0:09:16.76,0:09:20.17,Default,,0000,0000,0000,,So what he does, he takes a bunch of devices that are out there Dialogue: 0,0:09:20.17,0:09:22.90,Default,,0000,0000,0000,,and he looks at how they work Dialogue: 0,0:09:22.90,0:09:25.28,Default,,0000,0000,0000,,or downloads a bunch of software which generates keys Dialogue: 0,0:09:25.28,0:09:28.90,Default,,0000,0000,0000,,and then using that software, using those devices Dialogue: 0,0:09:28.90,0:09:32.22,Default,,0000,0000,0000,,he tries generating a bunch of p's and q's for himself Dialogue: 0,0:09:32.22,0:09:34.52,Default,,0000,0000,0000,,using whatever the random number generator is Dialogue: 0,0:09:34.52,0:09:36.93,Default,,0000,0000,0000,,in that device or in that software. Dialogue: 0,0:09:36.93,0:09:38.40,Default,,0000,0000,0000,,And then that's something which Dialogue: 0,0:09:38.40,0:09:40.68,Default,,0000,0000,0000,,maybe the random number generator works really badly Dialogue: 0,0:09:40.68,0:09:42.83,Default,,0000,0000,0000,,and maybe you're using that device, too. Dialogue: 0,0:09:42.83,0:09:45.76,Default,,0000,0000,0000,,So the attacker tries each of the primes that he see's Dialogue: 0,0:09:45.76,0:09:46.92,Default,,0000,0000,0000,,from this device Dialogue: 0,0:09:46.92,0:09:50.13,Default,,0000,0000,0000,,and tries seeing does that prime divide your N. Dialogue: 0,0:09:50.13,0:09:51.40,Default,,0000,0000,0000,,If you were using that device Dialogue: 0,0:09:51.40,0:09:52.93,Default,,0000,0000,0000,,and it doesn't generate very many primes Dialogue: 0,0:09:52.93,0:09:55.84,Default,,0000,0000,0000,,then maybe he gets lucky and finds your prime Dialogue: 0,0:09:55.84,0:09:57.97,Default,,0000,0000,0000,,because the device has generated the same prime for him Dialogue: 0,0:09:57.97,0:09:59.62,Default,,0000,0000,0000,,that it generated for you. Dialogue: 0,0:09:59.62,0:10:03.22,Default,,0000,0000,0000,,Now does anybody actually build devices which Dialogue: 0,0:10:03.22,0:10:07.00,Default,,0000,0000,0000,,screw up random numbers this badly? Dialogue: 0,0:10:07.00,0:10:08.52,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:10:08.52,0:10:11.54,Default,,0000,0000,0000,,As a matter of fact, yes, bears do shit in the woods. Dialogue: 0,0:10:11.54,0:10:13.54,Default,,0000,0000,0000,,So there are some famous examples. Dialogue: 0,0:10:13.54,0:10:16.95,Default,,0000,0000,0000,,We don't have a huge number of historical discussions in this talk Dialogue: 0,0:10:16.95,0:10:18.54,Default,,0000,0000,0000,,but just a few examples here. Dialogue: 0,0:10:18.54,0:10:22.40,Default,,0000,0000,0000,,Goldberg&Wagner totally broke the original Netscape Dialogue: 0,0:10:22.40,0:10:23.99,Default,,0000,0000,0000,,generation of public keys. Dialogue: 0,0:10:23.99,0:10:26.92,Default,,0000,0000,0000,,There are only something like 2^47 possible keys Dialogue: 0,0:10:26.92,0:10:29.22,Default,,0000,0000,0000,,which is a countable numbers. Dialogue: 0,0:10:29.22,0:10:31.08,Default,,0000,0000,0000,,So they could figure out all the possible keys Dialogue: 0,0:10:31.08,0:10:34.14,Default,,0000,0000,0000,,that Netscape could generate if they you knew when you generated a key Dialogue: 0,0:10:34.14,0:10:35.80,Default,,0000,0000,0000,,which was often very predictable. Dialogue: 0,0:10:35.80,0:10:37.72,Default,,0000,0000,0000,,Another example: the Debian bug, Dialogue: 0,0:10:37.72,0:10:40.97,Default,,0000,0000,0000,,the horrendous failure for SSH and lots of other applications Dialogue: 0,0:10:40.97,0:10:42.42,Default,,0000,0000,0000,,from a few years ago. Dialogue: 0,0:10:42.42,0:10:45.69,Default,,0000,0000,0000,,Debian and Ubuntu for a year and half were generating only Dialogue: 0,0:10:45.69,0:10:48.77,Default,,0000,0000,0000,,well, fewer than a million possible public keys. Dialogue: 0,0:10:48.77,0:10:51.42,Default,,0000,0000,0000,,So complete disasters of random number generation. Dialogue: 0,0:10:51.42,0:10:53.83,Default,,0000,0000,0000,,But if you want to add to this list, Dialogue: 0,0:10:53.83,0:10:55.20,Default,,0000,0000,0000,,if you want to do more and more of these Dialogue: 0,0:10:55.20,0:10:56.97,Default,,0000,0000,0000,,find bad random number generators Dialogue: 0,0:10:56.97,0:11:00.52,Default,,0000,0000,0000,,you have to say "ok what's the next device out there Dialogue: 0,0:11:00.52,0:11:01.86,Default,,0000,0000,0000,,that might have been screwed up." Dialogue: 0,0:11:01.86,0:11:03.42,Default,,0000,0000,0000,,"Let's look at it, look at the code." Dialogue: 0,0:11:03.42,0:11:05.04,Default,,0000,0000,0000,,"See what kind of primes it generates." Dialogue: 0,0:11:05.04,0:11:06.57,Default,,0000,0000,0000,,"Does it do badly?" Dialogue: 0,0:11:06.57,0:11:09.42,Default,,0000,0000,0000,,It takes some real work to figure this out. Dialogue: 0,0:11:09.42,0:11:11.80,Default,,0000,0000,0000,,Wouldn't it be nice if there was a systematic way Dialogue: 0,0:11:11.80,0:11:14.59,Default,,0000,0000,0000,,to just without having to do a lot of work, Dialogue: 0,0:11:14.59,0:11:16.58,Default,,0000,0000,0000,,to look at each device, each piece of software, Dialogue: 0,0:11:16.58,0:11:18.40,Default,,0000,0000,0000,,wouldn't it be nice to just figure out Dialogue: 0,0:11:18.40,0:11:21.57,Default,,0000,0000,0000,,"oh yeah, let's just magically figure out Dialogue: 0,0:11:21.57,0:11:23.73,Default,,0000,0000,0000,,if there's any primes out there generated Dialogue: 0,0:11:23.73,0:11:25.51,Default,,0000,0000,0000,,from bad random number generators." Dialogue: 0,0:11:25.51,0:11:28.02,Default,,0000,0000,0000,,You could imagine here's the easy attack. Dialogue: 0,0:11:28.02,0:11:29.62,Default,,0000,0000,0000,,Here's the systematic way to do this. Dialogue: 0,0:11:29.62,0:11:34.05,Default,,0000,0000,0000,,You take two users, so you and you. Dialogue: 0,0:11:34.05,0:11:35.44,Default,,0000,0000,0000,,And you each have a public key. Dialogue: 0,0:11:35.44,0:11:37.18,Default,,0000,0000,0000,,We're gonna grab those public keys Dialogue: 0,0:11:37.18,0:11:41.68,Default,,0000,0000,0000,,N1 and N2 Dialogue: 0,0:11:41.68,0:11:46.98,Default,,0000,0000,0000,,and then hope that this N1 and N2 share a prime. Dialogue: 0,0:11:46.98,0:11:54.13,Default,,0000,0000,0000,,N1 is some prime p times some q1 and N2 is some same prime p times a different q2. Dialogue: 0,0:11:54.13,0:11:55.66,Default,,0000,0000,0000,,Now this could happen, you could have Dialogue: 0,0:11:55.66,0:11:59.10,Default,,0000,0000,0000,,N1 and N2 sharing both primes. Dialogue: 0,0:11:59.10,0:12:02.10,Default,,0000,0000,0000,,That would be legitimate that two people who are actually Dialogue: 0,0:12:02.10,0:12:05.64,Default,,0000,0000,0000,,the same webserver sharing their keys, sharing their certificates, Dialogue: 0,0:12:05.64,0:12:06.84,Default,,0000,0000,0000,,they know they're doing this, Dialogue: 0,0:12:06.84,0:12:09.28,Default,,0000,0000,0000,,you can get the same public key from two places. Dialogue: 0,0:12:09.28,0:12:12.18,Default,,0000,0000,0000,,Google has their keys copied to tens of thousands of servers, Dialogue: 0,0:12:12.18,0:12:13.40,Default,,0000,0000,0000,,that's not a surprise. Dialogue: 0,0:12:13.40,0:12:15.40,Default,,0000,0000,0000,,But if there's a different... Dialogue: 0,0:12:15.40,0:12:16.100,Default,,0000,0000,0000,,If you have two different public keys Dialogue: 0,0:12:16.100,0:12:18.43,Default,,0000,0000,0000,,they shouldn't be sharing primes. Dialogue: 0,0:12:18.43,0:12:19.58,Default,,0000,0000,0000,,What if they do? Dialogue: 0,0:12:19.58,0:12:21.98,Default,,0000,0000,0000,,Well, here's this magic Euclid's algorithm Dialogue: 0,0:12:21.98,0:12:24.74,Default,,0000,0000,0000,,which will just print out the shared prime p. Dialogue: 0,0:12:24.74,0:12:26.07,Default,,0000,0000,0000,,This is a very simple algorithm. Dialogue: 0,0:12:26.07,0:12:28.50,Default,,0000,0000,0000,,It just takes one of the numbers, say N1 Dialogue: 0,0:12:28.50,0:12:31.96,Default,,0000,0000,0000,,and let's say N1 is the smaller one and N2 is the bigger one, Dialogue: 0,0:12:31.96,0:12:34.14,Default,,0000,0000,0000,,it divides N2 by N1 Dialogue: 0,0:12:34.14,0:12:37.51,Default,,0000,0000,0000,,and replaces N2 by the remainder and then switches the numbers Dialogue: 0,0:12:37.51,0:12:39.59,Default,,0000,0000,0000,,and that's exactly what this code does. Dialogue: 0,0:12:39.59,0:12:43.11,Default,,0000,0000,0000,,The N2 % N1 that's again the N2 mod N1 Dialogue: 0,0:12:43.11,0:12:45.54,Default,,0000,0000,0000,,the least remainder when you divide N2 by N1. Dialogue: 0,0:12:45.54,0:12:49.41,Default,,0000,0000,0000,,And then the result once one of the numbers gets down to zero Dialogue: 0,0:12:49.41,0:12:52.29,Default,,0000,0000,0000,,the other number is exactly the shared prime. Dialogue: 0,0:12:52.29,0:12:54.15,Default,,0000,0000,0000,,So this amazing algorithm, Dialogue: 0,0:12:54.15,0:12:57.05,Default,,0000,0000,0000,,here's just a little manual example Dialogue: 0,0:12:57.05,0:12:59.90,Default,,0000,0000,0000,,not with big 512, 1024 bit keys Dialogue: 0,0:12:59.90,0:13:04.14,Default,,0000,0000,0000,,this is with just tiny little I guess 8 bit primes Dialogue: 0,0:13:04.14,0:13:07.62,Default,,0000,0000,0000,,16 bit... well looks more like 13 bit keys. Dialogue: 0,0:13:07.62,0:13:12.38,Default,,0000,0000,0000,,So two numbers coming in and one is 4187 and two is 5989. Dialogue: 0,0:13:12.38,0:13:14.88,Default,,0000,0000,0000,,You can see if you keep dividing one number by the other, Dialogue: 0,0:13:14.88,0:13:16.16,Default,,0000,0000,0000,,replacing it by the remainder, Dialogue: 0,0:13:16.16,0:13:19.41,Default,,0000,0000,0000,,do that a few times, you quickly get down to zero. Dialogue: 0,0:13:19.41,0:13:22.77,Default,,0000,0000,0000,,And the number right before the zero in the middle of the slide is 53. Dialogue: 0,0:13:22.77,0:13:27.17,Default,,0000,0000,0000,,Now 53 is a shared prime between these two small keys. Dialogue: 0,0:13:27.17,0:13:28.77,Default,,0000,0000,0000,,If you scale this up, Dialogue: 0,0:13:28.77,0:13:32.26,Default,,0000,0000,0000,,if you do this computation for bigger numbers Dialogue: 0,0:13:32.26,0:13:34.18,Default,,0000,0000,0000,,then here's another timing example. Dialogue: 0,0:13:34.18,0:13:36.67,Default,,0000,0000,0000,,It's still really really fast, in the middle of the slide. Dialogue: 0,0:13:36.67,0:13:40.36,Default,,0000,0000,0000,,This is doing 1024 bit keys that share a 512 bit prime. Dialogue: 0,0:13:40.36,0:13:44.55,Default,,0000,0000,0000,,You can figure out this 512 bit prime so quickly that the timing Dialogue: 0,0:13:44.55,0:13:48.85,Default,,0000,0000,0000,,there is 0.00 seconds, can't even see how fast it is. Dialogue: 0,0:13:48.85,0:13:51.09,Default,,0000,0000,0000,,Ok, so that's Euclid's algorithm. Dialogue: 0,0:13:51.09,0:13:53.68,Default,,0000,0000,0000,,Now you can actually do this for tons and tons of keys. Dialogue: 0,0:13:53.68,0:13:57.70,Default,,0000,0000,0000,,You download, say, millions, tens of millions of keys from the Internet, Dialogue: 0,0:13:57.70,0:14:01.01,Default,,0000,0000,0000,,all the different SSL servers, maybe go for some SSH keys, Dialogue: 0,0:14:01.01,0:14:03.89,Default,,0000,0000,0000,,you download tons and tons of public keys and then Dialogue: 0,0:14:03.89,0:14:06.59,Default,,0000,0000,0000,,you try all the pairs with Euclid's algorithm. Dialogue: 0,0:14:06.59,0:14:09.41,Default,,0000,0000,0000,,And it's so fast that you can do this but actually Dialogue: 0,0:14:09.41,0:14:10.85,Default,,0000,0000,0000,,you can do better. Dialogue: 0,0:14:10.85,0:14:13.93,Default,,0000,0000,0000,,So there's an algorithm: batch GCD algorithm Dialogue: 0,0:14:13.93,0:14:15.40,Default,,0000,0000,0000,,which takes a whole bunch of keys Dialogue: 0,0:14:15.40,0:14:19.82,Default,,0000,0000,0000,,and figures out which of those keys share primes with the others. Dialogue: 0,0:14:19.82,0:14:22.52,Default,,0000,0000,0000,,Much much faster than trying every pair. Dialogue: 0,0:14:22.52,0:14:23.91,Default,,0000,0000,0000,,So you don't have to try every pair. Dialogue: 0,0:14:23.91,0:14:26.97,Default,,0000,0000,0000,,It's kind of like sorting, it's about that kind of speed Dialogue: 0,0:14:26.97,0:14:29.06,Default,,0000,0000,0000,,instead of having to try every pair. Dialogue: 0,0:14:29.06,0:14:30.81,Default,,0000,0000,0000,,If you have tens of millions you don't have to do Dialogue: 0,0:14:30.81,0:14:33.16,Default,,0000,0000,0000,,tens of millions times tens of millions of pairs. Dialogue: 0,0:14:33.16,0:14:35.74,Default,,0000,0000,0000,,You just have to pretty much reap through the whole list once. Dialogue: 0,0:14:35.74,0:14:38.88,Default,,0000,0000,0000,,So what does this batch GCD algorithm do? Dialogue: 0,0:14:38.88,0:14:41.45,Default,,0000,0000,0000,,It's figuring out for the first N1, Dialogue: 0,0:14:41.45,0:14:44.03,Default,,0000,0000,0000,,instead of computing the greatest common divisor, Dialogue: 0,0:14:44.03,0:14:45.91,Default,,0000,0000,0000,,the Euclid result for N1 and N2 Dialogue: 0,0:14:45.91,0:14:47.85,Default,,0000,0000,0000,,and for N1 and N3 and so on, Dialogue: 0,0:14:47.85,0:14:52.34,Default,,0000,0000,0000,,it figures out the product of N2, N3, N4 and so on, Dialogue: 0,0:14:52.34,0:14:55.26,Default,,0000,0000,0000,,takes the greatest common divisor of that with N1, Dialogue: 0,0:14:55.26,0:14:57.19,Default,,0000,0000,0000,,applies Euclid's algorithm to that Dialogue: 0,0:14:57.19,0:15:00.87,Default,,0000,0000,0000,,and then does a similar thing for N2 and for N3 and so on. Dialogue: 0,0:15:00.87,0:15:05.66,Default,,0000,0000,0000,,Each of those is gonna show you whether N1 or N2 or N3, Dialogue: 0,0:15:05.66,0:15:08.15,Default,,0000,0000,0000,,it's gonna show you whether they share some prime Dialogue: 0,0:15:08.15,0:15:10.25,Default,,0000,0000,0000,,with any of the other N's. Dialogue: 0,0:15:10.25,0:15:13.33,Default,,0000,0000,0000,,If you did exactly the computation Dialogue: 0,0:15:13.33,0:15:15.25,Default,,0000,0000,0000,,shown on the slide in the math formulas Dialogue: 0,0:15:15.25,0:15:16.62,Default,,0000,0000,0000,,it would still be too slow. Dialogue: 0,0:15:16.62,0:15:20.46,Default,,0000,0000,0000,,But the batch GCD algorithm finds redundancies Dialogue: 0,0:15:20.46,0:15:23.22,Default,,0000,0000,0000,,in these GCDs, and here's exactly what it does: Dialogue: 0,0:15:23.22,0:15:25.62,Default,,0000,0000,0000,,It figures out the product of all of the keys. Dialogue: 0,0:15:25.62,0:15:29.92,Default,,0000,0000,0000,,So you take, say, a million keys and you multiply them all together. Dialogue: 0,0:15:29.92,0:15:33.53,Default,,0000,0000,0000,,And that's done with the code here where you do... Dialogue: 0,0:15:33.53,0:15:35.12,Default,,0000,0000,0000,,maybe I'll just skip to the bottom. Dialogue: 0,0:15:35.12,0:15:37.47,Default,,0000,0000,0000,,You see numbers 10, 20, 30, 40. Dialogue: 0,0:15:37.47,0:15:39.36,Default,,0000,0000,0000,,You build a product tree. Dialogue: 0,0:15:39.36,0:15:42.21,Default,,0000,0000,0000,,So you take 10 times 20, compute 200. Dialogue: 0,0:15:42.21,0:15:44.69,Default,,0000,0000,0000,,Take the next pair 30 times 40, compute 1200. Dialogue: 0,0:15:44.69,0:15:47.89,Default,,0000,0000,0000,,The take the pair of products 200 times 1200. Dialogue: 0,0:15:47.89,0:15:50.38,Default,,0000,0000,0000,,If you have more numbers, you have more levels in the tree. Dialogue: 0,0:15:50.38,0:15:55.23,Default,,0000,0000,0000,,And that's exactly what the Sage code does here. Dialogue: 0,0:15:55.23,0:15:58.92,Default,,0000,0000,0000,,And then the last step of the algorithm is Dialogue: 0,0:15:58.92,0:16:02.85,Default,,0000,0000,0000,,kind of going down the tree, building a remainder tree. Dialogue: 0,0:16:02.85,0:16:06.52,Default,,0000,0000,0000,,So what's happening here to figure out the greatest common divisor Dialogue: 0,0:16:06.52,0:16:10.01,Default,,0000,0000,0000,,of N1 with the product of all the other keys, Dialogue: 0,0:16:10.01,0:16:12.85,Default,,0000,0000,0000,,the idea is to take this product Dialogue: 0,0:16:12.85,0:16:15.81,Default,,0000,0000,0000,,which is called big R on this slide, Dialogue: 0,0:16:15.81,0:16:23.16,Default,,0000,0000,0000,,take the product of all the keys and then divide that by N1^2 Dialogue: 0,0:16:23.16,0:16:26.29,Default,,0000,0000,0000,,and then take the remainders, so R mod N1^2, Dialogue: 0,0:16:26.29,0:16:31.15,Default,,0000,0000,0000,,divide by N1 and then compute the greatest common divisor of N1 mod N. Dialogue: 0,0:16:31.15,0:16:33.12,Default,,0000,0000,0000,,And the amazing effect is that it's exactly the Dialogue: 0,0:16:33.12,0:16:35.05,Default,,0000,0000,0000,,greatest common divisor we were looking for. Dialogue: 0,0:16:35.05,0:16:37.63,Default,,0000,0000,0000,,And what this little Sage script does is that it takes Dialogue: 0,0:16:37.63,0:16:42.28,Default,,0000,0000,0000,,R and divides R by, well a bunch of N's in a really fast way, Dialogue: 0,0:16:42.28,0:16:43.96,Default,,0000,0000,0000,,and then at the bottom, once it has figured out Dialogue: 0,0:16:43.96,0:16:47.23,Default,,0000,0000,0000,,all mod N1^2, all mod N2^2 and so on, Dialogue: 0,0:16:47.23,0:16:49.31,Default,,0000,0000,0000,,divides those by N1 and N2, Dialogue: 0,0:16:49.31,0:16:52.18,Default,,0000,0000,0000,,takes the greatest common divisor with N1 and N2 Dialogue: 0,0:16:52.18,0:16:54.82,Default,,0000,0000,0000,,and that's exactly telling you, the outputs here Dialogue: 0,0:16:54.82,0:16:57.06,Default,,0000,0000,0000,,that are different from 1, are exactly telling you Dialogue: 0,0:16:57.06,0:17:00.40,Default,,0000,0000,0000,,which N's share a prime with some others. Dialogue: 0,0:17:00.40,0:17:04.05,Default,,0000,0000,0000,,This very remarkably short little script does work quite well. Dialogue: 0,0:17:04.05,0:17:06.52,Default,,0000,0000,0000,,Here's how fast these are. Dialogue: 0,0:17:06.52,0:17:10.25,Default,,0000,0000,0000,,So I'm on some 800 MHz core. Dialogue: 0,0:17:10.25,0:17:13.44,Default,,0000,0000,0000,,If you try this for, say, a hundred numbers, Dialogue: 0,0:17:13.44,0:17:16.61,Default,,0000,0000,0000,,just hundred random 1024 bit numbers, Dialogue: 0,0:17:16.61,0:17:20.92,Default,,0000,0000,0000,,it doesn't matter what the numbers are, they always run at the same speed, Dialogue: 0,0:17:20.92,0:17:23.20,Default,,0000,0000,0000,,then that takes 0.05 seconds. Dialogue: 0,0:17:23.20,0:17:27.25,Default,,0000,0000,0000,,If you have 10 times as many numbers it takes about 20 times as long. Dialogue: 0,0:17:27.25,0:17:31.23,Default,,0000,0000,0000,,And if you have another 10 times as many numbers it takes about 20 times as long. Dialogue: 0,0:17:31.23,0:17:33.25,Default,,0000,0000,0000,,And it keeps scaling up like that. Dialogue: 0,0:17:33.25,0:17:35.95,Default,,0000,0000,0000,,So you can get to millions or tens of millions of numbers Dialogue: 0,0:17:35.95,0:17:38.58,Default,,0000,0000,0000,,and it still finishes in a reasonable amount of time. Dialogue: 0,0:17:38.58,0:17:40.07,Default,,0000,0000,0000,,So, amazingly fast algorithm. Dialogue: 0,0:17:40.07,0:17:43.81,Default,,0000,0000,0000,,You don't have to scale this up to like 2^50 or 2^100 keys. Dialogue: 0,0:17:43.81,0:17:46.06,Default,,0000,0000,0000,,There's only, say, tens of millions of keys out there Dialogue: 0,0:17:46.06,0:17:48.33,Default,,0000,0000,0000,,and this runs reasonably fast. Dialogue: 0,0:17:48.33,0:17:50.63,Default,,0000,0000,0000,,Ok. Dialogue: 0,0:17:50.63,0:17:52.42,Default,,0000,0000,0000,,Can you actually hope for this to work? Dialogue: 0,0:17:52.42,0:17:54.63,Default,,0000,0000,0000,,Are random number generators really this bad? Dialogue: 0,0:17:54.63,0:17:55.87,Default,,0000,0000,0000,,Well... Dialogue: 0,0:17:55.87,0:18:00.48,Default,,0000,0000,0000,,{\i1}laughs{\i0} Dialogue: 0,0:18:00.48,0:18:03.44,Default,,0000,0000,0000,,There's a 2012 paper from Heninger Dialogue: 0,0:18:03.44,0:18:04.93,Default,,0000,0000,0000,,that's the same Heninger we have sitting here Dialogue: 0,0:18:04.93,0:18:06.30,Default,,0000,0000,0000,,and Durumeric, Wustrow, Halderman, Dialogue: 0,0:18:06.30,0:18:09.88,Default,,0000,0000,0000,,that's got the best paper award at USENIX Security 2012. Dialogue: 0,0:18:09.88,0:18:14.68,Default,,0000,0000,0000,,What they did was they tried exactly this on tens of millions of keys out there Dialogue: 0,0:18:14.68,0:18:18.28,Default,,0000,0000,0000,,and factored tens of thousands of keys. Dialogue: 0,0:18:18.28,0:18:22.68,Default,,0000,0000,0000,,Admittely they used a C version of this instead of this Dialogue: 0,0:18:22.68,0:18:24.06,Default,,0000,0000,0000,,Sage script but Dialogue: 0,0:18:24.06,0:18:25.83,Default,,0000,0000,0000,,the Sage script will go up to millions. Dialogue: 0,0:18:25.83,0:18:28.36,Default,,0000,0000,0000,,It's just when you get beyond that you want to write it in C Dialogue: 0,0:18:28.36,0:18:31.01,Default,,0000,0000,0000,,to deal with using a lot of memory. Dialogue: 0,0:18:31.01,0:18:34.89,Default,,0000,0000,0000,,But you can use exactly this script for pretty large chunks of keys. Dialogue: 0,0:18:34.89,0:18:37.95,Default,,0000,0000,0000,,And so they factored tens of thousands of keys and said Dialogue: 0,0:18:37.95,0:18:42.24,Default,,0000,0000,0000,,that these keys are typically not your bank keys. Dialogue: 0,0:18:42.24,0:18:44.91,Default,,0000,0000,0000,,They gonna be, say, keys for your home router. Dialogue: 0,0:18:44.91,0:18:47.64,Default,,0000,0000,0000,,So the vulnerable devices are not gonna be, Dialogue: 0,0:18:47.64,0:18:49.89,Default,,0000,0000,0000,,say, a big server out there. Dialogue: 0,0:18:49.89,0:18:53.90,Default,,0000,0000,0000,,The vulnerable devices will be your FRITZ!Box. Dialogue: 0,0:18:53.90,0:18:57.34,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:18:57.34,0:18:59.84,Default,,0000,0000,0000,,Thank you, Nadia. Dialogue: 0,0:18:59.84,0:19:06.52,Default,,0000,0000,0000,,It's good to read the paper, go to factorable.net Dialogue: 0,0:19:06.52,0:19:09.07,Default,,0000,0000,0000,,and you get tons of analyses of why this happened Dialogue: 0,0:19:09.07,0:19:12.52,Default,,0000,0000,0000,,and why these devices are generated guessable numbers. Dialogue: 0,0:19:12.52,0:19:15.02,Default,,0000,0000,0000,,I mean numbers that are so non-random that they get Dialogue: 0,0:19:15.02,0:19:18.37,Default,,0000,0000,0000,,repeated between a lot of keys out there. Dialogue: 0,0:19:18.37,0:19:20.31,Default,,0000,0000,0000,,There was at the same time another team that Dialogue: 0,0:19:20.31,0:19:23.56,Default,,0000,0000,0000,,like within days announced the same result. Dialogue: 0,0:19:23.56,0:19:27.07,Default,,0000,0000,0000,,They independently did the same computation. Dialogue: 0,0:19:27.07,0:19:28.88,Default,,0000,0000,0000,,They said "yeah, we've also downloaded Dialogue: 0,0:19:28.88,0:19:31.35,Default,,0000,0000,0000,,a bunch of keys and factored as many as we could" Dialogue: 0,0:19:31.35,0:19:32.87,Default,,0000,0000,0000,,with basically the same algorithm. Dialogue: 0,0:19:32.87,0:19:35.20,Default,,0000,0000,0000,,At the end of it "yeah we factored Dialogue: 0,0:19:35.20,0:19:36.63,Default,,0000,0000,0000,,tens of thousands of keys." Dialogue: 0,0:19:36.63,0:19:38.88,Default,,0000,0000,0000,,That paper has no analysis. Dialogue: 0,0:19:38.88,0:19:41.58,Default,,0000,0000,0000,,They're like "yeah, there's keys" Dialogue: 0,0:19:41.58,0:19:43.27,Default,,0000,0000,0000,,"they share primes for some reason" Dialogue: 0,0:19:43.27,0:19:45.92,Default,,0000,0000,0000,,"I guess ecommerce is dead" Dialogue: 0,0:19:45.92,0:19:47.54,Default,,0000,0000,0000,,"go out, change your bank keys" Dialogue: 0,0:19:47.54,0:19:48.85,Default,,0000,0000,0000,,"call the New York Times" Dialogue: 0,0:19:48.85,0:19:50.55,Default,,0000,0000,0000,,There's the New York Times article: Dialogue: 0,0:19:50.55,0:19:52.60,Default,,0000,0000,0000,,"Flaw Found in an Online Encryption Method" Dialogue: 0,0:19:52.60,0:19:54.86,Default,,0000,0000,0000,,I also like the advertising on the side here. Dialogue: 0,0:19:54.86,0:19:57.15,Default,,0000,0000,0000,,Like iron key on the top and then: Dialogue: 0,0:19:57.15,0:20:01.17,Default,,0000,0000,0000,,"Encrypt, decrypt & access my secret data in real time" Dialogue: 0,0:20:01.17,0:20:03.14,Default,,0000,0000,0000,,"try it free for 30 days." Dialogue: 0,0:20:03.14,0:20:05.20,Default,,0000,0000,0000,,"I secured my cloud data. Have you?" Dialogue: 0,0:20:05.20,0:20:06.88,Default,,0000,0000,0000,,Awesome advertising there. Dialogue: 0,0:20:06.88,0:20:12.48,Default,,0000,0000,0000,,Once you found that there's a problem like this Dialogue: 0,0:20:12.48,0:20:14.92,Default,,0000,0000,0000,,then of course you start looking around for more and more places Dialogue: 0,0:20:14.92,0:20:17.44,Default,,0000,0000,0000,,where you might have some bad randomness. Dialogue: 0,0:20:17.44,0:20:22.80,Default,,0000,0000,0000,,For example there is a paper, or at least slides, Dialogue: 0,0:20:22.80,0:20:25.40,Default,,0000,0000,0000,,by Chou in Taiwan, saying Dialogue: 0,0:20:25.40,0:20:31.86,Default,,0000,0000,0000,,they took two million Taiwan Citizen Digital Certificates Dialogue: 0,0:20:31.86,0:20:34.33,Default,,0000,0000,0000,,and did some GCDs Dialogue: 0,0:20:34.33,0:20:36.63,Default,,0000,0000,0000,,and found that a 103 of those were Dialogue: 0,0:20:36.63,0:20:37.100,Default,,0000,0000,0000,,factorable. Dialogue: 0,0:20:37.100,0:20:40.05,Default,,0000,0000,0000,,So anybody who downloaded these certificates Dialogue: 0,0:20:40.05,0:20:43.18,Default,,0000,0000,0000,,which apparently are used in Taiwan for like paying your taxes, Dialogue: 0,0:20:43.18,0:20:44.39,Default,,0000,0000,0000,,talking to banks I don't know, Dialogue: 0,0:20:44.39,0:20:46.68,Default,,0000,0000,0000,,but paying taxes is one that I've checked. Dialogue: 0,0:20:46.68,0:20:49.54,Default,,0000,0000,0000,,So a 103 people out there have these Taiwan Dialogue: 0,0:20:49.54,0:20:51.01,Default,,0000,0000,0000,,Citizen Digital Certificates where Dialogue: 0,0:20:51.01,0:20:54.12,Default,,0000,0000,0000,,you're supposed to have in this database things like Dialogue: 0,0:20:54.12,0:20:57.12,Default,,0000,0000,0000,,the names of the people and their ID numbers Dialogue: 0,0:20:57.12,0:20:59.58,Default,,0000,0000,0000,,but you aren't supposed to have their secret keys. Dialogue: 0,0:20:59.58,0:21:01.54,Default,,0000,0000,0000,,The whole point is those are supposed to be private Dialogue: 0,0:21:01.54,0:21:03.94,Default,,0000,0000,0000,,kept on some smartcards that are issued to the citizens Dialogue: 0,0:21:03.94,0:21:05.30,Default,,0000,0000,0000,,in Taiwan. Dialogue: 0,0:21:05.30,0:21:08.71,Default,,0000,0000,0000,,And the randomness generation is so bad that Dialogue: 0,0:21:08.71,0:21:13.17,Default,,0000,0000,0000,,103 of those keys have now been factored. Dialogue: 0,0:21:13.17,0:21:15.45,Default,,0000,0000,0000,,The smartcard manufacturer, I also like this quote, Dialogue: 0,0:21:15.45,0:21:18.67,Default,,0000,0000,0000,,it's a company based in Munich called Dialogue: 0,0:21:18.67,0:21:22.32,Default,,0000,0000,0000,,Giesecke & Devrient and their motto is: Dialogue: 0,0:21:22.32,0:21:24.75,Default,,0000,0000,0000,,"Creating Confidence" Dialogue: 0,0:21:24.75,0:21:35.27,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:21:35.27,0:21:37.70,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: There's gonna be more of Dan, don't worry. Dialogue: 0,0:21:37.70,0:21:39.84,Default,,0000,0000,0000,,But we promised a bit more than just factoring Dialogue: 0,0:21:39.84,0:21:43.31,Default,,0000,0000,0000,,bad keys or the keys with their primes. Dialogue: 0,0:21:43.31,0:21:46.96,Default,,0000,0000,0000,,If you find another number like this one. Dialogue: 0,0:21:46.96,0:21:49.69,Default,,0000,0000,0000,,So here's coming some more of math stuff. Dialogue: 0,0:21:49.69,0:21:52.56,Default,,0000,0000,0000,,So if you see a number like this and you Dialogue: 0,0:21:52.56,0:21:56.43,Default,,0000,0000,0000,,observe this last digit, then yes. Dialogue: 0,0:21:56.43,0:21:58.74,Default,,0000,0000,0000,,It's very easy for you to see it's divisable by 5. Dialogue: 0,0:21:58.74,0:22:01.38,Default,,0000,0000,0000,,So if you find such a key that is easy to break Dialogue: 0,0:22:01.38,0:22:03.23,Default,,0000,0000,0000,,and you are a computer rather than a human being Dialogue: 0,0:22:03.23,0:22:05.32,Default,,0000,0000,0000,,you look at lots of those numbers. Dialogue: 0,0:22:05.32,0:22:07.08,Default,,0000,0000,0000,,You have a list of small primes stored Dialogue: 0,0:22:07.08,0:22:10.04,Default,,0000,0000,0000,,and what you're gonna do is just trial division. Dialogue: 0,0:22:10.04,0:22:11.99,Default,,0000,0000,0000,,So if there's any small factor Dialogue: 0,0:22:11.99,0:22:14.09,Default,,0000,0000,0000,,it's very easy to find this trial division. Dialogue: 0,0:22:14.09,0:22:16.71,Default,,0000,0000,0000,,Or what Dan showed was the remainder trees. Dialogue: 0,0:22:16.71,0:22:20.22,Default,,0000,0000,0000,,You can also do this for batch trial division. Dialogue: 0,0:22:20.22,0:22:23.73,Default,,0000,0000,0000,,So assuming that you're looking for a prime p somewhere Dialogue: 0,0:22:23.73,0:22:26.74,Default,,0000,0000,0000,,then you go linearly all the way up to the p Dialogue: 0,0:22:26.74,0:22:30.44,Default,,0000,0000,0000,,and there are about p/log(p) many primes Dialogue: 0,0:22:30.44,0:22:32.09,Default,,0000,0000,0000,,before you find this p. Dialogue: 0,0:22:32.09,0:22:33.97,Default,,0000,0000,0000,,For each of them you just do exact division. Dialogue: 0,0:22:33.97,0:22:36.56,Default,,0000,0000,0000,,If it works, fine you found a factor, otherwise not. Dialogue: 0,0:22:36.56,0:22:39.46,Default,,0000,0000,0000,,Now this is not going to work against your normal keys. Dialogue: 0,0:22:39.46,0:22:43.62,Default,,0000,0000,0000,,I know that in the example that Dan mentioned by Wagner&Goldberg Dialogue: 0,0:22:43.62,0:22:46.62,Default,,0000,0000,0000,,that they found one factor which had a 9 in there Dialogue: 0,0:22:46.62,0:22:49.98,Default,,0000,0000,0000,,but usually your keys don't have a 9. Dialogue: 0,0:22:49.98,0:22:54.69,Default,,0000,0000,0000,,For slightly larger numbers there is a method due to Pollard. Dialogue: 0,0:22:54.69,0:22:57.46,Default,,0000,0000,0000,,So if you see the respectful number here, Dialogue: 0,0:22:57.46,0:22:59.89,Default,,0000,0000,0000,,there is no obvious divisability of this one. Dialogue: 0,0:22:59.89,0:23:03.09,Default,,0000,0000,0000,,One thing you can try is Dialogue: 0,0:23:03.09,0:23:06.66,Default,,0000,0000,0000,,a walk, well we call this a walk. Dialogue: 0,0:23:06.66,0:23:10.40,Default,,0000,0000,0000,,You start with some random number smaller than N Dialogue: 0,0:23:10.40,0:23:12.90,Default,,0000,0000,0000,,and some offset here. Dialogue: 0,0:23:12.90,0:23:17.28,Default,,0000,0000,0000,,I should also say, all those scripts are available at this URL. Dialogue: 0,0:23:17.28,0:23:22.09,Default,,0000,0000,0000,,So if you go to facthacks.cr.yp.to then you'll find all the scripts Dialogue: 0,0:23:22.09,0:23:23.88,Default,,0000,0000,0000,,if you want to play with it at the same time, Dialogue: 0,0:23:23.88,0:23:26.62,Default,,0000,0000,0000,,including this one with some explanations and such. Dialogue: 0,0:23:26.62,0:23:31.09,Default,,0000,0000,0000,,So what you do is you start off two different numbers, Dialogue: 0,0:23:31.09,0:23:34.79,Default,,0000,0000,0000,,one at each step squares it and adds c. Dialogue: 0,0:23:34.79,0:23:37.23,Default,,0000,0000,0000,,And the other one squares it, adds c, Dialogue: 0,0:23:37.23,0:23:39.89,Default,,0000,0000,0000,,and squares it again and adds the c. Dialogue: 0,0:23:39.89,0:23:41.46,Default,,0000,0000,0000,,Each time computing mod N. Dialogue: 0,0:23:41.46,0:23:44.10,Default,,0000,0000,0000,,So you have two sequences running around, Dialogue: 0,0:23:44.10,0:23:46.02,Default,,0000,0000,0000,,one is twice the speed as the other. Dialogue: 0,0:23:46.02,0:23:50.95,Default,,0000,0000,0000,,At every step you check with the GCD of this number N Dialogue: 0,0:23:50.95,0:23:52.76,Default,,0000,0000,0000,,and the difference between the two walks Dialogue: 0,0:23:52.76,0:23:55.01,Default,,0000,0000,0000,,hasn't anything interesting now. Dialogue: 0,0:23:55.01,0:23:57.39,Default,,0000,0000,0000,,N is an RSA modulus, the only thing interesting Dialogue: 0,0:23:57.39,0:23:59.68,Default,,0000,0000,0000,,could either be p or q. Dialogue: 0,0:23:59.68,0:24:03.01,Default,,0000,0000,0000,,So for this particular number Dialogue: 0,0:24:03.01,0:24:04.27,Default,,0000,0000,0000,,when I run this Dialogue: 0,0:24:04.27,0:24:08.89,Default,,0000,0000,0000,,I find 2053 after a few milliseconds. Dialogue: 0,0:24:08.89,0:24:10.64,Default,,0000,0000,0000,,So this is again a cooked up example. Dialogue: 0,0:24:10.64,0:24:13.31,Default,,0000,0000,0000,,You won't find such a small factor if you're trying Dialogue: 0,0:24:13.31,0:24:16.17,Default,,0000,0000,0000,,a general RSA factor, otherwise your numbers Dialogue: 0,0:24:16.17,0:24:17.83,Default,,0000,0000,0000,,would be totally busted but Dialogue: 0,0:24:17.83,0:24:20.60,Default,,0000,0000,0000,,this shows if you have a small number in there Dialogue: 0,0:24:20.60,0:24:21.86,Default,,0000,0000,0000,,it's very easy to find. Dialogue: 0,0:24:21.86,0:24:24.36,Default,,0000,0000,0000,,All later on when Dan is talking about the number field sieve Dialogue: 0,0:24:24.36,0:24:26.16,Default,,0000,0000,0000,,this is an interesting subroutine. Dialogue: 0,0:24:26.16,0:24:28.09,Default,,0000,0000,0000,,So if you ever need to find small numbers Dialogue: 0,0:24:28.09,0:24:31.02,Default,,0000,0000,0000,,then, sure trial division is very easy for Dialogue: 0,0:24:31.02,0:24:34.08,Default,,0000,0000,0000,,really small numbers taking this long, Dialogue: 0,0:24:34.08,0:24:38.35,Default,,0000,0000,0000,,this one squared with p is much faster already. Dialogue: 0,0:24:38.35,0:24:42.07,Default,,0000,0000,0000,,Now even faster than that, also due to Pollard, Dialogue: 0,0:24:42.07,0:24:45.38,Default,,0000,0000,0000,,called Pollard's p-1 method. Dialogue: 0,0:24:45.38,0:24:47.90,Default,,0000,0000,0000,,Here is again an innocent looking number N. Dialogue: 0,0:24:47.90,0:24:49.84,Default,,0000,0000,0000,,You see the numbers get larger. Dialogue: 0,0:24:49.84,0:24:52.18,Default,,0000,0000,0000,,This is a 256 bit number. Dialogue: 0,0:24:52.18,0:24:56.74,Default,,0000,0000,0000,,In order to deal with such a number there is one step Dialogue: 0,0:24:56.74,0:24:59.34,Default,,0000,0000,0000,,which is expensive but you would do it only once Dialogue: 0,0:24:59.34,0:25:01.21,Default,,0000,0000,0000,,for all different numbers you want to try, Dialogue: 0,0:25:01.21,0:25:05.24,Default,,0000,0000,0000,,namely compute a big integer which has lots of little factors. Dialogue: 0,0:25:05.24,0:25:06.98,Default,,0000,0000,0000,,So you take the least common multiple Dialogue: 0,0:25:06.98,0:25:09.79,Default,,0000,0000,0000,,from 1, 2, 3, 4, 5... Dialogue: 0,0:25:09.79,0:25:12.20,Default,,0000,0000,0000,,Ok, once you hit the 4 you have another 2 in there. Dialogue: 0,0:25:12.20,0:25:13.81,Default,,0000,0000,0000,,So there's lots and lots of powers of 2, Dialogue: 0,0:25:13.81,0:25:15.41,Default,,0000,0000,0000,,lots and lots of powers of 3. Dialogue: 0,0:25:15.41,0:25:19.39,Default,,0000,0000,0000,,And then the larger primes only appear like once. Dialogue: 0,0:25:19.39,0:25:23.16,Default,,0000,0000,0000,,But you're not going up to 256 or 128 anywhere. Dialogue: 0,0:25:23.16,0:25:27.00,Default,,0000,0000,0000,,You're sticking here at 22 bits Dialogue: 0,0:25:27.00,0:25:29.06,Default,,0000,0000,0000,,and then use the same function that Nadia explained Dialogue: 0,0:25:31.02,0:25:32.99,Default,,0000,0000,0000,,in the RSA computation, namely the modular exponentiation. Dialogue: 0,0:25:32.99,0:25:36.58,Default,,0000,0000,0000,,So you take the 2^y, Dialogue: 0,0:25:36.58,0:25:38.24,Default,,0000,0000,0000,,this huge number, Dialogue: 0,0:25:38.24,0:25:40.49,Default,,0000,0000,0000,,but the whole computation mod N. Dialogue: 0,0:25:40.49,0:25:44.63,Default,,0000,0000,0000,,So this whole thing never grows beyond this 256 bit number. Dialogue: 0,0:25:44.63,0:25:47.94,Default,,0000,0000,0000,,Or for a real world example it would be a 1000 bit number. Dialogue: 0,0:25:47.94,0:25:52.52,Default,,0000,0000,0000,,And then you compute the GCD of this number and N. Dialogue: 0,0:25:52.52,0:25:55.09,Default,,0000,0000,0000,,For this particular one, again it's a cooked up example, Dialogue: 0,0:25:55.09,0:25:56.39,Default,,0000,0000,0000,,you get a factor. Dialogue: 0,0:25:56.39,0:25:59.79,Default,,0000,0000,0000,,Now this factor is actually 120 bits. Dialogue: 0,0:25:59.79,0:26:02.37,Default,,0000,0000,0000,,This is not a small factor. Dialogue: 0,0:26:02.37,0:26:05.69,Default,,0000,0000,0000,,So if you were using 256 bit numbers Dialogue: 0,0:26:05.69,0:26:07.86,Default,,0000,0000,0000,,this is something that could happen to you Dialogue: 0,0:26:07.86,0:26:11.30,Default,,0000,0000,0000,,and nevertheless this method would find it. Dialogue: 0,0:26:11.30,0:26:13.52,Default,,0000,0000,0000,,So this finds much larger factors than trial division Dialogue: 0,0:26:13.52,0:26:15.48,Default,,0000,0000,0000,,or the Rho method in the same amount of time. Dialogue: 0,0:26:15.48,0:26:17.38,Default,,0000,0000,0000,,But it doesn't work for all primes. Dialogue: 0,0:26:17.38,0:26:20.07,Default,,0000,0000,0000,,It works for primes which are kind of special. Dialogue: 0,0:26:20.07,0:26:23.86,Default,,0000,0000,0000,,Now what's special about this prime or the other factor? Dialogue: 0,0:26:23.86,0:26:29.55,Default,,0000,0000,0000,,If you take p and subtract -1, hence the name p-1 method, Dialogue: 0,0:26:29.55,0:26:31.66,Default,,0000,0000,0000,,and factor that thing, Dialogue: 0,0:26:31.66,0:26:35.27,Default,,0000,0000,0000,,that has lots, lots of small numbers. Dialogue: 0,0:26:35.27,0:26:36.94,Default,,0000,0000,0000,,So that's something we call smooth. Dialogue: 0,0:26:36.94,0:26:40.34,Default,,0000,0000,0000,,So a smooth number doesn't have big factors. Dialogue: 0,0:26:40.34,0:26:43.87,Default,,0000,0000,0000,,So a prime is like the least smooth number you can imagine. Dialogue: 0,0:26:43.87,0:26:47.37,Default,,0000,0000,0000,,And 2 to the power large is the most smooth number, Dialogue: 0,0:26:47.37,0:26:50.01,Default,,0000,0000,0000,,so lots of little factors means smooth. Dialogue: 0,0:26:50.01,0:26:55.57,Default,,0000,0000,0000,,This largest factor happens to be 21.7 bits Dialogue: 0,0:26:55.57,0:26:58.36,Default,,0000,0000,0000,,which is why I chose the 22 bits here. Dialogue: 0,0:26:58.36,0:27:03.70,Default,,0000,0000,0000,,So as soon I run over the largest prime in p-1 Dialogue: 0,0:27:03.70,0:27:06.13,Default,,0000,0000,0000,,with this exponent y here Dialogue: 0,0:27:06.13,0:27:08.65,Default,,0000,0000,0000,,then I do find this factor. Dialogue: 0,0:27:08.65,0:27:10.85,Default,,0000,0000,0000,,Now if you thought this was math Dialogue: 0,0:27:10.85,0:27:12.32,Default,,0000,0000,0000,,there is even more scary math Dialogue: 0,0:27:12.32,0:27:15.89,Default,,0000,0000,0000,,namely there are methods which are generalizing Dialogue: 0,0:27:15.89,0:27:19.32,Default,,0000,0000,0000,,this p-1 method using elliptic curves. Dialogue: 0,0:27:19.32,0:27:21.57,Default,,0000,0000,0000,,If you listen to the crypto advertisement Dialogue: 0,0:27:21.57,0:27:23.47,Default,,0000,0000,0000,,elliptic curves are usually something very good, Dialogue: 0,0:27:23.47,0:27:25.00,Default,,0000,0000,0000,,something you should have on your smartcard. Dialogue: 0,0:27:25.00,0:27:27.24,Default,,0000,0000,0000,,It's faster than RSA and so on. Dialogue: 0,0:27:27.24,0:27:29.38,Default,,0000,0000,0000,,That's the same type of elliptic curve Dialogue: 0,0:27:29.38,0:27:32.34,Default,,0000,0000,0000,,but here elliptic curves come in as an attack tool. Dialogue: 0,0:27:32.34,0:27:35.09,Default,,0000,0000,0000,,There is a method called the elliptic curve method ECM Dialogue: 0,0:27:35.09,0:27:41.26,Default,,0000,0000,0000,,which is a generalization of this p-1 method and does not need anything special, Dialogue: 0,0:27:41.26,0:27:44.71,Default,,0000,0000,0000,,I mean avoiding such primes is easy. Dialogue: 0,0:27:44.71,0:27:46.32,Default,,0000,0000,0000,,If you look into older standards Dialogue: 0,0:27:46.32,0:27:49.85,Default,,0000,0000,0000,,they all warn about "make sure to use strong primes" Dialogue: 0,0:27:49.85,0:27:53.17,Default,,0000,0000,0000,,"make sure to check that your p-1 is not smooth" Dialogue: 0,0:27:53.17,0:27:55.30,Default,,0000,0000,0000,,And of course you don't want your p-1 to be smooth Dialogue: 0,0:27:55.30,0:27:57.67,Default,,0000,0000,0000,,because otherwise this attack works. Dialogue: 0,0:27:57.67,0:28:00.76,Default,,0000,0000,0000,,But if I have some elliptic curve Dialogue: 0,0:28:00.76,0:28:03.49,Default,,0000,0000,0000,,a different type of prime is weak for that curve Dialogue: 0,0:28:03.49,0:28:06.35,Default,,0000,0000,0000,,and I have many, many, many elliptic curves. Dialogue: 0,0:28:06.35,0:28:08.62,Default,,0000,0000,0000,,For each of the curves some primes are weak. Dialogue: 0,0:28:08.62,0:28:11.16,Default,,0000,0000,0000,,You can't exclude this method. Dialogue: 0,0:28:11.16,0:28:13.57,Default,,0000,0000,0000,,So the only thing you can do is just, well, Dialogue: 0,0:28:13.57,0:28:18.04,Default,,0000,0000,0000,,choose your prime large enough and hope, well, Dialogue: 0,0:28:18.04,0:28:20.44,Default,,0000,0000,0000,,make sure p-1 doesn't get it and hope Dialogue: 0,0:28:20.44,0:28:22.60,Default,,0000,0000,0000,,that the next elliptic curves won't get it. Dialogue: 0,0:28:22.60,0:28:24.86,Default,,0000,0000,0000,,So elliptic curves are good for attacking. Dialogue: 0,0:28:24.86,0:28:27.62,Default,,0000,0000,0000,,It's still not the fastest method out there Dialogue: 0,0:28:27.62,0:28:33.18,Default,,0000,0000,0000,,but it's a good method for random factoring. Dialogue: 0,0:28:33.18,0:28:35.92,Default,,0000,0000,0000,,It's not the best method for finding RSA factors Dialogue: 0,0:28:35.92,0:28:38.37,Default,,0000,0000,0000,,but if you have a number which is most likely Dialogue: 0,0:28:38.37,0:28:44.53,Default,,0000,0000,0000,,not too non-smooth then it's a good method. Dialogue: 0,0:28:44.53,0:28:47.23,Default,,0000,0000,0000,,Now this is what you do for finding small factors. Dialogue: 0,0:28:47.23,0:28:50.51,Default,,0000,0000,0000,,To show some method for big factors, Dialogue: 0,0:28:50.51,0:28:53.99,Default,,0000,0000,0000,,now here that is a big number. Dialogue: 0,0:28:53.99,0:28:58.98,Default,,0000,0000,0000,,But this is what I would call factorization by inspection. Dialogue: 0,0:28:58.98,0:29:07.88,Default,,0000,0000,0000,,What's wrong with this number? Dialogue: 0,0:29:07.88,0:29:10.13,Default,,0000,0000,0000,,I mean this number is not small and Dialogue: 0,0:29:10.13,0:29:13.16,Default,,0000,0000,0000,,it won't have small factors, I promise you this. Dialogue: 0,0:29:13.16,0:29:19.84,Default,,0000,0000,0000,,So it's a decimal representation, so 9 is the digit before 0. Dialogue: 0,0:29:19.84,0:29:23.25,Default,,0000,0000,0000,,This looks very close to the power of 10. Dialogue: 0,0:29:23.25,0:29:28.25,Default,,0000,0000,0000,,Actually this is very close to 10^340. Dialogue: 0,0:29:28.25,0:29:30.29,Default,,0000,0000,0000,,If you take the square root of it Dialogue: 0,0:29:30.29,0:29:34.15,Default,,0000,0000,0000,,then you almost exactly hit 10^170. Dialogue: 0,0:29:34.15,0:29:37.11,Default,,0000,0000,0000,,This example was cooked up as taking two primes Dialogue: 0,0:29:37.11,0:29:46.65,Default,,0000,0000,0000,,namely 10^170-33 and 10^170+63 and multiplying them. Dialogue: 0,0:29:46.65,0:29:48.67,Default,,0000,0000,0000,,So if you see lots of 0's and lots of 9's Dialogue: 0,0:29:48.67,0:29:50.93,Default,,0000,0000,0000,,then you know that you are very close to a certain power. Dialogue: 0,0:29:50.93,0:29:53.46,Default,,0000,0000,0000,,Now in real life this wouldn't be a power of 10, Dialogue: 0,0:29:53.46,0:29:54.82,Default,,0000,0000,0000,,it would be a power of 2. Dialogue: 0,0:29:54.82,0:29:56.18,Default,,0000,0000,0000,,And there actually are some examples. Dialogue: 0,0:29:56.18,0:29:58.82,Default,,0000,0000,0000,,There's a famous story of a letter bomber in Austria Dialogue: 0,0:29:58.82,0:30:02.65,Default,,0000,0000,0000,,who wanted his message to be crackable Dialogue: 0,0:30:02.65,0:30:06.05,Default,,0000,0000,0000,,and he sent a message, well he was some right-wing asshole Dialogue: 0,0:30:06.05,0:30:08.33,Default,,0000,0000,0000,,that was letter-bombing people Dialogue: 0,0:30:08.33,0:30:10.81,Default,,0000,0000,0000,,and then he sent an encrypted message to the police. Dialogue: 0,0:30:10.81,0:30:14.64,Default,,0000,0000,0000,,And the police tried to factor it and tried to decipher it Dialogue: 0,0:30:14.64,0:30:18.57,Default,,0000,0000,0000,,hoping it would be the list of the next victims. Dialogue: 0,0:30:18.57,0:30:20.98,Default,,0000,0000,0000,,In the end it was not but Dialogue: 0,0:30:20.98,0:30:24.42,Default,,0000,0000,0000,,this person was actually using very close to a power of 2 Dialogue: 0,0:30:24.42,0:30:26.21,Default,,0000,0000,0000,,in order to have people crack it. Dialogue: 0,0:30:26.21,0:30:27.77,Default,,0000,0000,0000,,In the end it was just some propaganda, Dialogue: 0,0:30:27.77,0:30:29.46,Default,,0000,0000,0000,,some right-wing stuff as well. Dialogue: 0,0:30:29.46,0:30:32.78,Default,,0000,0000,0000,,So there are people using this for breakability. Dialogue: 0,0:30:32.78,0:30:35.50,Default,,0000,0000,0000,,I'm not aware of people actually using this as an accident. Dialogue: 0,0:30:35.50,0:30:40.44,Default,,0000,0000,0000,,But what can happen to you is not using close to the power of 2 Dialogue: 0,0:30:40.44,0:30:46.20,Default,,0000,0000,0000,,but saying "ok I learned I shouldn't be close to the power of 2 Dialogue: 0,0:30:46.20,0:30:48.85,Default,,0000,0000,0000,,so I take some offset and take the next prime." Dialogue: 0,0:30:48.85,0:30:51.13,Default,,0000,0000,0000,,Next prime just means, add 1, check is it prime, Dialogue: 0,0:30:51.13,0:30:53.80,Default,,0000,0000,0000,,add next one, add 2, add 3 Dialogue: 0,0:30:53.80,0:30:57.08,Default,,0000,0000,0000,,Just check primes linearly from then on. Dialogue: 0,0:30:57.08,0:30:59.26,Default,,0000,0000,0000,,Now if we jump to this where we finally find our prime p Dialogue: 0,0:30:59.26,0:31:00.97,Default,,0000,0000,0000,,it's a good prime. Dialogue: 0,0:31:00.97,0:31:03.87,Default,,0000,0000,0000,,It's not anywhere close to the power of 2 because my c was large enough. Dialogue: 0,0:31:03.87,0:31:07.13,Default,,0000,0000,0000,,Made it, good. Dialogue: 0,0:31:07.13,0:31:08.56,Default,,0000,0000,0000,,Now on q. Dialogue: 0,0:31:08.56,0:31:10.78,Default,,0000,0000,0000,,So again call the next_prime(). Dialogue: 0,0:31:10.78,0:31:14.44,Default,,0000,0000,0000,,So I do p+1, p+2 until I find a prime. Dialogue: 0,0:31:14.44,0:31:17.22,Default,,0000,0000,0000,,That means that if you take the product of the two Dialogue: 0,0:31:17.22,0:31:19.47,Default,,0000,0000,0000,,then this N is very close to a square. Dialogue: 0,0:31:19.47,0:31:22.92,Default,,0000,0000,0000,,So this N is cooked up with this method. Dialogue: 0,0:31:22.92,0:31:24.41,Default,,0000,0000,0000,,You don't see anything on the end, Dialogue: 0,0:31:24.41,0:31:26.68,Default,,0000,0000,0000,,there's nothing wrong there. Dialogue: 0,0:31:26.68,0:31:29.65,Default,,0000,0000,0000,,But when you compute the square root of it Dialogue: 0,0:31:29.65,0:31:33.16,Default,,0000,0000,0000,,it is almost an integer, it's .99999... Dialogue: 0,0:31:33.16,0:31:35.21,Default,,0000,0000,0000,,and then some dirt here. Dialogue: 0,0:31:35.21,0:31:39.29,Default,,0000,0000,0000,,So then you'll know that your primes were too small. Dialogue: 0,0:31:39.29,0:31:42.29,Default,,0000,0000,0000,,Sorry, not too small, too close to each other. Dialogue: 0,0:31:42.29,0:31:45.48,Default,,0000,0000,0000,,So if you ever take an RSA factor modulus Dialogue: 0,0:31:45.48,0:31:46.84,Default,,0000,0000,0000,,and you compute the square root Dialogue: 0,0:31:46.84,0:31:47.99,Default,,0000,0000,0000,,and you see something like this Dialogue: 0,0:31:47.99,0:31:51.88,Default,,0000,0000,0000,,then you know: that user did this method. Dialogue: 0,0:31:51.88,0:31:53.66,Default,,0000,0000,0000,,You could just say, I take the number, Dialogue: 0,0:31:53.66,0:31:56.55,Default,,0000,0000,0000,,subtract 1, subtract 2, just go off from the square root. Dialogue: 0,0:31:56.55,0:32:02.02,Default,,0000,0000,0000,,All you can check how far away is it from being a square. Dialogue: 0,0:32:02.02,0:32:03.70,Default,,0000,0000,0000,,So you take the seeding, Dialogue: 0,0:32:03.70,0:32:07.95,Default,,0000,0000,0000,,that means the closest integer counting upwards. Dialogue: 0,0:32:07.95,0:32:11.82,Default,,0000,0000,0000,,Just round it to this two, here's 57, is there a 56? Dialogue: 0,0:32:11.82,0:32:14.52,Default,,0000,0000,0000,,Compute the square of that and subtract N. Dialogue: 0,0:32:14.52,0:32:17.99,Default,,0000,0000,0000,,Now in this example that is 4096 Dialogue: 0,0:32:17.99,0:32:22.60,Default,,0000,0000,0000,,which itself is a square. Dialogue: 0,0:32:22.60,0:32:26.64,Default,,0000,0000,0000,,So the difference of N and a^2 is a square. Dialogue: 0,0:32:26.64,0:32:30.92,Default,,0000,0000,0000,,Then I take this 64, take a-64, divide N, Dialogue: 0,0:32:30.92,0:32:34.41,Default,,0000,0000,0000,,it's an exact division, so I found one of the factors. Dialogue: 0,0:32:34.41,0:32:37.20,Default,,0000,0000,0000,,And then there's the other factor. Dialogue: 0,0:32:37.20,0:32:39.74,Default,,0000,0000,0000,,It doesn't matter whether it's a power of 2 or a power of 10. Dialogue: 0,0:32:39.74,0:32:42.57,Default,,0000,0000,0000,,What matters is that the numbers are too close. Dialogue: 0,0:32:42.57,0:32:44.71,Default,,0000,0000,0000,,Now this method actually works surprisingly well Dialogue: 0,0:32:44.71,0:32:47.44,Default,,0000,0000,0000,,even if we don't do next_prime(). Dialogue: 0,0:32:47.44,0:32:50.33,Default,,0000,0000,0000,,So here's another example where I didn't do the next_prime() Dialogue: 0,0:32:50.33,0:32:52.28,Default,,0000,0000,0000,,but did something larger Dialogue: 0,0:32:52.28,0:32:55.11,Default,,0000,0000,0000,,so this is not really close to a square. Dialogue: 0,0:32:55.11,0:32:57.73,Default,,0000,0000,0000,,Some 9's but not too many. Dialogue: 0,0:32:57.73,0:33:00.05,Default,,0000,0000,0000,,What we did before we wrote it as a difference of squares Dialogue: 0,0:33:00.05,0:33:04.61,Default,,0000,0000,0000,,and then divided N by one of these two factors. Dialogue: 0,0:33:04.61,0:33:10.05,Default,,0000,0000,0000,,Now in this case here I would not start as a^2-N Dialogue: 0,0:33:10.05,0:33:12.26,Default,,0000,0000,0000,,but I say, well, if a^2-N is not a square Dialogue: 0,0:33:12.26,0:33:15.100,Default,,0000,0000,0000,,I try the next one, I do (a+1)^2, (a+2)^2 Dialogue: 0,0:33:15.100,0:33:20.78,Default,,0000,0000,0000,,each time subtract N and check when this is a square. Dialogue: 0,0:33:20.78,0:33:24.17,Default,,0000,0000,0000,,Now for this example I get lucky after 2. Dialogue: 0,0:33:24.17,0:33:26.33,Default,,0000,0000,0000,,And this actually took me a long time to cook up this example Dialogue: 0,0:33:26.33,0:33:28.61,Default,,0000,0000,0000,,because I was starting at something which was Dialogue: 0,0:33:28.61,0:33:31.67,Default,,0000,0000,0000,,half of the bits of p were changed. Dialogue: 0,0:33:31.67,0:33:35.87,Default,,0000,0000,0000,,So I was actually starting with a cube quite a distance away. Dialogue: 0,0:33:35.87,0:33:38.22,Default,,0000,0000,0000,,Still, most of those were just giving a square. Dialogue: 0,0:33:38.22,0:33:42.07,Default,,0000,0000,0000,,They were not giving me anything larger than zero here. Dialogue: 0,0:33:42.07,0:33:45.60,Default,,0000,0000,0000,,Now for general numbers if I wouldn't do like next_number() Dialogue: 0,0:33:45.60,0:33:48.79,Default,,0000,0000,0000,,but just, well, random prime, another random prime. Dialogue: 0,0:33:48.79,0:33:52.69,Default,,0000,0000,0000,,It still works but takes a long time Dialogue: 0,0:33:52.69,0:33:55.49,Default,,0000,0000,0000,,because I can always write it this way. Dialogue: 0,0:33:55.49,0:33:56.79,Default,,0000,0000,0000,,This is a, this is b. Dialogue: 0,0:33:56.79,0:34:00.60,Default,,0000,0000,0000,,But then usually it would take about square root of N Dialogue: 0,0:34:00.60,0:34:03.75,Default,,0000,0000,0000,,which is the same size as p until I get there. Dialogue: 0,0:34:03.75,0:34:07.35,Default,,0000,0000,0000,,This is a nice method if it looks like lots of Dialogue: 0,0:34:07.35,0:34:13.39,Default,,0000,0000,0000,,9999 and otherwise do something better as Dan will tell now. Dialogue: 0,0:34:13.39,0:34:13.96,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Ok. Dialogue: 0,0:34:13.96,0:34:21.51,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:34:21.51,0:34:23.66,Default,,0000,0000,0000,,Alright, so it's bad to have p and q Dialogue: 0,0:34:23.66,0:34:24.80,Default,,0000,0000,0000,,too close to each other Dialogue: 0,0:34:24.80,0:34:28.64,Default,,0000,0000,0000,,or have a small p or to have p and q non-random. Dialogue: 0,0:34:28.64,0:34:31.01,Default,,0000,0000,0000,,So let's do everything right. Dialogue: 0,0:34:31.01,0:34:34.24,Default,,0000,0000,0000,,Let's make just independently choose some big p Dialogue: 0,0:34:34.24,0:34:37.03,Default,,0000,0000,0000,,between 2^511 and 2^512 Dialogue: 0,0:34:37.03,0:34:38.67,Default,,0000,0000,0000,,and choose some big q Dialogue: 0,0:34:38.67,0:34:42.59,Default,,0000,0000,0000,,without being like the next prime or anywhere in the ballpark of p. Dialogue: 0,0:34:42.59,0:34:47.86,Default,,0000,0000,0000,,You could maybe say q has to be between 2^509 and 2^510 Dialogue: 0,0:34:47.86,0:34:49.52,Default,,0000,0000,0000,,and then it's definitely nowhere near p. Dialogue: 0,0:34:49.52,0:34:52.54,Default,,0000,0000,0000,,Now you got this public key and p times q Dialogue: 0,0:34:52.54,0:34:54.47,Default,,0000,0000,0000,,which is a 1024 bit RSA key. Dialogue: 0,0:34:54.47,0:34:58.74,Default,,0000,0000,0000,,If nothing has gone wrong with your randomness generation Dialogue: 0,0:34:58.74,0:35:00.15,Default,,0000,0000,0000,,then what does the attacker do? Dialogue: 0,0:35:00.15,0:35:04.47,Default,,0000,0000,0000,,Well, we don't know anything fast. Dialogue: 0,0:35:04.47,0:35:06.84,Default,,0000,0000,0000,,So this is gonna be the one part of the talk Dialogue: 0,0:35:06.84,0:35:08.50,Default,,0000,0000,0000,,where there's these big powers of 2 Dialogue: 0,0:35:08.50,0:35:09.78,Default,,0000,0000,0000,,for how fast things are Dialogue: 0,0:35:09.78,0:35:11.14,Default,,0000,0000,0000,,because they're not really fast. Dialogue: 0,0:35:11.14,0:35:14.62,Default,,0000,0000,0000,,You have to think about how much something like 2^80 is. Dialogue: 0,0:35:14.62,0:35:15.94,Default,,0000,0000,0000,,There's all these different methods, Dialogue: 0,0:35:15.94,0:35:17.94,Default,,0000,0000,0000,,I'll just skip down to the last two. Dialogue: 0,0:35:17.94,0:35:19.100,Default,,0000,0000,0000,,There's the quadratic sieve (QS), Dialogue: 0,0:35:19.100,0:35:22.11,Default,,0000,0000,0000,,the number field sieve (NFS). Dialogue: 0,0:35:22.11,0:35:24.11,Default,,0000,0000,0000,,These have been around since, well, Dialogue: 0,0:35:24.11,0:35:29.19,Default,,0000,0000,0000,,QS since the 80th, NFS since the early 90th. Dialogue: 0,0:35:29.19,0:35:32.33,Default,,0000,0000,0000,,The NFS, the general consensus is Dialogue: 0,0:35:32.33,0:35:35.20,Default,,0000,0000,0000,,it takes something like 2^80 operations. Dialogue: 0,0:35:35.20,0:35:36.68,Default,,0000,0000,0000,,Now here's something fun to try. Dialogue: 0,0:35:36.68,0:35:38.84,Default,,0000,0000,0000,,If somebody says 2^80 operations Dialogue: 0,0:35:38.84,0:35:41.47,Default,,0000,0000,0000,,and there's some cryptographer talking about the security or something, Dialogue: 0,0:35:41.47,0:35:44.24,Default,,0000,0000,0000,,ask them: what do you mean by an operation? Dialogue: 0,0:35:44.24,0:35:45.100,Default,,0000,0000,0000,,How fast is this operation? Dialogue: 0,0:35:45.100,0:35:47.48,Default,,0000,0000,0000,,And then most of the people saying this Dialogue: 0,0:35:47.48,0:35:48.62,Default,,0000,0000,0000,,will go running screaming like: Dialogue: 0,0:35:48.62,0:35:49.85,Default,,0000,0000,0000,,I don't know what an operation is, Dialogue: 0,0:35:49.85,0:35:51.19,Default,,0000,0000,0000,,don't ask me that question. Dialogue: 0,0:35:51.19,0:35:53.38,Default,,0000,0000,0000,,But still people will confidently tell you Dialogue: 0,0:35:53.38,0:35:56.23,Default,,0000,0000,0000,,that the NFS takes 2^80 operations Dialogue: 0,0:35:56.23,0:36:00.35,Default,,0000,0000,0000,,to break any 1024 bit RSA key Dialogue: 0,0:36:00.35,0:36:02.24,Default,,0000,0000,0000,,even if the user hasn't done anything wrong, Dialogue: 0,0:36:02.24,0:36:04.05,Default,,0000,0000,0000,,the implementor hasn't done anything wrong. Dialogue: 0,0:36:04.05,0:36:05.63,Default,,0000,0000,0000,,And this number, this 2^80 Dialogue: 0,0:36:05.63,0:36:07.62,Default,,0000,0000,0000,,if you pin down what those operations are, Dialogue: 0,0:36:07.62,0:36:11.10,Default,,0000,0000,0000,,this is something which is doable today Dialogue: 0,0:36:11.10,0:36:15.75,Default,,0000,0000,0000,,by people with a big botnet or people with a big computer cluster. Dialogue: 0,0:36:15.75,0:36:18.61,Default,,0000,0000,0000,,I'll give some details what I mean, the size is there. Dialogue: 0,0:36:18.61,0:36:21.80,Default,,0000,0000,0000,,As your computers get cheaper and cheaper, Dialogue: 0,0:36:21.80,0:36:23.72,Default,,0000,0000,0000,,somehow chips aren't going up in clockspeed Dialogue: 0,0:36:23.72,0:36:25.15,Default,,0000,0000,0000,,but they're still getting cheaper. Dialogue: 0,0:36:25.15,0:36:27.64,Default,,0000,0000,0000,,You can get a really cheap ARM which is doing Dialogue: 0,0:36:27.64,0:36:28.90,Default,,0000,0000,0000,,the same kind of computations Dialogue: 0,0:36:28.90,0:36:31.50,Default,,0000,0000,0000,,that a pretty big CPU was doing several years ago. Dialogue: 0,0:36:31.50,0:36:33.18,Default,,0000,0000,0000,,And chips are gonna continue getting cheaper Dialogue: 0,0:36:33.18,0:36:36.60,Default,,0000,0000,0000,,for a while. These attacks against RSA 1024 Dialogue: 0,0:36:36.60,0:36:39.57,Default,,0000,0000,0000,,are going to be common doable for more and more people. Dialogue: 0,0:36:39.57,0:36:43.12,Default,,0000,0000,0000,,How do these methods work? Dialogue: 0,0:36:43.12,0:36:47.21,Default,,0000,0000,0000,,I'll give one example and then one little Sage script. Dialogue: 0,0:36:47.21,0:36:50.17,Default,,0000,0000,0000,,Let's try just a really small number. Dialogue: 0,0:36:50.17,0:36:51.72,Default,,0000,0000,0000,,This will be with the quadratic sieve Dialogue: 0,0:36:51.72,0:36:53.73,Default,,0000,0000,0000,,which is not as fancy as the number field sieve Dialogue: 0,0:36:53.73,0:36:56.40,Default,,0000,0000,0000,,but it will give you some idea of how these methods work. Dialogue: 0,0:36:56.40,0:36:59.98,Default,,0000,0000,0000,,The QS starts with that Fermat method you heard about. Dialogue: 0,0:36:59.98,0:37:04.07,Default,,0000,0000,0000,,Remember, the idea there was to try to find a square Dialogue: 0,0:37:04.07,0:37:08.57,Default,,0000,0000,0000,,as a^2-N, so {\i1}a{\i0} was like the square root of N Dialogue: 0,0:37:08.57,0:37:10.52,Default,,0000,0000,0000,,or maybe the plus 1, plus 2 and so on Dialogue: 0,0:37:10.52,0:37:13.33,Default,,0000,0000,0000,,and you keep searching for a+1 and so on, Dialogue: 0,0:37:13.33,0:37:15.93,Default,,0000,0000,0000,,search for numbers that if you square them and subtract N Dialogue: 0,0:37:15.93,0:37:17.06,Default,,0000,0000,0000,,then you get a square. Dialogue: 0,0:37:17.06,0:37:20.71,Default,,0000,0000,0000,,So let's try that for 50=2759 which is not very big. Dialogue: 0,0:37:20.71,0:37:23.98,Default,,0000,0000,0000,,Then you try, 53 was the ceiling of the square root, Dialogue: 0,0:37:23.98,0:37:27.67,Default,,0000,0000,0000,,square that, subtract 2759, you get 50. Dialogue: 0,0:37:27.67,0:37:31.17,Default,,0000,0000,0000,,Well 25 would be a square, but 50 is not a square Dialogue: 0,0:37:31.17,0:37:33.31,Default,,0000,0000,0000,,it's 2 times 25, 2 times 5^2. Dialogue: 0,0:37:33.31,0:37:37.21,Default,,0000,0000,0000,,And then you try another number, 54^2-2759 Dialogue: 0,0:37:37.21,0:37:39.91,Default,,0000,0000,0000,,umm 157, that's too complicated Dialogue: 0,0:37:39.91,0:37:42.71,Default,,0000,0000,0000,,I don't remember that being a square so let's just skip it. Dialogue: 0,0:37:42.71,0:37:45.69,Default,,0000,0000,0000,,And then you keep going like this, 266, 377, Dialogue: 0,0:37:45.69,0:37:48.22,Default,,0000,0000,0000,,{\b1}490{\b0}. I remember 49 is a square Dialogue: 0,0:37:48.22,0:37:50.35,Default,,0000,0000,0000,,but that doesn't mean that 490 is a square Dialogue: 0,0:37:50.35,0:37:52.37,Default,,0000,0000,0000,,cause 10, 2 times 5, that's not a square. Dialogue: 0,0:37:52.37,0:37:55.87,Default,,0000,0000,0000,,And 605, you can try... Dialogue: 0,0:37:55.87,0:37:58.64,Default,,0000,0000,0000,,We remember how to take out the 5 Dialogue: 0,0:37:58.64,0:38:01.28,Default,,0000,0000,0000,,and then 60... 605 divided by 5. Dialogue: 0,0:38:01.28,0:38:03.59,Default,,0000,0000,0000,,You can figure out it's 5 times 11^2. Dialogue: 0,0:38:03.59,0:38:05.16,Default,,0000,0000,0000,,It's almost a square. Dialogue: 0,0:38:05.16,0:38:06.77,Default,,0000,0000,0000,,You keep doing this for a while Dialogue: 0,0:38:06.77,0:38:10.53,Default,,0000,0000,0000,,and it seems like Fermat's method is actually working pretty badly. Dialogue: 0,0:38:10.53,0:38:13.75,Default,,0000,0000,0000,,It does work eventually but it's taking quite a while. Dialogue: 0,0:38:13.75,0:38:16.67,Default,,0000,0000,0000,,Here's what the quadratic sieve does. Dialogue: 0,0:38:16.67,0:38:19.53,Default,,0000,0000,0000,,From the same computation you look at these Dialogue: 0,0:38:19.53,0:38:21.58,Default,,0000,0000,0000,,numbers that were not exactly squares Dialogue: 0,0:38:21.58,0:38:23.63,Default,,0000,0000,0000,,50 and 490 and 605 Dialogue: 0,0:38:23.63,0:38:27.06,Default,,0000,0000,0000,,and you notice if you multiple them together Dialogue: 0,0:38:27.06,0:38:28.47,Default,,0000,0000,0000,,50 was 2 times 5^2 Dialogue: 0,0:38:28.47,0:38:30.76,Default,,0000,0000,0000,,490 is 2 times 5 times 7^2 Dialogue: 0,0:38:30.76,0:38:33.07,Default,,0000,0000,0000,,605 is 5 times 11^2 Dialogue: 0,0:38:33.07,0:38:34.58,Default,,0000,0000,0000,,and then you multiply those together Dialogue: 0,0:38:34.58,0:38:38.52,Default,,0000,0000,0000,,you get 2^2 and 5^4 and 7^2 and 11^2 Dialogue: 0,0:38:38.52,0:38:41.12,Default,,0000,0000,0000,,and that's exactly the square of something. Dialogue: 0,0:38:41.12,0:38:44.59,Default,,0000,0000,0000,,The square of 2^1 times 5^2 times 7 times 11. Dialogue: 0,0:38:44.59,0:38:48.18,Default,,0000,0000,0000,,Then the quadratic sieve is taking the square root of that number Dialogue: 0,0:38:48.18,0:38:52.55,Default,,0000,0000,0000,,and subtracting that from the product of the fifty-somethings Dialogue: 0,0:38:52.55,0:38:53.95,Default,,0000,0000,0000,,that were on the left side Dialogue: 0,0:38:53.95,0:38:56.83,Default,,0000,0000,0000,,and taking the greatest common divisor of that with N Dialogue: 0,0:38:56.83,0:38:59.79,Default,,0000,0000,0000,,and amazingly that produces a factor of N. Dialogue: 0,0:38:59.79,0:39:02.29,Default,,0000,0000,0000,,And it's not just some random accident that Dialogue: 0,0:39:02.29,0:39:04.37,Default,,0000,0000,0000,,if you had tried the greatest common divisor of Dialogue: 0,0:39:04.37,0:39:06.08,Default,,0000,0000,0000,,"write down some hocuspocus then" Dialogue: 0,0:39:06.08,0:39:08.80,Default,,0000,0000,0000,,"you eventually get 31 coming out" Dialogue: 0,0:39:08.80,0:39:10.58,Default,,0000,0000,0000,,"every 31 times you write down a random number" Dialogue: 0,0:39:10.58,0:39:13.02,Default,,0000,0000,0000,,"it will have this 31 dividing it" Dialogue: 0,0:39:13.02,0:39:15.35,Default,,0000,0000,0000,,No, you can try this for bigger and bigger numbers Dialogue: 0,0:39:15.35,0:39:17.04,Default,,0000,0000,0000,,and actually this keeps working. Dialogue: 0,0:39:17.04,0:39:18.66,Default,,0000,0000,0000,,As soon as you find a square product Dialogue: 0,0:39:18.66,0:39:23.21,Default,,0000,0000,0000,,then half of those square products are gonna factor N. Dialogue: 0,0:39:23.21,0:39:25.36,Default,,0000,0000,0000,,So that's how the quadratic sieve works. Dialogue: 0,0:39:25.36,0:39:28.92,Default,,0000,0000,0000,,Here's a more systematic script with a much bigger number Dialogue: 0,0:39:28.92,0:39:31.30,Default,,0000,0000,0000,,which if it were just hocuspocus this wouldn't work. Dialogue: 0,0:39:31.30,0:39:32.62,Default,,0000,0000,0000,,But this does work. Dialogue: 0,0:39:32.62,0:39:36.83,Default,,0000,0000,0000,,So there's a number from my computer's random number generator Dialogue: 0,0:39:36.83,0:39:41.66,Default,,0000,0000,0000,,31415926... {\i1}laughter{\i0} Dialogue: 0,0:39:41.66,0:39:45.10,Default,,0000,0000,0000,,You try writing down a bunch of squares... Dialogue: 0,0:39:45.10,0:39:48.28,Default,,0000,0000,0000,,maybe I should get my computer's random number generator checked. Dialogue: 0,0:39:48.28,0:39:50.64,Default,,0000,0000,0000,,It is this two year old laptop you heard about before Dialogue: 0,0:39:50.64,0:39:52.20,Default,,0000,0000,0000,,so I'm not sure it's working properly. Dialogue: 0,0:39:52.20,0:39:55.60,Default,,0000,0000,0000,,You take a bunch of a^2-N and then Dialogue: 0,0:39:55.60,0:39:57.41,Default,,0000,0000,0000,,let's make a list of those called X. Dialogue: 0,0:39:57.41,0:40:00.75,Default,,0000,0000,0000,,You can see the range, there is up to 500.000 numbers. Dialogue: 0,0:40:00.75,0:40:02.95,Default,,0000,0000,0000,,It's a pretty big list we're talking about. Dialogue: 0,0:40:02.95,0:40:05.75,Default,,0000,0000,0000,,And then search through those elements, Dialogue: 0,0:40:05.75,0:40:08.54,Default,,0000,0000,0000,,search through those a^2-N, those differences, Dialogue: 0,0:40:08.54,0:40:09.50,Default,,0000,0000,0000,,the elements in this list, Dialogue: 0,0:40:09.50,0:40:12.98,Default,,0000,0000,0000,,to see which ones have easy factorizations. Dialogue: 0,0:40:12.98,0:40:15.44,Default,,0000,0000,0000,,Now a lot of numbers like that 157 Dialogue: 0,0:40:15.44,0:40:16.97,Default,,0000,0000,0000,,I know what the factorization of that is Dialogue: 0,0:40:16.97,0:40:19.85,Default,,0000,0000,0000,,but there is function which you can find on our website Dialogue: 0,0:40:19.85,0:40:22.70,Default,,0000,0000,0000,,easyfactorizations() which looks through the list X Dialogue: 0,0:40:22.70,0:40:25.25,Default,,0000,0000,0000,,and if it finds numbers that are easy to factor Dialogue: 0,0:40:25.25,0:40:27.94,Default,,0000,0000,0000,,then it quickly writes down the factorizations Dialogue: 0,0:40:27.94,0:40:30.48,Default,,0000,0000,0000,,using the small prime techniques you heard about. Dialogue: 0,0:40:30.48,0:40:33.17,Default,,0000,0000,0000,,And then makes a list of those easy factorizations, Dialogue: 0,0:40:33.17,0:40:34.40,Default,,0000,0000,0000,,puts those into F. Dialogue: 0,0:40:34.40,0:40:37.60,Default,,0000,0000,0000,,And then there's a big chunk which I won't try to explain Dialogue: 0,0:40:37.60,0:40:39.99,Default,,0000,0000,0000,,which is called linear algebra mod 2. Dialogue: 0,0:40:39.99,0:40:42.59,Default,,0000,0000,0000,,And that somehow figures out a square Dialogue: 0,0:40:42.59,0:40:45.70,Default,,0000,0000,0000,,that comes from the factorizations, Dialogue: 0,0:40:45.70,0:40:48.36,Default,,0000,0000,0000,,somehow looks through this list of factorizations Dialogue: 0,0:40:48.36,0:40:50.80,Default,,0000,0000,0000,,and magically applies some linear algebra stuff. Dialogue: 0,0:40:50.80,0:40:52.61,Default,,0000,0000,0000,,Well ok, I won't go through that. Dialogue: 0,0:40:52.61,0:40:54.07,Default,,0000,0000,0000,,It's something doable Dialogue: 0,0:40:54.07,0:40:58.60,Default,,0000,0000,0000,,and this is using some standard Sage functions to do it pretty easily. Dialogue: 0,0:40:58.60,0:41:01.74,Default,,0000,0000,0000,,There's all sorts of things that Dialogue: 0,0:41:01.74,0:41:03.66,Default,,0000,0000,0000,,in the interest of time I won't get into Dialogue: 0,0:41:03.66,0:41:05.87,Default,,0000,0000,0000,,like how this easyfactorizations() works. Dialogue: 0,0:41:05.87,0:41:07.60,Default,,0000,0000,0000,,And this is something where people write papers Dialogue: 0,0:41:07.60,0:41:09.80,Default,,0000,0000,0000,,and papers and papers talking about trying to make this Dialogue: 0,0:41:09.80,0:41:11.60,Default,,0000,0000,0000,,go as quickly as possible. Dialogue: 0,0:41:11.60,0:41:14.74,Default,,0000,0000,0000,,I do want to emphasize one fact about these methods: Dialogue: 0,0:41:14.74,0:41:17.48,Default,,0000,0000,0000,,the bold-faced **very small memory requirements**. Dialogue: 0,0:41:17.48,0:41:20.04,Default,,0000,0000,0000,,You can use the elliptic curve method Dialogue: 0,0:41:20.04,0:41:21.53,Default,,0000,0000,0000,,that you heard about before Dialogue: 0,0:41:21.53,0:41:24.88,Default,,0000,0000,0000,,you can use that to figure out easy factorizations Dialogue: 0,0:41:24.88,0:41:27.06,Default,,0000,0000,0000,,using very little memory. Dialogue: 0,0:41:27.06,0:41:28.50,Default,,0000,0000,0000,,That means you can build a chip Dialogue: 0,0:41:28.50,0:41:30.47,Default,,0000,0000,0000,,like a FPGA, a special purpose ASIC, Dialogue: 0,0:41:30.47,0:41:33.28,Default,,0000,0000,0000,,you can have thousands of little ECM units Dialogue: 0,0:41:33.28,0:41:35.07,Default,,0000,0000,0000,,running in parallel, so you can really Dialogue: 0,0:41:35.07,0:41:38.15,Default,,0000,0000,0000,,massively parallelize this easyfactorizations() function. Dialogue: 0,0:41:38.15,0:41:40.19,Default,,0000,0000,0000,,So if people tell you "oh you need tons of Dialogue: 0,0:41:40.19,0:41:43.39,Default,,0000,0000,0000,,memory for sieving to find easy factorizations" Dialogue: 0,0:41:43.39,0:41:45.87,Default,,0000,0000,0000,,then you should tell them "no no, that's not true" Dialogue: 0,0:41:45.87,0:41:47.98,Default,,0000,0000,0000,,"ECM you can do with very little memory Dialogue: 0,0:41:47.98,0:41:50.35,Default,,0000,0000,0000,,running massively parallelizable" Dialogue: 0,0:41:50.35,0:41:52.80,Default,,0000,0000,0000,,And then there's other things which, Dialogue: 0,0:41:52.80,0:41:54.49,Default,,0000,0000,0000,,I suppose if we had another hour Dialogue: 0,0:41:54.49,0:41:56.43,Default,,0000,0000,0000,,then we could get into all these details Dialogue: 0,0:41:56.43,0:41:59.12,Default,,0000,0000,0000,,of like how the number field sieve goes beyond this. Dialogue: 0,0:41:59.12,0:42:01.97,Default,,0000,0000,0000,,It's a similar kind of method but gets more complicated. Dialogue: 0,0:42:01.97,0:42:05.18,Default,,0000,0000,0000,,I do want to emphasize again thing in bold-face here Dialogue: 0,0:42:05.18,0:42:06.95,Default,,0000,0000,0000,,which is that if somebody tells you Dialogue: 0,0:42:06.95,0:42:10.44,Default,,0000,0000,0000,,"oh 2^80 operations, the attacker wouldn't do Dialogue: 0,0:42:10.44,0:42:13.80,Default,,0000,0000,0000,,that because the target isn't worth that much to them" Dialogue: 0,0:42:13.80,0:42:18.28,Default,,0000,0000,0000,,Well, **Batch NFS** is a way to take a bunch of N's Dialogue: 0,0:42:18.28,0:42:20.57,Default,,0000,0000,0000,,and like the batch techniques before Dialogue: 0,0:42:20.57,0:42:23.52,Default,,0000,0000,0000,,there's some magic ways to find redundancies Dialogue: 0,0:42:23.52,0:42:25.88,Default,,0000,0000,0000,,between doing factorizations of those N's. Dialogue: 0,0:42:25.88,0:42:26.94,Default,,0000,0000,0000,,So somebody tells you: Dialogue: 0,0:42:26.94,0:42:30.00,Default,,0000,0000,0000,,"oh 2^80, that isn't worth it for the attacker." Dialogue: 0,0:42:30.00,0:42:33.30,Default,,0000,0000,0000,,Well, **Batch NFS** reduces the cost quite a bit Dialogue: 0,0:42:33.30,0:42:34.82,Default,,0000,0000,0000,,for factoring each key. Dialogue: 0,0:42:34.82,0:42:36.85,Default,,0000,0000,0000,,If the attacker has a lot of keys to target Dialogue: 0,0:42:36.85,0:42:39.85,Default,,0000,0000,0000,,they can factor all of them in not much more cost Dialogue: 0,0:42:39.85,0:42:41.40,Default,,0000,0000,0000,,than just factoring one. Dialogue: 0,0:42:41.40,0:42:43.73,Default,,0000,0000,0000,,So don't believe people who take an economic view Dialogue: 0,0:42:43.73,0:42:46.99,Default,,0000,0000,0000,,how much the number field sieve is worth. Dialogue: 0,0:42:46.99,0:42:49.42,Default,,0000,0000,0000,,Alright, what does this mean? Dialogue: 0,0:42:49.42,0:42:52.12,Default,,0000,0000,0000,,Can the attacker actually do the NFS Dialogue: 0,0:42:52.12,0:42:54.13,Default,,0000,0000,0000,,once they've put in all these optimizations? Dialogue: 0,0:42:54.13,0:42:59.06,Default,,0000,0000,0000,,Well if you look carefully at the analyses of the NFS Dialogue: 0,0:42:59.06,0:43:02.42,Default,,0000,0000,0000,,there are only about 2^70 differences. Dialogue: 0,0:43:02.42,0:43:04.15,Default,,0000,0000,0000,,Things like these a^2-N's. Dialogue: 0,0:43:04.15,0:43:08.86,Default,,0000,0000,0000,,If you look through 2^70 of those and scan them properly, Dialogue: 0,0:43:08.86,0:43:10.77,Default,,0000,0000,0000,,find easy factorizations, do linear algebra, Dialogue: 0,0:43:10.77,0:43:13.67,Default,,0000,0000,0000,,you will factor any 1024 bit key. Dialogue: 0,0:43:13.67,0:43:16.31,Default,,0000,0000,0000,,And 2^70, how big is that number? Dialogue: 0,0:43:16.31,0:43:20.82,Default,,0000,0000,0000,,It's actually small enough that you can do this computation on Dialogue: 0,0:43:20.82,0:43:22.47,Default,,0000,0000,0000,,your favorite botnet. Dialogue: 0,0:43:22.47,0:43:25.75,Default,,0000,0000,0000,,Say, Conficker is shrinking, still Dialogue: 0,0:43:25.75,0:43:27.95,Default,,0000,0000,0000,,and it will probably be wiped out at some point Dialogue: 0,0:43:27.95,0:43:29.49,Default,,0000,0000,0000,,but it's an example of what you can do Dialogue: 0,0:43:29.49,0:43:32.47,Default,,0000,0000,0000,,using any of these security problems that are deployed Dialogue: 0,0:43:32.47,0:43:33.63,Default,,0000,0000,0000,,on enough machines. Dialogue: 0,0:43:33.63,0:43:35.40,Default,,0000,0000,0000,,You can break into a bunch of machines, Dialogue: 0,0:43:35.40,0:43:36.52,Default,,0000,0000,0000,,millions of machines. Dialogue: 0,0:43:36.52,0:43:40.30,Default,,0000,0000,0000,,Conficker estimates vary between 7 million and 12 million machines. Dialogue: 0,0:43:40.30,0:43:44.32,Default,,0000,0000,0000,,So use your, say, 2^23, that's 8 million machines. Dialogue: 0,0:43:44.32,0:43:46.52,Default,,0000,0000,0000,,Count how many seconds there are in a year Dialogue: 0,0:43:46.52,0:43:48.55,Default,,0000,0000,0000,,and then, say, ok that means we have to do Dialogue: 0,0:43:48.55,0:43:52.07,Default,,0000,0000,0000,,2^22 differences per second machine. Dialogue: 0,0:43:52.07,0:43:56.90,Default,,0000,0000,0000,,And that is slower than state of the art factorization code already runs. Dialogue: 0,0:43:56.90,0:43:59.23,Default,,0000,0000,0000,,So it's actually a pretty easy computation. Dialogue: 0,0:43:59.23,0:44:02.33,Default,,0000,0000,0000,,You don't even need that many millions of computers to do this. Dialogue: 0,0:44:02.33,0:44:04.47,Default,,0000,0000,0000,,If people tell you "wait a minute" Dialogue: 0,0:44:04.47,0:44:06.12,Default,,0000,0000,0000,,"you can't just use a bunch of machines" Dialogue: 0,0:44:06.12,0:44:08.07,Default,,0000,0000,0000,,"there's all this work for linear algebra" Dialogue: 0,0:44:08.07,0:44:09.97,Default,,0000,0000,0000,,Then I'll just skip this. Dialogue: 0,0:44:09.97,0:44:12.88,Default,,0000,0000,0000,,Be aware that linear algebra is not as much of a problem Dialogue: 0,0:44:12.88,0:44:15.33,Default,,0000,0000,0000,,as some people would say. Dialogue: 0,0:44:15.33,0:44:18.87,Default,,0000,0000,0000,,If you use a big botnet there's one little problem. Dialogue: 0,0:44:18.87,0:44:21.05,Default,,0000,0000,0000,,For an attacker who breaks into a bunch of machines Dialogue: 0,0:44:21.05,0:44:23.90,Default,,0000,0000,0000,,and then starts spinning them up, heating up the CPU, Dialogue: 0,0:44:23.90,0:44:25.92,Default,,0000,0000,0000,,the fan starts running, the user starts wondering Dialogue: 0,0:44:25.92,0:44:28.02,Default,,0000,0000,0000,,"why is my machine running so slowly?" Dialogue: 0,0:44:28.02,0:44:30.13,Default,,0000,0000,0000,,Maybe only use half of the CPU Dialogue: 0,0:44:30.13,0:44:33.57,Default,,0000,0000,0000,,but still it has still got a good chance of getting you detected Dialogue: 0,0:44:33.57,0:44:35.20,Default,,0000,0000,0000,,and kicked off the machines. Dialogue: 0,0:44:35.20,0:44:37.27,Default,,0000,0000,0000,,Users are gonna shut you down if you're doing a Dialogue: 0,0:44:37.27,0:44:39.46,Default,,0000,0000,0000,,say, year of computation on your botnet. Dialogue: 0,0:44:39.46,0:44:42.88,Default,,0000,0000,0000,,So what do you do instead? Dialogue: 0,0:44:42.88,0:44:45.02,Default,,0000,0000,0000,,Well you build a little computer cluster. Dialogue: 0,0:44:45.02,0:44:49.35,Default,,0000,0000,0000,,Now yesterday we heard about a big building Dialogue: 0,0:44:49.35,0:44:51.16,Default,,0000,0000,0000,,in Bluffdale, Utah, that apparently Dialogue: 0,0:44:51.16,0:44:54.83,Default,,0000,0000,0000,,is going to store all of the data collected by Dialogue: 0,0:44:54.83,0:44:57.17,Default,,0000,0000,0000,,the NSA for the next hundred years Dialogue: 0,0:44:57.17,0:44:58.85,Default,,0000,0000,0000,,or maybe forever. Dialogue: 0,0:44:58.85,0:45:00.91,Default,,0000,0000,0000,,But something that I didn't hear emphasized yesterday Dialogue: 0,0:45:00.91,0:45:04.92,Default,,0000,0000,0000,,was that this building also has a new power substation Dialogue: 0,0:45:04.92,0:45:08.15,Default,,0000,0000,0000,,which is drawing 65 megawatts, Dialogue: 0,0:45:08.15,0:45:10.16,Default,,0000,0000,0000,,well generating 65 megawatts. Dialogue: 0,0:45:10.16,0:45:13.100,Default,,0000,0000,0000,,Now what are we doing with 65 megawatts? Dialogue: 0,0:45:13.100,0:45:15.31,Default,,0000,0000,0000,,Is that the kind of power that you need to Dialogue: 0,0:45:15.31,0:45:17.49,Default,,0000,0000,0000,,store a bunch of data on tapes? Dialogue: 0,0:45:17.49,0:45:21.18,Default,,0000,0000,0000,,No, that's the kind of power you need to do computations. Dialogue: 0,0:45:21.18,0:45:24.72,Default,,0000,0000,0000,,So what is NSA doing with 2^26 watts? Dialogue: 0,0:45:24.72,0:45:26.96,Default,,0000,0000,0000,,Or maybe even with more watts. Dialogue: 0,0:45:26.96,0:45:30.91,Default,,0000,0000,0000,,You shouldn't actually think that 2^26 is such a big number. Dialogue: 0,0:45:30.91,0:45:33.53,Default,,0000,0000,0000,,Here's a little table with, well, Dialogue: 0,0:45:33.53,0:45:36.57,Default,,0000,0000,0000,,2^57 admittedly is pushing it a little bit. Dialogue: 0,0:45:36.57,0:45:40.62,Default,,0000,0000,0000,,This is the total power that the earth gets from the sun Dialogue: 0,0:45:40.62,0:45:43.21,Default,,0000,0000,0000,,of which about half gets to the earth's surface. Dialogue: 0,0:45:43.21,0:45:47.61,Default,,0000,0000,0000,,2^44 is the amount the human is using right now. Dialogue: 0,0:45:47.61,0:45:50.89,Default,,0000,0000,0000,,Varies a little bit but I mean this is the average power Dialogue: 0,0:45:50.89,0:45:53.43,Default,,0000,0000,0000,,including cars and such. Dialogue: 0,0:45:53.43,0:45:56.45,Default,,0000,0000,0000,,If you have the botnet that breaks into millions of machines Dialogue: 0,0:45:56.45,0:45:59.94,Default,,0000,0000,0000,,and runs in flat-out that's about 2^30 watts. Dialogue: 0,0:45:59.94,0:46:01.61,Default,,0000,0000,0000,,And actually if you think about it, wait a minute, Dialogue: 0,0:46:01.61,0:46:02.58,Default,,0000,0000,0000,,there's a lot of machines out there. Dialogue: 0,0:46:02.58,0:46:07.27,Default,,0000,0000,0000,,This means the 2^26 is not actually that much power. Dialogue: 0,0:46:07.27,0:46:11.46,Default,,0000,0000,0000,,It's just one dinky little Bluffdale 65 MW computer center Dialogue: 0,0:46:11.46,0:46:14.59,Default,,0000,0000,0000,,and actually if you're a government agency Dialogue: 0,0:46:14.59,0:46:16.14,Default,,0000,0000,0000,,you probably have more than one of those. Dialogue: 0,0:46:16.14,0:46:19.27,Default,,0000,0000,0000,,As you heard yesterday in the context of data storage Dialogue: 0,0:46:19.27,0:46:21.29,Default,,0000,0000,0000,,but again, it's not just data storage. Dialogue: 0,0:46:21.29,0:46:26.49,Default,,0000,0000,0000,,You don't make a 65 MW power station to just store data. Dialogue: 0,0:46:26.49,0:46:30.21,Default,,0000,0000,0000,,Ok, if you just take standard graphics processing units Dialogue: 0,0:46:30.21,0:46:33.22,Default,,0000,0000,0000,,and run 2^26 watts to those that will do about Dialogue: 0,0:46:33.22,0:46:36.45,Default,,0000,0000,0000,,2^84 floating point multiplications per year. Dialogue: 0,0:46:36.45,0:46:39.83,Default,,0000,0000,0000,,You have to figure out, ok, what are exactly the operations involved here. Dialogue: 0,0:46:39.83,0:46:44.83,Default,,0000,0000,0000,,This should be enough to break 1024 bit RSA Dialogue: 0,0:46:44.83,0:46:48.09,Default,,0000,0000,0000,,and if NSA is not just buying GPU's off-the-shelves Dialogue: 0,0:46:48.09,0:46:50.23,Default,,0000,0000,0000,,but really tuning chips that they build Dialogue: 0,0:46:50.23,0:46:57.41,Default,,0000,0000,0000,,using IBM to manufacture their chips at the moment. Dialogue: 0,0:46:57.41,0:47:01.63,Default,,0000,0000,0000,,Apparently it wasn't cost-effective for NSA to manufacture their own chips Dialogue: 0,0:47:01.63,0:47:04.48,Default,,0000,0000,0000,,so in 2005 they started subcontracting for IBM Dialogue: 0,0:47:04.48,0:47:08.15,Default,,0000,0000,0000,,but presumably through that fabrication IBM is building chips Dialogue: 0,0:47:08.15,0:47:11.07,Default,,0000,0000,0000,,that NSA wants and those should be about 10 times faster Dialogue: 0,0:47:11.07,0:47:13.02,Default,,0000,0000,0000,,than what GPU's can do. Dialogue: 0,0:47:13.02,0:47:18.36,Default,,0000,0000,0000,,So it should be possible with this little 65 MW computer cluster Dialogue: 0,0:47:18.36,0:47:21.48,Default,,0000,0000,0000,,to factor at least 1, maybe even 10, Dialogue: 0,0:47:21.48,0:47:23.48,Default,,0000,0000,0000,,and then with batch NFS maybe even more Dialogue: 0,0:47:23.48,0:47:30.01,Default,,0000,0000,0000,,1024 bit RSA keys in a year. Dialogue: 0,0:47:30.01,0:47:38.23,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:47:38.23,0:47:41.13,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: So to conclude things up here I want to Dialogue: 0,0:47:41.13,0:47:43.29,Default,,0000,0000,0000,,explain how you can use Dialogue: 0,0:47:43.29,0:47:46.06,Default,,0000,0000,0000,,from the comfort of your very own home Dialogue: 0,0:47:46.06,0:47:52.24,Default,,0000,0000,0000,,a distributed, a massive scale distributed cloud computing service Dialogue: 0,0:47:52.24,0:47:57.14,Default,,0000,0000,0000,,to calculate private keys on your own. Dialogue: 0,0:47:57.14,0:48:00.31,Default,,0000,0000,0000,,So many of you may be familiar with Amazon EC2 Dialogue: 0,0:48:00.31,0:48:04.64,Default,,0000,0000,0000,,but it turns out Google also has a large amount of computing infrastructure Dialogue: 0,0:48:04.64,0:48:07.34,Default,,0000,0000,0000,,and they actually have a very convenient web interface Dialogue: 0,0:48:07.34,0:48:08.45,Default,,0000,0000,0000,,to access it. Dialogue: 0,0:48:08.45,0:48:12.98,Default,,0000,0000,0000,,{\i1}laugther{\i0} Dialogue: 0,0:48:12.98,0:48:21.68,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:48:21.68,0:48:23.96,Default,,0000,0000,0000,,It's amazing what you can find on the Internet. Dialogue: 0,0:48:23.96,0:48:26.14,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:48:26.14,0:48:29.39,Default,,0000,0000,0000,,So ok, here's some keys except, you know, Dialogue: 0,0:48:29.39,0:48:30.58,Default,,0000,0000,0000,,if you look at these carefully Dialogue: 0,0:48:30.58,0:48:33.28,Default,,0000,0000,0000,,not all of these are sort of obviously RSA keys. Dialogue: 0,0:48:33.28,0:48:35.20,Default,,0000,0000,0000,,There are some problems here Dialogue: 0,0:48:35.20,0:48:40.70,Default,,0000,0000,0000,,like the second to last one on the bottom. Dialogue: 0,0:48:40.70,0:48:41.69,Default,,0000,0000,0000,,So... Dialogue: 0,0:48:41.69,0:48:43.34,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:48:43.34,0:48:49.82,Default,,0000,0000,0000,,After doing this search we found this key and Dialogue: 0,0:48:49.82,0:48:55.28,Default,,0000,0000,0000,,someone seems to have pasted a private key into pastebin Dialogue: 0,0:48:55.28,0:49:00.49,Default,,0000,0000,0000,,and someone came along and interrupted part of it Dialogue: 0,0:49:00.49,0:49:04.76,Default,,0000,0000,0000,,with some profanity. Dialogue: 0,0:49:04.76,0:49:07.39,Default,,0000,0000,0000,,This is an interesting problem. Dialogue: 0,0:49:07.39,0:49:08.81,Default,,0000,0000,0000,,What do we do with this key? Dialogue: 0,0:49:08.81,0:49:12.31,Default,,0000,0000,0000,,Clearly this is an interesting key, we must have this key. Dialogue: 0,0:49:12.31,0:49:14.20,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:49:14.20,0:49:24.85,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:49:24.85,0:49:26.05,Default,,0000,0000,0000,,Step 1... yeah? Dialogue: 0,0:49:26.05,0:49:29.57,Default,,0000,0000,0000,,{\i1}Male{\i0}: Did you see the easter egg in row 1? Dialogue: 0,0:49:29.57,0:49:31.20,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: Well, we'll discuss this. Dialogue: 0,0:49:31.20,0:49:34.31,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Questions will be later, after the talk please. Dialogue: 0,0:49:34.31,0:49:39.37,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: So yeah, we've removed the obvious problems here. Dialogue: 0,0:49:39.37,0:49:41.64,Default,,0000,0000,0000,,But there's still an issue which is that Dialogue: 0,0:49:41.64,0:49:43.84,Default,,0000,0000,0000,,we're missing hundreds and hundreds of bits of key. Dialogue: 0,0:49:43.84,0:49:45.94,Default,,0000,0000,0000,,We can't brute force-this. Dialogue: 0,0:49:45.94,0:49:47.66,Default,,0000,0000,0000,,What are we gonna do? Dialogue: 0,0:49:47.66,0:49:51.33,Default,,0000,0000,0000,,Well, let's look at what RSA keys actually are. Dialogue: 0,0:49:51.33,0:49:53.51,Default,,0000,0000,0000,,I introduced RSA keys and I was, like, Dialogue: 0,0:49:53.51,0:49:56.79,Default,,0000,0000,0000,,it's a d and d has like a thosand of bits. Dialogue: 0,0:49:56.79,0:50:00.67,Default,,0000,0000,0000,,And if we don't know p and q Dialogue: 0,0:50:00.67,0:50:02.61,Default,,0000,0000,0000,,how are we gonna get this d? Dialogue: 0,0:50:02.61,0:50:07.92,Default,,0000,0000,0000,,Here is the storage format for an RSA key. Dialogue: 0,0:50:07.92,0:50:11.26,Default,,0000,0000,0000,,Public key is the modulus N, the public exponent e. Dialogue: 0,0:50:11.26,0:50:14.71,Default,,0000,0000,0000,,Ok, private key has version, N, e, Dialogue: 0,0:50:14.71,0:50:16.54,Default,,0000,0000,0000,,d the decryption exponent, Dialogue: 0,0:50:16.54,0:50:20.27,Default,,0000,0000,0000,,p, q, d mod (p-1), d mod (q-1), Dialogue: 0,0:50:20.27,0:50:22.98,Default,,0000,0000,0000,,the inverse of q mod p, Dialogue: 0,0:50:22.98,0:50:25.30,Default,,0000,0000,0000,,this is all useful information if you want to Dialogue: 0,0:50:25.30,0:50:26.96,Default,,0000,0000,0000,,speed up your calculation and not have to Dialogue: 0,0:50:26.96,0:50:29.40,Default,,0000,0000,0000,,compute everything every time you use your key. Dialogue: 0,0:50:29.40,0:50:32.49,Default,,0000,0000,0000,,Okay. Dialogue: 0,0:50:32.49,0:50:35.95,Default,,0000,0000,0000,,What did we see here then? Dialogue: 0,0:50:35.95,0:50:40.98,Default,,0000,0000,0000,,Here is the key broken up into all of the difference pieces. Dialogue: 0,0:50:40.98,0:50:44.80,Default,,0000,0000,0000,,So we have: the red bit is approximately where N is sitting. Dialogue: 0,0:50:44.80,0:50:46.75,Default,,0000,0000,0000,,We've got e in orange. Dialogue: 0,0:50:46.75,0:50:50.57,Default,,0000,0000,0000,,We've got part of d in yellow. Dialogue: 0,0:50:50.57,0:50:52.37,Default,,0000,0000,0000,,We seem to be missing p Dialogue: 0,0:50:52.37,0:50:54.66,Default,,0000,0000,0000,,but we've got part of q Dialogue: 0,0:50:54.66,0:50:56.79,Default,,0000,0000,0000,,and then here's d mod p-1 Dialogue: 0,0:50:56.79,0:51:02.41,Default,,0000,0000,0000,,and d mod q-1 and q inverse mod p. Dialogue: 0,0:51:02.41,0:51:07.71,Default,,0000,0000,0000,,There's also a little problem before the red here Dialogue: 0,0:51:07.71,0:51:08.44,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:51:08.44,0:51:10.50,Default,,0000,0000,0000,,in addition. Dialogue: 0,0:51:10.50,0:51:13.56,Default,,0000,0000,0000,,You might call this the private part of the private key. Dialogue: 0,0:51:13.56,0:51:15.94,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:51:15.94,0:51:21.39,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:51:21.39,0:51:23.86,Default,,0000,0000,0000,,Fortunately this is just sitting in an encoding of the length Dialogue: 0,0:51:23.86,0:51:30.28,Default,,0000,0000,0000,,and the version. {\i1}laughter{\i0} Dialogue: 0,0:51:30.28,0:51:33.15,Default,,0000,0000,0000,,Alright, so what do we do with this information? Dialogue: 0,0:51:33.15,0:51:36.67,Default,,0000,0000,0000,,Basically given any part of this private key Dialogue: 0,0:51:36.67,0:51:38.91,Default,,0000,0000,0000,,we can easily compute all of the other parts. Dialogue: 0,0:51:38.91,0:51:40.26,Default,,0000,0000,0000,,Simple formulas: Dialogue: 0,0:51:40.26,0:51:48.94,Default,,0000,0000,0000,,q will be 2^(e times d mod p-1) - 1 and GCD that with N Dialogue: 0,0:51:48.94,0:51:51.87,Default,,0000,0000,0000,,then we get q and then Dialogue: 0,0:51:51.87,0:51:54.46,Default,,0000,0000,0000,,we can figure out what p was by dividing Dialogue: 0,0:51:54.46,0:51:56.39,Default,,0000,0000,0000,,and figure out what d is Dialogue: 0,0:51:56.39,0:51:57.95,Default,,0000,0000,0000,,and so on and so forth. Dialogue: 0,0:51:57.95,0:52:02.46,Default,,0000,0000,0000,,You can do this even if you have a part of a single value Dialogue: 0,0:52:02.46,0:52:04.11,Default,,0000,0000,0000,,from the private key. Dialogue: 0,0:52:04.11,0:52:08.20,Default,,0000,0000,0000,,You can still compute the rest of the private key from that. Dialogue: 0,0:52:08.20,0:52:12.34,Default,,0000,0000,0000,,We don't have time to get into this but it's online. Dialogue: 0,0:52:12.34,0:52:16.56,Default,,0000,0000,0000,,You've seen a little bit of math. Dialogue: 0,0:52:16.56,0:52:18.06,Default,,0000,0000,0000,,Single formulas, typed into Sage. Dialogue: 0,0:52:18.06,0:52:22.59,Default,,0000,0000,0000,,We can reconstruct the private key here. Dialogue: 0,0:52:22.59,0:52:29.49,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:52:29.49,0:52:32.94,Default,,0000,0000,0000,,So, what are the lessons that we can learn Dialogue: 0,0:52:32.94,0:52:35.55,Default,,0000,0000,0000,,from everything that we've done today. Dialogue: 0,0:52:35.55,0:52:38.94,Default,,0000,0000,0000,,The first one is: stop using 1024 bit RSA Dialogue: 0,0:52:38.94,0:52:41.01,Default,,0000,0000,0000,,if you haven't already. Dialogue: 0,0:52:41.01,0:52:43.39,Default,,0000,0000,0000,,I have looked at the keys that are out there on the Internet Dialogue: 0,0:52:43.39,0:52:45.94,Default,,0000,0000,0000,,and you are still using 1024 bit RSA. Dialogue: 0,0:52:45.94,0:52:48.46,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:52:48.46,0:52:51.79,Default,,0000,0000,0000,,Second: make sure your primes are big enough. Dialogue: 0,0:52:51.79,0:52:54.23,Default,,0000,0000,0000,,Don't try to be clever about how you're generating them. Dialogue: 0,0:52:54.23,0:52:58.02,Default,,0000,0000,0000,,Make sure your primes are random. Dialogue: 0,0:52:58.02,0:52:59.30,Default,,0000,0000,0000,,You guys have some problems Dialogue: 0,0:52:59.30,0:53:01.39,Default,,0000,0000,0000,,especially in hardware. Dialogue: 0,0:53:01.39,0:53:03.62,Default,,0000,0000,0000,,Also... Dialogue: 0,0:53:03.62,0:53:04.92,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:53:04.92,0:53:09.09,Default,,0000,0000,0000,,"FUCK A DUCK" is not good crypto. Dialogue: 0,0:53:09.09,0:53:11.54,Default,,0000,0000,0000,,Pastebin is not a secure cloud store. Dialogue: 0,0:53:11.54,0:53:13.87,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:53:13.87,0:53:20.29,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:53:20.29,0:53:22.66,Default,,0000,0000,0000,,And you probably shouldn't put your private key Dialogue: 0,0:53:22.66,0:53:24.78,Default,,0000,0000,0000,,in a secure cloud store anyway. Dialogue: 0,0:53:24.78,0:53:25.86,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:53:25.86,0:53:31.40,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:53:31.40,0:53:32.58,Default,,0000,0000,0000,,And lastly... Dialogue: 0,0:53:32.58,0:53:34.21,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:53:34.21,0:53:40.43,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:53:40.43,0:53:41.62,Default,,0000,0000,0000,,Thank you. Dialogue: 0,0:53:41.62,0:53:43.89,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:53:43.89,0:53:44.80,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Give them an applause. Dialogue: 0,0:53:44.80,0:54:05.94,Default,,0000,0000,0000,,{\i1}applause{\i0} Dialogue: 0,0:54:05.94,0:54:11.38,Default,,0000,0000,0000,,{\i1}Angel{\i0}: So questions will be taken at the numbered microphones. Dialogue: 0,0:54:11.38,0:54:14.96,Default,,0000,0000,0000,,So anyone who has a question please line up at a microphone Dialogue: 0,0:54:14.96,0:54:16.96,Default,,0000,0000,0000,,and we will start by the signal angel Dialogue: 0,0:54:16.96,0:54:19.53,Default,,0000,0000,0000,,who has a question from IRC. Dialogue: 0,0:54:19.53,0:54:23.63,Default,,0000,0000,0000,,*Signal Angel*: IRC has a lot of punch lines involving penisses Dialogue: 0,0:54:23.63,0:54:26.04,Default,,0000,0000,0000,,and some questions. Dialogue: 0,0:54:26.04,0:54:31.44,Default,,0000,0000,0000,,First question is: would you recommend more using Dialogue: 0,0:54:31.44,0:54:37.64,Default,,0000,0000,0000,,elliptic curves or RSA with multiple primes... Dialogue: 0,0:54:37.64,0:54:41.66,Default,,0000,0000,0000,,using proper primes. Dialogue: 0,0:54:41.66,0:54:47.19,Default,,0000,0000,0000,,{\i1}Dan{\i0}: There are ways to do elliptic curves wrong, Dialogue: 0,0:54:47.19,0:54:48.85,Default,,0000,0000,0000,,there are ways to do RSA wrong. Dialogue: 0,0:54:48.85,0:54:53.81,Default,,0000,0000,0000,,In general if you've got a particular performance requirement Dialogue: 0,0:54:53.81,0:54:55.62,Default,,0000,0000,0000,,then elliptic curves are gonna meet that Dialogue: 0,0:54:55.62,0:54:57.86,Default,,0000,0000,0000,,with a much higher security level Dialogue: 0,0:54:57.86,0:55:00.21,Default,,0000,0000,0000,,than RSA is gonna meet that. Dialogue: 0,0:55:00.21,0:55:03.00,Default,,0000,0000,0000,,Of course you can do RSA securely, Dialogue: 0,0:55:03.00,0:55:04.93,Default,,0000,0000,0000,,you can do elliptic curves securely Dialogue: 0,0:55:04.93,0:55:07.15,Default,,0000,0000,0000,,but if you've got some performance limitation Dialogue: 0,0:55:07.15,0:55:08.61,Default,,0000,0000,0000,,as many applications do Dialogue: 0,0:55:08.61,0:55:13.04,Default,,0000,0000,0000,,then elliptic curves tend to be a better choice. Dialogue: 0,0:55:13.04,0:55:14.43,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: I also want to clarify Dialogue: 0,0:55:14.43,0:55:17.83,Default,,0000,0000,0000,,the other most commonly used public-key cryptosystem Dialogue: 0,0:55:17.83,0:55:19.98,Default,,0000,0000,0000,,is DSA, the Digital Signature Algorithm. Dialogue: 0,0:55:19.98,0:55:21.43,Default,,0000,0000,0000,,There's also elliptic curve DSA Dialogue: 0,0:55:21.43,0:55:23.29,Default,,0000,0000,0000,,which is probably what you're thinking about Dialogue: 0,0:55:23.29,0:55:25.57,Default,,0000,0000,0000,,with elliptic curve cryptography. Dialogue: 0,0:55:25.57,0:55:31.21,Default,,0000,0000,0000,,DSA is in my opinion actually much worse Dialogue: 0,0:55:31.21,0:55:34.40,Default,,0000,0000,0000,,than RSA in terms of randomness failures. Dialogue: 0,0:55:34.40,0:55:36.25,Default,,0000,0000,0000,,In the paper that Dan referenced Dialogue: 0,0:55:36.25,0:55:39.38,Default,,0000,0000,0000,,we also talk about randomness failures in DSA Dialogue: 0,0:55:39.38,0:55:40.99,Default,,0000,0000,0000,,and it's horrifying. Dialogue: 0,0:55:40.99,0:55:44.52,Default,,0000,0000,0000,,If you ever ever screw up randomness in a single signature Dialogue: 0,0:55:44.52,0:55:48.35,Default,,0000,0000,0000,,your entire public key is lost. Dialogue: 0,0:55:48.35,0:55:50.76,Default,,0000,0000,0000,,{\i1}Angel:{\i0} We will take the next question from microphone nr 4 Dialogue: 0,0:55:50.76,0:55:53.07,Default,,0000,0000,0000,,to the right of the seat. Dialogue: 0,0:55:53.07,0:55:53.82,Default,,0000,0000,0000,,{\i1}Jake{\i0}: Hey guys. Dialogue: 0,0:55:53.82,0:55:56.28,Default,,0000,0000,0000,,Sorry I didn't mention the computing power of Bluffdale. Dialogue: 0,0:55:56.28,0:56:02.07,Default,,0000,0000,0000,,That said, when we want to transition from 1024 bit RSA Dialogue: 0,0:56:02.07,0:56:05.34,Default,,0000,0000,0000,,to something else, what do you think is a good idea? Dialogue: 0,0:56:05.34,0:56:10.03,Default,,0000,0000,0000,,So for example, in Tor we do use 1024 bit RSA for TLS. Dialogue: 0,0:56:10.03,0:56:12.53,Default,,0000,0000,0000,,{\i1}laughter{\i0} Yeah I know, right? Dialogue: 0,0:56:12.53,0:56:15.59,Default,,0000,0000,0000,,So the thing is we're working on changing these things Dialogue: 0,0:56:15.59,0:56:17.08,Default,,0000,0000,0000,,but what is... Dialogue: 0,0:56:17.08,0:56:19.77,Default,,0000,0000,0000,,I mean Zooko has this 100 year crypto project. Dialogue: 0,0:56:19.77,0:56:21.81,Default,,0000,0000,0000,,What is the real thing that we should, Dialogue: 0,0:56:21.81,0:56:23.91,Default,,0000,0000,0000,,like if we could switch tomorrow to something, Dialogue: 0,0:56:23.91,0:56:26.60,Default,,0000,0000,0000,,what's the useful that we can live with for 5 or 10 years? Dialogue: 0,0:56:26.60,0:56:28.80,Default,,0000,0000,0000,,Is 2048 going to be useful? Dialogue: 0,0:56:28.80,0:56:31.18,Default,,0000,0000,0000,,Is 4096 where we should go tomorrow? Dialogue: 0,0:56:31.18,0:56:32.78,Default,,0000,0000,0000,,Cause there is a trade-off between Dialogue: 0,0:56:32.78,0:56:34.59,Default,,0000,0000,0000,,performance and forward secrecy Dialogue: 0,0:56:34.59,0:56:37.96,Default,,0000,0000,0000,,and there are a lot of things to think about. Dialogue: 0,0:56:37.96,0:56:40.08,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: If you tell me 5 to 10 years Dialogue: 0,0:56:40.08,0:56:42.36,Default,,0000,0000,0000,,I would be still comfortable with elliptic curves. Dialogue: 0,0:56:42.36,0:56:44.77,Default,,0000,0000,0000,,If you talk 100 years Dialogue: 0,0:56:44.77,0:56:47.69,Default,,0000,0000,0000,,and then there's all these worse quantum computers around Dialogue: 0,0:56:47.69,0:56:51.14,Default,,0000,0000,0000,,then I would go for something which is worse in performance Dialogue: 0,0:56:51.14,0:56:52.83,Default,,0000,0000,0000,,like code-based cryptography Dialogue: 0,0:56:52.83,0:56:54.04,Default,,0000,0000,0000,,or for signatures hashing Dialogue: 0,0:56:54.04,0:56:55.74,Default,,0000,0000,0000,,but if you'd say in 5 to 10 years Dialogue: 0,0:56:55.74,0:56:57.41,Default,,0000,0000,0000,,I'm very comfortable recommending to you Dialogue: 0,0:56:57.41,0:56:59.94,Default,,0000,0000,0000,,elliptic curves with 256 bits. Dialogue: 0,0:56:59.94,0:57:02.16,Default,,0000,0000,0000,,{\i1}Jake{\i0}: Ok, thanks. Dialogue: 0,0:57:02.16,0:57:04.88,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Signal angel? Dialogue: 0,0:57:04.88,0:57:07.19,Default,,0000,0000,0000,,*Signal Angel*: Yeah, another question from IRC. Dialogue: 0,0:57:07.19,0:57:11.03,Default,,0000,0000,0000,,If you avoid all the easy primes Dialogue: 0,0:57:11.03,0:57:14.23,Default,,0000,0000,0000,,does this shrink the search space such that Dialogue: 0,0:57:14.23,0:57:17.86,Default,,0000,0000,0000,,it becomes easier to crack the remaining keys? Dialogue: 0,0:57:17.86,0:57:20.16,Default,,0000,0000,0000,,Or asked another way: Dialogue: 0,0:57:20.16,0:57:25.15,Default,,0000,0000,0000,,can you quantify the ratio of easy primes versus hard primes? Dialogue: 0,0:57:25.15,0:57:26.29,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Yeah, that's a good question. Dialogue: 0,0:57:26.29,0:57:28.57,Default,,0000,0000,0000,,The answer is: yes, it can be quantified Dialogue: 0,0:57:28.57,0:57:32.83,Default,,0000,0000,0000,,and once you're up to about to the 1024 bit RSA key level Dialogue: 0,0:57:32.83,0:57:35.31,Default,,0000,0000,0000,,then there's very very few weak primes. Dialogue: 0,0:57:35.31,0:57:37.08,Default,,0000,0000,0000,,So if you have a random number, Dialogue: 0,0:57:37.08,0:57:38.59,Default,,0000,0000,0000,,you just generate a random prime Dialogue: 0,0:57:38.59,0:57:40.24,Default,,0000,0000,0000,,then your chance of bumping into something weak Dialogue: 0,0:57:40.24,0:57:42.79,Default,,0000,0000,0000,,is so small that you just don't have to worry about it. Dialogue: 0,0:57:42.79,0:57:44.86,Default,,0000,0000,0000,,It is one of those much less frequent than Dialogue: 0,0:57:44.86,0:57:46.58,Default,,0000,0000,0000,,being hit by a lightning kind of events. Dialogue: 0,0:57:46.58,0:57:49.21,Default,,0000,0000,0000,,It is something that have been quantified Dialogue: 0,0:57:49.21,0:57:52.24,Default,,0000,0000,0000,,and it is an issue for smaller RSA keys Dialogue: 0,0:57:52.24,0:57:54.87,Default,,0000,0000,0000,,back when people were using, say, 512 bit RSA Dialogue: 0,0:57:54.87,0:57:56.75,Default,,0000,0000,0000,,then it was actually a noticable issue. Dialogue: 0,0:57:56.75,0:57:59.12,Default,,0000,0000,0000,,But once you're at 1024 or above then Dialogue: 0,0:57:59.12,0:58:00.69,Default,,0000,0000,0000,,the issue is basically gone. Dialogue: 0,0:58:00.69,0:58:03.83,Default,,0000,0000,0000,,It's something where you can and you should Dialogue: 0,0:58:03.83,0:58:06.10,Default,,0000,0000,0000,,look at exactly what the chance is of bumping into a weak Dialogue: 0,0:58:06.10,0:58:08.83,Default,,0000,0000,0000,,but it's not reallistically something Dialogue: 0,0:58:08.83,0:58:13.26,Default,,0000,0000,0000,,you're gonna encounter with 1024 bit RSA. Dialogue: 0,0:58:13.26,0:58:16.54,Default,,0000,0000,0000,,{\i1}Angel{\i0}: We're gonna take the next question from nr 1. Dialogue: 0,0:58:16.54,0:58:19.31,Default,,0000,0000,0000,,Just one notice: we don't have a lot of time left Dialogue: 0,0:58:19.31,0:58:23.55,Default,,0000,0000,0000,,so even though there is a talk in one hour Dialogue: 0,0:58:23.55,0:58:25.08,Default,,0000,0000,0000,,just ask. Dialogue: 0,0:58:25.08,0:58:28.16,Default,,0000,0000,0000,,{\i1}Male{\i0}: There is a devastating attack that can break AES, Dialogue: 0,0:58:28.16,0:58:31.87,Default,,0000,0000,0000,,SHA2, most probably SHA3 and DES. Dialogue: 0,0:58:31.87,0:58:33.76,Default,,0000,0000,0000,,It's called a biclique attack. Dialogue: 0,0:58:33.76,0:58:35.66,Default,,0000,0000,0000,,Are you concerned that it might break RSA Dialogue: 0,0:58:35.66,0:58:37.28,Default,,0000,0000,0000,,with any key size and even ECC Dialogue: 0,0:58:37.28,0:58:39.99,Default,,0000,0000,0000,,and even any public-key crypto? Dialogue: 0,0:58:39.99,0:58:41.66,Default,,0000,0000,0000,,{\i1}Dan{\i0}: No. Dialogue: 0,0:58:41.66,0:58:43.59,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:58:43.59,0:58:46.68,Default,,0000,0000,0000,,Bicliques are something which are certainly interesting Dialogue: 0,0:58:46.68,0:58:49.59,Default,,0000,0000,0000,,and I think about it as a way to speed up brute force Dialogue: 0,0:58:49.59,0:58:52.51,Default,,0000,0000,0000,,and it speeds up brute force by a noticable factor, Dialogue: 0,0:58:52.51,0:58:55.15,Default,,0000,0000,0000,,often makes attacks, say, twice as fast. Dialogue: 0,0:58:55.15,0:58:58.52,Default,,0000,0000,0000,,But with public-key crypto we have attacks which are Dialogue: 0,0:58:58.52,0:59:00.76,Default,,0000,0000,0000,,much much faster than brute force to begin with Dialogue: 0,0:59:00.76,0:59:04.21,Default,,0000,0000,0000,,so that kind of speed-up of brute force won't be competitive Dialogue: 0,0:59:04.21,0:59:08.23,Default,,0000,0000,0000,,with things like the number field sieve. Dialogue: 0,0:59:08.23,0:59:12.96,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next is from number 3. Dialogue: 0,0:59:12.96,0:59:16.82,Default,,0000,0000,0000,,{\i1}Male{\i0}: Me not coming from the dark side of mathematics, Dialogue: 0,0:59:16.82,0:59:20.92,Default,,0000,0000,0000,,how do I know that my random number generators are fine Dialogue: 0,0:59:20.92,0:59:23.66,Default,,0000,0000,0000,,for generating keys? Dialogue: 0,0:59:23.66,0:59:26.22,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,0:59:26.22,0:59:31.35,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: Seed them. Dialogue: 0,0:59:31.35,0:59:37.04,Default,,0000,0000,0000,,Basically the things that are out there if you're using Dialogue: 0,0:59:37.04,0:59:40.61,Default,,0000,0000,0000,,a standard random number generator like in Linux, Dialogue: 0,0:59:40.61,0:59:44.44,Default,,0000,0000,0000,,actually Linux has added patches to the kernel Dialogue: 0,0:59:44.44,0:59:48.02,Default,,0000,0000,0000,,to fix some of the problems that we've found. Dialogue: 0,0:59:48.02,0:59:50.43,Default,,0000,0000,0000,,If you want to know that you're keys are good: Dialogue: 0,0:59:50.43,0:59:54.69,Default,,0000,0000,0000,,if you generate them on a general purpose computer Dialogue: 0,0:59:54.69,0:59:56.60,Default,,0000,0000,0000,,after it has been running for a long time Dialogue: 0,0:59:56.60,0:59:59.56,Default,,0000,0000,0000,,you're probably fine. Dialogue: 0,0:59:59.56,1:00:04.79,Default,,0000,0000,0000,,I would not generate very important or long-term keys Dialogue: 0,1:00:04.79,1:00:09.71,Default,,0000,0000,0000,,on low-power hardware devices where you can't tell... Dialogue: 0,1:00:09.71,1:00:11.91,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,1:00:11.91,1:00:15.76,Default,,0000,0000,0000,,{\i1}Male{\i0}: Thank you. Dialogue: 0,1:00:15.76,1:00:18.34,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next question will be taken from number 4. Dialogue: 0,1:00:18.34,1:00:19.39,Default,,0000,0000,0000,,{\i1}Male{\i0}: Hi. Dialogue: 0,1:00:19.39,1:00:23.69,Default,,0000,0000,0000,,It's just a remark, not really a question. Dialogue: 0,1:00:23.69,1:00:25.41,Default,,0000,0000,0000,,I work in high performance computing. Dialogue: 0,1:00:25.41,1:00:26.91,Default,,0000,0000,0000,,I was at the supercomputing conference Dialogue: 0,1:00:26.91,1:00:29.38,Default,,0000,0000,0000,,a couple of weeks ago. Dialogue: 0,1:00:29.38,1:00:31.93,Default,,0000,0000,0000,,They're presenting large-scale installations Dialogue: 0,1:00:31.93,1:00:35.86,Default,,0000,0000,0000,,and dealing with problems of power. Dialogue: 0,1:00:35.86,1:00:38.93,Default,,0000,0000,0000,,They want to build petaflops and exaflops systems Dialogue: 0,1:00:38.93,1:00:42.26,Default,,0000,0000,0000,,that are in a range of 20 MW. Dialogue: 0,1:00:42.26,1:00:47.32,Default,,0000,0000,0000,,So I'm wondering what NSA is doing with 53 megawatts Dialogue: 0,1:00:47.32,1:00:53.82,Default,,0000,0000,0000,,in a data center because no storage takes that much capacity. Dialogue: 0,1:00:53.82,1:00:58.98,Default,,0000,0000,0000,,I think it's really something we should think about. Dialogue: 0,1:00:58.98,1:01:03.27,Default,,0000,0000,0000,,So thanks, nice talk. Dialogue: 0,1:01:03.27,1:01:04.88,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next question from... Dialogue: 0,1:01:04.88,1:01:06.96,Default,,0000,0000,0000,,does the signal angel have one? Dialogue: 0,1:01:06.96,1:01:08.68,Default,,0000,0000,0000,,*Signal angel*: Ok, another question is: Dialogue: 0,1:01:08.68,1:01:11.84,Default,,0000,0000,0000,,How big do you estimate the effort to Dialogue: 0,1:01:11.84,1:01:17.31,Default,,0000,0000,0000,,exchange keys and certificates involving 1024 bit primes Dialogue: 0,1:01:17.31,1:01:22.78,Default,,0000,0000,0000,,let's say worldwide at the moment? Dialogue: 0,1:01:22.78,1:01:24.50,Default,,0000,0000,0000,,{\i1}Dan{\i0}: I wasn't getting what the question was. Dialogue: 0,1:01:24.50,1:01:25.64,Default,,0000,0000,0000,,Could you repeat the question? Dialogue: 0,1:01:25.64,1:01:27.34,Default,,0000,0000,0000,,*Signal angel*: I don't really understand it myself. Dialogue: 0,1:01:27.34,1:01:28.88,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,1:01:28.88,1:01:33.18,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Ok, let's switch to 1. Dialogue: 0,1:01:33.18,1:01:37.01,Default,,0000,0000,0000,,{\i1}Male{\i0}: My question goes back to the idea Dialogue: 0,1:01:37.01,1:01:42.88,Default,,0000,0000,0000,,of how can we know how good the private keys are? Dialogue: 0,1:01:42.88,1:01:50.23,Default,,0000,0000,0000,,Is there something like a keygen evaluation tool? Dialogue: 0,1:01:50.23,1:01:56.57,Default,,0000,0000,0000,,Or can the quality of a key generator be estimated Dialogue: 0,1:01:56.57,1:01:58.54,Default,,0000,0000,0000,,from a sample of keys? Dialogue: 0,1:01:58.54,1:02:01.83,Default,,0000,0000,0000,,Like a public tool that you can throw keys on Dialogue: 0,1:02:01.83,1:02:05.56,Default,,0000,0000,0000,,and it will tell me a bias of my keygen? Dialogue: 0,1:02:05.56,1:02:09.09,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: If you go to factorable.net Dialogue: 0,1:02:09.09,1:02:12.57,Default,,0000,0000,0000,,my co-authors and I have made a key check tool Dialogue: 0,1:02:12.57,1:02:14.73,Default,,0000,0000,0000,,which will tell you if your key is in the Dialogue: 0,1:02:14.73,1:02:17.53,Default,,0000,0000,0000,,list of keys that we scraped off the Internet Dialogue: 0,1:02:17.53,1:02:19.30,Default,,0000,0000,0000,,that we were able to compromise. Dialogue: 0,1:02:19.30,1:02:21.25,Default,,0000,0000,0000,,That's a first check. Dialogue: 0,1:02:21.25,1:02:24.45,Default,,0000,0000,0000,,It's not a positive verification that your key is good Dialogue: 0,1:02:24.45,1:02:26.54,Default,,0000,0000,0000,,but it will tell you if it is very bad. Dialogue: 0,1:02:26.54,1:02:28.86,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,1:02:28.86,1:02:36.81,Default,,0000,0000,0000,,If you want to check your generator, Dialogue: 0,1:02:36.81,1:02:40.83,Default,,0000,0000,0000,,if you're worried about the factorization problems Dialogue: 0,1:02:40.83,1:02:43.24,Default,,0000,0000,0000,,we have fast code on the website in C Dialogue: 0,1:02:43.24,1:02:45.72,Default,,0000,0000,0000,,that will do the GCD calculation for you Dialogue: 0,1:02:45.72,1:02:50.20,Default,,0000,0000,0000,,if you just dump a gigantic collection of keys at it. Dialogue: 0,1:02:50.20,1:02:54.38,Default,,0000,0000,0000,,If you might have other problems like you are Dialogue: 0,1:02:54.38,1:02:56.99,Default,,0000,0000,0000,,not sure whether it's factorable like those don't come up Dialogue: 0,1:02:56.99,1:03:00.50,Default,,0000,0000,0000,,the experiment that you might want to do is Dialogue: 0,1:03:00.50,1:03:04.21,Default,,0000,0000,0000,,sort of restart the process in realistic conditions Dialogue: 0,1:03:04.21,1:03:06.18,Default,,0000,0000,0000,,and generate a gigantic quantity of keys Dialogue: 0,1:03:06.18,1:03:08.98,Default,,0000,0000,0000,,and just check for repeats. Dialogue: 0,1:03:08.98,1:03:12.38,Default,,0000,0000,0000,,The sort of obvious stress testings. Dialogue: 0,1:03:12.38,1:03:16.38,Default,,0000,0000,0000,,If you have a device you want to boot it up in realistic conditions Dialogue: 0,1:03:16.38,1:03:18.05,Default,,0000,0000,0000,,and then check them Dialogue: 0,1:03:18.05,1:03:19.80,Default,,0000,0000,0000,,and this is painstaking work Dialogue: 0,1:03:19.80,1:03:22.33,Default,,0000,0000,0000,,but I don't think there's any realistic way Dialogue: 0,1:03:22.33,1:03:25.55,Default,,0000,0000,0000,,of doing better than that. Dialogue: 0,1:03:25.55,1:03:28.40,Default,,0000,0000,0000,,Or inspect the code, the obvious thing. Dialogue: 0,1:03:28.40,1:03:30.92,Default,,0000,0000,0000,,Make sure you're seeding anything. Dialogue: 0,1:03:30.92,1:03:33.46,Default,,0000,0000,0000,,{\i1}Male{\i0}: Ok, thank you. Dialogue: 0,1:03:33.46,1:03:35.99,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next question will be from mic number 4. Dialogue: 0,1:03:35.99,1:03:37.04,Default,,0000,0000,0000,,{\i1}Male{\i0}: Hi. Dialogue: 0,1:03:37.04,1:03:40.74,Default,,0000,0000,0000,,If I got your numbers correctly so you said something like Dialogue: 0,1:03:40.74,1:03:45.45,Default,,0000,0000,0000,,it would take 8 million machines a year to factor 1024 Dialogue: 0,1:03:45.45,1:03:48.98,Default,,0000,0000,0000,,so I was wondering what if I would like to factor like Dialogue: 0,1:03:48.98,1:03:52.24,Default,,0000,0000,0000,,800 bits or 900 bits which is, Dialogue: 0,1:03:52.24,1:03:55.15,Default,,0000,0000,0000,,as I understand, way easier than 1024 Dialogue: 0,1:03:55.15,1:03:57.04,Default,,0000,0000,0000,,but was never done publicly. Dialogue: 0,1:03:57.04,1:04:00.26,Default,,0000,0000,0000,,So are you saying that would take like a day or something? Dialogue: 0,1:04:00.26,1:04:02.58,Default,,0000,0000,0000,,{\i1}Dan{\i0}: It depends on the size of cluster you have. Dialogue: 0,1:04:02.58,1:04:07.06,Default,,0000,0000,0000,,The RSA 768 factorization a couple of years ago Dialogue: 0,1:04:07.06,1:04:11.42,Default,,0000,0000,0000,,used something on the scale of a 1500 computers Dialogue: 0,1:04:11.42,1:04:14.13,Default,,0000,0000,0000,,for a year. Dialogue: 0,1:04:14.13,1:04:15.73,Default,,0000,0000,0000,,And those were normal kind of computers, Dialogue: 0,1:04:15.73,1:04:19.48,Default,,0000,0000,0000,,Desktop kind of computers with, I think, typically 2 cores. Dialogue: 0,1:04:19.48,1:04:24.24,Default,,0000,0000,0000,,Nowadays, if you have some faster, say, 3 GHz 4-core machines, Dialogue: 0,1:04:24.24,1:04:27.45,Default,,0000,0000,0000,,I think those were typically 2 GHZ 2-core, nowadays... Dialogue: 0,1:04:27.45,1:04:30.58,Default,,0000,0000,0000,,Tanja's mentioning you of course want to use GPUs Dialogue: 0,1:04:30.58,1:04:31.72,Default,,0000,0000,0000,,to speed things up. Dialogue: 0,1:04:31.72,1:04:33.40,Default,,0000,0000,0000,,And there's many ways to take advantage of Dialogue: 0,1:04:33.40,1:04:35.39,Default,,0000,0000,0000,,computer technology moving forward. Dialogue: 0,1:04:35.39,1:04:39.100,Default,,0000,0000,0000,,To get careful estimates: for going from 768 to 800, Dialogue: 0,1:04:39.100,1:04:42.19,Default,,0000,0000,0000,,that's a short enough extrapolation Dialogue: 0,1:04:42.19,1:04:44.11,Default,,0000,0000,0000,,that people are pretty confident about that. Dialogue: 0,1:04:44.11,1:04:48.01,Default,,0000,0000,0000,,Getting to 900 starts getting iffy what exactly the cost would be Dialogue: 0,1:04:48.01,1:04:50.95,Default,,0000,0000,0000,,and 1024 there's a fair amount of guess works. Dialogue: 0,1:04:50.95,1:04:53.80,Default,,0000,0000,0000,,There is some consensus on rougly what the costs are Dialogue: 0,1:04:53.80,1:04:55.43,Default,,0000,0000,0000,,but it's hard to say exactly. Dialogue: 0,1:04:55.43,1:04:58.06,Default,,0000,0000,0000,,But again, to give you a scale of it: Dialogue: 0,1:04:58.06,1:04:59.68,Default,,0000,0000,0000,,you were saying like 900 or 800. Dialogue: 0,1:04:59.68,1:05:03.21,Default,,0000,0000,0000,,Well, 768 RSA challenge was done Dialogue: 0,1:05:03.21,1:05:07.23,Default,,0000,0000,0000,,and that one was 1500 machine years. Dialogue: 0,1:05:07.23,1:05:08.50,Default,,0000,0000,0000,,{\i1}Male{\i0}: Ok, thank you. Dialogue: 0,1:05:08.50,1:05:10.26,Default,,0000,0000,0000,,{\i1}Angel{\i0}: We'll take four more questions. Dialogue: 0,1:05:10.26,1:05:12.36,Default,,0000,0000,0000,,Signal angel first. Dialogue: 0,1:05:12.36,1:05:16.68,Default,,0000,0000,0000,,*Signal angel*: It's a clarification of the question I asked before. Dialogue: 0,1:05:16.68,1:05:22.28,Default,,0000,0000,0000,,The actual question is: how big will be the effort Dialogue: 0,1:05:22.28,1:05:32.13,Default,,0000,0000,0000,,to upgrade existing keys from 1024 bits to 4K or 8K bits? Dialogue: 0,1:05:32.13,1:05:35.98,Default,,0000,0000,0000,,Considering that the keys are currently in use Dialogue: 0,1:05:35.98,1:05:37.91,Default,,0000,0000,0000,,how much effort worldwide would it be to Dialogue: 0,1:05:37.91,1:05:41.61,Default,,0000,0000,0000,,upgrade all that to something more secure? Dialogue: 0,1:05:41.61,1:05:43.56,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: I mean, for the private user if you're running Dialogue: 0,1:05:43.56,1:05:46.45,Default,,0000,0000,0000,,SSH on the laptop you can just generate a new key. Dialogue: 0,1:05:46.45,1:05:47.88,Default,,0000,0000,0000,,Doesn't take you much time. Dialogue: 0,1:05:47.88,1:05:50.34,Default,,0000,0000,0000,,You will notice maybe some degradation of performance Dialogue: 0,1:05:50.34,1:05:52.19,Default,,0000,0000,0000,,if you're running it on a netbook Dialogue: 0,1:05:52.19,1:05:54.76,Default,,0000,0000,0000,,but going to 2048 is not a big deal. Dialogue: 0,1:05:54.76,1:05:57.71,Default,,0000,0000,0000,,However, there is a recommendation of the Dialogue: 0,1:05:57.71,1:06:01.93,Default,,0000,0000,0000,,US government to stop using 1024 bit RSA as of 2010 Dialogue: 0,1:06:01.93,1:06:05.21,Default,,0000,0000,0000,,and we still see it everywhere. Dialogue: 0,1:06:05.21,1:06:07.56,Default,,0000,0000,0000,,Apparently it is bigger effort than just Dialogue: 0,1:06:07.56,1:06:10.74,Default,,0000,0000,0000,,everybody spending 10 minutes on the laptop. Dialogue: 0,1:06:10.74,1:06:13.64,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Maybe part of the problem is things like Dialogue: 0,1:06:13.64,1:06:16.100,Default,,0000,0000,0000,,everybody says "yeah, use 2048 or bigger" Dialogue: 0,1:06:16.100,1:06:18.88,Default,,0000,0000,0000,,and there's some financial standard Dialogue: 0,1:06:18.88,1:06:21.16,Default,,0000,0000,0000,,which says you can use any key size you want Dialogue: 0,1:06:21.16,1:06:23.94,Default,,0000,0000,0000,,up to 1984 bits. Dialogue: 0,1:06:23.94,1:06:25.63,Default,,0000,0000,0000,,I have no idea how they came up with this Dialogue: 0,1:06:25.63,1:06:27.21,Default,,0000,0000,0000,,but then they run into some other standard Dialogue: 0,1:06:27.21,1:06:29.28,Default,,0000,0000,0000,,which says use 2048 and they just can't Dialogue: 0,1:06:29.28,1:06:33.34,Default,,0000,0000,0000,,implement it on the smartcards which only support up to 1984. Dialogue: 0,1:06:33.34,1:06:36.47,Default,,0000,0000,0000,,Now if you get the standards people talking to each other for several years Dialogue: 0,1:06:36.47,1:06:39.26,Default,,0000,0000,0000,,then they agree on using 1984. Dialogue: 0,1:06:39.26,1:06:41.80,Default,,0000,0000,0000,,It's just about as good as 2048 Dialogue: 0,1:06:41.80,1:06:44.75,Default,,0000,0000,0000,,but realistically when you have these conflicts Dialogue: 0,1:06:44.75,1:06:47.13,Default,,0000,0000,0000,,in standards then it takes a while to work out. Dialogue: 0,1:06:47.13,1:06:48.74,Default,,0000,0000,0000,,And when you have a busy server Dialogue: 0,1:06:48.74,1:06:51.23,Default,,0000,0000,0000,,that's trying to do 2048 bit RSA Dialogue: 0,1:06:51.23,1:06:53.13,Default,,0000,0000,0000,,it doesn't matter what the standard says Dialogue: 0,1:06:53.13,1:06:55.45,Default,,0000,0000,0000,,if you got a ton of load you just can't handle that load Dialogue: 0,1:06:55.45,1:06:58.34,Default,,0000,0000,0000,,if you're spending a ton of time on cryptography. Dialogue: 0,1:06:58.34,1:07:00.46,Default,,0000,0000,0000,,And that again is where we like elliptic curves Dialogue: 0,1:07:00.46,1:07:02.56,Default,,0000,0000,0000,,because they give you for whatever your Dialogue: 0,1:07:02.56,1:07:05.34,Default,,0000,0000,0000,,performance constraints are much better security. Dialogue: 0,1:07:05.34,1:07:07.31,Default,,0000,0000,0000,,So if you're trying a given security level Dialogue: 0,1:07:07.31,1:07:09.83,Default,,0000,0000,0000,,the speed is much better. Dialogue: 0,1:07:09.83,1:07:12.81,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next question will be from number 2. Dialogue: 0,1:07:12.81,1:07:14.64,Default,,0000,0000,0000,,{\i1}Female{\i0}: So you've had two developers stand up Dialogue: 0,1:07:14.64,1:07:17.46,Default,,0000,0000,0000,,and ask how to verify whether or not their Dialogue: 0,1:07:17.46,1:07:19.73,Default,,0000,0000,0000,,key generation is correct and whether or not their Dialogue: 0,1:07:19.73,1:07:21.49,Default,,0000,0000,0000,,random numbers are correct. Dialogue: 0,1:07:21.49,1:07:23.89,Default,,0000,0000,0000,,And I think it's great that you give coding recommendations Dialogue: 0,1:07:23.89,1:07:27.44,Default,,0000,0000,0000,,like seed rand() but coming from the development Dialogue: 0,1:07:27.44,1:07:29.54,Default,,0000,0000,0000,,perspective I like to unit test my code Dialogue: 0,1:07:29.54,1:07:31.79,Default,,0000,0000,0000,,and specifically I like to write my unit tests Dialogue: 0,1:07:31.79,1:07:33.04,Default,,0000,0000,0000,,before I write my code, Dialogue: 0,1:07:33.04,1:07:34.71,Default,,0000,0000,0000,,it's called test-driven development. Dialogue: 0,1:07:34.71,1:07:38.18,Default,,0000,0000,0000,,So if I'm going about creating an algorithm to Dialogue: 0,1:07:38.18,1:07:39.99,Default,,0000,0000,0000,,encrypt something or whatever Dialogue: 0,1:07:39.99,1:07:42.77,Default,,0000,0000,0000,,what are the steps that I need to do Dialogue: 0,1:07:42.77,1:07:46.65,Default,,0000,0000,0000,,when I'm writing my unit test? Dialogue: 0,1:07:46.65,1:07:51.94,Default,,0000,0000,0000,,Has there been some kind of effort in that way Dialogue: 0,1:07:51.94,1:07:54.91,Default,,0000,0000,0000,,like what goes into unit test for determining that Dialogue: 0,1:07:54.91,1:07:56.61,Default,,0000,0000,0000,,your random number is correct? Dialogue: 0,1:07:56.61,1:07:59.09,Default,,0000,0000,0000,,I mean there's algorithms for determining Dialogue: 0,1:07:59.09,1:08:00.56,Default,,0000,0000,0000,,whether your random number generator is Dialogue: 0,1:08:00.56,1:08:02.77,Default,,0000,0000,0000,,operating correctly, right? Dialogue: 0,1:08:02.77,1:08:05.16,Default,,0000,0000,0000,,{\i1}Dan{\i0}: This is something where there is, Dialogue: 0,1:08:05.16,1:08:07.78,Default,,0000,0000,0000,,if you look at how the random number generators work, Dialogue: 0,1:08:07.78,1:08:10.21,Default,,0000,0000,0000,,there was just a NIST workshop Dialogue: 0,1:08:10.21,1:08:11.98,Default,,0000,0000,0000,,and there's some NIST standards Dialogue: 0,1:08:11.98,1:08:12.74,Default,,0000,0000,0000,,which are telling you Dialogue: 0,1:08:12.74,1:08:15.71,Default,,0000,0000,0000,,here's what to do to test your random number generators. Dialogue: 0,1:08:15.71,1:08:17.80,Default,,0000,0000,0000,,So you have a hardware random number generator, Dialogue: 0,1:08:17.80,1:08:19.59,Default,,0000,0000,0000,,some post-processing, and they say Dialogue: 0,1:08:19.59,1:08:22.41,Default,,0000,0000,0000,,"ok here's the standard for how to test those pieces" Dialogue: 0,1:08:22.41,1:08:24.70,Default,,0000,0000,0000,,Now that's not the same as testing the cryptography Dialogue: 0,1:08:24.70,1:08:26.34,Default,,0000,0000,0000,,that's using those pieces Dialogue: 0,1:08:26.34,1:08:28.99,Default,,0000,0000,0000,,and it's very helpful if there's a clear separation there. Dialogue: 0,1:08:28.99,1:08:30.46,Default,,0000,0000,0000,,So you have your cryptography Dialogue: 0,1:08:30.46,1:08:32.75,Default,,0000,0000,0000,,which is doing deterministic stuff Dialogue: 0,1:08:32.75,1:08:34.45,Default,,0000,0000,0000,,and says you have to have some randomness coming Dialogue: 0,1:08:34.45,1:08:37.81,Default,,0000,0000,0000,,from a totally separate unit where the only job Dialogue: 0,1:08:37.81,1:08:40.46,Default,,0000,0000,0000,,of that separate unit is do the randomness properly. Dialogue: 0,1:08:40.46,1:08:42.15,Default,,0000,0000,0000,,And then the NIST test will tell you Dialogue: 0,1:08:42.15,1:08:43.32,Default,,0000,0000,0000,,what the randomness does Dialogue: 0,1:08:43.32,1:08:45.94,Default,,0000,0000,0000,,and then deterministic cryptographic testing Dialogue: 0,1:08:45.94,1:08:48.39,Default,,0000,0000,0000,,will tell you that the other pieces are working correctly Dialogue: 0,1:08:48.39,1:08:50.21,Default,,0000,0000,0000,,for all sorts of inputs. Dialogue: 0,1:08:50.21,1:08:53.89,Default,,0000,0000,0000,,Where it goes wrong is something like the ECDSA standard Dialogue: 0,1:08:53.89,1:08:55.39,Default,,0000,0000,0000,,that Nadia was mentioning before Dialogue: 0,1:08:55.39,1:08:56.70,Default,,0000,0000,0000,,and that's one that says that Dialogue: 0,1:08:56.70,1:08:59.21,Default,,0000,0000,0000,,you don't just deterministically generate a signature Dialogue: 0,1:08:59.21,1:09:01.41,Default,,0000,0000,0000,,you make some new randomness every time you generate Dialogue: 0,1:09:01.41,1:09:03.70,Default,,0000,0000,0000,,a signature and that's what goes horribly wrong. Dialogue: 0,1:09:03.70,1:09:05.67,Default,,0000,0000,0000,,So that's something where we need new standards Dialogue: 0,1:09:05.67,1:09:07.79,Default,,0000,0000,0000,,which say instead of doing what ECDSA does Dialogue: 0,1:09:07.79,1:09:09.74,Default,,0000,0000,0000,,we have a clear separation between Dialogue: 0,1:09:09.74,1:09:12.19,Default,,0000,0000,0000,,the cryptography always does the same thing Dialogue: 0,1:09:12.19,1:09:15.04,Default,,0000,0000,0000,,making it testable, and then randomness is centralized Dialogue: 0,1:09:15.04,1:09:17.54,Default,,0000,0000,0000,,in one spot which hopefully the NIST standards Dialogue: 0,1:09:17.54,1:09:19.84,Default,,0000,0000,0000,,do a good enough job of testing. Dialogue: 0,1:09:19.84,1:09:23.51,Default,,0000,0000,0000,,{\i1}Female{\i0}: So there's something that says here's what determines... Dialogue: 0,1:09:23.51,1:09:26.95,Default,,0000,0000,0000,,I guess what I'm asking is do you know of any algorithms Dialogue: 0,1:09:26.95,1:09:30.14,Default,,0000,0000,0000,,that can be used for determining whether something Dialogue: 0,1:09:30.14,1:09:32.25,Default,,0000,0000,0000,,is a good random number and whether your random Dialogue: 0,1:09:32.25,1:09:34.52,Default,,0000,0000,0000,,number generator is generating things properly? Dialogue: 0,1:09:34.52,1:09:37.03,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: Well, there are a bunch of tests for. Dialogue: 0,1:09:37.03,1:09:39.31,Default,,0000,0000,0000,,There's hardware random number generators Dialogue: 0,1:09:39.31,1:09:42.13,Default,,0000,0000,0000,,you can run them through the diehard tests. Dialogue: 0,1:09:42.13,1:09:44.71,Default,,0000,0000,0000,,There's certificates by FIPS. Dialogue: 0,1:09:44.71,1:09:48.53,Default,,0000,0000,0000,,In general I would recommend implementing all those steps Dialogue: 0,1:09:48.53,1:09:50.81,Default,,0000,0000,0000,,but the smartcards that have been mentioned by Dan earlier Dialogue: 0,1:09:50.81,1:09:52.74,Default,,0000,0000,0000,,from the Taiwan citizen card Dialogue: 0,1:09:52.74,1:09:55.44,Default,,0000,0000,0000,,those are actually FIPS-certified. Dialogue: 0,1:09:55.44,1:09:58.94,Default,,0000,0000,0000,,So even though, these go through what is the industry standard Dialogue: 0,1:09:58.94,1:10:00.92,Default,,0000,0000,0000,,of doing random number generation on smartcards Dialogue: 0,1:10:00.92,1:10:03.62,Default,,0000,0000,0000,,which everybody thought was good enough, Dialogue: 0,1:10:03.62,1:10:04.98,Default,,0000,0000,0000,,apparently they're not. Dialogue: 0,1:10:04.98,1:10:06.48,Default,,0000,0000,0000,,So randomness is a total mess. Dialogue: 0,1:10:06.48,1:10:08.61,Default,,0000,0000,0000,,I mean after the paper by Nadia and Dialogue: 0,1:10:08.61,1:10:10.41,Default,,0000,0000,0000,,also when the paper by the Lausanne team came out, Dialogue: 0,1:10:10.41,1:10:12.69,Default,,0000,0000,0000,,there is no some more movement in finding Dialogue: 0,1:10:12.69,1:10:14.02,Default,,0000,0000,0000,,better random number generators. Dialogue: 0,1:10:14.02,1:10:18.66,Default,,0000,0000,0000,,At this moment, well, hope for the best. Dialogue: 0,1:10:18.66,1:10:20.62,Default,,0000,0000,0000,,{\i1}laughter{\i0} Dialogue: 0,1:10:20.62,1:10:22.18,Default,,0000,0000,0000,,Implement the standards, yes. Dialogue: 0,1:10:22.18,1:10:24.67,Default,,0000,0000,0000,,If you have some source of randomness Dialogue: 0,1:10:24.67,1:10:28.42,Default,,0000,0000,0000,,try to stretch it with a stream cipher or something like that. Dialogue: 0,1:10:28.42,1:10:31.30,Default,,0000,0000,0000,,{\i1}Nadia{\i0}: I want to tell a little story. Dialogue: 0,1:10:31.30,1:10:33.23,Default,,0000,0000,0000,,After we published the paper Dialogue: 0,1:10:33.23,1:10:35.64,Default,,0000,0000,0000,,I heard some very interesting things from some of the vendors. Dialogue: 0,1:10:35.64,1:10:39.33,Default,,0000,0000,0000,,I think one of the things that makes randomness Dialogue: 0,1:10:39.33,1:10:42.21,Default,,0000,0000,0000,,and cryptography a difficult problem is that Dialogue: 0,1:10:42.21,1:10:44.61,Default,,0000,0000,0000,,this kind of issue is something that Dialogue: 0,1:10:44.61,1:10:46.81,Default,,0000,0000,0000,,crosses a lot of the abstraction boundaries Dialogue: 0,1:10:46.81,1:10:48.55,Default,,0000,0000,0000,,that you're used to in coding. Dialogue: 0,1:10:48.55,1:10:50.52,Default,,0000,0000,0000,,You want to have the clean unit test that you know Dialogue: 0,1:10:50.52,1:10:52.34,Default,,0000,0000,0000,,that this piece works, and this piece works, Dialogue: 0,1:10:52.34,1:10:53.92,Default,,0000,0000,0000,,and this piece works, and this piece works, Dialogue: 0,1:10:53.92,1:10:57.78,Default,,0000,0000,0000,,and you put them all together and it will all work flawlessly. Dialogue: 0,1:10:57.78,1:11:00.30,Default,,0000,0000,0000,,Somehow this kind of problem is something that Dialogue: 0,1:11:00.30,1:11:02.90,Default,,0000,0000,0000,,happens at the boundaries of each unit test. Dialogue: 0,1:11:02.90,1:11:05.22,Default,,0000,0000,0000,,We know that the operating system is like Dialogue: 0,1:11:05.22,1:11:08.43,Default,,0000,0000,0000,,"ok I'm getting my proper inputs from the hardware Dialogue: 0,1:11:08.43,1:11:11.30,Default,,0000,0000,0000,,and I'm correctly generating my randomness from there" Dialogue: 0,1:11:11.30,1:11:12.84,Default,,0000,0000,0000,,and then the application says Dialogue: 0,1:11:12.84,1:11:15.02,Default,,0000,0000,0000,,"I'm getting my randomness from the operating system, Dialogue: 0,1:11:15.02,1:11:16.31,Default,,0000,0000,0000,,it's good randomness" Dialogue: 0,1:11:16.31,1:11:19.60,Default,,0000,0000,0000,,and then the application uses the correct crypto algorithms Dialogue: 0,1:11:19.60,1:11:21.93,Default,,0000,0000,0000,,to then do good cryptography. Dialogue: 0,1:11:21.93,1:11:24.50,Default,,0000,0000,0000,,And at the very beginning of that stage Dialogue: 0,1:11:24.50,1:11:27.78,Default,,0000,0000,0000,,there was something broken and it translated all the way Dialogue: 0,1:11:27.78,1:11:29.53,Default,,0000,0000,0000,,through all of these pieces of software Dialogue: 0,1:11:29.53,1:11:31.53,Default,,0000,0000,0000,,that were working correctly. Dialogue: 0,1:11:31.53,1:11:35.42,Default,,0000,0000,0000,,Testing this holistically was the only way Dialogue: 0,1:11:35.42,1:11:37.31,Default,,0000,0000,0000,,to find this kind of error. Dialogue: 0,1:11:37.31,1:11:41.24,Default,,0000,0000,0000,,One story that I heard from a vendor was that Dialogue: 0,1:11:41.24,1:11:43.91,Default,,0000,0000,0000,,they ran into randomness problems. Dialogue: 0,1:11:43.91,1:11:45.74,Default,,0000,0000,0000,,They developed some device. Dialogue: 0,1:11:45.74,1:11:47.32,Default,,0000,0000,0000,,It was working perfectly Dialogue: 0,1:11:47.32,1:11:51.48,Default,,0000,0000,0000,,and on the assembly line they were being turned on Dialogue: 0,1:11:51.48,1:11:55.50,Default,,0000,0000,0000,,and run through the checks. Dialogue: 0,1:11:55.50,1:11:57.81,Default,,0000,0000,0000,,You boot it up it checks the integrity Dialogue: 0,1:11:57.81,1:12:00.64,Default,,0000,0000,0000,,on the assembly line and it was continuing on. Dialogue: 0,1:12:00.64,1:12:06.39,Default,,0000,0000,0000,,If you exactly booted them up at the exact same time Dialogue: 0,1:12:06.39,1:12:10.13,Default,,0000,0000,0000,,in the exact same conditions Dialogue: 0,1:12:10.13,1:12:13.22,Default,,0000,0000,0000,,then all of the inputs to the random number generator Dialogue: 0,1:12:13.22,1:12:16.32,Default,,0000,0000,0000,,would be the same and they would generate the same keys Dialogue: 0,1:12:16.32,1:12:17.74,Default,,0000,0000,0000,,and then these keys would be, Dialogue: 0,1:12:17.74,1:12:19.72,Default,,0000,0000,0000,,you know, they already generated the keys, Dialogue: 0,1:12:19.72,1:12:21.20,Default,,0000,0000,0000,,so they wouldn't generate them again after Dialogue: 0,1:12:21.20,1:12:25.40,Default,,0000,0000,0000,,they went to the consumer. Dialogue: 0,1:12:25.40,1:12:27.14,Default,,0000,0000,0000,,I don't know how to unit test that Dialogue: 0,1:12:27.14,1:12:29.98,Default,,0000,0000,0000,,except take the entire device, turn it on, Dialogue: 0,1:12:29.98,1:12:32.59,Default,,0000,0000,0000,,and take multiple of them and make sure the devices Dialogue: 0,1:12:32.59,1:12:35.40,Default,,0000,0000,0000,,as they're coming out of the production process Dialogue: 0,1:12:35.40,1:12:39.60,Default,,0000,0000,0000,,are working correctly. Dialogue: 0,1:12:39.60,1:12:41.48,Default,,0000,0000,0000,,{\i1}Angel{\i0}: So we will take 2 more questions. Dialogue: 0,1:12:41.48,1:12:46.69,Default,,0000,0000,0000,,One from number 4 first and then number 1 at the last. Dialogue: 0,1:12:46.69,1:12:48.00,Default,,0000,0000,0000,,{\i1}Male{\i0}: How good, do you think, Dialogue: 0,1:12:48.00,1:12:52.54,Default,,0000,0000,0000,,hardware-supported random number generators are Dialogue: 0,1:12:52.54,1:12:53.43,Default,,0000,0000,0000,,after what you've just said? Dialogue: 0,1:12:53.43,1:12:55.81,Default,,0000,0000,0000,,I think they're probably not good anymore? Dialogue: 0,1:12:55.81,1:13:01.57,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Intel has their RdRand instruction in some of the newer chips Dialogue: 0,1:13:01.57,1:13:04.98,Default,,0000,0000,0000,,and they say that they've gone through Dialogue: 0,1:13:04.98,1:13:06.96,Default,,0000,0000,0000,,a reasonable number of evaluation steps. Dialogue: 0,1:13:06.96,1:13:09.44,Default,,0000,0000,0000,,It sounds like they're trying. Dialogue: 0,1:13:09.44,1:13:11.83,Default,,0000,0000,0000,,Whether they're successful is a different question. Dialogue: 0,1:13:11.83,1:13:13.66,Default,,0000,0000,0000,,Something I don't like about the API is Dialogue: 0,1:13:13.66,1:13:16.39,Default,,0000,0000,0000,,RdRand gives you no way to test the pieces. Dialogue: 0,1:13:16.39,1:13:18.80,Default,,0000,0000,0000,,You can only test the post-processed output. Dialogue: 0,1:13:18.80,1:13:22.16,Default,,0000,0000,0000,,So nobody else is able to test the actual Dialogue: 0,1:13:22.16,1:13:24.28,Default,,0000,0000,0000,,randomness generation part of the hardware. Dialogue: 0,1:13:24.28,1:13:26.54,Default,,0000,0000,0000,,You can only get a filtered version of that. Dialogue: 0,1:13:26.54,1:13:29.24,Default,,0000,0000,0000,,So Intel and people who are contracted by Intel Dialogue: 0,1:13:29.24,1:13:30.63,Default,,0000,0000,0000,,to see what's going on inside Dialogue: 0,1:13:30.63,1:13:32.83,Default,,0000,0000,0000,,are the only people who can run these tests. Dialogue: 0,1:13:32.83,1:13:35.87,Default,,0000,0000,0000,,It's not open in a way that allows the community Dialogue: 0,1:13:35.87,1:13:37.38,Default,,0000,0000,0000,,to see if there's further problems. Dialogue: 0,1:13:37.38,1:13:38.76,Default,,0000,0000,0000,,But at least they're trying Dialogue: 0,1:13:38.76,1:13:41.42,Default,,0000,0000,0000,,and maybe with enough effort the hardware manufacturers Dialogue: 0,1:13:41.42,1:13:43.46,Default,,0000,0000,0000,,will get randomness generation right. Dialogue: 0,1:13:43.46,1:13:47.58,Default,,0000,0000,0000,,Of course if you can generate any sort of secret once Dialogue: 0,1:13:47.58,1:13:50.46,Default,,0000,0000,0000,,if you have enough of a secret to start with Dialogue: 0,1:13:50.46,1:13:52.33,Default,,0000,0000,0000,,then you can use things like AES to Dialogue: 0,1:13:52.33,1:13:53.94,Default,,0000,0000,0000,,generate any number of secrets Dialogue: 0,1:13:53.94,1:13:55.49,Default,,0000,0000,0000,,and you can put those secrets into Dialogue: 0,1:13:55.49,1:13:57.30,Default,,0000,0000,0000,,any number of devices that you want. Dialogue: 0,1:13:57.30,1:13:59.59,Default,,0000,0000,0000,,If you use AES in counter mode with Dialogue: 0,1:13:59.59,1:14:02.12,Default,,0000,0000,0000,,encrypting 1, encrypting 2, encrypting 3... Dialogue: 0,1:14:02.12,1:14:04.98,Default,,0000,0000,0000,,you get totally unpredictable, unrelated outputs Dialogue: 0,1:14:04.98,1:14:07.38,Default,,0000,0000,0000,,and then use those, burn those into some hardware. Dialogue: 0,1:14:07.38,1:14:09.98,Default,,0000,0000,0000,,But where do you get that initial randomness from? Dialogue: 0,1:14:09.98,1:14:12.83,Default,,0000,0000,0000,,Are you going through a trustworthy process there? Dialogue: 0,1:14:12.83,1:14:16.31,Default,,0000,0000,0000,,It's a hard problem. Dialogue: 0,1:14:16.31,1:14:18.20,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Next question from number 1. Dialogue: 0,1:14:18.20,1:14:19.73,Default,,0000,0000,0000,,And that's the last question. Dialogue: 0,1:14:19.73,1:14:21.38,Default,,0000,0000,0000,,{\i1}Male{\i0}: You said something about Dialogue: 0,1:14:21.38,1:14:24.80,Default,,0000,0000,0000,,you dropped this group-based cryptography word. Dialogue: 0,1:14:24.80,1:14:28.11,Default,,0000,0000,0000,,Most of the stuff I've encountered under that heading Dialogue: 0,1:14:28.11,1:14:30.01,Default,,0000,0000,0000,,kind of sounded like snake oil Dialogue: 0,1:14:30.01,1:14:32.90,Default,,0000,0000,0000,,just cause they're using non-abelian groups and stuff. Dialogue: 0,1:14:32.90,1:14:35.83,Default,,0000,0000,0000,,Is there anything here that isn't? Dialogue: 0,1:14:35.83,1:14:38.28,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: Ok, I did not say group-based crypto. Dialogue: 0,1:14:38.28,1:14:38.91,Default,,0000,0000,0000,,{\i1}Male{\i0}: Ok. Dialogue: 0,1:14:38.91,1:14:40.26,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: I said {\b1}code{\b0}-based cryptography. Dialogue: 0,1:14:40.26,1:14:41.24,Default,,0000,0000,0000,,{\i1}Male{\i0}: Sorry, thanks. Dialogue: 0,1:14:41.24,1:14:42.77,Default,,0000,0000,0000,,{\i1}Tanja{\i0}: So there is a class of cryptosystems Dialogue: 0,1:14:42.77,1:14:44.83,Default,,0000,0000,0000,,which are fine against quantum computers. Dialogue: 0,1:14:44.83,1:14:50.15,Default,,0000,0000,0000,,For all crypto it's always up to what we know. Dialogue: 0,1:14:50.15,1:14:51.96,Default,,0000,0000,0000,,Next day, there could be somebody with a Dialogue: 0,1:14:51.96,1:14:54.01,Default,,0000,0000,0000,,polynomial-time factor algorithm and so on. Dialogue: 0,1:14:54.01,1:14:56.72,Default,,0000,0000,0000,,Now there's also a group of people doing Dialogue: 0,1:14:56.72,1:14:59.36,Default,,0000,0000,0000,,braid group cryptography, doing non-abelian groups, Dialogue: 0,1:14:59.36,1:15:01.76,Default,,0000,0000,0000,,most of these systems have been broken. Dialogue: 0,1:15:01.76,1:15:07.08,Default,,0000,0000,0000,,If they weren't broken by classical computers Dialogue: 0,1:15:07.08,1:15:10.91,Default,,0000,0000,0000,,maybe they would remain secure against quantum computers. Dialogue: 0,1:15:10.91,1:15:13.83,Default,,0000,0000,0000,,It's lots of "would"s there. Dialogue: 0,1:15:13.83,1:15:17.61,Default,,0000,0000,0000,,Yes, they might have this on their flags as well Dialogue: 0,1:15:17.61,1:15:20.55,Default,,0000,0000,0000,,but I wouldn't count this as a secure system. Dialogue: 0,1:15:20.55,1:15:23.03,Default,,0000,0000,0000,,Whereas code-based cryptography or lattice-based cryptography Dialogue: 0,1:15:23.03,1:15:26.48,Default,,0000,0000,0000,,are systems which should be fine. Dialogue: 0,1:15:26.48,1:15:28.65,Default,,0000,0000,0000,,{\i1}Dan{\i0}: Maybe just a URL if you're interested Dialogue: 0,1:15:28.65,1:15:31.94,Default,,0000,0000,0000,,in post-quantum cryptography is pqcrypto.org Dialogue: 0,1:15:31.94,1:15:34.51,Default,,0000,0000,0000,,and that keeps track of papers on the various types Dialogue: 0,1:15:34.51,1:15:37.23,Default,,0000,0000,0000,,of cryptography that should survive for a 100 years Dialogue: 0,1:15:37.23,1:15:41.45,Default,,0000,0000,0000,,and in particular against quantum computers. Dialogue: 0,1:15:41.45,1:15:42.44,Default,,0000,0000,0000,,{\i1}Angel{\i0}: Ladies and gentleman, please give Dialogue: 0,1:15:42.44,1:15:46.55,Default,,0000,0000,0000,,Nadia, Tanja and Daniel a big round of applause. Dialogue: 0,1:15:46.55,1:15:47.71,Default,,0000,0000,0000,,Thank you so much. Dialogue: 0,1:15:47.71,1:15:56.64,Default,,0000,0000,0000,,{\i1}applause{\i0}