Researchers have created a new and potentially dangerous encryption-breaking quantum algorithm

[Jimmy2x]

In a nutshell: Researchers at China's Tsinghua University believe they have discovered a quantum-based algorithm capable of breaking today's most complex encryption standards. The team claims that the algorithm can be run using currently available quantum technologies, too. If true, the lifespan of today's encryption could be drastically reduced to nothing in a handful of years.

Tsinghua University professor Long Guili and his team claim to have developed a new, qubit-saving factorization algorithm that could spell trouble for cryptographic security standards in the not-so-distant future. The algorithm, called sublinear-resource quantum integer factorization (SQIF), claims to optimize the quantum calculation process by reducing the number of qubits required to conduct the code-breaking calculations. The work is based on an algorithm developed in 2013 by German researcher Claus Schnorr.

What does that mean to someone who isn't overly familiar with quantum computing? If successful, the algorithm would increase the chances of breaking today's strongest encryption using currently available quantum technologies, and sooner than originally expected.

Must read: We Cannot Live Without Cryptography!

Created by the National Security Agency (NSA) in 2001, SHA-256 is a cryptographic hashing function that transforms data into an encrypted string of 256 characters. The encrypted output is unreadable unless a recipient has the proper key to decrypt the message.

These decryption keys are also comprised of complex mathematical strings related to the SHA-256 hash, making an encrypted message extremely difficult to decrypt without the proper keys. For example, the time to crack an RSA-2048 bit encryption key using today's most powerful traditional computing resources is estimated around the 300-trillion-year mark.

300 trillion sounds like a nice, safe number that no one should have to worry about. That is, at least until quantum computers are brought into the equation. According to cryptography and quantum experts, a properly sized quantum computer could complete the same algorithm-breaking operation in just under eight hours. This is where Guili's equation raises the alarm bells.

If the SQIF algorithm scales and effectively reduces the quantum computing resources required to run the calculations, then the wait for quantum technology to mature enough to run the calculations could be reduced from a few decades to just a few years.

IBM's Osprey is currently the largest quantum processor in the world, weighing in at 433 qubits. The company's quantum roadmap depicts plans to pursue larger processors ranging from 1,100 qubits in 2023 to more than 4,100 qubits in 2025. By comparison, the SQIF algorithm claims to bring the practical required scale of a quantum computer down to 372 qubits.

Currently the Tsinghua team has not yet proven the ability to break the 2048-bit encryption barrier. They have, however, successfully demonstrated SQIF's feasibility by breaking a 48-bit-length encryption key with a tiny 10-qubit superconductive quantum computer. Though the breakthrough may be nothing to worry about yet, it's definitely a development that security and cryptography experts will continue to monitor.

Permalink to story.

https://www.techspot.com/news/97270-researchers-have-created-new-potentially-dangerous-encryption-breaking.html

 

[Bullwinkle M]

"If successful, the algorithm could reduce the chances of breaking today's strongest encryption"

Correction:
What you meant to say was.....

If successful, the algorithm could INCREASE the chances of breaking today's strongest encryption

Still wrong though as there is ZERO chance of any quantum algorithm of ever breaking my best encryption techniques

If successful, it could however break "your" encryption standards

 

[psycros]

"If successful, the algorithm could reduce the chances of breaking today's strongest encryption"

Correction:
What you meant to say was.....

If successful, the algorithm could INCREASE the chances of breaking today's strongest encryption

Still wrong though as there is ZERO chance of any quantum algorithm of ever breaking my best encryption techniques

If successful, it could however break "your" encryption standards

So what's your technique? Never writing anything down?

 

[Tantor]

According to KeePass, a 48 bit key is very weak.
https://keepass.info/help/kb/pw_quality_est.html

 

[Hodor]

If the Chinese do that, it will only concern big corporations and military.

But it has zero influence on us, since we're already being spied upon by all the devices that surround us. No need for the sophisticated quantum mumbo jumbo to get our secrets.

 

[bviktor]

According to KeePass, a 48 bit key is very weak.
https://keepass.info/help/kb/pw_quality_est.html

That's totally dependent on implementation. It's not as simple as "this many bits".

In this case, it's obviously only relevant to Keepass. If you actually read the article you linked, you could see that even old and new Keepass' bits differ on the same passwords.

 

[kiwigraeme]

So what's your technique? Never writing anything down?

That's irrelevant here - maybe putting if offline and hiding it .
But if it's just iterations of multiple digital devices to encrypt - unless you split them into parts and then hidden in other digital stuff - QC if strong enough could do it - even splitting it up and hiding in other files - it's possible - but the quantum bits needed would be astronomical.

The point is I suppose encryption has to be convenient and easy enough - Most people should worry about security in how you store , and the PC/phone you use, Eg FBI/Police trick people into opening phones - or scammers taking over your PC - , phone , 2FA etc - spy cameras - thermal readers , sound loggers etc

 

[VitalyT]

This all is too cryptic to me.

 

[MaestroIT]

SHA-256 is a cryptographic hashing function that transforms data into an encrypted string of 256 characters. The encrypted output is unreadable unless a recipient has the proper key to decrypt the message.

What are you saying?? SHA doesn't produce encrypted output, nor does the output has any chance of being decrypted, it is a hash function... With or without any keys (not to mention SHA256 doesn't need a key to hash a message in the first place). You are confusing with AES.

 

[Bullwinkle M]

So what's your technique? Never writing anything down?

You are exactly right

I would never write down my quantum proof encryption techniques

We have encryption to protect them

 

[Vanderlinde]

According to KeePass, a 48 bit key is very weak.
https://keepass.info/help/kb/pw_quality_est.html

It would take a avg computer a full day to crack that 48 bits key. This quantum thing with only 5+ qubits takes 8 hours. So yeah. Every 5 added kind of reduces the time required significantly. Knowing there will be 1000+ qubits available in the future it will be a peace of cake to start hammering on 256 or even 512 bits keys.

 

[HardReset]

This news is pretty much fake. Modern GPU would crack simple 48-bit encryption even faster than 8 hours.

However they still have no proof that they could make anything better than this one https://en.wikipedia.org/wiki/Grover's_algorithm that halves encryption bit strength, so 256-bit encryption could be brute forced on 2^128 calculations. That's still too much time anyway.

Also good to remember not all ciphers are equal. You can brute force any 256-bit encryption just calculating all 2^256 possibilities (2^128 with Grover algorithm) but if not brute forcing, there is quite big difference between AES-256 and Serpent-256: https://www.cl.cam.ac.uk/~rja14/serpent.html

It would take a avg computer a full day to crack that 48 bits key. This quantum thing with only 5+ qubits takes 8 hours. So yeah. Every 5 added kind of reduces the time required significantly. Knowing there will be 1000+ qubits available in the future it will be a peace of cake to start hammering on 256 or even 512 bits keys.

Like stated above, not at all. No, it won't get significantly faster no matter how much qubits are added.

 

[jfinster]

It sounds like they can break 3DES (Triple DES) with a 10 qubit machine. It’s a cool academic exercise. Also, the author seems to have conflated AES256 with SHA256. This article lacks substantive, nothing to be alarmed about.

 

[PEnnn]

" For example, the time to crack an RSA-2048 bit ...."

Which begs the question:

Are there any technological constraints to raising the 2048 bit bit encryption key to deal with this? Say, to 2048^10?? Or even more.

 

[ChipBoundary]

That's not how ANY of this works. The math has already been done on this topic. Even if every particle of matter in the entire known universe was dedicated to computing, which you couldn't do because you need some of it to power the computing, it would take over a million years to decrypt moderation or something like that.

These scare tactics are ridiculous.

 

[Vanderlinde]

Like stated above, not at all. No, it won't get significantly faster no matter how much qubits are added.

In my understanding, if you give a traditional PC vs a quantum powered one, a simple task to find the key behind the 50 doors, the tradtional one will open up door by door till it finds the key. The quantum based one however will open up all 50 doors at once. And with more qubits that kind of accelerates that task significant.

 

[HardReset]

In my understanding, if you give a traditional PC vs a quantum powered one, a simple task to find the key behind the 50 doors, the tradtional one will open up door by door till it finds the key. The quantum based one however will open up all 50 doors at once. And with more qubits that kind of accelerates that task significant.

Basically yes. However modern encryption systems are very complex and therefore even quantum computers cannot predict outcome from starting values, meaning quantum computers still cannot easily break modern encryptions. No matter how many qubits.

There are some exceptions but AES etc are not those.

 

[quadibloc]

That's not how ANY of this works. The math has already been done on this topic. Even if every particle of matter in the entire known universe was dedicated to computing, which you couldn't do because you need some of it to power the computing, it would take over a million years to decrypt moderation or something like that.

Um, no. That math is about how hard it would be to break long keys in a world without quantum computers. One quantum computer with 10 qubits behaves as though it's 1024 (ridiculously weak) computers; and a quantum computer with 500 qubits behaves like 2 to the power 500 computers. Enough qubits to have as many computers as there are particles of matter in the known universe?
Entirely possible.

 

[Vanderlinde]

Yep; quantum is capable of breaking the strongest todays encryption in matters of hours or days.

 

[Endymio]

What are you saying?? SHA doesn't produce encrypted output, nor does the output has any chance of being decrypted, it is a hash function... With or without any keys (not to mention SHA256 doesn't need a key to hash a message in the first place). You are confusing with AES.

While true, a hash function can be cracked just like an encryption algorithm: it's technically not "decrypting", but the difference is rather sterile.

Basically yes. However modern encryption systems are very complex and therefore even quantum computers cannot predict outcome from starting values, meaning quantum computers still cannot easily break modern encryptions. No matter how many qubits.

Untrue. Quantum computers don't need to "predict" the outcome; they're essentially performing a brute-force crack. For asymmetric encryption, a QC transforms the problem from exponential complexity to an n log n (or even easier) problem. For symmetric encryption like AES, a QC essentially halves the bit length (sqrt(N) complexity). That's still a hard problem ... but unfortunately many symmetric algorithms perform an (asymmetric) public-key exchange to get the symmetric key, which makes them insecure as well.

Yep; quantum is capable of breaking the strongest todays encryption in matters of hours or days.

See above. Only asymmetric encryption is that compromised. Google "Grover's algorithm" for more details.

 

[tkabou]

Oak Ridge Laboratory has computers that will decrypt AES-256 in almost real-time. Where does that leave “crypto” LOL

 

[HardReset]

Oak Ridge Laboratory has computers that will decrypt AES-256 in almost real-time. Where does that leave “crypto” LOL

Yeah right. Source?

 

[crakbaby]

The story states: "National Security Agency (NSA) in 2001, SHA-256 is a cryptographic hashing function that transforms data into an encrypted string of 256 characters"

Did you mean to say AES? The algorithm developed by Joan Daemen &Vincent Rijmen in the late 90s was adopted by NIST and NSA in 2001 as AES.

SHA256 is a hashing algorithm not capable of encryption at all, because it is deterministic, meaning same input = same output, ad infinitum. We might use, and we do everywhere, because it is good practice, to use a hashing algorithm or key stretcher or salting mechanism like PBKDF2 or BCRYPT to "encrypt" passwords, however TRUE encryption uses a KEY to encipher and decipher, and hashing doesn't use a key on its own.

Not only is hashing deterministic, it essentially destroys a copy of the data using xor and other functions within, in the process of creating a hash. There is no data in the hash to "reverse" back to the input. Crack a hash, hell yes; ophcrack, rtgen, download a set of rainbow tables, collision attacks, birthday attacks, length extension attacks, and more. But don't call hashing cryptography, 'cause determinism and lack of a key says it ain't.

 

[Endymio]

SHA256 is a hashing algorithm not capable of encryption at all, because it is deterministic, meaning same input = same output, ad infinitum.... TRUE encryption uses a KEY to encipher and decipher, and hashing doesn't use a key on its own...

Not quite. Both hashing and encryption are deterministic (given the same inputs, they always yield the same outputs). The difference is that encryption is bijective, making it invertible, whereas hashing is one-way. In crypto terms, a hash function maps an infinitely-large domain onto a fixed range: a process that is thus irreversible.

Note: there are many "true encryption" schemes that do not use a key. However, all encryption -- key or not -- requires some form of secrecy. If you have no secret key, then the algorithm itself must provide the requisite secrecy. For widely-used algorithms, this is rightly denigrated as "security through obscurity", but in the case where the encryptor can tightly control access to the algorithm, it is just as secure as keyed encryption.