Re: [Cfrg] Elliptic Curves - curve form and coordinate systems

[Rene Struik <[e-mail]>]

Hi Dan:

It seems you confuse the sender and recipient side here: on the sender's side, the incremental cost of computing an affine point representation from an x-coordinate-only one is quite insignificant, whereas, indeed, on the recipient's side, this incremental cost is quite high. Hence, the entire discussion.

Rene


[excerpt of email Dan Bernstein as of Sun March 15, 2015, 8.22pm EDT]

Meanwhile you're forcing the ECDH key generator to
compute v in the first place---a significant increase in the complexity
of the simplest (Montgomery ladder) keygen software.


On 3/15/2015 8:22 PM, D. J. Bernstein wrote:
> One of the OpenSSL security fixes this year was correcting a bug in
> point validation. The bug is estimated to allow more than 2^192 bogus
> (x,y) pairs for NIST P-256, and presumably a few of those have order
> below 2^66. Finding these medium-order points is an open problem for the
> moment, but anyone who _can_ find them can use an active invalid-point
> attack to break Microsoft's two-hour ECDH keys with <2^70 computations,
> and thus to decrypt all other connections made during that two-hour
> period. (The computations don't have to finish within the two hours.
> Maybe this work can even be shared across multiple ECDH keys; I'd have
> to look at other protocol details to figure this out.)
>
> How many years did it take for this bug to be found in a very widely
> used cryptographic library? Who's reviewing all the other NIST P-256
> implementations to see whether they even _try_ to validate points, never
> mind whether they get it right?
>
> With the Montgomery ladder, the curve is reused in every step, and a bug
> that corrupts computations will simply move to different points on the
> same curve or its twist. Next-generation curves such as Curve25519
> guarantee that _none_ of those points have dangerous orders. The fault
> attack in
>
>     https://www.di.ens.fr/~fouque/pub/fdtc08.pdf
>
> worked only because it targeted old-fashioned curves that weren't
> twist-secure, such as NIST P-224. With proper choices (twist-secure
> curve, and scalar bits set accordingly) Montgomery-ladder ECDH doesn't
> need _any_ input validation.
>
> In particular, input 0 is handled correctly without any special tests,
> contrary to Rene's comments and earlier comments from Microsoft. See
> https://www.ietf.org/mail-archive/web/cfrg/current/msg05004.html.
>
> Here's another interesting data point regarding code simplicity. In
> flipping through Microsoft's "constant-time" ECCLib_v1.1, I noticed
>
>     temp = (scalar[0] & val1) - val2; // ki = (k mod 2^w)/2^(w-1)
>     *digits = (int)temp;
>     digits++;
>     res = scalar[0] - temp;           // k = (k-ki)/2^(w-1)
>     borrow = (temp > 0) & (scalar[0] < (unsigned int)temp);
>
> inside the fixed_window_recode() function. The scalar is, apparently,
> supplied by an attacker, and I would expect the compiler in most cases
> to turn the comparisons into variable-time branches, leaking scalar bits
> through timing---clearly violating the "constant-time" promise. With the
> Montgomery ladder, the scalar bits are used in a much simpler way,
> minimizing the number of opportunities to screw up the implementation.
>
> Andrey Jivsov writes:
>> A sample of the interest in unified format can be found here:
> You misunderstand. There are two different types of ECDH keygen code
> available for X25519:
>
>     * _simple_ key generators that use the Montgomery ladder;
>     * _fast_ key generators that use precomputed Edwards points and
>       convert the output to Montgomery format.
>
> Both of these approaches produce identical Montgomery x-coordinates on
> the wire. The fact that the fast implementations use Edwards internally
> doesn't mean that all implementations want to do this (for most people
> simplicity is more important than this extra burst of keygen speed) and
> certainly doesn't mean that it's a good idea to use anything other than
> Montgomery x on the wire for ECDH.
>
>    [ send an extra coordinate v along with the Montgomery x ]
>> An implementation that uses a Montgomery ladder simply ignores v
> Well, yes, this is what any sensible ECDH receiver will do, so why waste
> the network traffic? Meanwhile you're forcing the ECDH key generator to
> compute v in the first place---a significant increase in the complexity
> of the simplest (Montgomery ladder) keygen software.
>
>> implement both signatures and ECDH
> Switching from a "unified" format to Montgomery x for ECDH usually makes
> this type of software _simpler_. The underlying issue is that there are
> actually three different scalar-multiplication operations of interest:
>
>     * double-scalar multiplication (signature verification);
>     * fixed-base-point single-scalar multiplication (signing/keygen); and
>     * variable-base-point single-scalar multiplication (ECDH).
>
> For example, in Microsoft's library these are ECC_DBLMUL_TE,
> ECC_MUL_FIXED_TE, and ECC_MUL_TE. Ripping all the ECDH-specific
> functions out of the library (ECC_MUL_TE, fixed_window_recode, etc.),
> and replacing them with a Montgomery ladder, would _simplify_ the code.
>
> Furthermore, even if you can find a signature+ECDH library where a
> "unified" format _reduces_ complexity rather than _increasing_ it, the
> percentage saved will obviously be quite small---whereas sticking to
> Montgomery x for ECDH saves a _much_ larger percentage of a pure ECDH
> implementation.
>
>> a single set of test vectors, code reuse, and the benefits of sharing
>> pre-computed values
> Every function needs its own test vectors in any case. Pre-computed
> values are shared in any case. As for code reuse, see above.
>
>> no (measurable) performance penalty
> The extra network traffic is a measurable performance penalty, and is
> more important than the CPU time saved for decompression inside
> signature verification. See below.
>
> Michael Hamburg writes:
>    [ compression ]
>> saves time and energy on radio links
> Yes, obviously.
>
>> but costs time and energy on wired ones
> No.
>
> Time: Curve25519 decompression takes roughly 5 microseconds on a typical
> server CPU core, but this is less than the time that the core needs to
> receive 256 bits from the Internet---unless you've bought a single
> quad-core server to handle more than 200Mbps of Internet traffic; this
> doesn't make economic sense.
>
> Energy: 10 USD of electricity will pay for about 10 watt-years of this
> 125-watt quad-core CPU, i.e., a month of CPU time, i.e., 2000000000000
> decompressions, saving 64 terabytes of Internet traffic---a month of
> continuous traffic at 200Mbps, as above. Some ISPs do sell noticeable
> fractions of 200Mbps for 10 USD/month, but that's because they know that
> most users won't use the network anywhere near continuously.
>
>> or when the point is cached
> No. You pay _once_ to decompress a point the first time you use it, and
> after that you cache the decompressed version. (I'm assuming that it's
> cheaper for you to store the extra bytes than to recompute them; if not,
> you should cache the compressed version.) Local caching doesn't affect
> the performance impact of compression on the wire.
>
> ---Dan
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg


-- 
email: [e-mail] | Skype: rstruik
cell: [phone] | US: [phone]