Re: [CFRG] hash_to_field requires implementing a new 25519 field op

Rene Struik <rstruik.ext@gmail.com> Wed, 21 July 2021 22:22 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 D12FA3A2CAA for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:22:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 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, NICE_REPLY_A=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham 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 06MycIGWXri5 for <cfrg@ietfa.amsl.com>; Wed, 21 Jul 2021 15:22:36 -0700 (PDT)
Received: from mail-qt1-x829.google.com (mail-qt1-x829.google.com [IPv6:2607:f8b0:4864:20::829]) (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 21D953A2CA6 for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:22:35 -0700 (PDT)
Received: by mail-qt1-x829.google.com with SMTP id l2so2959559qtp.11 for <cfrg@irtf.org>; Wed, 21 Jul 2021 15:22:35 -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-transfer-encoding:content-language; bh=OvuTG4jRNGbinhyIbhFsWP9wzYGxDBJMXfZJTW9lIMY=; b=SNPu8h772tcjWDvP/BIZxz4/lSwNYnqk7qveVAoL5QyY0ys24diXCsYhtdJULleB81 dxcrcJuqScZkd3qB12vwn97paH4jAXbQmyTSS6iw72P9d8SB5sGlBtVVGYZgpBJ3ht0B NIuk8bvz1UbDy07i02WgiR4wYG1Gh0oVkUaPzTkncIPV6MSHjyMsvVPak0CAGQUpMABr W+VyNv0yKEjEJaj8G2ruFXWlvFdc4XKvasm6gpA/sNn0EBplkWy3sPaeLpNK0jJJyHqV aKTbD/8tL9Ua/Bh7isfCsy6jS+jIrt1YY7o0rnKb5yTUiTXzbIK/lrzoHegKohMQqhvg EY0g==
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-transfer-encoding :content-language; bh=OvuTG4jRNGbinhyIbhFsWP9wzYGxDBJMXfZJTW9lIMY=; b=MbybKPc+1V8r33qdNH9YBrT1vKA3hWjdmUFx9VaajSuyPKBB9E5mb9dYxLC0a8wb5A cU0KvekSC0b3Fg4bbz8igUEqCqJbwRAVs1yMGPOx+F6Q/CrrMZJDKtVS3fKCeAsDjfyg sMlny9OPhEArqFWYKiVymHO+CE9+pA4iO9ui3XqMuJaL1DHNwzOP2y3aRpU+PjuntILL 1H7OOOwd95OQ+t4baSRBGYXsYlM2gVADqfssvfFTD7gbgfNCHDv0dHZrtcleIpZv7dno GTVF1frPKOpYrwYCDUvy9AbK6oWgpwXEj6RosC9IPEoEW06Yh2/CM+jJT8DlgGjq/viF QcUA==
X-Gm-Message-State: AOAM533pobaPqGx2pUW3tGkjG4mU4AmfHRyuXZ8kvzZLEdvA1pv/GHk7 7RJA8FLXkB1AeVCks7AkNeAsQVrMMs0=
X-Google-Smtp-Source: ABdhPJx8ZeudN3J0+X9VhXkVt7FBHYSb4KIlwXcJYNsaFl+3iRsAPNyYq87njnJ2exAnamZkD3FgDw==
X-Received: by 2002:ac8:5e51:: with SMTP id i17mr25929483qtx.359.1626906154042; Wed, 21 Jul 2021 15:22:34 -0700 (PDT)
Received: from ?IPv6:2607:fea8:8a0:1397:a57f:e69a:8852:5d5a? ([2607:fea8:8a0:1397:a57f:e69a:8852:5d5a]) by smtp.gmail.com with ESMTPSA id 8sm10975586qkb.105.2021.07.21.15.22.33 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 21 Jul 2021 15:22:33 -0700 (PDT)
To: Loup Vaillant-David <loup@loup-vaillant.fr>, "Riad S. Wahby" <rsw@jfet.org>, Filippo Valsorda <filippo@ml.filippo.io>
Cc: cfrg@irtf.org
References: <aaa46d82-f05d-4558-8a2a-6d945fe9cb1d@www.fastmail.com> <20210721191123.i3f33p3qvkwxlbtl@kaon.local> <c16f6fe23f1b11e9a311f4b57cabfbef4a517b58.camel@loup-vaillant.fr>
From: Rene Struik <rstruik.ext@gmail.com>
Message-ID: <aebaaa16-8fda-bcf0-067c-e81d257a768a@gmail.com>
Date: Wed, 21 Jul 2021 18:22:31 -0400
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.12.0
MIME-Version: 1.0
In-Reply-To: <c16f6fe23f1b11e9a311f4b57cabfbef4a517b58.camel@loup-vaillant.fr>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Language: en-US
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/fgMP3zGoD84FLdg3LvhCSpThhJE>
Subject: Re: [CFRG] hash_to_field requires implementing a new 25519 field op
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: Wed, 21 Jul 2021 22:22:42 -0000

Hi Loup, Filippo:

I do not see the modular reduction implementation issue:

if x=x0+x1*2^m and N=2^m-alpha, x (mod N) = (x0 +alpha*x1) (mod N) = 
ZNadd(x0,ZNmul(alpha,x1)), where ZNadd and ZNmul are operators on the 
set ZN=[0..N-1). This may not be the most efficient, but using two 
invocations of a binary operator to implement a single modular reduction 
should work for "Arthur Random Programmer" (whoever that new [to me] 
creature is). For p=2^255-19, one could take m=255 and and alpha=19 
(i.e., N=p) or m=256 and alpha=38 (i.e., N=2*p), depending on libary 
details. The above also works for NIST prime curves, Brainpool curves, 
Gost curves, secp256k1 (all with negligible relative incremental cost).

I do not think a specification needs to spell out all implementation 
details, as long as it is plausible that effective implementations are 
possible.

This all being said, the suitability of curve maps (including detailed 
steps) depends on the application(s) one wishes to cater to. {I do not 
recall having seen such discussion, e.g., related to password schemes 
and pairing-based applications.}

Rene

On 2021-07-21 5:42 p.m., Loup Vaillant-David wrote:
> Hi,
>
>
>> But (as you know) in general it is not safe to reduce ceil(log2(p))
>> bits mod p, since this can give significant bias for general p. The
>> goal in the draft is to specify a hash-to-field method that is safe
>> for any p without requiring any parameter except the security level
>> in bits, k, and which gives bias roughly 2^-k. Adding parameters is
>> dangerous in the sense that incorrectly choosing parameters gives a
>> hash-to-field function that looks OK but is subtly broken.
> The three primes I know of are pretty clear cut. Two are clearly safe,
> the other clearly is not.
>
> 1. 2^255 - 2^4 - 2^1 - 1               (Curve25519)
> 2. 2^448 - 2^224 - 1                   (Curve448)
> 3. 2^256 - 2^224 + 2^96 + 2^192 - 1    (P-256)
>
> The first  has a bias of about 2^-(255-4)   == 2^-252. => Safe
> The second has a bias of about 2^-(448-224) == 2^-224. => Safe
> The third  has a bias of about 2^-(256-224) == 2^-32.  => Unsafe
>
> So, Curve25519 and Curve448 have biases well below 2^-128, and as such
> are virtually undetectable (you need about 2^128 samples, which you are
> not going to get). P-256's bias however can be detected with as little
> as a few billion samples, and as such is easily detected in realistic
> settings.
>
> Yes, having yet another parameter is a bummer, but as long as we don't
> use primes with a bias close to 2^-128, choosing an acceptable
> threshold (like 2^-128) should not be too much of a problem.
>
>
>> In my mind the second is the much more convincing argument, because
>> every EC-relevant field library that I'm aware of implements a wide
>> reduction already, inside the multiplication routine (which gives a
>> p^2-size intermediate result).
>>
>> So this
>>
>>> Curve25519 implementations will all have to implement and expose
>>> a new field operation (like https://git.io/JlU6L) which will be
>>> only
>>> used for h2c, meaning it will not be well tested or maintained,
>>> or h2c implementations will have to roll their own, probably
>>> in variable time.
>> isn't really true. If one exposes the ceil(log2(p^2)) bit reduction
>> that's already implemented for multiplication, then there's no need
>> for extra code, and maybe even no need for extra tests.
> Wait a minute, that reduction is not *nearly* as large as you make it
> out to be.  Let's take a look at Curve25519's ref10 implementation on
> SUPERCOP. You would think that because the result of the multiplication
> (before carry propagation) is stored in 10 64-bit signed integers, the
> number they represent easily exceeds 2^512, or even approaches 2^640.
>
> Nope.
>
> In fact, that number those wide limbs represent does not even exceed
> 2^293. That's because the limbs overlap: even though they're 63-bit
> wide, they're only 25 or 26 bits apart.
>
> How then can we compute the multiplication *at all*, would you say?
> I've explained it on https://loup-vaillant.fr/tutorials/poly1305-design
> Search for "Cheating at modular arithmetic".
>
> The trick is to perform part of the modular reduction by taking
> advantage of the fact that you're dealing with a pseudo Mersene prime.
> See, when you work modulo 2^255-19, multiplying 2^255 is the same as
> multiplying by 19. So you can just shift numbers to the right 255 bits,
> and multiply by 19 to compensate. That's why field multiplication has
> those *19 all over the place: instead of representing the number over
> twenty limbs, we just shift directly to one of the ten least
> significant limbs, and multiply by 19 to compensate.
>
> Long story short, your trick won't work. We will need to implement a
> separate reduction routine.
>
> ---
>
> And before someone is tempted to point out that EdDSA involves the
> reduction of a 512-bit modulo the prime order of the curve that we
> could reuse, hold your horses: while TweetNaCl and Monocypher uses a
> fairly generic algorithm that can easily be adapted by changing a
> single constant, I've seen ref10 use a highly optimised reduction where
> the value of the order of the curve is deeply embedded in the
> algorithm. I personally could not even make sense of it, so I don't
> think it can be adapted.
>
> Moreover, keep in mind that 2^255-19 is a pseudo Mersene prime, and as
> such can use a much faster reduction algorithm: just shift the most
> significant bits to the right, multiply by 19, and add it to the least
> significant bits. You'll get a full reduction in a couple iterations
> (less if you're clever). Still, implementing this is not for Arthur
> Random Programmer. I personally would test it quite extensively, and
> write a proof of correctness on top.
>
>
>> Would it partially allay your concerns if the hash-to-field section
>> explicitly pointed out that it's possible to use the multiplication
>> routine (or, well, half of it) for the wide modular reduction?
> Since to my knowledge it is *not* possible, it would actually make me
> very worried: either I missed something big (and I want to know), or
> the RFC writers did (and it needs to be pointed out).
>
> Loup.
>
>
> _______________________________________________
> 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