Nxt Forum

Please login or register.

Login with username, password and session length
Advanced search  

News:

Update to the latest Nxt Client 1.5.14

Pages: 1 [2] 3 4 ... 13  All

Author Topic: Bug report: severe ddos attack and unfair forging  (Read 9424 times)

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

i have not dig that deep into this attack, because i got shocked when the ddos worked on the mainnet and i immediately registered here.
what you probably could do is, kill all forkers, start forking two chains in parallel while keeping one smaller than the other, depositing nxt to an exchange on the longer chain, and after 20 confirmations let the longer chain die and switch to the alternative chain to charge back. i am not hundred percent sure that this would work, maybe the devs can comment on this if the nxt protocol has the same longest-chain mechanism like built into bitcoin. if it does, this would be fatal.

taking nxt out of another account is a different story, i am right now working on a mathematical write up concerning private key recovery by collecting multiple signed messages. i will get back to you once i finish. i hope i can help the community, and once again many apologies for my initial rude behavior when i first appeared on this forum.
please feel free to support me: my nxt account is 3829444439138730512

bitcoinpaul

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 3064
  • Karmageddon
  • Karma: +559/-558

Let's wait for the devs and relax.
Like my Avatar? Reply now! NXT-M5JR-2L5Z-CFBP-8X7P3

Damelon

  • Administrator
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 3570
  • [Tip Me]
    • Nxt Inside
  • Karma: +509/-34

taking nxt out of another account is a different story, i am right now working on a mathematical write up concerning private key recovery by collecting multiple signed messages. i will get back to you once i finish. i hope i can help the community, and once again many apologies for my initial rude behavior when i first appeared on this forum.

I can't comment on the technical side, but I appreciate you being polite :)
Props for that.
Member of D.O.R.C.S., creators of Lyth - An Emergent Trading Game | Donations: NXT-D6K7-MLY6-98FM-FLL5T

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

just to tell you a few concerns i have regarding the current signature process, and maybe qualify even more for a little bounty which i probably would not deserve at this point because of my rude behaviour.

the signature is calculated like this:

Code: [Select]
v = (x - h) s  mod q
where v is the signature as an output, s is the private key, x is some random variable and h is calculated from x.
v as well as h are both propagated through the network with the signed messages.

now just to keep it simple at the moment, if you have a signed message you know v and h in the formula (as both variables are in the signature field). so you have two unknown variables left in the equation. if you know x you can derive s from it, if you know s you can derive x from it.

if you collect a whole bunch (maybe two are enough) of signed messages you can formulate a system of two linear equations (in a finite field).
two equations with two unknown variables solve them both. you eventually end up with a solution for s, which is the private key that signed the message.

in fact it is a bit trickier, but it is still linear. bitcoin does its signing a bit different, it incorporates the modular inverse, which makes the equation non linear as the only way to solve the modular inverse of a number is using the very costly extended euclidean algorithm. but in nxt we have simple linear congruences.

there is more magic to be done, i am writing a short abstract with mathematical proofs for the devs right now.
« Last Edit: April 01, 2014, 05:21:25 pm by harmony666 »
please feel free to support me: my nxt account is 3829444439138730512

mthcl

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 511
  • [Tip Me]
  • Karma: +60/-1

just to tell you a few concerns i have regarding the current signature process, and maybe qualify even more for a little bounty which i probably would not deserve at this point because of my rude behaviour.

the signature is calculated like this:

Code: [Select]
v = (x - h) s  mod q
where v is the signature as an output, s is the private key, x is some random variable and h is calculated from x.
v as well as h are both propagated through the network with the signed messages.

now just to keep it simple at the moment, if you have a signed message you know v and h in the formula (as both variables are in the signature field). so you have two unknown variables left in the equation. if you know x you can derive s from it, if you know s you can derive x from it.

if you collect a whole bunch (maybe two are enough) of signed messages you can formulate a system of two linear equations (in a finite field).
two equations with two unknown variables solve them both. you eventually end up with a solution for s, which is the private key that signed the message.

in fact it is a bit trickier, but it is still linear. bitcoin does its signing a bit different, it incorporates the modular inverse, which makes the equation non linear as the only way to solve the modular inverse of a number is using the very costly extended euclidean algorithm. but in nxt we have simple linear congruences.

there is more magic to be done, i am writing a short abstract with mathematical proofs for the devs right now.
You mean that your system of equations is

v1 = (x - h1) s  mod q
v2 = (x - h2) s  mod q

right?
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7

Eadeqa

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1887
  • [Tip Me]
  • Karma: +81/-68

just to tell you a few concerns i have regarding the current signature process, and maybe qualify even more for a little bounty which i probably would not deserve at this point because of my rude behaviour.

the signature is calculated like this:

Code: [Select]
v = (x - h) s  mod q
where v is the signature as an output, s is the private key, x is some random variable and h is calculated from x.
v as well as h are both propagated through the network with the signed messages.

now just to keep it simple at the moment, if you have a signed message you know v and h in the formula (as both variables are in the signature field). so you have two unknown variables left in the equation. if you know x you can derive s from it, if you know s you can derive x from it.

if you collect a whole bunch (maybe two are enough) of signed messages you can formulate a system of two linear equations (in a finite field).
two equations with two unknown variables solve them both. you eventually end up with a solution for s, which is the private key that signed the message.

in fact it is a bit trickier, but it is still linear. bitcoin does its signing a bit different, it incorporates the modular inverse, which makes the equation non linear as the only way to solve the modular inverse of a number is using the very costly extended euclidean algorithm. but in nxt we have simple linear congruences.

there is more magic to be done, i am writing a short abstract with mathematical proofs for the devs right now.

What do you think about this review?

https://gist.github.com/doctorevil/9521116

The author seem to think it's secure
NXT-GZYP-FMRT-FQ9K-3YQGS

schnidl

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 31
  • Karma: +7/-0

thanks a lot harmony666!
NXT-NBY7-VPLP-YGF9-BXF7Z

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

i see i made a few little mistakes in the description. actually you end up with two different x.

v1 = (x1 - h1) s  mod q
v2 = (x2 - h2) s  mod q

while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.

i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.

its still all in the beginning phase, but i am working hard.
please feel free to support me: my nxt account is 3829444439138730512

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

What do you think about this review?

https://gist.github.com/doctorevil/9521116

The author seem to think it's secure

i will read it carefully, but on the first sight the author also states

Quote
As far as I can tell, NXT's fix in response to the attack I reported earlier, makes it immune to signature malleability.

which is not true, the counter proof was performed yesterday on the mainnet.
please feel free to support me: my nxt account is 3829444439138730512

Eadeqa

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1887
  • [Tip Me]
  • Karma: +81/-68

What do you think about this review?

https://gist.github.com/doctorevil/9521116

The author seem to think it's secure

i will read it carefully, but on the first sight the author also states

Quote
As far as I can tell, NXT's fix in response to the attack I reported earlier, makes it immune to signature malleability.

which is not true, the counter proof was performed yesterday on the mainnet.


Yes, but that yesterday attack didn't succeed in stealing nxt, did it? It killed forging nodes

The original attack could replicate transactions which would result in stealing nxt.
 
NXT-GZYP-FMRT-FQ9K-3YQGS

mthcl

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 511
  • [Tip Me]
  • Karma: +60/-1

i see i made a few little mistakes in the description. actually you end up with two different x.

v1 = (x1 - h1) s  mod q
v2 = (x2 - h2) s  mod q

while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.

i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.

its still all in the beginning phase, but i am working hard.

OK, I'm waiting for the math then. But have to confess that I didn't get you main idea so far. This q is supposed to be very large so that you cannot go through a cycle of length q in practice, right? So you'll need to prove that the size of the set of possible solutions decreases a lot as you increase the number of equations, and, for now, I don't see why should this be true.
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

i see i made a few little mistakes in the description. actually you end up with two different x.

v1 = (x1 - h1) s  mod q
v2 = (x2 - h2) s  mod q

while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.

i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.

its still all in the beginning phase, but i am working hard.

OK, I'm waiting for the math then. But have to confess that I didn't get you main idea so far. This q is supposed to be very large so that you cannot go through a cycle of length q in practice, right? So you'll need to prove that the size of the set of possible solutions decreases a lot as you increase the number of equations, and, for now, I don't see why should this be true.

well the key idea is, that you end up with solutions like this:
s=3563275632573257*t1
s=6364375784584585*t2
s=2643764374644743*t3
...

or something, for some random factors,
plus you get a few boundary conditions like the known ranges for s and t, which could make it even easier to find a set of valid t, which are solving the initial equations and all lead to the same s.

at the moment i am not even sure if you have to cycle through anything at all, or if a CAS can spit out the solution right away. i will need some more time to make it solid. but the fact is, that the linearity in the signing process is bad at all.

thats why ecdsa uses the modular inverse, and dsa uses exponentiation.
reverting exponentiation in a finite field is the unsolvable NP hard discrete logarithm problem.
solving linear equations in a finite field is no tough science at all.
« Last Edit: April 01, 2014, 08:25:41 pm by harmony666 »
please feel free to support me: my nxt account is 3829444439138730512

mthcl

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 511
  • [Tip Me]
  • Karma: +60/-1

i see i made a few little mistakes in the description. actually you end up with two different x.

v1 = (x1 - h1) s  mod q
v2 = (x2 - h2) s  mod q

while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.

i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.

its still all in the beginning phase, but i am working hard.

OK, I'm waiting for the math then. But have to confess that I didn't get you main idea so far. This q is supposed to be very large so that you cannot go through a cycle of length q in practice, right? So you'll need to prove that the size of the set of possible solutions decreases a lot as you increase the number of equations, and, for now, I don't see why should this be true.

well the key idea is, that you end up with solutions like this:
s=3563275632573257*x1
s=6364375784584585*x2
s=2643764374644743*x3
...

or something, for some random factors,
plus you get a few boundary conditions like the known ranges for s and x, which could make it even easier.

at the moment i am not even sure if you have to cycle through anything at all, or if a CAS can spit out the solution right away. i will need some more time to make it solid. but the fact is, that the linearity in the signing process is bad at all.

thats why ecdsa uses the modular inverse, and dsa uses exponentiation.
reverting exponentiation in a finite field is the unsolvable NP hard discrete logarithm problem.
solving linear equations in a finite field is no tough science at all.
Anyhow, the number of equations will be always less than the number of variables, so I doubt that any CAS can really solve it.   Also, if one wants to find possible values of s, will it be necessary to factorize all those big numbers before x's (which is hard as well)?
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

i see i made a few little mistakes in the description. actually you end up with two different x.

v1 = (x1 - h1) s  mod q
v2 = (x2 - h2) s  mod q

while h1 and 2 are known. so in fact you would have to collect a few more signatures. you will always end up with one variable more than you have equations.
so you have collected 10 equations, you have 11 unknown variables meaning all the x1...x10 plus s.

i have not yet managed to get this to work efficiently, but i am pretty sure that this is not much of a problem. i am really thinking, working, rethinking and hopefully i get it.
from the mathematical point of view, there is nothing that would prevent us solving a set of 10 linear equations with 11 variables for example. you would have a result in form of a linear congruence which you would then efficiently could cycle through.

its still all in the beginning phase, but i am working hard.

OK, I'm waiting for the math then. But have to confess that I didn't get you main idea so far. This q is supposed to be very large so that you cannot go through a cycle of length q in practice, right? So you'll need to prove that the size of the set of possible solutions decreases a lot as you increase the number of equations, and, for now, I don't see why should this be true.

well the key idea is, that you end up with solutions like this:
s=3563275632573257*x1
s=6364375784584585*x2
s=2643764374644743*x3
...

or something, for some random factors,
plus you get a few boundary conditions like the known ranges for s and x, which could make it even easier.

at the moment i am not even sure if you have to cycle through anything at all, or if a CAS can spit out the solution right away. i will need some more time to make it solid. but the fact is, that the linearity in the signing process is bad at all.

thats why ecdsa uses the modular inverse, and dsa uses exponentiation.
reverting exponentiation in a finite field is the unsolvable NP hard discrete logarithm problem.
solving linear equations in a finite field is no tough science at all.
Anyhow, the number of equations will be always less than the number of variables, so I doubt that any CAS can really solve it.   Also, if one wants to find possible values of s, will it be necessary to factorize all those big numbers before x's (which is hard as well)?

i am not sure if factorizing is really necessary here.
lets make an easier example, we work on the galois field GF(6131) so we have 6131 elements in our space. the galois field GF(q) is much bigger but lets stick to the easy example for the moment.

Now let us say we have signed two messages:

message1:  x=576  h=272  s=12345
so  v=(576-272)*12345 mod 6131 = 708

message2:  x=616  h=888  s=12345
so  v=(616-888)*12345 mod 6131 = 1948


now we only know v and h, and we can create a first linear set of equations:

708 = (x1-272)*s
1948 =  (x2-888)*s

reorganize equations: ($$)
1/s = (x1-272)/708
1/s =  (x2-888)/1948

note that the division operation is in fact a multiplication with invmod(x,6131)

once again (**)
(x1-272)/708 = (x2-888)/1948

resulting congruence is when calculation over whole R:
x1 = 177*n + 95
x2 = 487*n + 401

now just find an n so that the euqation from above (marked **) fulfills equality in the finite field.
this should be doable on every calculator  ;)

if you have it, you get the n which will give you (once inserted in one of the formulas marked $$) the value of 1/s.
Inverse it, and you have the private key.

forgive me any mistakes, i just did this out of my head and this has to be verified by the devs first. but i have big concers due to the linearity and i hope we can jointly work on verifying (or denying) such thoughts as a community. i really hope i get accepted here.
« Last Edit: April 01, 2014, 09:23:19 pm by harmony666 »
please feel free to support me: my nxt account is 3829444439138730512

IveBeenBit

  • Full Member
  • ***
  • Offline Offline
  • Posts: 131
  • Karma: +7/-2

OH, SNAP!
I need your suggestions for Nxt Podcast ideas. Click here and speak your mind!

IveBeenBit

  • Full Member
  • ***
  • Offline Offline
  • Posts: 131
  • Karma: +7/-2

Serious question now...these maths is way over my head. But I wonder if it's risky to be discussing this much detail openly until our developers have a chance to review the potential vulnerabilities? As I understand it, you're trying to find a way to compute someone's private key given enough signed transactions.

BTW, I'm really enjoying seeing harmony666's (cool username, BTW) about-face since his first post. It's cool to see someone with this much excitement and knowledge playing on "our team."

Harmony666 -- have you heard from Jean-Luc or Come From Beyond yet since you messaged them earlier today?
I need your suggestions for Nxt Podcast ideas. Click here and speak your mind!

harmony666

  • Jr. Member
  • **
  • Offline Offline
  • Posts: 61
  • Karma: +10/-5

Serious question now...these maths is way over my head. But I wonder if it's risky to be discussing this much detail openly until our developers have a chance to review the potential vulnerabilities? As I understand it, you're trying to find a way to compute someone's private key given enough signed transactions.

BTW, I'm really enjoying seeing harmony666's (cool username, BTW) about-face since his first post. It's cool to see someone with this much excitement and knowledge playing on "our team."

Harmony666 -- have you heard from Jean-Luc or Come From Beyond yet since you messaged them earlier today?

thank you for the kind words. it really makes a lot of fun, and if something does not work on the first try it encourages me even more to dig deeper and deeper into it. until it finally works, or is proven to be a waste of time. but without a counter proof i usually dont give up that fast.

yes, maybe we should not discuss it in public, you are right. however, i also just know basic math only, so it always takes some time until i fully understand everything. today i have spent 3 hours in the library alone, to read about all these galois fields and the discrete logarithm problem.

i cannot tell you why, but i want to help as much as i can. of course i have to pay my rent (as i have no regular job right now) but the fun working on cryptos is more important to me.

unfortunately i have not gotten any response back yet.
please feel free to support me: my nxt account is 3829444439138730512

forkedchain

  • Administrator
  • Hero Member
  • *****
  • Offline Offline
  • Posts: 1019
  • bite me
  • Karma: +61/-10

Odd,  I know when the Dr Evil exp
Serious question now...these maths is way over my head. But I wonder if it's risky to be discussing this much detail openly until our developers have a chance to review the potential vulnerabilities? As I understand it, you're trying to find a way to compute someone's private key given enough signed transactions.

BTW, I'm really enjoying seeing harmony666's (cool username, BTW) about-face since his first post. It's cool to see someone with this much excitement and knowledge playing on "our team."

Harmony666 -- have you heard from Jean-Luc or Come From Beyond yet since you messaged them earlier today?

thank you for the kind words. it really makes a lot of fun, and if something does not work on the first try it encourages me even more to dig deeper and deeper into it. until it finally works, or is proven to be a waste of time. but without a counter proof i usually dont give up that fast.

yes, maybe we should not discuss it in public, you are right. however, i also just know basic math only, so it always takes some time until i fully understand everything. today i have spent 3 hours in the library alone, to read about all these galois fields and the discrete logarithm problem.

i cannot tell you why, but i want to help as much as i can. of course i have to pay my rent (as i have no regular job right now) but the fun working on cryptos is more important to me.

unfortunately i have not gotten any response back yet.

Odd, I know when the Dr Evil exploit came along, they were all over him.  But he gave very detailed info, along with the fix even.  So maybe theyre still doing their research
NXT tips: 2319251 or NXT-8SWM-2224-YKWW-22222

mthcl

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 511
  • [Tip Me]
  • Karma: +60/-1

i am not sure if factorizing is really necessary here.
lets make an easier example, we work on the galois field GF(6131) so we have 6131 elements in our space. the galois field GF(q) is much bigger but lets stick to the easy example for the moment.
Keep it simple, write just ℤ/6131ℤ (6131 is a prime, so the construction of the GF is straightforward)   :)
 
Now let us say we have signed two messages:

message1:  x=576  h=272  s=12345
so  v=(576-272)*12345 mod 6131 = 708

message2:  x=616  h=888  s=12345
so  v=(616-888)*12345 mod 6131 = 1948


now we only know v and h, and we can create a first linear set of equations:

708 = (x1-272)*s
1948 =  (x2-888)*s

reorganize equations: ($$)
1/s = (x1-272)/708
1/s =  (x2-888)/1948

note that the division operation is in fact a multiplication with invmod(x,6131)

once again (**)
(x1-272)/708 = (x2-888)/1948

resulting congruence is when calculation over whole R:
x1 = 177*n + 95
x2 = 487*n + 401

now just find an n so that the euqation from above (marked **) fulfills equality in the finite field.
this should be doable on every calculator  ;)

Now, the key question is how many values of n you have to try. If it is comparable to q, than this can't be done in practice. Any idea, how this quantity can be estimated?
messages and donations: NXT-N8U7-TU6Z-HU3S-759Y7

Sebastien256

  • Hero Member
  • *****
  • Offline Offline
  • Posts: 2233
  • [Tip Me]
  • ^LOOK UP^ = Nxt community!
  • Karma: +110/-17

i am not sure if factorizing is really necessary here.
lets make an easier example, we work on the galois field GF(6131) so we have 6131 elements in our space. the galois field GF(q) is much bigger but lets stick to the easy example for the moment.
Keep it simple, write just ℤ/6131ℤ (6131 is a prime, so the construction of the GF is straightforward)   :)
 
Now let us say we have signed two messages:

message1:  x=576  h=272  s=12345
so  v=(576-272)*12345 mod 6131 = 708

message2:  x=616  h=888  s=12345
so  v=(616-888)*12345 mod 6131 = 1948


now we only know v and h, and we can create a first linear set of equations:

708 = (x1-272)*s
1948 =  (x2-888)*s

reorganize equations: ($$)
1/s = (x1-272)/708
1/s =  (x2-888)/1948

note that the division operation is in fact a multiplication with invmod(x,6131)

once again (**)
(x1-272)/708 = (x2-888)/1948

resulting congruence is when calculation over whole R:
x1 = 177*n + 95
x2 = 487*n + 401

now just find an n so that the euqation from above (marked **) fulfills equality in the finite field.
this should be doable on every calculator  ;)

Now, the key question is how many values of n you have to try. If it is comparable to q, than this can't be done in practice. Any idea, how this quantity can be estimated?

I think this can be reformulate into a linear least square optimization problem. f(n)=(x1 - 177*n + 95)^2+(x2 - 487*n + 401)^2, the goal is to minimize f(n), with minimum f(n)=0 at n. It is a one dimensional optimization. It should not be too hard to solve. Unless I miss something.

EDIT: is this reformulation valid with the GF? Or is there optimizor on GF?
« Last Edit: April 01, 2014, 10:39:54 pm by Sebastien256 »
Please drop your ideas concerning Nxt or NRS in this topic -> List of feature request for Nxt and NRS.
Pages: 1 [2] 3 4 ... 13  All