Successful attacks against 1024-bit RSA signatures

Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé published a report "Forging 1024-bit RSA signatures in nearly SNFS time" on implementing and successfully executing a not so well-known attack to forge RSA-1024 signatures by Joux, Naccache, and Thomé from 2007. The attack applies in principle to the blind signatures used by GNU Taler and as far as we know is the most efficient forgery attack on RSA signatures today.

Effects on Taler

Any real and recommended deployment of GNU Taler is not at risk from this attack, due to the following security measures in GNU Taler:

• Secure defaults: Taler's default minimal security level is RSA-2048, which makes the attack economically infeasible in practice.
• Key rotation: Taler supports key rotation of demonination keys, with a default of once per week, which makes the attack technically infeasible in practice.
• Alternative to RSA available: Taler supports blind signatures of type Clause-Schnorr—introduced precisely as an alternative to RSA—which are not affected by this attack.

Though we've never recommended using RSA-1024 and the academic attack is rather expensive, it still makes sense to analyze it to derive what its implications are on how one should configure a GNU Taler exchange, after all forging RSA signatures would enable an attacker to print money and bankrupt Taler exchange operators! What follows is a coarse back-of-the-envelope rough extrapolation of the cost of the attack against the standard GNU Taler configuration.

Technical Analysis

At a high level, the attack requires two steps: obtaining many signatures, and then doing an expensive computation using them. At RSA-2048, the recommended minimal security level for GNU Taler, the attack requires the attacker to obtain 2⁴³ signatures. Obtaining a signature from a Taler exchange is pretty easy: you can just pay for one. However, you need this many signatures for the same RSA key, and GNU Taler supports key rotation. Let's assume we rotate keys once per week (our default), and an attacker attacks the 0.02 EUR denomination (forging 0.01 EUR might be ineffective, given that the deposit fee for 0.01 EUR is likely 0.01 EUR leaving no profit for the attacker). In that case, you would need to withdraw 2⁴³ * 0.02 EUR or about 175 billion Euros in a single week. As a point of comparision, the GDP of the European Union is about 416 billion per week. Now, assuming the attacker has that much money to spend on buying the signatures, how about the computation?

Well, the first issue is the exchange server. While the attacker doesn't have to provision it, it still must be able to respond to the attackers requests and create a sufficient number of signatures. The exchange would need to create the 2⁴³ signatures in 7 days, and the current Taler implementation does not support sharing the same RSA key across multiple machines (each host creates its own private keys). Given a modern 256-core dual-die system where each core can create approximately 10,000 RSA-2048 signatures per second we can get about 2⁴¹ RSA signatures per week from a single host, assuming the system does basically nothing else. This would also require at least 15 GBit of sustained bandwidth for the blinded values, blind signatures and other protocol overheads. Pretty impressive: Taler theoretically could mint digital cash for the entire EU GDP on a single host, even using a rather tiny denomination of 0.02 EUR. The adversary would need to store at least the resulting 360 TB of signatures.

Still, that's only the first phase. In the second phase, the attacker would need to do 2⁹⁰ computations. The authors write that doing 2⁶⁵ computations (for RSA-1024) took 1380 core-years. So for RSA-2048, this would imply 2²⁵ * 1380 core-years or approximately 46 billion core-years. Realistic prices per core-year are around USD 100, so the computational cost of the attack would be about 4.6 trillion USD, or about 10% of the current US national debt. There is a little problem with provisioning the compute though: a random Internet search suggests we have about 2 billion (suitable, high-performance) CPU cores available in data centers on the planet (an alternative quick plausibility check suggested AMSL production limits resulting in about 4-8 billion suitable CPU cores having been produced in total by 2026). Taking the 2 billion number as available compute capacity, the computational part of the attack would require 23 years, and in the default configuration GNU Taler's blind signatures expire after about 2 years. Hence, for a practical attack, an attacker would also have to scale global available data center capacity by a factor of 10, and then use all of it for two years.

In summary, RSA-2048, especially combined with key rotation, makes the attack infeasible in practice. The GNU Taler default configuration should remain safe until attacks improve significantly. Concerned central banks for China, the US or Europe that require additional safety margins are advised to increase the key rotation frequency for their rCBDC GNU Taler deployments to once per day or even per hour. GNU Taler also supports RSA-4096, but at this point we see no reason for anyone to use settings beyond RSA-2048.