1 00:00:00,490 --> 00:00:04,130 So now, we just finish talking about basic confidentiality using simple Caesar 2 00:00:04,130 --> 00:00:06,828 cipher. And we'll get better before, we'll be 3 00:00:06,828 --> 00:00:10,312 more sophisticated than that because Caesar ciphers are trivially breakable, 4 00:00:10,312 --> 00:00:13,263 obviously. But now, we're going to switch from 5 00:00:13,263 --> 00:00:18,030 confidentiality integrity. And we're worried about the, the message, 6 00:00:18,030 --> 00:00:23,077 just to review, that confidentiality means we're hiding information. 7 00:00:23,077 --> 00:00:27,562 We just don't want Eve to see it because Eve sees the, the cipher text and we want 8 00:00:27,562 --> 00:00:32,400 her to never be able to extract the plain text. 9 00:00:32,400 --> 00:00:36,096 And as we say in the last lecture you, if I'm just using a Caesar cipher, I mean 10 00:00:36,096 --> 00:00:40,920 there was little or nothing I could do to stop you from doing it. 11 00:00:40,920 --> 00:00:43,325 All you do is enough work and you would figure out the shift, and then you'd have 12 00:00:43,325 --> 00:00:47,258 everything. So it would take you, you know, you write 13 00:00:47,258 --> 00:00:49,880 a program, it would take you like a thousandth of a second to check all 14 00:00:49,880 --> 00:00:54,930 possible things and you're done. So, that's confidentiality. 15 00:00:54,930 --> 00:00:56,980 Now, we're going to talk about integrity, right? 16 00:00:56,980 --> 00:01:00,510 And we're going to kind of assume confidentiality. 17 00:01:00,510 --> 00:01:03,324 Or perhaps assume it's not necessary, because we're transporting it in a locked 18 00:01:03,324 --> 00:01:05,240 box. Or in a, in a, whatever. 19 00:01:05,240 --> 00:01:10,615 But let's just say I had some some, some piece of paper, right? 20 00:01:10,615 --> 00:01:15,790 And, and you'd wanted to know if this piece of paper really came from me. 21 00:01:15,790 --> 00:01:20,490 Well, we would use things like a signature, right? 22 00:01:20,490 --> 00:01:24,714 Or we would use a bit of wax where we would push the our seal on it and the 23 00:01:24,714 --> 00:01:30,252 seal only belonged to us. But, but really did signatures can be 24 00:01:30,252 --> 00:01:35,105 forged you know, people can steal the wax imprint thing. 25 00:01:35,105 --> 00:01:38,615 I mean, in Roman times, they would wear it around their neck to make sure that no 26 00:01:38,615 --> 00:01:42,056 one stole it. But you could also just create a fake one 27 00:01:42,056 --> 00:01:46,640 so you could seal your letter with the wax but, and you break the wax seal. 28 00:01:46,640 --> 00:01:50,575 but in the computer world, we need something, right? 29 00:01:50,575 --> 00:01:54,775 We need a situation where where perhaps, I mean, my wife had to get a, a 30 00:01:54,775 --> 00:01:58,840 prescription. And they sent her an email with a 31 00:01:58,840 --> 00:02:02,087 prescription in it. And this prescription had on the end of 32 00:02:02,087 --> 00:02:05,390 it a digital signature, was just a bunch of numbers. 33 00:02:05,390 --> 00:02:08,836 And you think to yourself wow, you know, here's this prescription. 34 00:02:08,836 --> 00:02:12,216 And at the end it, just has a bunch of numbers, and that's the digital signature 35 00:02:12,216 --> 00:02:16,174 from the doctor. And how does that owrk? 36 00:02:16,174 --> 00:02:21,358 Well, it works surprisingly well. And, and that message can be forwarded, 37 00:02:21,358 --> 00:02:28,080 she can print it out, she can scan it, she can send it to a pharmacist by email. 38 00:02:28,080 --> 00:02:31,525 As long as that signature is in there, we can know that the data originally came 39 00:02:31,525 --> 00:02:35,256 from the doctor. And that, that you didn't, no one 40 00:02:35,256 --> 00:02:38,020 modified it to be a different kind of prescription. 41 00:02:38,020 --> 00:02:41,375 Like a different amount or a different drug. 42 00:02:41,375 --> 00:02:43,840 And, and the, that would invalidate the signature. 43 00:02:43,840 --> 00:02:47,918 And how exactly is that done? Well, it's done using a technique called 44 00:02:47,918 --> 00:02:53,312 Cryptographic Hashing. And it is a bit of computer software, a 45 00:02:53,312 --> 00:02:58,560 bit of code, that takes a large amount of text and reduces it down to some small 46 00:02:58,560 --> 00:03:04,300 set of numbers. A large block of data to a fixed 47 00:03:04,300 --> 00:03:09,790 length-set of numbers. And, and the message is the big thing. 48 00:03:09,790 --> 00:03:13,692 And the digest is the little thing. It sort of, it's like it digests it and 49 00:03:13,692 --> 00:03:18,580 sort of gives you this little tiny thing. Now the, the key is there are many 50 00:03:18,580 --> 00:03:24,730 different techniques to, to map from a message to the hash or the digest. 51 00:03:24,730 --> 00:03:28,139 And some are better than others. And it turns out that there is a long 52 00:03:28,139 --> 00:03:32,541 term whole field of mathematics and computer science that's dedicated to 53 00:03:32,541 --> 00:03:37,864 understanding what a good Cryptographic Hash might be. 54 00:03:37,864 --> 00:03:41,309 And so, there are, there are these well-known cryptographic hashes like, you 55 00:03:41,309 --> 00:03:45,938 may have heard of like SHA1 or MD5. Each of those is the result of many many 56 00:03:45,938 --> 00:03:51,750 years of research, of thinking through what a good cryptographic hash is. 57 00:03:51,750 --> 00:03:55,593 So, for example, one cryptographic hash might be I sign it with the number of 58 00:03:55,593 --> 00:03:59,404 characters in the message. That might be something that says like, 59 00:03:59,404 --> 00:04:01,836 well, at least they didn't expand or contract the number of characters in the 60 00:04:01,836 --> 00:04:04,590 message. But then at some point, that would be 61 00:04:04,590 --> 00:04:08,140 such an obvious thing, that you would change the signature as well. 62 00:04:08,140 --> 00:04:10,548 So, you want to make it so you can't change the message and change the 63 00:04:10,548 --> 00:04:14,250 signature, because then you're sort of properly forging a signature. 64 00:04:14,250 --> 00:04:18,581 So, the hash function that takes the message to create the digest, that's 65 00:04:18,581 --> 00:04:22,912 something that is a scientific, mathematical research effort to get the 66 00:04:22,912 --> 00:04:29,580 thing right, okay? So, here is an example of a hash 67 00:04:29,580 --> 00:04:33,456 function. Now, this hash function takes as message 68 00:04:33,456 --> 00:04:38,006 input on one side, right? It takes message input of and this is can 69 00:04:38,006 --> 00:04:41,240 be short medium or extremely long messages. 70 00:04:41,240 --> 00:04:46,640 And the digest is always a fixed size. It's always a fixed size, right? 71 00:04:46,640 --> 00:04:50,856 Some get longer than others different message hashing functions give different 72 00:04:50,856 --> 00:04:55,646 lengths, but they're all fixed. And they're fixed even if the input is 73 00:04:55,646 --> 00:04:58,192 megabytes. It can be megabytes, hundreds of 74 00:04:58,192 --> 00:05:01,133 megabytes. And you can still run all of that through 75 00:05:01,133 --> 00:05:04,430 the hash function and get a, a digest, okay? 76 00:05:04,430 --> 00:05:10,408 And so the key thing is, is to make it so that for any change in the input, the 77 00:05:10,408 --> 00:05:16,740 digest also changes, okay? And so, here we have the red fox jumps 78 00:05:16,740 --> 00:05:21,060 over the blue dog, right? And that's the hash that comes out. 79 00:05:21,060 --> 00:05:24,823 And if we change one letter, you know, the v to u, the hash changes 80 00:05:24,823 --> 00:05:29,267 dramatically. So this suggest this is a good crypt to 81 00:05:29,267 --> 00:05:34,120 graphic hash function, right? The length didn't change. 82 00:05:34,120 --> 00:05:38,064 All the characters are the same, but one character changed, and the hash function 83 00:05:38,064 --> 00:05:42,478 changes completely, okay? And here is another flipping of 84 00:05:42,478 --> 00:05:46,436 characters, right? Where the, from here to here, let's get a 85 00:05:46,436 --> 00:05:50,052 better color here. Which color is that? 86 00:05:50,052 --> 00:05:56,600 from here to here, the v and the e were just toggled. 87 00:05:56,600 --> 00:06:00,110 And yet, from here to here, the hash function is completely different. 88 00:06:00,110 --> 00:06:03,465 And so, the hash function needs to generate quite different hashes, even 89 00:06:03,465 --> 00:06:08,235 with tiny perturbations of the input. You're not even allowed to change one 90 00:06:08,235 --> 00:06:12,394 character or add or remove a character. And they know a cryptographic hash 91 00:06:12,394 --> 00:06:15,866 function is bad if they can take two different messages and send it through 92 00:06:15,866 --> 00:06:20,400 and get the same digest. And so, there's a lot of research to try 93 00:06:20,400 --> 00:06:23,182 to as soon as they come up with one of these things. 94 00:06:23,182 --> 00:06:26,062 There is a massive amount of research to try to disprove it, to say that's a bad 95 00:06:26,062 --> 00:06:29,742 one. And the bad one is if two different 96 00:06:29,742 --> 00:06:35,433 messages come in and they come out with the same hash function, then that's bad. 97 00:06:35,433 --> 00:06:39,401 Because it means that it's provably that the signature could use, the same 98 00:06:39,401 --> 00:06:44,620 signature could be used to sign two different input messages, okay? 99 00:06:44,620 --> 00:06:49,060 So, this hash function is a bit of computer code, right? 100 00:06:49,060 --> 00:06:56,920 And, you know, SHA1, you can go look on Wikipedia for SHA1, or MD5. 101 00:06:56,920 --> 00:07:01,034 These are kind of classic hash functions. And when you read the SHA1 or MD5 102 00:07:01,034 --> 00:07:04,816 Wikipedia, they'll talk about the fact that it's been decided it's kind of 103 00:07:04,816 --> 00:07:09,210 flawed. And so there's like SHA1, don't use it. 104 00:07:09,210 --> 00:07:11,079 It's not cool. Now you can use it for less critical 105 00:07:11,079 --> 00:07:14,038 things, you just have to be aware of what it's limitations are. 106 00:07:14,038 --> 00:07:19,703 So, SHA256 is better than SHA1. So, what happens is there's continuous 107 00:07:19,703 --> 00:07:22,865 research and there's continuous improvement in the mathematics of these 108 00:07:22,865 --> 00:07:26,231 hashing functions. And they're getting really good at it 109 00:07:26,231 --> 00:07:30,200 because we've been using these things from very, very, very long time. 110 00:07:31,359 --> 00:07:34,460 Now, if you want to play ooh, let me clear this up. 111 00:07:34,460 --> 00:07:39,920 So I've got a simple Sha1 calculator and you can, you'll be using this in 112 00:07:39,920 --> 00:07:45,439 homework. the SHA1 calculator takes as input, some 113 00:07:45,439 --> 00:07:52,140 kind of a plain text, and it produces output when you hit the thing. 114 00:07:52,140 --> 00:07:57,658 So, you can put in pony or fluffy, or whatever, or even a whole bunch of stuff 115 00:07:57,658 --> 00:08:03,691 and it produces a SHA1, okay? So basically, get ready to use this 116 00:08:03,691 --> 00:08:08,046 because the next upcoming exercises are going to use this. 117 00:08:08,046 --> 00:08:11,610 And you can reach SHA1, about SHA1 on Wikipedia. 118 00:08:11,610 --> 00:08:15,200 And you can find out like yes, scene is less than perfect. 119 00:08:15,200 --> 00:08:19,328 And you should use SHA256 or whatever. But actually, lots of applications in 120 00:08:19,328 --> 00:08:23,108 less than critical situations know that, you know, for short and reasonably length 121 00:08:23,108 --> 00:08:27,520 strings, you know, the flaws are mathematically found. 122 00:08:27,520 --> 00:08:31,544 But, they're not commonly run into. So, SHA1 is not horrible, has just been 123 00:08:31,544 --> 00:08:36,900 proven, sort of less than ideal. And so for highly sensitive information, 124 00:08:36,900 --> 00:08:41,990 you would never use SHA1. But for simple things SHA1, even things 125 00:08:41,990 --> 00:08:46,940 like MD5 are commonly used. Like for hashing passwords, so no hashing 126 00:08:46,940 --> 00:08:50,230 passwords. So, the first application of this that 127 00:08:50,230 --> 00:08:54,850 we're going to talk about is hashing passwords. 128 00:08:54,850 --> 00:08:58,322 So, you go to a new site, even coursera.org, and it asks you to create 129 00:08:58,322 --> 00:09:01,670 an account. Create a password. 130 00:09:01,670 --> 00:09:05,630 Now, you're not supposed to, but lots of people use the same password for lots of 131 00:09:05,630 --> 00:09:09,750 systems. And so, if your Coursera password were 132 00:09:09,750 --> 00:09:14,810 somehow mistakenly revealed, they might get your LinkedIn password as well. 133 00:09:14,810 --> 00:09:20,762 And so it is considered very bad form, very, very bad form to actually ever 134 00:09:20,762 --> 00:09:27,790 store your password in the Coursera database in plain text. 135 00:09:27,790 --> 00:09:31,694 Because if the database was somehow compromised, then all the bad guys would 136 00:09:31,694 --> 00:09:36,615 get all of the plain text passwords. And again, maybe use them not just on 137 00:09:36,615 --> 00:09:40,214 Coursera, because you can change your password on Coursera, but use them on 138 00:09:40,214 --> 00:09:45,774 LinkedIn and Twitter, and whatever. And YouTube and steal all your accounts 139 00:09:45,774 --> 00:09:50,045 by compromising one account. Because you made the mistake that lots of 140 00:09:50,045 --> 00:09:54,719 people do, of using the same password in a lot of different places. 141 00:09:54,719 --> 00:09:58,390 because we're tired of making up a new password for each place. 142 00:09:58,390 --> 00:10:02,560 So, you're not allowed to store the plain text password in the database. 143 00:10:02,560 --> 00:10:05,160 That's bad practice and we don't want to do that. 144 00:10:05,160 --> 00:10:09,460 So, the best practice is to store a hashed version of it. 145 00:10:09,460 --> 00:10:13,108 To run, take the plain text of the password when you're creating your 146 00:10:13,108 --> 00:10:18,442 account, run a cryptographic hash on it, store the cryptographic hash. 147 00:10:18,442 --> 00:10:22,154 And then when you log in next, you present to the system your plain text 148 00:10:22,154 --> 00:10:25,623 password. And it runs your presented password 149 00:10:25,623 --> 00:10:29,477 through a cryptographic hash, same cryptographic hash. 150 00:10:29,477 --> 00:10:33,530 And then, compares it with the hashed password in the database. 151 00:10:33,530 --> 00:10:38,160 If they match you must've presented the same plain text both times. 152 00:10:38,160 --> 00:10:42,768 This is a way that they can verify that you've represented the same plain text 153 00:10:42,768 --> 00:10:47,740 again without them ever storing the plain text, okay? 154 00:10:47,740 --> 00:10:51,710 That's why a respectable system will never send you your password. 155 00:10:51,710 --> 00:10:55,670 It's I've almost started doing this where I as soon as I go to a new system and I 156 00:10:55,670 --> 00:10:59,654 set my password. I set it to crap, and then I have them 157 00:10:59,654 --> 00:11:04,804 send me a message to reset my password. And if they send me the actual plain text 158 00:11:04,804 --> 00:11:09,670 of the password, it's like, [SOUND] and I use some crap password. 159 00:11:09,670 --> 00:11:13,880 I've actually got to the point where I'm tired of reusing my passwords. 160 00:11:13,880 --> 00:11:16,794 And my technique, I don't know if it's a good one or bad one, is I just put crap 161 00:11:16,794 --> 00:11:19,942 in for my password. And then every time I use the system, I 162 00:11:19,942 --> 00:11:22,652 have it send me a new password, or reset the password. 163 00:11:22,652 --> 00:11:25,938 I mean, I really think we should just change it so that when you log in it just 164 00:11:25,938 --> 00:11:31,381 comes to your email and you click a link. I don't know, I'm no an expert on this 165 00:11:31,381 --> 00:11:34,808 stuff, you know? So, but a respectable computing system 166 00:11:34,808 --> 00:11:37,784 will never, ever, ever send you your plain text password becaue they don't 167 00:11:37,784 --> 00:11:40,844 possess it. And they can't derive it, these 168 00:11:40,844 --> 00:11:44,750 cryptograph hashes are not backwards. You can't make them go backwards. 169 00:11:44,750 --> 00:11:47,990 Let's go back here. They're only a a one way hash. 170 00:11:47,990 --> 00:11:52,510 Because this might be one megabyte of data, and this might be, well let's see. 171 00:11:52,510 --> 00:11:56,800 Four times, this is 40 characters, 40 character of data, one megabyte squeezes 172 00:11:56,800 --> 00:12:01,051 down to forty characters. There is no way to go backwards, the 173 00:12:01,051 --> 00:12:05,856 information is lost. The hashes, you know, distinct and 174 00:12:05,856 --> 00:12:08,660 unique, right? But you cannot go backwards. 175 00:12:08,660 --> 00:12:11,267 It's a one way operation. You can go from the frame text to the 176 00:12:11,267 --> 00:12:14,019 hash, but you can't go from the hash to the plain text, which is very different 177 00:12:14,019 --> 00:12:18,600 than encryption and decryption, right? In decryption, you had to be able to pull 178 00:12:18,600 --> 00:12:21,890 plain text back out from the encrypted text. 179 00:12:21,890 --> 00:12:25,555 This is not encryption. This is calculating a special digest that 180 00:12:25,555 --> 00:12:29,172 is uniquely connected to the plain text message. 181 00:12:29,172 --> 00:12:34,410 But you need to run the pain text through the hash again and then compare, okay? 182 00:12:35,700 --> 00:12:39,920 So, let's do some homework. Well, so, no. 183 00:12:39,920 --> 00:12:43,007 Let me, let me, let me, let me first show you the, how this works in the hash 184 00:12:43,007 --> 00:12:47,189 passwords. So, so let's say for example, you're 185 00:12:47,189 --> 00:12:51,410 logging into coursera.org and creating a profile for the first time, and it says 186 00:12:51,410 --> 00:12:56,777 please give me your password. And you choose a singularly bad password 187 00:12:56,777 --> 00:13:01,195 as fluffy, okay? So fluffy, and you can type, go type 188 00:13:01,195 --> 00:13:05,680 fluffy into drchuck.com/sha1.php in another window. 189 00:13:05,680 --> 00:13:09,740 If you type fluffy and you encrypt it with SHA1, you get this as the hash 190 00:13:09,740 --> 00:13:14,368 password. And then, this is what they store in 191 00:13:14,368 --> 00:13:17,940 Coursera's database. And so that is, rhey don't know. 192 00:13:17,940 --> 00:13:20,230 They never store fluffy. They, they would not do that. 193 00:13:20,230 --> 00:13:23,590 That would be so bad if they did that. So, they started this. 194 00:13:23,590 --> 00:13:27,478 And if I get this, it's very difficult reverse engineer it to fluffy. 195 00:13:27,478 --> 00:13:31,300 It is also even harder if you make your password long. 196 00:13:31,300 --> 00:13:35,392 Best passwords are like sentences not just eight characters, but they're like 197 00:13:35,392 --> 00:13:40,890 long sentences of stuff that's rather difficult to predict. 198 00:13:40,890 --> 00:13:44,842 So, this is what's stored in the Coursera databases. 199 00:13:44,842 --> 00:13:50,780 Some ugly string which is a cryptographic hash digest of your password. 200 00:13:50,780 --> 00:13:55,096 So, you now, log out and this is gone. That's only in your mind and this is 201 00:13:55,096 --> 00:13:59,732 sitting in the database. So you log in, you log back in the 202 00:13:59,732 --> 00:14:04,010 Coursera and you forget your password, so you type in pony. 203 00:14:06,140 --> 00:14:13,012 If you run pony to SHA1, you get this as the cryptographic hash of the word pony. 204 00:14:13,012 --> 00:14:19,460 And you look and you compare and you go nope, that is not the right password. 205 00:14:19,460 --> 00:14:22,507 I don't know what the right password is, I can't give you a hint. 206 00:14:22,507 --> 00:14:25,313 I can't tell you hey, you, you put shift on your password, why don't you try 207 00:14:25,313 --> 00:14:29,015 taking that off? You know, you seem to have Caps lock on 208 00:14:29,015 --> 00:14:32,935 because it doesn't know what your password is, but it does know that pony 209 00:14:32,935 --> 00:14:38,057 is not your password. Then, what it does, right? 210 00:14:38,057 --> 00:14:41,450 So, this is what's stored in the database. 211 00:14:41,450 --> 00:14:44,364 Then you go, oh my secretary, that's right, I used fluffy for my password on 212 00:14:44,364 --> 00:14:47,802 Coursera. So then Coursera runs that through SHA1, 213 00:14:47,802 --> 00:14:52,691 it gets the cryptographic hash of the plain text that you entered. 214 00:14:52,691 --> 00:14:55,941 And then, it compares it to what it has stored as the cryptograph, as the plain, 215 00:14:55,941 --> 00:14:59,570 as the as your hash password. And it matches. 216 00:14:59,570 --> 00:15:03,060 So then it says, yehey, I'll let you back in. 217 00:15:03,060 --> 00:15:07,036 The fluffy only existed in your mind. Unless you foolishly like wrote it on a 218 00:15:07,036 --> 00:15:10,360 Post it Note, and stuck it up on your computer, which you shouldn't do as well. 219 00:15:10,360 --> 00:15:16,490 But whatever it was, Coursera never stored it, right? 220 00:15:16,490 --> 00:15:18,600 Coursera never stored it. Coursera only stored this. 221 00:15:18,600 --> 00:15:22,754 And that again is why Cursera can never tell you what your password is or any 222 00:15:22,754 --> 00:15:27,710 resonable site can never tell you what your password is. 223 00:15:27,710 --> 00:15:31,920 It can only tell you, it can only let you change it again. 224 00:15:31,920 --> 00:15:34,644 Which is easy. Changing again you just decides oh, it 225 00:15:34,644 --> 00:15:38,125 sends you mail, you give it a new password and recomputes a SHA1 for that 226 00:15:38,125 --> 00:15:43,118 one and stores that SHA1. You have to get password resets to 227 00:15:43,118 --> 00:15:46,651 happen, okay? Okay, so the next thing that I want to 228 00:15:46,651 --> 00:15:51,010 talk about is I want to talk about digital signatures. 229 00:15:51,010 --> 00:15:54,070 How we can use this for message integrity? 230 00:15:54,070 --> 00:15:57,020 So, we've got the notion of a cryptographic cache, which is a 231 00:15:57,020 --> 00:16:02,460 calculation takes a large block of text. So far, we've only used it on small 232 00:16:02,460 --> 00:16:06,290 blocks of text, okay? But now, we're going to use it on larger 233 00:16:06,290 --> 00:16:10,565 blocks of text where we're going to ensure message integrity. 234 00:16:10,565 --> 00:16:14,345 Which means we're going to figure out if this message actually came from the 235 00:16:14,345 --> 00:16:20,190 person we think that it came from, okay? So, we're going to use integrity now. 236 00:16:20,190 --> 00:16:23,326 I mean, in a sense, what the system was doing when you were typing in a password 237 00:16:23,326 --> 00:16:26,511 was it was insuring that you were really the person on the other end of the line, 238 00:16:26,511 --> 00:16:30,050 right? Hi, I'm logging in as Dr. 239 00:16:30,050 --> 00:16:35,109 Chuck and here's my password, fluffly. By giving you the password, I'm proving 240 00:16:35,109 --> 00:16:37,830 that to Coursera that I'm really Dr. Chuck. 241 00:16:37,830 --> 00:16:41,947 So, that's a form of integrity, right? identification is a form of integrity, 242 00:16:41,947 --> 00:16:43,710 right? It's no different than showing your 243 00:16:43,710 --> 00:16:46,157 driver's license. It says yes, this is really me. 244 00:16:46,157 --> 00:16:50,330 Okay, but now we're going to do it in a way that we're going to send a message. 245 00:16:50,330 --> 00:16:52,888 So, it's not just a password. We're not really solving just the 246 00:16:52,888 --> 00:16:55,694 password problem, but we're actually going to use it to make sure that the 247 00:16:55,694 --> 00:17:01,150 message, A, came from the right person. And B, was not modified in transit. 248 00:17:01,150 --> 00:17:04,129 This is kind of the doctor signing the prescription digitally. 249 00:17:04,129 --> 00:17:07,345 And then, sending you an email with your prescription that you can just print the 250 00:17:07,345 --> 00:17:12,060 email and take it, take it to your take it to your pharmacist. 251 00:17:12,060 --> 00:17:15,922 So again, message integrity. When you get a message, did it come from, 252 00:17:15,922 --> 00:17:18,662 who did it come from? And do you, did it come from who you 253 00:17:18,662 --> 00:17:22,225 really thought it came from? Or was it altered in transit? 254 00:17:22,225 --> 00:17:28,264 Okay, so if you go back to our little example from A Christmas Story the 255 00:17:28,264 --> 00:17:36,048 message from Annie was eat more Ovaltine. Now, the question really becomes, did it 256 00:17:36,048 --> 00:17:40,229 really come from Annie, right? because little orphan Annie didn't 257 00:17:40,229 --> 00:17:44,130 necessarily say it. Little orphan Annie's handed the message 258 00:17:44,130 --> 00:17:49,615 to somebody else and then they read it. So, did that person change the message? 259 00:17:49,615 --> 00:17:53,773 because maybe there was actually a secret message from Annie, and maybe Annie wrote 260 00:17:53,773 --> 00:17:57,926 it, and it really was an important secret message. 261 00:17:57,926 --> 00:18:01,708 But then, somebody like the advertiser changed it and sent it to you as if it 262 00:18:01,708 --> 00:18:06,322 had came from Annie. So the, we're not really worried so much 263 00:18:06,322 --> 00:18:10,809 now about the plaint text, that is the fine plain text. 264 00:18:10,809 --> 00:18:15,149 The question is, did it really come form little orphan Annie because we are 265 00:18:15,149 --> 00:18:21,230 receiving this from an insecure media? Like Annie is out here somewhere but 266 00:18:21,230 --> 00:18:24,282 Annie handed it to somebody and handed it to somebody. 267 00:18:24,282 --> 00:18:27,920 Handed it to somebody that sent it across radio, yadda yadda yadda. 268 00:18:27,920 --> 00:18:32,260 The question is, did the message originally come from Annie long, long ago 269 00:18:32,260 --> 00:18:37,579 handed through many people or not? This is again like the seal that you put 270 00:18:37,579 --> 00:18:41,914 on with the lax. Did it really come from that person or 271 00:18:41,914 --> 00:18:45,015 not? Is it really Annie, just saying, yeah 272 00:18:45,015 --> 00:18:47,090 this is Annie? That's too easy. 273 00:18:47,090 --> 00:18:52,350 You can say less Ovaltine or maybe Annie wanted to say I hate Ovaltine, right? 274 00:18:52,350 --> 00:18:56,445 That's, might be what, but we don't know if Annie said eat more Ovaltine or not, 275 00:18:56,445 --> 00:18:59,410 right? Because what we saw was eat more Ovaltine 276 00:18:59,410 --> 00:19:04,410 and seen the scene that come from Annie. We got to know that came from Annie or 277 00:19:04,410 --> 00:19:09,596 not, okay? So, simple message signing using shared 278 00:19:09,596 --> 00:19:12,405 secret. And we'll, we'll move to a better 279 00:19:12,405 --> 00:19:14,734 technique later. But we're going to start with a simple 280 00:19:14,734 --> 00:19:17,800 technique of shared secret. Is that we have a shared secret, that 281 00:19:17,800 --> 00:19:25,332 we're going to use for message signing. It'll probably be different than the 282 00:19:25,332 --> 00:19:30,043 cryptic, encryption secret, okay? So now, we get together with Annie in a 283 00:19:30,043 --> 00:19:33,306 shared room. And she tells us what the shift is going 284 00:19:33,306 --> 00:19:36,592 to be, and then she tells us what our shared signature secret is going to be, 285 00:19:36,592 --> 00:19:42,701 and then we separate. So, the technique that you do is, before 286 00:19:42,701 --> 00:19:48,171 we send the message, we can concatenate the secret to the message, right? 287 00:19:48,171 --> 00:19:53,090 So, eat more Ovaltine, and then put the secret on the end of the message. 288 00:19:53,090 --> 00:19:57,055 And then, you compute the digest of the message, plus the secret concatenated 289 00:19:57,055 --> 00:20:01,030 together. Then, you remove the secret from the 290 00:20:01,030 --> 00:20:06,213 message, and then you send the message plus the digest across the insecure. 291 00:20:06,213 --> 00:20:10,308 And in my wife's example, this was the little signature numbers that came from 292 00:20:10,308 --> 00:20:14,590 her doctor, was the digest. But it was the digest, not just of the 293 00:20:14,590 --> 00:20:17,010 message, but of the message plus the secret. 294 00:20:18,400 --> 00:20:21,830 The secret didn't come across the message plus the digest came across. 295 00:20:21,830 --> 00:20:27,220 So, let's look at this when we look at how, when we receive a message. 296 00:20:27,220 --> 00:20:30,630 So, we receive a message and we see a digest at the end of the message and it's 297 00:20:30,630 --> 00:20:35,058 across an insecure transport. So, we take the digest off the message, 298 00:20:35,058 --> 00:20:40,310 take the digest off the message, and we add the secret back on the message. 299 00:20:40,310 --> 00:20:42,852 We know the secret, Annie knows the secret, but the people in the middle who 300 00:20:42,852 --> 00:20:45,920 transported the message do not know the secret. 301 00:20:45,920 --> 00:20:49,495 So it's finally arrived in our location, we see the digest, we pull that off and 302 00:20:49,495 --> 00:20:52,790 hold on to it. We add the secret to it. 303 00:20:52,790 --> 00:20:57,870 We can take the concatenated message plus secret, we run it through SHA1. 304 00:20:57,870 --> 00:21:03,287 We get a digest locally. And then we compare that digest to the 305 00:21:03,287 --> 00:21:08,432 received digest. And the only way to make the digest match 306 00:21:08,432 --> 00:21:12,098 is to know the secret. Now, maybe somebody like made Annie tell 307 00:21:12,098 --> 00:21:15,855 them the secret, which means they can forge the messages. 308 00:21:15,855 --> 00:21:20,170 But, if the secret is not been compromised somehow. 309 00:21:20,170 --> 00:21:24,820 The only way to create the digest is to know the secret, right? 310 00:21:24,820 --> 00:21:28,106 And so, we can compare the received digest to the known other the, the, the, 311 00:21:28,106 --> 00:21:32,520 the known digest that we Compute on our end in a secure way. 312 00:21:32,520 --> 00:21:36,046 Because we and Annie are the only ones in possession of the secret. 313 00:21:36,046 --> 00:21:40,066 So, here we go. So, you can play with this on sha1.php, 314 00:21:40,066 --> 00:21:41,295 Dr. Chuck. 315 00:21:41,295 --> 00:21:45,366 And so, if the message is that Annie wants us to send, or Annie wants us to 316 00:21:45,366 --> 00:21:50,050 get is eat more Ovaltine, and the secret is Santa. 317 00:21:50,050 --> 00:21:54,760 So what the, what you do is you take the message. 318 00:21:54,760 --> 00:21:58,603 Concatenate the secret, and then run that through SHA1. 319 00:21:58,603 --> 00:22:02,751 This is all happening in, in Annie's secure room, and she comes up with a, a 320 00:22:02,751 --> 00:22:06,390 digest. Now, I'm not, there's, it;s longer than 321 00:22:06,390 --> 00:22:10,046 this but that's just a first 6 characters of it. 322 00:22:10,046 --> 00:22:14,820 And then, what she does is she removes the secret and then concatenates the 323 00:22:14,820 --> 00:22:18,370 digest, okay? And that's what gets sent across the 324 00:22:18,370 --> 00:22:20,990 insecure medium. It could be many steps, could be many 325 00:22:20,990 --> 00:22:25,350 people, it could be on paper, it could be Morse code, it could be phone call. 326 00:22:25,350 --> 00:22:29,420 Who knows, radio, but we, we just, this is the danger, right? 327 00:22:29,420 --> 00:22:34,295 This is, we do not know if the message is harmed in anyway as it moves across this 328 00:22:34,295 --> 00:22:40,252 medium, okay? So then, what we do is we receive the 329 00:22:40,252 --> 00:22:44,062 message, right? We don't know if it's a good message or a 330 00:22:44,062 --> 00:22:47,234 bad message. So, we see that it's a message and it has 331 00:22:47,234 --> 00:22:52,060 a digest on the end of the message and we split that out. 332 00:22:52,060 --> 00:22:56,801 We split the digest out and we hold onto the digest separately, okay? 333 00:22:56,801 --> 00:22:59,810 And now, we have the message minus the digest. 334 00:22:59,810 --> 00:23:03,409 And so, then what we do is we add the secret back on because only Annie and us 335 00:23:03,409 --> 00:23:08,004 know the secret, right? And, [COUGH] Annie and us know the 336 00:23:08,004 --> 00:23:13,661 secret, we all know how to do SHA1. Ad so, we take this message and we run it 337 00:23:13,661 --> 00:23:17,060 through SHA1. And we get a digest that we've computed 338 00:23:17,060 --> 00:23:19,917 locally. This is the receive digest, that's the 339 00:23:19,917 --> 00:23:24,750 local digest. And then we compare and we say this is 340 00:23:24,750 --> 00:23:28,113 great. That must've came from manning. 341 00:23:28,113 --> 00:23:31,399 And we know that it came from manning even if it came through a dangerous set 342 00:23:31,399 --> 00:23:34,495 of steps. And we can't trust any of the people that 343 00:23:34,495 --> 00:23:37,650 transported the message. We, they're all untrustworthy. 344 00:23:37,650 --> 00:23:41,603 But we know that no matter what happened, that originally, at that moment, Annie 345 00:23:41,603 --> 00:23:45,738 did this, okay? Annie made this digest because without 346 00:23:45,738 --> 00:23:52,710 knowing the word Santa, there is nothing. And this could be like megabytes of data. 347 00:23:52,710 --> 00:23:55,220 And this is a real tiny, you know, 40 character thing here. 348 00:23:55,220 --> 00:23:58,960 The digest is small, the message is large. 349 00:23:58,960 --> 00:24:03,440 So, you can't go backwards to get it. There's no backwards here. 350 00:24:03,440 --> 00:24:07,890 Now, if you can steal the secret from Annie, then all bets are off, of course. 351 00:24:07,890 --> 00:24:10,760 So we, we have to assume that Annie's okay. 352 00:24:10,760 --> 00:24:14,120 And that, you know, Annie was not compromised like in James Bond movies, 353 00:24:14,120 --> 00:24:19,447 for example. Where I was trying to get the secret from 354 00:24:19,447 --> 00:24:23,450 the good guy, okay? So, let's go and do this again, right? 355 00:24:23,450 --> 00:24:29,110 So, here we go. We want to send the Eat More Ovaltine. 356 00:24:29,110 --> 00:24:33,709 And the secret Santa. And so, we do the same thing, and we end 357 00:24:33,709 --> 00:24:38,740 up with, end up with that. And then she concatenates it. 358 00:24:38,740 --> 00:24:42,220 And this is all done, you know, in Annie's bedroom, in secret thing. 359 00:24:42,220 --> 00:24:48,540 And then she sends it, okay? She sends it to us, but a diabolical, 360 00:24:48,540 --> 00:24:55,602 diabolical courier says, I have a thing about Ovaltine, and I'm going to change 361 00:24:55,602 --> 00:25:01,132 the more to less. So, I'm going to change this message to 362 00:25:01,132 --> 00:25:09,243 be eat less Ovaltine, right? So eat less Ovaltine, bad, evil. 363 00:25:09,243 --> 00:25:14,611 [SOUND] I don't know how to draw evil. I'm a terrible artist, van't draw evil. 364 00:25:14,611 --> 00:25:20,131 so some untrusted courier has changed the word more to less. 365 00:25:20,131 --> 00:25:24,490 So we see the thing that says, and we don't know, right? 366 00:25:24,490 --> 00:25:27,650 We didn't see the courier that was carrying a box. 367 00:25:27,650 --> 00:25:29,760 Who knows what they did, but they changed it. 368 00:25:29,760 --> 00:25:32,817 And they gave us a new copy. So, we received this message from a 369 00:25:32,817 --> 00:25:36,250 untrusted medium. There's our untrusted medium. 370 00:25:36,250 --> 00:25:39,305 And it is our job to decide if it really came from Annie or not. 371 00:25:39,305 --> 00:25:43,940 So, [COUGH] what we do is just like we did before. 372 00:25:43,940 --> 00:25:47,768 We break the message and the digest into pieces, and then we add the known secret 373 00:25:47,768 --> 00:25:52,267 to the end of it, all right? So, we've added the known secret to the 374 00:25:52,267 --> 00:25:55,960 end of it right here. Now, we run it through the SHA1 375 00:25:55,960 --> 00:26:00,845 calculation. And you can take, here we go. 376 00:26:00,845 --> 00:26:05,750 There we go. And go ahead and try this if you want. 377 00:26:05,750 --> 00:26:09,172 Maybe you have this up in a separate window, sha1.php. 378 00:26:09,172 --> 00:26:13,072 Put less Ovaltine Santa in, and you'll get a different signature because you 379 00:26:13,072 --> 00:26:18,770 change even a single character, and SHA1 will give us a different digest. 380 00:26:18,770 --> 00:26:21,452 That's cryptographic hashes in action, right? 381 00:26:21,452 --> 00:26:27,890 Even the tiniest change in megabytes of data will change the cryptographic hash. 382 00:26:27,890 --> 00:26:31,920 That's the beauty of SHA1, MD5 and, you know SHA256 and the others. 383 00:26:31,920 --> 00:26:36,032 There is no match. So, we know that this message did not, 384 00:26:36,032 --> 00:26:41,500 either did not come from Annie or was modified in transit. 385 00:26:41,500 --> 00:26:48,466 So we can tell the difference, and we do not have to trust the medium, right? 386 00:26:48,466 --> 00:26:53,040 Okay, so let's see what we've got coming up next here, okay? 387 00:26:53,040 --> 00:26:58,957 [COUGH] So, here is the encryption technique, and let's just stop and let 388 00:26:58,957 --> 00:27:09,328 you do one of these on your own. And say that we've got two messages from 389 00:27:09,328 --> 00:27:14,960 Annie. And I want you to stop and I want you to 390 00:27:14,960 --> 00:27:19,929 calculate, Santa is the, Santa is the secret, okay? 391 00:27:19,929 --> 00:27:23,635 Santa is the secret. And I want you to tell me if free cookies 392 00:27:23,635 --> 00:27:27,670 or free candy actually came from Annie or not. 393 00:27:27,670 --> 00:27:31,534 One of them is a valid message from Annie, and the other is not a valid 394 00:27:31,534 --> 00:27:36,574 message from Annie, okay? So, I want you to take a moment, use the 395 00:27:36,574 --> 00:27:40,314 SHA1 calculator. And I want you to try and figure out 396 00:27:40,314 --> 00:27:44,864 which of these is valid, and wihch of these is not valid. 397 00:27:44,864 --> 00:27:52,424 Give you a minute. Okay, one last chance before we do the 398 00:27:52,424 --> 00:27:58,130 reveal. Okay, here we go. 399 00:27:58,130 --> 00:28:05,720 So, here comes the message from insecure medium, free cookies, with that as the 400 00:28:05,720 --> 00:28:11,960 message digest. We, and we got the other one, free candy. 401 00:28:11,960 --> 00:28:17,006 With that as the message digest. So, what we do is we take an, take off 402 00:28:17,006 --> 00:28:22,640 the digest and add the word Santa to each one. 403 00:28:22,640 --> 00:28:30,020 And then we run the SHA1 on each one. And then we get the two SHA1s. 404 00:28:30,020 --> 00:28:35,082 Here's the one and here's the two. And then what we do, most importantly, is 405 00:28:35,082 --> 00:28:41,196 we compare them with the received SHA1. And when you compare them with the 406 00:28:41,196 --> 00:28:44,730 received SHA1 or the received the message digest, or the received message 407 00:28:44,730 --> 00:28:49,480 signature, you see right away that one is good and one is bad. 408 00:28:49,480 --> 00:28:53,644 It's as simple as that, right? One of these is good, and one of these is 409 00:28:53,644 --> 00:28:57,414 bad. So digital signatures are, are actually 410 00:28:57,414 --> 00:29:01,135 really surprisingly simple, and surprisingly easy to do without a lot of 411 00:29:01,135 --> 00:29:05,558 complex technology. The only complex technology in here is 412 00:29:05,558 --> 00:29:08,841 really the, the clever mathematics that makes these cryptographic hashes work 413 00:29:08,841 --> 00:29:13,580 effectively. It the simple concatenation of a secret. 414 00:29:13,580 --> 00:29:16,604 Now, you want your secrets to be kind of longer than this and more random than 415 00:29:16,604 --> 00:29:19,442 that. But ultimately, the notion of a digital 416 00:29:19,442 --> 00:29:23,114 signature is actually a simple and, and rather elegant and beautiful notion that 417 00:29:23,114 --> 00:29:26,300 really leverages this notion of cryptographic caches in a really cool 418 00:29:26,300 --> 00:29:30,967 manner. So, that kind of sums up our first half 419 00:29:30,967 --> 00:29:36,102 lecture, where we really talk more about the techniques of both integrity and 420 00:29:36,102 --> 00:29:41,402 confidentiality. But we've done it all with share, a 421 00:29:41,402 --> 00:29:45,143 secret key, right? Where we have the same key, we have a 422 00:29:45,143 --> 00:29:50,220 moment where we're together in a secure manner, and we exchange the code book. 423 00:29:50,220 --> 00:29:54,173 Whether it's Annie or, or the Caesar, or whatever where we know what the shift is, 424 00:29:54,173 --> 00:29:57,825 right? So, every pair of communicating people or 425 00:29:57,825 --> 00:30:02,398 systems needs a, a key. Now, in the internet, with everybody 426 00:30:02,398 --> 00:30:07,170 buying from everybody else and using credit cards, it's just not practical. 427 00:30:07,170 --> 00:30:10,824 You just could not have a secret key for Amazon, I guess it kind of works with a 428 00:30:10,824 --> 00:30:14,171 password. Now that's dif, we'll get to that in a 429 00:30:14,171 --> 00:30:16,506 second. The password doesn't solve everything 430 00:30:16,506 --> 00:30:20,740 because then you would have to actually visit Amazon to get your password set up. 431 00:30:20,740 --> 00:30:24,634 And so, the problem is, is that you, you, you, we have to use an insecure medium to 432 00:30:24,634 --> 00:30:31,340 establish the first secret as it were. And so, it just was never going to work. 433 00:30:31,340 --> 00:30:34,221 So, we need a different approach for the internet, and that's what we're going to 434 00:30:34,221 --> 00:30:38,060 talk about in the next lecture, okay? See you then.