From nobody Wed Jul 21 15:22:43 2021
Return-Path:
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 ; 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 ;
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 ; Wed, 21 Jul 2021 15:22:35 -0700 (PDT)
Received: by mail-qt1-x829.google.com with SMTP id l2so2959559qtp.11
for ; 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 , "Riad S. Wahby"
, Filippo Valsorda
Cc: cfrg@irtf.org
References:
<20210721191123.i3f33p3qvkwxlbtl@kaon.local>
From: Rene Struik
Message-ID:
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:
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Content-Language: en-US
Archived-At:
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
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-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=3Dx0+x1*2^m and N=3D2^m-alpha, x (mod N) =3D (x0 +alpha*x1) (mod N) =
=3D=20
ZNadd(x0,ZNmul(alpha,x1)), where ZNadd and ZNmul are operators on the=20
set ZN=3D[0..N-1). This may not be the most efficient, but using two=20
invocations of a binary operator to implement a single modular reduction =
should work for "Arthur Random Programmer" (whoever that new [to me]=20
creature is). For p=3D2^255-19, one could take m=3D255 and and alpha=3D19=
=20
(i.e., N=3Dp) or m=3D256 and alpha=3D38 (i.e., N=3D2*p), depending on lib=
ary=20
details. The above also works for NIST prime curves, Brainpool curves,=20
Gost curves, secp256k1 (all with negligible relative incremental cost).
I do not think a specification needs to spell out all implementation=20
details, as long as it is plausible that effective implementations are=20
possible.
This all being said, the suitability of curve maps (including detailed=20
steps) depends on the application(s) one wishes to cater to. {I do not=20
recall having seen such discussion, e.g., related to password schemes=20
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) =3D=3D 2^-252. =3D> Safe
> The second has a bias of about 2^-(448-224) =3D=3D 2^-224. =3D> Safe
> The third has a bias of about 2^-(256-224) =3D=3D 2^-32. =3D> 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
--=20
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 287-3867