[TLS] (EC)DSA potential problems (ECC "brittleness")

Peter Gutmann <pgut001@cs.auckland.ac.nz> Fri, 11 October 2013 12:17 UTC

Return-Path: <pgut001@cs.auckland.ac.nz>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BC33321F9CED for <tls@ietfa.amsl.com>; Fri, 11 Oct 2013 05:17:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Wug5OfZEMevX for <tls@ietfa.amsl.com>; Fri, 11 Oct 2013 05:17:37 -0700 (PDT)
Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) by ietfa.amsl.com (Postfix) with ESMTP id C86CF21F9C34 for <tls@ietf.org>; Fri, 11 Oct 2013 05:17:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1381493857; x=1413029857; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=H/djW1TrZaIaIsg9phiBjSyKo942By89oGfl+Rj4Avk=; b=HWVJx5ro1b4EnTYxpjSRY9FyuH85RIt0yr1u5JoEmQjOah6BTAHH0Bwf Pjgu0wlvheFYwxlZL97AnsXEEdxbMkTTw5D5T2+tz3j4wScu+HFSxbYgz X7m8zZrYo36E2x6HYAKzoT3AeKE7gqsDueG4tnzbWgoqyaNPlvHI5yl91 w=;
X-IronPort-AV: E=Sophos;i="4.90,1080,1371038400"; d="scan'208";a="217084577"
X-Ironport-HAT: MAIL-SERVERS - $RELAYED
X-Ironport-Source: 130.216.4.106 - Outgoing - Outgoing
Received: from uxchange10-fe2.uoa.auckland.ac.nz ([130.216.4.106]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 12 Oct 2013 01:17:29 +1300
Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.179]) by uxchange10-fe2.UoA.auckland.ac.nz ([130.216.4.106]) with mapi id 14.03.0158.001; Sat, 12 Oct 2013 01:17:29 +1300
From: Peter Gutmann <pgut001@cs.auckland.ac.nz>
To: "tls@ietf.org" <tls@ietf.org>
Thread-Topic: [TLS] (EC)DSA potential problems (ECC "brittleness")
Thread-Index: Ac7Ge9pHV4fQ9eWiT1ir7fSQHYZRwQ==
Date: Fri, 11 Oct 2013 12:17:28 +0000
Message-ID: <9A043F3CF02CD34C8E74AC1594475C735568A5EC@uxcn10-6.UoA.auckland.ac.nz>
Accept-Language: en-NZ, en-GB, en-US
Content-Language: en-NZ
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [130.216.158.4]
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
Subject: [TLS] (EC)DSA potential problems (ECC "brittleness")
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Fri, 11 Oct 2013 12:17:41 -0000

Martin Rex <mrex@sap.com> writes:

>Which "recommended (until not too long ago) way to generate your k for (EC)
>DSA" are you referring to specifically?

See Adam Back's conveniently-timed post to the Ramdombit crypto list:

-- Snip --

Some may remember Bleichenbacher found a random number generator bias in the
original DSA spec, that could leak the key after soem number of signatures
depending the circumstances.

Its described in this summary of DSA issues by Vaudenay "Evaluation Report
on DSA"

http://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1002_reportDSA.pdf

Bleichenbacher's attack is described in section 5.

The conclusion is "Bleichenbacher estimates that the attack would be
practical for a non-negligible fraction of qs with a time complexity of
2^63, a space complexity of 2^40, and a collection of 2^22 signatures.  We
believe the attack can still be made more efficient."

NIST reacted by issuing special publication SP 800-xx to address and I
presume that was folded into fips 186-3.  Of course NIST is down due to the
USG political level stupidity (why take the extra work to switch off the web
server on the way out I dont know).

That means 186-1 and 186-2 were vulnerable.

An even older NSA sabotage spotted by Bleichenbacher?

Anyway it highlights the significant design fragility in DSA/ECDSA not just
in the entropy of the secret key, but in the generation of each and every k
value, which leads to the better (but non-NIST recommended) idea adopted by
various libraries and applied crypto people to use k=H(m,d) so that the
signture is determinstic in fact, and the same k value will only be used
with the same message (which is harmless as thts just reissuing the bitwise
same signature).

-- Snip --

(my ref. for this was "The Insecurity of the Digital Signature Algorithm with
Partially Known Nonces" by Phong Nguyen and Igor Shparlinski, but Vaudenay's
work is a better ref).

>Is or was this part of FIPS 186-x for DSA--or some X9.xx document for ECDSA
>that do not have (not having coughed up the $$), and is that specific issue
>sufficient to enable the attack described in this paper:
>
>  Jean-Charles Faugere, Christopher Goyet and Guenael Renault
>  "Attacking (EC)DSA Given Only an Implicit Hint"
>
>  http://www-polsys.lip6.fr/~goyetc/doc/ImplicitECDSA_Goyet.pdf

No, that's yet another one.

(I did mention that DLP-based PKCs were quite brittle, didn't I? :-).

>Btw. where would one find the information necessary to implement (EC)DSA safe
>with respect to the state-of-the-art?

I don't think there is one, you need to either be aware of a whole pile of
research papers (some of which are only drafts, or tech reports, which means
reading a pile of crypto lists), or to read code comments in a well-maintained
crypto library that mentions the workarounds to various problems.

(Again, my brittleness comment, with RSA you use blinding/const-time modexp
and do a consistency check on your signatures to check for faults and you're
done, with the DLP's its a continuous arms race).

Peter.