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

Rene Struik <rstruik.ext@gmail.com> Sat, 10 April 2021 17:51 UTC

Return-Path: <rstruik.ext@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 D8E643A16EE for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 10:51:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, NICE_REPLY_A=-0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 7atrFWBeiK33 for <cfrg@ietfa.amsl.com>; Sat, 10 Apr 2021 10:51:51 -0700 (PDT)
Received: from mail-qt1-x82f.google.com (mail-qt1-x82f.google.com [IPv6:2607:f8b0:4864:20::82f]) (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 711E43A16EF for <cfrg@irtf.org>; Sat, 10 Apr 2021 10:51:51 -0700 (PDT)
Received: by mail-qt1-x82f.google.com with SMTP id j7so6752200qtx.5 for <cfrg@irtf.org>; Sat, 10 Apr 2021 10:51:51 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=to:cc:references:from:subject:message-id:date:user-agent :mime-version:in-reply-to:content-language; bh=LGOm7XPwTDEeH0izeiuGhNMRlk9Rj71YJfT/ZQCqaFo=; b=KRVDrwp0PyScN4rfYG1qzQBcQlZWARWe8v5H0GoU4kVV7TzQbIK7nJz1kIeel4PIOO pe4PCGAtL7+I8Es83smeibb0mSYe2tH7hd4O6nhSpv3N+USyx6enjPQtQAgp1LfC+dSP FwQ3Ne8QJ9Xt+e0HeFYQ8SnGFHOBxDNRchwpKtkynuKrJktqqQQM59PoLNsPnqu/J26r +p76Are9KbuUjt2X1VZyPbRH27ahnOSuWeL/9a3PpSo4FoxeGvkB4b2cG6shgcsbK8tI 8qHdUgliWGCfaLojdUu67+iBnuljM+J69R7wCaEx/L08qa/rjbAVCn3+aTcehqkE3YK/ XXGw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:to:cc:references:from:subject:message-id:date :user-agent:mime-version:in-reply-to:content-language; bh=LGOm7XPwTDEeH0izeiuGhNMRlk9Rj71YJfT/ZQCqaFo=; b=JJxBB8oqqPqp5kXKVi5XLbaHZ7a8PP3xUq+r+pRqVaCFVdLHbbv/CeHmOPTCTRd/3l pDmXD075xuhwh8qq14STePeHJ8yNFK6SSMttD1xiF3GtZ6kYH7ZR4Sp9jJzPKg7q4l3J PJaBzxH1ysyg66u+IzRewvjy7J2+tajC9+BguMbUuqBBNoxv8kRcAOeuPXc0wypuGe2S Ng8KL6x/LRntXk9jIx8plVFY61DZsudB1iuNSlCMGOKEjYMNmCtiyoKb+vTiHmMQ+74e aZpGS6oQXUNEQty2YvnY+ctTOOBUc0JEen1B2qmQ+8MUWKMow7WRaBGoQjiNMr30EuCm gbVA==
X-Gm-Message-State: AOAM531ZpEj/JDLYxkAp9bhm+jfq0Ua4bhWIbkolDWugd5s/c5iQ7+Wc rqlxP3I8obngGDLE0s8NNxE=
X-Google-Smtp-Source: ABdhPJxnH2H/SrQen+CGoU/U76Hl/boT/0Tw598+e+FMIwhd6mrA+jVrO43uC65172QbEqSLXmvFRg==
X-Received: by 2002:a05:622a:1748:: with SMTP id l8mr18596656qtk.73.1618077109034; Sat, 10 Apr 2021 10:51:49 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:d5ce:5162:99f4:1aa? ([2607:fea8:8a0:1397:d5ce:5162:99f4:1aa]) by smtp.gmail.com with ESMTPSA id o30sm4382194qtl.8.2021.04.10.10.51.47 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sat, 10 Apr 2021 10:51:48 -0700 (PDT)
To: Hugo Krawczyk <hugo@ee.technion.ac.il>
Cc: CFRG <cfrg@irtf.org>, "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>
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>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <f9265449-6921-7b3a-7b02-5580c8bf1b75@gmail.com>
Date: Sat, 10 Apr 2021 13:51:45 -0400
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.9.1
MIME-Version: 1.0
In-Reply-To: <CADi0yUNo7o07qM2Qw8yd_eVw_-cM-9wNy3CrLw_Pif79oD_+Og@mail.gmail.com>
Content-Type: multipart/alternative; boundary="------------A2877C88484CB0231F7A26A2"
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/HlVWsgC5WC2y8AgtKW8mQvsGEpY>
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: Sat, 10 Apr 2021 17:51:57 -0000

Hi Hugo:

It would be of interest what the impact of a "broken" hash function in 
the hash to curve construction on the security of password based schemes 
would be. In the case of mappings that always yield a high-order point, 
the impact may not immediately be obvious, while with mappings that do 
not preclude low-order points this might show more readily, also to 
offline observers. This may be an interesting addition to security proof 
papers that now focus mostly on idealized functionality (such as random 
oracles).

As an aside, as I noted in my email of yesterday [1],  mappings that 
fix 
a particular image point for a specific input are trivial if the 
construction itself has "free variables" one could fix after the fact 
(e.g., pick delta such that delta*H("Hugo123")^2=t0), thereby yielding 
an immediate attack, irrespective of hash function functionality. See 
specific comment a) in [1].

All in all, it seems that guaranteeing that curve mappings would never 
yield low-order points seems prudent, esp. if it comes at roughly the 
same computational cost as ones that do not give those assurances.

Best regards, Rene

Ref: [1] 
https://mailarchive.ietf.org/arch/msg/cfrg/lAhuAaEBIgaxhf3Q81jOFjXQLz0/

On 2021-04-10 1:27 p.m., Hugo Krawczyk wrote:
> Feng, you say:
>
> > On the other hand, from the perspective of a higher layer protocol 
> (say CPace, OPAQUE and PAK), it’s simply impossible to handle the 
> exception. As soon as map-to-curve hits the small subgroup, the 
> password in a PAKE system will be compromised. Therefore, the above 
> warning is self-defeating and not meaningful.
>
> 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.
>
> (The same alarm should go off if it just happens in a run of any other 
> protocol.)
>
> (*) Of course, you should first check that you really have a preimage 
> of the identity under the hash - the most probable event to produce 
> such a result is an implementation error.
>
> Hugo
>
> PS: When you have an analysis that assumes a uniform distribution and 
> then decide to deviate from it as a way to "enhance" the design, you 
> may be introducing subtle weaknesses. An historic example (irrelevant 
> to the cases we are discussing here but illustrating the principle) is 
> Enigma's avoidance  of encrypting letters to themselves - something 
> Turing was fast to exploit
> https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties 
> <https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma#Security_properties>
>
> On Sat, Apr 10, 2021 at 11:13 AM <rsw@cs.stanford.edu 
> <mailto:rsw@cs.stanford.edu>> wrote:
>
>     Hello Feng,
>
>     "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org
>     <mailto:40warwick.ac.uk@dmarc.ietf.org>> wrote:
>     > Rsw also gave a similar example of having all zeros for the hash.
>     > Let me clarify that we are not – and shouldn’t be 
- concerned with
>     > any of such cases since the values are uniformly distributed within
>     > their respective range.
>
>     Right. And the argument is precisely the same for hash-to-curve!
>
>     Let me be perfectly clear: the property that hash_to_curve gives
>     is that the output is a uniformly* distributed point in the (big)
>     prime-order subgroup of the target elliptic curve.
>
>     At the risk of seeming didactic (in which case, apologies): the
>     identity element is indeed an element of the target group G.
>
>     Put another way: fix a generator g of group G of prime order q. Then,
>     hash_to_curve returns g^r in G, for r sampled uniformly* at random
>     in 0 <= r < q. Under the assumption that discrete log is hard in G,
>     hash_to_curve does not reveal r. Under the preimage and collision
>     resistance of the underlying hash function, one cannot choose any
>     particular r or find two inputs that hash to the same r.
>
>     I hope this helps clarify the security properties, and why focus
>     on low-order points at intermediate steps of the computation is not
>     relevant to the security of hash_to_curve as specified.
>
>     * uniformly except for some statistical distance less than 2^-100.
>
>     Regards,
>
>     -=rsw
>
>     _______________________________________________
>     CFRG mailing list
>     CFRG@irtf.org <mailto:CFRG@irtf.org>
>     https://www.irtf.org/mailman/listinfo/cfrg
>     <https://www.irtf.org/mailman/listinfo/cfrg>
>
>
> _______________________________________________
> CFRG mailing list
> CFRG@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867