[noise] Nonce Post-Increment vs Pre-Increment

[Jason A. Donenfeld]

Hi Trevor,

We spoke a while back about nonce++ vs ++nonce. At the time I said I
preferred ++nonce for my implementation particularities, but that was
just me, and you shouldn't take that into consideration. Now, when
trying to adjust my implementation to interop with your rust one, I've
gone back through seeing what it'd be like to do nonce++. It turns out
that it makes the code considerably more complex and less performant.

On the receiving end, I use a 64bit counter to store the greatest
nonce received so far, and an "unsigned long"-size bitfield for a
backtrack of the "sizeof(unsigned long)*8" previous nonces. I thought
I had invented this cleverclever method, and was feeling quite smug
and dandy, when Bellovin pointed out to me that this is actually the
exact algorithm of Appendix C of RFC 2401; there are no original
ideas, alas. But this does give me some assurance that for what I'm
doing, this is the correct algorithm. In this algorithm, since the
64bit counter stores the _greatest_ counter yet received, there is not
room for receiving 0, since the variable is already initialized to it.
Yes, I could add more logic to work around it, but it'd be at the
expense not only of speed, but of considerable complexity and bloat.
Disallowing zero also makes a nice safeguard against wrap-around bugs.
And it appears that the authors of that RFC felt ++nonce was better
too, when in their appendix they add the line, explicitly, "if (seq ==
0) return 0;". So, the wisdom of 1998, and my own personal practical
fumblings around implementing this in a void have yielded the same
results. ++nonce is much better.

On the sending end, I use atomic instructions to "increment, then
return". The kernel's library routines don't even contain a function
for "return, then increment". Yes, I could just subtract one every
time, but in addition to the extra instruction (probably negligible
anyway), this again complicates the wraparound logic and is
burdensome. So for here, too, ++nonce is considerably better.

Not repeating nonces and correctly validating nonces is of tippy-top
importance. If an implementation screws this up, it's gameover.
Therefore, I think it'd be wise for Noise to mandate something that
can be implemented as simply as possible in a wide variety of
settings, to prevent a litany of nonce implementation error CVEs and
the like. Simply changing Noise to be ++nonce instead of nonce++
shaves off a lion's share of code and complexity, and makes auditing
and verifying implementations simpler.

Could we change it to ++nonce, please?

Thanks,
Jason