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.
A Vulnerability in Implementations of SHA-3, Shake, EdDSA
31–40 of 49 posts
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#32I 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.
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.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#33Is 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, serious…
I'm going with "neither".
It's true that Snowden revealed the NSA had their fingers in NIST's cryptographic standards team, with Dual-EC a specific example that is considered suspicious since the revelations. So a suspicion of malice is not completely unfounded, but as far as I can tell, this code was written by the Keccak team not NIST itself, and for any claim of "they're NSA stooges", I would need evidence.
It also seems to me that the Keccak team are not stupid people. That leaves "honest mistake" as the most likely explanation.
There are lots of studies on human behaviour that show a competent and diligent human will mess up every Nth time they perform a routine task; some forms of probabilistic risk analysis take N = 10^3 as a lower bound for this.
There is a long history of railroad operation in the UK (who invented the steam train after all) where occasionally, a signaller would send an express onto a line where they'd forgotten that the local was standing, or two trains head-on down a single line in opposite directions. This led to the development of interlockings and token working systems as technological solutions to mitigate the risks of human error, and later on to today's computerised safety systems, because signallers are (almost always) neither stupid nor malicious, but still human. The same can be said for programmers.
(As I understand, the recent train disaster in Greece was on a line where there should have been interlocking in place, but it wasn't active.)
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#34I 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.
Rust doesn't prevent integer over/underflows.
Yes, but crypto should probably use under/overflow safe arithmetic, which the rust standard library allows for.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#35Earlier quoted context omitted.
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.
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;
}
$ ./a.out
9876543210
9876543210 (llu)
1286608618 (u)
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
unsigned u = (unsigned)llu;
long long unsigned u = (unsigned)llu;
printf("%llu (u)\n", u);
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.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#36I 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'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.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#37Earlier 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.
overflow-checks=true is already present in many cryptographic and blockchain Cargo packages, as its trade-offs are worth it Vs. a human error.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#38Earlier 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.
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-iis/cryptoline
* https://github.com/mit-plv/fiat-crypto/ (Bedrock2)
* https://github.com/hacl-star/hacl-star (F* and ValeCrypt)
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#39It may be helpful to give this vulnerability a name, contributing to public awareness of the issue. For example, The SHA-Shake Redemption.
Re: A Vulnerability in Implementations of SHA-3, Shake, EdDSA
#40Earlier 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.
>In Rust debug builds, integer overflows crash
That's true with C/C++ compilers too, if you want, using UBSan.