Some concerns regarding the overflows in modL function

[valerini]

Hey Dmitry,

I have some troubles convincing myself that the modL function won't suffer from overflows. If you have any references to a more detailed description of modL that would be really helpful! In particular I am concerned with its use here:

tweetnacl-js/nacl.js

Line 788 in 1b61c87

modL(sm.subarray(32), x);

Two arrays h and d get multiplied to produce x.

Both h and d are Uint8Array(64) with elements at most 8 bits each and only the first 32 elements non-zero, both elements were reduced mod L.

The resulting x is of type Float64Array(64).

I believe, that the number of bits in each element of the array x is maxed at the following values:
[16, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 19, 19, 19, 19, 18, 18, 17, 16, 0], i.e. the bit length |x[0]| <= 16, |x[1]| <= 17, etc.

Now, the modL function is called on x. And in this line

tweetnacl-js/nacl.js

Line 729 in 1b61c87

x[j] += carry - 16 * x[i] * L[j - (i - 32)];

it can happen that |x[j]| > 32, since |16 * x[i] * L[j - (i - 32)]| <= 4 + 21 + 8 = 33.
But during the bit operation on the next line:

tweetnacl-js/nacl.js

Line 730 in 1b61c87

carry = (x[j] + 128) >> 8;

(x[j] + 128) will get converted to a 32-bits signed integer (according to https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators, Section Bitwise shift operators). This will act as expected only if the length of the number being shifted is at most 32 bits, but why now will it be the case?

[dchest]

Thanks for the analysis, I believe you're correct! It should be replaced with division. I'll fix it tomorrow morning.

[dchest]

It seems to me that it array x maxes out at 20 bits due to this reduction of h:

tweetnacl-js/nacl.js

Line 778 in 1b61c87

reduce(h);

But I'm half-asleep, so I'll recheck tomorrow (even if so, still worth fixing if modL is to be used externally).

[dchest]

Here's a test with maximal values for each input:

var L = new Float64Array([0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x10]);

function modL(r, x) {
  var carry, i, j, k;
  for (i = 63; i >= 32; --i) {
    carry = 0;
    for (j = i - 32, k = i - 12; j < k; ++j) {
      x[j] += carry - 16 * x[i] * L[j - (i - 32)];
      carry = (x[j] + 128) >> 8;
      if (Math.floor((x[j] + 128) / 256) != carry) throw 'overflow';
      x[j] -= carry * 256;
    }
    x[j] += carry;
    x[i] = 0;
  }
  carry = 0;
  for (j = 0; j < 32; j++) {
    x[j] += carry - (x[31] >> 4) * L[j];
    carry = x[j] >> 8;
    x[j] &= 255;
  }
  for (j = 0; j < 32; j++) x[j] -= carry * L[j];
  for (i = 0; i < 32; i++) {
    x[i+1] += x[i] >> 8;
    r[i] = x[i] & 255;
  }
}

function reduce(r) {
  var x = new Float64Array(64), i;
  for (i = 0; i < 64; i++) x[i] = r[i];
  for (i = 0; i < 64; i++) r[i] = 0;
  modL(r, x);
}

var x=new Float64Array(64);
var h=new Uint8Array(64).fill(0xff);
var d= new Uint8Array(64).fill(0xff);
d[0] &= 248;
d[31] &= 127;
d[31] |= 64;

console.log('max d:', d)

console.log('max h before reduction:', h)
reduce(h);
console.log('max h after reduction:', h)
for (var i = 0; i < 32; i++) {
    for (var j = 0; j < 32; j++) {
      x[i+j] += h[i] * d[j];
    }
}
console.log('max x values:', x)
console.log('max x bits:', x.map(v => Math.ceil(Math.log2(v))))

var sm=new Uint8Array(32).fill(255);
modL(sm, x)

The results are:

max d: Uint8Array(64) [
  248, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 127, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255
]
max h before reduction: Uint8Array(64) [
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255
]
max h after reduction: Uint8Array(64) [
    0,  15, 156,  68, 227,  17,   6, 164,  71, 147, 133, 104,
  167,  27,  14, 208, 101, 190, 245,  23, 210, 115, 236, 206,
   61, 154,  48, 124,  27,  65, 153,   3,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0
]
max x values: Float64Array(64) [
       0,   3720,  42513,  60469, 117241, 123046,
  124653, 165367, 184123, 221076, 255089, 281812,
  323956, 331821, 335482, 387164, 413668, 461495,
  523585, 531004, 583245, 613235, 672568, 725308,
  741878, 780497, 793479, 824567, 832131, 848440,
  886839, 888654, 886755, 864882, 836366, 798674,
  767669, 764742, 742988, 713072, 685239, 649546,
  619343, 584759, 560094, 554873, 526471, 487127,
  449980, 394490, 360431, 330630, 289240, 244427,
  188087, 154117, 126658, 100956,  78988,  59784,
   48035,  20196,    381,      0
]
max x bits: Float64Array(64) [
  -Infinity, 12, 16,        16, 17,
         17, 17, 18,        18, 18,
         18, 19, 19,        19, 19,
         19, 19, 19,        19, 20,
         20, 20, 20,        20, 20,
         20, 20, 20,        20, 20,
         20, 20, 20,        20, 20,
         20, 20, 20,        20, 20,
         20, 20, 20,        20, 20,
         20, 20, 19,        19, 19,
         19, 19, 19,        18, 18,
         18, 17, 17,        17, 16,
         16, 15,  9, -Infinity
]

If you comment-out reduce(h), it indeed overflows. As it is used in crypto_sign, though, it doesn't seem to me it will ever overflow (modL is also used in reduce, but in both instances where it's called, the max values are 255.)

[valerini]

Hi Dmitry,

Thanks for your quick replies, sorry for the delay. Very helpful of you to put together this test! How about this slightly modified variant of the test, here h is reduced from the start (i.e. reduce(h) does not change h), but some components of h are at max number of set bits (i.e. at 255):

instead of line

var h=new Uint8Array(64).fill(0xff);

do

var h=new Uint8Array(64).fill(0xff);
h[31] &= 15;
for (var i = 0; i < 32; i++) {
    h[32+i] = 0;
}

then the output will be:

max d: Uint8Array [
  248, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 127, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255,
  255
]
max h before reduction: Uint8Array [
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255,  15,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0
]
max h after reduction: Uint8Array [
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
  255, 255, 255, 255, 255, 255, 255,  15,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
    0,   0,   0,   0
]
max x values: Float64Array [
    63240,  128265,  193290,  258315,  323340,  388365,
   453390,  518415,  583440,  648465,  713490,  778515,
   843540,  908565,  973590, 1038615, 1103640, 1168665,
  1233690, 1298715, 1363740, 1428765, 1493790, 1558815,
  1623840, 1688865, 1753890, 1818915, 1883940, 1948965,
  2013990, 1986855, 1921935, 1856910, 1791885, 1726860,
  1661835, 1596810, 1531785, 1466760, 1401735, 1336710,
  1271685, 1206660, 1141635, 1076610, 1011585,  946560,
   881535,  816510,  751485,  686460,  621435,  556410,
   491385,  426360,  361335,  296310,  231285,  166260,
   101235,   36210,    1905,       0
]
max x bits: Float64Array [
  16, 17, 18,        18, 19,
  19, 19, 19,        20, 20,
  20, 20, 20,        20, 20,
  20, 21, 21,        21, 21,
  21, 21, 21,        21, 21,
  21, 21, 21,        21, 21,
  21, 21, 21,        21, 21,
  21, 21, 21,        21, 21,
  21, 21, 21,        21, 21,
  21, 20, 20,        20, 20,
  20, 20, 20,        20, 19,
  19, 19, 19,        18, 18,
  17, 16, 11, -Infinity
]

[dchest]

Oh, thanks! Also, my test missed that x contained r. Fixing.

[dchest]

@valerini could you please review #188 ? Thanks!

[valerini]

Looks good, thanks! Agree, for the rest of the modL it should be ok to have the binary operations. I will look through the modL a bit more, but hope it's all good now.

[dchest]

Awesome, thanks a lot! I'm releasing the update soon.