Re: [Cfrg] Comments on draft-irtf-cfrg-pairing-friendly-curves

Yumi Sakemi <yumi.sakemi@lepidum.co.jp> Mon, 18 May 2020 14:20 UTC

Return-Path: <yumi.sakemi@lepidum.co.jp>
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 243803A00D2 for <cfrg@ietfa.amsl.com>; Mon, 18 May 2020 07:20:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.001
X-Spam-Level:
X-Spam-Status: No, score=0.001 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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=lepidum-co-jp.20150623.gappssmtp.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 ZrzDe82XSHzv for <cfrg@ietfa.amsl.com>; Mon, 18 May 2020 07:20:48 -0700 (PDT)
Received: from mail-lf1-x142.google.com (mail-lf1-x142.google.com [IPv6:2a00:1450:4864:20::142]) (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 70E213A00C9 for <cfrg@irtf.org>; Mon, 18 May 2020 07:20:48 -0700 (PDT)
Received: by mail-lf1-x142.google.com with SMTP id h188so8226460lfd.7 for <cfrg@irtf.org>; Mon, 18 May 2020 07:20:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lepidum-co-jp.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=iUYnBieMftCWcRCYnLxYSncmZIo8sl4jZbwSMQpHCCA=; b=c/UO8n5iH9rB+ZQkPzZjPhDgx6g80/e/KGs6Zav6pyS1T66p6NcPx53frL7HHsgNix tx1edDGjGRVGXam7jVF1NBchoL3PNTroRzAqObkP19x5Yk4t3xEuJN9YxIFYAqfweZpT ZslXpwiDMokwYKVG1tGN5vrLF+/ElMZjoJ8hKL5C5bP/fmfzrLLJunACJamlAhKtQTZU wKPgiMKwtg8TB2TezBQQsug4it+gczpCguRPaZdV7QDm6WTxDVVz2tXoPpbycCyCu8R4 aOE7Ea4vyc8mlh1J+NoX/+Q3yof0SmJQUcmveauyTeO0gSuXGmHU4UGPb8Eq1ZMUvYFu bC1g==
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:content-transfer-encoding; bh=iUYnBieMftCWcRCYnLxYSncmZIo8sl4jZbwSMQpHCCA=; b=InCp8nk5JyQx8yJI4GCKCZm4Vso0mZxDxzp6apvlcl0b8YLRE0OjTjZ5IByw0Jbkgw XykuXPPb3C0Ucq9NehroGI8HJLxDyASkOLzXurYAIskKuwe4yw+tJkubxlwPA8IXHXD8 tocXIHOD61OZ/JSMGnnSptPGgl3dFHYmPYM3djvmj3H3AK8TEIK+7MMJX/ShQqDChrPx 1+2RWX+bD3lYSUS2oxyLpGO+gyYBuo9SLaEL+Uwr24HjkV4irm5d7KsGqpb15MXPtf47 hcLt5Iw8vqfyekhKa6iitBWfRCspA5PjvqxXFrtzA36cgV4Z4dY7I8WeDxrP3dq8QQON dPgg==
X-Gm-Message-State: AOAM532UB3EBG03icGhcUxPb3NZ++0IHvDTUUVgCRpazi2bjc+ywZ6nb PF8lSpQaOPdJeVNxvwea4CxAuit0oNWKmpFc8GThdqz9HeM=
X-Google-Smtp-Source: ABdhPJxYbtwUJ9M1HN4MVW1s6h/ESB/tW6S42QuXcKRgjgZzuAVclyxDEdLTv9FBYLNNYHhEn6VMCeVhso1g2IV7/YI=
X-Received: by 2002:ac2:5e24:: with SMTP id o4mr11722330lfg.37.1589811646311; Mon, 18 May 2020 07:20:46 -0700 (PDT)
MIME-Version: 1.0
References: <CACsn0ckfA1WLOA9L8j_9pcOoaVBhjYX4jX2M0Bk78h8eniYA7A@mail.gmail.com>
In-Reply-To: <CACsn0ckfA1WLOA9L8j_9pcOoaVBhjYX4jX2M0Bk78h8eniYA7A@mail.gmail.com>
From: Yumi Sakemi <yumi.sakemi@lepidum.co.jp>
Date: Mon, 18 May 2020 23:20:35 +0900
Message-ID: <CAA4D8KbE+ZWvjkd6h0xii2PqNt8yeXut=WR2f+47pg=spSeoOA@mail.gmail.com>
To: Watson Ladd <watsonbladd@gmail.com>
Cc: CFRG <cfrg@irtf.org>, Tetsutaro Kobayashi <tetsutaro.kobayashi.dr@hco.ntt.co.jp>, SAITO Tsunekazu <tsunekazu.saito.hg@hco.ntt.co.jp>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/EmBgeRLFibynQSccCNZueuT6Rrc>
Subject: Re: [Cfrg] Comments on draft-irtf-cfrg-pairing-friendly-curves
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: Mon, 18 May 2020 14:20:51 -0000

Dear Watson

Thank you for many useful comments!
I'm so sorry for my late reply.
I discussed about your comments with the co-authors.
According to the four comments you have sent, we answer as follows.

1. About equivalent security and adoption of BLS12-381
Thank you for your detailed explanation and suggestions for equivalent security!
As you pointed out, we agree that a simple expression of bit security
is misleading.
So, we will add a description of equivalent security to our draft.
Also, regarding BLS12-381, it was excluded from the candidates due to
our lack of investigation.
However, we received information from a reviewer at Expert Review and
found that BLS12-381 matches our selection policy from the perspective
of efficiency and security.
Therefore, please rest assured that BLS12-381 will be the recommended
parameters as well.

2. Description of detailed pairing algorithm
We also recognize that there are calculation methods using Affine
coordinates, projective coordinates, Jacobian coordinates, etc.
We considered, but we think that showing a specific algorithm would
reduce the flexibility of the implementers.
Therefore, we describe the most basic method as an algorithm, and
describe that there are isomorphism techniques, for example.

3. Security consideration
As you pointed out, the explanation of attacks in security
considerations is insufficient.
I appreciate your comments.
We will update the description of the security considerations by
adding the following.
- Checking whether elements exist in an appropriate group
- Checking for side channel attack resistance
- Checking whether range of coefficient is appropriate

4. About editorial comments
Regarding the English expression, we have received many comments from
the reviewer at Expert Review,
and we plan to entirely improve it in version 05.
Also, regarding Table1, one of our selection policies is that there
are multiple implementations,
 so we consider that Table1 is essential as the evidence.
On the other hand, as you pointed out, Table 1 is very large, and it
reduces the readability of the draft,
so we will consider whether we can devise an expression.
(For example, we move Table1 to Appendix and refer it)

Finally, thank you for reading our draft!
I think it will be a better draft to reflect your comments!

Best regards,
Yumi

2020年5月9日(土) 3:19 Watson Ladd <watsonbladd@gmail.com>:
>
> Dear cfrg,
>
> I’ve looked at draft-irtf-cfrg-pairing-friendly-curves and have a few
> comments I hope can be addressed before the next version. Cloudflare
> has built a number of products and experiments on top of pairing based
> curves and would like to see advancement of this draft.  It’s a good
> step towards standardization of type III pairings but, to be as useful
> as possible for implementors as well as prevent fragmentation, I have
> four issues that I think need to be addressed.
>
> One issue that persists is the disconnect between  security levels and
> recommendations. At the textual level BLS12-381 is introduced as an
> alternative to BN468 at the 128 bit security level, but then the
> discussion seems to indicate the security level is really 117 bits. In
> practice few people care about  a factor of a thousand difficulty in
> breaking, but plenty of people do care about the performance hit of
> that bigger base field. It would be nice to have only one
> recommendation, and I think it’s pretty clear that BLS12-381 is going
> to be much more useful.
>
> This relates to a wider trend that I think I counterproductive: using
> single numbers like 128 to denote security levels. What does this
> mean?  Naively one might think that the effort to conduct key recovery
> on AES-128, find the discrete logarithm of P256 elliptic curves, and
> compute the discrete log of a point on the curve from the draft are
> the same, since they are all 128 bit security. This is true for
> attackers that are only conducting one attack and who have probability
> 1 of succeeding. Actual attackers have multiple targets and do not
> need to have probability 1 of success. For the problem of recovering k
> from AES_k(0), each additional target AES_k2(0), AES_k3(0), etc, is
> free, and the probability of success goes up linearly with the number
> of queries.
>
> In the multitarget scenario contrast recovering the discrete log of Q1
> via a distinguished point algorithm doesn’t help with recovering Q2,
> etc. By contrast AES is considerably weaker than the discrete
> logarithm problem with the same bit security. The probability of
> success is then quadratic in the effort: an attacker satisfied with a
> success probability of ¼ has to do ¼ the work for AES, but  a full ½
> of the work for ECC. These are very different levels of security, so
> the use of the same number to describe them is counterproductive.
>
> Similarly, the security of the finite field Diffie-Hellman problem in
> medium size extensions is one where an attacker faced with a number of
> targets can do a substantial amount of shared work, reducing the cost
> of each additional broken key.  Furthermore there is substantial
> uncertainty about the runtime, particularly with the sieving step and
> search for good polynomials, as well as a lack of good experiments to
> quantify the runtime heuristics. The draft does well to mention a few
> recent papers to justify the numbers presented, but there is still
> substantial uncertainty.  The benign outcome is that the single number
> gives no practical insights; the worse outcome is that it guides users
> towards poor choices. In light of the advent of quantum computers the
> long term security of these curves is broken anyway.
>
> Secondly, the draft presents a real opportunity to be useful to
> implementors, that will be missed without additional practical advice
> or recommendations. Appendix A omits a particularly efficient
> algorithm due to use of affine coordinates and division, and many
> applications can make use of optimizations that combine the final
> exponentiation across pairings since they are computing a multipairing
> product. From experience pseudocode that expresses a reasonably
> efficient algorithm, together with information on avoiding side
> channels and optimizations for the frequently used optimizations would
> be very beneficial. That’s particularly true for handling invalid
> inputs safely, a topic frequently neglected but essential for
> security.
>
> Both RFC 7748 and RFC 6090 provide this guidance to implementors and
> are much more useful for it. Including these extra practical
> recommendations is a lot of work, but avoids so much more effort
> afterwards when needing to repeat the translation from paper into
> pseudocode, as well as hopefully avoiding common security pitfalls.
> Bitter experience has shown that pointing to a literature reference
> has shortcomings.
>
> Thirdly the security considerations section is woefully inadequate.
> What are the considerations implementors should be aware of when
> implementing this document and that those who use it should be aware
> of? Are there attacks based on invalid data that need to be
> considered? How does one validate group elements efficiently? All of
> these are important details that I think should be addressed here. RFC
> 7748 does a decent job and should be looked to as a model.
>
> Lastly there are a number of small tweaks I would make to the English
> throughout the document in the interest of readability: fixes to
> tense, articles, etc. I suspect the definition of nondegeneracy is
> incorrect due to recorded clauses: it should read “e(S, T)=1 for all T
> if and only if S=O_E”, etc. I’d be happy to submit a PR with the
> changes if I knew where it lived in git.
>
> The table of implementor and standardization choices I don’t think
> adds much to the text and should be removed. Likewise, the laundry
> list of applications is good motivation, but it could be shortened
> without losing too much.
>
> Thanks to the authors for advancing this draft, and I’m happy to
> discuss these points further with them or others on the list/contribute text.
>
> Sincerely,
>
> Watson Ladd
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg



-- 
Yumi Sakemi
Lepidum Co. Ltd.
E-Mail: yumi.sakemi@lepidum.co.jp