Wild Side Channels
RSA relies on basic modular arithmetic to secure and sign a massive percentage of Internet traffic. In fact, RSA signing is so simple that Medium’s math formatting almost supports it¹:
M is the message to sign, d is the signing (private) key, n is the (public) modulus, and S is the resulting signature. So it must just be for job security, then, that cryptographers still proclaim in the forums that you should not write your own cryptography — right?
Well, not exactly. A secure hash function is most obvious omission from a naive RSA signing function such as the one above — passing in un-hashed data leaves signers vulnerable to oracle attacks² — but there are more subtle and creative ways of cracking bad implementations of even such simple cryptographic functions. Cryptography is a single (albeit supremely strong) point of failure for data protection, and so sophisticated attackers will pile mountains of time and resources into figuring out ways to break it. Side channel attacks demonstrate the surprising creativity cryptanalysts wreak on imperfect implementations of theoretically secure algorithms.
Timing Attacks
Cryptographic computations — such as encryption, decryption, or signing — must be performed on real hardware. Layers of abstraction usually hide raw hardware instructions from the developer, but ultimately C compiles to machine code, Rust compiles to machine code, and Java compiles to Java bytecode, which the JVM translates to machine code. Since computations must be performed on real hardware, they are subject to physical constraints.
In particular, the time a computation takes will vary based on the specific numbers involved in it. For example, multiplying an integer by two may only require a single bit shift and the activation of a small number of logical gates, whereas multiplying the same number by three may require the execution of a more general multiplication algorithm and the activation of a much larger number of logical gates. For known hardware, an attacker can test the time different computations will take and use this information to triangulate a secret or a private key.
Timing attacks are the most common type of side channel attack on many different cryptographic algorithms. Surprisingly, they are even possible over a network.⁴ AES presents users with a particularly difficult tradeoff between speed and susceptibility to timing attacks⁵. On the other hand, RSA, with its highly commutative mathematical foundations, permits a relatively easy mitigation called blinding.
Before decryption or signing⁶, choose a random padding r and compute the multiplicative inverse of r modulo n (the same n used as the RSA modulus). For a message M as before and a public key e such that⁷ ed = 1 (mod λ(n)), the signature S is instead computed in two steps:
The signature S will be the same as before, but now the involved computations will include random noise that will subdue attempts at timing attacks.
Most modern cryptography libraries use this trick — OpenSSL’s implementation of it is spread across a few files. crypto/rsa/rsa_ossl.c, the file containing most of the RSA logic, contains the snippets
if (blinding != NULL) {
...
if (!rsa_blinding_convert(blinding, f, unblind, ctx))
goto err;
}
... (Perform the RSA decryption)
if (blinding)
if (!rsa_blinding_invert(blinding, ret, unblind, ctx))
goto err;around the decryption call (of which I am trying my hardest to avoid bothering the maintainers with a PR to standardize the code style). These call the rsa_blinding_convert and rsa_blinding_invert functions with blinding, the random blinding parameter r, f, the data to be encrypted, unblind, the unblinding factor — the inverse of r, and ctx, the RSA context (importantly, this structure contains the RSA modulus). These are channeled into calls to functions in the “big number” (BN) module. In particular, crypto/bn/bn_blind.c has the functions
int BN_BLINDING_convert_ex(BIGNUM *n, BIGNUM *r, BN_BLINDING *b, BN_CTX *ctx)
{
...
if (b->m_ctx != NULL)
ret = BN_mod_mul_montgomery(n, n, b->A, b->m_ctx, ctx);
else
ret = BN_mod_mul(n, n, b->A, b->mod, ctx);
return ret;
}which multiplies the blinding factor and the data to be signed or decrypted, and
int BN_BLINDING_invert_ex(BIGNUM *n, const BIGNUM *r, BN_BLINDING *b,
BN_CTX *ctx)
{
...
if (b->m_ctx != NULL) {
/* ensure that BN_mod_mul_montgomery takes pre-defined path */
if (n->dmax >= r->top) {
size_t i, rtop = r->top, ntop = n->top;
BN_ULONG mask;
for (i = 0; i < rtop; i++) {
mask = (BN_ULONG)0 - ((i - ntop) >> (8 * sizeof(i) - 1));
n->d[i] &= mask;
}
mask = (BN_ULONG)0 - ((rtop - ntop) >> (8 * sizeof(ntop) - 1));
/* always true, if (rtop >= ntop) n->top = r->top; */
n->top = (int)(rtop & ~mask) | (ntop & mask);
n->flags |= (BN_FLG_FIXED_TOP & ~mask);
}
ret = bn_mul_mont_fixed_top(n, n, r, b->m_ctx, ctx);
bn_correct_top_consttime(n);
} else {
ret = BN_mod_mul(n, n, r, b->mod, ctx);
}
bn_check_top(n);
return ret;
}which contains a significant amount of logic to ensure that the unblinding does not permit any timing attacks.
Acoustics
Timing attacks are not the only way to divine key material without attacking a cryptographic algorithm directly. In a paper⁸ that may be deeply disturbing to the spiritual constitution of anyone unfamiliar with it, three authors (including Adi Shamir, the “S” in RSA) demonstrated an acoustic side-channel attack: the researchers found that different private keys produced different acoustic signatures and that these could accurately predict the private key used in an RSA signing or decryption operation. In other words, transformer whine gave away the private key the CPU used to sign messages. Amazingly, they were able to reproduce their results using a mobile phone microphone (circa 2013) placed multiple feet from the test computer.
Obviously, an acoustic attack of this nature is extremely hardware dependent and depending on the acoustic environment, could suffer significant practical limitations. It also requires the placement of a microphone near the target CPU. The researchers state that implementations of RSA that use blinding appear to be less vulnerable to acoustic cryptanalysis, which makes sense given that the acoustic signatures produced by a CPU likely correlate with the same patterns in logic gate activation that facilitated timing attacks. But the profundity of the fact that this attack is possible cannot be overstated.
Attacks like this — as well as the relative obscurity of even more common tricks like blinding — are the reason that cryptographic implementations are better left to the experts.
Endnotes
- Medium doesn’t support super-scripted letters (without special characters).
- https://en.wikipedia.org/wiki/Chosen-ciphertext_attack
- Bernstein, Daniel J. “Cache-timing attacks on AES.” April 14, 2005. http://cr.yp.to/antiforgery/cachetiming-20050414.pdf.
- Brumley, David, and Dan Boneh. “Remote timing attacks are practical.” Computer Networks 48, no. 5 (2005): 701–716. https://crypto.stanford.edu/~dabo/papers/ssl-timing.pdf.
- Bernstein, sections 8–15.
- RSA decryption and signing are identical operations.
- λ(n) is Carmichael’s totient function. The Wikipedia article on RSA has a good explanation of why this is used instead of the textbook Euler’s totient function.
- Genkin, Daniel, Adi Shamir, and Eran Tromer. “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis.” December 18, 2013. http://www.cs.tau.ac.il/~tromer/papers/acoustic-20131218.pdf.
