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

Andrey Jivsov <> Mon, 11 May 2015 06:33 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E1AE91A1B17 for <>; Sun, 10 May 2015 23:33:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.002
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id gGQmNaEP86ho for <>; Sun, 10 May 2015 23:33:20 -0700 (PDT)
Received: from ( [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 (Postfix) with ESMTPS id B35961A1B0D for <>; Sun, 10 May 2015 23:33:20 -0700 (PDT)
Received: from ([]) by with comcast id SWZE1q0035AAYLo01WZKpK; Mon, 11 May 2015 06:33:19 +0000
Received: from [] ([]) by with comcast id SWZJ1q0034uhcbK01WZJ7d; Mon, 11 May 2015 06:33:19 +0000
Message-ID: <>
Date: Sun, 10 May 2015 23:33:18 -0700
From: Andrey Jivsov <>
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 <>
References: <> <> <> <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: <>
Subject: Re: [Cfrg] Elliptic Curves - signature scheme: randomised or not (ends on May 13th)
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-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 

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 

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.