Are your fraud protections obsolete before the quantum era even begins? I previously wrote about algorithms that purport to protect against quantum-powered fraud. See my October post “Is the Quantum Security Threat Solved Before It Arrives? Probably Not.”
Let’s take a step back from Module-Lattice-Based Digital Signature Standards (NIST FIPS 204) and see what quantum-infused fraudsters can do to bypass your security protections. Your “practically unbreakable” security system today may be wide open in 10 years…or 5 years.
Shor’s Algorithm
To understand how fraud can occur, you need to understand (Peter) Shor’s Factoring Algorithm.
According to Classiq, Shor’s Factoring Algorithm can find the prime factors of any number, including very large numbers.
“Factoring numbers with Shor’s algorithm begins with selecting a random integer smaller than the number to be factored. The classically-calculated greatest common divisor (GCD) of these two numbers, the random number and the target number, is then used to determine whether the target number has already been factored accidentally. For smaller numbers, that’s a possibility. For larger numbers, a supercomputer could be needed. And for numbers that are believed to be cryptographically secure, a quantum computer will be needed.”
So what? I appreciate that people like the late Richard Crandall were into finding prime numbers with 20th century technology, but how does that relate to whether a fraudster can drain my bank account?
Breaking RSA encryption
It definitely relates, according to the MIT Technology Review. This article was written back in 2019.
“[C]omputer scientists consider it practically impossible for a classical computer to factor numbers that are longer than 2048 bits, which is the basis of the most commonly used form of RSA encryption.
“Shor showed that a sufficiently powerful quantum computer could do this with ease, a result that sent shock waves through the security industry.
“And since then, quantum computers have been increasing in power. In 2012, physicists used a four-qubit quantum computer to factor 143. Then in 2014 they used a similar device to factor 56,153.”
The largest recent record number that I found was 261,980,999,226,229, as described in this paper. It should be noted that many of these numbers were factored by a variety of methods: using a pure Shor’s Factoring Algorithm, the maximum number factored so far is 21.
What does this mean?
So what does this mean for 2048-bit encryption? 2048 bits is equivalent to hundreds of decimal digits. I’ve found different numbers of decimal digits, but for all practical purposes I can’t calculate them anyway. Heck, I can’t calculate trillions in my head. And there’s RSA-4096 encryption, but…well, we’ll get to that.
But when quantum calculating abilities can crack algorithms, then it’s trivial to compute the number of combinations to crack an encryption…or guess a password…or generate a face.
“Brute force attacks function by calculating every possible combination of passwords. As the password’s strength increases, the amount of time to crack it increases exponentially. So, in theory, if hackers tried to brute force their way into a key with AES-128 encryption, it would take approximately 1 billion years to crack with the best hardware available today [2023].
“But what if we lived in a post-quantum computing world? How long would a brute-force attack on popular cypher technologies take?…[We’re] likely still a decade or two away from Quantum computers that can easily break many of the cypher technologies in use today….
“[I]n a recently published report from Global Risk Institute (GRI), the time to break RSA-4096, which is practically impossible to break with classical computing technology, is under three days with a theoretical 1 megaqubit computer. While we are still a long way from a 1 megaqubit computer, the resources and time required are reducing rapidly at the same time we see advancements in Quantum computing which are in development.”
Yes, even RSA-4096 is vulnerable.
Now many claim that AES encryption such as AES-256 is quantum resistant, but even AES may have been breached, if you believe the claims of Chinese researchers. (But that’s a big if.)
I have no idea how much lattice-based access control mitigates these threats, but if you go around saying that strong encryption will never be broken, you are a fool.
Bredemarket 