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

From: [email-masked]
Date: Fri, 7 May 2021 10:45:41 -0500 (CDT)

My guess is they got M and N wrong. Ah they got M and N wrong oh and [redacted]... wait they didn't fix [redacted]. This is still broken. OK I guess it's theoretically broken: 5 racks of computers breaks a PAKE exchange on average every 4 days. There's a better method but I don't think it works in this case.

P.S. I sent him an email. So it should be fixed soon.

> On 05/07/2021 2:24 AM Ruben Gonzalez <[email-masked]> wrote:
> 
>  
> Hello CFRGers,
> 
> this is my first time posting on the mailing list. In case this is the 
> wrong place for such a message, I apologize.
> 
> Aaron Kaiser (in CC) and I wrote a detailed blog post about a 
> vulnerability Aaron found in a real world SPAKE2 implementation.
> 
> The blog post "Croc Full Plaintext Recovery - CVE-2021-31603" can be 
> found here: https://redrocket.club/posts/croc/.
> 
> We did not attack SPAKE2 directly, but a faulty implementation. The blog 
> post might still be relevant for authors of the standard, since it shows 
> how developers can easily misunderstand it.
> 
> For questions or additional information, just drop us an email.
> 
> Kind regards,
> 
> Ruben Gonzalez
> 
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Dan Harkins <[email-masked]>
Date: Fri, 07 May 2021 13:18:53 -0700

On 5/7/21 8:45 AM, [email-masked] 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

---

From: [email-masked]
Date: Fri, 7 May 2021 22:49:15 -0500 (CDT)

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 <[email-masked]> wrote:
> 
>