Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

eprint.iacr.org

Post reply on HN
Print view View original

41–49 of 49 posts

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

#41

Post by seanw444 »

miohtama wrote: post #36
rurban wrote: post #19

Earlier quoted context omitted.

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 paragraph, and "Finding Bugs in Cryptographic Hash Function…

Hopefully people working on hashes and codecs will use Rust in the future, so Valgrinding and such are less needed.

Let me cross that one off my daily bingo card...

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

#42

Post by pornel »

roca wrote: post #32
execveat wrote: post #26

Earlier quoted context omitted.

Rust doesn't prevent integer over/underflows.

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.

Additionally the only type allowed for array indexing and buffer slicing is usize, equivalent of size_t, and it's 64-bit on 64-bit platforms.

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

#43

Post by nayuki »

IYasha wrote: post #17
loup-vaillant wrote: post #16

Earlier quoted context omitted.

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…

umm... But how (uint - uint) can be negative? I thought it would warp around 0 into (UINT_MAX - leftovers).

So, (unsigned int) - (unsigned int) → (unsigned int) is guaranteed on every platform.

But relevant to the bad SHA-3 code, the resulting type of size_t - size_t can be surprising. First, size_t is not guaranteed to have any relation with unsigned int; it could be narrower, the same, or wider. For example, size_t could map to unsigned short, unsigned int, unsigned long, or unsigned long long.

If size_t is defined as unsigned short (note that size_t must be at least 16 bits), and short is 16 bits wide, and int is 32 bits wide, then the calculation of size_t - size_t will be promoted to (signed int) - (signed int), and thus the result will have the type signed int.

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

#44

Post by jonstewart »

loup-vaillant wrote: post #35
jonstewart wrote: post #30

Earlier quoted context omitted.

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.

Here's the definite answer: #include 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…

Thank you, I wanted to do this last night but haven’t had the time.

I think it’s perfectly fine for an algorithm contest not to require a bugfree implementation… but I also feel that if we’re going to standardize on a cryptographic algorithm, throwing all the tools and formal methods we can at it during development of the reference implementation makes a lot of sense.

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

#45

Post by GoblinSlayer »

ysleepy wrote: post #28
Arnavion wrote: post #25

Earlier quoted context omitted.

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.

It seems to be an array out of bounds read/write. Rust does bound checks, so this should be covered.

All languages except for C do bound checks, you don't need a borrow checker for this.

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

#46

Post by mm2023 »

pas wrote: post #27
eulgro wrote: post #2

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.

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 ... and it's not like there wasn't a FOSS test suite for this.

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!

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

#48

Post by touisteur »

rurban wrote: post #38
miohtama wrote: post #36

Earlier quoted context omitted.

Hopefully people working on hashes and codecs will use Rust in the future, so Valgrinding and such are less needed.

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-safere... * https://github.com/GaloisInc/hacrypto * https://github.com/fmlab…

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-...

* https://blog.adacore.com/sparknacl-two-years-of-optimizing-c...

* 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...

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

#49

Post by roca »

1over137 wrote: post #40
roca wrote: post #32

Earlier quoted context omitted.

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.

>In Rust debug builds, integer overflows crash That's true with C/C++ compilers too, if you want, using UBSan.

Unsigned integer overflow is not undefined behavior in C++ so won't be caught by UBSan.

Also, UBSan is more overhead than turning on Rust's overflow checking.

Post reply on HN