[Cryptography] IETF discussion on new ECC curves.

[Phillip Hallam-Baker]

On Sat, Aug 2, 2014 at 7:25 AM, Jerry Leichter <leichter at lrw.com> wrote:
> On Aug 1, 2014, at 5:26 PM, Phillip Hallam-Baker <phill at hallambaker.com> wrote:
>> E-480 is not just slightly less secure than E-512, the work factor is
>> reduced by 2^16, that's 65,536 times less security than we asked for.
>> And the so-called 'Goldilocks curve' is twice as fast but the E-512 is
>> 4 billion times harder to break....
> I haven't dug into all the technical issues here, but I can't buy these assertions.  A change in work factor of 2^16 when you change the number of bits in the key by 16 makes sense only for searches equivalent to brute force.
>
> All of these numbers are way beyond any possible brute force search.  (No, not just based on existing technologies, but based on any technology consistent with what we know about physics.)  Answering that, sure, brute force isn't relevant, but that for *any* attack, more bits is always harder, ignores the important question of *how much* harder.  Your assertions assume exponential scaling in the number of bits.  That means attacks equivalent to brute force - so just as impractical as brute force at these sizes, regardless of the details.


Once you decide on a safety margin you should meet it. I want a safety
margin that is good enough to maintain WF128 even if someone works out
the ECC equivalent of meet-in-the-middle.


The point I am making here is that when we are talking about making
compromises between speed and security we need to look at the actual
work factor, not its logarithm.

Going down from WF256 to WF240 is not a small change and going to
WF224 is a huge change.


Going from WF256 to WF254 is well within the margin of error measuring
performance and the argument might be stretched to WF250. But any
further and you are eating into the safety margin.

There are only two poles that are helpful here 'high security with
performance' and 'beyond any rational doubt'. Any ECC scheme that is
lower than WF250 is definitely going to create reasonable doubt.

Data paths come in binary exponent widths, there are machines with 32,
64, 128 and 512 bit data buses in common use. Choosing the strongest
work factor that does not exceed a data bus size is a really good way
to get rigidity.


The task here is to make a decision. Binary exclusionary criteria are
more useful than grey scale.