Differences

This shows you the differences between two versions of the page.

--- em:20482030 [2023/07/10 20:04] – Typo b.walzer
+++ em:20482030 [2024/11/22 23:01] (current) – [2048 Bit RSA and the Year 2030] NIST speaks, typo b.walzer
@@ Line 1: / Line 1: @@
 ======2048 Bit RSA and the Year 2030======
-In the course of some recent work I developed the impression that 2048 RSA was quite secure. Canada(([[https://www.cyber.gc.ca/en/guidance/cryptographic-algorithms-unclassified-protected-protected-b-information-itsp40111|Cryptographic algorithms for UNCLASSIFIED, PROTECTED A, and PROTECTED B Information - ITSP.40.111]])) (my country of residence) and others
+//Update: NIST released a draft that modified their recommendations (Oct 2024)(([[https://csrc.nist.gov/pubs/sp/800/131/a/r3/ipd|Transitioning the Use of Cryptographic Algorithms and Key Lengths, Rev 3]])). RSA 2048 is to be only  considered "deprecated" after 2030. The draft states://
+>//Currently, a 112-bit security strength for the classical digital signature and key-establishment algorithms does not appear to be in imminent danger of becoming insecure in the near future, so this approach should allow an orderly transition to quantum-resistant algorithms without unnecessary effort for the cryptographic community.//
+//Generally the idea seems to be that there would be no point in increasing key sizes in light of the quantum threat. Quantum computing seems to me to represent even less danger than the ideas discussed in this article but I will leave actual discussion of this very controversial topic to others.//
+In the course of some recent work I developed the impression that 2048 bit RSA was quite secure. Canada(([[https://www.cyber.gc.ca/en/guidance/cryptographic-algorithms-unclassified-protected-protected-b-information-itsp40111|Cryptographic algorithms for UNCLASSIFIED, PROTECTED A, and PROTECTED B Information - ITSP.40.111]])) (my country of residence) and others
 (([[https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r5.pdf|Recommendation for Key Management]] (USA), [[https://www.ssi.gouv.fr/uploads/2021/03/anssi-guide-mecanismes_crypto-2.04.pdf|Règles et recommandations concernant le choix et le dimensionnement des mécanismes cryptographiques]] (France) )) are currently strongly suggesting that 2048 bit RSA should be considered potentially insecure after the year 2030 and that the minimum length considered secure should be then be 3072 bits. That is only 7 years from now (2023).
 =====Where did the 2030 cutoff come from?=====
-I am reasonably certain that the ideas here came from an influential paper released in 2004 by Arjen K. Lenstra((https://infoscience.epfl.ch/record/164539/files/NPDF-32.pdf|Key Lengths: Contribution to The Handbook of Information Security)) that showed this year in a table. Here is a simplified version of the table:
+I am reasonably certain that the ideas here came from an influential paper released in 2004 by Arjen K. Lenstra(([[https://infoscience.epfl.ch/record/164539/files/NPDF-32.pdf|Key Lengths: Contribution to The Handbook of Information Security]])) that showed this year in a table. Here is a simplified version of the table:
 ^ Modulus Bit Length ^ Conservative Year ^ Optimistic Year ^
@@ Line 98: / Line 104: @@
 =====Where Are We Now?=====
-How do things look for breaking 2014 bit RSA right now in 2023?
+How do things look for breaking 2048 bit RSA right now in 2023?
 The best available algorithm known, usable with the most powerful computers we know how to build, is NFS. So we would use the NFS algorithm.
@@ Line 106: / Line 112: @@
 Bitcoin mining is a process that makes money for the entity running the mining system. This financial incentive has created a situation where the mining network has expanded to what might seem a ridiculous extent. The incentive is very sensitive to the cost of electricity. As a result the mining systems are designed to be as power efficient as humanly possible. The end of Dennard scaling is very relevant here. The troublesome heat starts as expensive electricity. Even with this desperate quest for energy efficiency, it is estimated that the Bitcoin mining network consumed 1/200th (0.5%) of all the electricity generated on the entire planet(([[https://ccaf.io/cbnsi/cbeci|Cambridge Bitcoin Electricity Consumption Index]], 136.19 TWh annually May 10/2021 | [[https://www.eia.gov/international/data/world/electricity/electricity-consumption?pd=2|U.S. Energy Information Administration]], 25343 TWh annually 2021 ))in 2021. This makes the network a good upper limit on what might be done in secret. If some over funded national signals intelligence agency built that much processing power we would be able to tell just by checking their power bill. Electricity consumption at the level of an entire country would be impossible to hide.
-Let's imagine that we could magically repurpose the processing power of the entire Bitcoin mining network for breaking a single 2048 bit RSA key. This will require us to relate what the network is currently doing to the NFS algorithm. I will use the "apples to apples" relation developed in RFC3766(([[https://www.ietf.org/rfc/rfc3766.txt|Determining RFC3766: Strengths For Public Keys Used For Exchanging Symmetric Keys]], 0.02*e^( 1.92*cubrt( ln(n)*( ln( ln(n) ) )^2 ) )/300)). It's based on the situation in 2004 but there does not seem to be a better one available. The operations that the Bitcoin network performs would seem to take roughly the same amount of processing as the operations used as a reference in RFC3766((The Bitcoin network is performing half the work per operation so ignoring the difference is conservative. Assumptions: [[https://cryptopp.com/benchmarks.html|Crypto++ 5.6.0 Benchmarks]], Bitcoin: 2 SHA-256, 16 bytes/SHA-256, 15.8 cycles/byte, 3DES: 8 bytes/3DES, 134.5 cycles/byte.)). By RFC3766, breaking 2048 bit RSA would require 9.01×10<sup>30</sup> cryptographic operations. The Bitcoin mining network recently achieved a rate of 1.24×10<sup>28</sup> operations/year(([[https://www.blockchain.com/explorer/charts/hash-rate|Blockchain.com / Total Hash Rate]], 3.94×10<sup>20</sup> Bitcoin hashes/second on Jun 12/2023)).
+Let's imagine that we could magically repurpose the processing power of the entire Bitcoin mining network for breaking a single 2048 bit RSA key. This will require us to relate what the network is currently doing to the NFS algorithm. I will use the "apples to apples" relation developed in RFC3766(([[https://www.ietf.org/rfc/rfc3766.txt|RFC3766: Determining Strengths For Public Keys Used For Exchanging Symmetric Keys]], 0.02*e^( 1.92*cubrt( ln(n)*( ln( ln(n) ) )^2 ) )/300)). It's based on the situation in 2004 but there does not seem to be a better one available. The operations that the Bitcoin network performs would seem to take roughly the same amount of processing as the operations used as a reference in RFC3766((The Bitcoin network is performing half the work per operation so ignoring the difference is conservative. Assumptions: [[https://cryptopp.com/benchmarks.html|Crypto++ 5.6.0 Benchmarks]], Bitcoin: 2 SHA-256, 16 bytes/SHA-256, 15.8 cycles/byte, 3DES: 8 bytes/3DES, 134.5 cycles/byte.)). By RFC3766, breaking 2048 bit RSA would require 9.01×10<sup>30</sup> cryptographic operations. The Bitcoin mining network recently achieved a rate of 1.24×10<sup>28</sup> operations/year(([[https://www.blockchain.com/explorer/charts/hash-rate|Blockchain.com / Total Hash Rate]], 3.94×10<sup>20</sup> Bitcoin hashes/second on Jun 12/2023)).
 So using the power of the largest amount of computing ever dedicated to breaking cryptographic operations in history, it would take  9.01×10<sup>30</sup>/1.24×10<sup>28</sup> years to break one RSA key. That works out to 727 years. If we could magically create enough physical hardware to break a RSA key in a year then we would need to come up with 727/200 or 3.6 times the amount of electricity currently generated on the planet to run that hardware.
@@ Line 166: / Line 172: @@
 Some examples of symmetric encryption schemes are: [[wp>Advanced_Encryption_Standard|AES]], [[wp>Salsa20#ChaCha_variant|ChaCha20]] and [[wp>Camellia_(cipher)|Camellia]].
-One extra key bit doubles the difficulty here. That's 128-112=16 difficulty doublings over the 11 year period. So an implicit assumption that the capability available for breaking elliptic curves will double every 11*12/16=8.25 months. That's a bit faster than the 9 month double exponential assumption that in turn comes from the assumption that available processing power and algorithmic capability are each doubling every 18 months. We know that that is not true for processing power.
+One extra key bit doubles the difficulty here. That's 128-112=16 difficulty doublings over the 11 year period. So an implicit assumption that the capability available for breaking symmetric encryption will double every 11*12/16=8.25 months. That's a bit faster than the 9 month double exponential assumption that in turn comes from the assumption that available processing power and algorithmic capability are each doubling every 18 months. We know that that is not true for processing power.
 The idea that the algorithmic capability against symmetric encryption might be doubling every 18 months is fairly surprising. A regular increase here is not something that is normally assumed. Perhaps there was some sort of "debt" with respect to key length that we are making up for in this time period. It might be good to apply the Bitcoin thought experiment as previously seen in this article as a sort of sanity check.
@@ Line 173: / Line 179: @@
 It does not seem reasonable to increase minimum symmetric encryption key size past 112 bits after 2030.
+[[em:index|Encrypted Messaging index]]\\
+[[:|Home]]