No more "Generated an Incorrect Block"

[gim]

There's a problem in .sign method that BloodyRookie found and fixed.

I've made test repo, for BloodyRookie's patch:
https://github.com/gimer/curve25519-sign-test

if you want to run the test:

Code: [Select]

nxtcurve\bin> java nxtcurve.TestCurve
      original failed: 132 / 1000
BloodyRookie's failed: 0 / 1000
      original failed: 121 / 1000
BloodyRookie's failed: 0 / 1000
      original failed: 137 / 1000
BloodyRookie's failed: 0 / 1000
      original failed: 133 / 1000
BloodyRookie's failed: 0 / 1000
...

If you want to get rid of  "Generated an Incorrect Block" message, you may try replacing:
"nxt-0.7.2\webapps\root\WEB-INF\classes\nxt\crypto\Curve25519.class"
with a file from:
https://github.com/gimer/curve25519-sign-test/blob/master/bin/nxt/crypto/Curve25519.class

(You're doing this on your own responsibility)

If you want tip someone, tip BloodyRookie, not me.

I can answer any questions, when I"ll be back (~3h)

[Come-from-Beyond]

This solution may leak private key bits until the opposite is proved.

[gim]

To all folks interested, detailed description, of .sign() is  in original BloodyRookie's post:
https://bitcointalk.org/index.php?topic=397183.msg4645132#msg4645132

To understand it, you need some crypto knowledge regarding finite fields and calculation on elliptic curves.
I was one of 4 people sitting on JS implementation of the curve, so it was bit easier for me to understand change that BloodyRookie did.

There is one additional information needed to fully understand what's going on:
First one is following post from sci.crypt, by xmath (author of ORIGINAL C implementation, from which Java version was derived):

Note that there isn't actually such a thing as positive or negative in
a finite field, but you should just pick some definition.  My favorite
is to define elements with the least significant bit set (when fully
reduced) to be negative, and non-zero elements with the least
significant bit clear (when fully reduced) to be positive.  This makes
sure that if x is positive then -x (= p-x) is negative and vice versa.
 - xmath

so basically the check that BloodyRookie is doing here:

Code: [Select]

if ((v[31] & 0x80) != 0)
{
mula_small(v, v , 0, ORDER, 32, 1);
}

check if result of v=(x-h) is negative, and if so multiplies adds it by group order (mentioned by doctorevil),
to get POSITIVE value of (x-h).

That's all the magic to it. I'm going to run NRS with patched Curve from now on.
"Generated an Incorrect Block" must die

[Come-from-Beyond]

I hope people won't run the code patched such the way until we get a proof that it's safe...

https://bitcointalk.org/index.php?topic=345619.msg5039513#msg5039513
https://bitcointalk.org/index.php?topic=345619.msg5039887#msg5039887

[doctorevil]

IMHO, the patch won't leak private key bits. 

It looks totally kosher to me.

Iruu's mention of a possible timing attack doesn't really apply to the patch.  The impact on the timing of sign() that the changes make only leak data about values that are already public.

All this being said, the canonicalization issue should also be fixed.

[BloodyRookie]

I posted a long description on the sign() method in the BTT forum:
https://bitcointalk.org/index.php?topic=345619.msg5060356#msg5060356

[Leteu]

Someone posted the original C version

https://bitcointalk.org/index.php?topic=345619.msg5106688#msg5106688