Re: [Cfrg] What constitutes a curve with a 256-bit security level?

[Mike Hamburg <[e-mail]>]

On 02/18/2015 10:57 PM, David Jacobson wrote:
> On 2/18/15 2:45 PM, Watson Ladd wrote:
>>
>>
>> On Feb 18, 2015 2:39 PM, "Tony Arcieri" <[e-mail] 
>> <mailto:[e-mail]>> wrote:
>> >
>> > On Wed, Feb 18, 2015 at 2:14 PM, Michael Hamburg 
>> <[e-mail] <mailto:[e-mail]>> wrote:
>> >>
>> >> It may be that you’re thinking SHA512-and-truncate won’t be 
>> uniform enough mod the order of Ridinghood.  But in fact it will, 
>> because the order of Ridinghood is 2^480 - O(2^240), and so the 
>> deviation from uniformity will be O(2^-(240+32)).  The same would not 
>> be true for a prime with a large coefficient like NIST P-256.
>> >
>> >
>> > Okay, my mistake, but that is an issue for E-521, right?
>>
>> Not really. While the naïve approach if using a single hash function 
>> output of double length for deterministic signing won't work, hashing 
>> an incrementing counter with the message and private key, or some 
>> other variant will.
>>
>> Sincerely,
>> Watson Ladd
>>
> [snip]
>
> Clarifying question:
>
> Do you mean to be advocating using a KDF like the counter one in NIST 
> SP 800-108, and specifying an output bit length of the ceiling of log2 
> of the order of the base point?

This.  The only trouble is that 519 > 512.

> Or do you mean using a construct similar to that, but if the results 
> is >= the curve order, try again with the next counter values, until 
> you get a value < the order of the base points. In this construct all 
> possible values < the order of the base point are equally likely.
>
>     --David Jacobson
>
No, because the order of the curve is p +- O(sqrt(p)), and the subgroup 
order is exactly 1/4 that, so with p = 2^521-1 the bias is provably 
negligible.

Cheers,
-- Mike