WEBVTT

1
00:00:00.080 --> 00:00:01.360
<v Speaker 1>Hey, there, curious minds.

2
00:00:01.439 --> 00:00:03.720
<v Speaker 2>Every time you send a secure message, log into your bank,

3
00:00:03.799 --> 00:00:05.679
<v Speaker 2>or even you know, just see that little padlock on

4
00:00:05.679 --> 00:00:08.919
<v Speaker 2>a website, there's this whole complex thing happening behind the scenes.

5
00:00:08.919 --> 00:00:09.560
<v Speaker 1>It's not magic.

6
00:00:09.599 --> 00:00:15.119
<v Speaker 2>It's this fascinating world built on really clever math, sophisticated codes,

7
00:00:15.359 --> 00:00:18.480
<v Speaker 2>and it's constantly changing to keep our digital stuff safe. Today,

8
00:00:18.600 --> 00:00:21.600
<v Speaker 2>we're taking a deep dive into modern cryptography. We'll look

9
00:00:21.640 --> 00:00:23.480
<v Speaker 2>at where it came from, how it works now, and

10
00:00:23.559 --> 00:00:29.239
<v Speaker 2>crucially the big challenges ahead like quantum computing. Our guide

11
00:00:29.359 --> 00:00:33.119
<v Speaker 2>is Introduction to Modern Cryptography, third edition by Jonathan Katz.

12
00:00:33.439 --> 00:00:37.200
<v Speaker 2>It's pretty rigorous, but honestly surprisingly easy to follow on

13
00:00:37.240 --> 00:00:39.560
<v Speaker 2>a lot of this stuff. Our mission, as always, is

14
00:00:39.600 --> 00:00:42.039
<v Speaker 2>to give you that shortcut to being really well informed.

15
00:00:42.240 --> 00:00:44.399
<v Speaker 2>We want to pull out the key ideas, the surprising

16
00:00:44.439 --> 00:00:46.159
<v Speaker 2>bits that make up our digital security.

17
00:00:46.679 --> 00:00:47.759
<v Speaker 1>Okay, let's unpack this.

18
00:00:47.880 --> 00:00:51.520
<v Speaker 2>Let's start way back the old school stuff, classical cryptography

19
00:00:51.880 --> 00:00:55.479
<v Speaker 2>ciphers like Visionnaire, maybe trying to hide pattern, Yeah exactly,

20
00:00:55.840 --> 00:00:59.399
<v Speaker 2>But what was the big weakness there? Why didn't that last? Well?

21
00:00:59.399 --> 00:01:01.799
<v Speaker 3>The fundamental issue with those older schemes, and it's why

22
00:01:01.840 --> 00:01:04.120
<v Speaker 3>we often call it an art back then was this

23
00:01:04.239 --> 00:01:07.560
<v Speaker 3>reliance on security by obscurity.

24
00:01:07.719 --> 00:01:09.319
<v Speaker 1>Just keep the method secret, right.

25
00:01:09.560 --> 00:01:13.040
<v Speaker 3>The thinking was, if nobody knows how you're encrypting, you're safe.

26
00:01:13.599 --> 00:01:16.480
<v Speaker 3>But that just doesn't hold up with visionnaire. For instance,

27
00:01:16.959 --> 00:01:21.719
<v Speaker 3>even basic statistical tools like calculating the index of coincidence.

28
00:01:22.079 --> 00:01:26.159
<v Speaker 3>It basically measures letter frequencies that can reveal patterns. For

29
00:01:26.239 --> 00:01:28.840
<v Speaker 3>English text, that index is around point zero six y five.

30
00:01:29.239 --> 00:01:31.719
<v Speaker 3>If you analyze cipher text, then it's close to that

31
00:01:32.000 --> 00:01:35.319
<v Speaker 3>something's up. And even simpler if an attacker could just

32
00:01:35.359 --> 00:01:38.280
<v Speaker 3>guess a tiny bit of the original message like dear sir.

33
00:01:38.280 --> 00:01:40.680
<v Speaker 1>Maybe a known plaintext attack.

34
00:01:40.400 --> 00:01:45.159
<v Speaker 3>Exactly, those basic shift substitution Visionaire ciphers, they become well,

35
00:01:45.200 --> 00:01:46.760
<v Speaker 3>the book calls them trivial to break.

36
00:01:46.879 --> 00:01:49.480
<v Speaker 2>Okay, So that leads right into Kirkhoff's principle, doesn't it.

37
00:01:49.480 --> 00:01:53.200
<v Speaker 2>It sounds backward, But why is keeping the algorithm secret

38
00:01:53.239 --> 00:01:54.680
<v Speaker 2>actually a bad idea?

39
00:01:54.719 --> 00:01:59.079
<v Speaker 3>Precisely, Kirkhoff said way back that the security should only

40
00:01:59.079 --> 00:02:03.280
<v Speaker 3>depend on the key being secret, not the method. Proprietary

41
00:02:03.359 --> 00:02:06.879
<v Speaker 3>sort of home brewed algorithms are dangerous because they haven't

42
00:02:06.920 --> 00:02:07.640
<v Speaker 3>been hammered on.

43
00:02:07.680 --> 00:02:10.199
<v Speaker 2>By experts, no public scrutiny, and.

44
00:02:10.240 --> 00:02:15.840
<v Speaker 3>History is littered with disastrous results from ignoring this. Think

45
00:02:16.039 --> 00:02:19.599
<v Speaker 3>early DRM, some Wi Fi security. They just crumbled once

46
00:02:19.639 --> 00:02:22.120
<v Speaker 3>someone reverse engineered the secret sauce and found it was

47
00:02:22.240 --> 00:02:25.800
<v Speaker 3>well weak. Our confidence in something like as comes to

48
00:02:25.840 --> 00:02:28.599
<v Speaker 3>the fact that it's been extensively studied by experts for

49
00:02:28.680 --> 00:02:30.080
<v Speaker 3>decades and it's held up.

50
00:02:30.280 --> 00:02:32.719
<v Speaker 2>So the art was obscurity and tricks. How did we

51
00:02:32.719 --> 00:02:34.960
<v Speaker 2>get to the science of modern crypto? What changed?

52
00:02:35.479 --> 00:02:38.240
<v Speaker 3>It was a fundamental shift really kicking off around the eighties.

53
00:02:38.280 --> 00:02:42.080
<v Speaker 3>Modern crypto was built on three pillars. First, formal definitions.

54
00:02:42.360 --> 00:02:44.759
<v Speaker 3>You have to define exactly what secure means for your

55
00:02:44.759 --> 00:02:47.319
<v Speaker 3>specific goal, Like the book says, if you don't know

56
00:02:47.360 --> 00:02:49.039
<v Speaker 3>what it is you are trying to achieve, how can

57
00:02:49.080 --> 00:02:51.039
<v Speaker 3>you hope to know when you have achieved?

58
00:02:51.039 --> 00:02:54.159
<v Speaker 2>It makes sense, right, Yeah, absolutely define the target.

59
00:02:54.400 --> 00:02:59.840
<v Speaker 3>Second, precise assumptions we state explicitly. Okay, this system is

60
00:03:00.400 --> 00:03:03.360
<v Speaker 3>if this specific math problem is hard to solve, like

61
00:03:03.400 --> 00:03:08.599
<v Speaker 3>factoring large numbers for example. And Third, rigorous proofs mathematical

62
00:03:08.599 --> 00:03:11.280
<v Speaker 3>proofs that show the scheme meets the definition, assuming the

63
00:03:11.360 --> 00:03:12.680
<v Speaker 3>underlying problem is hard.

64
00:03:12.919 --> 00:03:15.319
<v Speaker 2>So it's not just hoping it's secure, it's a proof

65
00:03:15.520 --> 00:03:18.240
<v Speaker 2>like an ironclad guarantee almost that's.

66
00:03:18.039 --> 00:03:20.560
<v Speaker 3>The phrase the book uses. Yeah, proofs of security given

67
00:03:20.599 --> 00:03:25.879
<v Speaker 3>ironclad guarantee, but crucially relative to the definition and the assumptions.

68
00:03:25.960 --> 00:03:27.840
<v Speaker 1>Okay, caveats apply exactly.

69
00:03:28.039 --> 00:03:31.039
<v Speaker 3>It shifts crypto from an art to a science. Real

70
00:03:31.080 --> 00:03:34.039
<v Speaker 3>world implementations can still mess things up, or maybe an

71
00:03:34.080 --> 00:03:37.039
<v Speaker 3>assumption turns out to be wrong someday, but it provides

72
00:03:37.039 --> 00:03:40.560
<v Speaker 3>a framework, as the source puts it, provable security helps

73
00:03:40.560 --> 00:03:43.000
<v Speaker 3>shift the odds in the defender's favor. It gives us

74
00:03:43.039 --> 00:03:44.840
<v Speaker 3>real confidence in the core algorithms.

75
00:03:44.960 --> 00:03:48.439
<v Speaker 2>Okay, let's move into symmetric key crypto private key. This

76
00:03:48.479 --> 00:03:51.199
<v Speaker 2>is where Alice and Bob share the same secret key, right,

77
00:03:51.400 --> 00:03:52.039
<v Speaker 2>that's the one.

78
00:03:52.159 --> 00:03:55.199
<v Speaker 3>Formerly you've got three bits Jen to generate the key

79
00:03:55.280 --> 00:03:58.319
<v Speaker 3>into encrypt using the key, and d to decrypt using

80
00:03:58.319 --> 00:04:00.439
<v Speaker 3>that same key and the basic proper But he's just

81
00:04:00.479 --> 00:04:04.120
<v Speaker 3>deckangam encrypt and decrypt with the same key. You get

82
00:04:04.120 --> 00:04:04.919
<v Speaker 3>your original message.

83
00:04:04.919 --> 00:04:05.280
<v Speaker 2>Genback.

84
00:04:05.319 --> 00:04:06.120
<v Speaker 3>Simple concept.

85
00:04:06.240 --> 00:04:10.400
<v Speaker 2>Now you hear about perfect secrecy sounds like the ultimate goal, Right,

86
00:04:10.520 --> 00:04:12.199
<v Speaker 2>what does that actually mean? Why don't we just use

87
00:04:12.240 --> 00:04:12.879
<v Speaker 2>it for everything?

88
00:04:12.960 --> 00:04:16.759
<v Speaker 3>Perfect secrecy, like the one time pad, is the theoretical peak.

89
00:04:17.480 --> 00:04:21.079
<v Speaker 3>It's secure even if the attacker has infinite computing power.

90
00:04:21.199 --> 00:04:22.639
<v Speaker 1>Wow, infinite.

91
00:04:22.800 --> 00:04:26.240
<v Speaker 3>Yeah, the encrypted message gives zero information about the original

92
00:04:26.439 --> 00:04:29.319
<v Speaker 3>It looks like pure random noise. But and this is

93
00:04:29.360 --> 00:04:32.560
<v Speaker 3>the huge practical catch. The key has to be truly random,

94
00:04:32.920 --> 00:04:34.519
<v Speaker 3>just as long as the message, and you can only

95
00:04:34.600 --> 00:04:35.079
<v Speaker 3>use it once.

96
00:04:35.519 --> 00:04:39.079
<v Speaker 2>H So sending a movie would need a movie sized

97
00:04:39.160 --> 00:04:41.360
<v Speaker 2>key used once exactly.

98
00:04:41.399 --> 00:04:44.879
<v Speaker 3>Imagine securely exchanging that massive single use key. First, it's

99
00:04:44.920 --> 00:04:47.240
<v Speaker 3>just not practical for email or web browsing.

100
00:04:47.399 --> 00:04:49.519
<v Speaker 2>So how do we handle that for everyday stuff? If

101
00:04:49.519 --> 00:04:51.399
<v Speaker 2>the one time pad is out? Yea.

102
00:04:51.759 --> 00:04:56.600
<v Speaker 3>We move to computationally secure encryption. We assume attackers have

103
00:04:56.680 --> 00:04:59.600
<v Speaker 3>limited computing power, still powerful.

104
00:04:59.639 --> 00:05:03.800
<v Speaker 2>But not infinite, a more realistic assumption definitely, And this

105
00:05:03.879 --> 00:05:06.040
<v Speaker 2>lets us use reusable keys.

106
00:05:05.959 --> 00:05:09.079
<v Speaker 3>That are much shorter than the messages. We use tools

107
00:05:09.160 --> 00:05:13.399
<v Speaker 3>like pseudorandom generators prgs to stretch a short random seed

108
00:05:13.839 --> 00:05:16.639
<v Speaker 3>into a long string that looks random to computers okay,

109
00:05:16.759 --> 00:05:20.279
<v Speaker 3>and pseudorandom functions PRFs, which act like random functions. These

110
00:05:20.279 --> 00:05:23.639
<v Speaker 3>are the building blocks. Then, for encrypting actual data, we

111
00:05:23.759 --> 00:05:26.879
<v Speaker 3>use things called modes of operation with block ciphers like

112
00:05:26.959 --> 00:05:30.120
<v Speaker 3>aes CTR mode for instance, lets you encrypt parts of

113
00:05:30.120 --> 00:05:33.560
<v Speaker 3>a message in parallel, which is way faster speeds things up.

114
00:05:33.720 --> 00:05:36.959
<v Speaker 3>Absolutely essential for performance and underpinning all this is the

115
00:05:37.000 --> 00:05:39.920
<v Speaker 3>need for good randomness sources, high entropy data from things

116
00:05:39.959 --> 00:05:44.680
<v Speaker 3>like network timings, your keystrokes, even tiny fluctuations in hardware temperature.

117
00:05:44.879 --> 00:05:46.680
<v Speaker 3>Got to get those initial random seeds right.

118
00:05:46.839 --> 00:05:50.160
<v Speaker 2>We've focused a lot on secrecy keeping things private. Is

119
00:05:50.199 --> 00:05:52.839
<v Speaker 2>that the whole story for digital security not even closed.

120
00:05:52.839 --> 00:05:55.560
<v Speaker 3>This is a really important point. Encryption by itself usually

121
00:05:55.560 --> 00:05:57.839
<v Speaker 3>doesn't guarantee message integrity.

122
00:05:57.519 --> 00:06:00.000
<v Speaker 2>Meaning someone could mess with the message even if they

123
00:06:00.079 --> 00:06:01.360
<v Speaker 2>can't read it precisely.

124
00:06:01.560 --> 00:06:04.959
<v Speaker 3>An active attacker, someone sitting in the middle might be

125
00:06:05.000 --> 00:06:07.560
<v Speaker 3>able to flip bits in the ciphertext. They don't know

126
00:06:07.560 --> 00:06:10.519
<v Speaker 3>what they're changing maybe, but when it gets decrypted it

127
00:06:10.560 --> 00:06:10.879
<v Speaker 3>could be.

128
00:06:10.879 --> 00:06:13.800
<v Speaker 2>Completely different, like changing a dollar amount in a bank transfer.

129
00:06:13.959 --> 00:06:17.759
<v Speaker 3>Exactly that scenario. The encrypted one hundred dollars gets subtly

130
00:06:17.839 --> 00:06:20.720
<v Speaker 3>changed and the bank decrypts it as the thousand dollars.

131
00:06:21.480 --> 00:06:22.600
<v Speaker 3>Encryption didn't stop that.

132
00:06:22.759 --> 00:06:25.959
<v Speaker 2>Okay, that's yeah, that's bad. So how do we make

133
00:06:25.959 --> 00:06:28.759
<v Speaker 2>sure the message wasn't altered, that it's authentic.

134
00:06:29.079 --> 00:06:32.959
<v Speaker 3>That's where MAA keys come in message authentication codes. You

135
00:06:33.000 --> 00:06:36.000
<v Speaker 3>need another shared secret key separate from the encryption key.

136
00:06:36.079 --> 00:06:39.839
<v Speaker 3>Usually with this maat key, the sender calculates a short

137
00:06:39.839 --> 00:06:41.360
<v Speaker 3>cryptographic tag for the.

138
00:06:41.319 --> 00:06:44.000
<v Speaker 2>Message, like a checksum but secure.

139
00:06:43.879 --> 00:06:47.399
<v Speaker 3>Kind of yeah, but much much stronger. The receiver uses

140
00:06:47.439 --> 00:06:50.600
<v Speaker 3>the same maakey to recalculate the tag on the message

141
00:06:50.639 --> 00:06:53.879
<v Speaker 3>they received. If their calculated tag matches the tag that

142
00:06:54.000 --> 00:06:55.800
<v Speaker 3>came with the message, it's authentic.

143
00:06:55.920 --> 00:06:58.639
<v Speaker 1>And if anything changed, the tags won't match exactly.

144
00:06:59.120 --> 00:07:01.079
<v Speaker 3>Even changing one one bit in the message or the

145
00:07:01.120 --> 00:07:05.160
<v Speaker 3>tag will cause verification to fail. HMAC is a really

146
00:07:05.160 --> 00:07:09.240
<v Speaker 3>common standard for this. It provides what's called existential unforgeability

147
00:07:09.600 --> 00:07:12.000
<v Speaker 3>fancy term, but it means an attacker can't create any

148
00:07:12.079 --> 00:07:14.959
<v Speaker 3>valid tag for any new message, even after seeing lots

149
00:07:15.040 --> 00:07:19.079
<v Speaker 3>of legitimate message tag pairs the very strong integrity guarantee.

150
00:07:19.160 --> 00:07:20.639
<v Speaker 1>Okay, MSC's for integrity.

151
00:07:20.680 --> 00:07:23.519
<v Speaker 2>Now. Hash functions, they seem to be everywhere. What makes

152
00:07:23.519 --> 00:07:25.279
<v Speaker 2>a hash function cryptographic? Right?

153
00:07:25.319 --> 00:07:29.199
<v Speaker 3>They are work horses. A cryptographic hash function takes any

154
00:07:29.240 --> 00:07:32.199
<v Speaker 3>input could be tiny, could be huge, and spits out

155
00:07:32.199 --> 00:07:35.839
<v Speaker 3>a fixed size digest a digital fingerprint. The key security

156
00:07:35.879 --> 00:07:39.920
<v Speaker 3>property is collision resistance. It must be incredibly hard computationally

157
00:07:39.959 --> 00:07:43.040
<v Speaker 3>infeasible to find two different inputs that produce the exact

158
00:07:43.040 --> 00:07:44.240
<v Speaker 3>same hash output.

159
00:07:44.160 --> 00:07:46.959
<v Speaker 2>Like finding two people with the same fingerprint, should be

160
00:07:47.040 --> 00:07:48.120
<v Speaker 2>basically impossible.

161
00:07:48.160 --> 00:07:50.800
<v Speaker 3>Ideally, yes, but there's a catch.

162
00:07:51.079 --> 00:07:53.480
<v Speaker 1>Uh I've heard about birthday attacks.

163
00:07:53.879 --> 00:07:56.839
<v Speaker 3>Sounds harmless, It does, but it's a mathematical phenomenon, the

164
00:07:56.879 --> 00:08:00.000
<v Speaker 3>birthday paradox. It means finding any two inputs that collide

165
00:08:00.319 --> 00:08:02.720
<v Speaker 3>is much easier than finding an input that matches a

166
00:08:02.759 --> 00:08:04.000
<v Speaker 3>specific hash output.

167
00:08:04.279 --> 00:08:05.560
<v Speaker 1>Okay, how much easier.

168
00:08:05.360 --> 00:08:08.000
<v Speaker 3>Roughly the square root of the possibilities. So if a

169
00:08:08.040 --> 00:08:11.120
<v Speaker 3>hash has n possible outputs, you only need a bout.

170
00:08:11.120 --> 00:08:13.959
<v Speaker 3>Squirt tries to find a collision for a hash with

171
00:08:14.399 --> 00:08:17.120
<v Speaker 3>l output bits, that's two L two operations.

172
00:08:17.199 --> 00:08:19.199
<v Speaker 2>So for MD five, which is one hundred and twenty

173
00:08:19.199 --> 00:08:20.560
<v Speaker 2>eight bits, that's two sixty.

174
00:08:20.279 --> 00:08:23.439
<v Speaker 3>Four exactly and two sixty four. While big is actually

175
00:08:23.439 --> 00:08:27.040
<v Speaker 3>achievable with modern computing power. That's why MD five is

176
00:08:27.079 --> 00:08:29.519
<v Speaker 3>considered broken. Collisions can be found.

177
00:08:29.279 --> 00:08:31.720
<v Speaker 1>Fast and SAHA one that was used everywhere too.

178
00:08:32.000 --> 00:08:33.919
<v Speaker 3>SAHA one is one hundred and sixty bits, so you're

179
00:08:33.919 --> 00:08:36.440
<v Speaker 3>looking at two hundred and eighty operations for a birthday attack.

180
00:08:36.919 --> 00:08:41.279
<v Speaker 3>Harder but also broken. Now explicit collisions have been demonstrated.

181
00:08:40.840 --> 00:08:42.879
<v Speaker 2>Which is why we use SAHA two fifty six or

182
00:08:42.879 --> 00:08:44.039
<v Speaker 2>even longer hashes.

183
00:08:44.120 --> 00:08:47.399
<v Speaker 3>Now precisely you need that longer output, that larger L

184
00:08:47.480 --> 00:08:50.519
<v Speaker 3>to make the two L two birthday attack computationally infeasible.

185
00:08:50.559 --> 00:08:54.480
<v Speaker 2>Again, okay, so we have symmetric encryption MAACS hashes, but

186
00:08:54.600 --> 00:08:57.120
<v Speaker 2>all the symmetric stuff, the private key stuff, relies on

187
00:08:57.159 --> 00:09:00.279
<v Speaker 2>Alison already having a shared secret key. How do they

188
00:09:00.320 --> 00:09:01.919
<v Speaker 2>get that key in the first place if they've never

189
00:09:01.960 --> 00:09:04.000
<v Speaker 2>met sounds like a chicken and egg problem.

190
00:09:04.080 --> 00:09:06.840
<v Speaker 3>It absolutely was. The book calls it one of the

191
00:09:06.840 --> 00:09:10.759
<v Speaker 3>most important open problems in cryptography before the mid seventies.

192
00:09:11.240 --> 00:09:15.279
<v Speaker 3>Think about it. A network of n people. Each pair

193
00:09:15.360 --> 00:09:18.639
<v Speaker 3>needs a unique key that's roughly n squared.

194
00:09:18.360 --> 00:09:20.440
<v Speaker 1>Keys, which gets huge, fast.

195
00:09:20.399 --> 00:09:24.120
<v Speaker 3>Astronomical for just one thousand users, it's nearly half a

196
00:09:24.120 --> 00:09:27.720
<v Speaker 3>million keys to pre share and manage securely. People tried

197
00:09:27.840 --> 00:09:32.399
<v Speaker 3>using key distribution centers KDCs, trusted servers that would generate

198
00:09:32.480 --> 00:09:34.399
<v Speaker 3>keys for pairs of users, But then.

199
00:09:34.279 --> 00:09:35.840
<v Speaker 1>The KDC is a massive target.

200
00:09:35.639 --> 00:09:38.120
<v Speaker 3>Right exactly, a high value target and a single point

201
00:09:38.120 --> 00:09:41.279
<v Speaker 3>of failure. If the KDC gets hacked, everyone's keys could

202
00:09:41.279 --> 00:09:43.039
<v Speaker 3>be compromised. It was a major bottleneck.

203
00:09:43.360 --> 00:09:46.320
<v Speaker 2>Then Diffy and Hellman came along the public key revolution.

204
00:09:46.440 --> 00:09:47.360
<v Speaker 1>What was the big idea?

205
00:09:47.720 --> 00:09:50.919
<v Speaker 3>It was truly paradigm shifting. They showed how two people

206
00:09:50.960 --> 00:09:53.600
<v Speaker 3>could agree on a shared secret over a public channel,

207
00:09:53.759 --> 00:09:56.000
<v Speaker 3>even if someone is listening to everything.

208
00:09:55.639 --> 00:09:58.279
<v Speaker 2>Like shouting numbers across a crowded room, but ending up

209
00:09:58.320 --> 00:09:59.879
<v Speaker 2>with a secret only you two know.

210
00:10:00.320 --> 00:10:03.919
<v Speaker 3>That's a great analogy. Mathematically, Alice picks a secret X,

211
00:10:04.120 --> 00:10:06.600
<v Speaker 3>Bob picks a secret why there's a public base g

212
00:10:07.120 --> 00:10:10.360
<v Speaker 3>Alice sends gx to Bob, Bob sends gs air y.

213
00:10:10.679 --> 00:10:12.879
<v Speaker 3>Because of exponent rules, they both arrive at the same

214
00:10:13.000 --> 00:10:14.639
<v Speaker 3>value gx y.

215
00:10:14.919 --> 00:10:19.720
<v Speaker 2>An eavesdropper who sees GX and g can't easily figure

216
00:10:19.720 --> 00:10:20.919
<v Speaker 2>out gx correct.

217
00:10:20.960 --> 00:10:23.799
<v Speaker 3>That relies on the presumed hardness of the discrete logarithm

218
00:10:23.879 --> 00:10:27.799
<v Speaker 3>problem or the related computational Diffie Hellman problem. Going from

219
00:10:27.840 --> 00:10:30.960
<v Speaker 3>G and X to gx is easy. Going backwards from

220
00:10:30.960 --> 00:10:34.000
<v Speaker 3>it GX to find x is believed to be incredibly

221
00:10:34.000 --> 00:10:35.480
<v Speaker 3>hard for classical computers.

222
00:10:35.639 --> 00:10:38.200
<v Speaker 1>Mind blowing. But you mentioned a catch earlier.

223
00:10:38.240 --> 00:10:41.639
<v Speaker 3>Ah, Yes, the basic Diffie helmet exchange is completely insecure

224
00:10:41.639 --> 00:10:42.879
<v Speaker 3>against a man in the middle attack.

225
00:10:42.960 --> 00:10:43.759
<v Speaker 1>How does that work?

226
00:10:43.879 --> 00:10:47.320
<v Speaker 3>An attacker Mallory sits between Alice and Bob. Mallory does

227
00:10:47.320 --> 00:10:49.600
<v Speaker 3>a diffie helmet exchange with Alice pretending to be Bob,

228
00:10:49.840 --> 00:10:51.960
<v Speaker 3>and does another one with Bob pretending to be Alice.

229
00:10:52.080 --> 00:10:54.159
<v Speaker 3>Alice and Bob think they have a shared secret, but

230
00:10:54.200 --> 00:10:58.000
<v Speaker 3>they actually share secrets with Mallory, who just decrypts, reads,

231
00:10:58.159 --> 00:11:01.159
<v Speaker 3>possibly modifies, and re encry messages between them.

232
00:11:01.320 --> 00:11:01.759
<v Speaker 1>OUCH.

233
00:11:01.879 --> 00:11:03.799
<v Speaker 2>So you need some way to know you're really talking

234
00:11:03.840 --> 00:11:05.600
<v Speaker 2>to Bob, not Mallory exactly.

235
00:11:05.679 --> 00:11:09.360
<v Speaker 3>You need authentication on top of the basic key exchange, certificates,

236
00:11:09.399 --> 00:11:11.159
<v Speaker 3>pre shared keys, something.

237
00:11:11.440 --> 00:11:14.759
<v Speaker 2>But this idea opened the door to public key encryption

238
00:11:15.000 --> 00:11:17.360
<v Speaker 2>like RSA and digital signatures.

239
00:11:17.399 --> 00:11:18.399
<v Speaker 1>How do those work?

240
00:11:18.759 --> 00:11:21.720
<v Speaker 3>So with public key encryption, you generate a key pair,

241
00:11:22.399 --> 00:11:25.039
<v Speaker 3>a public key you can publish anywhere, and a private

242
00:11:25.080 --> 00:11:29.080
<v Speaker 3>key you guard fiercely. Anyone can use your public key

243
00:11:29.120 --> 00:11:32.039
<v Speaker 3>to encrypt a message for you, but only you with

244
00:11:32.120 --> 00:11:33.919
<v Speaker 3>your private key can decrypt it.

245
00:11:34.000 --> 00:11:35.960
<v Speaker 2>And RSS security comes from.

246
00:11:35.720 --> 00:11:38.720
<v Speaker 3>The difficulty of factoring large numbers. The public key involves

247
00:11:38.720 --> 00:11:41.240
<v Speaker 3>a large number that's the product of two big primes.

248
00:11:41.679 --> 00:11:44.840
<v Speaker 3>Finding those crimes factoring is necessary to get the private

249
00:11:44.879 --> 00:11:48.600
<v Speaker 3>key and that's believed hard digital signatures flip it. You

250
00:11:48.720 --> 00:11:51.440
<v Speaker 3>use your private key to create a signature on a message.

251
00:11:51.759 --> 00:11:53.720
<v Speaker 3>Anyone can use your public key to verify that.

252
00:11:53.679 --> 00:11:56.279
<v Speaker 2>Signature, proving it came from you and wasn't changed.

253
00:11:56.399 --> 00:12:01.960
<v Speaker 3>Yes, it provides authenticity and integrity plus non repudiation. That

254
00:12:02.000 --> 00:12:04.960
<v Speaker 3>means you can't later deny sending the message because only

255
00:12:05.039 --> 00:12:07.440
<v Speaker 3>you have the private key that could create that signature.

256
00:12:07.639 --> 00:12:09.200
<v Speaker 3>It's verifiable by anyone.

257
00:12:09.440 --> 00:12:12.360
<v Speaker 2>Now, I remember hearing public key crypto is way slower

258
00:12:12.399 --> 00:12:13.360
<v Speaker 2>than symmetric stuff.

259
00:12:13.399 --> 00:12:13.840
<v Speaker 1>Is that right?

260
00:12:13.919 --> 00:12:17.159
<v Speaker 3>Oh? Yeah, orders of magnitude slower. Doing math with those

261
00:12:17.240 --> 00:12:20.879
<v Speaker 3>huge numbers is computationally expensive. Encrypting a large file with

262
00:12:21.000 --> 00:12:23.600
<v Speaker 3>RSA directly would be painfully slow.

263
00:12:23.799 --> 00:12:25.360
<v Speaker 1>So how do we use it? In practice?

264
00:12:25.440 --> 00:12:30.759
<v Speaker 3>We use hybrid encryption, often called KEEMDEM key encapsulation data encapsulation.

265
00:12:30.919 --> 00:12:31.720
<v Speaker 1>How does that work?

266
00:12:32.320 --> 00:12:35.440
<v Speaker 3>Use the slow public key crypto only to encrypt and

267
00:12:35.519 --> 00:12:39.399
<v Speaker 3>exchange a temporary random symmetric key, that's the CAM part.

268
00:12:39.960 --> 00:12:43.399
<v Speaker 3>Then use that fast symmetric key with something like AES

269
00:12:43.759 --> 00:12:46.679
<v Speaker 3>to encrypt the actual bulk data. That's the DEM part.

270
00:12:46.799 --> 00:12:47.679
<v Speaker 1>Best of both worlds.

271
00:12:47.759 --> 00:12:50.639
<v Speaker 2>Public key solves the key exchange problem. Symmetric key does

272
00:12:50.679 --> 00:12:52.440
<v Speaker 2>the fast data encryption exactly.

273
00:12:52.519 --> 00:12:56.240
<v Speaker 3>That's how things like TLSSL secure websites work, how PGP

274
00:12:56.360 --> 00:12:58.519
<v Speaker 3>email encryption works. It's the standard approach.

275
00:12:58.639 --> 00:13:01.919
<v Speaker 2>Okay, so V Hellman and RSA, all these public key

276
00:13:01.919 --> 00:13:05.559
<v Speaker 2>systems rely on certain math problems being hard for current computers.

277
00:13:06.039 --> 00:13:07.919
<v Speaker 1>What happens if they become easy?

278
00:13:08.200 --> 00:13:11.039
<v Speaker 3>And that is the multi trillion dollar question right now.

279
00:13:11.519 --> 00:13:16.399
<v Speaker 3>Here's where it gets really interesting and potentially scary. Back

280
00:13:16.440 --> 00:13:20.559
<v Speaker 3>in nineteen ninety four, Peter Shore published an algorithm. Shore's

281
00:13:20.600 --> 00:13:24.519
<v Speaker 3>algorithm shows that a sufficiently powerful quantum computer could solve

282
00:13:24.559 --> 00:13:28.960
<v Speaker 3>both factoring and discrete logarithms efficiently in polynomial time.

283
00:13:29.080 --> 00:13:33.159
<v Speaker 1>Wait, both problems the foundations of RSA and diffy Hellman and.

284
00:13:33.240 --> 00:13:35.759
<v Speaker 3>Elliptic curve cryptography, which is widely.

285
00:13:35.519 --> 00:13:39.039
<v Speaker 2>Used to Yes, so a working quantum computer basically breaks

286
00:13:39.159 --> 00:13:41.720
<v Speaker 2>all the public key crypto we use today pretty much.

287
00:13:41.759 --> 00:13:45.320
<v Speaker 3>The book states it's starkly all public cryptosystems we have

288
00:13:45.360 --> 00:13:48.440
<v Speaker 3>covered thus far can be broken in polynomial time by

289
00:13:48.480 --> 00:13:49.399
<v Speaker 3>a quantum computer.

290
00:13:49.519 --> 00:13:52.399
<v Speaker 1>Okay, wow, So what's the plan? Are we heading for

291
00:13:52.799 --> 00:13:53.960
<v Speaker 1>crypto apocalypse?

292
00:13:54.120 --> 00:13:56.200
<v Speaker 3>Well? Hopefully not. This is the whole field of post

293
00:13:56.240 --> 00:14:00.480
<v Speaker 3>quantum cryptography or PKEC. Researchers worldwide are racing to develop

294
00:14:00.559 --> 00:14:04.799
<v Speaker 3>and standardize new public key cryptosystems based on different mathematical problems,

295
00:14:04.799 --> 00:14:07.320
<v Speaker 3>ones believed to be hard even for quantum computers, like

296
00:14:07.320 --> 00:14:10.799
<v Speaker 3>what kind of problems Things like lattice based cryptography are

297
00:14:10.840 --> 00:14:15.519
<v Speaker 3>big contenders, problems like lwe learning with errors. There's also

298
00:14:15.679 --> 00:14:20.600
<v Speaker 3>hash based signatures, code based crypto, a few different families. NIST,

299
00:14:20.759 --> 00:14:23.519
<v Speaker 3>the US standards body, has been running a competition to

300
00:14:23.559 --> 00:14:26.399
<v Speaker 3>select the best candidates and they've chosen the first set

301
00:14:26.399 --> 00:14:27.000
<v Speaker 3>of standards.

302
00:14:27.480 --> 00:14:30.240
<v Speaker 2>So we're actively replacing the old algorithms.

303
00:14:30.679 --> 00:14:35.159
<v Speaker 3>The transition is starting. It's a massive undertaking, but essential.

304
00:14:35.919 --> 00:14:40.000
<v Speaker 3>Even symmetric crypto needs adjustments. Hash functions need bigger outputs,

305
00:14:40.039 --> 00:14:44.039
<v Speaker 3>maybe doubling key sizes for as against certain quantum attacks,

306
00:14:44.240 --> 00:14:47.120
<v Speaker 3>just to maintain the same security level. Grower's algorithm effects

307
00:14:47.120 --> 00:14:49.080
<v Speaker 3>symmetric search problems.

308
00:14:48.600 --> 00:14:50.039
<v Speaker 1>So it really touches everything.

309
00:14:50.200 --> 00:14:53.120
<v Speaker 3>It really does. It's a fundamental shift in the underlying assumptions.

310
00:14:53.240 --> 00:14:58.120
<v Speaker 2>Wow, from visioneer and statistical tricks to lattices and quantum resistance.

311
00:14:58.240 --> 00:15:00.799
<v Speaker 1>It's just been this constant evolution, this arms race.

312
00:15:00.919 --> 00:15:03.639
<v Speaker 3>Absolutely the attacker finds a weakness, the defender builds a

313
00:15:03.679 --> 00:15:07.440
<v Speaker 3>stronger wall using deeper mathematics. It constantly pushes the boundary

314
00:15:07.679 --> 00:15:09.720
<v Speaker 3>of what we thought was computationally possible.

315
00:15:09.879 --> 00:15:13.600
<v Speaker 2>So what does this all mean for you listening right now, Well,

316
00:15:13.639 --> 00:15:16.799
<v Speaker 2>it means that the invisible shield protecting your emails, your

317
00:15:16.799 --> 00:15:21.600
<v Speaker 2>bank accounts, your online life is constantly being rebuilt, reinforced

318
00:15:21.600 --> 00:15:22.679
<v Speaker 2>with new kinds of math.

319
00:15:22.960 --> 00:15:26.159
<v Speaker 3>It's a silent, ongoing process, but absolutely critical.

320
00:15:26.360 --> 00:15:29.039
<v Speaker 2>So next time you see that padlock or hit send

321
00:15:29.120 --> 00:15:31.879
<v Speaker 2>on an encrypted message, maybe take a second think about

322
00:15:31.879 --> 00:15:34.679
<v Speaker 2>that hidden dance of math, the assumptions, the proofs keeping

323
00:15:34.720 --> 00:15:38.480
<v Speaker 2>your data safe, and consider how cryptographers right now are

324
00:15:38.559 --> 00:15:42.080
<v Speaker 2>choreographing the next dance, designing the steps needed to withstand

325
00:15:42.159 --> 00:15:45.200
<v Speaker 2>the incredible power of computers that don't even fully exist yet.

326
00:15:45.200 --> 00:15:45.960
<v Speaker 2>It's quite something