4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This is a rather programming question about the compiler. Do you expect that the compiler designers change/optimize your assembly code in C code? That would defeat the purpose of inline assembly. If it ever optimizes there should be some flags not to do it. $\endgroup$ – kelalaka Feb 8 at 11:23
  • $\begingroup$ Where in the example you gave you see "table look-ups performed with secret index" or any other data-dependent computation flow? $\endgroup$ – Krystian Feb 8 at 17:19
  • $\begingroup$ @Krystian the variable b contains a secret bit, and the goal of this specific function is to leave r->v with the value it has or the value of x->v. It is commonly seen in Ed25519 code for windowed multiplication of a fixed secret scalar by a fixed-point. $\endgroup$ – SquareRootOfTwentyThree Feb 8 at 23:39
  • $\begingroup$ The value of b has no effect on which indices are accessed nor what order they are accessed in. There are no table lookups based on b. $\endgroup$ – Future Security Feb 9 at 0:14
  • $\begingroup$ @SquareRootOfTwentyThree: But note that regardless of the value of bit b, the sequence of memory lookups is the same. So it's not a side channel, since from the complete sequence of memory reads the attacker doesn't gain any knowledge about the value of b. $\endgroup$ – Krystian Feb 10 at 20:13
1
$\begingroup$

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).

| improve this answer | |
$\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.