Re: [Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)

Watson Ladd <watsonbladd@gmail.com> Sun, 12 January 2014 22:39 UTC

Return-Path: <watsonbladd@gmail.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 3FB0A1A1F3F for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 14:39:56 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-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 Yb92XgOUKVKz for <cfrg@ietfa.amsl.com>; Sun, 12 Jan 2014 14:39:54 -0800 (PST)
Received: from mail-wi0-x236.google.com (mail-wi0-x236.google.com [IPv6:2a00:1450:400c:c05::236]) by ietfa.amsl.com (Postfix) with ESMTP id 478801A1F33 for <cfrg@irtf.org>; Sun, 12 Jan 2014 14:39:54 -0800 (PST)
Received: by mail-wi0-f182.google.com with SMTP id en1so1514678wid.15 for <cfrg@irtf.org>; Sun, 12 Jan 2014 14:39:43 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=ol6m7y36dS06pSmRrjclIneqvM4xwJFIoaAXYFBrS2s=; b=nLp6//HHWEsY8hwzd2DDrNQytf8BZwP99ML4bls0EBn3S0J5up8OehhbEBhoyo6Bc/ roH7Gqa0iBWOnA7JOKJfDSMBEp1gQLjlMj+nCpKHSJ3mWUXt69fbdZZVh9/US/AFwhK3 AOz10IVUqLxt00USIogCSaSUyqiPHlB78WgclDr3kco7zQbrkdkVmDYStjmMsPIYmRrk 2Xbfs7GVRmlhl017z0YrLYXrpeIw5dwxkCLAKSaiacK7j7wx1zql/5B4xl8cowJlJaUX gBLKFkejumIZ//ltqD7yJw2PDy+dTJFgNz2S0zWyaDSWBx5TRPpgutDhD89iIyTpkNyd heIg==
MIME-Version: 1.0
X-Received: by 10.194.178.135 with SMTP id cy7mr19045927wjc.21.1389566382944; Sun, 12 Jan 2014 14:39:42 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Sun, 12 Jan 2014 14:39:42 -0800 (PST)
In-Reply-To: <20140112222944.GB29131@vc.unity.net>
References: <87eh4e7a2y.fsf@latte.josefsson.org> <52D18475.10709@akr.io> <20140112062942.GA32437@LK-Perkele-VII> <52D29153.7000301@akr.io> <20140112142923.GA19922@netbook.cypherspace.org> <CABqy+srUUiFcniM404uPcqDChW3xkcTcAjqTejG=Q_pEQMaTsg@mail.gmail.com> <20140112222944.GB29131@vc.unity.net>
Date: Sun, 12 Jan 2014 14:39:42 -0800
Message-ID: <CACsn0cmYbRBe_pSxdVqvfWGFqwjS_Lh0wrgFNZ_xs=6Baa3OtQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Vadym Fedyukovych <vf@unity.net>
Content-Type: text/plain; charset=UTF-8
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] EdDSA and > 512 curve & hash (Re: [TLS] Additional Elliptic Curves (Curve25519 etc) for TLS ECDH key agreement)
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: Sun, 12 Jan 2014 22:39:56 -0000

On Sun, Jan 12, 2014 at 2:29 PM, Vadym Fedyukovych <vf@unity.net> wrote:
> On Sun, Jan 12, 2014 at 07:13:16AM -0800, Robert Ransom wrote:
>> On 1/12/14, Adam Back <adam@cypherspace.org> wrote:
>>
>> > So actually Bernstein went in the opposite direction, not only using
>> > sub-group size, but double sub-group size hash, basically because he could
>> > without increasing the signature size, and thereby slightly even further
>> > reducing the dependency on hash security and hash properties.  I do not
>> > consider its necessary, just its because he could, slightly more security
>> > almost for free.  But I think an EdDSA variant that used a 512-bit curve
>> > could safely use a 512-bit hash, because even the double width hash is
>> > over-engineering.
>>
>> It can for the hash of the message.
>>
>> > EdDSA also uses the deterministic DSA k trick (computed from m and x the
>> > private key).
>>
>> Deterministic generation of message keys is the primary reason that
>> EdDSA requires a double-length hash function.
>>
>> EdDSA relies on the hash function having double-length output in two ways:
>>
>> * Message key generation relies on the output being noticeably longer
>> than the group order in order to generate *uniform* exponents.
>
> Choosing a message key (an initial random in interactive system)
> from a large interval is a well-known idea for a group of a hidden order.
> For a group of known order, reducing almost anything modulo group order
> would likely result in quite a non-uniform distribution.
> It is non-trivial to see how/whether hash of roughly twice-bitlength of group order
> would be better than hash smaller than group order.

Completely wrong for trivial reasons. Let's say we are picking a
random number up to k by taking one up to n and reducing.
Write n=kq+r, with r the remainder. Then the bias is exactly r/n,
which for n the square of k is at most 1/k, and hence negligible if
k is big enough. This is clearly better than if the hash length is
smaller than the group order, in which case a significant number of
group elements will never be picked.

Sincerely,
Watson Ladd

>
> Hash bitlength is rather non-critical while choosing a challenge,
> that should be just a large enough set.
>
> Vadym Fedyukovych
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg



-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin