Steal Now, Reveal Never: The Quiet Arrival of Quantum Attacks

Transcript

[music] Yeah. Hello everybody. My name is Shankra. I'm the chief research officer at Veradise. And today I would like to talk about the threats that quantum computers pose to the Ethereum ecosystem. Um sorry. Uh so when I refer to the Ethereum ecosystem I'm referring to the following technology stack consisting of broadly of four layers. Uh so we have the application layer, L2s and rollups, data availability and consensus. And so in this talk I'll talk about which layers are vulnerable to a quantum adversary and what those attacks may

look like. Oh sorry. uh but before doing so let me briefly go over some quantum computing terminology uh for those who are unfamiliar with it. So a quantum computer uses cubits instead of bits. So a classical bit is either zero or one but a cubit can be in a superp position of 0 and one. And it's only when you actually measure a cubit that you get a definite result uh with some probability. Since quantum measurements are inherently probabilistic, quantum algorithms exploit a property called interference to make it so that incorrect answers cancel out and we get the right answer with very high probability.

So when people talk about cubits, they could be referring to two different things. Uh first are what are called logical cubits which are these idealized error-free cubits that can reliably maintain their state throughout a computation. And when we talk about how many cubits an algorithm requires, we're generally generally referring to logical cubits. So if you heard somebody say ECC can be broken with 1200 cubits. They're talking about logical cubits. However, uh we don't know how to build these logical cubits directly. So the physical cubits we have are noisy. Small environmental disturbances can cause bit flips or phase errors. And these errors accumulate making longunning

computations unreliable. And so the solution to this is something called quantum error correction where we encode a logical bit across many physical cubits continuously detecting and correcting for these errors. So while algorithms are typically described in terms of uh logical cubits um I'll be using physical cubit counts throughout the talk since those reflect the actual hardware requirements. So what are quantum computers actually good at? Uh so they're not faster at everything. Uh but one problem they're remarkably good at is called quantum period finding. So given a repeating mathematical pattern, determine how

often it repeats. And um Shor's algorithm is quite good at solving this problem efficiently. And the reason this is important is that u both prime factorization and discrete log reduce to uh period finding and um our the security of a lot of our cryptography depends on these being hard problems to solve. So what cryptographic schemes are actually vulnerable to quantum computers. So Shor's algorithm makes factoring efficient breaking RSA. It also makes the discrete log problem efficient to solve both in traditional finite fields as well as on elliptic curves. And so this will break defy homeman key exchanges along with widely

used cryptographic schemes like ECDSA BLS signatures and KCG commitments. And now on the other hand uh there are still some uh problems that appear hard for even quantum computers. These are usually hashbased schemed um and uh uh schemes based on lattises. Uh to the best of our knowledge uh those are still resistant to quantum attacks. But the problem for us is that a lot of Ethereum's cryptography lies squarely in the left column.

And if we go to the our technology stack, it turns out that every layer uses ECC. So on the application layer transactions are signed using ECDSA. Uh [snorts] a number of rollups use pairing based snarks. Um now pure dash the data native data availability um protocol uses KCG commitments and then our consensus layer uses BLS signatures. And so I'm going to call the day that the quantum computer is able to break ECC Qday. So in particular, it's the day when any quantum computer can derive the private key from an elliptic curve public key. And we don't really know

when that day is. We have some estimates, but they're really just guesses at this point. Um, but we can kind of visualize the race towards Qday as happening from two directions. Uh, in particular, we can kind of keep improving Shor's algorithm, reducing the number of cubits to break ECC along with the time needed to break it. Um and we but we can also go on the hardware side and keep building more and more powerful quantum computers with more cubits and improved error correction. And so you can think of Qday as being the day when these two lines meet. And so it's worth looking at uh what the progress has been. Um so

uh in 2019 at least on the hardware side I think Google's sycamore had about between 10 and 100 cubits and now uh 6 years after that Caltech a team at Caltech built a quantum computer with about 6100 cubits so almost two orders of magnitude more and then um I'm sure you guys have heard of the improvements on the algorithm side. So about in 2022, the best estimates were that we needed about 10 million cubits for an attack that would take about a day. Um but this past year, Google published a paper estimating that an attack would require fewer than 500,000 cubits and could run in um 10 minutes.

Now uh to to be clear this graph is in uh log scale. So there's still a non-trivial gap between the cubits required by our best algorithms and the hardware that we built. Um but I think it's important to know that these two lines are converging and we should be wary about that. And even though you should also know that even though there is a gap um it's technically possible that we are too late. Um so to see why there's a simple formula called Moscow's inequality that captures this well. So let Z be the time until Q day and let X be the time it takes to migrate our cryptography and let Y be the length um of time for protected information must remain

secret. Uh so Moscow's inequality says that if X + Y is greater than Z then you're already too late. Stuff is already exposed. Now for Ethereum I would say that uh Y is effectively zero because onchain data and public t's are generally public so there's nothing really to harvest. Uh so the main concern here is migration time. Uh so the uh NIS postquantum uh standard security standard uh says that migrations have taken about 10 years in practice. Uh that's not how long it might take for Ethereum. I think their road map says they want to get it done by 2028.

Um, but the thing is that I don't know exactly how long it's going to take, but the important thing is that every layer of the stack has to change. So [snorts] maybe let's go through them and see what needs to change and what kind of threat uh attacks we could see if we don't change it fast enough. So let's start with the application layer. Uh so in the application layer uh account transactions are signed using ECDSA. Um and before your first transaction, your public key is actually not visible.

Uh your address is like your hash of your public key. Uh but after your first transaction, your public key is actually visible on chain and forever exposed. And so the attack scenario here is quite simple. Um since uh the public keys are already recorded on chain, it's easy for an attacker to kind of recover them. So they can scan the blockchain for exposed public keys, take those public keys, use a quantum computer running shores to drive the private key, and then steal funds. And I think the interesting thing here is how they steal the funds. Um, I think it's plausible that the first types of attacks we could see are kind of these silent mo um kind of uh silent

transactions where funds are quietly drained from accounts that have that are generally dormant and have a lot of ETH. Um, but I think that's still uh TBD. But how much ETH is actually at risk? Uh so if you look at the top 1,00 accounts in terms of ETH with exposed public keys, they have a combined 20.5 million ETH. And our best quantum algorithms could recover those uh those keys in approximately in in several days. Um and then not just uh account keys, but admin keys are another risk. So for many contracts, admin accounts could mint or burn assets. And it's estimated that about $200 billion dollars in stable

coins and real world assets could be at risk. [snorts] Um, okay. So, next is going to be roll-ups. So, I'm going to focus on ZK roll-ups here, particularly those that use pairing based snarks. Um, so at a high level, the way a ZK rollup works is that you have this off-chain sequencer that executes a batch of transactions for the L2 and then what it will do is submit a zero knowledge proof of the state transition uh along with an updated state route for the L2 chain. Then a verifier on the L1 will check the proof, record the new state route and then the rollup's bridge um will accept that new state route and then unlock funds for people trying to

withdraw. Um so the bridge the key point here is the bridge trusts whatever the verifier accepts and this verifier um checks a pairing based snark which relies on elliptic curves and so it's vulnerable to a quantum attack. And so here's what an attack scenario might look like. Um so for pairing based snarks, uh the uh one attack scenario is that a quantum adversary runs Shor's algorithm to recover uh the secret behind a verifier's public setup parameters. Um so that would let them generate bogus proofs that still verify.

And so in particular, they can forge a proof for a straight state transition that gives them all of the bridges funds. Um and so the L1 verifier will accept the proof and the new state route will get recorded and then the bridge could pay will pay out everything to the attacker if they try to withdraw. Um I think a safe path to the best of our knowledge are kind of stark based um stark based uh rollups. Uh but you but everything has to be um a stark. So many starks do um a kind of final uh wrap like recursion step with uh groth 16 or pairing based snark.

Okay. The third layer is the data availability um which is used heavily by rollups. And so with the Fusaka upgrade, Ethereum added pure um and the key idea here with Purdas is that nodes don't need to download an entire blob to know that it's available. uh what they do is they just check a few random chunks instead and um and [snorts] what makes this all work is a combination of data redundancy and KCG polinomial commitments and um as I mentioned before the primary users are both are rollups both optimistic and zk and so here's how it works at a high level so a blob is going to be a chunk of data say D1 through D4 and so whoever

posts it computes a KCG commitment D for the whole blob and we can think of C as a fingerprint and the block will only store C. [snorts] So then the block gets extended with redundant chunks so that any half of the chunks is enough to rebuild the whole thing. And with KCG the KCG commitment scheme each chunk comes with a small proof which says that this chunk I of the blob this is chunk I of the blob whose commitment is C and anyone can check it against C.

And so a node just asks for a few random chunks and checks the proof. Uh to make the blob unreoverable, an attacker would have to withhold more than half the chunks and then random samples uh would catch them almost immediately. The catch here is that the KZG security also relies on this secret number tow staying unreoverable. So on for pure dash towel came out of a ceremony with only a with 140,000 contributors and so as long as one of them was honest nobody should know it but uh a quantum computer um can derive towo directly from the public parameters and so once you do once an adversary does that they would they could forge proofs uh on their

laptops and so what can attacker do with tow so what they can do is post a blob whose chunks all come with fake proofs such that when a node samples any given chunk that proof uh verifies. But the idea here is that um the commitment itself should be derable from the blob. So if an honest node collects the chunks and rebuilds the commitments, it will actually get something different. So an attacker can post a blob that doesn't actually match its commitment but still passes node verification.

And this matters the most I think for optimistic roll-ups because they depend on that data to catch fraud. And so here's one line of attack that might be plausible. Uh so an optimistic rollup assumes a batch is valid unless someone disputes it during a challenge period. So in the first step maybe an attacker recovers the KZG setup secret with their quantum computer and then they also take control of the rollups batch poster by cracking their signing key. uh this is uh exposed because they sign every batch. So then posing as the rollup uh the attacker posts a blob commitment but withholds the actual transaction data like and hands out forged um uh pieces and proofs instead. And as I mentioned

before this will get accepted by the nodes even though nobody can reconstruct the real data. They then propose a new state route and post a bond. Um, but the problem is that uh an honest challenger will try to reconstruct this batch and prove that the state route is wrong, but the data isn't actually there. And so nobody can build a fraud proof. And so um if this remains unchallenged then um when the window closes after a week the attacker will withdraw could withdraw um all the bridges funds if they have in their state route that all the bridges funds go to them.

Um, but I think, you know, I don't know if this necessarily would happen, uh, because I think, uh, optimistic roll-ups tend to have security councils that that watch for this, uh, that would watch for this and and freeze the rollup, but you might end up seeing some sort of ransom type attack as a result. Um, and then also with security councils, you have keys, and those are things that an attacker could attack. All right, so let's look at the last layer which is the consensus and the foundation of the stack.

So Ethereum has uh roughly a million validators and each one signs their votes with a BLS key and the BLS uh lets the chain combine thousands of those signatures into one which is what makes everything scale. But BLS is built on elliptic curves and so a sufficiently powerful quantum computer could recover the validator's signing key from their public key um and every validator's public keys on chain. So the real question here is what an attacker could do with the with a validator signing key and how many of them would they need to launch a serious attack.

So what an attacker can do depends on how much voting stake they control. So above one-third uh they can stop the network from finalizing. Uh but Ethereum does have a safety valve for this called uh the inactivity leak I believe where validators that stop voting slowly lose stake until the honest ones are back above 2/3. But with stolen uh stolen keys the stake being compromised is actually the validators and so the attackers can keep cracking the remaining validators keys. Above half a stake, above half the stake, the attackers control what chain everybody builds on. They can reorganize recent blocks and censored transactions.

And then um at 2/3, they can finalize whatever chain they want on their own. And the pro protocol has no way to undo it. At that point, the only way out is some kind of uh community coordinating a hard f a hard fork to recover the honest chain. So how realistic is this? I think of everything we've looked at, I believe consensus is probably the hardest target um because like breaking pure dash just requires one quantum computation to recover the secrets and then I think cracking only a few thousand uh accounts or admin keys are required to really do real damage to the application layer. Um, but I think taking over consensus would mean cracking hundreds and thousands of keys,

possibly one at a time. And so if it takes minutes uh to break a key, it might take several several months for an attacker to reach 2/3 of the stake. Um, but I think the one issue though is that uh validator keys don't really change. So a patient attacker could collect them quietly for let's say a year and then strike all at once. uh so I think the number of keys does raise the cost but it doesn't uh protect anybody on its own and I think with the consolidation that number is also shrinking.

Um it's also worth noting if you guys attended Justin Drake's uh keynote talk um the there are more new algorithms that are able to uh where it's projected that uh cracking an elliptic curve private public key could be noticeably faster than minutes. So what I just said might be completely false. Um so that's the bad news. But the good news is that postquantum alternatives exist. So NIST has just standardized uh latisbased key exchanges signatures um alongside approved hashbased signature schemes and its transition guidance targets phasing out vulnerable public key algorithms after 2030 uh completely deprecated by 2035. And Ethereum

researchers are exploring changes at every level. uh from account signatures to blob commitments, rollups and validator signatures. They are aware of all these problems. But the hard part is just making sure we safely migrate the whole whole ecosystem with relatively new cryptography that we're confident is correct uh and efficient. Um, so if you want to go deeper into anything I've talked about, um, and you want to learn more about the migration plan, uh, here are some, uh, QR codes for for links that I found pretty useful. So, Ethereum's postquantum migration plan, NIST's uh, postquantum cryptography standards, and then there's a great paper by Google uh, with Justin Drake kind of talking where I got a lot

of the numbers uh, from this talk. Uh so we've started at Veradise we've started a postquantum uh dedicated postquantum team. So if you have concerns about migrating to postquantum cryptography we can help you um find uh where you're exposed and migrate safely. Uh and yeah if you're interested in learning more about that please scan the QR code or come talk to me after the talk. All right. Thank you. >> Awesome. Awesome. That was a really great talk. Um, anything postquantum gets me really excited. Honestly, this might be a slightly controversial question about uh cryptography. It's my question. Uh, what do you think is more conservative of a like postquantum

digital signature scheme? Hashbased or lattisbased or something else? >> Um, I think Ethereum is generally uh bullish on the uh hashbased schemes. I think generally uh with hashbased schemes there isn't quite a lot of structure and so um generally it's thought that there's less surface area for attack. Um I think also there's like a sweet spot that we need to get in uh be in where with just pure uh I think hashbased schemes I think aggregation gets very I think there's a lot of performance concerns um with that. So I think finding a good sweet spot where we can use hashbased schemes and do so efficiently would be um is probably the the way to go. But yeah there's lot of

space schemes have been examined for decades. So um those are also worth exploring. >> Um another question it's slightly simple question but um what will oh yeah it's actually not a simple question. >> What will happen to privacy protocols that use elliptic curves in the postquantum era? >> Oh that's a great question. Uh I think there's a real concern there. I I mentioned earlier in the slide about on Ethereum the when I was talking about Moscow's inequality Y is equal to zero. Well that's not actually true for privacy solutions on top of Ethereum.

Um, I think that's a very non-trivial question because in principle they should also move to postquantum but now you have to encode that postquantum cryptography probably inside of a ZK circuit and do so efficiently. Uh, that's like a non-trivial technical challenge. Um, so I think people are having to invest a lot into kind of improving the ZK technology to support these postquantum embedded postquantum schemes. I think it will I think they will eventually have to migrate to postquantum. Um but I don't know when when that's going to be feasible.

>> Um another question is who would have access to a quantum computer to break elliptic curve cryptography to steal ETH? Would it be hackers or a nation state? >> Um well I I guess can it be both? I mean a nation state could be a hacker I guess, right? So I mean with like the Binance hack I think it's like if if somehow North Korea manages to get its hands on a sufficiently powerful quantum computer I mean that's very scary. So >> another question is you say migration and performance are the main challenges which should Ethereum prioritize first postquantum accounts via EIP7932 or hashbased validator signatures and why?

Um I think the hashbased validator signatures are pretty is a fairly challenging problem. Um I think one um one thing is at least for the postquantum accounts uh I I believe there as I mentioned earlier um with before you like initially your private public key is actually hidden behind your address. So one simple mitigation at least for accounts is just migrate your ETH to a fresh account. Um so that that would at least keep it somewhat secure. I think the hashbased validator signatures getting that correct and um performant is definitely a huge challenge.

>> Another question is you say migration performance are the main challenges. Oh sorry I'm reading that again. Um oh yeah okay okay. How do security teams distinguish a subtle quantum key compromise from routine insider threats or software bugs before public panic sets in? >> Distinguish a >> So yeah, like how would you tell I guess like if it's a key compromise or just like a quantum computer? Like how would you tell if it's maybe like a >> Oh yeah, I think yeah that's a good question. I mean, I think with key compromises, um, you would see typically like one a small group of people that are affected. I

think if we get a quantum computer that's actually able to drive a private key from a public key efficiently, um, we could see several accounts being targeted at once across different communities and groups. Um, so I think I think I think that might be one way we could sort of tell um, especially if we see a large scale attack. And uh last question like what what year or what timeline when do you think Qday is actually coming? Like should we be panicking right now or like is it 5 years out 10 years out? Some people say like cloud for has one estimate, Ethereum has a different estimate. What is your estimate?

>> Uh I think it would be kind of irresponsible to like really give an estimate. Um I don't know. I think um we do see a rapid amount of money being put into building quantum computers. uh we see AI being used to optimize our quantum algorithms. It's really hard to predict, but I think it's important that migration takes time and so we should just start as soon as possible and try to get all our elliptic curve cryptography migrated to postquantum schemes. [music]