Cryptology ePrint Archive: Report 2021/549

High-assurance field inversion for curve-based cryptography

Benjamin Salling Hvass and Diego F. Aranha and Bas Spitters

Abstract: Modern cryptography must satisfy a myriad of security properties, ranging from sound hardness assumptions to correct and secure implementations that resist side-channel cryptanalysis. Curve-based cryptography is not different in this regard, and substantial progress in the last few decades has been achieved in both selecting parameters and devising secure implementation strategies. In this context, the security of implementations of field inversion is sometimes overlooked in the research literature, because (i) the approach based on Fermat's Little Theorem (FLT) suffices performance-wise for many parameters used in practice; (ii) it is typically invoked only at the very end of scalar multiplication or pairing computation, with a small impact in performance; (iii) it is challenging to implement securely for general parameters without a significant performance penalty. However, field inversion can process sensitive information and must be protected with side-channel countermeasures like any other cryptographic operation, as illustrated by recent attacks. In this work, we focus on timing attacks against field inversion for primes of cryptographic interest, both in the case when FLT-based inversion can be efficiently implemented or not. We extend the Fiat-Cryptography framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang constant-time inversion algorithm as a step toward this goal. This allows a correct implementation of prime field inversion to be conveniently synthesized for any prime. We benchmark the implementations across a range of primes for curve-based cryptography and they outperform traditional FLT-based approaches in most cases, with observed speedups up to 2.5 for the largest parameters.

Category / Keywords: implementation / Field inversion, Constant-time execution, Implementation security, Formal verification.

Date: received 25 Apr 2021, last revised 27 Apr 2021

Contact author: bsh at cs au dk,dfaranha@cs au dk,spitters@cs au dk

Available format(s): PDF | BibTeX Citation

Version: 20210427:064655 (All versions of this report)

Short URL: ia.cr/2021/549


[ Cryptology ePrint archive ]