Can you point to a resource that explains what a carry propagation bug means? I am having a hard time searching for an explanation, especially in the context of how it can cause security issues.
http://blog.skylable.com/2014/05/tweetnacl-carrybit-bug/
StackOverflow had nothing useful with that phrase. Weird. I tried Modular and Montgomery Multiplication as they're important key words that should give you an idea about potential carry issues. I found these decent descriptions in my short Googling:
https://en.wikipedia.org/wiki/Kochanski_multiplication
http://www.hackersdelight.org/MontgomeryMultiplication.pdf
Best I can do with little time and the flood of irrelevant results I saw. Maybe need a thorough write-up on these sorts of things that shows up in Google. At least I serendipitously found a great paper on statically detecting flaws in error propagation:
http://pages.cs.wisc.edu/~liblit/dissertations/crubio.pdf
So, thanks for asking even if not an intended benefit. :)
A carry propagation bug is a special case of a fault attack. Fault attacks, in their most general form, are attacks where an adversary tries to induce an error during a cryptographic computation. The consequences of a fault during a computation are algorithm-specific; here are some examples:
- In RSA, a fault during a decryption or signature operation using a particular (CRT) implementation approach lets the attacker recover the private key [1]. You do this by obtaining an incorrect signature S for some message M you know about, and then recover one of the prime factors of the modulus with the easy computation gcd(S - M^e, N). This is often called the Bellcore attack.
- With elliptic curves, if you can convince a scalar multiplication to work on an incorrect point on the curve (either because the implementation doesn't check the point is valid, or via a hardware fault), you can likewise recover the secret key [2]. The process here is a little more complicated, but no less efficient.
- With AES, if you can trigger a fault in a state byte right before the eighth round, you can recover the full key very easily having both the valid ciphertext and the erroneous one [3]. This attack only makes sense for hardware implementations, since software implementations of symmetric ciphers do not generally leave much space for errors to occur.
In the Golang case, the carry bit failure leads to the Bellcore attack. All you have to do, in principle, is to harvest around 2^25 RSA signatures (and respctive messages) from a buggy target, compute a GCD, and you're done.
[1] https://doi.org/10.1007/3-540-69053-0_4