### Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)

Andrey Jivsov <crypto@brainhub.org> Mon, 11 May 2015 06:33 UTC

Return-Path: <crypto@brainhub.org>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (ietfa.amsl.com [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id E1AE91A1B17
for <cfrg@ietfa.amsl.com>; Sun, 10 May 2015 23:33:22 -0700 (PDT)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -0.002

X-Spam-Level:

X-Spam-Status: No, score=-0.002 tagged_above=-999 required=5
tests=[BAYES_40=-0.001, SPF_PASS=-0.001] autolearn=ham

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 gGQmNaEP86ho for <cfrg@ietfa.amsl.com>;
Sun, 10 May 2015 23:33:20 -0700 (PDT)

Received: from resqmta-po-10v.sys.comcast.net (resqmta-po-10v.sys.comcast.net
[IPv6:2001:558:fe16:19:96:114:154:169])
(using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id B35961A1B0D
for <cfrg@irtf.org>; Sun, 10 May 2015 23:33:20 -0700 (PDT)

Received: from resomta-po-15v.sys.comcast.net ([96.114.154.239])
by resqmta-po-10v.sys.comcast.net with comcast
id SWZE1q0035AAYLo01WZKpK; Mon, 11 May 2015 06:33:19 +0000

Received: from [192.168.1.2] ([71.202.164.227])
by resomta-po-15v.sys.comcast.net with comcast
id SWZJ1q0034uhcbK01WZJ7d; Mon, 11 May 2015 06:33:19 +0000

Message-ID: <55504D2E.8030709@brainhub.org>

Date: Sun, 10 May 2015 23:33:18 -0700

From: Andrey Jivsov <crypto@brainhub.org>

User-Agent: Mozilla/5.0 (X11; Linux x86_64;
rv:31.0) Gecko/20100101 Thunderbird/31.5.0

MIME-Version: 1.0

To: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>

References: <5546032D.5070208@isode.com>
<EE0F9CDF-7B62-4950-A708-EAC071FCAE4F@shiftleft.org>
<5549D23F.5000107@brainhub.org> <20150506093204.GA26785@LK-Perkele-VII>

In-Reply-To: <20150506093204.GA26785@LK-Perkele-VII>

Content-Type: text/plain; charset=utf-8; format=flowed

Content-Transfer-Encoding: 7bit

Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/a_rVVyTmTMUgiZcaZTov52XDJLY>

Cc: cfrg@irtf.org

Subject: Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not
(ends on May 13th)

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.15

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Mon, 11 May 2015 06:33:23 -0000

On 05/06/2015 02:32 AM, Ilari Liusvaara wrote: > On Wed, May 06, 2015 at 01:35:11AM -0700, Andrey Jivsov wrote: >> >> I second the problem with #2 that it's not cryptographically enforceable and >> it limits some performance optimizations. Therefore, SHOULD is fine, but >> prohibiting random bytes instead of specific DRBG is overkill. TLS1.2 >> currently requires access to plenty of random/pseudorandom bytes, for >> example. > > Except there are random numbers and there are random numbers. > > What happens in practice if you feed slightly bad random numbers > into... > a) TLS nonces? > b) TLS DHE private keys? > c) TLS Encrypted premaster secrets? > d) TLS RSA signatures? > e) TLS non-RSA deterministic signature tweaks? > f) TLS non-RSA signture random r's? > > Answers: > a) Nothing. > b) Nothing. > c) Nothing. > d) Nothing. > e) Nothing. > f) Signature key compromised pretty quickly, all active security > lost. > > > -Ilari > I agree that signing algorithms like ECDSA are sensitive to the leaking of a few bits of nonces per signature. However, a secure DRBG/KDF used throughout is considered mandatory nowadays. Nonces, long-term key generation, IVs, session keys, etc, should be obtained via good DRBG/PRF anyway. Your list got me thinking regarding the issue of fault attacks on deterministic signatures. I will use the EdDSA as an example. Consider an EdDSA signing on a smartcard. EdDSA algorithm, in its canonical version, includes a message M in the calculation of the hash twice: once to calculate the ephemeral private value r for R=r*G, and second, to calculate a multiple of the long-term private signing key 'a' during the calculation of S. {R,S} is the signature. Assume that a smartcard signature implementation requires transfer of the M to the smartcard twice, due to limited memory on the smartcard and that the EdDSA cryptographically enforces that the two hashing operations are performed sequentially. As a result, the signing operation provides a reliable method to affect the second hashing, but not the first. A user (or malware) can change the M to M' at the appropriate moment, affecting the second hashing, which should be a realistic task with a sufficiently large message. The second hashing in the EdDSA algorithm is done over data that the user knows, specifically, H'=Hash(R, A, M'). It can be observed that one valid signature and one invalid, generated as described above, will recover the private key 'a'. Hint: the deterministic r remains the same and is canceled out by subtraction. This attack is similar to RSA CRT fault attacks on PKCS#1.5 deterministic signatures. A random 'r' could have helped to "blind" the private key from the above exposure. As I voted earlier, I don't think it's the the best to _prohibit_ a random 'r' for all applications, as opposed to _discourage_. A closed-source implementations may still use random values for 'r' despite the prohibition in the spec.

- [Cfrg] Elliptic Curves - signature scheme: random… Alexey Melnikov
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Stephen Farrell
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Salz, Rich
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Paul Hoffman
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Andy Lutomirski
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… David Jacobson
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Watson Ladd
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Tony Arcieri
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Alyssa Rowan
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Michael Hamburg
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Yoav Nir
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… James Cloos
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… David Jacobson
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Michael Hamburg
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Nico Williams
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Damien Miller
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… David Jacobson
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Michael Hamburg
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Adam Langley
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Daniel Kahn Gillmor
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Ilari Liusvaara
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Dan Brown
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Parkinson, Sean
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Simon Josefsson
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… D. J. Bernstein
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Ilari Liusvaara
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Paul Lambert
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Olafur Gudmundsson
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Andrey Jivsov
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Ilari Liusvaara
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Dan Brown
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Watson Ladd
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Dan Brown
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Russ Housley
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Watson Ladd
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Nico Williams
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Andrey Jivsov
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Brian Smith
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Sean Turner
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Watson Ladd
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Nico Williams
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… D. J. Bernstein
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Nico Williams
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Andrey Jivsov
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… Nico Williams
- Re: [Cfrg] Elliptic Curves - signature scheme: ra… David Leon Gil
- [Cfrg] Summary of the poll: Elliptic Curves - sig… Alexey Melnikov