2
$\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); }
Improve this question
$\endgroup$
2

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This answer need the solution, though the OP did not show how they used the result.. $\endgroup$ Commented Jan 5, 2024 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$ Commented Jan 5, 2024 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$ Commented Jan 5, 2024 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$ Commented Jan 5, 2024 at 13:13
  • $\begingroup$ Then you may separate the condition and use 2:1 multiplexer as stated in the if/else $\endgroup$ Commented Jan 5, 2024 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.

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

Improve this answer
$\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$ Commented Jan 6, 2024 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$ Commented Jan 8, 2024 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$ Commented Jan 9, 2024 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$ Commented Jan 9, 2024 at 7:02

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.