This is the description of an arithmetic bug I found in one of the operations used during the computations of Curve25519 scalar multiplications in the TweetNaCl library.
The culprit is the code handling the final reduction modulo 2255 - 19 located in the function
pack25519(). The following snippet presents the original code (version 20131229) of this function:
sv pack25519(u8 *o, const gf n)
This bug is triggered when the last limb
n of the input argument
n of this function is greater or equal than
0xffff. In these cases the result of the scalar multiplication is not reduced as expected resulting in a wrong packed value. This code can be fixed simply by replacing
Examples triggering this error are easy to generate. For instance, here is a case where a carefully selected scalar
n when multiplied with the base point
(9, y) in the Montgomery curve representation and using TweetNaCl's
scalarmult_base() function outputs a wrong result:
Scalar value n:
Wrong result obtained from bugged scalarmult_base(n) in pack25519():
Expected result obtained from ref implementation:
This error should be relatively frequent, it happens around or a bit less than one time for every 216 computations for computations with different scalar values or different points. However, beyond the wrongness of the resulting x-coordinate, and because this error happens at the end of computations steps there is no risk it could lead to greater damages like for instance revealing bits of user's secret. So just update your code with the new version (20140427) and you'll be fine.