Re: [Cfrg] using hash2curve in a protocol

Mathy Vanhoef <> Fri, 16 August 2019 23:42 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 9028D120113 for <>; Fri, 16 Aug 2019 16:42:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 oN-ldu21VZ3h for <>; Fri, 16 Aug 2019 16:42:38 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4864:20::22b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id BB2DF1200DE for <>; Fri, 16 Aug 2019 16:42:38 -0700 (PDT)
Received: by with SMTP id t24so5963468oij.13 for <>; Fri, 16 Aug 2019 16:42:38 -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; bh=tbn8EpjCTBLhhi76NZ/uoMSiPIuMPs1blp8k239EUXc=; b=sFA2dDa8udZGuC0XseKCyrQUbMsoMGvV6UaYJvdMyrr33K4d6EbqIFT/vV/Qr/5XX6 If/OPZN0g/PYqgb0/mR7GBhqTNQ4lyFp4kOMUMTXNNU/IVSoYty2eGF3dERHRu90ydsj 1qjd5d6jztbGflHorMk2N5UBO6+D6/Y8wBadS7E5o/5KyXfrkgTuUry5BQiX6uYKQyKT f5+vst6FnamxAWbpy9mdaiJcZqbjRWvAGY8GQiGq/MoAIUHlRqnDZLCCT9xjwn28EOfA 9CvSN2jtOjNloRdPv8CIh3stAiZs+l3DGzbdJp5Jh490So6pc2KYge8JsWcX7UQhR6zb eDjg==
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; bh=tbn8EpjCTBLhhi76NZ/uoMSiPIuMPs1blp8k239EUXc=; b=UT2hira+J87h+LQqcSY84kjeFqhg7pv8CyB1uaHj6/eY/df6NhIdgpdCH1LLzhssm+ aLQRc8finw2H9M7dzN+Yu4kHcPDmcvEwx4mDGxljogNr55w9wfAjwY6VD0Yf/WkuXvkC wDvnOnD7MhdKP/EW1KaB0x6N/xfGTuNgHUe9D0SfbmgrBkFMPsw4Dg3Z1hMl/C0U/yr8 ZCa4pb330w/fpNO6fMBgn0BdnZ31Q6zZPsIy0oDyn156CRZe+xcYurT98aaujn6HubZv K6aWox8zWbp6XRQxpLCXa+GOSlZCfwpyBP5fIziVZBFtmJE82IYVOwpsNMHAH+Axl3D6 9JQA==
X-Gm-Message-State: APjAAAWvmfukVhmO/DV4vMdM+TBRAUYFoVOpO9DrVwiL4zLDX46AsH+n DcsqAGk2BxJp+zf8vkHRK+3lqPsLfCTcUbAHoqy8tm1B
X-Google-Smtp-Source: APXvYqwyColR3BrcKSva8Ay+zzsMjhAdZ/mFKjpMALq4fIJhJ5n2B9e7Izf7K9GosUTpWxeLdFSkHDEcMd5bnTYg9TA=
X-Received: by 2002:aca:d7d5:: with SMTP id o204mr6655136oig.16.1565998957910; Fri, 16 Aug 2019 16:42:37 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <>
In-Reply-To: <>
From: Mathy Vanhoef <>
Date: Fri, 16 Aug 2019 16:42:30 -0700
Message-ID: <>
To: Dan Harkins <>
Cc: "" <>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <>
Subject: Re: [Cfrg] using hash2curve in a protocol
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: Fri, 16 Aug 2019 23:42:41 -0000

> On 8/10/19 8:57 AM, Mathy Vanhoef wrote:
> > Because similar changes are also being proposed in an update to the
> > Wi-Fi standard, one remark is that in the simplified_swu and
> > hash_to_ffc routine you can use PBKDF2 or similar instead of HKDF.
> > This will make possible brute-force attacks (e.g. due to
> > implementation issues or other side-channels) more costly. Since these
> > routines only have to be executed when configuring the password, and
> > not in every run of the handshake, the added overhead should be
> > manageable.
>    Given that hash_to_element() takes the password as the only
> parameter there is nothing to prevent rainbow tables from being
> generated based on the "X most popular" passwords (where X is 100 or
> 1000 or whatever). In fact, it's a given that they will be generated
> (this was done in the "Wi-Fi standard" you refer to). So any benefit
> you propose seems mostly imaginary.

Trying the "X most popular" password sounds like an online attack,
while rainbow tables are for an offline attack and over much more
passwords. What exactly do you mean?

I'll assume hash_to_element() refers to either simplified_swu() or
hash_to_ffc(). So with the current proposal, even with PBKDF2, rainbow
tables would be possible. You can include the SSID in hash_to_element
to *mitigate* this. Note the word *mitigate*, because like with WPA2,
rainbow tables can then still be generated for the X most popular
SSIDs. Nevertheless, that's still a better situation than not
including these defenses!

>    A KE is a PAKE when the advantage that an adversary gains is through
> interaction (on-line) instead of through computation (off-line). But if
> the individual act of testing a password is based on a rainbow table
> then it doesn't matter whether PBKDF2 was used or whether just HKDF was
> used. The attack will simply run through a table of predetermined elements.
> It will just be done on-line.

Not sure what you mean. Rainbow table is an offline attack, not
online. An adversary can always try the X most popular passwords
online (can be mitigated a bit with rate-limiting though).

Using PBKDF2 is to mitigate implementation bugs that leak the
hash_to_element result (a.k.a offline attacks). For example, Aruba's
EAP-pwd used predictable randomness, thereby leaking the password
element. A router or client device being compromised is another

>    The key in using a PAKE is to make sure your password is not guessable
> (which is a MUCH lower bar than saying it must be a "random n-bit PSK" *).
> Since an attack against a PAKE requires repeated active attacks (instead
> of just number crunching off-line) there is a benefit since it constrains
> attacks and forces them to be detectable, but there really isn't much of
> a gain by trying to increase the unit cost of each guess. Unless I'm
> missing something. What am I missing?

Threat model for using PBKDF2 is when the result of hash_to_element
leaks, not online attacks. See examples above.