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

From: Tony Arcieri <[email-masked]>
Date: Wed, 18 Feb 2015 10:28:20 -0800

Well, the votes are in, and I guess people want a 256-bit security level.

But what is actually meant by this? It's arguable that e.g. 2^448-2^224-1
(sorry to beat a dead horse) is at least as strong as e.g. AES-256. Should
we discount it because it's otherwise considered to be 32-bits short of a
256-bit security level?

It seems the tendency is to reach for a curve like E-521 which exceeds a
256-bit security level, but I think curves that are a "bit too big" are
more problematic than ones that are a "bit too small".

-- 
Tony Arcieri

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 18 Feb 2015 11:21:19 -0800

I believe the chairs have explicitly stated that Ed448-Goldilocks will not be eligible, because it is almost exactly between WF192 and WF256, and because they feel that curves must be voted off the island in order to make progress.  Though I am curious — is the same also true of Ed480-Ridinghood?

Cheers,
— Mike

> On Feb 18, 2015, at 10:28 AM, Tony Arcieri <[email-masked]> wrote:
> 
> But what is actually meant by this? It's arguable that e.g. 2^448-2^224-1 (sorry to beat a dead horse) is at least as strong as e.g. AES-256. Should we discount it because it's otherwise considered to be 32-bits short of a 256-bit security level?
> 
> It seems the tendency is to reach for a curve like E-521 which exceeds a 256-bit security level, but I think curves that are a "bit too big" are more problematic than ones that are a "bit too small".
> 
> -- 
> Tony Arcieri
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 18 Feb 2015 11:55:58 -0800

On Wed, Feb 18, 2015 at 11:21 AM, Michael Hamburg <[email-masked]>
wrote:

> I believe the chairs have explicitly stated that Ed448-Goldilocks will not
> be eligible, because it is almost exactly between WF192 and WF256, and
> because they feel that curves must be voted off the island in order to make
> progress.  Though I am curious — is the same also true of Ed480-Ridinghood?
>

Correct me if I'm wrong, but aren't there issues around signatures for
Ridinghood that aren't problematic for Goldilocks?

Also note: Having good answers to questions like this is a reason why I
feel that signatures should take priority over a higher security curve.

-- 
Tony Arcieri

---

From: Michael Hamburg <[email-masked]>
Date: Wed, 18 Feb 2015 14:14:31 -0800

> On Feb 18, 2015, at 11:55 AM, Tony Arcieri <[email-masked]> wrote:
> 
> On Wed, Feb 18, 2015 at 11:21 AM, Michael Hamburg <[email-masked] <mailto:[email-masked]>> wrote:
> Correct me if I'm wrong, but aren't there issues around signatures for Ridinghood that aren't problematic for Goldilocks?

… no?

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.

> Also note: Having good answers to questions like this is a reason why I feel that signatures should take priority over a higher security curve.
> 
> -- 
> Tony Arcieri

Agreed.

Cheers,
— Mike

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 18 Feb 2015 14:38:45 -0800

On Wed, Feb 18, 2015 at 2:14 PM, Michael Hamburg <[email-masked]> 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?

-- 
Tony Arcieri

---

From: Watson Ladd <[email-masked]>
Date: Wed, 18 Feb 2015 14:45:42 -0800

On Feb 18, 2015 2:39 PM, "Tony Arcieri" <[email-masked]> 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

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 18 Feb 2015 14:47:43 -0800

On Wed, Feb 18, 2015 at 2:45 PM, Watson Ladd <[email-masked]> wrote:

> 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
Okay, seems I was confused. Thanks for clearing that up. That said...

On Wed, Feb 18, 2015 at 11:21 AM, Michael Hamburg <[email-masked]>
 wrote:

> ...curves must be voted off the island in order to make progress.  Though
> I am curious — is the same also true of Ed480-Ridinghood?
>

+1 on curiosity about whether Ridinghood is still a candidate if Goldilocks
is out.

-- 
Tony Arcieri

---

From: David Jacobson <[email-masked]>
Date: Wed, 18 Feb 2015 22:57:37 -0800

On 2/18/15 2:45 PM, Watson Ladd wrote:
>
>
> On Feb 18, 2015 2:39 PM, "Tony Arcieri" <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >
> > On Wed, Feb 18, 2015 at 2:14 PM, Michael Hamburg <[email-masked] 
> <mailto:[email-masked]>> wrote:
> >>
> 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.
> >
> >
> 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?

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

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 18 Feb 2015 23:53:27 -0800

On 02/18/2015 10:57 PM, David Jacobson wrote:
>> > On Wed, Feb 18, 2015 at 2:14 PM, Michael Hamburg 
>> <[email-masked] <mailto:[email-masked]>> 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.
>> >
>> >
> 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 
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