Crypto-apocalypse soon? Chinese researchers find a potential quantum attack on classical encryption

Chinese researchers claim they have found a way to use D-Wave's quantum annealing systems to develop a promising attack on classical encryption. Outlined in a paper [PDF] titled "Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage", published in the late September edition of Chinese Journal of …

[Roland 2]

What about cryptographic hashes in crypto-currencies

If this can be used to solve a 2048 bit RSA public key, what are the implications for the safety of SHA-256 used for bitcoin?

Would that push the value of Bored Ape NFTs below the Plank constant?

[Anonymous Coward]

Re: What about cryptographic hashes in crypto-currencies

I've asked this a few times to crypto "SME" (lol) audiences, and it's like the emperors new clothes, they just want to ignore it. It's literally hands over ears and "blah blah blah". No confirmation, no denial.

I wish I could help you and answer, but I'm still clueless :D

[Anonymous Coward]

Re: What about cryptographic hashes in crypto-currencies

I searched for "is sha-256 quantum resistant?" in Google Scholar and got this link among the results:

Stewart I., Ilie D., Zamyatin A., Werner S., Torshizi M. F. and Knottenbelt W. J. 2018. "Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack", R. Soc. Open Sci.5180410, http://doi.org/10.1098/rsos.180410

Abstract

Quantum computers are expected to have a dramatic impact on numerous fields due to their anticipated ability to solve classes of mathematical problems much more efficiently than their classical counterparts. This particularly applies to domains involving integer factorization and discrete logarithms, such as public key cryptography. In this paper, we consider the threats a quantum-capable adversary could impose on Bitcoin, which currently uses the Elliptic Curve Digital Signature Algorithm (ECDSA) to sign transactions. We then propose a simple but slow commit–delay–reveal protocol, which allows users to securely move their funds from old (non-quantum-resistant) outputs to those adhering to a quantum-resistant digital signature scheme. The transition protocol functions even if ECDSA has already been compromised. While our scheme requires modifications to the Bitcoin protocol, these can be implemented as a soft fork.

See whether this answers your questions.

[Bebu]

Re: What about cryptographic hashes in crypto-currencies

My reading of quoted claims in this Vulture article their current approach is confined to AES (symmetric key.)

Considering the grant seeking behaviour typical of academics in their publish or perish ecosystem, it is arguable whether such ephemeral claims that their approach can be used against other symmetric systems and public (asymmetric) key systems actually carry much weight or conviction.

Time will tell. ;)

Still if you *really* need to keep stuff secret for a lot more than twenty years you probably needed to deal with this twenty years ago. ;)

[Anonymous Coward]

Re: What about cryptographic hashes in crypto-currencies

It is about "Public key", not symmetric key algorithms like AES:

"Outlined in a paper [PDF] titled "Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage", published in the late September edition of Chinese Journal of Computers, the researchers assert that D-Wave’s machines can optimize problem-solving in ways that make it possible to devise an attack on public key cryptography."

[FrogsAndChips]

Re: Time will tell

Further research is necessary. Please find attached my £2,000,000 grant application.

[Yet Another Anonymous coward]

Re: Time will tell

>Further research is necessary. Please find attached my £2,000,000 grant application.

Damn commies, funding fundamental scientific research is unfair

[DS999]

The risk of quantum computers

For something like bitcoin is that the algorithm it uses is fixed. It can't use more bits in its existing algorithm, or switch to an algorithm that's more resistant.

An even bigger issue is that there is significant financial incentive to being the first to break bitcoin. Obviously its value becomes zero when that first break is known, but if someone would develop that ability but rather than publishing papers about it put it to use, they could steal billions of dollars before the bitcoin community started to figure out what was happening.

The trick is you have to develop this capability in secret. If word gets out that someone is close, the value will plummet as everyone runs for the hills so instead of stealing billions you'd only be able to steal millions.

[Jimmy2Cows]

Something's fishy...

Surprised the Chinese government would allow this to be published so openly, since, if real, it would give them a huge asymmetrical advantage over the rest of the world.

Unless the true goal is to spread some fear around the world's intelligence agencies.

[O'Reg Inalsin]

Re: Something's fishy...

Research, and maybe even more so research in China, is cut throat. There is a constant stream of "exaggeration" and backlash to that over "exaggeration". The "new angle" part might be true, but that's still far from being a threat to encryption. Not giving all the details under color of "security & secrecy", keeps it from being subjected to world review which would find the weaknesses in the claim.

[Anonymous Coward]

Assumption Alert!!

Quote: "...quantum computers will one day possess the power to easily decrypt data enciphered with today’s tech..."

I'm sure that this quote refers to the usual alphabet soup: AES, PGP, samba20, chacha20, etc.

It may also refer to key management: 25519 and so on.

But what about more limited approaches, those which simply keep messaging private:

- one time pads?

- dictionary ciphers?

- users of multiple passes through any (or all) of the above?

"Easily"??? The quote sounds like misdirection to me.

[Anonymous Coward]

Re: Assumption Alert!!

I was thinking in the same direction, though "quantum computers" aren't necessarily needed. Look at the encryption used 30 years ago. Modern machines can break it pretty easily. Today's encryption is likely to be easily broken using whatever tech we have at hand in 30 years.

[Anonymous Coward]

Re: Assumption Alert!!

Dictionary ciphers are not effective and only appear in B grade films.

[Anonymous Coward]

Another Assumption Alert!!!

No mention of a fact about messages:

- The value of any message declines sharply with time!

So......how long will quantum computers take? If it's longer than a day or so, the message will be mostly worthless!!

[Anonymous Coward]

Yet Another Assumption Alert!!!!!

....and then there's the fact that the snoops have to sort through BILLIONS of messages!!!

Which messages need the attention of the local quantum computer?? Guess.....but who knows??

So....that fake TOR gateway is spewing out ONLY millions of messages!!!

Love that Fort Meade (or is it GCHQ?) sponsors all this misdirection!!

[Anonymous Coward]

Value For Money???

"...Fort Meade (or is it GCHQ?)...."

Yup.....your taxpayer dollar (or pound) hard at work......

[F Seiler]

Not an expert, but this is interesting in that so far the quantum threat to cryptography seemed largely confined to asymmetric systems. Now this is explicitly about substitution boxes, as used e.g. in AES, *but* this is explicitly about the gift-64/128, rectangle, and present algorithms. All 3 are lightweight algorithms, which seems to mean how can we get some security out of as few jules of energy used and as low hardware complexity as possible.

Im not saying it has no relevance to AES at all, but no results for AES is mentioned in the article, and i have to assume the researchers probably do not yet know what it could mean either. Maybe it shaves a bit or two off at some point, but if they found a direct way to shave off a large number of bits off AES, or even actually reduce the problem complexity, either this would have landed with very explicit claims towards AES and a huge bang, or they would have been stuck into a reaseach cave in a military faciliy before the paper even concluded its review phase.

[F Seiler]

Postscript: this comment was based on the article here and what the linked south china morning post article writes. I cannot read Chinese, but from the English abstract, cited references at the end, abbreviations and formulas in the text of the linked paper it seems to be about application of global minimization algorithms to searching for prime factors. Not sure how the scmp article and the paper are related.

[Bear]

Sound and fury signifying nothing

Putting the paper through translation, there are a lot of untested assumptions in the paper.

It appears to be an attempt to conduct some sort of quantum Linear Cryptanalysis in the style of Kasia Nyberg. It may have had some success on a small block size, but it will not really scale up to full size ciphers.

It's an interesting idea and presents the first real quantum cryptanalysis that isn't simply factoring large integers.