Lots of people are still complaining about it.
There is only one method left, that is Curve25519.sign(), so the bug must inside that method. Let's take a look at it.
It calculates (x-h)*s mod q.
Looks legit? Not! If x
reduction will not return the desired value. We have to take care of the case x
test for a negativ result by looking at the highest bit and, in case it is set, add q to the result making it positive (If you don't reduce x and h mod q then you can't use
mula_small because you can't test the result by looking at the highest bit). So the new method Curve25519.sign() should look like this:
private static final void reduce(byte[] x) {
byte[] tmp=new byte[32];
divmod(tmp, x, 32, ORDER, 32);
if ((x[31] & 0x80) != 0)
{
// x is negativ, add q to it
mula_small(x, x , 0, ORDER, 32, 1);
}
}
public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
// v = (x - h) s mod q
int w, i;
byte[] h1 = new byte[32], x1 = new byte[32];
byte[] tmp1 = new byte[64];
byte[] tmp2 = new byte[64];
// Don't clobber the arguments, be nice!
cpy32(h1, h);
cpy32(x1, x);
// Reduce modulo group order
reduce(h1);
reduce(x1);
// v = x1 - h1
// If v is negative, add the group order to it to become positiv.
mula_small(v, x1, 0, h1, 32, -1);
if ((v[31] & 0x80) != 0)
{
mula_small(v, v , 0, ORDER, 32, 1);
}
// tmp1 = (x-h)*s mod q
mula32(tmp1, v, s, 32, 1);
divmod(tmp2, tmp1, 64, ORDER, 32);
for (w = 0, i = 0; i < 32; i++)
w |= v[i] = tmp1[i];
return w != 0;
}
I have tested the new sign() method with 10000 random pass phrases and messages and the verification has not failed a single time!
The bug I found is not the last flaw but nevertheless it is an anoying bug making verify() fail sometimes.
Are smart people besides CIYAM thinking about it?
