Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Dan Brown <dbrown@certicom.com> Mon, 24 September 2012 18:37 UTC

Return-Path: <prvs=261400c488=dbrown@certicom.com>
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 1C32A21F8876 for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 11:37:56 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.782
X-Spam-Level:
X-Spam-Status: No, score=-2.782 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, EXTRA_MPART_TYPE=1, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=1.396, RCVD_IN_DNSWL_MED=-4, SARE_GIF_ATTACH=1.42]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 7DJG+vLHbcyG for <cfrg@ietfa.amsl.com>; Mon, 24 Sep 2012 11:37:51 -0700 (PDT)
Received: from mhs061cnc.rim.net (mhs061cnc.rim.net [208.65.73.35]) by ietfa.amsl.com (Postfix) with ESMTP id 9991821F887B for <cfrg@irtf.org>; Mon, 24 Sep 2012 11:37:50 -0700 (PDT)
X-AuditID: 0a412830-b7fab6d000006b80-c2-5060a879eec3
Received: from XCT102CNC.rim.net (xct102cnc.rim.net [10.65.161.202]) (using TLS with cipher AES128-SHA (AES128-SHA/128 bits)) (Client did not present a certificate) by mhs061cnc.rim.net (SBG) with SMTP id 4D.16.27520.978A0605; Mon, 24 Sep 2012 18:37:45 +0000 (GMT)
Received: from XCT111CNC.rim.net (10.65.161.211) by XCT102CNC.rim.net (10.65.161.202) with Microsoft SMTP Server (TLS) id 14.2.298.4; Mon, 24 Sep 2012 14:37:44 -0400
Received: from XMB111CNC.rim.net ([fe80::fcd6:cc6c:9e0b:25bc]) by XCT111CNC.rim.net ([::1]) with mapi id 14.02.0298.004; Mon, 24 Sep 2012 14:37:44 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'David McGrew (mcgrew)'" <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
Thread-Index: AQHNkb3A2Mn62duUhkur3ySu3qHaQ5eZv7lQ
Date: Mon, 24 Sep 2012 18:37:43 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF50B9A9C@XMB111CNC.rim.net>
References: <CC7768A9.EDA64%mcgrew@cisco.com>
In-Reply-To: <CC7768A9.EDA64%mcgrew@cisco.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.248]
Content-Type: multipart/related; boundary="_004_810C31990B57ED40B2062BA10D43FBF50B9A9CXMB111CNCrimnet_"; type="multipart/alternative"
MIME-Version: 1.0
X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFjrNJsWRmVeSWpSXmKPExsXC5bjwlG7lioQAg+c3pCy6fxxksri66g+7 A5PHlN8bWT0mbzzMFsAU1cBok5RYUhacmZ6nb2eTmJeXX5JYkqqQklqcbKvkk5qemKMQUJRZ lphcqeCSWZyck5iZm1qkpJCZYqtkoqRQkJOYnJqbmldiq5RYUJCal6Jkx6WAAWyAyjLzFFLz kvNTMvPSbZU8g/11LSxMLXUNlex0Ezp5Mo7u/sFY8GUdU8W5L1fYGhjvdjN1MXJwSAiYSFxs 4O9i5AQyxSQu3FvP1sXIxSEk0MckcelMMzOEs5JR4tKcvVCZOYwSTecPs4C0sAmoStw/eo4Z xBYRCJZouPSeFcQWFsiQWPrlPTtEPFPi+9S/bBC2kcSvFZ/A4ixAvWeX3AWzeQXcJO78eQ02 U0hAV2Lp+kOMINdxCuhJTD9SBhJmFJCV2H32OhOIzSwgLnHryXwmiKtFJB5ePM0GYYtKvHz8 jxXCVpSYP/cS2M3MAp2MEk9/3mGF2CUocXLmE6hdChJXru9jmcAoNgvJ3FnIemYh6YEoypWY 3dHPCGHrSCzY/YkNwtaWWLbwNTOMfebAYyZMcR2JzZd2Qs1RlGjrnA21bCmjRNfi80AJDrCi 9s+iMDVTuh+yL2DkXcUomJtRbGBmmJyXrFeUmauXl1qyiRGcBjUMdjC+f29xiFGAg1GJh/fQ rIQAIdbEsuLK3EOMEhzMSiK8V7qAQrwpiZVVqUX58UWlOanFhxjjgVEwkVmKOzkfmKLzSuKN DQzI4SiJ884VjQ4QEkgHJurs1NSC1CKYDUwcnCAXcEmJFAPTbWpRYmlJRjwoK8QXA/OCVANj bY2ctuOHAw4hscF1Fe5n5gpKv7CRErXQcd6mY9+rVJJ4XWZX2slqH62v2x9ves0XHHAxWndq 7IRLqnyyQm/U+TU3eucIH3ZJYdSYr3Iq6aDPpY7ls7ae7ir/zL9wk2vW8jOpUmYXovVf8z6I 23Y52ejLiaxHl/afipySWy588eOfvrP1q5YqsRRnJBpqMRcVJwIATenrV94DAAA=
Subject: Re: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
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, 24 Sep 2012 18:37:56 -0000

Dear CFRG subscribers,

0. Summary of this email (because it is rather long, sorry)

The I-D that is the topic of this thread addresses a major issue in using (EC)DSA, and provides a good solution, but there is a simpler and more standards compliant solution, which is described below.  This I-D also addresses a minor issue in using (EC)DSA, and provides a good solution.  Though addressing a minor issue, it is worth an RFC, but perhaps with greater coordination with other standards.


1. The Issues

A general issue is that ephemeral private keys (EC)DSA must be secret (and must not even possess certain kinds of bias) and also must not repeat for distinct messages, (even show other weaker types of interdependence). Otherwise, known attack algorithms can be used to learn the static private key.

A major issue, which can be viewed a special case of the general issue, is how to handle an (EC)DSA instantiation with no live entropy source for generating secret ephemeral keys.

A minor issue is to purposely make (EC)DSA operate in a mode that generates a constant signature per message.   Firstly, this mode avoids certain attacks (on repeated keys per message), but is not the only way to do so.  Secondly, this mode makes certain security proofs work.  Thirdly, perhaps some unknown attacks exploit a small leakage per each different (but unbiased) ephemeral key per message, in which case this mode would resists those attacks.


2. A Simpler and More Compliant Solution to the Major Issue

A solution (simpler than in the I-D) to the major issue is to generate the (EC)DSA static and ephemeral keys with a pre-seeded DRBG, the first being the static private key, and the remaining being ephemeral keys.  Just to be clear: the initial DRBG must be seeded with enough entropy.

Alternatively, and along the lines of the I-D, all ephemeral keys could be generated using a single DRBG instance seeded with the static private key.  This is not very compliant for two reasons: (1) the static private key is being use for another purpose, and (2) standards such as NIST Draft Special Publication 800-90C defined an entropy as inside an RBG boundary and not accessible to the application using it, such as the (EC)DSA implementation, so the general RBG API does not allow the external control the entropy.

If there is some risk that this single DRBG is multi-threaded and could possibly supply the same key to two different threads (which it should never ever do, and this would be a major implementation error), then one could add the message hash as an additional input the message digest.  This would help avoid the fatal problem of a repeated ephemeral across different messages.  In other words, the (EC)DSA implementation could try to be very robust and overcome a potential deficiency in a (faulty) DRBG implementation.

Perhaps another I-D explaining this simpler solution would help the IETF.

By the way, I agree with that using HMAC_DRBG may well be quite helpful in getting it deployed, because current ANSI/NIST compliant implementation should already use HMAC_DRBG (or another the SP 800-90A DRBGs).  I also agree, that using HMAC_DRBG helps with compliance, but with the following reservation.    I also agree that although this I-D may not comply with various standards, it is probably a harmless violation.


3. Solving the Minor Issue

On the minor issue, which may be main motivation for the I-D, of generating a constant signature per message, there is only a small benefit.  It would nice if a solution, unlike the I-D, could be strictly compliant to the other RBG standards.

I am reviewing SP 800-90C, but so far I haven't found any way to use it, in strict compliance, to achieve an (EC)DSA with constant signature per message.  Again, by strict compliance, I mean the (EC)DSA is not allowed to see, touch, or influence the entropy inputs, and also the entropy inputs cannot be replicated.  The closest I could get is as follows.  First, instantiate an initial DRBG with real entropy.  It serves as a source of entropy input SEI for further DRBGs, using the notion of an "RBG chain" from NIST's Draft Special Publication 800-90C, subsequent DRBGs can be instantiated using this SEI.  As in the I-D, one DRBG instance could be instantiated per signature.   Note that this requires that this per-signature DRBG be seeded using the output of the initial DRBG, which generates some new random bits for the purposes of the seeding.  The message digest, could be fed in as additional input (or nonce).  However, in order to have a constant-signature-per-message, the (EC)DSA would have to maintain a database of message to ephemeral key values.

Perhaps, I'm interpreting 90C too strictly, and it does allow entropy-input replication.  But I would be surprised if it did, because in general, that could be very bad if not carefully handled.  In that case, the initial DRBG could be called once as SEI, to obtain an initial seed, then this since can be replicated in the sense that is used to instantiate multiple other DRBGs.


4.  Question about deterministic modes

I am also not totally confident that running (EC)DSA with no new entropy per ephemeral key does not lose any security.  For example, it may cause the security of (EC)DSA to rely more heavily on the properties of the hash functions, than it would normally.  Any thoughts?


5. Regarding Anonymity

The security consideration section of the I-D mentions anonymity.  A message and its ECDSA signature (r,s) can be used to reconstruct the public key (or a small set of possible candidates for the keys), and should probably not be regarded as anonymous.  (Doing so for DSA seems to be hard problem.)  So, the security consideration could perhaps be clarified, to avoid giving the wrong impression.  (At this point, I don't have a suggested re-wording, but I could probably be


6. Regarding some of David Kravitz's Comments

My reservations about compliance are also related to David Kravitz's concern, which I agree with. The danger may be that this non-compliant way of using the DRBG in this I-D is mistakenly ported from (EC)DSA over to some other applications, with some potentially bad consequences.  David Kravitz's counter proposal is also not compliant with the current (EC)DSA standards, which that the keys be generated using an approved RNG.


7. Modifying other (EC)DSA standards

So, if a deterministic mode of (EC)DSA is really desired, and deemed secure, should the (EC)DSA standards be amended to loosen this requirement on the key generation, such as in the manner of the I-D, or as in Kravitz's alternative solution?

I can take this question to ANSI X9F1 working group for the next revision of ANS X9.62 (ECDSA), which I am currently editing.

Best regards,

Daniel Brown

Research In Motion Limited




[cid:image001.gif@01CD9A50.EC8235B0]



From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of David McGrew (mcgrew)
Sent: Thursday, September 13, 2012 10:41 AM
To: cfrg@irtf.org
Subject: [Cfrg] call for review: Deterministic Usage of DSA and ECDSA Digital Signature Algorithms

Hi,

Thomas has updated his individual submission on deterministic [EC]DSA.   I think this is useful work that deserves to move forward to RFC, and that the research group should support it (based on my own opinion and the positive feedback on the list regarding version -00).   Please take a look at the draft if you have an opinion on digital signatures, and let Thomas know if you have constructive criticism.   Verification of the test cases, and review of the security considerations, would be especially helpful.

Thanks,

David

<http://tools.ietf.org/html/draft-pornin-deterministic-dsa-01>

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.