Re: [TLS] [Cfrg] FW: Schnorr Signatures

Johannes Merkle <johannes.merkle@secunet.com> Mon, 07 July 2014 14:53 UTC

Return-Path: <Johannes.Merkle@secunet.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D150C1A01E1 for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 07:53:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.251
X-Spam-Level:
X-Spam-Status: No, score=-3.251 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.651] 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 Z4k4C1UgChT9 for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 07:53:28 -0700 (PDT)
Received: from a.mx.secunet.com (a.mx.secunet.com [195.81.216.161]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3D55B1A01F1 for <tls@ietf.org>; Mon, 7 Jul 2014 07:53:28 -0700 (PDT)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id C597B1A0099 for <tls@ietf.org>; Mon, 7 Jul 2014 16:53:24 +0200 (CEST)
X-Virus-Scanned: by secunet
Received: from a.mx.secunet.com ([127.0.0.1]) by localhost (a.mx.secunet.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 6ZPtFdTfJeyC for <tls@ietf.org>; Mon, 7 Jul 2014 16:53:16 +0200 (CEST)
Received: from mail-gw-int (unknown [10.53.40.207]) by a.mx.secunet.com (Postfix) with ESMTP id 43E751A0096 for <tls@ietf.org>; Mon, 7 Jul 2014 16:53:16 +0200 (CEST)
Received: from [10.53.40.204] (port=60893 helo=mail-essen-01.secunet.de) by mail-gw-int with esmtp (Exim 4.80 #2 (Debian)) id 1X4AI9-0005h3-Eo for <tls@ietf.org>; Mon, 07 Jul 2014 16:53:17 +0200
Received: from [10.208.1.76] (10.208.1.76) by mail-essen-01.secunet.de (10.53.40.204) with Microsoft SMTP Server (TLS) id 14.3.195.1; Mon, 7 Jul 2014 16:53:17 +0200
Message-ID: <53BAB45C.7040603@secunet.com>
Date: Mon, 7 Jul 2014 16:53:16 +0200
From: Johannes Merkle <johannes.merkle@secunet.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: <tls@ietf.org>
References: <53AC88F2.7020405@cs.bris.ac.uk>
In-Reply-To: <53AC88F2.7020405@cs.bris.ac.uk>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 8bit
X-Originating-IP: [10.208.1.76]
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/RKkDDzly-BEy-zcZExsAmqFFBPo
Subject: Re: [TLS] [Cfrg] FW: Schnorr Signatures
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.15
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: Mon, 07 Jul 2014 14:53:32 -0000

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.


[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