Pages:
Author

Topic: Nxt source code flaw reports - page 20. (Read 113369 times)

legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 08:22:26 AM
Btw, this has just come to my mind. Noone did an audit of Crypto and Curve25519 code yet. We would pay a reward for found flaws.


The comments in the code
   /* Ported  .............. 23/02/08.
    * Original: http://cds.xs4all.nl:8081/ecdh/
    */
   /* Generic 64-bit integer implementation of Curve25519 ECDH
    * ..... 200608242056
    * Public domain.
    *

cause such impression that the code is old enough and likely reviewed enough, i.e. cleared from errors.
And so that would have been a good block to skip over ;-)

Or have you inserted there new flaws ...


This was taken from https://code.google.com/p/curve25519-java/

If u see no difference than u could assume that there wasn't a flaw injected.
hero member
Activity: 834
Merit: 524
Nxt NEM
January 13, 2014, 08:15:24 AM
Btw, this has just come to my mind. Noone did an audit of Crypto and Curve25519 code yet. We would pay a reward for found flaws.


The comments in the code
   /* Ported  .............. 23/02/08.
    * Original: http://cds.xs4all.nl:8081/ecdh/
    */
   /* Generic 64-bit integer implementation of Curve25519 ECDH
    * ..... 200608242056
    * Public domain.
    *

cause such impression that the code is old enough and likely reviewed enough, i.e. cleared from errors.
And so that would have been a good block to skip over ;-)

Or have you inserted there new flaws ...
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 06:17:27 AM
Btw, this has just come to my mind. Noone did an audit of Crypto and Curve25519 code yet. We would pay a reward for found flaws.

I went through Crypto code, and it looked okay. I've mentioned it here or on nextcoin forum.

Curve I'm not sure yet, there are at least two strange things there, maybe will know something more till the end of the week.

Good. We'll get some bitcoins to set a reward for Nxt crypto algo audit. Yes, bitcoins, not nxts, coz if the algo is flawed nxts won't be worth a lot Grin.
legendary
Activity: 866
Merit: 1002
January 13, 2014, 06:15:07 AM
Btw, this has just come to my mind. Noone did an audit of Crypto and Curve25519 code yet. We would pay a reward for found flaws.

I went through Crypto code, and it looked okay. I've mentioned it here or on nextcoin forum.

Curve I'm not sure yet, there are at least two strange things there, maybe will know something more till the end of the week.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:57:52 AM
Btw, this has just come to my mind. Noone did an audit of Crypto and Curve25519 code yet. We would pay a reward for found flaws.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:53:53 AM
This is close to one of the injected flaws, so I can't give u more details. If u think it's a flaw u r supposed to describe it, not ask questions.

The Crypto  class implementation doesn't check the return value of sign(...). It should because it will detect if the signature is 0.

No. But this situation is avoided by https://bitbucket.org/JeanLucPicard/nxt-public/src/4073c21098076d3469b3f74d49e73ffabe3a2001/Nxt.java?at=master#cl-3458
hero member
Activity: 687
Merit: 500
January 13, 2014, 05:49:38 AM
This is close to one of the injected flaws, so I can't give u more details. If u think it's a flaw u r supposed to describe it, not ask questions.

The Crypto  class implementation doesn't check the return value of sign(...). It should because it will detect if the signature is 0.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:49:27 AM
Hey... I believe if we replace the two ? with . we have a description!   Wink

Do it and we will see. If this is the flaw then u'll get the reward.

Just in case CrazyEyes does not see your reply to his post... I will have a go at it... ON BEHALF OF CrazyEyes of course...

The Elliptic Curve Algorithm can be broken due to the first 32 bits of signature always being 0; thus enabling private key extraction.

Actually they r not ZEROs, look at any signature, for example http://localhost:7874/nxt?requestType=getTransaction&transaction=7790905943202759516
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:48:15 AM
Great, i am always writing like this, trying to be humble:p but ok, s/?/./g. Hehe sorry.

This is not the injected flaw. But it doesn't mean that there r no other flaws. If u dig deeper and find something flawed u'll get a reward.
full member
Activity: 137
Merit: 100
January 13, 2014, 05:42:42 AM

This is close to one of the injected flaws, so I can't give u more details. If u think it's a flaw u r supposed to describe it, not ask questions.

Great, i am always writing like this, trying to be humble:p but ok, s/?/./g. Hehe sorry.

Regards
j0b
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:34:22 AM
Hey... I believe if we replace the two ? with . we have a description!   Wink

Do it and we will see. If this is the flaw then u'll get the reward.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 05:20:33 AM
Could this be a flaw? I am as usual very humble about my knowledge around this things.. but there are some questions here though.
I hope i will understand this better afterwards.

In this function

Line 1349: static byte[] sign(byte[] message, String secretPhrase)
We call a function for creating a signature calling curve.sign..


                byte[] v = new byte[32];
                Curve25519.sign(v, h, x, s);
               
                byte[] signature = new byte[64];
                System.arraycopy(v, 0, signature, 0, 32);
                System.arraycopy(h, 0, signature, 32, 32);
               
                return signature;

In this case, as seen in the function below, the first 32 bits of signature will always be 0.


                 *   v  [out] signature value
                 *   h  [in]  signature hash (of message, signature pub key, and context data)
                 *   x  [in]  signature private key
                 *   s  [in]  private key for signing
                 * returns true on success, false on failure (use different x or h)
                 */
                public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
                        /* v = (x - h) s  mod q  */
                        byte[] tmp1=new byte[65];
                        byte[] tmp2=new byte[33];
                        int w;
                        int i;
                        for (i = 0; i < 32; i++)
                                v = 0;
                        i = mula_small(v, x, 0, h, 32, -1);
                        mula_small(v, v, 0, ORDER, 32, (15-v[31])/16);
                        mula32(tmp1, v, s, 32, 1);
                        divmod(tmp2, tmp1, 64, ORDER, 32);
                        for (w = 0, i = 0; i < 32; i++)
                                w |= v = tmp1;
                        return w != 0;
                }

So i quote directly from wikipedia, and i have also read the RFC regarding elliptic curve algorithm.. i see that if s is 0 then we are fucked?
And since we copy v into signatures first 32 bits, we could assume this as s = 0? This will in that case break the algorithm below not going back too step 3 if r is zero.


    Calculate e = \textrm{HASH}(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
    Select a random integer k from [1, n-1].
    Calculate the curve point (x_1, y_1) = k * G.
    Calculate r = x_1\,\bmod\,n. If r = 0, go back to step 3.
    Calculate s = k^{-1}(z + r d_A)\,\bmod\,n. If s = 0, go back to step 3.
    The signature is the pair (r, s).

When computing s, the string z resulting from (m) shall be converted to an integer. Note that z can be greater than n but not longer.[1]

As the standard notes, it is crucial to select different k for different signatures, otherwise the equation in step 6 can be solved for d_A, the private key: Given two signatures (r,s) and (r,s'). This implementation failure was used, for example, to extract the signing key used in the PlayStation 3 gaming-console.[2]

Regards
j0b, operator in #nxtalk at irc.freenode.net

This is close to one of the injected flaws, so I can't give u more details. If u think it's a flaw u r supposed to describe it, not ask questions.
full member
Activity: 137
Merit: 100
January 13, 2014, 05:09:56 AM
Could this be a flaw? I am as usual very humble about my knowledge around this things.. but there are some questions here though.
I hope i will understand this better afterwards.

In this function

Line 1349: static byte[] sign(byte[] message, String secretPhrase)
We call a function for creating a signature calling curve.sign..


                byte[] v = new byte[32];
                Curve25519.sign(v, h, x, s);
               
                byte[] signature = new byte[64];
                System.arraycopy(v, 0, signature, 0, 32);
                System.arraycopy(h, 0, signature, 32, 32);
               
                return signature;

In this case, as seen in the function below, the first 32 bits of signature will always be 0.


                 *   v  [out] signature value
                 *   h  [in]  signature hash (of message, signature pub key, and context data)
                 *   x  [in]  signature private key
                 *   s  [in]  private key for signing
                 * returns true on success, false on failure (use different x or h)
                 */
                public static final boolean sign(byte[] v, byte[] h, byte[] x, byte[] s) {
                        /* v = (x - h) s  mod q  */
                        byte[] tmp1=new byte[65];
                        byte[] tmp2=new byte[33];
                        int w;
                        int i;
                        for (i = 0; i < 32; i++)
                                v = 0;
                        i = mula_small(v, x, 0, h, 32, -1);
                        mula_small(v, v, 0, ORDER, 32, (15-v[31])/16);
                        mula32(tmp1, v, s, 32, 1);
                        divmod(tmp2, tmp1, 64, ORDER, 32);
                        for (w = 0, i = 0; i < 32; i++)
                                w |= v = tmp1;
                        return w != 0;
                }

So i quote directly from wikipedia, and i have also read the RFC regarding elliptic curve algorithm.. i see that if s is 0 then we are fucked?
And since we copy v into signatures first 32 bits, we could assume this as s = 0? This will in that case break the algorithm below not going back too step 3 if r is zero.


    Calculate e = \textrm{HASH}(m), where HASH is a cryptographic hash function, such as SHA-1.
    Let z be the L_n leftmost bits of e, where L_n is the bit length of the group order n.
    Select a random integer k from [1, n-1].
    Calculate the curve point (x_1, y_1) = k * G.
    Calculate r = x_1\,\bmod\,n. If r = 0, go back to step 3.
    Calculate s = k^{-1}(z + r d_A)\,\bmod\,n. If s = 0, go back to step 3.
    The signature is the pair (r, s).

When computing s, the string z resulting from (m) shall be converted to an integer. Note that z can be greater than n but not longer.[1]

As the standard notes, it is crucial to select different k for different signatures, otherwise the equation in step 6 can be solved for d_A, the private key: Given two signatures (r,s) and (r,s'). This implementation failure was used, for example, to extract the signing key used in the PlayStation 3 gaming-console.[2]

Regards
j0b, operator in #nxtalk at irc.freenode.net
legendary
Activity: 866
Merit: 1002
January 13, 2014, 04:29:14 AM
Regarding the performance criteria, are you referring to curve25519 or crypto operations per second? And, if you're looking for running this in the browser, what browsers are you looking at supporting? Considering curve25519's heavy reliance on 64-bit arithmetic (which JavaScript doesn't support natively), it will probably be a lot slower than you're expected (especially running outside of v8). Do you have test data you are using for a benchmark?

Crypto operations. Chrome. No test data, I'll take an ordinary payment transaction.


Crypto operations include also calculating sha... :/
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 01:20:37 AM
But I'd be very interested in hearing why the unverifiability happens and to see numbers on how often that happens.

Sometimes verification faces a situation similar to

Code:
X * 0 == Y * 0

In this case it's impossible to make sure that X == Y.

It happens ~ each 4th time.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 01:16:32 AM
Regarding the performance criteria, are you referring to curve25519 or crypto operations per second? And, if you're looking for running this in the browser, what browsers are you looking at supporting? Considering curve25519's heavy reliance on 64-bit arithmetic (which JavaScript doesn't support natively), it will probably be a lot slower than you're expected (especially running outside of v8). Do you have test data you are using for a benchmark?

Crypto operations. Chrome. No test data, I'll take an ordinary payment transaction.


Also, are you giving the whole bounty to the fastest solution, or going to split it among functionally correct submissions?

The fastest submission will get (a part of) the bounty.
legendary
Activity: 2142
Merit: 1010
Newbie
January 13, 2014, 01:11:50 AM
I might be overlooking something, but I can't come up with an explanation as to why this would happen. Is this a bug?

It's a trick to prevent forging all the blocks by a single big account.
legendary
Activity: 866
Merit: 1002
January 12, 2014, 08:08:21 PM

keygen gets the digested secretPhrase, which is exactly 32 bytes.
The result is also not null, just in case you haven't checked yourself...

Sorry my fault, I've got different copies of code all over the place, and this is, how I was looking at following one.
Ad you've said in released sources it calls SHA256, so it should be ok.

Code:
static byte[] getPublicKey(byte[] priv)
{
try
{
byte abyte0[] = new byte[32];
Curve25519.keygen(abyte0, null, priv);
return abyte0;
}
catch(Exception _ex)
{
_ex.printStackTrace();
return null;
}
}
newbie
Activity: 56
Merit: 0
January 12, 2014, 07:56:15 PM
The result of the hash function has 32 bytes, so that's not the problem. And also there are no exceptions in that code.

Instead of passing result of hash function, he's passing short words -> Crypto.getPublicKey -> Crypto.keygen -> clamp -> OOB exception
exception is silently handled, getPublicKey returns null in result

keygen gets the digested secretPhrase, which is exactly 32 bytes.
The result is also not null, just in case you haven't checked yourself...
legendary
Activity: 866
Merit: 1002
January 12, 2014, 07:51:54 PM
The result of the hash function has 32 bytes, so that's not the problem. And also there are no exceptions in that code.

Instead of passing result of hash function, he's passing short words -> Crypto.getPublicKey -> Crypto.keygen -> clamp -> OOB exception
exception is silently handled, getPublicKey returns null in result
Pages:
Jump to: