SHA2 Fatal Flaw? (Hash Length Extension Attack) - Computerphile

Key Takeaways

One of the reasons that SHA 3 exists other than it's nice to have a backup is it specifically addresses this problem of length extension attacks which is something that's you know an attack that you can leverage on things like SHA 2 uh and MD5 but not on SHA 3. Let's just very quickly remind ourselves about roughly the kind of the way a hash function works and the way that SHA 3 and SHA 2 differ, right? And and I'm going to skip over all you know the complexities of how they differ. So remember what you've got, what you're trying to do is you're trying to calculate a summary of a document or a digital file. And so you're putting bits of digital file into your hash function, jumbling them up, and then at the end you read out your hash, right? And that can have loads of uses, including in something called authentication, right? Which is this idea of is the is the message I just received over the internet internet a legitimate message or did someone else write it, right? Or change it. So, you know, let's imagine you have um you know, some kind of initial state, which we're going to call hn because that's what they call it in uh in char 2. And we're going to take our first block of message and we're going to put these in to our hash function, which compresses them down. And this is where our round function goes. And this is not dissimilar to how SHA 3 works. >> So, when you say round function, that's cuz there will be more than one round. >> Yes. Yeah. You have some amount of jumbling of bits and then you repeat that some number of times, right? So in SH 3 it was 24 times. And then what we do is we take this state which is now H1. Uh there we go. And we put it through again. And we put in the next block of message. And then we repeat this again. And we put in the next block of message. You know, I can't I can't make them all the same shape and size. I mean, that would be too much to ask, right? So this is H1, H2, and so on. Now, let's imagine you only have three blocks of message. Then you're you're done. This is your hash. So this is the hash of the message. Now in char three, I had to remember which one I was talking about. You have some other information here which I'm going to sort of pretend is kind of joined on the side. This is completely different to the diagram I drew in the last video. So don't go back and compare. Um and this is what we call the capacity. And this is hidden data that interacts with your state but isn't output at the end. >> But it's secret, isn't it? >> It's secret. That's important. So it means that if I wanted to know what this state was, I can only know what this bit is, which is this. I can't see what this bit is, right? And that's relevant to our length extension attack. In SHA 2, we have no such capacity. So this isn't there. This isn't there. This isn't there. It's just this standard thing. And that means if you read the hash out of SHA 2, you're actually reading the output of this bit here, here, right? which if you had more blocks of message are what you would use as input to those blocks. All right, so let's now think about a time where we might use a hash function and then we can start to see why this could be a problem, right? Cuz actually this doesn't seem like a big problem, right? Yeah, I mean we know what this is, but that's because we have everyone sees the hash, who cares, right? Well, actually this could cause a problem, right? So let's have a look. One common way to send a message over the internet is to authenticate it, right? So what we don't want to happen if you think about the internet I send you a message someone you know on a router or some other machine in between our two endpoints could alter that message and so it's very very common in fact it's basically ubiquitous now to send a message with some kind of authentication code put on the end of it and what that says is this hasn't been tampered with this was actually sent from Mike you know using the key that you both know and so on one way of doing this is something called a message authentication code. And we also did a video on a HMAC, which is a better version of this. And then we calculate our hash. So let's look at a message authentication code. Let's suppose good old Alice here is sending a message to Bob. And the message she's sending is just this sort of encrypted message, this cipher text. She wants Bob to know when he receives a message that this cipher text is from Alice and it hasn't been changed. So what she does is she takes their secret key, which they must have because they've produced some cipher text, right? or maybe they derive that some other way. She appends it to the cipher text, right, by just sticking them together. So now it's just a longer message and then hashes this using a hash function and then sticks that on the end as a tag. So the actual message that Alice sends is the cipher text with a hash of the key and the cipher text together at the end. >> So it's like the proof. >> Yeah, it is a proof. It's like a kind of signature except it's not using public key cryptography. It's a symmetric version. Only Bob knows this key as well as Alice. So when Bob receives this, what he does is he takes this, he appends his key to it. So this is Bob's key. Uh that's not a K, that's a H. Uh this is Bob's key. And he appends it to this to the message and calculates that hash. And then he checks that these two things are the same. And they should be because they both got the same key. He's got the same cipher text. And that will tell him two things. It will tell him first that it came from Alice because they're the only two people that have this key. And it will also say that no one's fiddled around with this because if someone had changed this this N to a one in somewhere in this message, that would no longer match. >> Oh, because the hash would be different. >> The hash would be different. And so that is also a check that says, okay, no one's tampered with the message even if they can't read it. Why is this a problem for SH 2, right? And this is what this is a length extension attack. The length extension attack is is this idea that if someone has a key, you know what what what's confused me is I put the blue lid on the black and so it confused me every time I uh every time I Anyway, it doesn't matter. Um they have a key appended to our message and they hash this and they send that as verification that they were the legitimate signer of this message or the legitimate sender of this message. What we can do with a length extension attack is make this message longer and be able to calculate this the correct hash for it without knowing what the key is. As an attacker, we receive the message. We receive the hash of the key and the message which we cannot reverse because the hash looks random. And we can calculate a message with extra data. Let's just call it X, right? And we can also calculate the hash of the key and the message and X. And that is a big problem, right? It's a problem because we can't change the message, but we can add to it. So we might re you know we might say forget all that stuff, do something different, right? And that could be a problem on internet. So let's let's use an example. Let's imagine we're sending a bank transaction. Right? Now I can't tell you exactly the structure of a bank transaction sent over the internet. That's privy, you know, bank information. However, you might imagine it has like a from field and it has a two field. So these will be sort of numbers 105. So that's you know account number 105 to account number,7 and the amount will be I don't know £10, right? Something like that, right? And you and you stick this into a data structure and then using your keyed hash you calculate an authentication code on this so that people can't fiddle with this during transit, right? Then what happens when you you send it over to the next bank is they also have the key and they verify that this hasn't been tampered with and that act of doing that says okay this is a legitimate transaction we're allowed to send it and that's fine. Now instead let's imagine so this is bank B and this is bank A. Let's imagine that we intercept this message and we kind of redirect it to ourselves right and let's imagine that we we can't alter this message. All we can do is append to it. We can extend it. So all we're going to do is extend with something like we're going to take the original message and we're also going to append amount 1,000. All right. So we're just going to add amount a th00and onto the end of it. Now that might crash the bank because they might say we've given two amounts and we don't know which one's the correct one or they might have programmed it wrong and it just takes whichever val the second one was right which is pretty common if you're writing a for loop right of parsing. And so what you're doing is you're write you're finding some data that goes on the end of your normal transaction but in some way changes or you know wrecks this message and does something you don't want to be doing. So we have to make an assumption that the banks have not quite coded their you know their system properly and they will accept this. But if you can calculate a valid hash for this so that's the key appended to this appended to this then this bank will accept that transaction and send the bigger amount of money. And this is possible in SHA 2 because if we go back to our message here, the hash of the key and the message is here. This is no longer the hash of the message. This is the hash of the key appended to the message. Right? So we take this hash and we resume the char 2 function at this point. We don't need the key which went in here. The key went in here. >> That's the fundamental weakness here is that the key goes in at the beginning. You don't need it again. Is that right? >> You don't need it again because the hash is resumed. So you know the idea of of this message authentication code is you put the key in and then you put you know bank bank transaction transaction n and transaction one. So that's like the two parts of the transaction. Let's just for the sake of simplicity assume that it splits nicely into three parts. It's a little bit more complicated than that. We can then calculate transaction three and kind of stick it in here and do some more hashing. Right? And then we get a hash of the key plus the message plus our attack. That's the idea. So SH 2 allows you to resume hashing at a midway point based on an existing hash, which is really not what you should be able to do. Hmat doesn't let you do this because it hashes two times to mask this process. SH 3 doesn't let you do this because you have these extra capacities which we can't guess. So we don't have all of the information we need to put into this function, right? But char 2 and a char one family of hash functions are vulnerable to this. And this is one reason why you know you might choose to use char 3. The reason it's slightly more complicated is that part of the char 2 algorithm any hash function is padding. Right? We can't put in any size of message here. What we have to do is split the message into blocks of the right size. And if t1 is too short we add some padding. So we might say plus padding here. Right? And so actually what we're going to do if we go back to here is we're going to have to simulate that padding because there's going to be some padding that we've got added that we can't predict. We have to add in what the padding would have been then resume from there to add our attack. This is the kind of thing that would work on a system where assumptions have been made about what was secure and given those assumptions they'd cause themselves a real problem. In practice, you use an HMAC or you verify that your transaction has a certain format or you do both of those things and that would make it much much harder to pull off. For quite a while, I thought of Brilliant as a great resource for learning about mathematics and traditional science. But more and more I'm being blown away by all the coding, computer, and AI related content on there. Just take a look at some of this. It's so visual. It's interactive. It's a great way to learn. This is a fun workout for your brain. It makes you smarter. And with so much of the future heading in this direction, Brilliance courses and content could be the first step on your own career path or at the very least give you a better understanding of what's going on around you. To learn for free on Brilliant, go to brilliant.org/computile. Scan the QR code on screen or click on the links below. Brilliant also giving our viewers 20% off an annual premium subscription which gives you unlimited daily access to everything. Our thanks to them for supporting this episode. So I thought we'd cover that today and I've actually implemented one up so we can have a look at it. So I've taken a working copy of SH 256 and I've edited it so that rather than just hashing from the start, I can also resume hashing at a certain point. Right? So what I'm essentially doing, if we look at my picture,