Re: [CFRG] Attack on a Real World SPAKE2 Implementation

[[e-mail]]

It was patched: https://github.com/schollz/pake/commit/886f7d50e5dba3956e3db3db842e937ee6281760

[redacted] was "short keys".

Private keys were only 8 bytes. DLPs of this size can be trivially solved in a few seconds. Now to successfully break this PAKE with the auto generated password, you would need to solve on average 2^31 of these which takes like 5 racks of computers running for 4 days.

The attack is if you observe the PAKE exchange then you can make offline guesses at the password. Once you have the password you can run the rest of the PAKE to get the session key. You observe A's "X" and make a password guess "pw" and do A' = X - pw*U. Try to solve the DLP for A'. If you find the 64 bit private key then you found the password and A's private key. To solve the 64 bit DLP you can use Baby-Step Giant-Step. Basically you store 0*G, 1*G, 2*G, 3*G, ... (n-1)*G then look up A'-0*(n*G), A'-1*(n*G), A'-2*(n*G), A'-3*(n*G), ... A'-(2^64/n-1)*(n*G). There's a time-memory trade-off with the choice of "n". Higher values take more space to store but less time to solve.

There is a way to solve several DLPs at the same time faster than doing them all sequentially. I don't know how that method works but I'm going to assume it won't work for this case. Where only one private key is 64 bits and the others are full random private keys.


> On 05/07/2021 3:18 PM Dan Harkins <[e-mail]> wrote:
> 
>  
> On 5/7/21 8:45 AM, [e-mail] wrote:
> > 5 racks of computers breaks a PAKE exchange on average every 4 days.
> 
>    Can you expand on this? The adversarial advantage of a PAKE is supposed
> to be related to interaction and not computation. What PAKE? And how
> do 5 racks take 4 days to break it?
> 
>    regards,
> 
>    Dan.
> 
> -- 
> "The object of life is not to be on the side of the majority, but to
> escape finding oneself in the ranks of the insane." -- Marcus Aurelius