Re: [Cfrg] Comments Requested on Deterministic DSA and ECDS draft

Jon Callas <jon@callas.org> Wed, 13 April 2011 20:12 UTC

Return-Path: <jon@callas.org>
X-Original-To: cfrg@ietfc.amsl.com
Delivered-To: cfrg@ietfc.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfc.amsl.com (Postfix) with ESMTP id C4977E07CB for <cfrg@ietfc.amsl.com>; Wed, 13 Apr 2011 13:12:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.495
X-Spam-Level:
X-Spam-Status: No, score=-0.495 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FH_RELAY_NODNS=1.451, HELO_MISMATCH_COM=0.553, RDNS_NONE=0.1]
Received: from mail.ietf.org ([208.66.40.236]) by localhost (ietfc.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 4u-rzIRbOsEe for <cfrg@ietfc.amsl.com>; Wed, 13 Apr 2011 13:12:06 -0700 (PDT)
Received: from merrymeet.com (unknown [173.164.244.100]) by ietfc.amsl.com (Postfix) with ESMTP id 1AC3BE06BC for <cfrg@irtf.org>; Wed, 13 Apr 2011 13:12:04 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by merrymeet.com (Postfix) with ESMTP id C2FC92E10E for <cfrg@irtf.org>; Wed, 13 Apr 2011 13:12:20 -0700 (PDT)
Received: from merrymeet.com ([127.0.0.1]) by localhost (host.domain.tld [127.0.0.1]) (amavisd-maia, port 10024) with ESMTP id 12524-02 for <cfrg@irtf.org>; Wed, 13 Apr 2011 13:12:18 -0700 (PDT)
Received: from keys.merrymeet.com (keys.merrymeet.com [173.164.244.97]) (Authenticated sender: jon) by merrymeet.com (Postfix) with ESMTPA id 9AB9C2E108 for <cfrg@irtf.org>; Wed, 13 Apr 2011 13:12:18 -0700 (PDT)
Received: from [17.193.15.61] ([17.193.15.61]) by keys.merrymeet.com (PGP Universal service); Wed, 13 Apr 2011 13:12:01 -0700
X-PGP-Universal: processed; by keys.merrymeet.com on Wed, 13 Apr 2011 13:12:01 -0700
Mime-Version: 1.0 (Apple Message framework v1084)
From: Jon Callas <jon@callas.org>
In-Reply-To: <009a01cbf993$fbb34650$f319d2f0$@augustcellars.com>
Date: Wed, 13 Apr 2011 13:11:59 -0700
Message-Id: <2F0EC11A-4C8A-4A84-A85B-342361C87A1F@callas.org>
References: <009a01cbf993$fbb34650$f319d2f0$@augustcellars.com>
To: Jim Schaad <ietf@augustcellars.com>
X-Mailer: Apple Mail (2.1084)
X-PGP-Encoding-Format: Partitioned
X-PGP-Encoding-Version: 2.0.2
X-Content-PGP-Universal-Saved-Content-Transfer-Encoding: quoted-printable
X-Content-PGP-Universal-Saved-Content-Type: text/plain; charset=us-ascii
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: QUOTED-PRINTABLE
X-Virus-Scanned: Maia Mailguard
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Comments Requested on Deterministic DSA and ECDS draft
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: Wed, 13 Apr 2011 20:12:06 -0000

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Jim,

I'm basically supportive of this. In PGP 5.0, we did something analogous to this -- we hashed together the private key, the hash of the message, and I think a couple other things like a time stamp (as a form of sequence number). We were very concerned about the quirk of DSA that losing the random number loses the private key. Certainly, we've seen that as a break of DSA in a couple places since.

There is a lot of discussion of this in the code comments on rationale etc., but the idea was that even if your random number generator was broken in ways that you didn't understand, your private key would still be safe. We noted that strictly speaking, a completely broken random number generator wouldn't spill the keys, which is pretty much the same point that this draft has.

We've encouraged people to use this basic technique. Obviously, today you'd use an HMAC instead of a hash (we did this in the days when dinosaurs roamed the earth and there were no HMACs), etc. Also, back in those days, hardly anyone used DSA. But with DSA coming back through ECDSA, a safety net using steps like these.

This would have saved Sony, and there are others for whom this is a good safety net on the crypto.

However, I raise an eyebrow at turning the virtue of a safety net into a necessity. Despite having been proud of this safety net being so good that it protects against a broken RNG, I wouldn't recommend determinism to *anyone*. It seems to me that it's skating on very thin ice to go completely deterministic.

These techniques make basic DSA better, because if there is weakness in the RNG, you're protected to the degree to which your mixing function resembles a random oracle. It's a huge leap of faith then pin all your security on that. I fear that the basic very good idea might be lost by this final leap of faith.

	Jon


-----BEGIN PGP SIGNATURE-----
Version: PGP Universal 2.10.0 (Build 554)
Charset: us-ascii

wj8DBQFNpgORsTedWZOD3gYRAp97AJ0QOEIAL1/C7Vr5DIxMf429YoIrRgCfe8Ux
kasJ5CJFRUU/BefHigM0IOA=
=r+y5
-----END PGP SIGNATURE-----