Hacker News Reader

Comment by londons_explore | Hacker News Reader

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)

View on HN

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.

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

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.

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.

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?

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)

Now I feel better for never using the same key for different servers.

Reply on news.ycombinator.com