0 00:00:00,000 --> 00:00:30,000 Dear viewer, these subtitles were generated by a machine via the service Trint and therefore are (very) buggy. If you are capable, please help us to create good quality subtitles: https://c3subtitles.de/talk/1082 Thanks! 1 00:00:02,830 --> 00:00:21,880 [Music] 2 00:00:18,080 --> 00:00:25,640 hey our next talk is going to take a 3 00:00:21,880 --> 00:00:29,320 look at what you can do wrong if you're 4 00:00:25,640 --> 00:00:31,640 using secure crypto Primitives but don't 5 00:00:29,320 --> 00:00:34,680 use them the right way and what you can 6 00:00:31,640 --> 00:00:37,760 possibly do about that by writing formal 7 00:00:34,680 --> 00:00:40,280 proofs so to tell you more about that we 8 00:00:37,760 --> 00:00:41,780 have Florian and Lucas a warm Round of 9 00:00:40,280 --> 00:00:48,320 Applause 10 00:00:41,780 --> 00:00:51,920 [Applause] 11 00:00:48,320 --> 00:00:54,840 please so good morning and thank you for 12 00:00:51,920 --> 00:00:56,640 waking up it's a great honor for us to 13 00:00:54,840 --> 00:01:00,440 give this talk especially in the slot 14 00:00:56,640 --> 00:01:03,000 directly after djb and Tanya langa 15 00:01:00,440 --> 00:01:05,439 uh before we start I want to mention two 16 00:01:03,000 --> 00:01:09,119 points which might not be clear in the 17 00:01:05,439 --> 00:01:12,320 talk the first one is we like provable 18 00:01:09,119 --> 00:01:14,680 security and AIT gold is a great 19 00:01:12,320 --> 00:01:17,000 cryptographer and this talk should not 20 00:01:14,680 --> 00:01:17,000 be a 21 00:01:18,119 --> 00:01:22,960 rent the organization is as follows 22 00:01:21,079 --> 00:01:24,079 we'll give a short motivation why you 23 00:01:22,960 --> 00:01:26,759 want to 24 00:01:24,079 --> 00:01:30,600 have proofs of 25 00:01:26,759 --> 00:01:34,399 security and then we'll show how to do 26 00:01:30,600 --> 00:01:37,799 them and the next uh the the latest two 27 00:01:34,399 --> 00:01:41,000 points will be on strange stuff happens 28 00:01:37,799 --> 00:01:41,000 if you use provable 29 00:01:43,840 --> 00:01:48,560 security anyone from the most clueless 30 00:01:46,360 --> 00:01:50,560 Amer to the best cryptographer can 31 00:01:48,560 --> 00:01:54,000 create an algorithm that he himself 32 00:01:50,560 --> 00:01:57,479 can't break it's not even hard this 33 00:01:54,000 --> 00:02:00,000 quote by Bruce schneer shows a little 34 00:01:57,479 --> 00:02:02,840 bit why you want to have provable 35 00:02:00,000 --> 00:02:05,399 security just because you look on your 36 00:02:02,840 --> 00:02:08,319 own scheme and you don't find the floor 37 00:02:05,399 --> 00:02:11,800 it does not mean that it's not there and 38 00:02:08,319 --> 00:02:13,280 a strict mathematical proof can handle 39 00:02:11,800 --> 00:02:15,120 this 40 00:02:13,280 --> 00:02:18,840 problem 41 00:02:15,120 --> 00:02:23,519 but it's not that easy and you should be 42 00:02:18,840 --> 00:02:23,519 aware of the boundaries of proof 43 00:02:24,360 --> 00:02:31,080 systems I'm sure you know this 44 00:02:27,239 --> 00:02:33,560 example the uh electronic code book mode 45 00:02:31,080 --> 00:02:36,879 is an encryption scheme where you take 46 00:02:33,560 --> 00:02:41,319 blocks of a plain text and you encrypt 47 00:02:36,879 --> 00:02:45,040 each block on its own and uh it's it's 48 00:02:41,319 --> 00:02:48,400 secure in the the meaning that uh each 49 00:02:45,040 --> 00:02:52,680 block looks random compared to this uh 50 00:02:48,400 --> 00:02:58,400 plain text but in the end that's maybe 51 00:02:52,680 --> 00:02:58,400 not what you mean by a secure encryption 52 00:02:58,760 --> 00:03:04,799 scheme 53 00:03:00,440 --> 00:03:08,120 a more complex example is the CBC or 54 00:03:04,799 --> 00:03:11,159 Cipher block chaining mode here you see 55 00:03:08,120 --> 00:03:12,959 that you have uh blocks of Cipher text 56 00:03:11,159 --> 00:03:17,040 and of PL 57 00:03:12,959 --> 00:03:18,480 text and in the decryption step and I 58 00:03:17,040 --> 00:03:24,920 use 59 00:03:18,480 --> 00:03:26,440 my L um you use the cipher text from one 60 00:03:24,920 --> 00:03:29,959 block 61 00:03:26,440 --> 00:03:34,720 and exort it uh to the decryption of 62 00:03:29,959 --> 00:03:38,879 another uh Cipher text block to get a PL 63 00:03:34,720 --> 00:03:42,159 text and for a for a deeper insight into 64 00:03:38,879 --> 00:03:47,400 this uh protocol you can watch the talk 65 00:03:42,159 --> 00:03:50,360 on TLS 1.3 by Hano uh but we'll show 66 00:03:47,400 --> 00:03:52,360 small problem of this um but before I 67 00:03:50,360 --> 00:03:56,159 need to introduce so-called 68 00:03:52,360 --> 00:03:59,720 oracles oracles are a way to formulate 69 00:03:56,159 --> 00:04:02,200 that you have some protal party which 70 00:03:59,720 --> 00:04:04,480 takes a well- defined input and answers 71 00:04:02,200 --> 00:04:07,599 with a well- defined output and it's 72 00:04:04,480 --> 00:04:11,079 typically used to perform operations 73 00:04:07,599 --> 00:04:14,560 that the parties by themselves can't 74 00:04:11,079 --> 00:04:18,160 handle and if you introduce a special 75 00:04:14,560 --> 00:04:22,800 so-called petting Oracle to the to this 76 00:04:18,160 --> 00:04:26,040 CBC mode which takes a cipher text and 77 00:04:22,800 --> 00:04:29,440 answers you if the padding of the plane 78 00:04:26,040 --> 00:04:30,280 text is correct which means that sorry 79 00:04:29,440 --> 00:04:33,400 it 80 00:04:30,280 --> 00:04:36,800 it ends with either a one b or two two 81 00:04:33,400 --> 00:04:38,320 bytes or 3 three byes uh just entering 82 00:04:36,800 --> 00:04:40,800 an oracle which tells you this 83 00:04:38,320 --> 00:04:42,960 information is enough to break the 84 00:04:40,800 --> 00:04:46,840 complete Cipher text because you now can 85 00:04:42,960 --> 00:04:48,919 just guess uh one bite after another 86 00:04:46,840 --> 00:04:53,400 which is much more efficient than 87 00:04:48,919 --> 00:04:57,039 Breaking the complete Cipher in one shot 88 00:04:53,400 --> 00:05:00,160 so to understand the security of a 89 00:04:57,039 --> 00:05:02,039 system you need to understand 90 00:05:00,160 --> 00:05:05,440 uh what problem you have and what 91 00:05:02,039 --> 00:05:08,840 definition of security you want to have 92 00:05:05,440 --> 00:05:10,360 and then you can go there and prove that 93 00:05:08,840 --> 00:05:12,160 your system is 94 00:05:10,360 --> 00:05:14,680 secure but 95 00:05:12,160 --> 00:05:16,680 unfortunately you won't be able to prove 96 00:05:14,680 --> 00:05:19,080 it without taking 97 00:05:16,680 --> 00:05:22,960 assumptions you might know about the P 98 00:05:19,080 --> 00:05:25,840 versus NP problem and that you can get 99 00:05:22,960 --> 00:05:28,479 quite Rich by solving 100 00:05:25,840 --> 00:05:30,560 it if you have a cipher 101 00:05:28,479 --> 00:05:32,360 text 102 00:05:30,560 --> 00:05:34,880 an encryption 103 00:05:32,360 --> 00:05:39,560 scheme and you prove that it's secure in 104 00:05:34,880 --> 00:05:42,880 the sense that given um encryption of 105 00:05:39,560 --> 00:05:45,400 something you can't tell that this is an 106 00:05:42,880 --> 00:05:48,120 encryption of a 107 00:05:45,400 --> 00:05:50,960 zero and you can prove this without 108 00:05:48,120 --> 00:05:54,160 taking additional assumptions then you 109 00:05:50,960 --> 00:05:58,600 would have shown an example of a problem 110 00:05:54,160 --> 00:06:01,759 which is in NP because given the secret 111 00:05:58,600 --> 00:06:04,800 key it's easy to do this you uh decrypt 112 00:06:01,759 --> 00:06:09,160 it and then you know if it's a zero or 113 00:06:04,800 --> 00:06:12,080 not but it's hard to do without and then 114 00:06:09,160 --> 00:06:15,880 you would have found an example uh where 115 00:06:12,080 --> 00:06:19,120 p and NP is different uh which make you 116 00:06:15,880 --> 00:06:21,720 quite rich and famous but it's not that 117 00:06:19,120 --> 00:06:25,560 plausible that you find it just uh on 118 00:06:21,720 --> 00:06:25,560 the way of proving the security of your 119 00:06:25,759 --> 00:06:33,440 scheme so we have to do some assumptions 120 00:06:30,720 --> 00:06:36,280 and uh Floren will now tell you about 121 00:06:33,440 --> 00:06:37,919 some of these okay uh good morning 122 00:06:36,280 --> 00:06:43,160 everyone 123 00:06:37,919 --> 00:06:47,080 um now many of you may have seen RSA and 124 00:06:43,160 --> 00:06:49,840 I've just um written down the uh a short 125 00:06:47,080 --> 00:06:53,319 version of it on the slides uh let me 126 00:06:49,840 --> 00:06:55,479 check here um it's quite commonly known 127 00:06:53,319 --> 00:06:57,759 that you have two very big primes p and 128 00:06:55,479 --> 00:07:00,280 Q you multiply them and get a very big 129 00:06:57,759 --> 00:07:02,400 integer n and you also take some 130 00:07:00,280 --> 00:07:06,000 exponent that we will just set to three 131 00:07:02,400 --> 00:07:08,440 in this example and this is all you need 132 00:07:06,000 --> 00:07:10,720 for a public key and then there is some 133 00:07:08,440 --> 00:07:13,360 uh more complicated way to compute the 134 00:07:10,720 --> 00:07:16,599 secret key and once you have these 135 00:07:13,360 --> 00:07:19,039 values um encrypting uh stuff is as 136 00:07:16,599 --> 00:07:20,960 simple as taking the Blaine text and 137 00:07:19,039 --> 00:07:23,919 taking it to the power of E so in our 138 00:07:20,960 --> 00:07:26,960 case three and doing that modulo n 139 00:07:23,919 --> 00:07:29,080 modulo uh in case you don't remember if 140 00:07:26,960 --> 00:07:31,120 you do division with remainder you throw 141 00:07:29,080 --> 00:07:34,720 away quotient and keep the remainder and 142 00:07:31,120 --> 00:07:36,400 that's what we call modulus so almost 143 00:07:34,720 --> 00:07:39,240 all examples that we will show will have 144 00:07:36,400 --> 00:07:41,919 some modulus in them um and in this case 145 00:07:39,240 --> 00:07:44,680 encryption as you see it's not really 146 00:07:41,919 --> 00:07:47,639 complicated and decryption uh you take 147 00:07:44,680 --> 00:07:49,919 the secret key as the exponent and for 148 00:07:47,639 --> 00:07:52,159 some uh reasons that we won't go into in 149 00:07:49,919 --> 00:07:55,919 this talk this actually works out to 150 00:07:52,159 --> 00:07:58,280 give you back the um original BL text 151 00:07:55,919 --> 00:08:00,639 and there is this common misconception 152 00:07:58,280 --> 00:08:03,479 that RSA is secure if factoring is 153 00:08:00,639 --> 00:08:05,759 secure that's not really the case the 154 00:08:03,479 --> 00:08:09,039 assumption that RSA uses is the 155 00:08:05,759 --> 00:08:12,159 so-called RSA assumption and it is 156 00:08:09,039 --> 00:08:14,199 roughly equivalent to the following it's 157 00:08:12,159 --> 00:08:16,759 impractical um if you I give you a 158 00:08:14,199 --> 00:08:18,360 public key and some Cipher text that was 159 00:08:16,759 --> 00:08:20,520 created with the public key with a 160 00:08:18,360 --> 00:08:23,280 random plane text for you to fully 161 00:08:20,520 --> 00:08:25,240 extract that Blaine text it sounds a 162 00:08:23,280 --> 00:08:28,000 little bit like RSA is secure because 163 00:08:25,240 --> 00:08:30,280 RSA is secure and actually that's 164 00:08:28,000 --> 00:08:31,960 getting quite close except that we have 165 00:08:30,280 --> 00:08:33,839 the problem that this version of RSA is 166 00:08:31,960 --> 00:08:36,560 not even really secure for sensible 167 00:08:33,839 --> 00:08:39,080 security definitions because just being 168 00:08:36,560 --> 00:08:42,000 unable to extract the Blaine text from a 169 00:08:39,080 --> 00:08:44,519 cipher text doesn't mean that there are 170 00:08:42,000 --> 00:08:47,279 no practical attacks on it if you're 171 00:08:44,519 --> 00:08:50,279 only able to extract half the plain text 172 00:08:47,279 --> 00:08:53,160 and you know that the it that it 173 00:08:50,279 --> 00:08:55,560 contains um asy text that says either 174 00:08:53,160 --> 00:08:58,760 yes or no and I give you the first bite 175 00:08:55,560 --> 00:09:00,920 of it you can pretty much guess what's 176 00:08:58,760 --> 00:09:04,720 the other bytes might 177 00:09:00,920 --> 00:09:07,560 be and there are many other problems uh 178 00:09:04,720 --> 00:09:11,200 with RSA in that shape for example if 179 00:09:07,560 --> 00:09:14,480 you um want to encrypt uh small numbers 180 00:09:11,200 --> 00:09:18,279 23 you take 23 to the power of three 181 00:09:14,480 --> 00:09:20,000 modulo some really huge uh number 23 to 182 00:09:18,279 --> 00:09:22,760 3 is 183 00:09:20,000 --> 00:09:26,279 12,167 that's way way smaller than 184 00:09:22,760 --> 00:09:30,120 though than n so you can simply throw 185 00:09:26,279 --> 00:09:31,839 the cube cube root at it and you get the 186 00:09:30,120 --> 00:09:34,240 BL text back that's an efficient 187 00:09:31,839 --> 00:09:37,800 operation and one of the reasons why you 188 00:09:34,240 --> 00:09:41,959 should naively use RSA U RSA now you 189 00:09:37,800 --> 00:09:44,519 might say I'm not going to encrypt um my 190 00:09:41,959 --> 00:09:47,000 plane text with RSA directly anyways I'm 191 00:09:44,519 --> 00:09:49,360 going to use hybrid encryption where I 192 00:09:47,000 --> 00:09:51,800 just encrypt a secret key for symmetric 193 00:09:49,360 --> 00:09:53,480 scheme with RSA and then encrypt the 194 00:09:51,800 --> 00:09:55,120 message with the symmetric scheme 195 00:09:53,480 --> 00:09:57,519 because that's way more efficient and it 196 00:09:55,120 --> 00:10:01,399 is indeed what you would usually do in 197 00:09:57,519 --> 00:10:04,440 reality but think about it um let's be 198 00:10:01,399 --> 00:10:07,399 generous and say you're using 256 uh key 199 00:10:04,440 --> 00:10:12,079 bits for some secure version of 200 00:10:07,399 --> 00:10:16,519 as and you're quite um daring and use 201 00:10:12,079 --> 00:10:21,079 only 1,24 uh bits of RSA 202 00:10:16,519 --> 00:10:24,079 key 256 * 3 is still a lot smaller than 203 00:10:21,079 --> 00:10:28,160 uh 1,24 so this attack perfectly works 204 00:10:24,079 --> 00:10:30,360 there and this means that you really 205 00:10:28,160 --> 00:10:32,160 have to be careful with RSA and also 206 00:10:30,360 --> 00:10:34,440 it's a deterministic scheme if you have 207 00:10:32,160 --> 00:10:36,639 an idea what the Blaine text might be 208 00:10:34,440 --> 00:10:39,040 you can simply encrypt it after all it's 209 00:10:36,639 --> 00:10:43,440 a public key encryption scheme and check 210 00:10:39,040 --> 00:10:46,160 if the result matches so the long story 211 00:10:43,440 --> 00:10:48,839 short version here is using RSA is not 212 00:10:46,160 --> 00:10:51,399 trivial there are secure versions of RSA 213 00:10:48,839 --> 00:10:53,240 or versions that we believe to be secure 214 00:10:51,399 --> 00:10:55,320 but they are a lot more complicated than 215 00:10:53,240 --> 00:10:57,880 what you're usually shown and for 216 00:10:55,320 --> 00:11:00,880 example none of them for none of them 217 00:10:57,880 --> 00:11:02,760 the often claim case of encrypting uh 218 00:11:00,880 --> 00:11:06,200 signing is encrypting with the secret 219 00:11:02,760 --> 00:11:07,880 key doesn't work um that statement that 220 00:11:06,200 --> 00:11:10,920 signing is encrypting with the secret 221 00:11:07,880 --> 00:11:13,000 key is not to my knowledge true for any 222 00:11:10,920 --> 00:11:16,720 secure scheme in either 223 00:11:13,000 --> 00:11:18,720 direction now RSA is not the only thing 224 00:11:16,720 --> 00:11:22,120 that has its 225 00:11:18,720 --> 00:11:24,360 issues and um we will later look at 226 00:11:22,120 --> 00:11:26,160 elgamal which is a very great encryption 227 00:11:24,360 --> 00:11:28,000 scheme but even there if you don't pay 228 00:11:26,160 --> 00:11:30,880 close attention you might end up leaking 229 00:11:28,000 --> 00:11:32,600 plain text bits and a single PL text bit 230 00:11:30,880 --> 00:11:34,639 can be disastrous in certain 231 00:11:32,600 --> 00:11:36,480 circumstances imagine you're doing an 232 00:11:34,639 --> 00:11:39,160 election and you encrypt your yes or no 233 00:11:36,480 --> 00:11:42,800 vote if I learn one bit about the plain 234 00:11:39,160 --> 00:11:45,320 text I learn everything and another 235 00:11:42,800 --> 00:11:47,920 example where people uh often have wrong 236 00:11:45,320 --> 00:11:51,519 ideas as with hashes yes it is true if 237 00:11:47,920 --> 00:11:53,600 you take some um random input from a big 238 00:11:51,519 --> 00:11:55,839 set and you throw it through a hash it's 239 00:11:53,600 --> 00:11:58,519 impractical to learn a pre-image for the 240 00:11:55,839 --> 00:12:00,880 hash but if the original set from which 241 00:11:58,519 --> 00:12:04,200 you're play uh pre-image comes is small 242 00:12:00,880 --> 00:12:06,079 you can simply brute force it and I've 243 00:12:04,200 --> 00:12:07,959 heard this several times that where 244 00:12:06,079 --> 00:12:10,959 people made this claim maybe they even 245 00:12:07,959 --> 00:12:12,880 knew it but they didn't say so the 246 00:12:10,959 --> 00:12:15,279 result is of course that you get 247 00:12:12,880 --> 00:12:18,720 vulnerabilities 248 00:12:15,279 --> 00:12:21,519 everywhere now we need so one of the 249 00:12:18,720 --> 00:12:23,760 issues that we saw in RSA with this RSA 250 00:12:21,519 --> 00:12:26,360 assumption was that we need some proper 251 00:12:23,760 --> 00:12:30,120 definition of what security actually 252 00:12:26,360 --> 00:12:32,680 means and a rather old notion that is 253 00:12:30,120 --> 00:12:36,320 not without problems but is a good first 254 00:12:32,680 --> 00:12:39,040 idea is called semantic security and 255 00:12:36,320 --> 00:12:41,120 what you see on the slides is a 256 00:12:39,040 --> 00:12:43,360 simplified version in the sense that it 257 00:12:41,120 --> 00:12:46,320 uses regular language instead of very 258 00:12:43,360 --> 00:12:48,560 comp complicated formulas but it gives 259 00:12:46,320 --> 00:12:51,639 you the CH uh the gist of what the idea 260 00:12:48,560 --> 00:12:54,079 is if I give you a public key and a 261 00:12:51,639 --> 00:12:56,160 cipher text you should not be able to 262 00:12:54,079 --> 00:12:59,199 learn anything about the contained PL 263 00:12:56,160 --> 00:13:01,680 text except for its length if this is 264 00:12:59,199 --> 00:13:04,000 true for an encryption scheme then we 265 00:13:01,680 --> 00:13:06,120 consider that um scheme secure in the 266 00:13:04,000 --> 00:13:09,600 sense that it provides semantic 267 00:13:06,120 --> 00:13:11,440 security the issue with this is it's not 268 00:13:09,600 --> 00:13:14,199 really that simple to prove that for 269 00:13:11,440 --> 00:13:16,920 schemes even if you use proper 270 00:13:14,199 --> 00:13:19,480 assumptions so there is another notion 271 00:13:16,920 --> 00:13:21,720 and that is called in CPA that is sh for 272 00:13:19,480 --> 00:13:22,800 indistinguishability under chosen Blain 273 00:13:21,720 --> 00:13:26,680 text 274 00:13:22,800 --> 00:13:30,639 attacks again this is the um colloquial 275 00:13:26,680 --> 00:13:33,320 version of it but it boils down to if I 276 00:13:30,639 --> 00:13:35,600 give you a public key and you are the 277 00:13:33,320 --> 00:13:38,560 attacker and you are now allowed to 278 00:13:35,600 --> 00:13:40,560 choose two plane texts can be anything 279 00:13:38,560 --> 00:13:43,199 as long as they have the same length you 280 00:13:40,560 --> 00:13:45,199 give both of them to me I pick a random 281 00:13:43,199 --> 00:13:47,480 one I will encrypt it with the public 282 00:13:45,199 --> 00:13:50,759 key and give you the cipher text you 283 00:13:47,480 --> 00:13:53,320 should not be able to uh distinguish 284 00:13:50,759 --> 00:13:55,600 which um plane text that you gave me I 285 00:13:53,320 --> 00:13:57,959 encrypted better than just making random 286 00:13:55,600 --> 00:14:00,279 guesses or at least substantially better 287 00:13:57,959 --> 00:14:02,320 there's always the chance that you just 288 00:14:00,279 --> 00:14:05,320 by pure chance guessed the secret key 289 00:14:02,320 --> 00:14:06,920 correctly we don't worry about that but 290 00:14:05,320 --> 00:14:10,680 anything that is substantially better 291 00:14:06,920 --> 00:14:13,519 than guessing is a real issue and we uh 292 00:14:10,680 --> 00:14:16,399 and the nice thing is at some point some 293 00:14:13,519 --> 00:14:18,519 people went through uh the trouble of 294 00:14:16,399 --> 00:14:20,880 proving that those two Notions are SEC 295 00:14:18,519 --> 00:14:25,199 are equivalent and thus if you prove in 296 00:14:20,880 --> 00:14:29,360 CPA security you have proven semantic 297 00:14:25,199 --> 00:14:31,959 security but again semantic security is 298 00:14:29,360 --> 00:14:34,399 just one definition of security and it 299 00:14:31,959 --> 00:14:36,800 is not necessarily A sufficient one for 300 00:14:34,399 --> 00:14:39,320 what you want we mentioned the CBC mode 301 00:14:36,800 --> 00:14:42,279 in the beginning um where you could had 302 00:14:39,320 --> 00:14:44,839 were able to fully decrypt some Blaine 303 00:14:42,279 --> 00:14:47,320 text using a petting Oracle CBC mode 304 00:14:44,839 --> 00:14:51,279 provide semantic security it's simply 305 00:14:47,320 --> 00:14:53,920 that they attack this um the uh pading 306 00:14:51,279 --> 00:14:56,160 Oracle is not part of the definition of 307 00:14:53,920 --> 00:14:58,519 semantic security and thus the attack 308 00:14:56,160 --> 00:15:00,079 happens outside of the security model so 309 00:14:58,519 --> 00:15:03,079 it's it's really important that you 310 00:15:00,079 --> 00:15:05,000 choose um a good and appropriate 311 00:15:03,079 --> 00:15:07,680 security model I believe we have a 312 00:15:05,000 --> 00:15:11,000 couple of more examples where this will 313 00:15:07,680 --> 00:15:12,880 come up and a very notable one that we 314 00:15:11,000 --> 00:15:15,199 won't talk about anymore in this talk 315 00:15:12,880 --> 00:15:17,279 are site Channel attacks if you are 316 00:15:15,199 --> 00:15:19,720 capable of learning The Secret Key by 317 00:15:17,279 --> 00:15:22,320 just um looking at the network stream 318 00:15:19,720 --> 00:15:24,839 and take a stopwatch the encryption 319 00:15:22,320 --> 00:15:27,240 scheme can be as good as you want it 320 00:15:24,839 --> 00:15:31,279 won't help you if that is the way you 321 00:15:27,240 --> 00:15:32,920 get a key and and that's where why uh 322 00:15:31,279 --> 00:15:35,600 implementing cryptography is so hard 323 00:15:32,920 --> 00:15:39,560 because you have to um take care of all 324 00:15:35,600 --> 00:15:42,399 these problems also just because a 325 00:15:39,560 --> 00:15:44,240 scheme is secure on its own that doesn't 326 00:15:42,399 --> 00:15:47,120 mean that this is secure if you combine 327 00:15:44,240 --> 00:15:48,880 it with other schemes and finding a 328 00:15:47,120 --> 00:15:50,399 proper definition of security can 329 00:15:48,880 --> 00:15:53,000 sometimes be the hardest problem of all 330 00:15:50,399 --> 00:15:55,160 in cryptography there are actually cases 331 00:15:53,000 --> 00:15:57,440 where it's easier to come up with aure 332 00:15:55,160 --> 00:15:59,839 solution to a problem than with a proper 333 00:15:57,440 --> 00:16:03,880 definition of what sec cure 334 00:15:59,839 --> 00:16:05,920 means now that being said let's look at 335 00:16:03,880 --> 00:16:08,120 how we do the 336 00:16:05,920 --> 00:16:10,199 proofs um we are doing so-called 337 00:16:08,120 --> 00:16:13,519 reductions as Lucas already 338 00:16:10,199 --> 00:16:14,920 explained we cannot do absolute proofs 339 00:16:13,519 --> 00:16:16,440 that don't need assumptions because 340 00:16:14,920 --> 00:16:19,040 there is this Millennium problem in the 341 00:16:16,440 --> 00:16:23,319 way so we need some assumption for a 342 00:16:19,040 --> 00:16:25,759 hard problem and this is usually defined 343 00:16:23,319 --> 00:16:27,800 as some kind of game where you have a 344 00:16:25,759 --> 00:16:29,319 Challenger in this case we call this the 345 00:16:27,800 --> 00:16:32,120 Assumption Challenger 346 00:16:29,319 --> 00:16:35,880 that gives us some kind of challenge for 347 00:16:32,120 --> 00:16:37,839 example um The Challenge where he says 348 00:16:35,880 --> 00:16:41,720 here is an RSA public here in a cipher 349 00:16:37,839 --> 00:16:45,079 text give me the plain text and we then 350 00:16:41,720 --> 00:16:48,279 have some kind of translator and we have 351 00:16:45,079 --> 00:16:51,880 the um an attacker on our scheme that we 352 00:16:48,279 --> 00:16:54,279 want to prove as secure so for example 353 00:16:51,880 --> 00:16:56,360 um this might be an attacker on the ncpa 354 00:16:54,279 --> 00:16:59,639 security of an encryption scheme and it 355 00:16:56,360 --> 00:17:02,519 will take um again some kind of uh 356 00:16:59,639 --> 00:17:05,439 public key and play uh some kind of 357 00:17:02,519 --> 00:17:09,000 security game and the translator now has 358 00:17:05,439 --> 00:17:10,439 the task to translate the challenge that 359 00:17:09,000 --> 00:17:13,919 it received from the Assumption 360 00:17:10,439 --> 00:17:17,240 Challenger into something that the um 361 00:17:13,919 --> 00:17:19,959 attacker on the um scheme that we want 362 00:17:17,240 --> 00:17:21,400 to prove as secure can use to attack 363 00:17:19,959 --> 00:17:23,520 that scheme if it is capable of 364 00:17:21,400 --> 00:17:25,839 attacking the scheme and then translate 365 00:17:23,520 --> 00:17:29,039 the result of that attack back into 366 00:17:25,839 --> 00:17:31,200 something that um the original 367 00:17:29,039 --> 00:17:33,679 assumption Challenger would accept as a 368 00:17:31,200 --> 00:17:35,600 break of the Assumption and since we 369 00:17:33,679 --> 00:17:38,600 believe that there is no way to break 370 00:17:35,600 --> 00:17:41,160 the Assumption and we demonstrated that 371 00:17:38,600 --> 00:17:42,600 uh breaking our scheme uh breaks the 372 00:17:41,160 --> 00:17:43,880 also implies an attack against the 373 00:17:42,600 --> 00:17:47,840 Assumption we believe that is 374 00:17:43,880 --> 00:17:51,559 Impractical to break uh our 375 00:17:47,840 --> 00:17:53,720 scheme we will now look at a full 376 00:17:51,559 --> 00:17:55,720 example where this will maybe get a 377 00:17:53,720 --> 00:17:58,520 little bit more clear and for that we 378 00:17:55,720 --> 00:18:01,400 will look at a encryption scheme called 379 00:17:58,520 --> 00:18:03,200 elgamal which unlike RSA is secure out 380 00:18:01,400 --> 00:18:05,280 of the box at least in a sense of 381 00:18:03,200 --> 00:18:08,440 semantic 382 00:18:05,280 --> 00:18:11,000 security again we start with two big 383 00:18:08,440 --> 00:18:13,720 primes p and Q but this time they are 384 00:18:11,000 --> 00:18:16,200 required to have a special property P 385 00:18:13,720 --> 00:18:18,559 has to be twice Q + 1 so they are 386 00:18:16,200 --> 00:18:22,159 closely related primes and we also call 387 00:18:18,559 --> 00:18:25,200 P a safe Prime and Q a sopa mod Prime 388 00:18:22,159 --> 00:18:28,400 and the reason of this these we won't go 389 00:18:25,200 --> 00:18:30,159 into here um you also need to take some 390 00:18:28,400 --> 00:18:32,720 something called a generator and we just 391 00:18:30,159 --> 00:18:34,880 pick four because that always works if 392 00:18:32,720 --> 00:18:36,280 you pick a bad generator this is 393 00:18:34,880 --> 00:18:39,280 actually the case that I mentioned in 394 00:18:36,280 --> 00:18:42,360 the beginning where you leak PL text 395 00:18:39,280 --> 00:18:44,960 bits and we will now do several 396 00:18:42,360 --> 00:18:47,039 operations of those we have some 397 00:18:44,960 --> 00:18:49,000 operations between elements where we 398 00:18:47,039 --> 00:18:52,200 multiply base elements those are all 399 00:18:49,000 --> 00:18:54,320 modulo P so the lowercase here and we 400 00:18:52,200 --> 00:18:57,280 have exponents in the game and those are 401 00:18:54,320 --> 00:19:00,320 modular q and for reasons that you can 402 00:18:57,280 --> 00:19:03,840 learn about in a group group Theory um 403 00:19:00,320 --> 00:19:07,039 university lecture this makes actually 404 00:19:03,840 --> 00:19:09,760 sense and for notational purposes the 405 00:19:07,039 --> 00:19:13,039 set of all integers between zero and Q 406 00:19:09,760 --> 00:19:17,559 minus one we will call set 407 00:19:13,039 --> 00:19:19,720 Q now in order to use elgamal we need we 408 00:19:17,559 --> 00:19:21,360 assume we have those integers P andq 409 00:19:19,720 --> 00:19:23,080 they don't need to be secret or anything 410 00:19:21,360 --> 00:19:26,559 they can even be standardized and 411 00:19:23,080 --> 00:19:29,360 usually or very often they actually are 412 00:19:26,559 --> 00:19:33,120 and the key generator will Now sample a 413 00:19:29,360 --> 00:19:37,240 random exponent x from set q and this is 414 00:19:33,120 --> 00:19:40,600 the secret key then um he or she will 415 00:19:37,240 --> 00:19:45,600 take the generator G and compute G to 416 00:19:40,600 --> 00:19:47,960 the power of X so again this is modulo p 417 00:19:45,600 --> 00:19:52,320 so this number won't grow completely out 418 00:19:47,960 --> 00:19:55,320 of proportion but um what um yeah the 419 00:19:52,320 --> 00:19:58,360 result is the public key you already see 420 00:19:55,320 --> 00:20:00,760 here um this operation this G to the x 421 00:19:58,360 --> 00:20:02,840 is probably hard to reverse so you can't 422 00:20:00,760 --> 00:20:05,000 undo this to get a signature scheme out 423 00:20:02,840 --> 00:20:07,120 of this and that's everything you need 424 00:20:05,000 --> 00:20:09,880 to do for key generation which is much 425 00:20:07,120 --> 00:20:12,280 easier than finding two primes for 426 00:20:09,880 --> 00:20:15,960 RSA encryption is a little bit more 427 00:20:12,280 --> 00:20:18,720 complicated but also doable you pick 428 00:20:15,960 --> 00:20:20,440 another random integer R this is your 429 00:20:18,720 --> 00:20:23,760 encryption Randomness this avoids the 430 00:20:20,440 --> 00:20:26,039 attack of um looking uh of trying to 431 00:20:23,760 --> 00:20:27,640 encrypt some assumed BL text and 432 00:20:26,039 --> 00:20:28,799 checking whether they match because 433 00:20:27,640 --> 00:20:31,520 every time you script you use a 434 00:20:28,799 --> 00:20:34,039 different value R and then you compute G 435 00:20:31,520 --> 00:20:36,159 Tod R first this is your first part of 436 00:20:34,039 --> 00:20:38,880 your Cipher text then you take the 437 00:20:36,159 --> 00:20:41,679 public key G to the X and compute it to 438 00:20:38,880 --> 00:20:45,400 the power of R and by the rules of uh 439 00:20:41,679 --> 00:20:49,240 how Powers work G to the X to the r is 440 00:20:45,400 --> 00:20:52,240 equal to G Tod x * R and that you 441 00:20:49,240 --> 00:20:54,120 multiply simply with the pl text M those 442 00:20:52,240 --> 00:20:55,679 two elements are now your complete 443 00:20:54,120 --> 00:20:59,880 Cipher text and that is everything you 444 00:20:55,679 --> 00:21:04,039 have to do for encryption and finally 445 00:20:59,880 --> 00:21:07,039 decryption um you take the second part 446 00:21:04,039 --> 00:21:10,679 of the um Cipher text here so this G to 447 00:21:07,039 --> 00:21:13,279 the XR * m and the idea is now that you 448 00:21:10,679 --> 00:21:16,320 remove this G to the XR and for that you 449 00:21:13,279 --> 00:21:19,279 take the G Tod R and compute it to the 450 00:21:16,320 --> 00:21:22,760 power of X and again rules of power G to 451 00:21:19,279 --> 00:21:25,080 the r to the x is g to the RX and if you 452 00:21:22,760 --> 00:21:29,919 now do this to the minus one you get G 453 00:21:25,080 --> 00:21:33,600 to the minus RX G to the minus RX * G to 454 00:21:29,919 --> 00:21:36,960 the RX is g to the RX minus RX this is g 455 00:21:33,600 --> 00:21:39,000 to the Z which is 1 so it's you just 456 00:21:36,960 --> 00:21:42,120 have the BL Tex left here and you're 457 00:21:39,000 --> 00:21:43,799 done with the decryption and that's all 458 00:21:42,120 --> 00:21:47,279 there is to the scheme so it's not 459 00:21:43,799 --> 00:21:48,880 really that hard now we still need an 460 00:21:47,279 --> 00:21:51,400 assumption relative to which we will 461 00:21:48,880 --> 00:21:53,159 prove uh that algal is secure and for 462 00:21:51,400 --> 00:21:54,480 that we will use the decisional defy 463 00:21:53,159 --> 00:21:57,440 Helman 464 00:21:54,480 --> 00:22:00,200 assumption it says that if you take 465 00:21:57,440 --> 00:22:02,600 three random exponents it is not you're 466 00:22:00,200 --> 00:22:04,440 not able you're not going to be able to 467 00:22:02,600 --> 00:22:07,240 tell whether I give you a triple that 468 00:22:04,440 --> 00:22:09,840 consists out of GTX G to the Y G to the 469 00:22:07,240 --> 00:22:12,760 Z or of or a triple that consists of G 470 00:22:09,840 --> 00:22:16,279 to the x g to the Y and G to the 471 00:22:12,760 --> 00:22:18,919 XY um we won't argue why this is true 472 00:22:16,279 --> 00:22:21,520 there is some good rational why we might 473 00:22:18,919 --> 00:22:23,360 believe that but this is an assumption 474 00:22:21,520 --> 00:22:25,000 so we don't have to prove it we just 475 00:22:23,360 --> 00:22:26,960 have to assume it and then prove that 476 00:22:25,000 --> 00:22:28,720 our scheme is secure if this assumption 477 00:22:26,960 --> 00:22:31,640 holds 478 00:22:28,720 --> 00:22:33,760 and for that we are going to use the uh 479 00:22:31,640 --> 00:22:36,799 game structure that you just that I 480 00:22:33,760 --> 00:22:39,880 showed you before that and this is the 481 00:22:36,799 --> 00:22:44,159 full game so at the start you see the 482 00:22:39,880 --> 00:22:46,240 ddh Challenger uh passes some triple to 483 00:22:44,159 --> 00:22:48,559 the translator and at the end the 484 00:22:46,240 --> 00:22:51,200 translator outputs a bit B that tells 485 00:22:48,559 --> 00:22:54,279 the translator's Assumption whether set 486 00:22:51,200 --> 00:22:56,279 in this case is equal to x * y so you 487 00:22:54,279 --> 00:22:58,559 have this game on the left side on the 488 00:22:56,279 --> 00:23:01,840 right side you have the in CPA game game 489 00:22:58,559 --> 00:23:04,679 so you have in the start you give a 490 00:23:01,840 --> 00:23:07,720 public key so for this you use ch2d x to 491 00:23:04,679 --> 00:23:10,200 the elgamal attacker then the attacker 492 00:23:07,720 --> 00:23:13,480 will hand out two uh possible plane 493 00:23:10,200 --> 00:23:15,919 texts m0 and M1 and the translator now 494 00:23:13,480 --> 00:23:18,679 selects one at random for that uh he 495 00:23:15,919 --> 00:23:21,240 picks a random bit B and MB will from 496 00:23:18,679 --> 00:23:24,520 now on be the selected plane 497 00:23:21,240 --> 00:23:27,279 text you then take it then takes the 498 00:23:24,520 --> 00:23:29,840 second part of the provided triple G2 Dy 499 00:23:27,279 --> 00:23:32,480 and uses that in place of G Tod R so 500 00:23:29,840 --> 00:23:35,320 that's the first part of the cipher text 501 00:23:32,480 --> 00:23:38,080 and it takes G to the Z in place of G to 502 00:23:35,320 --> 00:23:40,960 the RX so the second part of the cyer 503 00:23:38,080 --> 00:23:44,679 text except for the plain text which we 504 00:23:40,960 --> 00:23:47,159 let at afterwards so you see here this 505 00:23:44,679 --> 00:23:50,080 has basically the structure of an algal 506 00:23:47,159 --> 00:23:52,679 uh Cipher text and then you let the 507 00:23:50,080 --> 00:23:54,760 attacker guess it can now do pretty much 508 00:23:52,679 --> 00:23:57,120 what it wants as long as it doesn't run 509 00:23:54,760 --> 00:23:59,799 uh extraordinarily long and at the end 510 00:23:57,120 --> 00:24:02,960 it will output an assumption uh B Dash 511 00:23:59,799 --> 00:24:04,600 about which BL text was encrypted the 512 00:24:02,960 --> 00:24:06,799 translator then just checks whether the 513 00:24:04,600 --> 00:24:09,640 assumption is correct and outputs the 514 00:24:06,799 --> 00:24:12,200 bit whether it is correct to the 515 00:24:09,640 --> 00:24:15,080 Challenger it might not be completely 516 00:24:12,200 --> 00:24:18,480 obvious at this point why this is a 517 00:24:15,080 --> 00:24:21,440 proof but let's consider the different 518 00:24:18,480 --> 00:24:24,880 cases um let's say the attacker has a 519 00:24:21,440 --> 00:24:27,279 success rate of 1/2 plus Epsilon 1/2 is 520 00:24:24,880 --> 00:24:30,760 the uh probability that you would get by 521 00:24:27,279 --> 00:24:32,559 just r guessing so if the attacker is 522 00:24:30,760 --> 00:24:35,240 better than just random guessing there 523 00:24:32,559 --> 00:24:38,120 has to be some additional so-called 524 00:24:35,240 --> 00:24:39,760 adversarial Advantage Epsilon and we 525 00:24:38,120 --> 00:24:44,559 just assume that it is 526 00:24:39,760 --> 00:24:47,679 positive now if x * Y is equal to set 527 00:24:44,559 --> 00:24:49,840 which is the case 50% of the time then 528 00:24:47,679 --> 00:24:54,080 this is a perfect simulation of the uh 529 00:24:49,840 --> 00:24:57,279 real uh ncpa game because the public key 530 00:24:54,080 --> 00:24:59,679 G2 Rex is a completely random element so 531 00:24:57,279 --> 00:25:02,240 perfectly IND distinguishable G to d y 532 00:24:59,679 --> 00:25:04,960 perfect indistinguishably also random G 533 00:25:02,240 --> 00:25:09,120 Tod Z is in that case by definition 534 00:25:04,960 --> 00:25:13,799 equal to x g Tod x * y so again perfect 535 00:25:09,120 --> 00:25:15,799 uh simulation and we simply get the um 536 00:25:13,799 --> 00:25:19,559 success probability of the attacker in 537 00:25:15,799 --> 00:25:23,480 that case and yeah so that's fine 538 00:25:19,559 --> 00:25:28,120 otherwise however um g2d set is not in 539 00:25:23,480 --> 00:25:31,320 any kind of correlation to uh G2x and G2 540 00:25:28,120 --> 00:25:33,960 d y and as such it is also this plane 541 00:25:31,320 --> 00:25:36,520 this Cipher text won't be in any 542 00:25:33,960 --> 00:25:38,159 correlation uh with to either of the 543 00:25:36,520 --> 00:25:41,279 Blaine texts with overwhelming 544 00:25:38,159 --> 00:25:43,720 probability so it's only possible to get 545 00:25:41,279 --> 00:25:46,760 a success rate of 1 half for the 546 00:25:43,720 --> 00:25:49,399 attacker and since either of these have 547 00:25:46,760 --> 00:25:52,399 a probability of of occurring of one2 we 548 00:25:49,399 --> 00:25:54,880 simply compute the mean value of those 549 00:25:52,399 --> 00:25:58,200 and that happens to be 1 12 plus Epsilon 550 00:25:54,880 --> 00:26:00,559 half therefore if the there is an 551 00:25:58,200 --> 00:26:04,039 attacker against the semantic security 552 00:26:00,559 --> 00:26:06,880 or the ncpa security of elgamal we just 553 00:26:04,039 --> 00:26:09,760 converted it into an attacker on the ddh 554 00:26:06,880 --> 00:26:12,960 Assumption with success probability 1 12 555 00:26:09,760 --> 00:26:14,840 plus Epsilon half if Epsilon is non- 556 00:26:12,960 --> 00:26:17,279 negligible then the definition of 557 00:26:14,840 --> 00:26:19,640 negligible implies that Epsilon half is 558 00:26:17,279 --> 00:26:22,440 also non- negligible and since we 559 00:26:19,640 --> 00:26:24,960 believe that there is no attacker on the 560 00:26:22,440 --> 00:26:27,399 uh ddh assumption that has non- 561 00:26:24,960 --> 00:26:29,880 negligible Advantage we conclude that 562 00:26:27,399 --> 00:26:33,080 there also no attacker on the security 563 00:26:29,880 --> 00:26:35,120 of the elgamal scheme that has um non- 564 00:26:33,080 --> 00:26:38,440 negligible Advantage it follows that 565 00:26:35,120 --> 00:26:41,559 elgamal is ncpa secure and thus provides 566 00:26:38,440 --> 00:26:45,200 semantic security end of 567 00:26:41,559 --> 00:26:47,279 proof now you might say yeah but what 568 00:26:45,200 --> 00:26:48,720 did we gain of that we um replaced the 569 00:26:47,279 --> 00:26:51,480 assumption that the encryption scheme is 570 00:26:48,720 --> 00:26:55,399 secure with an assumption that is also 571 00:26:51,480 --> 00:26:57,640 quite weird well first of all the 572 00:26:55,399 --> 00:26:59,360 assumption is a little bit less complex 573 00:26:57,640 --> 00:27:03,000 though in that that case the difference 574 00:26:59,360 --> 00:27:06,279 is not that huge but this is an image of 575 00:27:03,000 --> 00:27:08,640 the old version of the TLs handshake as 576 00:27:06,279 --> 00:27:10,640 you see you probably see nothing because 577 00:27:08,640 --> 00:27:12,159 it is too complicated to properly fit on 578 00:27:10,640 --> 00:27:14,600 the slide which is the entire point I'm 579 00:27:12,159 --> 00:27:16,520 trying to make here these kinds of 580 00:27:14,600 --> 00:27:19,120 proofs allow you to take a complex 581 00:27:16,520 --> 00:27:22,399 scheme and reduce it to the security of 582 00:27:19,120 --> 00:27:24,520 some small simple well understood uh 583 00:27:22,399 --> 00:27:26,799 assumption and you can also share this 584 00:27:24,520 --> 00:27:29,120 assumption there are many cryptographic 585 00:27:26,799 --> 00:27:34,120 schemes that can be can be reduced to 586 00:27:29,120 --> 00:27:36,480 incp uh to DD to the ddh Assumption and 587 00:27:34,120 --> 00:27:38,200 that way all everyone who wants to try 588 00:27:36,480 --> 00:27:41,240 to break the schemes can simply try to 589 00:27:38,200 --> 00:27:42,919 break the ddh Assumption and either all 590 00:27:41,240 --> 00:27:44,679 schemes are broken or none of them but 591 00:27:42,919 --> 00:27:47,399 we have uh something that we can very 592 00:27:44,679 --> 00:27:50,120 well concentrate on if you visited the 593 00:27:47,399 --> 00:27:52,600 postquantum crypto talk yesterday uh 594 00:27:50,120 --> 00:27:55,240 Tanya and djb were complaining about all 595 00:27:52,600 --> 00:27:57,559 those proposals for the postquantum uh 596 00:27:55,240 --> 00:28:00,840 schemes and that it was impossible to 597 00:27:57,559 --> 00:28:03,760 review them all this is what allows to 598 00:28:00,840 --> 00:28:05,240 review all those new um cryptographic 599 00:28:03,760 --> 00:28:07,240 schemes that are not only encryption 600 00:28:05,240 --> 00:28:09,880 schemes because everyone just has to 601 00:28:07,240 --> 00:28:13,720 look at very few 602 00:28:09,880 --> 00:28:15,360 assumptions and you also avoid problems 603 00:28:13,720 --> 00:28:18,279 from weird interactions if you have 604 00:28:15,360 --> 00:28:21,480 multiple assumptions um this was not the 605 00:28:18,279 --> 00:28:24,559 case right now but in reality you use 606 00:28:21,480 --> 00:28:26,600 several Primitives and even if those are 607 00:28:24,559 --> 00:28:29,159 secure on their own they might not be if 608 00:28:26,600 --> 00:28:31,360 you combine in with others and the proof 609 00:28:29,159 --> 00:28:34,240 now gives you the certainty that my 610 00:28:31,360 --> 00:28:37,000 scheme is secure as long as all of those 611 00:28:34,240 --> 00:28:41,200 are secure I didn't introduce issues 612 00:28:37,000 --> 00:28:45,919 from combining them which is also very 613 00:28:41,200 --> 00:28:47,919 valuable now um back to the definition 614 00:28:45,919 --> 00:28:49,360 of security and the problems there or 615 00:28:47,919 --> 00:28:51,519 well in this case not really that much 616 00:28:49,360 --> 00:28:53,960 of a problem what you just saw is a so 617 00:28:51,519 --> 00:28:56,039 called game based proof I mean you saw a 618 00:28:53,960 --> 00:28:59,159 game so it's rather intuitive why it's 619 00:28:56,039 --> 00:29:02,279 called that way and those are generally 620 00:28:59,159 --> 00:29:05,600 speaking easier to do than the 621 00:29:02,279 --> 00:29:07,919 alternative exceptions exist but they 622 00:29:05,600 --> 00:29:11,320 often have a less intuitive meaning for 623 00:29:07,919 --> 00:29:15,240 example I told you that rough definition 624 00:29:11,320 --> 00:29:17,640 of ncpa and semantic security ncpa was 625 00:29:15,240 --> 00:29:19,799 comparatively weird and Technical 626 00:29:17,640 --> 00:29:21,760 whereas semantic security was pretty 627 00:29:19,799 --> 00:29:23,320 straight to the point and that is often 628 00:29:21,760 --> 00:29:26,440 an issue that those game based 629 00:29:23,320 --> 00:29:28,760 definitions have they are very technical 630 00:29:26,440 --> 00:29:32,120 and it's harder to get an intuitive idea 631 00:29:28,760 --> 00:29:35,039 what they really mean also the more 632 00:29:32,120 --> 00:29:36,760 complex your protocols get and for 633 00:29:35,039 --> 00:29:39,320 example if you want to design 634 00:29:36,760 --> 00:29:41,440 cryptographic voting schemes the less 635 00:29:39,320 --> 00:29:42,720 these proof scale at some point you need 636 00:29:41,440 --> 00:29:44,919 to switch to the 637 00:29:42,720 --> 00:29:48,760 alternative which are so-called 638 00:29:44,919 --> 00:29:51,960 simulation based proofs for those you 639 00:29:48,760 --> 00:29:54,399 define some ideal functionality so 640 00:29:51,960 --> 00:29:56,320 imagine it as a trusted party that just 641 00:29:54,399 --> 00:29:58,960 falls from the sky and is perfectly 642 00:29:56,320 --> 00:30:02,760 trustworthy you define whatever you want 643 00:29:58,960 --> 00:30:04,279 to do is done by that party and then um 644 00:30:02,760 --> 00:30:05,799 assume that everyone has perfectly 645 00:30:04,279 --> 00:30:08,720 secure connections to that party and 646 00:30:05,799 --> 00:30:12,880 then prove that your real protocol is as 647 00:30:08,720 --> 00:30:15,000 secure as this idealized uh thing those 648 00:30:12,880 --> 00:30:17,320 proofs tend to get more intuitive 649 00:30:15,000 --> 00:30:18,880 meanings uh semantic security is a 650 00:30:17,320 --> 00:30:22,279 simulation-based 651 00:30:18,880 --> 00:30:24,240 um uh definition of security and as I 652 00:30:22,279 --> 00:30:27,039 said it's a lot easier to understand 653 00:30:24,240 --> 00:30:30,640 what it means but they also usually a 654 00:30:27,039 --> 00:30:33,559 bit harder to do also especially with 655 00:30:30,640 --> 00:30:35,120 them though that may be because the uh 656 00:30:33,559 --> 00:30:37,120 schemes that you will usually prove of 657 00:30:35,120 --> 00:30:39,720 them are more complicated you can get 658 00:30:37,120 --> 00:30:42,399 something called proof artifacts that's 659 00:30:39,720 --> 00:30:45,279 where you need some very weird thing in 660 00:30:42,399 --> 00:30:47,559 your cryptographic scheme that doesn't 661 00:30:45,279 --> 00:30:50,360 appear to serve any purpose for 662 00:30:47,559 --> 00:30:52,960 example you suddenly have a cipher text 663 00:30:50,360 --> 00:30:55,360 in some place for a public key and no 664 00:30:52,960 --> 00:30:57,720 nobody ever has a secret key for that 665 00:30:55,360 --> 00:31:00,799 public key and that may sound sound very 666 00:30:57,720 --> 00:31:03,320 weird and pointless and sometimes it may 667 00:31:00,799 --> 00:31:05,279 be sometimes actually do serve a purpose 668 00:31:03,320 --> 00:31:07,880 so just because something looks weird 669 00:31:05,279 --> 00:31:11,000 doesn't mean that it is unnecessary but 670 00:31:07,880 --> 00:31:14,200 maybe sometimes it is and that's one of 671 00:31:11,000 --> 00:31:17,279 the big issues we Face there 672 00:31:14,200 --> 00:31:22,279 now in the start I mentioned RSA and I 673 00:31:17,279 --> 00:31:24,720 said there are secure versions of it and 674 00:31:22,279 --> 00:31:26,559 this is the case however they require 675 00:31:24,720 --> 00:31:28,480 something a bit more complicated and one 676 00:31:26,559 --> 00:31:30,600 of the things they Ed to acquire 677 00:31:28,480 --> 00:31:33,600 security are hash 678 00:31:30,600 --> 00:31:35,760 functions and hash functions are pretty 679 00:31:33,600 --> 00:31:39,440 much functions where you can throw in 680 00:31:35,760 --> 00:31:42,320 some random some string of some length 681 00:31:39,440 --> 00:31:44,120 and get out a random looking bit strings 682 00:31:42,320 --> 00:31:47,399 of fixed lengths independently of how 683 00:31:44,120 --> 00:31:50,480 long the um string that you throw in is 684 00:31:47,399 --> 00:31:53,200 and I say random looking because the 685 00:31:50,480 --> 00:31:55,039 proper definitions of what uh a secure 686 00:31:53,200 --> 00:31:56,880 hash function is are shockingly 687 00:31:55,039 --> 00:32:00,120 complicated you can ask me after the 688 00:31:56,880 --> 00:32:02,480 lecture if you want but um it's very 689 00:32:00,120 --> 00:32:05,519 very easy to get them wrong especially 690 00:32:02,480 --> 00:32:08,080 since they appear to be so easy now 691 00:32:05,519 --> 00:32:11,200 Lucas will now tell us how these hash 692 00:32:08,080 --> 00:32:13,760 functions are used or well some of the 693 00:32:11,200 --> 00:32:16,559 issues that they we face with them 694 00:32:13,760 --> 00:32:18,399 because the RSA proofs are not really in 695 00:32:16,559 --> 00:32:19,360 the standard model instead they use 696 00:32:18,399 --> 00:32:23,080 something 697 00:32:19,360 --> 00:32:26,799 else yes well if we want to model a hash 698 00:32:23,080 --> 00:32:28,840 function in our proofs and we want to 699 00:32:26,799 --> 00:32:31,039 get rid of all these strange properties 700 00:32:28,840 --> 00:32:34,600 of hash functions we use something 701 00:32:31,039 --> 00:32:38,159 called a random Oracle which is in fact 702 00:32:34,600 --> 00:32:42,399 uh this dwarf and this dwarf uh lives in 703 00:32:38,159 --> 00:32:44,799 a box and he has a DI in a book and if 704 00:32:42,399 --> 00:32:47,559 someone comes to the box and wants to 705 00:32:44,799 --> 00:32:50,159 have a hash for a specific message he 706 00:32:47,559 --> 00:32:52,960 looks into his book and wants to check 707 00:32:50,159 --> 00:32:55,720 out if he already answered such an 708 00:32:52,960 --> 00:32:57,960 message and if he did then he answers in 709 00:32:55,720 --> 00:33:01,200 the same way as he did before 710 00:32:57,960 --> 00:33:04,080 and otherwise he rolls his Dice and gets 711 00:33:01,200 --> 00:33:07,360 a new random value uh which is now the 712 00:33:04,080 --> 00:33:07,360 hash of this 713 00:33:07,880 --> 00:33:14,080 message unfortunately no one has ever 714 00:33:11,000 --> 00:33:15,799 found such a box with a dwarf and 715 00:33:14,080 --> 00:33:18,320 furthermore it would be quite difficult 716 00:33:15,799 --> 00:33:20,559 to handle because every time you want to 717 00:33:18,320 --> 00:33:22,519 compute a hash you would have to go to 718 00:33:20,559 --> 00:33:26,000 the 719 00:33:22,519 --> 00:33:28,760 dwarf but the biggest problem is that 720 00:33:26,000 --> 00:33:31,360 this is not a 721 00:33:28,760 --> 00:33:33,720 abstraction and I'll show you what the 722 00:33:31,360 --> 00:33:33,720 problem 723 00:33:33,919 --> 00:33:39,320 is let's assume that we have a secure 724 00:33:37,559 --> 00:33:43,279 encryption 725 00:33:39,320 --> 00:33:46,320 scheme and let H be either a hash 726 00:33:43,279 --> 00:33:46,320 function or a random 727 00:33:46,679 --> 00:33:53,320 Oracle then we simply 728 00:33:49,840 --> 00:33:55,960 reuse the generation algorithm which 729 00:33:53,320 --> 00:33:59,399 gives us a Keir for a new encryption 730 00:33:55,960 --> 00:34:01,000 scheme and we partly reuse the 731 00:33:59,399 --> 00:34:04,320 encryption 732 00:34:01,000 --> 00:34:07,800 algorithm and modify it like this we 733 00:34:04,320 --> 00:34:11,079 check is the message valid 734 00:34:07,800 --> 00:34:13,440 code note that uh a code execution 735 00:34:11,079 --> 00:34:17,639 attack is not the problem here we simply 736 00:34:13,440 --> 00:34:21,520 look at it is it a valid uh code we take 737 00:34:17,639 --> 00:34:26,399 random input X and evaluate the code 738 00:34:21,520 --> 00:34:29,760 given this uh random input and if the 739 00:34:26,399 --> 00:34:32,879 results of the code is different than 740 00:34:29,760 --> 00:34:34,879 what age tells us then we use our secure 741 00:34:32,879 --> 00:34:37,679 encryption 742 00:34:34,879 --> 00:34:42,040 scheme but if it's the 743 00:34:37,679 --> 00:34:46,440 same we use our secret key as the cipher 744 00:34:42,040 --> 00:34:49,440 text this might sound very weird yes you 745 00:34:46,440 --> 00:34:54,119 should not do this in a real encryption 746 00:34:49,440 --> 00:34:56,520 scheme but here we can see that this 747 00:34:54,119 --> 00:34:57,640 scheme is secure if we use a random 748 00:34:56,520 --> 00:35:00,440 Oracle 749 00:34:57,640 --> 00:35:01,640 but insecure for any instantiation with 750 00:35:00,440 --> 00:35:05,240 a hash 751 00:35:01,640 --> 00:35:09,000 function if you use a random Oracle the 752 00:35:05,240 --> 00:35:13,280 probability of uh the dwarf to get uh 753 00:35:09,000 --> 00:35:16,280 the same output as the given code is 754 00:35:13,280 --> 00:35:19,480 negligible because it's randomly 755 00:35:16,280 --> 00:35:22,200 chosen but for a real hash function you 756 00:35:19,480 --> 00:35:25,680 simply can put in the code of your hash 757 00:35:22,200 --> 00:35:29,000 function and it will of course be 758 00:35:25,680 --> 00:35:31,800 evaluated to the uh same result as the 759 00:35:29,000 --> 00:35:33,280 hash function and then you always get 760 00:35:31,800 --> 00:35:37,280 the secret 761 00:35:33,280 --> 00:35:41,680 key so the random Oracle allows us to 762 00:35:37,280 --> 00:35:41,680 prove schemes which are obviously 763 00:35:42,359 --> 00:35:48,920 insecure uh the authors who uh write the 764 00:35:45,720 --> 00:35:51,000 first paper on this came to some harsh 765 00:35:48,920 --> 00:35:53,040 statements it should be clear that the 766 00:35:51,000 --> 00:35:55,160 random Oracle mythology is not sound 767 00:35:53,040 --> 00:35:57,319 that is the mere fact that a scheme is 768 00:35:55,160 --> 00:36:00,400 secure in the random Oracle model cannot 769 00:35:57,319 --> 00:36:03,079 taken as evidence or indication to the 770 00:36:00,400 --> 00:36:05,480 security and furthermore he 771 00:36:03,079 --> 00:36:07,800 said indeed what happened with the 772 00:36:05,480 --> 00:36:10,560 random Oracle model reminds us of the 773 00:36:07,800 --> 00:36:12,880 biblical story of The Bronze serpent the 774 00:36:10,560 --> 00:36:15,160 story illustrates the process by which a 775 00:36:12,880 --> 00:36:18,319 good thing may become a fetish and what 776 00:36:15,160 --> 00:36:22,599 you should do in such a 777 00:36:18,319 --> 00:36:25,000 case spoiler alert this snake had to be 778 00:36:22,599 --> 00:36:28,839 destroyed but if you need to sign the 779 00:36:25,000 --> 00:36:32,240 Bible as a cryptographer uh your point 780 00:36:28,839 --> 00:36:36,319 maybe is not as uh good as you might 781 00:36:32,240 --> 00:36:39,160 might think other also authors 782 00:36:36,319 --> 00:36:41,839 said that if one of the world's leading 783 00:36:39,160 --> 00:36:43,599 Specialists put forth his best effort to 784 00:36:41,839 --> 00:36:45,720 undermine the validity of the random 785 00:36:43,599 --> 00:36:48,119 Oracle assumption and if the flawed 786 00:36:45,720 --> 00:36:50,560 construction is the best he can do then 787 00:36:48,119 --> 00:36:53,640 perhaps there's more reason than ever to 788 00:36:50,560 --> 00:36:56,760 have confidence in the random Oracle 789 00:36:53,640 --> 00:36:59,680 model so you see that even in the 790 00:36:56,760 --> 00:37:01,839 scientific Community this model is uh 791 00:36:59,680 --> 00:37:05,359 it's not clear what what to do with it 792 00:37:01,839 --> 00:37:07,359 because it's widely used in proofs and 793 00:37:05,359 --> 00:37:10,960 there are schemes that can only be 794 00:37:07,359 --> 00:37:14,079 proven in the random Oracle model and 795 00:37:10,960 --> 00:37:17,400 they seem to be secure 796 00:37:14,079 --> 00:37:19,640 but obviously as you you saw the random 797 00:37:17,400 --> 00:37:21,880 Oracle model allows also to prove the 798 00:37:19,640 --> 00:37:25,599 security of insecure 799 00:37:21,880 --> 00:37:27,440 protocols so people try to get rid of 800 00:37:25,599 --> 00:37:30,240 it 801 00:37:27,440 --> 00:37:33,520 they invented uh signature schemes which 802 00:37:30,240 --> 00:37:36,280 don't use the random Oracle model but 803 00:37:33,520 --> 00:37:38,800 suddenly strange stuff 804 00:37:36,280 --> 00:37:41,720 appeared this duplicate signature key 805 00:37:38,800 --> 00:37:43,599 selection attack is an attack which is 806 00:37:41,720 --> 00:37:46,040 also out of model for the typical 807 00:37:43,599 --> 00:37:49,640 definition of the security of uh 808 00:37:46,040 --> 00:37:52,599 signature schemes and it allows that 809 00:37:49,640 --> 00:37:56,119 given a signature and the message under 810 00:37:52,599 --> 00:38:01,280 some public key you could be able to 811 00:37:56,119 --> 00:38:03,800 find a new key pair such that the 812 00:38:01,280 --> 00:38:06,319 signature is valid under your new 813 00:38:03,800 --> 00:38:09,640 generated key for the same 814 00:38:06,319 --> 00:38:13,960 message and maybe that's not a problem 815 00:38:09,640 --> 00:38:16,720 in your specific uh use case but you 816 00:38:13,960 --> 00:38:18,280 should really be aware that uh this 817 00:38:16,720 --> 00:38:20,839 could happen if you use this kind of 818 00:38:18,280 --> 00:38:20,839 sign 819 00:38:20,880 --> 00:38:27,520 signatures another example the bonen 820 00:38:24,920 --> 00:38:29,560 signatures uh were derived from another 821 00:38:27,520 --> 00:38:32,359 signature scheme but suddenly the 822 00:38:29,560 --> 00:38:35,160 signatures get much more complicated 823 00:38:32,359 --> 00:38:37,119 here in the easy one you have just one 824 00:38:35,160 --> 00:38:40,680 group element in the complex one you 825 00:38:37,119 --> 00:38:44,240 have two and the second one is quite 826 00:38:40,680 --> 00:38:46,640 difficult to calculate and the 827 00:38:44,240 --> 00:38:49,560 probability that a programmer will do 828 00:38:46,640 --> 00:38:52,720 some mistakes by implementing it is much 829 00:38:49,560 --> 00:38:55,800 higher than in the easy scheme and then 830 00:38:52,720 --> 00:38:57,440 the question is is this worth the effort 831 00:38:55,800 --> 00:39:00,480 do we want to have 832 00:38:57,440 --> 00:39:05,000 have schemes which are secure without 833 00:39:00,480 --> 00:39:07,599 using this unsound model or do we want 834 00:39:05,000 --> 00:39:11,280 to have the easy 835 00:39:07,599 --> 00:39:13,960 ones so you might have noticed that we 836 00:39:11,280 --> 00:39:17,599 get a little bit deeper in the beauty of 837 00:39:13,960 --> 00:39:20,000 proving brinar and for the next step 838 00:39:17,599 --> 00:39:23,240 I'll introduce another cryptographic 839 00:39:20,000 --> 00:39:26,280 tool which is called commitment 840 00:39:23,240 --> 00:39:28,000 schemes a commitment scheme works like 841 00:39:26,280 --> 00:39:30,880 this 842 00:39:28,000 --> 00:39:36,319 uh a party Alis has a message 843 00:39:30,880 --> 00:39:39,800 M and she wants to tell Bob that she 844 00:39:36,319 --> 00:39:42,280 knows that that she's choosing the 845 00:39:39,800 --> 00:39:45,319 message but not telling the message to 846 00:39:42,280 --> 00:39:48,040 Bob you can imagine it like uh having a 847 00:39:45,319 --> 00:39:50,800 save writing the message on a piece of 848 00:39:48,040 --> 00:39:56,000 paper put it into the save lock it and 849 00:39:50,800 --> 00:39:58,359 give the save to to Bob and if you tell 850 00:39:56,000 --> 00:40:01,119 Bob the the code for the save then he 851 00:39:58,359 --> 00:40:03,560 can open it and read the 852 00:40:01,119 --> 00:40:06,160 message for this scheme we have two 853 00:40:03,560 --> 00:40:08,200 messages the first one is called the 854 00:40:06,160 --> 00:40:10,440 commitment and it should have two 855 00:40:08,200 --> 00:40:13,280 properties it should be binding which 856 00:40:10,440 --> 00:40:16,040 means after sending the commitment Ellis 857 00:40:13,280 --> 00:40:19,000 should not be able to manipulate the 858 00:40:16,040 --> 00:40:21,800 message and it should be hiding which 859 00:40:19,000 --> 00:40:25,280 means that Bob should not should not 860 00:40:21,800 --> 00:40:27,560 learn anything about the message given 861 00:40:25,280 --> 00:40:30,560 the commitment 862 00:40:27,560 --> 00:40:31,960 and later Ellis can open this commitment 863 00:40:30,560 --> 00:40:35,160 which is called the 864 00:40:31,960 --> 00:40:37,920 unveil in this case she simply sends the 865 00:40:35,160 --> 00:40:39,960 message and the random and now Bob can 866 00:40:37,920 --> 00:40:43,040 calculate if this message and this 867 00:40:39,960 --> 00:40:45,319 random matches to the uh commitment 868 00:40:43,040 --> 00:40:45,319 given 869 00:40:45,800 --> 00:40:54,839 before well let's assume we have this 870 00:40:49,480 --> 00:40:57,319 secure scheme and we buil a more complex 871 00:40:54,839 --> 00:41:00,920 protocol let's assume assume that they 872 00:40:57,319 --> 00:41:02,839 both want to know if the message that 873 00:41:00,920 --> 00:41:04,599 they've chosen is larger than the 874 00:41:02,839 --> 00:41:08,599 message the other one has 875 00:41:04,599 --> 00:41:11,359 chosen Ellis commits on M and send the 876 00:41:08,599 --> 00:41:13,680 commitment to Bob Bob commits on another 877 00:41:11,359 --> 00:41:16,880 message and sends the commitment to 878 00:41:13,680 --> 00:41:20,800 Ellis and then they open the commitments 879 00:41:16,880 --> 00:41:23,640 and they see who wins the 880 00:41:20,800 --> 00:41:26,680 game but what happens if Alis is not 881 00:41:23,640 --> 00:41:29,800 interacting with Bob who's nice but with 882 00:41:26,680 --> 00:41:33,880 an evil party mallerie who acts like 883 00:41:29,800 --> 00:41:37,880 this mallerie takes the commitment C and 884 00:41:33,880 --> 00:41:41,040 multiplies it by the generator Ellis has 885 00:41:37,880 --> 00:41:44,040 used then when Ellis opens the 886 00:41:41,040 --> 00:41:48,200 commitment mallerie can simply open this 887 00:41:44,040 --> 00:41:51,119 message as a commitment on M 888 00:41:48,200 --> 00:41:54,920 plus1 that's not what we want to have 889 00:41:51,119 --> 00:41:57,079 using our commitment scheme so composing 890 00:41:54,920 --> 00:41:59,920 protocols together 891 00:41:57,079 --> 00:42:00,960 can make them insecure or can can lead 892 00:41:59,920 --> 00:42:02,560 to 893 00:42:00,960 --> 00:42:06,480 insecure 894 00:42:02,560 --> 00:42:11,319 protocols and what we want to have in a 895 00:42:06,480 --> 00:42:13,839 security definition is that the security 896 00:42:11,319 --> 00:42:16,880 definition should contain all imaginable 897 00:42:13,839 --> 00:42:18,560 properties and should be secure 898 00:42:16,880 --> 00:42:21,200 regardless of the context in which you 899 00:42:18,560 --> 00:42:25,240 use your uh 900 00:42:21,200 --> 00:42:28,359 primitive you see that using these uh 901 00:42:25,240 --> 00:42:30,520 locks for the like are not composable 902 00:42:28,359 --> 00:42:34,400 they're not even 903 00:42:30,520 --> 00:42:38,720 secure to do this we use this simulation 904 00:42:34,400 --> 00:42:42,599 based uh proofs and a special uh variant 905 00:42:38,720 --> 00:42:45,400 of it called the universal composability 906 00:42:42,599 --> 00:42:46,839 model here we have this ideal function 907 00:42:45,400 --> 00:42:50,280 floran mentioned 908 00:42:46,839 --> 00:42:55,800 before and we have the real protocol and 909 00:42:50,280 --> 00:42:57,000 we prove that um environment which is 910 00:42:55,800 --> 00:42:59,839 everything 911 00:42:57,000 --> 00:43:02,000 outside of the protocol all computers 912 00:42:59,839 --> 00:43:06,079 all protocols on the internet for 913 00:43:02,000 --> 00:43:08,760 example is unable to distinguish if it's 914 00:43:06,079 --> 00:43:12,040 interacting with the real world or with 915 00:43:08,760 --> 00:43:16,520 the ideal world so we have 916 00:43:12,040 --> 00:43:20,920 this uh sorry that's not an ideal 917 00:43:16,520 --> 00:43:24,000 functionality um this one um so we have 918 00:43:20,920 --> 00:43:28,240 here is Catholic so that's why it's 919 00:43:24,000 --> 00:43:31,800 trusty so we have this trustworthy 920 00:43:28,240 --> 00:43:35,240 Authority and the parties simply put 921 00:43:31,800 --> 00:43:36,640 their input to the trustworthy Authority 922 00:43:35,240 --> 00:43:39,440 and the 923 00:43:36,640 --> 00:43:42,400 authority calculates stuff and gives it 924 00:43:39,440 --> 00:43:44,760 back to the parties in the ideal 925 00:43:42,400 --> 00:43:47,880 scenario and in the real scenario we 926 00:43:44,760 --> 00:43:50,319 have the parties executing our 927 00:43:47,880 --> 00:43:52,440 protocol but we don't have only the 928 00:43:50,319 --> 00:43:55,720 parties but also an 929 00:43:52,440 --> 00:43:58,800 adversary who can for example listen to 930 00:43:55,720 --> 00:44:01,240 the message messages uh manipulate them 931 00:43:58,800 --> 00:44:03,720 or even corrupt 932 00:44:01,240 --> 00:44:05,079 parties and he interacts with the 933 00:44:03,720 --> 00:44:09,079 environment 934 00:44:05,079 --> 00:44:12,680 that so you can think about like the 935 00:44:09,079 --> 00:44:17,480 environment and the adversary are one 936 00:44:12,680 --> 00:44:21,000 party and uh they want to know if they 937 00:44:17,480 --> 00:44:23,559 are in the real scenario or in the ideal 938 00:44:21,000 --> 00:44:26,400 one in the ideal one you have a So-Cal 939 00:44:23,559 --> 00:44:28,839 simulator and he tries to con convince 940 00:44:26,400 --> 00:44:31,559 the environment that he is a real 941 00:44:28,839 --> 00:44:32,839 attacker but he is interacting with the 942 00:44:31,559 --> 00:44:36,480 ideal 943 00:44:32,839 --> 00:44:39,920 function which uh won't tell him too 944 00:44:36,480 --> 00:44:43,079 much on the messages the parties gave 945 00:44:39,920 --> 00:44:44,599 in and now we say that a scheme is 946 00:44:43,079 --> 00:44:47,240 secure 947 00:44:44,599 --> 00:44:50,599 if for every 948 00:44:47,240 --> 00:44:54,640 adversary there exists a simulator such 949 00:44:50,599 --> 00:44:59,920 that any environment is unable to 950 00:44:54,640 --> 00:45:02,800 distinguish uh in which world uh it 951 00:44:59,920 --> 00:45:04,640 lives how does such an Nal functionality 952 00:45:02,800 --> 00:45:08,520 look 953 00:45:04,640 --> 00:45:09,680 like we'll look at the uh functionality 954 00:45:08,520 --> 00:45:13,040 for 955 00:45:09,680 --> 00:45:15,559 commitments Alis can put the message in 956 00:45:13,040 --> 00:45:19,800 then the message uh the functionality 957 00:45:15,559 --> 00:45:24,520 tells Bob that Ellis has committed later 958 00:45:19,800 --> 00:45:27,960 Lis says unve it and then Bob gets the 959 00:45:24,520 --> 00:45:30,839 message so now now we'll try to prove 960 00:45:27,960 --> 00:45:33,160 such a system in this Universal 961 00:45:30,839 --> 00:45:35,720 composability 962 00:45:33,160 --> 00:45:39,559 scheme the environment using the 963 00:45:35,720 --> 00:45:41,319 attacker tells the corrupted Senter to 964 00:45:39,559 --> 00:45:44,640 use this 965 00:45:41,319 --> 00:45:49,559 commitment the corrupted Center uses 966 00:45:44,640 --> 00:45:53,880 this commitment later it he's told to 967 00:45:49,559 --> 00:45:55,880 unveil he unveils and then uh the 968 00:45:53,880 --> 00:45:57,640 receiver who is not corrupted can ask 969 00:45:55,880 --> 00:46:00,440 answer with the 970 00:45:57,640 --> 00:46:03,400 message in the ideal 971 00:46:00,440 --> 00:46:06,640 scenario the simulator is on the good 972 00:46:03,400 --> 00:46:08,400 side because he wants to confirm the en 973 00:46:06,640 --> 00:46:10,880 environment that he's in the real 974 00:46:08,400 --> 00:46:12,960 scenario and he works together with the 975 00:46:10,880 --> 00:46:15,520 corrupted 976 00:46:12,960 --> 00:46:19,800 party the environment tells the 977 00:46:15,520 --> 00:46:19,800 corrupted party to use this 978 00:46:19,880 --> 00:46:26,319 commitment it tries to uh send it to the 979 00:46:24,160 --> 00:46:28,760 uh ideal functionality and 980 00:46:26,319 --> 00:46:32,280 ideal functionality is confused because 981 00:46:28,760 --> 00:46:34,200 there is no definition of to give in a 982 00:46:32,280 --> 00:46:38,079 commitment but you want to have a 983 00:46:34,200 --> 00:46:41,800 message instead and you could try to 984 00:46:38,079 --> 00:46:45,160 extract the message from this 985 00:46:41,800 --> 00:46:46,960 commitment which should do the simulator 986 00:46:45,160 --> 00:46:50,720 but this would break the security 987 00:46:46,960 --> 00:46:54,800 definition of our commitment scheme so 988 00:46:50,720 --> 00:46:57,480 there can't be a commitment scheme which 989 00:46:54,800 --> 00:47:00,359 realizes this ideal 990 00:46:57,480 --> 00:47:02,800 functionality that's bad because we 991 00:47:00,359 --> 00:47:04,160 believe that there are secure uh 992 00:47:02,800 --> 00:47:08,280 commitment 993 00:47:04,160 --> 00:47:12,720 schemes so what's the reasonable and 994 00:47:08,280 --> 00:47:15,760 most clear solution for this of course 995 00:47:12,720 --> 00:47:18,079 we could introduce a back door uh sorry 996 00:47:15,760 --> 00:47:20,079 I mean uh we could introduce a common 997 00:47:18,079 --> 00:47:24,280 reference string a common reference 998 00:47:20,079 --> 00:47:27,000 string is a randomly choosen value by 999 00:47:24,280 --> 00:47:30,400 from a given distribution 1000 00:47:27,000 --> 00:47:32,800 it's choosen honestly but exists only in 1001 00:47:30,400 --> 00:47:32,800 the real 1002 00:47:34,960 --> 00:47:40,760 world so let's assume that our uh common 1003 00:47:38,839 --> 00:47:43,280 reference string in this case is a 1004 00:47:40,760 --> 00:47:48,920 public key and two 1005 00:47:43,280 --> 00:47:51,839 generators such that the uh public key 1006 00:47:48,920 --> 00:47:55,760 is chosen randomly and no one knows the 1007 00:47:51,839 --> 00:47:59,480 secret key now Ellis can uh use this 1008 00:47:55,760 --> 00:48:02,160 same commitment scheme as before for c0 1009 00:47:59,480 --> 00:48:05,880 she encrypts the message with the public 1010 00:48:02,160 --> 00:48:09,839 key where no one knows the secret key of 1011 00:48:05,880 --> 00:48:14,559 she proves with some magic cryptography 1012 00:48:09,839 --> 00:48:19,559 that the message in C1 and C2 is the 1013 00:48:14,559 --> 00:48:19,559 same and then she uses this as a 1014 00:48:21,520 --> 00:48:32,119 commitment the simulator 1015 00:48:24,520 --> 00:48:35,319 now uh uh can just uh take the uh common 1016 00:48:32,119 --> 00:48:37,680 reference string on its own but he's not 1017 00:48:35,319 --> 00:48:40,520 taking it from a given distrib 1018 00:48:37,680 --> 00:48:43,880 distribution randomly but instead he 1019 00:48:40,520 --> 00:48:47,000 uses uh a real uh key generation 1020 00:48:43,880 --> 00:48:49,640 algorithms so he knows the secret key 1021 00:48:47,000 --> 00:48:53,079 and he don't take random 1022 00:48:49,640 --> 00:48:56,520 generators but he chooses them in a way 1023 00:48:53,079 --> 00:49:01,880 such that he knows an X with g to the x 1024 00:48:56,520 --> 00:49:04,799 h and now he's able to extract the 1025 00:49:01,880 --> 00:49:08,000 message bit from the 1026 00:49:04,799 --> 00:49:11,839 commitment and put it into the ideal 1027 00:49:08,000 --> 00:49:14,400 functionality so in producing this uh 1028 00:49:11,839 --> 00:49:18,599 back I I mean introducing the common 1029 00:49:14,400 --> 00:49:21,200 reference string uh allows us to prove 1030 00:49:18,599 --> 00:49:21,200 this 1031 00:49:22,119 --> 00:49:30,599 CQR so maybe when the uh NSA gave us ecd 1032 00:49:27,440 --> 00:49:32,359 RBG they didn't want to Snoop on us but 1033 00:49:30,599 --> 00:49:35,160 maybe they just wanted to give us a tool 1034 00:49:32,359 --> 00:49:37,440 to provide extractability in UC 1035 00:49:35,160 --> 00:49:41,079 scenarios well maybe they probably they 1036 00:49:37,440 --> 00:49:43,200 wanted a snoop um as we said common 1037 00:49:41,079 --> 00:49:46,200 references strings are basically back 1038 00:49:43,200 --> 00:49:48,640 doors so it's quite hard to convince 1039 00:49:46,200 --> 00:49:50,799 people that they honestly 1040 00:49:48,640 --> 00:49:52,920 generated the probably most 1041 00:49:50,799 --> 00:49:55,599 sophisticated one where people actually 1042 00:49:52,920 --> 00:49:58,000 use complex com reference strings um 1043 00:49:55,599 --> 00:50:00,319 involves the cryptocurrency ccache where 1044 00:49:58,000 --> 00:50:03,280 they went through quite Great Lengths to 1045 00:50:00,319 --> 00:50:06,359 produce a common reference thing that is 1046 00:50:03,280 --> 00:50:07,160 plausibly honestly generated of course 1047 00:50:06,359 --> 00:50:09,000 it is 1048 00:50:07,160 --> 00:50:10,839 indistinguishable it must be 1049 00:50:09,000 --> 00:50:14,400 indistinguishable whether that's the 1050 00:50:10,839 --> 00:50:17,640 case um we did uh subtitle there is a 1051 00:50:14,400 --> 00:50:20,079 link if you download the uh slides uh 1052 00:50:17,640 --> 00:50:23,520 you can watch the video it's quite 1053 00:50:20,079 --> 00:50:25,680 interesting um in other scenarios uh 1054 00:50:23,520 --> 00:50:28,200 sometimes you might get away with 1055 00:50:25,680 --> 00:50:30,160 nothing up my sleeve numbers for example 1056 00:50:28,200 --> 00:50:33,079 the Monero guys will tell you that they 1057 00:50:30,160 --> 00:50:36,119 don't involve uh they don't they don't 1058 00:50:33,079 --> 00:50:38,359 use anything that uses a trusted setup 1059 00:50:36,119 --> 00:50:39,839 well they use Patterson commitments 1060 00:50:38,359 --> 00:50:42,799 which are the commitments that we 1061 00:50:39,839 --> 00:50:45,720 started out with and for them you still 1062 00:50:42,799 --> 00:50:48,000 um need some kind of plausibility that 1063 00:50:45,720 --> 00:50:51,160 nobody knows the discrete logarithm 1064 00:50:48,000 --> 00:50:54,720 between that G and that age and what 1065 00:50:51,160 --> 00:50:57,440 they did was basically they uh took uh 1066 00:50:54,720 --> 00:51:00,440 the element she G through uh through it 1067 00:50:57,440 --> 00:51:03,839 through sha 3 and use the output as the 1068 00:51:00,440 --> 00:51:06,440 other uh group element and that is 1069 00:51:03,839 --> 00:51:08,440 indeed quite plausible that it's secure 1070 00:51:06,440 --> 00:51:12,440 but still it is a kind of common 1071 00:51:08,440 --> 00:51:14,520 reference string now all that being said 1072 00:51:12,440 --> 00:51:16,960 let's come to the conclusions the first 1073 00:51:14,520 --> 00:51:19,280 one as always for these kinds of talks 1074 00:51:16,960 --> 00:51:20,920 please don't roll your own crypto it's 1075 00:51:19,280 --> 00:51:25,040 extremely likely that you will get it 1076 00:51:20,920 --> 00:51:29,240 wrong we um skipped over several details 1077 00:51:25,040 --> 00:51:31,920 here and even if you implement manage to 1078 00:51:29,240 --> 00:51:33,599 implement um a scheme in a secure way 1079 00:51:31,920 --> 00:51:34,960 for some security definition it's still 1080 00:51:33,599 --> 00:51:37,040 doesn't mean that your security 1081 00:51:34,960 --> 00:51:40,799 definition is what you might 1082 00:51:37,040 --> 00:51:43,079 want um other than that security is 1083 00:51:40,799 --> 00:51:46,839 difficult if you do it please at least 1084 00:51:43,079 --> 00:51:50,280 employ proofs and be aware of their 1085 00:51:46,839 --> 00:51:54,920 limitations also um the random Oro model 1086 00:51:50,280 --> 00:51:56,760 may be a flaw um framework but no scheme 1087 00:51:54,920 --> 00:51:59,160 no real world scheme that has been 1088 00:51:56,760 --> 00:52:01,240 proven secure in it has ever been broken 1089 00:51:59,160 --> 00:52:03,359 because of the random ARA model so a 1090 00:52:01,240 --> 00:52:07,520 good euristic is a lot better than 1091 00:52:03,359 --> 00:52:09,440 nothing so at least use that and if your 1092 00:52:07,520 --> 00:52:12,799 proofs are too complicated for other 1093 00:52:09,440 --> 00:52:14,839 people to read they are not all uh that 1094 00:52:12,799 --> 00:52:18,640 much worse that's the big problem with 1095 00:52:14,839 --> 00:52:21,520 UC proofs they are so complicated that 1096 00:52:18,640 --> 00:52:23,960 often nobody really reads them and they 1097 00:52:21,520 --> 00:52:26,280 are arguably therefore less uh 1098 00:52:23,960 --> 00:52:29,319 convincing than random Oracle model 1099 00:52:26,280 --> 00:52:32,319 proofs because those tend to be simple 1100 00:52:29,319 --> 00:52:34,960 enough for people to understand with all 1101 00:52:32,319 --> 00:52:36,559 that being said we are now here for some 1102 00:52:34,960 --> 00:52:37,220 questions and thank you very much for 1103 00:52:36,559 --> 00:52:39,290 your 1104 00:52:37,220 --> 00:52:44,440 [Applause] 1105 00:52:39,290 --> 00:52:46,520 [Music] 1106 00:52:44,440 --> 00:52:49,280 attention thank you very much for this 1107 00:52:46,520 --> 00:52:51,839 most excellent talk we have microphones 1108 00:52:49,280 --> 00:52:54,119 in the S here so please line up behind 1109 00:52:51,839 --> 00:52:57,240 them and to start it off we have a 1110 00:52:54,119 --> 00:52:57,240 question from the internet 1111 00:52:57,280 --> 00:53:04,799 okay and can you elaborate why there is 1112 00:53:00,280 --> 00:53:09,760 such such much conference in ddh 1113 00:53:04,799 --> 00:53:12,280 assumptions yeah um the first thing is 1114 00:53:09,760 --> 00:53:15,200 it's very people spend a lot of time 1115 00:53:12,280 --> 00:53:17,520 looking at it and assumptions usually uh 1116 00:53:15,200 --> 00:53:20,520 stem from the idea that if we looked at 1117 00:53:17,520 --> 00:53:22,839 it for a very long time and nobody found 1118 00:53:20,520 --> 00:53:26,440 an attack there's a good chance that is 1119 00:53:22,839 --> 00:53:30,040 secure there's also a different argument 1120 00:53:26,440 --> 00:53:34,000 um there is something called the um 1121 00:53:30,040 --> 00:53:37,559 generic group model and it uh formalizes 1122 00:53:34,000 --> 00:53:40,680 the notion of those mathematical um 1123 00:53:37,559 --> 00:53:43,079 Concepts that are used I only showed you 1124 00:53:40,680 --> 00:53:46,079 um the a very technical definition of 1125 00:53:43,079 --> 00:53:48,359 the alal scheme there is actually a way 1126 00:53:46,079 --> 00:53:50,599 to view it in terms of group Theory and 1127 00:53:48,359 --> 00:53:52,440 if you do that it Al it becomes much 1128 00:53:50,599 --> 00:53:56,240 simpler but you require the previous 1129 00:53:52,440 --> 00:53:59,720 knowledge and you see how you can 1130 00:53:56,240 --> 00:54:02,640 um map it to this generic group model 1131 00:53:59,720 --> 00:54:04,520 and the generic group model allows you 1132 00:54:02,640 --> 00:54:06,920 to prove that there are no generic 1133 00:54:04,520 --> 00:54:11,599 attacks that only use the structure of 1134 00:54:06,920 --> 00:54:13,200 the group and there is a proof that um 1135 00:54:11,599 --> 00:54:15,799 in the generic group model the 1136 00:54:13,200 --> 00:54:17,960 decisional defy Helman assumption holds 1137 00:54:15,799 --> 00:54:21,720 but that doesn't mean that there are no 1138 00:54:17,960 --> 00:54:24,680 attacks on it that use non-generic uh 1139 00:54:21,720 --> 00:54:26,640 properties of the group for example the 1140 00:54:24,680 --> 00:54:28,839 reason we want use elliptic curves is 1141 00:54:26,640 --> 00:54:32,079 that we believe that they are mostly 1142 00:54:28,839 --> 00:54:35,480 equivalent to generic groups and the 1143 00:54:32,079 --> 00:54:37,920 reason we need so huge uh groups for if 1144 00:54:35,480 --> 00:54:40,599 you want to use regular prime numbers is 1145 00:54:37,920 --> 00:54:43,839 that they have more structure than that 1146 00:54:40,599 --> 00:54:45,440 so it's a very good argument but it's of 1147 00:54:43,839 --> 00:54:47,440 course not perfect and also if you get 1148 00:54:45,440 --> 00:54:50,040 quantum computers all bets are off uh 1149 00:54:47,440 --> 00:54:53,280 that's completely broken in that case 1150 00:54:50,040 --> 00:54:56,160 microphone number two please hey 1151 00:54:53,280 --> 00:54:58,319 thanks um my question is is do you think 1152 00:54:56,160 --> 00:55:02,160 doing a proof in the random Oracle wle 1153 00:54:58,319 --> 00:55:04,960 is helpful in constructing um a proof 1154 00:55:02,160 --> 00:55:07,119 that can later be Advanced to remove the 1155 00:55:04,960 --> 00:55:09,240 random Oracle model and does this 1156 00:55:07,119 --> 00:55:11,720 usually happen in your 1157 00:55:09,240 --> 00:55:15,280 experience well 1158 00:55:11,720 --> 00:55:17,480 yes often you start by approving your 1159 00:55:15,280 --> 00:55:19,880 scheme in the random Oracle model and 1160 00:55:17,480 --> 00:55:22,000 then try to get rid of 1161 00:55:19,880 --> 00:55:24,760 it but 1162 00:55:22,000 --> 00:55:25,839 this you saw the results yes you saw the 1163 00:55:24,760 --> 00:55:29,480 result 1164 00:55:25,839 --> 00:55:31,440 uh often you need to uh change stuff in 1165 00:55:29,480 --> 00:55:33,559 your protocol uh to get rid of the 1166 00:55:31,440 --> 00:55:36,400 random Oracle model and this leads to 1167 00:55:33,559 --> 00:55:39,119 complicated constructions uh which are 1168 00:55:36,400 --> 00:55:41,680 difficult to implement and may introduce 1169 00:55:39,119 --> 00:55:41,680 strange 1170 00:55:44,520 --> 00:55:49,119 properties does that answer your 1171 00:55:46,280 --> 00:55:52,920 question yes then microphone to again 1172 00:55:49,119 --> 00:55:56,640 please what's on the next 1173 00:55:52,920 --> 00:55:59,119 slide okay that's the bonus slide um a 1174 00:55:56,640 --> 00:56:01,440 little bit on security levels um if you 1175 00:55:59,119 --> 00:56:04,559 want I can tell um I believe we have 1176 00:56:01,440 --> 00:56:08,640 some time left there is four more 1177 00:56:04,559 --> 00:56:11,240 minutes okay that's uh is enough um 1178 00:56:08,640 --> 00:56:14,559 there is this uh you occasionally count 1179 00:56:11,240 --> 00:56:16,760 the uh encounter the idea that there 1180 00:56:14,559 --> 00:56:19,200 that some security level is enough or 1181 00:56:16,760 --> 00:56:21,880 insufficient or whatever and the first 1182 00:56:19,200 --> 00:56:23,760 thing uh that is maybe not that trivial 1183 00:56:21,880 --> 00:56:26,520 is that there are fundamentally 1184 00:56:23,760 --> 00:56:29,240 different kinds of Security even for the 1185 00:56:26,520 --> 00:56:31,319 same definition the one that most people 1186 00:56:29,240 --> 00:56:34,000 think about is called computational 1187 00:56:31,319 --> 00:56:36,599 security and what that means is 1188 00:56:34,000 --> 00:56:39,119 basically if I give the attacker a 1189 00:56:36,599 --> 00:56:40,839 certain amount of computational power 1190 00:56:39,119 --> 00:56:43,559 the attacker shouldn't be able to break 1191 00:56:40,839 --> 00:56:47,000 my scheme using brute force and that's 1192 00:56:43,559 --> 00:56:49,880 where you um where this 128 bit comes 1193 00:56:47,000 --> 00:56:52,359 from which is a level where the energy 1194 00:56:49,880 --> 00:56:54,520 if you use somewhat realistic 1195 00:56:52,359 --> 00:56:55,960 assumptions on Hardware the Pure Energy 1196 00:56:54,520 --> 00:56:57,720 conern Assumption of going through that 1197 00:56:55,960 --> 00:57:01,160 many steps is I believe enough to boil 1198 00:56:57,720 --> 00:57:05,000 the oceans so 128 bits on itself is 1199 00:57:01,160 --> 00:57:07,160 pretty much sufficient there are also um 1200 00:57:05,000 --> 00:57:10,520 certain schemes that provide statistical 1201 00:57:07,160 --> 00:57:14,280 security which is in a way much better 1202 00:57:10,520 --> 00:57:16,280 because in that case the question is not 1203 00:57:14,280 --> 00:57:18,680 how much computational power does the 1204 00:57:16,280 --> 00:57:22,079 adversary have but just how much luck 1205 00:57:18,680 --> 00:57:24,079 does he have and if you think about it 1206 00:57:22,079 --> 00:57:28,160 um computational Power has to factor 1207 00:57:24,079 --> 00:57:31,359 that in if you um have a one in a 1208 00:57:28,160 --> 00:57:36,480 thousand chance to um brute force a 1209 00:57:31,359 --> 00:57:38,680 certain key using 2 Tod 128 operations 1210 00:57:36,480 --> 00:57:42,960 you still have to factor in that factor 1211 00:57:38,680 --> 00:57:45,359 of one in a thousand you um so the 1212 00:57:42,960 --> 00:57:48,440 statistical security uh parameters can 1213 00:57:45,359 --> 00:57:52,039 be much smaller and if you read 40 bits 1214 00:57:48,440 --> 00:57:54,280 of statistical security that's not great 1215 00:57:52,039 --> 00:57:55,480 but it's not as terrible as it may sound 1216 00:57:54,280 --> 00:57:58,079 at first 1217 00:57:55,480 --> 00:58:01,160 and finally there's perfect security 1218 00:57:58,079 --> 00:58:03,000 which is even if you give all 1219 00:58:01,160 --> 00:58:06,160 computational power of the world and 1220 00:58:03,000 --> 00:58:08,079 then a lot more to the attacker and if 1221 00:58:06,160 --> 00:58:10,880 the attacker has perfect luck he still 1222 00:58:08,079 --> 00:58:12,359 isn't able to break it the most popular 1223 00:58:10,880 --> 00:58:17,119 scheme that provides that is of course 1224 00:58:12,359 --> 00:58:19,079 the onetime pad where for every um 1225 00:58:17,119 --> 00:58:20,720 possible blame text there is a key that 1226 00:58:19,079 --> 00:58:23,160 will encrypt the cipher text to the 1227 00:58:20,720 --> 00:58:25,680 plane text those are completely 1228 00:58:23,160 --> 00:58:29,200 impossible to break and as such there is 1229 00:58:25,680 --> 00:58:31,599 no security parameter yeah I think we 1230 00:58:29,200 --> 00:58:34,400 might be able to take one last question 1231 00:58:31,599 --> 00:58:37,960 do we have another question from the 1232 00:58:34,400 --> 00:58:41,480 internet no no question from here well 1233 00:58:37,960 --> 00:58:44,949 then a warm Round of Applause for Lucas 1234 00:58:41,480 --> 00:58:44,949 [Applause] 1235 00:58:45,230 --> 00:58:52,409 [Music] 1236 00:58:53,720 --> 00:59:04,280 and 1237 00:58:56,610 --> 00:59:07,280 [Music] 1238 00:59:04,280 --> 00:59:07,280 a