1
$\begingroup$

This question is a consequence of an older one about multiplying a twisted Etwards point in Montgomery space. Turns out that this is unsafe in some circumstances.

The following Montgomery ladder as implemented in the ref10 implementation is unsafe: when the scalar is zero, the result of the multiplication is not the zero point, but a point that has a low order. This caused a critical security vulnerability in my crypto library.

Because of this, I have decided not to use the Montgomery ladder for signature verification. The Double scalar multiplication (with merged doublings and sliding windows) is faster and doesn't take much code. I would still like however to use the Montgomery ladder for signing and public key generation.

My question is, is it safe?

Public key generation multiplies the base point by a random, trimmed scalar. The trimming process is the same as for X25519: set bit 254, clear bits 0, 1, 2, and 255. I guess the Montgomery ladder unconditionally produces good results in this case, because the X25519 public key generation does the same. Is that right?

Signatures still multiply the base point, but they do not trim the scalar before performing the scalar multiplication. Instead, they start from a hash, which is different from zero, and that hash is reduced modulo L (the order of the curve). Basically, we multiply by a random number between 0 (yikes) and L-1.

I believe we have a negligible chance of multiplying by zero by accident (something like 2⁻²⁵²). We could check for an all zero input, but this looks overkill. What I'm worried about is other exceptional values. Does the Montgomery ladder fail on any other value than zero? Are any of those values lower than L?

$\endgroup$
1
$\begingroup$

Actually, the answer is none. Everything works, and produces the correct results.

Potential problems arise when converting back to Twisted Edwards space, and that's a different question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.