Like much of Peter Gutmann’s writing this is a mixture of good points and things that are downright incorrect or at least misleading. For example, he criticises GCM for losing confidentiality when a nonce is reused. True, but ChaPoly has exactly the same issue. And although CBC+HMAC is somewhat better in that regard, it doesn’t “drop back to ECB mode”, and it still loses CPA security. HMAC is far more robust than any polynomial MAC, but the persistent idea that there is any meaningful difference in robustness between any of the traditional cipher modes under nonce/IV misuse is nonsense. If you need misuse resistance then use a mode that actually provides it, like SIV.
I mean, he hasn't nailed the reason ChaPoly is favored over GCM, and it's not a good paragraph, but he's not wrong that GCM is ill-loved by cryptography engineers, despite its ubiquity. Really though, it's just missing an important bit of the history, which is that there was a decent stretch of years where it was basically impossible to implement GCM securely on architectures that didn't have something like the CLMUL instruction.
I don't agree with you at all about the equivalent of IV misuse under CBC+HMAC and nonce reuse under ChaPoly. It's a bug either way, and bugs in cryptosystems are bad, but it's much less bad in CBC+HMAC. That is in fact a good reason to use it.
But it’s less bad because of HMAC, not because of CBC. Hand waving arguments that CBC is meaningfully better than CTR mode under IV reuse are silly. There are cases where a nonce reuse in CTR mode reveals very little (eg key wrapping) and cases where the same in CBC mode reveals everything. The worst case for both is equally bad.
I still disagree with you even given this refinement. A repeated CBC IV is a second-order vulnerability that still requires you to set up the conditions for an ECB-style attack on the system, which isn't always possible. A repeated CTR nonce immediately sacrifices confidentiality.
And my claim is that is not always valuable to an attacker, whereas I can't think of an instance where a repeated CTR nonce wasn't game-over.
It's always bad. I don't want to get into a semantic argument about whether or not a repeated IV is a vulnerability. It is. But it's not as severe a vulnerability as a repeated CTR nonce, which repeats the entire keystream.
> whereas I can’t think of an instance where a repeated CTR nonce wasn’t game-over.
The fact that you can’t think of an example is not a serious security argument. This is why we have rigorous security definitions rather than hand waving “I can’t think of anything” arguments, which should have died in the 90s.
I already gave you one example: key-wrapping. JOSE (of course) has a key-wrapping mode based on GCM, and at least one recent article advocates for its widespread use [1] (see recommendations at end). Despite me not agreeing with that advice, it is an example of where CTR loses no information at all under nonce reuse: the XOR of two random keys is itself indistinguishable from random.
I can certainly think of examples based on encrypting binary data streams where the XOR of plaintexts may also reveal very little. To decide whether CBC or CTR leaks more you have to consider the specifics of the application, or you have to make shaky assumptions about “typical” data. IMO those assumptions are not a good foundation for security and we should move past them.
In practice nonce reuse with CTR+GCM virtually always results in an obvious exploitable vulnerability. With CBC+HMAC nonce reuse sometimes results in an obvious exploitable vulnerability but often results in a system which has unclear security properties but which isn't known to be practically exploitable under common use (and may even still be provably secure under after careful analysis).
In other words, if the latter system is flawed it ends up having the sort of security properties more akin to physical security rather than the strong mathematical assurances we expect from cryptographic systems.
Given the high rate of issues with nonce mishandling in real systems, even ones that appeared to be carefully engineered, it shouldn't be hard to understand why systems engineers (as opposed to, say, cryptographic researchers) would have an unambiguous preference for one over another when it comes to practical systems, at least if all else were equal (which, of course, it seldom is!).
> IMO those assumptions are not a good foundation for security and we should move past them.
No one here is advocating that using CBC with intentional potential IV reuse is good security. But defense in depth is a good security practice and using primitives that fail less catastrophically when inevitable disasters happen is also a good security practice.
This is doubly so because there we know that that some sophisticated attackers have been known to exploit the brittleness of otherwise secure schemes to compromise implementations. Brittleness doesn't just increase exposure to chance it also makes it easier to inject bugdoors and to plausibly deny them.
Comparing GCM to CBC+HMAC is not fruitful because they are different in too many aspects. I already stated in the very first message in this thread that HMAC is far more robust than GMAC. Compare CTR+HMAC vs CBC+HMAC.
What I take issue with is people stating that CBC somehow provides more security than CTR mode under IV reuse. (Ie your statement that it provides defence in depth). That is a statement that doesn’t stand up to scrutiny in any rigorous way. Both fail pretty badly. Learning the XOR of two plaintexts is sometimes worse than learning if they share a common prefix, sometimes not.
Put it another way, how would using CBC vs CTR mode in any way impact your response to learning you had a IV reuse bug in production? It wouldn’t in any meaningful way at all - you’d still have to assume that the data was compromised to some degree. Compare that to a real defence in depth like SIV mode, where in most cases (not all) you could assume that no data breach occurred.
Thomas Ptacek thinks that I’m being a purist about this stuff. Fair enough. But I think people who believe that CBC provides meaningfully better protection than CTR in the real world are kidding themselves.
You're responding to an argument I didn't make. Obviously I don't believe that repeated CBC IVs are never an exploitable vulnerability. There are famously exploitable instances; one broke TLS. I'm arguing that a repeated CBC IV is less likely to be practically exploitable than a repeated CTR nonce, which is virtually always exploitable.
You previously said CTR mode nonce repetitions are “always bad” and are “game-over”. I provided a simple counterexample.
You also said that IV reuse in CBC mode can only be exploited if you setup an ECB-style attack. Also untrue.
Now you have retreated to merely claiming that CBC issues are less likely to be exploitable, but have provided absolutely zero evidence to backup that assertion. I don’t think you could really stand that up without making a bunch of assumptions about typical application data that I think are shaky.
The way to address this is not to endlessly debate the pros and cons of different confidentiality-only cipher modes. Instead, modern crypto acknowledges that none of them are CPA-secure in the case of IV reuse, and they all leak info in different ways. The best course of action is then to assume that in the worst case they are basically all terrible and design around that at higher levels: like SIV, or XChaCha, or whatever.
I didn't catch the CTR bit in your key wrap example. To be honest, when people start talking about key wrapping, I stop paying attention.
We just disagree. You have a purer take on this stuff. My personal experience, which is that of a vulnerability researcher and not that of a cryptography engineer, is that the purity test perspective is helpful for spotting patterns of vulnerability, but that's about it. It's demonstrably safer to run a CBC+HMAC authenticated secure channel than to run a GCM secure channel, and lots of people do exactly that for exactly that reason. The purity test vantage says "feh! the same bug exists in both!". The vulnerability researcher vantage says "no, all bugs are not in fact the same".
Why are we so concerned with nonce misuse anyway? I understood it at the time when nonces had complex rules, and when they were created deterministically. But nowadays it's pretty standard that modern algorithms work jut fine with completely random nonces, and it's pretty standard that you make them this way.
It being standard, they just come packed with the algorithm. IMO, worrying about bugs there makes exactly as much sense as worrying about bugs on the main algorithm. There's no reason to single them out.
This is a question with a simple answer. The most popular nonce-based AEAD is GCM, which has only the AES block size to fit both a nonce and a counter, which doesn't leave enough headroom to comfortably use random nonces. As a result, people build elaborate schemes to generate deterministic fresh nonces, and when those break, GCM breaks.
There are several reasons. Off the top of my head:
1. People use bad PRNGs or otherwise mess this up so the nonces aren’t as random as they should be, or they use ciphers with small nonce spaces (eg original ChaCha with 64-bit nonces) and generate enough nonces that collisions become likely.
2. Even if you use a larger nonce space, like GCM’s usual 96-bits, you may be Google and generate so many nonces so quickly that collisions even then become likely. (This is generally not a problem for >128 bit nonces though). See the rationale for the development of AES-GCM-SIV for an example.
3. If you generate a random nonce then you have to send that nonce on the wire, which adds overhead (e.g. 16 bytes per message). If you send a lot of small messages or have strict space limits then you might not want this overhead, leading back to deterministic nonce generation.
4. There are a lot of existing crypto protocols in use, and almost all of them use deterministic nonces. We’re not going to just replace them all overnight with random nonce variants.
Also nonce misuse is a common failure mode among novices who might not understand what a nonce is supposed to be. People do all kinds of mistakes including using hardcoded static nonces. Its also fairly easy to come up with a bad protocol where someone can trick you into nonce reuse. Or there is a complicated error path that might involve a device going through reset where a nonce reuse might occur. Some of these are not so trivial to identify either.
Boring is a sign of maturing: the focus should shift from algorithmic innovations to testing / validation / proof that the implementation is correct, which requires a mostly monoculture.
That's what I was thinking. If we want transparent crypto (i.e. not security by obscurity) and the implementation is highly vetted, its "monopoly" is actually desirable.
Of course we might not even be aware of even better methods of doing crypto. But such advancements come from researchers anyway, and in that are not hindered by this monopoly.
Demonstrably, the most secure cryptosystems today are the one that secures Bitcoin. If that could be cracked, or even work-reduced, someone would be a multi-billionaire, and the transfers would be noticed. Since that hasn't happened, we can have some confidence in those cryptosystems.
Why would that be the case specifically for bitcoin? Lots of cryptography secures things far more valuable than bitcoin and breaks in bitcoin would reduce its value to zero unlike many of the other things protected by cryptography.
I assume that the argument is that a break in secp256k1 has an especially straightforward monetization, where breaking the cryptography in TLS, while much more destabilizing to the Internet and the things running on it, wouldn't immediately net you a bunch of cash, but rather would just enable further attacks that might get you that.
Ah, I see, thanks. Somewhat reminiscent of 'why waste 0-days stealing WoW gold'. Still feels like the argument is complicated up by things like Very Lorge or State Actors (to whomst money is not even money, as you like to point out) and that the value they seek to derive is also not necessarily financial or at least not immediately so. Like, surely more effort has been spent trying to break TLS than secp256k1 specifically.
> I assume that the argument is that a break in secp256k1 has an especially straightforward monetization
Exactly. Considering the sheer effort put into Bitcoin, including volume manufacture of custom ICs, if this was possible, someone would have done it by now. It wouldn't even be illegal.
What I think your analysis misses is that the security of a cryptosystem isn't an absolute thing. All sorts of cryptosystems exist that haven't been broken, and may never be broken, but would likely get someone else broken if emulated in a different setting. So the reason cryptography engineers probably wouldn't use ECDSA in a modern signing system, if they had a choice, is that ECDSA includes a bunch of footguns that better signing systems avoid.
I think you'll find most cryptography engineers wouldn't reach first for secp256k1, or for the ECDSA signing system, regardless of their success in Bitcoin.
It seems currently open source has a DJB monoculture. Meanwhile, recent NIST has a Joan Daemen monoculture (AES and SHA-3). Early 1990s there was a Ron Rivest monoculture (RSA, MD5, RC4).
It's also somewhat of its time - there has definitely been a turn towards systems which are less full of footguns in the intervening years. TLS 1.3 for example, which heavily pared down the available ciphersuites.
Was anyone ever not hacked for using Sendmail? I lost count of the number of times the project included remote-code-execution-as-a-service in a point release.
That's the one thing keeping me from operating my own Mastodon instance. All it takes for me to be in serious trouble is some troll tooting CSAM while mentioning my account... that causes my Mastodon instance to automatically download it, and so the troll can then report me to the authorities for hosting CSAM. Or Nazi content (which is banned in Germany for good reasons). Or piracy. The list of how one can shoot themselves in the groin by simply running a Mastodon server is pretty much endless, and it's not made easier by the fact that German prosecutors are so tone-deaf regarding anything Internet that it took years to get them to stop raid TOR exit-node operators.
How people are running Mastodon servers out of Germany, or how there are people running Mastodon-as-a-service shops is frankly mind-blowing IMHO.
Your Mastodon instance is caching stuff locally. If you post something to your instance it lives there until another instance requests it. Then it lives on both instances. If your instance deleted the toot/content and I try to access it after the deletion I won't be able to get ahold of it. Same concept as IM2000.
Note I'm not sour on the idea of IM2000. I genuinely think its ideas were used by ActivityPub.
I wonder if there’s any cryptocurrency article from 2016 that would be worth reading today.
Cryptocurrency content ages like milk. Some of the original papers are worth reading of course, but by 2016 the influencers and hype shills had thoroughly taken over. That was the era when Buterin was calling Ethereum “a global supercomputer” with a straight face.
I was thinking that one of the PoS papers might fit, but the Tendermint paper was 2014, and the Casper FFG paper was 2017.
Do you think Groth16 counts? So named because it was written by Groth in 2016. Groth16 introduces the first really practical zero knowledge proving scheme. I'm pretty sure it's used by zcash as well as Filecoin, and projects like Tornado cash. It opened the floodgates on verifiable computation techniques that are used for everything from scaling to privacy.
Every year there's a ton of braindead noise, obviously, but every year there are also fundamental breakthroughs that change how we compute.
Actually, specifically because of Groth16, the "world computer" concept is becoming more and more possible every day. When you have verifiable computing, you shift the paradigm from every node on the network having to verify every state transition to any given state transition only needing to be verified by one machine somewhere in the world, once (which can be done in parallel with the proving of every other state transition). This means something like a blockchain network is now only limited in scale by how much compute you can throw at it, and as the algorithms get faster, and the compute gets better, we're seeing multiple orders of magnitude throughput increases every year. Things have been getting pretty wild in the cryptocurrency space for the past couple years, and the future looks insane.
edit: For people interested in diving into WTF "verifiable computing" is, this is a really awesome project that does some cool stuff with it that I'm not affiliated with in any way : https://github.com/risc0/risc0
I'd call Pinocchio [PGHR13] the first truly practical zk-SNARK and Groth16 close to being the endgame of pairing-based SNARKs. The difference between earlier constructions and Groth16 (in proof size/prover complexity/verifier complexity) is less than 2x: https://github.com/scipr-lab/libsnark/blob/master/libsnark/z...
We academically wrote (2014) and then deployed Zcash (2016) using PGHR13, and then later Zcash upgraded to a better circuit that used Groth16. It was, to my knowledge, the first production system to use SNARKs, and “modern” systems like Tornado Cash Nova use basically the same ideas.
Are you from 2021? Because in 2023 the landscape has literally been obliterated to say the least.
P.S I think "global computer", "verifiable computation" are a make believe concept if you ask a computer scientist. Sounds good on paper and feel futuristic though.
Computer scientists don’t believe verifiable computation is make believe, it’s real and here now, and all of the ones working in cryptography or adjacent fields know it.
It’s only the rest of the mainstream business world that hasn’t yet caught on to the value it can provide. There are numerous good ideas for using it in business contexts that aren’t being done yet. It’s mainly the cryptocurrency ecosystem that grokked its value first and have been rapidly deploying it into production.
Since October 2020, the entire future roadmap of Ethereum, the second largest cryptocurrency, has been heavily based on verifiable computation, in the form of rollups.
In 2023 alone, maybe 5 or so fully functional proving systems for running verifiable compute in the Ethereum Virtual Machine have been launched, and are currently live and operational. It's still early days, and there's a lot more work that needs to be done to fulfill the vision, but progress is happening faster than anyone expected.
How many actually do that and how many just make HTTP calls to SaaS providers? It only means anything if you run your own node and/or actually implement or at least use verifiable compute code.
I don't see why the difference matters. In both cases, verifiable computation is deployed and useful.
In the case of HTTP calls to SaaS providers, that's part of the promise of verifiable computation - that you can outsource it to a provider and verify that both the input and the computation are what you specified, and thus that you can trust the output. Even if its running in an otherwise black box on the SaaS provider's infrastructure.
Ha, I started using Bitcoin in 2009. There was maybe a three month mania back in 2021 where everything was valued 3x higher than it should have been, and now we're back to the mean. The idea that a 60% dip from ATH is "obliteration" is pretty laughable.
Verifiable computation doesn't require your faith. It works, and it's powering several billion dollar economies at the moment, and growing like crazy. By all means you're free to demonstrate that the math is faulty. Basically every project in that space has a million+ dollar bounty program for such bugs.
> Verifiable computation doesn't require your faith
Isn’t it so that in general verifiable computation needs a trusted setup phase? Although it can be run between multiple parties, still one needs to have faith in their honesty.
Only a small subset of computations does not require a trusted setup phase. Proof of shuffle and threshold decryption comes to my mind as examples.
Sometimes I stop and take a moment to appreciate DJB and his contributions both mathematically and ideologically. We're really fortunate to have him holding it down on the chalkboard and in the court room.
There was a time, not long ago, when HN was filled to Crypto threads. Now you can see one every other week. What happened? The same people who was invested in crypto is now all on AI? Or is just the media?
