[Cfrg] Suggestions for draft-hao-schnorr

Robert Ransom <rransom.8774@gmail.com> Tue, 03 December 2013 23:35 UTC

Return-Path: <rransom.8774@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id AAD301ADFB9 for <cfrg@ietfa.amsl.com>; Tue, 3 Dec 2013 15:35:46 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.028
X-Spam-Status: No, score=-0.028 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, J_CHICKENPOX_17=0.6, SPF_PASS=-0.001, URI_HEX=1.122] autolearn=no
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id rSY3YxnhkPPt for <cfrg@ietfa.amsl.com>; Tue, 3 Dec 2013 15:35:45 -0800 (PST)
Received: from mail-qc0-x22e.google.com (mail-qc0-x22e.google.com [IPv6:2607:f8b0:400d:c01::22e]) by ietfa.amsl.com (Postfix) with ESMTP id 57AA01ADFA9 for <cfrg@irtf.org>; Tue, 3 Dec 2013 15:35:45 -0800 (PST)
Received: by mail-qc0-f174.google.com with SMTP id n7so1420562qcx.19 for <cfrg@irtf.org>; Tue, 03 Dec 2013 15:35:42 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:cc:content-type :content-transfer-encoding; bh=9mhw3b0Xe1aG393scYpn47eTAzDG2axOCqQyLUYlfQo=; b=HzdYl6UGvnlAkroBIdtggIlBBRQ1U/oh3c35N3Hno6BvuV7YNb/x5Zt+wj+W5NsrtM xGH52Qx4PMnZBkAXB7t6g1Rnrh/vIahfSXkEThE3xYgz9yr8h+c9rk67XoVV7/mmNrs2 7BrHvycJZp6ItoBhIu6lr+5TIjltYY5bkTYz2s97DNfPIYimkpo13wUxoQ7In/tnVTVC ZrJBjWVJKuIhlszVedin0DTw/iU4INBdE/X4eAm1uPsQYQj/qWXdLidprd2JolC17jKG 4SEZN0c+707dxDSaFbwgYhkFU5Q/c1rNAMMPpf3luIPO6IbEK+Ka/4NBbEa5IZGUPtPQ lrJg==
MIME-Version: 1.0
X-Received: by with SMTP id b13mr24239845qeg.3.1386113742376; Tue, 03 Dec 2013 15:35:42 -0800 (PST)
Received: by with HTTP; Tue, 3 Dec 2013 15:35:42 -0800 (PST)
Date: Tue, 3 Dec 2013 15:35:42 -0800
Message-ID: <CABqy+srcOK0g-M+MNAVRkAFY688W_Vhg7o=1PzKTGRn5CVU5WA@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Feng Hao <feng.hao@newcastle.ac.uk>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: cfrg@irtf.org
Subject: [Cfrg] Suggestions for draft-hao-schnorr
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: Tue, 03 Dec 2013 23:35:46 -0000

draft-hao-schnorr-00 is incorrectly labeled as describing the ‘Schnorr
signature’.  The protocol it describes is a non-interactive proof of
knowledge of a discrete logarithm, as required by J-PAKE (and other
protocols); the Schnorr signature IS NOT a proof of knowledge.

In the notation used in the draft, the original Schnorr signature (as
described by Wikipedia, ‘Applied Cryptography’, and a PDF file from
somewhere on the Internet claiming to be a 1991 paper by Schnorr) uses
h = H(Message || g^v).  With that choice of h, an attacker can choose
V with unknown discrete logarithm, choose r and Message arbitrarily,
and compute the X for which the signature is valid; the attacker (and
anyone else who sees the signature) will know the discrete logarithm
of X with respect to V, but not with respect to g.

I suggest replacing “Schnorr signature” with “Schnorr proof of
knowledge” in the titles of Section 4 and the draft itself, and adding
text in the draft warning about the difference between the PoK and the
original signature scheme, to try to reduce the risk that someone will
break a protocol by substituting the original (non-PoK) Schnorr
signature for the PoK you are describing.

(I don't believe that using the original Schnorr signature in J-PAKE
would break J-PAKE's security, but it's certainly not a good thing to

The draft must specify that implementations MUST choose v *uniformly*
at random from Z/qZ, and MUST NOT use the same v for more than one
signature.  (See section 2, subsection ‘Pseudorandom generation of r’
(on pages 8 and 9) of <http://ed25519.cr.yp.to/ed25519-20110926.pdf>
for reasons and references.)  The draft should specify that
implementations which use long-term signing keys SHOULD arrange to
generate v in a secretly deterministic manner, and protocols in which
long-term signing keys may need to be interoperable between
implementations MUST specify the details of deterministic generation
of v and storage and transport of any extra key material required for
that purpose.

Robert Ransom