pull down to refresh

649 sats \ 4 comments \ @0xbitcoiner 21 Apr security math

A stubborn misconception is hampering the already hard work of quantum readiness.

With growing focus on the existential threat quantum computing poses to some of the most crucial and widely used forms of encryption, cryptography engineer Filippo Valsorda wants to make one thing absolutely clear: Contrary to popular mythology that refuses to die, AES 128 is perfectly fine in a post-quantum world.

AES 128 is the most widely used variety of the Advanced Encryption Standard, a block cipher suite formally adopted by NIST in 2001. While the specification allows 192- and 256-bit key sizes, AES 128 was widely considered to be the preferred one because it meets the sweet spot between computational resources required to use it and the security it offers. With no known vulnerabilities in its 30-year history, a brute-force attack is the only known way to break it. With 2¹²⁸ or 3.4 x 10³⁸ possible key combinations, such an attack would take about 9 billion years using the entire Bitcoin mining resources as of 2026.
It boils down to parallelizationIt boils down to parallelization
Over the past decade, something interesting happened to all that public confidence. Amateur cryptographers and mathematicians twisted a series of equations known as Grover’s algorithm to declare the death of AES 128 once a cryptographically relevant quantum computer (CRQC) came into being. They said a CRQC would halve the effective strength to just 2⁶⁴, a small enough supply that—if true—would allow the same Bitcoin mining resources to brute force it in less than a second (the comparison is purely for illustration purposes; a CRQC almost certainly couldn’t run clusters of Bitcoin ASICs and more importantly couldn’t parallelize the workload as the amateurs assume).

...read more qat arstechnica.com

view all related items

226 sats \ 0 replies \ @nichro 21 Apr

Imagine it with small numbers, let’s say there are 256 possible combinations to a lock, A normal attack would take 256 tries. You decide it’s too long, so you get three friends and you each do 64 tries. “That’s the classical parallelization. With Grover you could in theory do √256)=16 tries in a row, but if that’s still too long and you again look for help from three friends. Each has to do √256/4)=8 tries.

So in total you do 8*4=32 tries, which is more than the 16 you would have done alone! Asking for help to parallelize the attack made the attack slower overall.

I love math.

no matter what happens with quantum, all I'm rooting for in the end is for cryptography and the power of math to still exist and empower freedom as it does now if not better.

"It isn’t obvious that the world had to work this way. But somehow the universe smiles on encryption." as Assange once said

215 sats \ 2 replies \ @siggy47 21 Apr

What does this mean, if true, about bitcoin addresses that some see as vulnerable? If anything?

184 sats \ 0 replies \ @SimpleStacker 21 Apr

The article is saying that the quantum threat to classical cryptographic schemes is overstated.

This misunderstanding stems from a short-hand calculation people use for quantum speed up. The short-hand calculation is to simply take the square-root of the keyspace to get how long it takes a quantum computer to find the key. So for example, if a classical computer would take at most N operations, a quantum computer would take at most √N operations.

So, if your original keyspace is 2^128, Grover's algorithm sees it as a 2^64 keyspace, and 2^64 seems pretty crackable by classical machines.

The article is saying that this claim, "pretty crackable by classical machines", hides an assumption, which is the parallelizability of the search strategy. Our classical techniques for searching over a 2^64 keyspace relies a lot on parallelization, but quantum computers can't be parallelized in a similar way. Thus, saying 2^64 is crackable by classical techniques relying on parallelization doesn't mean 2^64 is crackable by non-parallelizable quantum methods.

Big caveatBig caveat

As to how it applies to Bitcoin, here's my understanding.

It doesn't for addresses with an exposed public key. Bitcoin's ECC can be cracked by Shor's algorithm, which is different from what they're talking about in this article (Grover's algorithm). Shor's algorithm is actually very efficient for ECC, so Bitcoin addresses with an exposed public key are super vulnerable still (assuming a large enough quantum computer).
It does apply for addresses without an exposed public key, Grover's algorithm is needed to go from the hash of the public key to the public key itself. So that part of the cracking is still relatively hard for a quantum computer, due to what was discussed in the article.

40 sats \ 0 replies \ @0xbitcoiner OP 21 Apr

From what I've been reading, the problem with Bitcoin addresses is that reusing them makes them more vulnerable cryptographically. I think legacy addresses are vulnerable too.