## Arithmetic Bug in TweetNaCl

###### 28 April 2014 ∞

This is the description of an arithmetic bug I found^{1} 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 2^{255} - 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) { int i,j,b; gf m,t; FOR(i,16) t[i]=n[i]; car25519(t); car25519(t); car25519(t); FOR(j,2) { m[0]=t[0]-0xffed; for(i=1;i<15;i++) { m[i]=t[i]-0xffff-((m[i-1]>>16)&1); m[i-1]&=0xffff; } m[15]=t[15]-0x7fff-((m[14]>>16)&1); b=(m[15]>>16)&1; m[15]&=0xffff; sel25519(t,m,1-b); } FOR(i,16) { o[2*i]=t[i]&0xff; o[2*i+1]=t[i]>>8; } }

This bug is triggered when the last limb `n[15]`

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 `m[15]&=0xffff;`

by `m[14]&=0xffff;`

.

Examples triggering this error are easy to generate. For instance, here is a case where a carefully selected^{2} 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: 76f6507a08e5d77a9a7b316d93cbb59b afa2e13d1f84d181a35779e7fc471d19 Wrong result obtained from bugged scalarmult_base(n) in pack25519(): 829253d8647cd88e3fb76358cfef0a91 51aa8e7189fb6326dfb0603f6bff0000 Expected result obtained from ref implementation: 6f9253d8647cd88e3fb76358cfef0a91 51aa8e7189fb6326dfb0603f6bffff7f

This error should be relatively frequent, it happens around or a bit less than one time for every 2^{16} computations for computations with different scalar values or different points. However, beyond the wrongness of the resulting x-coordinate^{3}, 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.