Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)

Watson Ladd <> Sun, 08 September 2019 16:36 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BE24812006A for <>; Sun, 8 Sep 2019 09:36:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.099
X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id oEOm1W_r8lmZ for <>; Sun, 8 Sep 2019 09:36:07 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4864:20::12f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 0799E120020 for <>; Sun, 8 Sep 2019 09:36:07 -0700 (PDT)
Received: by with SMTP id u13so8617409lfm.9 for <>; Sun, 08 Sep 2019 09:36:06 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=p9Up1IbDnhLI4ClH52O8vxhABQIR8c5cI+RXSiIZto0=; b=nmqArmpTR5H2GH89iquIb3Ho1UwUrEeg5pgEaXzQqY7xshPAcsS++kIvZFS5Ir3D76 ubsmx2Vydfon5tuhMUf4TH6TeFG5lxJu7Qv4tf+3o4nIPmQWokgXzzVobgN0jFoIBVg5 VO328xMQJmUX+Ol5vkDseoFdYDYk322C/Mo0ix1FhIh2fEGo1nXMsfeISQHIcnTlM2nW NaOz6QoxctsuQm0TN+rzHPloIbLkRjZb1RIugt5TKEnFAYPwzUWEM6w/8kdV8e9RsqH2 EEq811NLSS/OrN7XFOLkMvotzWSI9NOrB2kuUOC01PyB2+mP9uLC/8MgO6VAutS9ytov G4ag==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=p9Up1IbDnhLI4ClH52O8vxhABQIR8c5cI+RXSiIZto0=; b=ovVUIFe6u+Wxd8qhq3yYTOAoBbVgeWx943VA+Yu8hFNohpQRTW+myNrQkzqihsqPfx rVOuUa7l2x0GbQtORCCRRGmsfGLvwayD4gqlM3whWY3XFdSDm2EwRIJWZOqmYMYDUFB9 PzrmPzh+Yo48aN/ADsNoSb+NrXMz95QjUpEIA8HxJrnW6J5MoFmgOUfUoNsKX2vGMBJV g1NtPKm/czLYDQsxxfXCkQAbkvkusvF3kKzdz5Z9zRFmPf2SG/Ivsobn3EdurRwTqjFS 5CQ4ztZi5FFUecZFnMwXPJ8cXyJJlEPb3yWOfVhfI1MXPuoE1UonY3CqediApNGYapCs dtDw==
X-Gm-Message-State: APjAAAXXErq/5RwWZr8v1RecegI6TBa4l1NgSaYIFlvddcLKygD25p8/ 2M1B243Hw2591GrrC6JjsjZfedlV4US+TGaTG94=
X-Google-Smtp-Source: APXvYqz3phcAM5oqy5fumMGonK6ruNz9yNvgIp0FvcL/yy7g3y2tpf3SafXmpnAElGLN1v8CZuFoSQ3E4RUzyNgW67o=
X-Received: by 2002:ac2:4945:: with SMTP id o5mr13975170lfi.70.1567960565143; Sun, 08 Sep 2019 09:36:05 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <>
In-Reply-To: <>
From: Watson Ladd <>
Date: Sun, 8 Sep 2019 09:35:52 -0700
Message-ID: <>
To: "Hao, Feng" <>
Cc: "Scott Fluhrer (sfluhrer)" <>, "" <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <>
Subject: Re: [Cfrg] My review of the four balanced PAKE (SPAKE2, SPEKE, CPACE, J-PAKE)
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Sun, 08 Sep 2019 16:36:10 -0000

On Sun, Sep 8, 2019 at 9:14 AM Hao, Feng <> wrote:
> How much harder are many logs then one on a quantum computer? Not very.
> I believe that it is about one million times harder to do one million discrete logs than it is to do one (given that Shor’s algorithm doesn’t generate any side information from one run that would help you with the next; I also can’t think of any way to combine N points, and solve fewer than N discrete logs in a way that would allow you to recover the DLogs of the original N points).
> Looking at the likely progression of Quantum Computers, it appears probable that, once someone creates a real one (as opposed to the toys that exist now), they could break a ECDLog problem, but it may take weeks to do so (and there are not likely to be a number of them available).  Hence, one a TLA gets one, it might gain the capability to solve dozens of ECDlog problems a year, but no more than that; hence this vulnerability of SPAKE2 might be relevant.  Now, this is entirely speculation, and also it would be reasonable to suspect that the speed/cost of QCs would rise/drop fairly rapidly, and so a few years after that it might be feasible to attack the other schemes as well (at least for their high-value targets).  This scenario did seem plausible enough for me to mention it.
> In addition, for most other methods, it may be that a single discrete log might not be sufficient to break a single instance of the other schemes; however that really is currently speculation, as I have not seriously studied the issue, nor do I know anyone else who has
> IMHO, the threat is not so much a quantum computer, but a state actor (a three-letter agency) who breaks one instance of DL simply by brute-force, which will be justified if this single attack allows the adversary to break everywhere.

Maybe you shouldn't use brute-forceable parameters? Making a DLOG
instance in the prequantum world a billion times harder is simple: add
32 bytes.

> _______________________________________________
> Cfrg mailing list

"Man is born free, but everywhere he is in chains".