Subject: Re: [Cfrg] draft-irtf-cfrg-curves-07

From: Michael Hamburg <[email-masked]>
Date: Thu, 3 Sep 2015 17:58:55 -0700

> On Aug 31, 2015, at 6:10 PM, Adam Langley <[email-masked]> wrote:
> 
> On Mon, Aug 31, 2015 at 4:39 PM, Ronald Harvey <[email-masked]> wrote:
>> In Section 5.1, the second input u-coordinate for each of "X25519" and
>> "X448" are, to my computations, not on the curve. These are the values
>> beginning e5210f1278 and 0fbcc2f993cd56d, respectively.  I believe
>> that this makes 'any valid implementation' unable to compute the
>> answer, as only implementations which use an x-only algorithm could
>> possibly find the expected new u.  If it was intentional, then it
>> should probably be noted that these are limited in scope.
> 
> X25519 and X448, as defined, are functions from (byte[32], byte[32])
> to byte[32] (or byte[56] for X448). As such, they are defined for all
> inputs.
> 
> Although it is the case that one only expects points on a curve to be
> generated and transmitted etc, partial implementations present at
> least a fingerprinting issue. Since all the field functions can be
> shared, and the Montgomery ladder is small, I think the assumption is
> that implementations will use it. You can certainly still reuse
> generator tables in Edwards form for calculating multiples of the base
> point without any issues.

I think this could go either way.  It’s kind of painful to ban implementations which
reject small torsion points and/or points on the twist, because that’s a natural
thing to do.  Also, AFAIK an honest party cannot complete an ECDH key exchange
with a party that sends a twist point, unless either that point is a 4-torsion point or
the honest party’s secret key is compromised.  Still, that’s a little bit of fingerprinting.

On the other hand, it is nice to lock down a specification like this completely, and
the ladder code isn’t very big.

Out of curiosity, how is this specified for RSA?  Are implementations required to
accept any (N,e)?  What if one or both are even?

>> When using other than x-only ladder for doing ECDH on these curves, is
>> there a recommended procedure for running the (twisted) Edwards point
>> multiply when starting from an 'invalid' u?  Most square root
>> procedures will fail to return an answer when y^2 is not square.
> 
> (Completely shooting from the hip: the twist of curve25519 will also
> be bi-rationally equivalent to a twisted Edwards curve. Some of the
> Edwards formulas don't depend on d and so you might be able to compute
> on that curve with the same formulae. Still, that seems more complex
> and worse than using the ladder.)

Yes, though the formulas which don’t depend on d aren’t complete.  Also,
you will need to check whether the point is on the curve or the twist to carry
out a different isomorphism in each case.

>> Regarding the Monte Carlo tests, it seems likely that a k which gets
>> turned into a u will not always be on the curve, thus making it
>> impossible also to use the tests with an Edwards (or other x-y)
>> implementation.  Perhaps both k and u should be the result of the
>> function after each iteration, ensuring a valid u as input; or k could
>> be computed from the new u, e.g.
> 
> Are the "Monte Carlo" tests the iterated ones? If so, then I think it
> might actually work out (by accident). The initial values are on the
> curve and thus so will the outputs of the function be. So I think that
> all the values will be on the curve? (Those tests were intended to
> shake out any arithmetic errors in implementations rather than
> anything else.)

This sounds right to me.

> Cheers
> 
> AGL
> 
> -- 
> Adam Langley [email-masked] https://www.imperialviolet.org
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://mail.ietf.org/mailman/listinfo/cfrg

---

From: Thomas Pornin <[email-masked]>
Date: Fri, 4 Sep 2015 15:42:03 +0200

On Thu, Sep 03, 2015 at 05:58:55PM -0700, Michael Hamburg wrote:
> Out of curiosity, how is this specified for RSA?  Are implementations
> required to accept any (N,e)?  What if one or both are even?

As per PKCS#1, implementations are only required to correctly process
"valid RSA public keys". A RSA public key is valid consists in (n,e)
where n is a product of u distinct primes (u >= 2), and e is an integer
between 3 and n-1 such that GCD(e, lambda(n)) = 1. From these rules, we
can infer that in a valid RSA public key, n and e MUST be odd.

As far as I can see, there is no rule that mandates any kind of
verification of the public key. An implementation MAY reject a public
key with an even n or an even e, but is not required to. In any case, a
verifier cannot fully check that a RSA public key is valid (e.g. it
cannot easily check that the prime factors of the modulus are distinct).

To put things into perspective, nothing in PKCS#1 says that, say,
400-bit RSA keys should be rejected (except when using a hash function
such that the padded size would simply not fit in the modulus). Yet many
implementations will reject such key sizes, and nobody clamours about
the non-compliance of such a behaviour. In fact, it is generally
considered a good thing to refuse to use a public key which is way too
small to achieve decent security.

In practice, an even modulus messes up with Montgomery multiplication;
to support exponentiations modulo an even n, one must include some
specific extra code. An RSA implementation that uses a generic
big-integer library (say, a Java implementation that runs over
java.math.BigInteger) may accept an even modulus and compute the
"proper" value x^e mod n. A dedicated RSA implementation will either
reject an even modulus, or compute something else than x^e mod n,
because it will lack the code for handling modular exponentiations
modulo an even modulus.

As for an even public exponent, there again, some implementations will
accept it, others will reject, and I suppose that some will simply
assume that the least significant bit is 1 and ignore the provided
value (it depends on whether the implementation handles the exponent
bits from least to most significant, or not).

To give an actual example: Microsoft's implementation of RSA (CryptoAPI)
used to accept e=1. It was even documented as a feature, to be used for
simple plaintext extraction of symmetric key through key wrapping. In
Windows 8.1, this ceased to work; I could not find any documentation
about that change.

I suppose the theory is that when you use a public key, whether for
encryption or signature verification, then you already have validated
that the public key is "the right one", and attack models with a
corrupted public key then make no sense at all. This is the classic,
X.509-certificates view of things, which may be restrictive.

So, basically, PKCS#1 does not specify implementation behaviour against
invalid public keys. Rejection is allowed, not mandated.

	--Thomas Pornin