17

When you are working with secret keys, if your code branches unequally it could reveal bits of the secret keys via side channels. So for some algorithms it should branch uniformly independently of the secret key.

On C/C++/Rust, you can use assembly to be sure that no compiler optimizations will mess with the branching. However, on Java, the situation is difficult. First of all, it does JIT for desktop, and AOT on Android, so there are 2 possibilities for the code to be optimized in an unpredictable way, as JIT and AOT are always changing and can be different for each device. So, how are side channel attacks that take advantage of branching prevented on Java?

Guerlando OCs
  • 405
  • 4
  • 14

2 Answers2

24

While you can make some attempt towards constant-time code in general purpose JITed languages like Java, you generally run into some problems:

  • The runtime implementation is, generally, intended to be transparent to the code that is running on top of it, and therefore does not provide strong guarantees about timing behaviour or cache side-channels.
  • If you validate that a Java program generates constant-time results when executed under a particular JRE, there is no guarantee that the timing behaviour will remain unchanged on other JREs or after updates are installed.
  • If you validate that a Java program generates constant-time results when running on a particular architecture, there is no guarantee that the timing behaviour will remain unchanged on other architectures.
  • Assumptions made about the behaviour of runtime library calls may be invalidated after updating the runtime library.
  • The JRE/JIT is a very large and complex system that might have unforeseen behaviours in circumstances that were not identified during development and testing of a constant-time implementation written in Java.

The result of this is that you can't really use Java to solve the problem, in most cases. You need to solve it in a way that doesn't depend on JIT behaviour.

There are three general approaches here:

  1. The runtime library contains one or more constant-time platform-native implementations of the functionality. These are specific to the architecture.
  2. The runtime library contains an implementation that provides a shim interface between the Java code and some underlying hardware implementation of the functionality (e.g. if you're running Java on an ARM SoC and that processor has a cryptographic coprocessor or HSM).
  3. An implementation is written in a different language that allows for constant-time guarantees, which the Java code can then call into using JNI.

These approaches allow for the constant-time parts to be made and maintained more easily.

One final approach that isn't really relevant in the general case, but does come up in some specific circumstances (e.g. Java smartcards), is the use of a custom runtime and JIT/AOT that provides extra controls and guarantees that allow for these algorithms to be implemented directly in Java, albeit with some extra development overhead and (usually) a much more constrained environment.

Polynomial
  • 132,208
  • 43
  • 298
  • 379
  • do you think a code implemented in Java would be only dangerous for side channel attacks that require phisical access to the device? I was thinking if there's a way to retrieve information remotely in this case – Guerlando OCs Mar 07 '22 at 01:51
  • If I remember correctly, the RSA implementation on Java uses BigInteger, so it's a pure implementation. how do they handle this kind of stuff? – Guerlando OCs Mar 07 '22 at 01:54
  • 3
    @GuerlandoOCs Timing attacks could definitely be viable over the network. The BigInteger implementation itself is mostly constant-time, and the RSA implementation that uses it is written in a way that avoids secret-dependent timing variances. That said, the typical RSA implementation in the standard Java runtime library is absolutely not secure against things like power analysis, due to Chinese Remainder Theorem optimisations used in it. In Java smartcards the implementation is different to avoid that issue. – Polynomial Mar 07 '22 at 03:25
  • 2
    Java for JavaCards is not really Java. It is a very *very* small subset of it. No JIT there. – A. Hersean Mar 07 '22 at 09:08
  • @A.Hersean Yes, sorry, I should've made it clear that that's all AOT. – Polynomial Mar 07 '22 at 19:45
3

The best way to mitigate branch side-channel attacks in Java is to completely eliminate branches that depend on secret data. Do all your work using simple arithmetic (=, +, -, *, <<, >>, >>>, ~, &, |, ^), which any reasonable JIT should should compile down to constant-time single machine instructions. Also don't use secret indexes when reading arrays.

Even if you ensure your Java, C, or machine code is perfectly constant-time, you still cannot prevent the CPU silicon from implementing something like if (eax == 0) delayOneExtraClockCycle();. Indeed, there are some systems where writing a cache line (~64 bytes) full of zeros is faster than writing a line that isn't uniformly zero.

See also: Is masking effective for thwarting side channel attacks?

Example: Selector

// Given values
int s = (...);  // Boolean 0 or 1
int x = (...);
int y = (...);

// Naive computation with potential branch
int z = s != 0 ? x : y;

// Constant-time computation
int z = (-s & x) | ((s - 1) & y);

Example: Equality

// Given values
int x = (...);
int y = (...);

// Naive computation with potential branch
int z = x == y ? 1 : 0;  // Boolean 0 or 1

// Constant-time computation
int z = ~((x ^ y) | -(x ^ y)) >>> 31;  // Boolean 0 or 1

Example: A full elliptic-curve cryptography stack

Int256Math.java, CurvePointMath.java, Ecdsa.java

Nayuki
  • 222
  • 2
  • 7