High-assurance field inversion for curve-based cryptography

Benjamin Salling Hvass, Diego F. Aranha, Bas Spitters

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Abstract

The security of modern cryptography depends on multiple factors, from sound hardness assumptions to correct 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 a cryptographic computation, with a small impact on 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 [1]-[3]. In this work, we focus on implementing field inversion for primes of cryptographic interest with security against timing attacks, irrespective of whether the FLT-based inversion can be efficiently implemented. We extend the Fiat-Crypto framework, which synthesizes provably correct-by-construction implementations, to implement the Bernstein-Yang inversion algorithm as a step towards this goal. This allows a correct implementation of prime field inversion to be 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 for the largest parameters.

Original languageEnglish
Title of host publication 2023 IEEE 36th Computer Security Foundations Symposium (CSF)
Number of pages16
PublisherIEEE
Publication date2023
Pages552-567
ISBN (Print)979-8-3503-2192-0
DOIs
Publication statusPublished - 2023
Event36th IEEE Computer Security Foundations Symposium - Dubrovnik, Croatia
Duration: 10 Jul 202314 Jul 2023
https://www.ieee-security.org/TC/CSF2023/

Conference

Conference36th IEEE Computer Security Foundations Symposium
Country/TerritoryCroatia
CityDubrovnik
Period10/07/202314/07/2023
Internet address
SeriesProceedings of the IEEE Computer Security Foundations Symposium
ISSN1940-1434

Keywords

  • Constant-time execution
  • Field arithmetic
  • Formal verification
  • Implementation security

Fingerprint

Dive into the research topics of 'High-assurance field inversion for curve-based cryptography'. Together they form a unique fingerprint.

Cite this