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

Johannes Merkle <johannes.merkle@secunet.com> Mon, 07 July 2014 16:10 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 E83871A0342 for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 09:10:26 -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 IxJqFSIOpCNp for <tls@ietfa.amsl.com>; Mon, 7 Jul 2014 09:10:23 -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 A44351A02F1 for <tls@ietf.org>; Mon, 7 Jul 2014 09:10:18 -0700 (PDT)
Received: from localhost (alg1 [127.0.0.1]) by a.mx.secunet.com (Postfix) with ESMTP id D069E1A0097; Mon, 7 Jul 2014 18:10:15 +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 8nCvd4WxGqnv; Mon, 7 Jul 2014 18:10:10 +0200 (CEST)
Received: from mail-gw-int (unknown [10.53.40.207]) by a.mx.secunet.com (Postfix) with ESMTP id C0B3E1A0066; Mon, 7 Jul 2014 18:10:10 +0200 (CEST)
Received: from [10.53.40.204] (port=15219 helo=mail-essen-01.secunet.de) by mail-gw-int with esmtp (Exim 4.80 #2 (Debian)) id 1X4BUa-0007o3-1y; Mon, 07 Jul 2014 18:10:12 +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 18:10:11 +0200
Message-ID: <53BAC663.2090401@secunet.com>
Date: Mon, 7 Jul 2014 18:10:11 +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: Watson Ladd <watsonbladd@gmail.com>, <tls@ietf.org>
References: <53AC88F2.7020405@cs.bris.ac.uk> <53BAB45C.7040603@secunet.com> <CACsn0ckNFh_sH0WOpTSE6byq9_-2JqApWYREjzkfsyGCDMGThQ@mail.gmail.com>
In-Reply-To: <CACsn0ckNFh_sH0WOpTSE6byq9_-2JqApWYREjzkfsyGCDMGThQ@mail.gmail.com>
X-Enigmail-Version: 1.6
Content-Type: text/plain; charset="windows-1252"
Content-Transfer-Encoding: 7bit
X-Originating-IP: [10.208.1.76]
Archived-At: http://mailarchive.ietf.org/arch/msg/tls/H2KLZrXO5F4DqcQtS-2VqNj3xrE
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 16:10:27 -0000

Watson Ladd wrote on 07.07.2014 17:01:
> 
> On Jul 7, 2014 7:53 AM, "Johannes Merkle" <johannes.merkle@secunet.com <mailto: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.

I didn't mean to imply that loosing the security proof makes the scheme insecure. But we have the choice (for 128 bit
security level):
1. Use the provably secure version with signature length of 64 byte
2. Use an optimized version without security proof giving signature length of 48 byte.

> 
> 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.

Hmmm, by Hasse's theorem and for moderate co-factors, the size of the group roughly equals the size of the group
elements. Thus, this variant has about the same signature length as the original version (64 byte for 128 bit security).
Or do I miss something?

-- 
Johannes