I'll look up this carry propagation business, but again, this looks like a mundane correctness issue (with possibly tragic consequences), though it is hard to assess without looking at intermediate results (I have).
Also, didn't the carry propagation bug reports come with failing tests vectors? Or are they hard to find even if one knows of the bug?
> the only thing I care about is the idea that if you pass test vectors and Valgrind is OK with your binary, you're probably OK. No!
Definitely agree. Even test vectors + safe Rust aren't enough. Which is why I added random comparison tests with libsodium (for every possible length input between 0 and a couple times the size of the block), and property based tests.
I'm still a bit uneasy about carry propagation in Poly1305, but I really checked the hell out of my code.
I originally didn't. But when I noticed it was designed to facilitate 32-bit limbs, I couldn't resist. The result is pretty simple.
I also figured it would perform well, though it currently seems to be 20% slower than Donna (32-bit version). I'll try to find why (I can think of 2 causes: sub-optimal loading code, and crappy data flow in the main carry operation. If it's the latter, I'll use the Donna implementation.)
EDIT: I tweaked the loading code again, it's even faster now. I'm now 7% than poly-donna-32 (and 5% faster than libsodium). My implementation is also simpler. I'm keeping it.
> go do the research about how these bugs are found and exploited,
I'd have to know how.
My first searches turned up no methodology —just instances of such bugs being found. And again, this is just a correctness issue. One just have to prove the whole thing works as intended (even informally). I wouldn't trust myself to do it for curve25519, but poly1305 was doable.
Also, didn't the carry propagation bug reports come with failing tests vectors? Or are they hard to find even if one knows of the bug?
> the only thing I care about is the idea that if you pass test vectors and Valgrind is OK with your binary, you're probably OK. No!
Definitely agree. Even test vectors + safe Rust aren't enough. Which is why I added random comparison tests with libsodium (for every possible length input between 0 and a couple times the size of the block), and property based tests.
I'm still a bit uneasy about carry propagation in Poly1305, but I really checked the hell out of my code.