13 ms·

A Vulnerability in Implementations of SHA-3, Shake, EdDSA

185 points by state 4y ago

eulgro 4y ago
I didn't read the whole paper, but how can this even happen? Seems like the buffer overflow would be triggered for any file larger than 4 GiB, which I assume someone has tested in the 8 years since it was released.
- cesarb 4y ago
  > I didn't read the whole paper, but how can this even happen? Seems like the buffer overflow would be triggered for any file larger than 4 GiB I skimmed the paper, and as far as I understood it: Most cryptographic hash functions operate in fixed-size blocks (for instance, 32 bytes). Additionally, most cryptographic hash function implementations are designed to be streaming, that is, they do not receive the whole input at once. If you give them a partial input which is not a multiple of their block size, these implementations have to buffer the partial input, so that it can be combined with the next partial input (or flushed, if the next call is to finish the computation and generate the output). The arithmetic overflow which leads to the buffer overflow happens when computing how much it has to buffer, given a partial input and any previous partial input already in its internal buffer. That is, having a file larger than 4GiB is not enough; it has to also be cut into pieces which are not a multiple of the block size (which is normally a power of two). Most users of a cryptographic hash function will either give it the input in large power-of-two pieces (for instance, 8 KiB or 64 KiB), or give it the input all at once, and thus will not hit the bug.
- userbinator 4y ago
  You need to feed it a block slightly less than its blocksize, then another one slightly less than 4GB.
- rurban 4y ago
  You'd be surprised how many of those submitted and approved crypto standards are still not tested with industry best practices. buffer overflows or integer UB's and overflows are very common. ubsan, asan, valgrind tests are missing. some do offer symbolic verification of the algo, but not the implementations. See my https://github.com/rurban/smhasher#crypto https://github.com/rurban/smhasher#crypto paragraph, and "Finding Bugs in Cryptographic Hash Function Implementations", Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker, 2017. https://eprint.iacr.org/2017/891.pdf https://eprint.iacr.org/2017/891.pdf
  - miohtama 4y ago
    Hopefully people working on hashes and codecs will use Rust in the future, so Valgrinding and such are less needed.
    - rurban 4y ago
      Or even better an explicitly secure language, not just one only claiming various safeties without actually implementing them. ADA/Spark or Modula-2 would come to my mind, but there must be more like rune for constant-time and more such crypto-only problems. I'm sure djb has such one also. https://cr.yp.to/talks/2021.09.03/slides-djb-20210903-saferewrite-4x3.pdf https://cr.yp.to/talks/2021.09.03/slides-djb-20210903-safere... * https://github.com/GaloisInc/hacrypto https://github.com/GaloisInc/hacrypto * https://github.com/fmlab-iis/cryptoline https://github.com/fmlab-iis/cryptoline * https://github.com/mit-plv/fiat-crypto/ https://github.com/mit-plv/fiat-crypto/ (Bedrock2) * https://github.com/hacl-star/hacl-star https://github.com/hacl-star/hacl-star (F* and ValeCrypt) * https://github.com/jasmin-lang/jasmin https://github.com/jasmin-lang/jasmin * https://vst.cs.princeton.edu/ https://vst.cs.princeton.edu/
      - touisteur 4y ago
        Yes, there are actually implementations of most standard stuff in Ada and SPARK (so with some level of proof) Interesting posts (and links): * https://blog.adacore.com/avoiding-vulnerabilities-in-crypto-code-with-spark https://blog.adacore.com/avoiding-vulnerabilities-in-crypto-... * https://blog.adacore.com/sparknacl-two-years-of-optimizing-crypto-code-in-spark-and-counting https://blog.adacore.com/sparknacl-two-years-of-optimizing-c... * https://github.com/Componolit/libsparkcrypto https://github.com/Componolit/libsparkcrypto Proof of constant-time execution is an interesting field, but as I understand very much less mature than the SPARK toolset. If anyone has a toolchain working over llvm to check and/or make code constant-time, I'm interested. I mean, if the standards people want to keep writing C, they can probably use Frama-C for the standard implementation...
    - seanw444 4y ago
      Let me cross that one off my daily bingo card...
- pas 4y ago
  You might remember that JDK 15-18 versions shipped to GA with a bug that accepted (0,0) as valid key for ECDSA. https://news.ycombinator.com/item?id=31089216 https://news.ycombinator.com/item?id=31089216 ... and it's not like there wasn't a FOSS test suite for this.
  - mm2023 4y ago
    It was worse, it wasn't a (0,0) key it accepted. If that was all then you could blame the user for loading in a bad key etc. No the vuln was that it accepted (0,0) as being a valid signature over any text and validated using any public key! So you could forge any signature by simply using (0,0) as the sig itself!
jonstewart 4y ago
> partialBlock = (unsigned int)(dataByteLen - i); The paper makes no mention of compiler warnings… but shouldn’t this cast trigger a compiler warning?
- caf 4y ago
  No? The effect of that is well-defined, and the cast is a pretty strong signal that the author is deliberately converting the value. Casts to unsigned that deliberately discard the high bits are relatively common.
  - loup-vaillant 4y ago
    I believe Clang under -Weverything has a warning about possible loss of precision. It also has lots of annoying warnings that would dissuade many people from running -Weverything by default.
    - jonstewart 4y ago
      Yes, the loss of precision warnings. It may be these only happen if you compile as C++ and not as straight C? (I don’t do straight C much.) Of course you’ll run into dozens of instances of it with old C code… and my experience has been that some of those instances are bugs similar to this one.
      - loup-vaillant 4y ago
        Here's the definite answer: #include <stdio.h> int main() { long long unsigned llu; if (scanf("%llu", &llu) == EOF) { printf("EOF!!\n"); } printf("%llu\n", llu); unsigned u = llu; printf("%u\n", u); return 0; } Here's an execution run: $ ./a.out 9876543210 9876543210 (llu) 1286608618 (u) I tried to compile it as C and C++, with both Clang (14.0.0) and GCC (11.3.0): gcc -Wall -Wextra # no warning g++ -Wall -Wextra # no warning clang -Wall -Wextra # no warning clang++ -Wall -Wextra # no warning clang -Wall -Wextra -Weverything # loss of precision warning clang++ -Wall -Wextra -Weverything # loss of precision warning However, the warning goes away if there's an explicit cast: unsigned u = (unsigned)llu; Worse, I still have no warning if I do the narrowing cast then affect it to a wider variable: long long unsigned u = (unsigned)llu; printf("%llu (u)\n", u); In C++ I'm warned about the old style cast of course, but using `static_cast` makes the warning go away. And of course the code overflows just like before. I don't have a good solution to this. Sometimes I do want to lose the precision. Bignum arithmetic for instance. In any case, I'm pretty sure the Keccak team's compiler did not issue any warning. Sorry if I implied otherwise.
makeworld 4y ago
This is over 4 months old, and is already patched in Python. Was discussed on HN at the time: https://news.ycombinator.com/item?id=33281106 https://news.ycombinator.com/item?id=33281106
- EGreg 4y ago
  What about PHP?
  - tomudding 4y ago
    Yes, fixed in all (at the time) supported versions in October last year [0]. [0]: https://github.com/php/php-src/commit/248f647 https://github.com/php/php-src/commit/248f647
Donckele 4y ago
Is this due to stupidity or malice? I just can’t get my head round the idea that software written and reviewed by experts and submitted to the “National Institute of Standards and Technology” with a budget of 1 billion dollars can fuck up this way. I’m no mathematician but I would have thought implementing pure number crunching code is not rocket science. Buffer overflow, overwrite memory, run arbitrary code, seriously? LOL, WTF.
- bilekas 4y ago
  > Buffer overflow, overwrite memory, run arbitrary code, seriously? LOL, WTF. Do you think everything (arguably anything) is released flawless?
- drivebycomment 4y ago
  Nobody with any experience would laugh at mistakes like this. It's only easy in hindsight. Past 30+ years of collective experience in our industry shows that these classes of bugs are nearly impossible to completely stamp out in any language but especially in memory unsafe ones, even with dramatically better compile time and runtime tools that can spot many of these nowadays. During the early days of the internet and the buffer overflow attacks after Morris worm, buffer overflow bugs existed in practically all software. There were times when pretty much any servers connected to the internet could be had relatively easily. Even with memory safe languages, there are dangers. Humanity just hasn't figured out how to produce completely bug-free code at the scale we need in general, let alone in a memory-unsafe language.
  - loup-vaillant 4y ago
    This particular mistake is all the more infuriating because it comes from a precaution. Or trying to silence a compiler warning: partialBlock = (unsigned int)(dataByteLen - i); Where both `dataByteLen` and `i` where actually `size_t`. Assuming this is close enough to C, what happens is that we're converting a difference between `size_t` into a mere `unsigned`, and since they're not the same sizes on 64-bit platforms this can give `partialBlock` the wrong value, and the whole thing then snowballs into a catastrophic error that is not trivial to test because it only happens with huge buffer sizes. The biggest mistake here is having written `(unsigned int)` instead of `(size_t)`. But the reason it happened in the first place is because they tried to do the right thing: writing the cast as a precaution, even though the following would have worked: partialBlock = dataByteLen - i; I really can't fault them: because it was a difference it could theoretically yield a "negative" result, and therefore intuitively the type of a difference should be signed, so we should cast it back to unsigned to be crystal clear. I knew C was dangerous, but to be honest I didn't expect such a wicked mind game. Now I'm going to have to take a look at my code.
eterevsky 4y ago
I wonder if this could be avoided by writing the canonical implementations in Rust or better yet in some system with formal verification. This is such a critical part of the software stack, that we need a more reliable way of validation than just a bunch of people staring at the code written in C.
- Arnavion 4y ago
  Rust won't help. Sure the compiled code would be bounds-checked, but nobody would notice the bug unless they gave it the crashing input. And then when they reimplemented the code in their non-bounds-checked language then that would reintroduce the bug anyway. A formal verification implementation would catch it at authoring time, yes.
  - ysleepy 4y ago
    It seems to be an array out of bounds read/write. Rust does bound checks, so this should be covered.
    - GoblinSlayer 4y ago
      All languages except for C do bound checks, you don't need a borrow checker for this.
- execveat 4y ago
  Rust doesn't prevent integer over/underflows.
  - roca 4y ago
    It helps. In Rust debug builds, integer overflows crash -> tests will detect them. In release builds they're not detected by default, but you can add "overflow-checks = true" to the Cargo profile to enable those checks in release builds too if you want.
    - 4y ago
red_admiral 4y ago
To clarify, this only affects EdDSA as far as implementations use SHA-3 to hash a message before applying the signature. The actual elliptic curve operations code seems to be fine.
harveywi 4y ago
It may be helpful to give this vulnerability a name, contributing to public awareness of the issue. For example, The SHA-Shake Redemption.
rurban 4y ago
I find the current polynonce attack much worse: https://news.ycombinator.com/item?id=35048431 https://news.ycombinator.com/item?id=35048431

185 points by state 4y ago

I didn't read the whole paper, but how can this even happen? Seems like the buffer overflow would be triggered for any file larger than 4 GiB, which I assume someone has tested in the 8 years since it was released.

cesarb 4y ago
> I didn't read the whole paper, but how can this even happen? Seems like the buffer overflow would be triggered for any file larger than 4 GiB I skimmed the paper, and as far as I understood it: Most cryptographic hash functions operate in fixed-size blocks (for instance, 32 bytes). Additionally, most cryptographic hash function implementations are designed to be streaming, that is, they do not receive the whole input at once. If you give them a partial input which is not a multiple of their block size, these implementations have to buffer the partial input, so that it can be combined with the next partial input (or flushed, if the next call is to finish the computation and generate the output). The arithmetic overflow which leads to the buffer overflow happens when computing how much it has to buffer, given a partial input and any previous partial input already in its internal buffer. That is, having a file larger than 4GiB is not enough; it has to also be cut into pieces which are not a multiple of the block size (which is normally a power of two). Most users of a cryptographic hash function will either give it the input in large power-of-two pieces (for instance, 8 KiB or 64 KiB), or give it the input all at once, and thus will not hit the bug.
userbinator 4y ago
You need to feed it a block slightly less than its blocksize, then another one slightly less than 4GB.
rurban 4y ago
You'd be surprised how many of those submitted and approved crypto standards are still not tested with industry best practices. buffer overflows or integer UB's and overflows are very common. ubsan, asan, valgrind tests are missing. some do offer symbolic verification of the algo, but not the implementations. See my https://github.com/rurban/smhasher#crypto https://github.com/rurban/smhasher#crypto paragraph, and "Finding Bugs in Cryptographic Hash Function Implementations", Nicky Mouha, Mohammad S Raunak, D. Richard Kuhn, and Raghu Kacker, 2017. https://eprint.iacr.org/2017/891.pdf https://eprint.iacr.org/2017/891.pdf
- miohtama 4y ago
  Hopefully people working on hashes and codecs will use Rust in the future, so Valgrinding and such are less needed.
  - rurban 4y ago
    Or even better an explicitly secure language, not just one only claiming various safeties without actually implementing them. ADA/Spark or Modula-2 would come to my mind, but there must be more like rune for constant-time and more such crypto-only problems. I'm sure djb has such one also. https://cr.yp.to/talks/2021.09.03/slides-djb-20210903-saferewrite-4x3.pdf https://cr.yp.to/talks/2021.09.03/slides-djb-20210903-safere... * https://github.com/GaloisInc/hacrypto https://github.com/GaloisInc/hacrypto * https://github.com/fmlab-iis/cryptoline https://github.com/fmlab-iis/cryptoline * https://github.com/mit-plv/fiat-crypto/ https://github.com/mit-plv/fiat-crypto/ (Bedrock2) * https://github.com/hacl-star/hacl-star https://github.com/hacl-star/hacl-star (F* and ValeCrypt) * https://github.com/jasmin-lang/jasmin https://github.com/jasmin-lang/jasmin * https://vst.cs.princeton.edu/ https://vst.cs.princeton.edu/
    - touisteur 4y ago
      Yes, there are actually implementations of most standard stuff in Ada and SPARK (so with some level of proof) Interesting posts (and links): * https://blog.adacore.com/avoiding-vulnerabilities-in-crypto-code-with-spark https://blog.adacore.com/avoiding-vulnerabilities-in-crypto-... * https://blog.adacore.com/sparknacl-two-years-of-optimizing-crypto-code-in-spark-and-counting https://blog.adacore.com/sparknacl-two-years-of-optimizing-c... * https://github.com/Componolit/libsparkcrypto https://github.com/Componolit/libsparkcrypto Proof of constant-time execution is an interesting field, but as I understand very much less mature than the SPARK toolset. If anyone has a toolchain working over llvm to check and/or make code constant-time, I'm interested. I mean, if the standards people want to keep writing C, they can probably use Frama-C for the standard implementation...
  - seanw444 4y ago
    Let me cross that one off my daily bingo card...
pas 4y ago
You might remember that JDK 15-18 versions shipped to GA with a bug that accepted (0,0) as valid key for ECDSA. https://news.ycombinator.com/item?id=31089216 https://news.ycombinator.com/item?id=31089216 ... and it's not like there wasn't a FOSS test suite for this.
- mm2023 4y ago
  It was worse, it wasn't a (0,0) key it accepted. If that was all then you could blame the user for loading in a bad key etc. No the vuln was that it accepted (0,0) as being a valid signature over any text and validated using any public key! So you could forge any signature by simply using (0,0) as the sig itself!

jonstewart 4y ago

> partialBlock = (unsigned int)(dataByteLen - i); The paper makes no mention of compiler warnings… but shouldn’t this cast trigger a compiler warning?

caf 4y ago
No? The effect of that is well-defined, and the cast is a pretty strong signal that the author is deliberately converting the value. Casts to unsigned that deliberately discard the high bits are relatively common.
- loup-vaillant 4y ago
  I believe Clang under -Weverything has a warning about possible loss of precision. It also has lots of annoying warnings that would dissuade many people from running -Weverything by default.
  - jonstewart 4y ago
    Yes, the loss of precision warnings. It may be these only happen if you compile as C++ and not as straight C? (I don’t do straight C much.) Of course you’ll run into dozens of instances of it with old C code… and my experience has been that some of those instances are bugs similar to this one.
    - loup-vaillant 4y ago
      Here's the definite answer: #include <stdio.h> int main() { long long unsigned llu; if (scanf("%llu", &llu) == EOF) { printf("EOF!!\n"); } printf("%llu\n", llu); unsigned u = llu; printf("%u\n", u); return 0; } Here's an execution run: $ ./a.out 9876543210 9876543210 (llu) 1286608618 (u) I tried to compile it as C and C++, with both Clang (14.0.0) and GCC (11.3.0): gcc -Wall -Wextra # no warning g++ -Wall -Wextra # no warning clang -Wall -Wextra # no warning clang++ -Wall -Wextra # no warning clang -Wall -Wextra -Weverything # loss of precision warning clang++ -Wall -Wextra -Weverything # loss of precision warning However, the warning goes away if there's an explicit cast: unsigned u = (unsigned)llu; Worse, I still have no warning if I do the narrowing cast then affect it to a wider variable: long long unsigned u = (unsigned)llu; printf("%llu (u)\n", u); In C++ I'm warned about the old style cast of course, but using `static_cast` makes the warning go away. And of course the code overflows just like before. I don't have a good solution to this. Sometimes I do want to lose the precision. Bignum arithmetic for instance. In any case, I'm pretty sure the Keccak team's compiler did not issue any warning. Sorry if I implied otherwise.

makeworld 4y ago

This is over 4 months old, and is already patched in Python. Was discussed on HN at the time: https://news.ycombinator.com/item?id=33281106 https://news.ycombinator.com/item?id=33281106

EGreg 4y ago
What about PHP?
- tomudding 4y ago
  Yes, fixed in all (at the time) supported versions in October last year [0]. [0]: https://github.com/php/php-src/commit/248f647 https://github.com/php/php-src/commit/248f647

Donckele 4y ago

Is this due to stupidity or malice? I just can’t get my head round the idea that software written and reviewed by experts and submitted to the “National Institute of Standards and Technology” with a budget of 1 billion dollars can fuck up this way. I’m no mathematician but I would have thought implementing pure number crunching code is not rocket science. Buffer overflow, overwrite memory, run arbitrary code, seriously? LOL, WTF.

bilekas 4y ago
> Buffer overflow, overwrite memory, run arbitrary code, seriously? LOL, WTF. Do you think everything (arguably anything) is released flawless?
drivebycomment 4y ago
Nobody with any experience would laugh at mistakes like this. It's only easy in hindsight. Past 30+ years of collective experience in our industry shows that these classes of bugs are nearly impossible to completely stamp out in any language but especially in memory unsafe ones, even with dramatically better compile time and runtime tools that can spot many of these nowadays. During the early days of the internet and the buffer overflow attacks after Morris worm, buffer overflow bugs existed in practically all software. There were times when pretty much any servers connected to the internet could be had relatively easily. Even with memory safe languages, there are dangers. Humanity just hasn't figured out how to produce completely bug-free code at the scale we need in general, let alone in a memory-unsafe language.
- loup-vaillant 4y ago
  This particular mistake is all the more infuriating because it comes from a precaution. Or trying to silence a compiler warning: partialBlock = (unsigned int)(dataByteLen - i); Where both `dataByteLen` and `i` where actually `size_t`. Assuming this is close enough to C, what happens is that we're converting a difference between `size_t` into a mere `unsigned`, and since they're not the same sizes on 64-bit platforms this can give `partialBlock` the wrong value, and the whole thing then snowballs into a catastrophic error that is not trivial to test because it only happens with huge buffer sizes. The biggest mistake here is having written `(unsigned int)` instead of `(size_t)`. But the reason it happened in the first place is because they tried to do the right thing: writing the cast as a precaution, even though the following would have worked: partialBlock = dataByteLen - i; I really can't fault them: because it was a difference it could theoretically yield a "negative" result, and therefore intuitively the type of a difference should be signed, so we should cast it back to unsigned to be crystal clear. I knew C was dangerous, but to be honest I didn't expect such a wicked mind game. Now I'm going to have to take a look at my code.

eterevsky 4y ago

I wonder if this could be avoided by writing the canonical implementations in Rust or better yet in some system with formal verification. This is such a critical part of the software stack, that we need a more reliable way of validation than just a bunch of people staring at the code written in C.

Arnavion 4y ago
Rust won't help. Sure the compiled code would be bounds-checked, but nobody would notice the bug unless they gave it the crashing input. And then when they reimplemented the code in their non-bounds-checked language then that would reintroduce the bug anyway. A formal verification implementation would catch it at authoring time, yes.
- ysleepy 4y ago
  It seems to be an array out of bounds read/write. Rust does bound checks, so this should be covered.
  - GoblinSlayer 4y ago
    All languages except for C do bound checks, you don't need a borrow checker for this.
execveat 4y ago
Rust doesn't prevent integer over/underflows.
- roca 4y ago
  It helps. In Rust debug builds, integer overflows crash -> tests will detect them. In release builds they're not detected by default, but you can add "overflow-checks = true" to the Cargo profile to enable those checks in release builds too if you want.
  - 4y ago

red_admiral 4y ago

To clarify, this only affects EdDSA as far as implementations use SHA-3 to hash a message before applying the signature. The actual elliptic curve operations code seems to be fine.

harveywi 4y ago

It may be helpful to give this vulnerability a name, contributing to public awareness of the issue. For example, The SHA-Shake Redemption.

rurban 4y ago

I find the current polynonce attack much worse: https://news.ycombinator.com/item?id=35048431 https://news.ycombinator.com/item?id=35048431