4 ms·

So this signing method requires a 521 bit random number, and this flaw caused the top 9 bits of that number to be zero instead, and somehow after 60 signatures

So this signing method requires a 521 bit random number, and this flaw caused the top 9 bits of that number to be zero instead, and somehow after 60 signatures this leaks the private key? Anyone care to explain how exactly? How it it any different to the top 9 bits being zero by chance (which happens in 1 out of ~500 attempts anyway)

lambdafu 3y ago
For the attack all 60 signatures need a nonce that is special in this way. If for example only one out of the 60 is short, the attack fails in the lattice reduction step. The reason is that in the attack, all 60 short nonces "collude" to make up a very special short vector in the lattice, which is much shorter than usual because it is short in all 60 dimensions, not just one out of 500 dimensions. The approximate shortest vector is then obtainable in polynomial time, and this happens to contain the secret key by construction. As an analogy: Imagine you had a treasure map with 60 steps "go left, go right, go up, go down, go down again" etc. If only one out of 60 instructions where correct, you wouldn't know where the treasure is. All of the instructions need to be correct to get there.
jwilk 3y ago
Sure, it happens by chance, but the attacker doesn't know when it happens.
janmo 3y ago
Doesn't make sense to me as well, even when fully random after 30,000 signatures you would get around 60 signatures where the nonce starts with nine zero bits. I suspect there must be something else at play here. EDIT: the nonce is PRIVATE, so the scenario I described would not work because we wouldn't know for which of the 30k signatures the nonce starts with 9 zero bits. Makes sense now.
- gs17 3y ago
  If I'm understanding correctly, the difference is between knowing you have 60 and having to try (30000!/(60! * (30000 - 60)!) combinations and seeing if they worked, which is quite a few.
  - cchance 3y ago
    I mean the write up indicates you'd need access to the server side, or the pageant with the private key loaded, which both seem to be like... umm... at that point don't we have bigger issues?
    - Khoth 3y ago
      Not sure about the pageant part, but it's a major problem when connecting to a compromised server leaks the client's private key. (For example, if an attacker has compromised server A and you connect to it, they can now use your key to connect to server B which you also use)
      - leni536 3y ago
        Now I feel better for never using the same key for different servers.

lambdafu 3y ago

For the attack all 60 signatures need a nonce that is special in this way. If for example only one out of the 60 is short, the attack fails in the lattice reduction step. The reason is that in the attack, all 60 short nonces "collude" to make up a very special short vector in the lattice, which is much shorter than usual because it is short in all 60 dimensions, not just one out of 500 dimensions. The approximate shortest vector is then obtainable in polynomial time, and this happens to contain the secret key by construction. As an analogy: Imagine you had a treasure map with 60 steps "go left, go right, go up, go down, go down again" etc. If only one out of 60 instructions where correct, you wouldn't know where the treasure is. All of the instructions need to be correct to get there.

jwilk 3y ago

Sure, it happens by chance, but the attacker doesn't know when it happens.

janmo 3y ago

Doesn't make sense to me as well, even when fully random after 30,000 signatures you would get around 60 signatures where the nonce starts with nine zero bits. I suspect there must be something else at play here. EDIT: the nonce is PRIVATE, so the scenario I described would not work because we wouldn't know for which of the 30k signatures the nonce starts with 9 zero bits. Makes sense now.

gs17 3y ago
If I'm understanding correctly, the difference is between knowing you have 60 and having to try (30000!/(60! * (30000 - 60)!) combinations and seeing if they worked, which is quite a few.
- cchance 3y ago
  I mean the write up indicates you'd need access to the server side, or the pageant with the private key loaded, which both seem to be like... umm... at that point don't we have bigger issues?
  - Khoth 3y ago
    Not sure about the pageant part, but it's a major problem when connecting to a compromised server leaks the client's private key. (For example, if an attacker has compromised server A and you connect to it, they can now use your key to connect to server B which you also use)
    - leni536 3y ago
      Now I feel better for never using the same key for different servers.