Re: [Cfrg] FW: Schnorr Signatures

Dan Brown <dbrown@certicom.com> Mon, 07 July 2014 17:00 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 87A7B1A03FC for <cfrg@ietfa.amsl.com>; Mon, 7 Jul 2014 10:00:20 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id ETlFQXkjK0ij for <cfrg@ietfa.amsl.com>; Mon, 7 Jul 2014 10:00:18 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 0E2641A0370 for <cfrg@irtf.org>; Mon, 7 Jul 2014 10:00:17 -0700 (PDT)
Received: from xct101cnc.rim.net ([10.65.161.201]) by mhs215cnc.rim.net with ESMTP/TLS/AES128-SHA; 07 Jul 2014 13:00:17 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT101CNC.rim.net ([fe80::9c22:d9c:c906:c488%16]) with mapi id 14.03.0174.001; Mon, 7 Jul 2014 13:00:16 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'watsonbladd@gmail.com'" <watsonbladd@gmail.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [Cfrg] FW: Schnorr Signatures
Thread-Index: Ac+aBBiYLqfqpxUASzGqBqdqcZD3Tw==
Date: Mon, 07 Jul 2014 17:00:15 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5CB578F@XMB116CNC.rim.net>
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.250]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg="SHA1"; boundary="----=_NextPart_000_000E_01CF99E3.65365840"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/cvKEqIX1uTPGNNXyK0f9YHXEyrk
Subject: Re: [Cfrg] FW: Schnorr Signatures
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: Mon, 07 Jul 2014 17:00:20 -0000

For half-length hashes, and thus 3b-bit Schnorr signatures (that consist of hash plus a group element), I’ve devised a hash that seems to show that the loose bound implicit in the Neven--Smart—Warinschi Theorem 2 cannot be improved without new hash assumptions.  In other words, the looseness of the results is not merely an artefact of the proof.

 

So, for b=128, the 128-bit hash seems to be 128-bit RPP-secure (and speculatively RPSP secure), yet when use with 192-bit Schnorr signature gives only 64-bit security.  

 

I’m drafting a report about this … but have confirmed it with authors.

 

Just to be clear, it is a contrived hash.  It does not rule out new provable security results with a tighter bound, but does prove that such a new result would require further assumptions about the hash function, not just RPP and RPSP security.

 

Here’s the contrived hash function: H(R||m) = H1(R) + H2(m) where H1 and H2 are secure 128-bit hashes.  Specifically, H1 needs a smoothness property (thanks to Neven for this property, I had used random oracle), and H2 needs a pre-image resistance property, to achieve the RPP property in the NSW paper.  

 

Note that this contrived H is not OW (it only has 64-bit security), so perhaps a new provable security result for short Schnorr adding the condition of the short hash being one-way, in addition to RPP and RPSP secure might still be possible.

 

From: TLS [mailto:tls-bounces@ietf.org] On Behalf Of Watson Ladd
Sent: Monday, July 07, 2014 11:01 AM
To: tls@ietf.org
Subject: Re: [TLS] [Cfrg] FW: Schnorr Signatures

 


On Jul 7, 2014 7:53 AM, "Johannes Merkle" <johannes.merkle@secunet.com> wrote:
>
> Nigel Smart wrote on 26.06.2014 22:56:
> > With Schnorr you dont send the x-coord of R. What you send is
> > half the hash value e
> >     e=Hash(R||Message)
> > So if using SHA-256 you send 128 bits of e over.
>
> Actually, the Schnorr signature is defined as using the full hash value, but it has been repeatedly proposed (originally
> by Schnorr himself) to use a half-length hash function (and that could be truncated SHA-256).
>
> However, as you pointed out in [1], the security proofs you mentioned do not work with reduced hash length h=b AND
> standard group order g = 2^(2b) for security level b. Your proof in the generic model [1] requires h=2*b and the proof
> of Pointcheval and Stern in the Random oracle model [2] needs g=2^(3b). Thus, when using half-length hash values you
> sacrifice provable security.

While the Pointcheval and Stern result is not tight, no one has made attacks that do better.

The most compact and performant variant sends R and S. R is the size of a group element, S the size of order of the group. This way the length of what is to be transmitted does not depend on the hash used.
>
>
> [1] Gregory Neven, Nigel P. Smart, and Bogdan Warinschi. Hash function requirements for schnorr
> signatures. J. Mathematical Cryptology, 3(1):69–87, 2009
>
> [2] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures.
> Journal of Cryptology, 13(3):361–396, March 2000.
>
>
> --
> Johannes
>
> _______________________________________________
> TLS mailing list
> TLS@ietf.org
> https://www.ietf.org/mailman/listinfo/tls