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

Hugo Krawczyk <hugo@ee.technion.ac.il> Sun, 11 April 2021 04:22 UTC

Return-Path: <hugokraw@gmail.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 C638C3A28FC for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 21:22:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.399
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IvMV_zTiTUsF for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 21:21:56 -0700 (PDT)
Received: from mail-ed1-f52.google.com (mail-ed1-f52.google.com [209.85.208.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3C3DE3A28F0 for <cfrg@irtf.org>; Sat, 10 Apr 2021 21:21:20 -0700 (PDT)
Received: by mail-ed1-f52.google.com with SMTP id 18so11068346edx.3 for <cfrg@irtf.org>; Sat, 10 Apr 2021 21:21:20 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; 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: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <d0778523-5f5d-4327-b795-279918c1899c@www.fastmail.com> <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com> <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03> <VI1SPR01MB035772443E4DA3206E4CD4D3D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <7944D4F1-81F8-44FC-95D1-45D47733B385@shiftleft.org> <VI1SPR01MB03574E592790FD59C1ACEB84D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com> <20210410151254.7ze5pt4lpvblhk3f@muon> <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com> <VI1SPR01MB0357253A9BA2C2544D6B3F51D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
In-Reply-To: <VI1SPR01MB0357253A9BA2C2544D6B3F51D6729@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
Date: Sun, 11 Apr 2021 00:20:52 -0400
Message-ID: <CADi0yUP-Q-bjmDn-RpiVkns4c8ruK97SidFycg1cPVPJvdFB4w@mail.gmail.com>
To: "Hao, Feng" <Feng.Hao@warwick.ac.uk>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="0000000000008a9c7205bfaaba6d"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/1-q29N-LA1pUs_FTMZtq6GUsr6Y>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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: Sun, 11 Apr 2021 04:22:01 -0000

On Sat, Apr 10, 2021 at 4:37 PM Hao, Feng <Feng.Hao@warwick.ac.uk> 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
>    function. STOP USING IT IMMEDIATELY FOR ANY PURPOSE.
>
>
>
> 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
https://github.com/cfrg/draft-irtf-cfrg-opaque

>
>
> 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".

Hugo


>
> 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?
>
>
>
>
>