Paper 2021/1121

Constant-Time Arithmetic for Safer Cryptography

Lúcás Críostóir Meier, Simone Colombo, Marin Thiercelin, and Bryan Ford

Abstract

The humble integers, $\mathbb{Z}$, are the backbone of many cryptosystems. When bridging the gap from theoretical systems to real-world implementations, programmers often look towards general purpose libraries to implement the arbitrary-precision arithmetic required. Alas, these libraries are often conceived without cryptography in mind, leaving applications potentially vulnerable to timing attacks. To address this, we present saferith, a library providing safer arbitrary-precision arithmetic for cryptography, through constant-time operations. The main challenge was in designing an API to provide this functionality alongside these stronger constant-time guarantees. We benchmarked the performance of our library against Go's big.Int library, and found an acceptable slowdown of only 2.56x for modular exponentiation, the most expensive operation. Our library was also used to implement a variety cryptosystems and applications, in collaboration with industrial partners ProtonMail and Taurus. Porting implementations to use our library is relatively easy: it took the first author under 8 hours to port Go's implementation of P-384.