[ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures

[gimre]

I think 25% is probably overestimate, but curve edit (I mean curve25519 ofc) as a function is not surjective, so one should expect that...

[Jaguar0625]

hoax, did you test the original cpp code? I tried but I got funny results

I wouldn't be shocked if there is a bug in the Java code. Cfb's expectation that ~25% of signatures can't be verified is surprising to me. Also, the fact that the C++ code is using uint8 types whereas the JavaScript code is using longs for essentially the same thing is suspicious.

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

[Jaguar0625]

I put together a small test corpus in my repo https://github.com/Jaguar0625/JavaScriptNrs that you guys can use to test your implementations for correctness. (Basically black box testing where i validate the inputs and outputs are the same as the original Java code):

Just run the following after swapping in your implementation:

Code:

node test.js

Not sure if this helps but i thought i'd share .

[Jaguar0625]

I have a few ideas about how to optimize the long class, but I need to spend time with a profiler first and see where all the time is being spent. Has anyone tried this already?

Look at my repo. I removed from Long all codepathsthat useless for long10 implementation. Also added multiplySmall, which faster when we multiple int64 by 1,2,4,9,19,38,76.

Maybe we can optimize further but with loss of readability or insignificantly

As i can seen now, https://github.com/rev22/curve255js have nice performance only for one reason: it have simplified math, which can't work with negative numbers. This is reason, why "verify" used this math doesn't work.

I see. It looks like you removed the long 10 class and optimized the google long class. Are you getting good enough performance or thinking of scrapping the Long class altogether?

[BloodyRookie]

My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation.

So what's the logic behind is_negative?

[gimre]

My code is finally working uff, took me a lot to figure out how to do that is_negative crap in my representation.

So what's the logic behind is_negative?

I've actually partially* answered to that in code flaws thread:

Can you please ask that guy what the reasoning behind the strange is_negative(long10 x) function is? It's kind of hard to understand.

I'm also interested in this.
a) why there is is_overflow at all... (I thought it'd be simpler to have element of long10 have always reduced mod q....)
b) the second part is magic, as there shouldn't be something like "negative", so I assume job of that xor is to split values into two groups... (why?)

(edit: added is_negative, snippet)

Code:

		/* checks if x is "negative", requires reduced input */
		private static final int is_negative(long10 x) {
			return (int)(((is_overflow(x) || (x._9 < 0))?1:0) ^ (x._0 & 1));
		}

I might shed some more light upon that, but probably not today (UTC)

edit:
Oh, P.S.

I'm getting quite terrible results from node.js - last time I checked they were 10 times worse than ones from the browser...
I would appreciate if anyone would share his (her?) results from within the browser

[Come-from-Beyond]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

[hoax]

My js ported directly from this, not from Nxt sources

ok, but did you actually test the c++ program?

No, compared only with Nxt sources behavior.

I'm getting quite terrible results from node.js - last time I checked they were 10 times worse than ones from the browser...
I would appreciate if anyone would share his (her?) results from within the browser

CPU - core i5 2.6ghz

Chrome 32beta:
crypto_sign - 64ms, crypto_verify - 32ms

Node.js:
crypto_sign - 88ms, crypto_verify - 44ms

Firefox 26:
crypto_sign - 80ms, crypto_verify - 60ms

Results depends on "how you're measure" them

Sometimes browser can be meditative and run JS slowly and i get worst results(~ x2 slower). And if i call this functions in 100x cycle then avg time is better(36ms, 29ms on chrome).

[gimre]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

That depends on algo.
In case of Nxt's EC-KCDSA "k" value is picked not choosen randomly,
So if you feed it with the same data, sig should be te same...

(k is calculated from 1360-1365, that's Y in NXT code
https://bitbucket.org/JeanLucPicard/nxt-public/src/4073c21098076d3469b3f74d49e73ffabe3a2001/Nxt.java?at=master#cl-1360
and it's based on "sig priv key" (s based on user's pub key) and message
)

[Come-from-Beyond]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

That depends on algo.
In case of Nxt's EC-KCDSA "k" value is picked not choosen randomly,
So if you feed it with the same data, sig should be te same...

(k is calculated from 1360-1365, that's Y in NXT code
https://bitbucket.org/JeanLucPicard/nxt-public/src/4073c21098076d3469b3f74d49e73ffabe3a2001/Nxt.java?at=master#cl-1360
and it's based on "sig priv key" (s based on user's pub key) and message
)

Stick to NRS code.

[BloodyRookie]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

What? Same message, same secret phrase ==> same signature.
Or I am missing something?

One question: are timing attacks an issue for the client software (i.e. the javascript software)?

[Come-from-Beyond]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

What? Same message, same secret phrase ==> same signature.
Or I am missing something?

U r, let's go back to the topic. Don't pay attention to this part now.

[BloodyRookie]

I might shed some more light upon that, but probably not today (UTC)

I think I figured it out.

[BloodyRookie]

I would appreciate if anyone would share his (her?) results from within the browser

I am not speed testing the bare Curve25519 functions but the getPublicKey, sign and verify function from Cryto class (converted to javascript).
On my i7 950 3.07GHz (you need to tell us what cpu u r using) using firefox v26 I get:

Code:

Speed test
Javascript needs 21.66ms/getPublicKey
Javascript needs 46.92ms/sign
Javascript needs 39.34ms/verify
Finished

[Jaguar0625]

2.4 GHz Intel Core i5

Chrome (initial approach, which was a straight port of the Java code using the Long class):

Code:

Javascript needs 167.5ms/getPublicKey
Javascript needs 332.9ms/sign
Javascript needs 272.4ms/verify

Although, switching the getPublicKey function to the one from the native JS implementation dropped getPublicKey to 9.8ms [for some reason this change had a much larger impact in the browser than in node; I'm not sure why because they're both using V8].

I think @BloodyRookie has the right idea .

[Jaguar0625]

Actually, there might be a bug in the C++ code. I compiled it and ran a few tests with sign, but the signature that gets generated is different each time i run the program (typically the sign of an uninitialized variable somewhere). The problem appears to happen somewhere in divmod.

It's a normal behavior, not a bug, don't waste too much time on that.

What? Same message, same secret phrase ==> same signature.
Or I am missing something?

U r, let's go back to the topic. Don't pay attention to this part now.

Since the Java code is producing deterministic signatures, I'm assuming you want the JavaScript port to have the same behavior?

If not, that would potentially open up other areas for optimization.

[gimre]

I would appreciate if anyone would share his (her?) results from within the browser

I am not speed testing the bare Curve25519 functions but the getPublicKey, sign and verify function from Cryto class (converted to javascript).
On my i7 950 3.07GHz (you need to tell us what cpu u r using) using firefox v26 I get:

Code:

Speed test
Javascript needs 21.66ms/getPublicKey
Javascript needs 46.92ms/sign
Javascript needs 39.34ms/verify
Finished

glad you figured, I also went <100ms for whole sig+verify, will post details later

(the thing is I operate on data in bit different format, so I'll have to preprocess it first... and that'll have penalty for sure)

[BloodyRookie]

@gimre: On what kind of cpu r u testing, gimre?
@Jaguar0625: 9.8ms/getPublicKey with javascript?

[hoax]

What else do you think is not working?

I was wrong But also confused by "It's a normal behavior"(c)CfB

[Jaguar0625]

@Jaguar0625: 9.8ms/getPublicKey with javascript?

Yes, but don't worry, I ran your code too and it was faster . These are the results for your code on my machine (i am using the test js/html from your repo):

Code:

Javascript needs 5.5ms/getPublicKey
Javascript needs 12ms/sign
Javascript needs 9.5ms/verify

I suspect you're seeing slower numbers on your machine because you're testing in FireFox. AFAIK, Chrome has a faster JavaScript interpreter.