What is bignum-free RSA?

Question

I recently saw a claim that BearSSL has a bignum-free implementation of RSA. What does this mean? I don't see how one could implement RSA without bignum arithmetic.

Answer 1

It just means that BearSSL was implemented without using any third-party bignum libraries. According to the BearSSL website:

BearSSL's current implementation are less than optimal with regards to performance; they are in pure C, with only 32-bit multiplications. Better implementations shall be added in subsequent versions.

Avoiding the use of external code libraries is one way of reducing the size and attack surface of a software package. For example, gmp (a popular bignum library) includes all sorts of functions that are unnecessary for RSA, like signed arithmetic and floating-point arithmetic, and is optimized for speed rather than security. So it's probably vulnerable to timing attacks.

Rather than importing a bignum library from somewhere else and auditing its security performance in exhaustive detail, it looks like the BearSSL developers decided to roll their own code instead.

Answer 2

First things first, I would not have described BearSSL as being "bignum-free". However, it is true that it does not have a generic implementation of big integers; what it contains is a generic implementation (actually several) of big modular integers. And it matters.

About low-level multiplications

Software libraries run on some hardware and cannot use anything else than what the hardware offers. Regarding multiplications, a common CPU will offer a 32-bit multiplication with a 64-bit result. For instance, the x86 line of CPU has an assembly opcode called mul that multiplies two 32-bit unsigned values (one in the eax register, the other in a register passed as parameter) and yields a 64-bit result, split into two 32-bit halves in eax and edx. When writing C code, you usually obtain a result of the same size as the operand, i.e. if you multiply two uint32_t values, you get a uint32_t result; to obtain the full 64-bit result, you need to use some casts into uint64_t. When BearSSL was first released, this 32×32→64 multiplication was the largest that the implementation was using.

Some architectures do not offer a 32×32→64 opcode. In particular, the ARM Cortex M0 and M0+ have an efficient 32×32→32 opcode, but a 32×32→64 multiplication must use a software routine that is considerably slower (we are talking about 1 cycle vs 40 cycles here) and also often non-constant-time. Some other have a 32×32→64 opcode, but it is not constant-time (e.g. ARM Cortex M3). This is why BearSSL also offers implementations that use only 16×16→32 multiplications (these are codenamed "i15" in the BearSSL API).

More recently, I added some code called "i62" which leverages the 64×64→128 opcodes that are available on some big architectures, in particular x86 in 64-bit mode. This requires using some compiler-specific extensions, because (in general) there is no uint128_t type made available (see here for the relevant source code; this is done only for modular exponentiations, as used in RSA).

About generic bignum code

Many cryptographic libraries include a generic "big integer" implementation: this is a set of memory structures and functions that can represent and perform arithmetic operations on integers which are not a priori limited in length. In OpenSSL, this is called BIGNUM (or "BN"). Internally, each such big integer is a structure that references an array that contains the integer contents, split into elementary "limbs" (in the same way that when you write an integer in decimal, you represent it as a sequence of digits); other structure elements contain the actual integer length and relevant memory management information.

Writing a generic big integer library is a natural way of doing things: a good software engineer thinks top-down and writes code bottom-up. Thus, since many asymmetric cryptographic algorithms are expressed over large integers (e.g. RSA, DSA, ECC...), that engineer will start by writing a good, reliable big integer library, then use it to implement the relevant algorithms. As a second phase, for pure performance reasons, some of the most expensive operations in the said algorithms will be reimplemented with dedicated code (that's how OpenSSL now has dedicated assembly code with AVX2 opcodes that handles, specifically, the modular exponentiations in RSA for RSA keys of length exactly 2048 bits). Also, when implementing cryptography in some languages, a big integer library is already there and ready to be used (e.g. Java's java.math.BigInteger).

Now, BearSSL does not follow that road, and there is a reason. BearSSL does not include a generic "big integer" library. It has something which somewhat looks like it, but really implements operations on modular integers, i.e. integers considered modulo a given (odd) integer. The functions are not part of the public API (this is for internal use) but are documented here. Implementation is in the src/int/ directory.

The underlying reason is the quest for constant-time code, so as not to leak information through timing-based side channel attacks, in particular cache attacks. To really defeat such attacks, the implementation must use a memory access pattern that does not depend on secret information. However, a generic big integer implementation cannot be constant-time, because values are allocated in buffers which are dynamically sized, depending on the represented integer; therefore, an attacker who can observe the memory access pattern of some code will be able to notice when an integer value is "short" or "long".

To follow a strict constant-time discipline in BearSSL, a modular integer is handled in an array whose length matches that of the modulus, not that of the value itself, and all array slots are always accessed, even in cases where some contains only zeros. Internally, that concept is described as "announced bit length": a big integer structure, in its header, states a bit length which is that of the modulus, and all operation loops work on that bit length, not on any length inferred from the value (the big integer "structure" is actually a simple array of words, and the "header" is the first word in that array).

It shall be noted that usual cryptographic libraries like OpenSSL have a long history, which began way before cache attacks were invented; moreover, their "big integer" library is often part of the public API, and thus they cannot simply remove it without breaking compatibility with existing applications. BearSSL is relatively recent (I started it in 2015), and thus I could design its structure and API with full knowledge of cache attacks, hence the lack of generic big integer code, and also the fact that the code for modular integers is not part of the public API (so that I may change things later on, if necessary).

Answer 3

The biggest and largely untapped security issue nowadays are so-called side-channel attacks where the algorithm itself is "correct" but information about its operation leaks to different processes: operations with different input lead to different branches being taken and different memory locations getting accessed. The changes in global internal state of the CPU in the form of the subsequent performance of possibly affected cache hits or branch predictions or temperature changes or other measurable impacts can be observed using carefully crafted code running in purportedly independent tasks.

The recent Spectre and Meltdown vulerabilities of Intel CPUs are an artifact of "speculative execution" bypassing all memory protection layers for efficiency reasons and its "results" getting discarded when the speculatedly executed code is determined not to be actually a target of running. Its sidechannel effects, however, stay around.

To come back to the question: when using an external multiprecision library, this library will be designed for efficiency and thus will minimize the expected computational requirements, resulting in performance and behavior dependent on the actual values being processed. This will make the library's operation observable via side channel attacks, and since the objectives of a general multi-precision library and the arithmetic for applications intended not to be prone to side-channel attacks for its own use cases differ, using efficient multi-precision libraries not specifically designed for the cryptographic task to be performed is vastly more likely to result in software observable in manners breaking its encapsulation.

Some such sidechannel attacks can even be performed through code executed via JavaScript compilers.