bn/bn_exp.c: mitigation of the One-and-Done side-channel attack.

The One&Done attack, which is described in a paper to appear in the
USENIX Security'18 conference, uses EM emanations to recover the values
of the bits that are obtained using BN_is_bit_set while constructing
the value of the window in BN_mod_exp_consttime. The EM signal changes
slightly depending on the value of the bit, and since the lookup of a
bit is surrounded by highly regular execution (constant-time Montgomery
multiplications) the attack is able to isolate the (very brief) part of
the signal that changes depending on the bit. Although the change is
slight, the attack recovers it successfully >90% of the time on several
phones and IoT devices (all with ARM processors with clock rates around
1GHz), so after only one RSA decryption more than 90% of the bits in
d_p and d_q are recovered correctly, which enables rapid recovery of
the full RSA key using an algorithm (also described in the paper) that
modifies the branch-and-prune approach for a situation in which the
exponents' bits are recovered with errors, i.e. where we do not know
a priori which bits are correctly recovered.

The mitigation for the attack is relatively simple - all the bits of
the window are obtained at once, along with other bits so that an
entire integer's worth of bits are obtained together using masking and
shifts, without unnecessarily considering each bit in isolation. This
improves performance somewhat (one call to bn_get_bits is faster than
several calls to BN_is_bit_set), so the attacker now gets one signal
snippet per window (rather than one per bit) in which the signal is
affected by all bits in the integer (rather than just the one bit).

Reviewed-by: Andy Polyakov <appro@openssl.org>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/6276)

0 files changed, 0 insertions, 0 deletions