Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Hugo Krawczyk <> Sun, 11 April 2021 04:22 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id C638C3A28FC for <>; Sat, 10 Apr 2021 21:22:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Status: No, score=-1.399 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id IvMV_zTiTUsF for <>; Sat, 10 Apr 2021 21:21:56 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 3C3DE3A28F0 for <>; Sat, 10 Apr 2021 21:21:20 -0700 (PDT)
Received: by with SMTP id 18so11068346edx.3 for <>; Sat, 10 Apr 2021 21:21:20 -0700 (PDT)
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=2cbnkijCc52DUNLkLvMBSVgM1NGw2CbAl2cpgvCvRQg=; b=f3a7hlyIeyCaBVsss+g5eocgWNqEJoIHhjuE+LgeZlj4HsA3huqwZEhuVpQuiT6SAp wjjLxLTPiSqRgEIVegpQnRG7M6eaOWFw+A4hY1Sz/skenxtz1El3lbJUt3NadbFxqU4k IXpd6kHn+iRXiLUPAA1r8aQ+bT2x2f5T+Otd0+BArEh48qOPoAOnT8x9Y1rgdsp4TwOK +9xpupJ52GkjgZwScWMD/Q5SHrSa3+p5lMVTlY9RhCMSXSni+zV6tflk+xR8C7DBRaww zdG3lGl9NSe0st3KK6j4GYujhGAJ0XYbMdC0Ci4ERgeR686JaqcLk2sl0++0BtsOnIz5 I37g==
X-Gm-Message-State: AOAM530jki+v8QwztJt/OcwNZtIHJFZQH46dwxFb6urBNJU+WUggWpEI 4ITgNuqYkKiYZK048iQfeacE0mTUWgB+LBoBRh8=
X-Google-Smtp-Source: ABdhPJwqSNIqKlGjc0iLwIszYbqurKnmGErDdF7/CEeijCk38GRse4eN6h9r5cfTt3CbHF2hXLdscYEbdSaP4OM2fYc=
X-Received: by 2002:a05:6402:22f9:: with SMTP id dn25mr9445236edb.171.1618114878544; Sat, 10 Apr 2021 21:21:18 -0700 (PDT)
MIME-Version: 1.0
References: <> <> <> <> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <> <> <> <20210410151254.7ze5pt4lpvblhk3f@muon> <> <>
In-Reply-To: <>
From: Hugo Krawczyk <>
Date: Sun, 11 Apr 2021 00:20:52 -0400
Message-ID: <>
To: "Hao, Feng" <>
Cc: CFRG <>
Content-Type: multipart/alternative; boundary="0000000000008a9c7205bfaaba6d"
Archived-At: <>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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, 11 Apr 2021 04:22:01 -0000

On Sat, Apr 10, 2021 at 4:37 PM Hao, Feng <> wrote:

> Hi Hugo,
>    - If I understand correctly, you are saying that in the case of
>    password protocols, the unlikely event of (a correctly designed, correctly
>    implemented) hash-to-curve mapping some value to the identity has
>    irrecoverable consequences that are specific to the PAKE setting.
>    - I wanted to comment that in the case of OPAQUE, you could check
>    during password registration that a user's password maps to the identity
>    and ask to choose a new password (we are used to websites rejecting some
>    passwords). However, when that happens, the website should immediately (*)
>    sound an alarm to be heard across the universe. You would have found a
>    preimage of the identity under a RO-modeled hash function. Either you are
>    observing an event with probability, say, 2^{-256}, or you are observing a
>    hugely more probable event: Someone broke the one-wayness of the hash
> As you know, hash-to-curve has three components: hash_to_field,
> map_to_curve and clear_co_factor. For the sake of discussion, let’s remove
> clear_to_factor as it has been a source of confusion, and this removal
> doesn’t affect our analysis in any way. Also for generality, let’s assume
> the small subgroup size is L. The value L depends on the group setting. In
> MODP, L is large, but in EC, it’s usually small, but that’s the
> implementation detail.
> OPAQUE has a registration phase. In your paper, you assume registration is
> done securely but without details. Therefore, I have to fill in the details
> below according to my understanding (apologies if I got anything wrong, but
> in that case, do correct me!)

You can see the details here

> Unlike CPace and other balanced protocols which may use an out-of-band
> channel (visual, sound etc) to distribute a low-entropy secret, OPAQUE has
> to do the registration over a network since it involves exchanging data of
> long strings (k, Ps, c). However, in a typical PAKE context, there is no
> pre-existing secure channel. A natural solution would be to do the
> registration over SSL/TLS (which introduces a PKI which is what PAKE aims
> to avoid). But a PKI is needed only for a registration phase, so let’s
> assume registration is done over SSL/TLS.
> The scenario we consider is what happens if the output of map_to_curve
> falls into a small subgroup. The user has to reject it and choose another
> password, but the timing side channel gives away the exact oracle to a
> passive attacker to do an offline dictionary attack. Note that the attacker
> doesn’t need to read the content in SSL/TLS, but just observes the
> communication time. He can exclude passwords that don’t fall into the small
> subgroup.

I don't see any timing attack here. We are talking about a user that
chooses a password that is mapped to the identity (let's call such a
password *magic) *and is asked to choose a new one. Only non-magic
passwords are allowed. All the attacker learned is that the user *initially*
chose  a magic  password that was rejected and then chose a regular
non-magic password. It knows nothing about the user's accepted password.

Of course, this is a purely fictional discussion since the probability to
have a magic password in a dictionary of 2^128 passwords (as rich as an
AES-128 random key) is 2^{-128}  (for curves of size 2^256).

This reminded me of the well known medieval question of "how many angels
can dance on the head of a PIN" but in the present case it seems more
appropriate to ask "how many angels can dance on the head of a password".


> So the registration phase doesn’t help you. Even if it’s done over a
> secure SSL/TLS channel, it’s sufficient if the attacker can observe the
> timing delay in the communication.
> Therefore, the best one can do is to hope map-to-curve never falls into a
> small subgroup. But in that case, wouldn’t it better to preclude small
> subgroup points from map-to-curve by design?