A Go implementation of Poly1305 that makes sense

[zimmerfrei]

One reason this cannot be translated into a portable C version while retaining its compactness (and readability) is the lack of support for carry/borrow chains.

In Go, bits.Add64 takes as input and returns the carry.

In C, there are some constructs that modern compilers will recognize as patterns people use to extract the carry, but it is a hit-and-miss.

Even compiler-specific intrinsics are a few and far between, inefficient or even broken.

[boomlinde]

If you look into the implementations of Add64/Sub64/Mul64 you'll see that it's not a lot of code and that there is nothing magical about them. They can just as easily be implemented in C in some 30 lines of code. Because they concern unsigned integers only there is no UB to consider on overflow/carry.

[tarikjn]

Great write-up, I haven't dug into understanding the whole code yet, but perhaps someone can answer this for me: can the code be made even simpler using Go's bignum: big.Int?

[CaliforniaKarl]

One concern may be the lack of a constant-time guarantee. If there are any optimizations that run differently depending on the numbers involved, then that may be an opening to a side-channel attack.

[olliej]

Big integer libraries are written to be as fast as possible, this pretty much guarantees the evaluation of primitive operations is not constant time.

[cyphar]

Possibly, but I would assume it would would be too slow. While big does have assembly implementations, it is designed to handle very large numbers -- ~int128 sized numbers are probably too small for it to be efficient. I could be wrong though.

[jacobvosmaer]

I'm not sure but I suspect the algorithm contains optimizations that require direct access to the "limbs" of the big integers.

Or perhaps it's about avoiding allocations?

[simonhorlick]

I find a lot of go libraries are very well commented and very accessible, but the standard library and especially the crypto stuff is very sparsely commented.