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

steve@tobtu.com Sat, 08 May 2021 03:49 UTC

Return-Path: <steve@tobtu.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5E5353A110C for <cfrg@ietfa.amsl.com>; Fri, 7 May 2021 20:49:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.917
X-Spam-Level:
X-Spam-Status: No, score=-1.917 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_BLOCKED=0.001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_NONE=0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OzyKBG4qIK_G for <cfrg@ietfa.amsl.com>; Fri, 7 May 2021 20:49:35 -0700 (PDT)
Received: from mout.perfora.net (mout.perfora.net [74.208.4.197]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 22EC83A3B11 for <cfrg@irtf.org>; Fri, 7 May 2021 20:49:34 -0700 (PDT)
Received: from oxuslxaltgw10.schlund.de ([10.72.76.66]) by mrelay.perfora.net (mreueus004 [74.208.5.2]) with ESMTPSA (Nemesis) id 1M6mQM-1lbNwG3rI6-008GHf; Sat, 08 May 2021 05:49:18 +0200
Date: Fri, 7 May 2021 22:49:15 -0500 (CDT)
From: steve@tobtu.com
To: Dan Harkins <dharkins@lounge.org>, Ruben Gonzalez <in+lists@ruben-gonzalez.de>, cfrg@irtf.org
Cc: rixxc@redrocket.club
Message-ID: <244947427.38250.1620445755120@email.ionos.com>
In-Reply-To: <024d23db-0c5b-e4aa-b0ca-c7dbac60002d@lounge.org>
References: <736794875.32663.1620402341358@email.ionos.com> <024d23db-0c5b-e4aa-b0ca-c7dbac60002d@lounge.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Priority: 3
Importance: Normal
X-Mailer: Open-Xchange Mailer v7.10.4-Rev22
X-Originating-Client: open-xchange-appsuite
X-Provags-ID: V03:K1:oBXLiabL+z2EHndIqyMqDGwmk/MQADQVWMvzPvwGFVoYByritiF Tz9MDucZvlIjClY2stiMCVncqq0fMk8a8JTJfW3kPsGdGCKMe7fNBodLvpzdSxaKTr6A+3A X3MLkJZ9o1QpDrTCEODfKVArZCt506GSYbn9pbHXOxKERl3AcrPLisSPkjnL8mxL4VBcUFZ FCtop0YMEWZ0rrefwrnUQ==
X-UI-Out-Filterresults: notjunk:1;V03:K0:k8wjXODfPvs=:DfnND5lxR6hKXHnoYMHGxH kzFFpX6muS/T53T7uWtsIKfckYBLRuX+QcNOJTzcUhUv2Z+pn9ONKf5ZERdvDx7dWFxOxznpx SRmUyKE4YTwZCZJ1VN8cS1w/KX+DBJ84+o7x989h9ZdYGewimXngZQHkjv5mgFkLqLZAXjeiw aZmiIdS1gs3EPvx89NcVULKcfcyw84i8YtOFFWXFwzK0InCh5b3emQgw+FZKdqCsde72kDMAa a6k0vZRfNQa3EIp4h/PzCFgZ7kzKecuYhLWcMO1AAl3PKvFSsntl5ZSE5g+txmqYUfWhLl5h1 lusbwbR8/DbBiNpFivGBYxsQAjOsFH5sccBiKl1LeJU3bSK1ffh9kOjabfy3la8NUocv7LlxH 6bzdZKzIu6d+6QwIMv8dKFrVjaKWCpn8xzoH9ehloPX1oAfvcnVxnkuH2g5/soLu2DFfCjcDt 5lP3MP4WeFdtoTpRbK6DMs68tNMnEfIVvzE9cx4Jn9G9rxbRfW4kv5XVwk8abA9SKTz8fTpHV Z/gxvNQ4ccCJs/LxCQU1Mk=
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/icl1AGo62iq8vQM3-NE8XS3bmvo>
Subject: Re: [CFRG] Attack on a Real World SPAKE2 Implementation
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 08 May 2021 03:49:40 -0000

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 <dharkins@lounge.org> wrote:
> 
>  
> On 5/7/21 8:45 AM, steve@tobtu.com 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