IETF Logo Mail Archive

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.

v2.23.0 | Report a Bug | By Email