4 ms·

Reasoning by Lego: The wrong way to think about cryptography

32 points by ColinWright 6y ago

barbegal 6y ago
The author takes the following statement to be incorrect: > I had written code for a constant-time text comparison of the MAC but then realized that this is not an issue when using the MAC-then-encrypt method because the MAC is only compared after decryption to verify that the data is intact and the same as when it was encrypted. Since the correct MAC is only exposed when the correct encryption key is used it doesn’t matter whether the text comparison is done in constant-time or not. Changing to an encrypt-then-MAC method (requiring a constant-time MAC comparison) would not be backwards compatible with the current version. I don't see anything wrong with this statement. With encrypt-then-MAC the application is going to calculate the MAC on the ciphertext then compare it against the MAC included with the ciphertext. If the two match then the application will decrypt the ciphertext into plaintext. If the attacker doesn't actually know the encryption key then the data will be garbled but that might not matter for certain attacks. The key to the attack is getting the MAC correct and to do that timing attacks on the comparison can be done. But in this case we are using MAC-then-encrypt. The application is going to decrypt the ciphertext to produce plaintext and MAC. Every time the attacker changes the ciphertext both the MAC and the plaintext will change unpredictably. Even with the timing leak, the attacker can't do anything with the ciphertext to make it such that the MAC verifies the plaintext One of the key flaws of modern security protocols is making them robust to bad implementations and side channels. I don't see the problem as being reasoning by Lego but rather in neglecting that the information you wish to protect is not just in the ciphertext, it can leak out into everything, the length of the message, padding, MAC, timing...
- Nursie 6y ago
  > If the attacker doesn't actually know the encryption key then the data will be garbled That depends on exactly what sort of cipher scheme is used. I don't know what exact scheme we're talking about here (it wasn't described in the post and I didn't go hunting any further) but there are stream constructions where if you change a bit in the ciphertext, it changes a corresponding bit in the plaintext that comes out. This is because in these modes the keystream is independent of the data and the ciphertext is the result of XORing the keystream with the plaintext. The plaintext is unrecoverable without the key, but what's decoded can be manipulated, even without knowing what it is. Mac-then-encrypt is definitely a problem in that circumstance. Encrypt-then-Mac is better in that it protects you from even decrypting anything before you've authenticated the source. > it can leak out into everything, ... MAC, timing... A good MAC algorithm doesn't leak anything about the plaintext. A good mac-checking algorithm doesn't give anything away with timing either. (edited to remove references to CFB, my memory of that stream construction was inaccurate, but the point in general stands, if I can manipulate some of the ciphertext that make known-changes to the plaintext decryption, I'm back to being able to make a timing analysis on MAC checking. It's better to check the MAC first, and in constant time.)
  - just-ok 6y ago
    > A good MAC algorithm doesn't leak anything about the plaintext. Though this may be true for specific MAC algorithms, it's a very dangerous and incorrect assumption to hold in general. MACs are designed for integrity and nothing more.
    - Nursie 6y ago
      Fair enough, also not really at issue when we're talking about encrypt-then-mac I guess.
      - just-ok 6y ago
        Yep! Absolutely true, and one of the reasons why Encrypt-then-MAC is the only generic composition method scheme that always provides certain security properties (specifically, security against chosen-ciphertext attacks given that the "encrypt" part is secure against chosen-plaintext attacks and the "MAC" part is secure against forgeries).
- tialaramex 6y ago
  > Every time the attacker changes the ciphertext both the MAC and the plaintext will change unpredictably. No. This system uses CBC so changes to the ciphertext have predictable consequences for some of the plaintext including the MAC. This is why padding oracle attacks on CBC work so nicely. You smash a random byte you don't care about in block N-1 and twiddle a byte in block N. The padding oracle tells you if you got that byte "right" by the padding rules and so you can deduce what it was before you twiddled it.
  - barbegal 6y ago
    > This system uses CBC so changes to the ciphertext have predictable consequences for some of the plaintext including the MAC. Specifically they have predictable consequences for the next block so if the MAC is at the end of the Nth block you can change the ciphertext of block N-1. You still have the problem that this changes both the plaintext and the MAC so the attack would still fail. Or so I thought until I read through https://gist.github.com/defuse/0822a9c6d70ab4939c95 https://gist.github.com/defuse/0822a9c6d70ab4939c95 to understand the attack. The MAC here fills at least a whole block allowing independent changes to the MAC and the plaintext.
rudolph9 6y ago
Why do websites hijack the back button? The article was interesting but I’m always turned off by pages to make me hit the back button like 20 times to actually go to the previous page I was visiting.
- ColinWright 6y ago
  I agree with you entirely, and in defence I've got into the habit of always, without exception, opening a link in a new tab. Then I can simply close the tab to return to my launch point.
  - hansvm 6y ago
    My favorite website feature is when a button masquerades as a link via javascript so that CTRL+click doesn't open it in a new tab like I intended.
Redoubts 6y ago
So where does one go to learn the good, practical ways to think about cryptography and authentication?
- jolux 6y ago
  https://cryptopals.com/ https://cryptopals.com/, by Matasano/NCC Group (originally @tptacek iirc)
  - tialaramex 6y ago
    There are a few problems with these exercises in their current form. Firstly they have aged. They're a product of a specific period of time and things do change in the real world albeit slowly. There's some modern stuff later on, but too much of it in my opinion is now a history lesson without further application. Secondly they were written as a challenge-response type of situation. Thomas says do X, you say "Huh? But A" and then a day later Thomas explains yes A so technically he meant X' - but as a web page you don't benefit from that. This means if you aren't already fairly confident of this material you may in some cases fool yourself into believing you did it correctly when you missed the point of the exercise - or worse, spend a lot of time thrashing around trying to do something that's impossible because you didn't understand what was intended. e.g. you can find on the Web plenty of people who've "passed" Challenge 13 by granting themselves as attacker the ability to encrypt strings of their choice, not just user "profiles" from the imaginary target system. They aren't "cheating" which would be pointless, but without feedback they don't end up learning the intended lesson. Thirdly (OK much less seriously) clearly in this more enlightened age we need different example plaintext. How about well known lyrics by Greg Camp which I believe featured in a Oscar winning animated feature around the turn of the century? On the other hand (and more seriously again), I don't see a whole pile of better training materials laying around if you're a confident programmer who wants to understand some practical cryptography issues at ground level.
    - jolux 6y ago
      I’m mostly basing the recommendation on the last sentence, but welcome recommendations for other resources.
mcguire 6y ago
Once upon a time, roughly the mid '90s, I attended a talk by somebody from the Horus Project (https://www.cs.cornell.edu/info/projects/horus/); https://www.cs.cornell.edu/info/projects/horus/); mercifully, I've forgotten who it was. Anyway, this person was blathering on and on about the Lego model of network protocol components and how you could build new protocols quickly by stacking different blocks and only needed to build your specific functionality into a block to re-use the other components. See Horus: A Flexible Group Communications System (https://www.cs.cornell.edu/home/rvr/papers/HorusFlexible.pdf https://www.cs.cornell.edu/home/rvr/papers/HorusFlexible.pdf) for an example. Anyway, in their slides, the example was two Lego bricks labelled "Encryption" and "Compression", which were shown stacked in the two different orders. The problem is that doesn't work. You cannot compress something that has been encrypted. Those two blocks do not commute. I was, unfortunately, too much of a gutless larval grad student to bring this up at the talk, though.
- tialaramex 6y ago
  Even better, while compressing a good quality ciphertext doesn't work - enciphering a compressed stream may introduce more problems than if it had not been compressed first. This doesn't look like a real world problem and I can believe that in "the mid '90s" a cryptographer who pointed out that it's a bad idea would have been dismissed for focusing on a purely academic concern. In a cryptographer's model an adversary who is able to use your system to encrypt plaintext partially or entirely of their choosing is a reasonable hypothetical, but in the real world such adversaries were rare. Who lets somebody else choose part of the messages they're encrypting? The Web offers a concrete answer in the form of: Cookies, HTTPS and Javascript. Bad guys get to cause you to encrypt a mixture of their chosen plaintext plus a cookie value they don't yet know. Is that a problem? Well... if you compress the data before encrypting then the bad guys get to see whether it compresses more or less with their chosen input, and you've got CRIME (and later BREACH).

32 points by ColinWright 6y ago

The author takes the following statement to be incorrect: > I had written code for a constant-time text comparison of the MAC but then realized that this is not an issue when using the MAC-then-encrypt method because the MAC is only compared after decryption to verify that the data is intact and the same as when it was encrypted. Since the correct MAC is only exposed when the correct encryption key is used it doesn’t matter whether the text comparison is done in constant-time or not. Changing to an encrypt-then-MAC method (requiring a constant-time MAC comparison) would not be backwards compatible with the current version. I don't see anything wrong with this statement. With encrypt-then-MAC the application is going to calculate the MAC on the ciphertext then compare it against the MAC included with the ciphertext. If the two match then the application will decrypt the ciphertext into plaintext. If the attacker doesn't actually know the encryption key then the data will be garbled but that might not matter for certain attacks. The key to the attack is getting the MAC correct and to do that timing attacks on the comparison can be done. But in this case we are using MAC-then-encrypt. The application is going to decrypt the ciphertext to produce plaintext and MAC. Every time the attacker changes the ciphertext both the MAC and the plaintext will change unpredictably. Even with the timing leak, the attacker can't do anything with the ciphertext to make it such that the MAC verifies the plaintext One of the key flaws of modern security protocols is making them robust to bad implementations and side channels. I don't see the problem as being reasoning by Lego but rather in neglecting that the information you wish to protect is not just in the ciphertext, it can leak out into everything, the length of the message, padding, MAC, timing...

Nursie 6y ago
> If the attacker doesn't actually know the encryption key then the data will be garbled That depends on exactly what sort of cipher scheme is used. I don't know what exact scheme we're talking about here (it wasn't described in the post and I didn't go hunting any further) but there are stream constructions where if you change a bit in the ciphertext, it changes a corresponding bit in the plaintext that comes out. This is because in these modes the keystream is independent of the data and the ciphertext is the result of XORing the keystream with the plaintext. The plaintext is unrecoverable without the key, but what's decoded can be manipulated, even without knowing what it is. Mac-then-encrypt is definitely a problem in that circumstance. Encrypt-then-Mac is better in that it protects you from even decrypting anything before you've authenticated the source. > it can leak out into everything, ... MAC, timing... A good MAC algorithm doesn't leak anything about the plaintext. A good mac-checking algorithm doesn't give anything away with timing either. (edited to remove references to CFB, my memory of that stream construction was inaccurate, but the point in general stands, if I can manipulate some of the ciphertext that make known-changes to the plaintext decryption, I'm back to being able to make a timing analysis on MAC checking. It's better to check the MAC first, and in constant time.)
- just-ok 6y ago
  > A good MAC algorithm doesn't leak anything about the plaintext. Though this may be true for specific MAC algorithms, it's a very dangerous and incorrect assumption to hold in general. MACs are designed for integrity and nothing more.
  - Nursie 6y ago
    Fair enough, also not really at issue when we're talking about encrypt-then-mac I guess.
    - just-ok 6y ago
      Yep! Absolutely true, and one of the reasons why Encrypt-then-MAC is the only generic composition method scheme that always provides certain security properties (specifically, security against chosen-ciphertext attacks given that the "encrypt" part is secure against chosen-plaintext attacks and the "MAC" part is secure against forgeries).
tialaramex 6y ago
> Every time the attacker changes the ciphertext both the MAC and the plaintext will change unpredictably. No. This system uses CBC so changes to the ciphertext have predictable consequences for some of the plaintext including the MAC. This is why padding oracle attacks on CBC work so nicely. You smash a random byte you don't care about in block N-1 and twiddle a byte in block N. The padding oracle tells you if you got that byte "right" by the padding rules and so you can deduce what it was before you twiddled it.
- barbegal 6y ago
  > This system uses CBC so changes to the ciphertext have predictable consequences for some of the plaintext including the MAC. Specifically they have predictable consequences for the next block so if the MAC is at the end of the Nth block you can change the ciphertext of block N-1. You still have the problem that this changes both the plaintext and the MAC so the attack would still fail. Or so I thought until I read through https://gist.github.com/defuse/0822a9c6d70ab4939c95 https://gist.github.com/defuse/0822a9c6d70ab4939c95 to understand the attack. The MAC here fills at least a whole block allowing independent changes to the MAC and the plaintext.

rudolph9 6y ago

Why do websites hijack the back button? The article was interesting but I’m always turned off by pages to make me hit the back button like 20 times to actually go to the previous page I was visiting.

ColinWright 6y ago
I agree with you entirely, and in defence I've got into the habit of always, without exception, opening a link in a new tab. Then I can simply close the tab to return to my launch point.
- hansvm 6y ago
  My favorite website feature is when a button masquerades as a link via javascript so that CTRL+click doesn't open it in a new tab like I intended.

Redoubts 6y ago

So where does one go to learn the good, practical ways to think about cryptography and authentication?

jolux 6y ago
https://cryptopals.com/ https://cryptopals.com/, by Matasano/NCC Group (originally @tptacek iirc)
- tialaramex 6y ago
  There are a few problems with these exercises in their current form. Firstly they have aged. They're a product of a specific period of time and things do change in the real world albeit slowly. There's some modern stuff later on, but too much of it in my opinion is now a history lesson without further application. Secondly they were written as a challenge-response type of situation. Thomas says do X, you say "Huh? But A" and then a day later Thomas explains yes A so technically he meant X' - but as a web page you don't benefit from that. This means if you aren't already fairly confident of this material you may in some cases fool yourself into believing you did it correctly when you missed the point of the exercise - or worse, spend a lot of time thrashing around trying to do something that's impossible because you didn't understand what was intended. e.g. you can find on the Web plenty of people who've "passed" Challenge 13 by granting themselves as attacker the ability to encrypt strings of their choice, not just user "profiles" from the imaginary target system. They aren't "cheating" which would be pointless, but without feedback they don't end up learning the intended lesson. Thirdly (OK much less seriously) clearly in this more enlightened age we need different example plaintext. How about well known lyrics by Greg Camp which I believe featured in a Oscar winning animated feature around the turn of the century? On the other hand (and more seriously again), I don't see a whole pile of better training materials laying around if you're a confident programmer who wants to understand some practical cryptography issues at ground level.
  - jolux 6y ago
    I’m mostly basing the recommendation on the last sentence, but welcome recommendations for other resources.

mcguire 6y ago

Once upon a time, roughly the mid '90s, I attended a talk by somebody from the Horus Project (https://www.cs.cornell.edu/info/projects/horus/); https://www.cs.cornell.edu/info/projects/horus/); mercifully, I've forgotten who it was. Anyway, this person was blathering on and on about the Lego model of network protocol components and how you could build new protocols quickly by stacking different blocks and only needed to build your specific functionality into a block to re-use the other components. See Horus: A Flexible Group Communications System (https://www.cs.cornell.edu/home/rvr/papers/HorusFlexible.pdf https://www.cs.cornell.edu/home/rvr/papers/HorusFlexible.pdf) for an example. Anyway, in their slides, the example was two Lego bricks labelled "Encryption" and "Compression", which were shown stacked in the two different orders. The problem is that doesn't work. You cannot compress something that has been encrypted. Those two blocks do not commute. I was, unfortunately, too much of a gutless larval grad student to bring this up at the talk, though.

tialaramex 6y ago
Even better, while compressing a good quality ciphertext doesn't work - enciphering a compressed stream may introduce more problems than if it had not been compressed first. This doesn't look like a real world problem and I can believe that in "the mid '90s" a cryptographer who pointed out that it's a bad idea would have been dismissed for focusing on a purely academic concern. In a cryptographer's model an adversary who is able to use your system to encrypt plaintext partially or entirely of their choosing is a reasonable hypothetical, but in the real world such adversaries were rare. Who lets somebody else choose part of the messages they're encrypting? The Web offers a concrete answer in the form of: Cookies, HTTPS and Javascript. Bad guys get to cause you to encrypt a mixture of their chosen plaintext plus a cookie value they don't yet know. Is that a problem? Well... if you compress the data before encrypting then the bad guys get to see whether it compresses more or less with their chosen input, and you've got CRIME (and later BREACH).