4 ms·

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 so

by 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!

by eulgro 4y ago

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!