1
$\begingroup$

If I have a function f(x, y) and g(x, y) and f and g a are constant time, is the following code vulnerable to side channel attacks (assuming the conditional is constant time as well)

if (conditional) {
  f(a, b);
  g(b, a);
else {
  f(b, a);
  g(a, b);
}
$\endgroup$
2

3 Answers 3

2
$\begingroup$

Yes. The if-else statements illustrated in the OP would usually compile to something similar to this:

JUMP-IF   ElseLabel, Condition-Register;
MOV       Arg1, a
MOV       Arg2, b
CALL      f
MOV       Arg1, b
MOV       Arg2, a
CALL      g
JUMP-TO   EndOfElseLabel
ElseLabel:
MOV       Arg1, b
MOV       Arg2, a
CALL      f
MOV       Arg1, a
MOV       Arg2, b
CALL      g
EndOfElseLabel:

It is the consensus of the cryptography community that any non-deterministic code paths constitute side channel, such as the one above where assembly code may take either path depending on the condition. This is exacerbated considering (among many reasons) the CPU implementations would often carry out predictive branching - code paths are executed behind-the-scene with outcome chosen at a time deferred to when the condition is actually computed.

$\endgroup$
5
  • $\begingroup$ This answer need the solution, though the OP did not show how they used the result.. $\endgroup$
    – kelalaka
    Commented Jan 5 at 11:37
  • $\begingroup$ @kelalaka I may offer a solution if OP tell us what language they're using. I would assume C, but even then, I need to know what type each variables are. $\endgroup$
    – DannyNiu
    Commented Jan 5 at 11:39
  • $\begingroup$ We have a common solution for the if/else independent of the language, the real problem what they do with the result.. $\endgroup$
    – kelalaka
    Commented Jan 5 at 11:45
  • $\begingroup$ @DannyNiu I'm using Rust for the same. Both results are assigned to an x and y variable in both branches. $\endgroup$
    – Rabool
    Commented Jan 5 at 13:13
  • $\begingroup$ Then you may separate the condition and use 2:1 multiplexer as stated in the if/else $\endgroup$
    – kelalaka
    Commented Jan 5 at 13:21
1
$\begingroup$

Yes, the code shown is potentially vulnerable to timing attack, the simplest form of side-channel attack, to determine the value of condition. More generally, essentially any use of a variable quantity in C or Rust can leak it's value by side-channels, e.g. power analysis.

Among the few uses of a variable quantity that is generally* safe from timing attack in compiled languages (like C or Rust) on modern CPUs are bitwise and arithmetic operators & | ^ ~ + - when operating on integer types; casting among these types; shift (<< >>) of such quantity if the shift count is non-secret (including a public constant shift). Also, reading from or writing to a variable (or a vector at a non-secret offset) is safe.

With this in mind, assuming a and b are of unsigned type, and condition is 0 or 1 and of type ìnt, this code is provably equivalent to the one in the question and is less unlikely to be constant-time:

unsigned ai = a ^ b;
unsigned bi = ((-(unsigned)conditional) & ai) ^ a; // b if conditional, a otherwise
ai ^= bi;                                          // a if conditional, b otherwise
f(ai, bi);
g(bi, ai);

This produces the correct result because (-(unsigned)conditional) has all it's bit at 0 if conditional is 0, and all it's bit at 1 if conditional is 1. This is an insurance of the C language.

This solves the data-dependent timing in the code shown, but is still potentially vulnerable to other side-channel attacks, e.g. power analysis. And of course there remains the potential for data-dependent timing inside the code of f and g.


* It's still advisable to check the generated code, especially when using signed quantities. An example is uint64_t j = i where i is an ìnt8_t variable: duration conceivably could depend on the sign of i on some combinations of CPU and compiler.

$\endgroup$
0
$\begingroup$

You can try

f(conditional ? a : b, conditional ? b : a)
g(conditional ? b : a, conditional ? a : b)

Then check the assembler code to see that the compiler is using conditional instruction.

$\endgroup$
4
  • $\begingroup$ I compiled this code there with their default (x86-64 gcc 13.2) and there are four more jmp when conditional is true. Curse is that the four tests are implemented with je. And even if nominal timing was the same, there could still be timing dependencies due to branch prediction. The safe thing is to consider that any code that branches according to secret data can leak it thru timing. $\endgroup$
    – fgrieu
    Commented Jan 6 at 17:53
  • $\begingroup$ That’s a shame. Clang on arm which I usually use would do this without branches with a bit of optimisation. I guess gcc and clang should provide a built in intrinsic. You’d still have to check the assembler code. $\endgroup$
    – gnasher729
    Commented Jan 8 at 21:30
  • $\begingroup$ This code would probably (I think, but not sure) compile to branch-free code on GPUs. I'd assume so as OpenCL spec specified a tenary operator-like function that's recommended as replacement for use in expressions in place of if-else statements $\endgroup$
    – DannyNiu
    Commented Jan 9 at 2:07
  • $\begingroup$ Admittedly, if I compile with -O2, gcc's code uses a single branch, and clang's code is linear. The later uses cmove, and I wish I knew if it is constant time on every x64 CPU. $\endgroup$
    – fgrieu
    Commented Jan 9 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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