Timing side-channel in pure-Erlang X25519 scalar multiplication leaks the private key in jose

Summary

Observable Timing Discrepancy vulnerability in potatosalad jose allows recovery of a long-term X25519 private key through a timing side channel in the pure-Erlang Curve25519 fallback.

The pure-Erlang X25519 implementation performs scalar multiplication over the secret private key using a recursive Montgomery ladder (jose_jwa_x25519:curve25519/2) whose clauses branch on individual bits of the clamped private scalar, and whose per-step operations (jose_jwa_x25519:montgomery_add/3 and jose_jwa_x25519:montgomery_double/1) and field inversion are built from value-dependent Erlang bignum arithmetic (multiplication, remainder, and modular exponentiation). Although the ladder is operation-count balanced and fixed at 254 steps, the concrete integer values processed at each step, and therefore the running time, depend on the secret scalar. The execution time of the public entry points jose_jwa_x25519:scalarmult/2, jose_jwa_x25519:x25519/2, jose_jwa_x25519:x25519_base/1, and jose_jwa_x25519:sk_to_pk/1 is thus a function of the private key.

This path is reachable from the public API, most notably when a service decrypts attacker-supplied ECDH-ES (JWE) messages with a long-term X25519 key (for example through JOSE.JWK.box_decrypt_ecdh_es/2, which reaches jose_jwa_curve25519:x25519_shared_secret/2 and the ladder). An attacker who can submit ciphertexts and measure decryption timing can, in principle, recover the private key bit by bit, defeating the resistance X25519 was designed to provide. Recovery of the key compromises the confidentiality and authenticity of all data protected by it.

This issue affects jose: from 1.10.0 before 1.11.13.

Workarounds

Use a constant-time native X25519 implementation for private-key operations: install the libsodium or libdecaf NIF, or run on an OTP release whose crypto application provides x25519, and do not force the pure-Erlang Curve25519 fallback (JOSE.crypto_fallback(true) or JOSE.curve25519_module(:jose_jwa_curve25519)) for long-lived keys.

Configurations

The vulnerability is only exploitable when X25519 private-key operations run through the pure-Erlang Curve25519 fallback, for example when the crypto fallback is enabled (JOSE.crypto_fallback(true) or JOSE.curve25519_module(:jose_jwa_curve25519)) or when no constant-time native X25519 implementation (a libsodium or libdecaf NIF, or the OTP crypto application providing x25519) is available. Deployments that use a constant-time native X25519 are not affected.