Is Ed25519 really constant-time as widely implemented?

Question

Despite the frequent claims that Ed25519 is more secure against side-channel attacks than (for instance) signatures performed over NIST P-256, I noticed that most implementations (including the original submissions) rely on table look-ups performed with secret index to achieve high performance.

That is notoriously a big no-no, but I see that concerns are waived due to the use of conditional move constructions.

For instance, the fundamental construct is often:

void fe25519_cmov(fe25519 *r, const fe25519 *x, unsigned char b)
{
  int i;
  crypto_uint32 mask = b;
  mask = -mask;
  for(i=0;i<32;i++) r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
}

where mask is either all 1s or all 0s.

I am not totally convinced by this construction.

For instance, when implemented in C, what are the chances that the compiler deobfuscate this into a branch?

For an assembly implementation, what is the chance that XOR by a mask depends on the number of 1s set in the mask?

Is safe to use this approach beyond Ed25519?

Answer 1

For instance, when implemented in C, what are the chances that the compiler deobfuscate this into a branch?

At first glance, it sounds unlikely. For example, if you're worried about the compiler translating this as:

 if (b) {
    for(i=0;i<32;i++) r->v[i] = x->v[i];
 }

well, that would be a valid transformation only if the optimizer could deduce that b could only be 0 or 1; depending on how the caller is written, that could be difficult.

Now, there are additional steps that the quoted code could take, such as:

volatile crypto_uint32 *dest = r->v[ix];
volatile crypto_uint32 *src = x->v[ix];
for(i=0;i<32;i++) dest[i] ^= mask & (dest[i] ^ src[i]);

(the volatile attributes would specifically prohibit the optimizer from eliding the memory accesses).

However, ultimately, we can't be certain that the optimizer doesn't insert unexpected branches (or other side channel issues) into our code; for example, the optimizer could insert logic at the beginning some code of the form:

 if (b) a_do_nothing_call();

We generally assume that the optimizer won't do that sort of thing without a good reason.

For an assembly implementation, what is the chance that XOR by a mask depends on the number of 1s set in the mask?

The answer to that would depend on the side channels you are concerned about. We assume that, with an assembler, the instructions you write are pretty much the instructions the CPU will execute, and we generally assume that the XOR instruction on the CPU doesn't access memory conditionally, or change the amount of time taken based on the data. However, if we're concerned about DPA style attacks (by which I mean an attack that depends on the actions of the gates that make up the CPU), there is some leakage - not typically a large amount, but some. The techniques we've been discussing wouldn't necessarily be sufficient, and we would need to use additional techniques (in this case, probably some sort of blinding).