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

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