I want to break square-free: The 4p-1 factorization method and its RSA backdoor viability [SeCrypt 2019]

  @conference{secrypt19,
   author={Vladimir Sedlacek and Dusan Klinec and Marek Sys and Petr Svenda and Vashek Matyas.},
   title={I Want to Break Square-free: The 4p − 1 Factorization Method and Its RSA Backdoor Viability},
   booktitle={Proceedings of the 16th International Joint Conference on e-Business and Telecommunications (ICETE 
   2019) - Volume 2: SECRYPT,},
   year={2019},
   pages={25-36},
   publisher={SciTePress},
   organization={INSTICC},
   doi={10.5220/0007786600250036},
   isbn={978-989-758-378-0},
  }

Abstract:

In this paper, we analyze Cheng's $4p-1$ factorization method as the means of a potential backdoor for the RSA primes generated inside black-box devices like cryptographic smartcards, and we devise three detection methods for such a backdoor. We also audit 44 millions of RSA keypairs generated by 18 different types of cryptographic devices. Finally, we offer an improved, simplified and asymptotically deterministic version of the method, together with a deeper analysis of its performance and we publish a Sage implementation (we are currently not aware of any other public implementation).

The contributions of the paper are the following:

• We analyze and improve a factorization method of integers of special form pq, where p,q are primes and the square-free part of 4p-1 is small. If an RSA key is generated in this form, an attacker can easily factor a modulus with bit length 2048 (and even more).
• If an RSA key is generated properly, such vulnerability almost never occurs. Thus if such a vulnerability is present, it was intentionally created.
• We devised and analyzed several possible methods of detecting such a backdoor and applied these on 44 millions of RSA keypairs generated by 18 different types of cryptographic devices.
• Even though we did not find any indication of a backdoor on the examined devices, we showed that generating vulnerable keys is possible by a clever attacker.

• Factorization implementation, testing code and more
• ERRATA: The final estimates in Section 5.1 of the paper are flawed. Please see pages 26-27 in the relevant PhD thesis for the correct version. However, the conclusions do not fundamentally change.
• There has been a rather curious timeline of developments related to the method. In 2002, Cheng published a version working for linear Hilbert polynomials, and shortly after that, a a revised version working for all Hilbert polynomial degrees. We encountered both of these papers only after reinventing the respective part of the method ourselves, but luckily before submitting our paper. Interestingly, it seems that Shirase unknowingly made the same mistake - his 2017 paper references only Cheng's first paper and introduces the solution for quadratic Hilbert polynomials, which is a special case of Cheng's second approach. But the story does not end here - Aikawa, Nuida and Shirase independently rediscover the solution for an arbitrary degree in their 2019 paper (around the same time our paper was published), though they also extend the method for traces of Frobenius other than 1. The recent 2021 paper by Vitto summarizes some of these developments and finds new applications. Let this comment serve as a cautionary tale for all of us who have tendencies to rediscover the wheel.

We acknowledge the support of the Czech Science Foundation, project GA16-08565S. V.Sedlacek was also supported by the Brno Ph.D. Talent Scholarship (funded by the Brno City Municipality). The access to the computing and storage resources of National Grid Infrastructure MetaCentrum (LM2010005) is greatly appreciated.