Nxt source code flaw reports

[ricot]

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

[gimre]

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;
		}
	}

[Come-from-Beyond]

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.

[Come-from-Beyond]

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.

[Come-from-Beyond]

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.

[gimre]

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... :/

[CrazyEyes]

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

[Come-from-Beyond]

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.

[Come-from-Beyond]

Hey... I believe if we replace the two ? with . we have a description!  

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

[CrazyEyes]

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

[Come-from-Beyond]

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.

[Come-from-Beyond]

Hey... I believe if we replace the two ? with . we have a description!  

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

[BloodyRookie]

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.

[Come-from-Beyond]

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

[Come-from-Beyond]

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.

[gimre]

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.

[Come-from-Beyond]

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 .

[jkoil]

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

[Come-from-Beyond]

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.

[jkoil]

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.

ok...

... yes, they are identical