[ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures - page 3.

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: Come-from-Beyond on January 15, 2014, 05:36:55 AM

Quote from: BloodyRookie on January 15, 2014, 05:34:00 AM

Quote from: Come-from-Beyond on January 15, 2014, 04:03:00 AM

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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.

Jaguar0625

sr. member

Activity: 299

Merit: 250

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

.

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: gimre on January 15, 2014, 02:46:21 AM

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

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: gimre on January 15, 2014, 02:46:21 AM

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

I think I figured it out.

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: BloodyRookie on January 15, 2014, 05:34:00 AM

Quote from: Come-from-Beyond on January 15, 2014, 04:03:00 AM

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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

hero member

Activity: 687

Merit: 500

Quote from: Come-from-Beyond on January 15, 2014, 04:03:00 AM

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: gimre on January 15, 2014, 05:05:30 AM

Quote from: Come-from-Beyond on January 15, 2014, 04:03:00 AM

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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.

gimre

legendary

Activity: 866

Merit: 1002

Quote from: Come-from-Beyond on January 15, 2014, 04:03:00 AM

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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
)

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 14, 2014, 10:55:17 AM

Quote from: hoax on January 14, 2014, 07:08:58 AM

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.

Quote from: gimre on January 15, 2014, 02:46:21 AM

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).

Come-from-Beyond

legendary

Activity: 2142

Merit: 1010

Newbie

Quote from: Jaguar0625 on January 14, 2014, 08:24:50 PM

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.

gimre

legendary

Activity: 866

Merit: 1002

Quote from: BloodyRookie on January 15, 2014, 01:20:04 AM

Quote from: gimre on January 14, 2014, 04:49:45 PM

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:

Quote from: gimre on January 14, 2014, 08:35:05 AM

Quote from: BloodyRookie on January 13, 2014, 01:12:23 PM

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

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: gimre on January 14, 2014, 04:49:45 PM

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?

Jaguar0625

sr. member

Activity: 299

Merit: 250

Quote from: hoax on January 14, 2014, 04:56:35 AM

Quote from: Jaguar0625 on January 13, 2014, 09:14:09 AM

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?

Jaguar0625

sr. member

Activity: 299

Merit: 250

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

sr. member

Activity: 299

Merit: 250

Quote from: Jaguar0625 on January 14, 2014, 06:09:26 PM

Quote from: BloodyRookie on January 13, 2014, 09:28:45 AM

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

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.

gimre

legendary

Activity: 866

Merit: 1002

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

sr. member

Activity: 299

Merit: 250

Quote from: BloodyRookie on January 13, 2014, 09:28:45 AM

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

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.

gimre

legendary

Activity: 866

Merit: 1002

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

My current times:

Code:

 priv in:  210, 196, 255, 153, 6, 54, 138, 84, 232, 24, 222, 198, 233, 178, 192, 61, 46, 110, 249, 92, 37, 250, 62, 206, 16, 71, 242, 136, 153, 234, 194, 151, 
genPubWithS: 58.000ms 
    pub:  18, 173, 235, 164, 40, 128, 113, 104, 72, 242, 216, 5, 56, 18, 81, 45, 182, 177, 242, 122, 147, 174, 222, 226, 103, 224, 136, 35, 255, 173, 112, 52,
   sess:  74, 142, 86, 157, 36, 54, 116, 31, 195, 152, 94, 81, 151, 234, 6, 58, 52, 159, 55, 156, 194, 136, 214, 121, 86, 234, 144, 80, 73, 255, 6, 14,
msghash:  224, 94, 33, 147, 82, 148, 111, 121, 162, 115, 175, 49, 25, 9, 193, 102, 90, 114, 177, 246, 58, 178, 213, 252, 205, 21, 160, 52, 210, 239, 202, 17,
genPub: 30.000ms
      x:  56, 202, 26, 238, 143, 109, 13, 46, 68, 242, 230, 144, 117, 26, 35, 82, 185, 104, 189, 171, 185, 231, 219, 160, 226, 15, 25, 173, 12, 47, 149, 72,
      Y:  255, 86, 46, 149, 26, 72, 141, 90, 42, 124, 209, 211, 33, 126, 7, 149, 222, 249, 90, 197, 87, 173, 210, 15, 153, 198, 14, 116, 91, 27, 139, 99,
signing:
    sha:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
sign: 0.000ms
  vh[0]:  38, 92, 148, 183, 122, 6, 174, 55, 94, 129, 218, 168, 118, 156, 21, 98, 10, 23, 24, 244, 169, 75, 62, 154, 5, 88, 16, 114, 241, 17, 201, 1, 
  vh[1]:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
verify: 49.000ms
 hashing sig:  255, 86, 46, 149, 26, 72, 141, 90, 42, 124, 209, 211, 33, 126, 7, 149, 222, 249, 90, 197, 87, 173, 210, 15, 153, 198, 14, 116, 91, 27, 139, 99,
h_verify:  77, 170, 60, 190, 71, 254, 202, 56, 39, 211, 119, 32, 153, 190, 64, 97, 46, 28, 8, 115, 115, 149, 16, 121, 182, 69, 186, 159, 37, 229, 120, 65,
 verification =?= vh[1]:
ALL TIME: 160.000ms

Code:

 priv in:  212, 215, 120, 183, 50, 2, 38, 73, 6, 176, 105, 222, 132, 202, 18, 161, 165, 186, 129, 60, 222, 69, 25, 30, 201, 220, 102, 201, 246, 118, 112, 127, 
genPubWithS: 62.000ms
    pub:  223, 120, 104, 231, 254, 142, 4, 197, 103, 120, 80, 42, 121, 163, 172, 175, 112, 183, 92, 53, 174, 174, 106, 175, 52, 132, 33, 254, 147, 202, 189, 89,
   sess:  1, 235, 206, 226, 194, 0, 108, 59, 21, 56, 112, 230, 43, 5, 58, 166, 186, 14, 192, 10, 136, 169, 0, 168, 141, 157, 253, 109, 92, 164, 141, 6,
msghash:  224, 94, 33, 147, 82, 148, 111, 121, 162, 115, 175, 49, 25, 9, 193, 102, 90, 114, 177, 246, 58, 178, 213, 252, 205, 21, 160, 52, 210, 239, 202, 17,
genPub: 31.000ms
      x:  160, 134, 16, 204, 227, 72, 60, 80, 61, 72, 20, 184, 27, 50, 91, 144, 58, 143, 93, 94, 182, 218, 63, 185, 180, 103, 235, 92, 143, 69, 250, 90,
      Y:  25, 68, 99, 3, 220, 120, 0, 254, 135, 235, 145, 49, 33, 175, 178, 51, 85, 109, 83, 123, 79, 242, 47, 246, 21, 239, 130, 81, 185, 235, 67, 122,
signing:
    sha:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176,
sign: 1.000ms 
  vh[0]:  89, 34, 99, 164, 248, 105, 148, 205, 219, 19, 132, 9, 153, 239, 28, 161, 205, 194, 27, 242, 214, 227, 85, 241, 251, 224, 148, 72, 150, 64, 18, 15, 
  vh[1]:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176, 
verify: 50.000ms 
 hashing sig:  25, 68, 99, 3, 220, 120, 0, 254, 135, 235, 145, 49, 33, 175, 178, 51, 85, 109, 83, 123, 79, 242, 47, 246, 21, 239, 130, 81, 185, 235, 67, 122, 
h_verify:  49, 103, 140, 21, 153, 144, 6, 45, 72, 166, 26, 232, 129, 182, 10, 195, 121, 74, 78, 165, 215, 241, 27, 222, 250, 58, 48, 194, 134, 161, 137, 176, 
 verification =?= vh[1]:
ALL TIME: 168.000ms

Is that fast or slow?

(above I'm doing equivalent of java code):

Code:

Curve25519.keygen(pub,sigPriv,priv); // generate pub and sigPriv  // time1
..
Curve25519.keygen(sigPub, null, sigPriv); // generate sigPub from sigPriv  // time2   
..
Curve25519.sign(v, hash1, hash2, sigPriv); // return (v, hash1) as a sig   // time3

Curve25519.verify(Y, v, hash1, pub); // generate Y  // time4
hash(hash(message)+Y) == hash1

)

BloodyRookie

hero member

Activity: 687

Merit: 500

Quote from: hoax on January 14, 2014, 07:08:58 AM

My js ported directly from this, not from Nxt sources

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

Quote from: hoax on January 14, 2014, 07:08:58 AM

Quote from: BloodyRookie on January 14, 2014, 05:47:58 AM

The only thing not working is the is_negative function, right?

Not only, as i can see.

What else do you think is not working?

hoax

newbie

Activity: 36

Merit: 0

Quote from: BloodyRookie on January 14, 2014, 05:47:58 AM

Quote from: hoax on January 14, 2014, 04:56:35 AM

Sources of what?

https://code.google.com/p/gvl/source/browse/crypt/curve25519.cpp?r=3c26171fd2d914484f03b7b63ca2065fa03a7aa3

My js ported directly from this, not from Nxt sources

And about "helloworld" false result: CfB said that this is normal behavior :O

Quote from: BloodyRookie on January 14, 2014, 05:47:58 AM

Quote from: hoax on January 14, 2014, 04:56:35 AM

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.

The only thing not working is the is_negative function, right?

Not only, as i can see.

Topic: [ANN] Nxt Bounty for working JavaScript code that signs and verifies signatures - page 3. (Read 8451 times)