6 ms·

> Bad crypto code usually looks and produces results indistinguishable from good crypto code This is such a weird part of cryptography... you can have two impl

> Bad crypto code usually looks and produces results indistinguishable from good crypto code This is such a weird part of cryptography... you can have two implementations, which both always produce the exact same output... and yet, one could be vulnerable because of side channel or timing attacks.

stouset 6y ago
Not just that but something like AES using ECB is indistinguishable from random to the casual observer. Only when you’re aware of why ECB is bad will you understand what to look for to defeat it.
- andrewnicolalde 6y ago
  I actually have a sticker of ECB Tux[1] on my laptop to serve as a fun reminder :P [1] https://filippo.io/images/Tux-ECB.png https://filippo.io/images/Tux-ECB.png
  - nmadden 6y ago
    Which is the classic illustration that ECB is _not_ indistinguishable from random, even to a casual observer.
    - tialaramex 6y ago
      I think "casual observer" and "shove deliberately patterned data through the system then render it so that I can see if the patterns show through" aren't the same thing. In the Tux data maybe 03038F12128F0303 turns into 49DC195026F3300A and that looks pretty random. It's only visible as the Tux image because every 03038F12128F0303 turns into 49DC195026F3300A, thus preserving the very bold overall pattern of the image. If you shove a photograph of a kitten through it, that looks like noise, but Tux is made of these big bold shapes and so the resulting pattern is big enough to "show through" the ECB encryption.
      - nmadden 6y ago
        These kinds of patterns are present in input data quite often - eg fixed headers, markup etc. As usual, there’s even an xkcd on it: https://xkcd.com/1286/ https://xkcd.com/1286/
      - Dylan16807 6y ago
        You're basically implying that a casual observer would look at AES all by itself and then say things are good. And I think you're correct to imply that. But that means that ECB isn't actually passing the smoke test, because the casual observer isn't analyzing AES+ECB. They're only analyzing AES.
    - tzs 6y ago
      I think when people say that a block cipher is indistinguishable from random they mean that for a given key k, the permutation 0 -> cipher(0, k), 1 -> cipher(1, k), ..., 2^n-1 -> cipher(2^n-1, k) where n is the block length in bits is indistinguishable from a random permutation of (0, 1, 2, ..., 2^n-1).
      - nmadden 6y ago
        That’s an ok(ish) definition of indistinguishability for a block cipher, but not for a mode of operation like ECB.
  - mhe 6y ago
    In case anyone wants to create a similar reminder for a specific image, a while ago I created a small utility that does just that: https://github.com/mhe/visualmoo https://github.com/mhe/visualmoo
    - andrewnicolalde 6y ago
      This is very cool, thanks for sharing!
- betterunix2 6y ago
  Actually a casual observer can distinguish ECB from random, though they may not realize that is what they are doing. For example if you manage to compress the ciphertext -- random data should not compress by much so if you can do any significant compression on ciphertext then you are distinguishing it from random bits. ECB should be compressable if the plaintext is compressable (though probably not as well as the plaintext do to the way ECB is divided into blocks). Recognizing that this is a problem is another matter.
ecesena 6y ago
This is true for every piece of software, isn't it!? You can have 2 identical websites, one checks your username+password for real, the other always logs you in. Or even better, one stores bcrypted passwords, then other cleartext ones... Use battle tested frameworks. For crypto, for sites, for everything.
- cortesoft 6y ago
  This goes beyond that, though... in your example, the two programs DON’T give identical output with identical input; one will log you in with a bad password, one won’t. That is different behavior. Likewise, with your second example, the storing clear text and bcrypted passwords are different outputs. When I say the two pieces of code have identical outputs for identical inputs, I mean everything, not just what an end user sees. Here is a toy example to show what I mean: say you have a function that takes a username and password, and compares it against a stored username and password (lets ignore the insecurity of storing a plain text password for this example). Now, you have two implementations of the function, and we know that both work as desired; they both will accept all correct username/password combos, and will reject all incorrect username/password combos. We have exhaustive tests proving that both return the same result when given the same input. Normally, this is good enough - both functions are interchangeable, because they are guaranteed to always output the same data with the same input. You would probably choose the implementation that is faster, or used less memory, or whatever. However, for crypto, this isn’t enough. Lets say in our exmaple, one implementation starts checking each bit of the password. If the first bit of the submitted password matches the first bit of the stored password, it moves to the next bit. If they don't match, it returns false because it knows that the passwords don't match. What a great optimization! You don't have to keep checking once you hit the first wrong bit. The second implementation checks every bit, even after it finds an incorrect match. So inefficient! However, even though they both work perfectly in the sense that they will always return the correct result, the one that returns false on the first mismatched bit is vulnerable to a timing attack. An attacker can keep submitting passwords, and wait for the response to get a little bit slower... now they know they have the first bit correct. Repeat this for a while, and you can figure out all the bits. This is obviously a toy example, but this technique has been used over and over again to break crypto implementations. You have to care about more than just the output when you deal with crypto! Here is a paper about using this technique to break an earlier version of OpenSSL: https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf

stouset 6y ago

Not just that but something like AES using ECB is indistinguishable from random to the casual observer. Only when you’re aware of why ECB is bad will you understand what to look for to defeat it.

andrewnicolalde 6y ago
I actually have a sticker of ECB Tux[1] on my laptop to serve as a fun reminder :P [1] https://filippo.io/images/Tux-ECB.png https://filippo.io/images/Tux-ECB.png
- nmadden 6y ago
  Which is the classic illustration that ECB is _not_ indistinguishable from random, even to a casual observer.
  - tialaramex 6y ago
    I think "casual observer" and "shove deliberately patterned data through the system then render it so that I can see if the patterns show through" aren't the same thing. In the Tux data maybe 03038F12128F0303 turns into 49DC195026F3300A and that looks pretty random. It's only visible as the Tux image because every 03038F12128F0303 turns into 49DC195026F3300A, thus preserving the very bold overall pattern of the image. If you shove a photograph of a kitten through it, that looks like noise, but Tux is made of these big bold shapes and so the resulting pattern is big enough to "show through" the ECB encryption.
    - nmadden 6y ago
      These kinds of patterns are present in input data quite often - eg fixed headers, markup etc. As usual, there’s even an xkcd on it: https://xkcd.com/1286/ https://xkcd.com/1286/
    - Dylan16807 6y ago
      You're basically implying that a casual observer would look at AES all by itself and then say things are good. And I think you're correct to imply that. But that means that ECB isn't actually passing the smoke test, because the casual observer isn't analyzing AES+ECB. They're only analyzing AES.
  - tzs 6y ago
    I think when people say that a block cipher is indistinguishable from random they mean that for a given key k, the permutation 0 -> cipher(0, k), 1 -> cipher(1, k), ..., 2^n-1 -> cipher(2^n-1, k) where n is the block length in bits is indistinguishable from a random permutation of (0, 1, 2, ..., 2^n-1).
    - nmadden 6y ago
      That’s an ok(ish) definition of indistinguishability for a block cipher, but not for a mode of operation like ECB.
- mhe 6y ago
  In case anyone wants to create a similar reminder for a specific image, a while ago I created a small utility that does just that: https://github.com/mhe/visualmoo https://github.com/mhe/visualmoo
  - andrewnicolalde 6y ago
    This is very cool, thanks for sharing!
betterunix2 6y ago
Actually a casual observer can distinguish ECB from random, though they may not realize that is what they are doing. For example if you manage to compress the ciphertext -- random data should not compress by much so if you can do any significant compression on ciphertext then you are distinguishing it from random bits. ECB should be compressable if the plaintext is compressable (though probably not as well as the plaintext do to the way ECB is divided into blocks). Recognizing that this is a problem is another matter.

ecesena 6y ago

This is true for every piece of software, isn't it!? You can have 2 identical websites, one checks your username+password for real, the other always logs you in. Or even better, one stores bcrypted passwords, then other cleartext ones... Use battle tested frameworks. For crypto, for sites, for everything.

cortesoft 6y ago
This goes beyond that, though... in your example, the two programs DON’T give identical output with identical input; one will log you in with a bad password, one won’t. That is different behavior. Likewise, with your second example, the storing clear text and bcrypted passwords are different outputs. When I say the two pieces of code have identical outputs for identical inputs, I mean everything, not just what an end user sees. Here is a toy example to show what I mean: say you have a function that takes a username and password, and compares it against a stored username and password (lets ignore the insecurity of storing a plain text password for this example). Now, you have two implementations of the function, and we know that both work as desired; they both will accept all correct username/password combos, and will reject all incorrect username/password combos. We have exhaustive tests proving that both return the same result when given the same input. Normally, this is good enough - both functions are interchangeable, because they are guaranteed to always output the same data with the same input. You would probably choose the implementation that is faster, or used less memory, or whatever. However, for crypto, this isn’t enough. Lets say in our exmaple, one implementation starts checking each bit of the password. If the first bit of the submitted password matches the first bit of the stored password, it moves to the next bit. If they don't match, it returns false because it knows that the passwords don't match. What a great optimization! You don't have to keep checking once you hit the first wrong bit. The second implementation checks every bit, even after it finds an incorrect match. So inefficient! However, even though they both work perfectly in the sense that they will always return the correct result, the one that returns false on the first mismatched bit is vulnerable to a timing attack. An attacker can keep submitting passwords, and wait for the response to get a little bit slower... now they know they have the first bit correct. Repeat this for a while, and you can figure out all the bits. This is obviously a toy example, but this technique has been used over and over again to break crypto implementations. You have to care about more than just the output when you deal with crypto! Here is a paper about using this technique to break an earlier version of OpenSSL: https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf