How to avoid side channel attacks when handling large numbers?

Question

For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.

We have seen lots of side channel attacks due to timing differences or power usages analysis.

• How are large numbers handled in cryptography and cryptanalysis?
• What are the good libraries against side-channel attacks, including time and power analysis?
• Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?

Answer 1

I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).

Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.

Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.

BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.

An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.

Answer 2

This answer tackles mostly the first bullet:

How are large numbers handled in cryptography and cryptanalysis?

Getting the result

Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:

• Using a language without such limitation (like Python, GP/Pari, Mathematica..)
• Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like + - * / %, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=2⁴, 2⁸, 2¹⁶, 2³²..): + - have complexity $O(n)$, and schoolbook algorithms for * / % are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance.
• Using a ready-made implementation of the previous approach.
• Using an external library, which might use another language; e.g. GMP.

Other issues

Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:

1. Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
2. Security against other side-channel attacks
   • analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
   • information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
3. Performance (speed, computer resources)

The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).

Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.

---

Bibiography

For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.

Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.

Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.