I read it, I don't buy it in general. In most use cases we need serious safety margins. Their "attacks always get better" section downplays serious issues.
First, it seems extreme hubris to think that something can't ever be broken before the human race disappears. There are plenty of algorithms that have been broken over the years, and there is no mathematical proof that the current set are unbreakable. Sure, the algorithms they listed aren't broken yet, but that's a carefully crafted list. In any case, "not broken yet" is a far cry from "unbreakable".
Another problem is that if a crypto algorithm is broken, there's a significant risk that the users of the algorithm will not be informed until possibly decades later. Many countries dedicate serious resources to attack, and would want to exploit those advantages if they could find them.
Finally, if a major algorithm (e.g., AES) was broken, it would take many years (probably more than 10) to replace it. The reality is that software systems are often hard to upgrade. Yes, that's a problem, but ignoring reality doesn't make it go away.
The only solution we know of is to have large margins.
In the physical engineering world, where we have far better understanding (due to physical models), smart engineers include significant margins when designing things. In the crypto area, where we do not have good models showing that something cannot be broken and the impact of failure is large, it is wise to have much bigger margins.
I agree that sometimes cryptographers incorrectly ignore other attacks. And no matter what, impractical attacks are - by definition - impractical. But I think it's wise to assume that attacks will get better, and we cannot reasonably predict how much better they'll get over the years. Past performance is no guarantee of future results. Margins also increase the likelihood of a break being partial, giving people time to switch to another algorithm.
In special cases, maybe the margin doesn't need to be so big. But nobody likes dealing with special cases.
The point this paper is trying to make is that we should be using safety margins based on knowledge rather than perpetuating the numerology that's been in-place to-date. The very same argument you're making here can be made regarding switching to 512-bit keys. And heck, why not 1024-bit keys too. The fundamental point the paper is making is:
A) The key size & number of rounds aren't where the security issues are today
B) We have a sufficient margin of error and understand the space well-enough that we're likely OK to use existing symmetric encryption with fewer rounds & smaller key lengths.
C) If you're a target of an attack the encryption keys are unlikely to present a significant challenge as attackers will choose easier alternate vectors.
I find the arguments pretty compelling especially when you consider A & C.
> The point this paper is trying to make is that we should be using safety margins based on knowledge rather than perpetuating the numerology that's been in-place to-date.
Exactly. The point is that a fair A/B speed comparison between competing ciphers should be normalizing both A and B to equivalent security margins. Instead, its been up to each individual cipher designer as to how many extra rounds should be used.
That said, I think the paper's point would be clearer if they had written down a complete table of "equivalent margin rounds" holding each of the standards constant. Ie, how many rounds does ChaCha need to have equivalent margin to AES-128 at its specified number of rounds?
> Exactly. The point is that a fair A/B speed comparison between competing ciphers should be normalizing both A and B to equivalent security margins
Assuming that A and B have received an equal amount of cryptanalytic attention and the "best publicly known" attacks represent equal amounts of effort/progress against the algorithm.
In practice, we need to overspecify algorithms initially, not knowing what the next 10-50 years of attacks will look like. Maybe 15 years in you go "woops, could have used fewer rounds-- we're holding up much better than I thought," but at that point the parameters are standard and...
Are you suggesting it's going to look a lot different from the previous 45 years? Because the previous 45 years suggest pretty strongly that we do in fact know how to design a block cipher.
Public knowledge of differential cryptanalysis is younger than 45 years, and was known to NSA 20+ years before its public "discovery" (and known to IBM 15 years before).
Multiple finalists in the AES competition (which selected Rijndael) had significant weaknesses found in the decade since, despite receiving relatively little attention (MARS, Serpent).
A factor of 2x+ speedup isn't "not much to be gained", but the point again is just to be more rigorous about the security margins we're trying to get.
Can you say more about what you believe the "debate" about key size and number of rounds to be? A pretty important point Aumasson seems to be trying to make here is that the reduced-round analytic results against ciphers are arguments in favor of their fundamental strength, not signs that they're teetering on a precipice of insecurity.
2x+ speedup would assume that all you do is just doing encryption/decryption while in most cases crypto would use only a small percentage of cpu time anyways. So if - let's say 1% of cpu time is spent on crypto, then that 2x gain translates to .5% overall speedup. On the other hand I do understand that this % varies a lot depending on what software/system you look at
I assume we all understand that in this thread, when we talk about performance increases, we mean of the ciphers themselves. "Crypto performance doesn't matter" is a coherent argument, if you want to make it, but if crypto performance does matter, a 2x boost is obviously material.
"We could have doubled the speed of this hash if we had been more rigorous about security margins" seems clearly to be a powerful claim. Especially since performance is in reality a pretty huge part of how we choose the cipher designs we standardize.
the argument I was trying to make is more in the sense "is it worth to take (even a minimal) risk optimizing performance given that this very performance gain is not (that) important overall"
That being said, I do understand that there are a lot of areas where performance/energy budget is tight and this actually makes a (huge) difference
How true is this (I have no idea)? And to the extent it is, how valid would it be to draw a comparison to the security of software, saying something like "after out-of-bounds writes, we're mostly out of ideas on how to get RCE out of C programs"? There are a lot of extensions to basic differential cryptanalysis.
Seems like a tough comparison to make given the security of a cryptosystem is a lot better defined than that of a program, even in a constrained case like 'RCE in a C program'.
It might be, I don't know. In practice (that is, in carrying out cryptographic attacks on real systems), nobody ever cryptanalyzes ciphers, so I've hardly studied block cipher cryptanalysis at all; someone much smarter than me gave me a purely linear block cipher once and I didn't spot it (plus side: now I can break purely linear ciphers! make a bunch of them! put them in JWT!), so this stuff is generally over my pay grade, though I have cryptopals exercises for basic linear and differential cryptanalysis tee'd up.
But I'm just noticing how many named cryptanalytic techniques, like Boomerang, Impossible Differential, even I guess to an extent Slide, are really extensions of Matsui and Biham and Shamir. And that's true of C/C++ software too: most attacks seen in the wild are derivatives of just a couple basic techniques ("out of bound write" is obviously putting my thumb on the scale, but "buffer overrun", "integer mishandling", and "use after free" cover a pretty good fraction of all attacks on memory safety).
Which is all to say: "we've had no good ideas since differential" might not be as meaningful as it sounds? Or maybe it is. Sometimes the best way to get good information into a message board thread is to add bad information, and, in theoretical cryptography, I contribute that ably!
I don't really know either, I'm just pedentipointing out that the security of one of these things is an actual number, measurable in bits and this fact makes Aumasson's argument possible to begin with.
The 'security' of any program even in relatively constrained cases is woolier. Is a C program that can't write to executable memory at all but can allow the interpretation and execution of some language it happens to interpret vulnerable to RCE, etc. So if there is a parallel of some sort, it seems to me it could only be a narrative one.
Analysis of security of arbitrary programs is in its infancy, we can't quantify anything yet. I think the best we have is halvarflake's provable unexploitability [1] and that is very weak.
When I look at the number of papers published, the number of courses offered, professors, or companies, it doesn't seem like the cryptanalysis field is particularly big.
> The point this paper is trying to make is that we should be using safety margins based on knowledge rather than perpetuating the numerology that's been in-place to-date.
Yes, but we should also understand that additional computing, in most situations, is really cheap, and that compromised cryptography in wide use is inordinately expensive.
> The very same argument you're making here can be made regarding switching to 512-bit keys. And heck, why not 1024-bit keys too.
We know we need at least like 80 bits to start to be safe against brute force. 128-256 bits are reasonable "round number" sizes that have a keyspace in large multiple of this.
> A) The key size & number of rounds aren't where the security issues are today
They're a key part of the security of the thing we're actually talking about (the cryptographic algorithm) and excessive key size and number of rounds has often rendered actual algorithmic weaknesses unexploitable in the past.
> B) We have a sufficient margin of error and understand the space well-enough that we're likely OK to use existing symmetric encryption with fewer rounds & smaller key lengths.
Maybe. And again, why?
> C) If you're a target of an attack the encryption keys are unlikely to present a significant challenge as attackers will choose easier alternate vectors.
You could use this argument to make every single bit of the security stack (equally) weak.
>We know we need at least like 80 bits to start to be safe against brute force.
you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number. (That is probably the numerology the GP was referring to)
[0]Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive
> you could imagine a cipher with a computational/memory[0] intensity so high that the brute force attack could be practically infeasible even at lower key-sizes. I am not advocating using smaller keys, just pointing out that there is more to brute-force resistance that simply just the key-length number.
In general, this is a dumb trade to make, because more key bits are cheap and that computation costs every user.
Things like what you describe exist-- where initial key scheduling does key stretching, etc.
> Since memory intensity instead of pure computational intensity seems to be employed by some hashing alghorithms I wonder is that would be possible block ciphers as well. The way I understand this, it makes ASIC/FPGA brute-forcing a lot harder/expensive
Anything is possible, but this often does more to hurt low-resource users than brute force also.
>but this often does more to hurt low-resource users than brute force also.
1MB memory usage would not hurt most of the low-resource users while having 1MB memory for each of the millions of computational units in a brute-force rig would hurt the attacker a lot more. I assume that it is relatively easy to have a huge number of brute-force cracking units in a simple GPU/FPGA/ASIC rig but if each of them would additionally need lets say 1MB of RAM that would present a serious problem for the constructor of such rig.
I do get that AES will happily run on a 20-year old smart-card simplified cpu without a problem while my fictional 1meg-requiring cipher would be problematic, but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems.
> but then again it's 2019 and 1MB is not that of a problem for the least powerful smartphones or even embedded systems.
1MB means you basically obliterate caches and torture memory bandwidth every time you want to encrypt a tiny block. But ignoring that...
Low cost microcontrollers with 4k or 8k of RAM total are still used in embedded systems and often have hardware AES built in. Even things like ESP32 are often considered relatively big and have 520k of ram.
There are applications and services that have a million or more connected sockets with encryption at a time. This would represent a terabyte of RAM just for this 1MB block cipher scratchpad.
If one were to just use a megabyte during key scheduling or something-- that's feasible, I guess, but it still locks out a lot of the embedded world.
True but also to remember that vendors build the chips the industry demands. So if they need to provide 1MB they will - it will just mean a larger BOM unless the chip package needs to grow. The size is going to be the biggest bottleneck there.
You fixated on one bit of the argument, but if you want to discuss that: Memory on logic processes is expensive. That's why SRAM is precious on microcontrollers. Also, already the largest memory sizes require much larger than typical packages.
A microcontroller with a few megabytes of RAM to support several crypto sessions with this cipher is going to be a big cost multiple over current micros.
>C) If you're a target of an attack the encryption keys are unlikely to present a significant challenge as attackers will choose easier alternate vectors.
Absolutely true and none need look further than how the best of the best (NSA/Equation Group) handle such hurdles....they install malware on the computer to grab your keystrokes. Though I think if you have mission critical data you would be wise to never connect your machine with encrypted data to a network, ever. You need to have two machines. One which stores the encrypted data, custom built with trusted hardware. No wifi, no bluetooth, no USB, no cd rom etc.
There are other novel means to leap air gaps. I remember from a few years ago a technique using ultrasonic by, IIRC, spinning a harddrive at certain intervals and listening in from a standard PC mic.
Also, a stripped down computer like you describe is going to be of marginal utility. How do you get the sensitive data in or out? Transcribe by hand? Might as well write your secrets in a code on a piece of paper and lock it in a vault.
Airgapping by removing CD/USB/network, you arent really increasing security. Youre just freezing the machine in a point in time with no security updates or other useful means of actually handling sensitive materials. One could argue this actually makes it easier to exploit given sufficient physical access.
Also, NSA using keyloggers doesn't make them best of the best (not that they arent good at what they do, just saying key loggers is a small barrier and very common and easy to use - easy enough I was using them as a kid in the 80s). They may have superior ways of achieving it, such as supply chain attacks, but key loggers have been around pretty much since computers have existed.
For the symmetric block ciphers we have a reason to be confident that we're done, that we learned all the things we needed to learn to do this properly, not just for a generation - which reducing the round count would make us less confident of.
The rationale goes like this: After all this time, the best practical attacks on the _previous_ symmetric block cipher (DES) focus on the two things its designers intentionally picked to be weaker because they saw this as appropriate. The keys are too small (56-bits) and the blocks are too short (64-bits).
Cryptanalytically, there has been not insignificant progress on DES, but after decades of focus fire it's looking in relatively good shape. Some type of Linear cryptanalysis might get you down to 2^40 DES trials after you collect 2^47 plaintexts for example. That would be unacceptable in a brand new cipher (if you got this far thinking "Maybe I should use DES?" you are a bad Hacker and should feel bad), but still falls short of what you'd need to actually do bad things in the real world. We should not expect AES to suffer a quicker death. AES has 128-bit (or 256-bit) keys and a 128-bit block length so the obvious problems are fixed.
I don't have the same good feelings about the hashes or the asymmetric crypto yet.
> I don't have the same good feelings about the hashes or the asymmetric crypto yet.
You might be interested in https://electriccoin.co/blog/lessons-from-the-history-of-att... (caveat: it’s a few years old, and it might have mistakes). It’s an empirical view on the history of hash functions. The results were very interesting to me. Against collision attacks, it kind of seems like we figured out how to make hash functions secure against them in the 2000’s (compared to block ciphers, which I guess we mostly figured out in the 1970’s). Against preimage attacks, it seems like we figured out how to make hash functions secure against them as soon as we invented secure hash functions at all — in the 1990’s.
Des is both an example and a counterexample - the same changes that shortened its key to 56 bits also changed its S-boxes to be resistant to differential cryptanalysis. That was a previously unknown (although later separately discovered) attack vector to the public community. It's important to always think of the attacks you're describing as the best publicly known attacks.
And man, the rounds we have are not so expensive. Even cheap phone SoCs tend to have hardware-accelerated crypto. Some server chips have AES-128 in the memory controller, inspired by a feature console makers wanted: https://www.crn.com/news/components-peripherals/amd-s-xbox-p...
(AES-128 happens to also be one of the algorithms he thinks has the least "extra" margin, for whatever that's worth. Bigger difference for ChaCha.)
I do have some sympathy with the idea there's less uncertainty around long-studied symmetric algos than there was long ago, so the sensible margin is smaller than it used to be. Symmetric crypto's certainly moved closer to the good kind of boring since the AES competition and e.g. thorough study of RAX ciphers and other minimal primitives.
But from another angle, we have a system that's working pretty well, including in cost and performance. Given interoperability, etc. seems like there's a high bar to mess with it in the name of making a few more super-small-scale uses of crypto possible or cheaper.
You're saying "the rounds are not very expensive" but the paper is generating 2x+ speedups. This is a paper by a cryptographer (Aumasson is an author of BLAKE and BLAKE2) and a participant in the cryptographic contests that have selected the primitives we use now, in significant part due to performance concerns.
Which is just to say, to the extent that the performance issues Aumasson is talking about don't seem relevant to you, you might just not be the audience to whom the paper is directed.
Yes, I know Aumasson's a highly respected professional and followed the contests, and am even, like I said, kinda sympathetic to the idea that keeping a big margin for unknown unknowns may make less sense than it once did.
What's the practical play here though? I guess lower-round ChaCha-Poly1305 TLS cipher suites could be worth it for users without hardware AES. I suspect even less-aggressive folks would be comfortable enough with ChaCha12 instead of 20 (e.g. Android already uses it to encrypt storage when there's no AES acceleration).
But trying to move to reduced-round variants of every already-standardized primitive would be a lot of effort to, for most applications, move symmetric crypto from one tiny amount of resource use to another (even if it's much smaller in relative terms!).
I do realize that people care a lot about performance, that there are applications either building on tiny microcontrollers or handling redonkulous data flows, and that any possible bit of flexibility could help someone. Still seems fair to ask: if the broad change in perspective Aumasson wants does happen, is it really going to change much about crypto in the wild soon?
I think the big unknown unknown would be something along the lines of a hypothetical mathematical breakthrough that renders current cryptography useless. I'm not even suggesting quantum computing. Suppose someone figures out a way to rapidly factor large numbers easily using classical computing?
Yes, we dont know how to do it now, but there have been a lot of things we didnt know how to do or was thought impossible 20, 50, 100 years ago.
I dont have any special insight to this, just saying that what was once impossible can become a daily occurance in time and with the right breakthrough.
Factoring large numbers won't have any effect on symmetric cryptography. Finite field cryptography, if you want to call it that (DH, RSA) requires the primes be big enough to generate sufficiently large finite fields for all algorithms that might factor or solve dlog to be so expensive to run you can't do it. Same with elliptic curves - the finite fields are chosen to be large enough to make the best algorithms that can solve the ecdlp impossible within our lifetime, modulo either quantum computers or a major classical speedup.
At a very high level (I'm about to take liberties with the entire field), symmetric cryptography is a permutation of bits in the input block. To make it secure we need two things: confusion and diffusion. We don't want the relationship between plaintext, key and ciphertext to be simple to describe, and every time a bit is flipped, we want approximately half the output bits to be flipped. There's actually very little mathematics involved here: you can describe AES in terms of finite fields, but there's no hard to inverse problem in place. It's simply that finite fields a) conveniently describe binary in characteristic 2 (AES uses GF(2^8) which can be represented as 8 bits, or one byte) and b) have "weird" multiplication even when using the most obvious characteristic polynomial, which AES does not. Actually I think this was mildly controversial at the time, because it implies some structure (and we generally want no evidence of structure of any kind).
Cryptanalysis, in this context, tries to find "chinks" in this confusion and diffusion. Imagine if you took two plaintexts, what happens if you start doing things like encrypting the xor of them, versus encrypting one or the other? Doing this with enough plaintext/ciphertext pairs gives us enough information to find the key being used, eventually. Or what happens if we can make linear approximations to parts of the cipher? Can we use this to take shortcuts and guess the key? Have a read of http://theamazingking.com/crypto-diff.php and the linear stuff there. This is the best we have.
tl;dr factoring large numbers, or any advance in the mathematical areas has little bearing on symmetric cryptography. What we need is a way to see structure in something that has been deliberately designed to have as little as possible. Of course, nobody knows, but I'd guess that it's more likely someone will find a speedup for the ecdlp than any meaningful improvement to block cipher cryptanalysis.
I think the point is that additional rounds are poorly representing any sort of measurable return. Maybe the thesis is poorly worded to get attention?
I don't think anything in cryptography should be taken for granted. Any sort of assumptions that were made 20 years ago should be revisited given how much the landscape is changed.
That being said, it actually DOES look like there is a call for less rounds, and I am totally projecting what I think we should be advocating for.
Isn't one of the cardinal rules of crypto "fast crypto is easily broken crypto?"
Is not the solution to have crypto libraries abstract away the exact crypto algorithm used. Say it provides a collection of symmetric key algorithms without letting the users pick which algorithm is used. This way the library can update and prohibit algorithms deemed insecure and the user doesn’t have to worry about it.
The reason for that is that there were way to many attacks on earlier TLS versions that used the cryptographic agility to make the victims use poor crypto. The strong crypto was never broken, but the protocol was used to make sure strong crypto never happened.
Also: if I send a sufficiently encrypted message today, that message may be captured by a malicious actor, stored and decoded later, after the cypher has been broken.
Yes, everyone understands this. That's why the paper is talking about attacks at the boundaries of what is physically possible, not in terms of what an attacker could cost-effectively do online.
But all the prior blocks are static, that's the point. If you can break the cipher used at some time t, anything that people had "stored securely" by encrypting it and putting it on the blockchain before time t is vulnerable. As our technology and understanding gets better, t might get later and later. Obviously it depends on your use case, but it's a good argument for not putting sensitive things out in public on a blockchain at all.
> Suppose that against all expectations, someone finds a 2^100 attack on AES-128 that is embarrassingly parallel and uses no additional memory. Say you have 10 billion cores, each running at 10 GHz, trying one key per cycle, and you’re aiming for a one-in-a-million success rate: it’d still take you on average more than twelve thousand years of computation to do the ≈ 2^80 required
According to the Bitcoin node on my computer, there have been ≈ 2^92.4 executions of the sha-2 compression function used for Bitcoin so far, exactly the sort of embarrassingly parallel memory-less task that the author speculates about.
So the author's example of a obviously secure attack resistance level has already been exceeded just by bitcoin mining by a factor of thousands.
> For example, “zero-sum distinguishers” [4],arguably the most contrived and meaningless type of attack ever, are about finding a set of input values whose output values sum to zero.
I realize that the author is making fun of his own prior work, but I think he exaggerates the uselessness of such an attack. Finding a set of inputs to a hash function such that the hashes sum to zero (or other specific values) can be directly turned into attacks on cryptographic systems that use those hashes. In particular, attacks like that can lead to total breaks in things like threshold signature protocols and blind signing.
When cryptographic primitives have surprising structured properties there often seems to be a greater fool hiding right around the corner waiting to build a system that almost magically is broken by the structured property. :)
Unless I'm missing something in the calculation, 2^80 / (10 billion * 10ghz) = 12089 seconds, not years, which does flip his point re: 2^128 being uncomfortably risky if you want to factor in potential improvements.
You're not wrong. I wouldn't count on AES-128 staying secure for all of eternity, but I don't like they way you say
> just by bitcoin mining
like the bitcoin network is a small hobby project in someones basement. The bitcoin network has the same annual energy footprint as the country of Austria. The truth is that even with a purely hypothetical 2^100 attack on AES-128 the NSA wouldn't be able to crack a single key even if all of their funds would go directly into paying for electricity.
The energy calculations for bitcoin usually range between wrong and absurdly and painfully wrong.
Expenditures on the mining are bounded on the upper end by the income, which sets a current ceiling at about $13 million USD per day. In practice actual expenditures are a fraction of that upper bound, since the hardware still needs to be paid for an it wouldn't be worth doing without a profit.
Bitcoin's energy usage level (even the high upper bound) of expenditure is within the estimates of the NSA's budget (10.8billion usd/yr est in 2013).
The Manhattan Project had an estimated cost of $23 billion (2018) dollars.
If we take the article's target of 2^80 operations (for a one in a million against a 2^100 expected attack), and assume those operations are as efficient as bitcoin miners do sha256(sha256()) -- 0.075J/billion ops. And then we assume you pay 2.5cts per KWH for power (an industrially available rate in low power cost areas of the US) --- that attack would cost $629648 in power. I bet the US has single munitions that cost almost much.
The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely-- it doesn't matter that the computation has indeed, been pretty costly.
This makes another argument for setting parameters conservatively: order of magnitude errors in attack costs are less likely to be fatal if you do!
> The article is just simply mistaken about the intractability, the current existence of computation at a scale it claimed would take ten thousand years shows it nicely
Well yeah, the article might be wrong about how untractable it is, but that doesn't mean it is tractable. Even when taking the minimum annual electricity consumption of the Bitcoin network (41.31TWH/yr) and assuming the Bitcoin network did all those hashes in the last year and assuming that a 2^100 attack on AES-128 exists (which it doesn't), you'll still need an absurd amount of energy just to crack a single key.
> setting parameters conservatively
My argument is that for almost all applications key lengths of 128 bits are pretty conservative. AES-128 will not be the weak link in your application, bad usage of cryptography, memory leaks, use-after-free vulnerabilities, users just doing stupid things, 0-days in your operating system of choice are all easier to exploit than cracking a single AES-128 key.
That said, you probably shouldn't use AES-128 if your threat model includes a intelligence agency 50 years into the future. In that case AES-256 will not help you either.
Blake2: 8 instead of 12 for Blake2b (IIRC, Blake's rounds are derived from Chacha);
Chacha: 8 rounds instead of 20.
SHA-3: 10 rounds instead of 24 (Keccak).
(§5.3, "How many rounds?")
I'm not any kind of cryptographer, just an engineer who sometimes interacts with cryptographic algorithms, so I cannot comment on the specific recommendations.
I'm not qualified to say this but because it's HN I'll say it anyways: I'd imagine Aumasson's response to this would be: "we've cut it close on key size by playing around below the 2^128 threshold, and close on block size in the same way, but there's no evidence we've come dangerously close to practical attacks based on iteration count, and some evidence in the other direction; in fact, at this point, a cipher design that wasn't attackable through some number of rounds would likely be rejected for want of cryptanalysis".
It's also worth pointing out the NIST LWC has a proposed security level of 112-bit. We're actively designing and analyzing algorithms that can be acceptably below the 128-bit security bound, yet have a sufficient security margin for most people.
The obsolete NSA Skipjack algorithm was the epitome of having just enough rounds. It has 32 rounds. It was declassified in 1998 and within months, attacks on 31 of 32 rounds were published. However, there are still no attacks against 32 round Skipjack.
The idea that you could slash SHA-3 from 24 rounds to 10 (2.4x faster) and get the same effective security is astounding. I assume that applies just as much to using Keccak for encryption as hashing?
SHA-3 was finished in the aftermath of Snowden's revelations, and NIST's credibility was very low at the time, they needed to be extra conservative about security margins for this reason.
> SHA-3 was finished in the aftermath of Snowden's revelations, and NIST's credibility was very low at the time, they needed to be extra conservative about security margins for this reason.
Yep. There was discussion about this among NIST, the Keccak team, and the other cryptographers contributing to SHA-3. The consensus was that because NIST had been involved in the Dual_EC_DRBG backdoor, that their credibility was dangerously low and that they couldn’t standardize anything that ill-informed people could misconstrue as “weakening” SHA-3, even if the actual cryptographers involved thought it would still be secure. So in one sense, you can chalk up the unnecessary computational cost of SHA-3 as collateral damage from the Dual_EC_DRBG backdoor.
Kravatte (briefly mentioned in the paper), Keyak, and Ketje (all using the keccak permutation) do use fewer rounds than SHA-3, e.g. 12 in the case of Keyak.
The paper is describing what cryptographers have been doing the past 5ish years at least (see various CAESAR contest entries, the forms of Masked Even-Mansour that use 4 or 6 rounds of BLAKE2b permutation, etc.), but maybe encouraging them to push more in that direction.
I think this is a "Nobody got fired for choosing IBM" thing, where you might be better off with something else, but don't want to be the guy who picked the something else if things go wrong.
This is great though. The speedups advertised for using the recommended number of rounds is important (2x or more in some cases). While you don't want to be the guy "who picked it wrong," picking some arbitrarily high number isn't right either, and going about it scientifically as in the paper is the right way to go.
At some point, for people optimizing things at large scale, it's possible they will want to look at these round reductions, and the type of education needed to make this kind of judgement call goes way beyond "nobody got fired for choosing IBM"...
I like the argument that if you can break 2^100 complexity, you can probably break 2^200 because it will have meant you turned NP into P.
But... I have a 64Mhz embedded device doing 10,000 ChaCha20-poly1305 encryption operations per second on 64 bytes of data and 64 of “add” in the AEAD MAC. Small packet, but those numbers are crazy.
Chacha is FAST considering it doesn’t need the same special hardware that AES does.
I guess I get the idea of not doing extra work and at a global scale it might add up. But I won’t move my rounds down from existing standard unless I needed to.
IMHO if we look at the global scale, we might as well optimize tons other software or operating systems before. Or we could force-enforce SPF and DMARC and kill a lot of e-mail spam and save power like that. Reducing cryptosystems' safety margins doesn't just seem optimal to me.
I just figured out the other day that if I turn the POE off at our offices from 12am to 5am, it saves us $500 a year and a little durability on the switches. It's not processing, but I guarantee it's a larger difference for us than dropping rounds out of encryption.
A one time pad requires a randomly generated pad. I don't have confidence that todays random number generators won't be found in the future to be predictable, especially over long runs as required for a one time pad.
It's not one-time pad encryption if you use data from a PSEUDO-random number generator. “One-time pad encryption” only applies when a true random stream is used as key, otherwise it's just a block cipher with a particularly inconvenient way for the user to store the key.
Or are you claiming that there's a risk in the future someone will find how to predict what output true random generators produced when they generated the key?
You can generate a secure random bitstream by flipping a coin. To eliminate bias, use the von Neumann procedure: flip the coin twice; if the results differ, use the first; otherwise, try again. If you're paranoid about snooping, go out into the woods or make a Faraday cage or something.
Some hashing algorithms get broken, and we can never be sure whether a particular one is completely safe against attacks.
Now, to mitigate risks, one could use a composition of multiple hash functions, e.g. always apply SHA-1, then SHA-2 on data. Computation would be more expensive, but if one of the hashes gets cracked, data would still be safe as long as there at least one un-cracked hash function in the chain.
Matthew Green has a related post about this speaking to “multiple encryption” where people do the same thing with ciphers. [1]
A very generic take would be that depending on the system, it may be able to be done securely, but with all crypto there be dragons.
For example, let’s say you have two hashes H1 and H2 and want to use the double hash to prove existence of a file in history. Publish the hash to a blockchain or something.
So the file is hashed H1(H2(file)). In what ways could you break this if one of the hash functions is broken?
The first way is if you want to dispute the validity of what file was hashed. If we assume they later publish the file and you have a second-preimage attack on the hash.
You can create a different file where H2(file) = H2(newFile), and because H1 is deterministic, this second file verifies. It’s now no longer clear which is the true file. While a single hash function also fails under this attack, you increase your exposure to possible attacks by introducing a second one.
If you have control over the verification procedure you can imagine a similar attack with only a break in H2 by not even using H1 to generate the output.
The way to combine hash functions for collision resistance is not composition (as with encryption) but concatenation: H'(file) = (H1(file), H2(file)). Now to have a collision on H' you need to collide both H1 and H2. But now pre-image resistance suffers.
Checking two full hashes and requiring both to match only improves pre-image resistance. However, you now need twice the space to store the hash and efficiency suffers, likely wose than the sum of the speeds due to cache effects of running two different algorithms on the data. If you use shorter or weaker hashes you might end up with two breakable hashes (either now or by some potential quantum computer) rather than one unbreakable hash.
Some package systems store multiple secure hashes and pick one at random to verify.
> Thanks also to Dominique Bongard, Pascal Junod, Nadim Kobeissi, Alfred Menezes, Andrew Miller, Thomas Pornin, Antony Vennard, and Zooko for their feedback and improve-
ment suggestions.
Must be the first time I see someone with a family name referenced only by given name in an academic paper. It really shows how well-known Wilcox-O'Hearn is in crypto circles.
I think that this is poor style, but also probably is more because of his extremely unique given name. There are many Alfreds, Andrews, and Thomases, and so it really is necessary to specify Alfred Menezes, Andrew Miller, and Thomas Pornin. I don't know of any other Zookos, though.
Interesting read. While not addressed in the paper, what's a safe iteration count for password derivation algorithm like PBKDF2? Last I read it was 100,000 for modern machines.
The number of rounds in an iterated cipher is wildly different --- in fact, close to the opposite --- of the number of iterations in a password KDF. But: don't use PBKDF2 at all, if this is something you're trying to optimize; scrypt and Argon2 are memory-hard in addition to time-hard.
Good to know. Yes, PBKDF2 is kind of outdated. It's just that ripping it out and replacing with new key derivation algorithms takes time, especially needing inter-operated with other tools, while the iteration count is a simple configuration to bump up on existing implementation.
There is no such thing. The standard recommendation is to measure how much time you spend with your hardware and adjust the iteration count to the maximum tolerable amount.
The whole point of password derivation functions is to be slow, not fast. It’s just a matter of how slow is too slow.
For a reference, Django currently uses 260k iterations or something like that.
The hardware isn't fixed, though: I am both simultaneously writing software and deploying servers. I have an incentive to choose cheap servers, and in fact tend to run as much stuff as I can on tiny little instances that are just barely little slivers of CPU in the cloud somewhere. Locally, for app-based designs, I do a lot of work on phones, which are extremely variable. I have no clue if I am selecting numbers here large enough, and "choose what you can maximally tolerate" when you can also spend more money on faster hardware or require fancier phones from your users is nonsensical as it doesn't provide me any way to prioritize this expenditure versus other costs. I really wish someone would just tell me what I should be doing every year--including expirations on passwords or whatever else is required to deal with how the requirements change or alternatively telling me how to upgrade existing hashes to better ones (which I can never tell if the off-the-shelf algorithms even support, which is really annoying; like I would expect with something that has iterative rounds I could just iterate all my passwords a bit more every year to account for faster machines, but I think the final round is always different?)--and I can do that and feel good and point at it and say I did that.
First, it seems extreme hubris to think that something can't ever be broken before the human race disappears. There are plenty of algorithms that have been broken over the years, and there is no mathematical proof that the current set are unbreakable. Sure, the algorithms they listed aren't broken yet, but that's a carefully crafted list. In any case, "not broken yet" is a far cry from "unbreakable".
Another problem is that if a crypto algorithm is broken, there's a significant risk that the users of the algorithm will not be informed until possibly decades later. Many countries dedicate serious resources to attack, and would want to exploit those advantages if they could find them.
Finally, if a major algorithm (e.g., AES) was broken, it would take many years (probably more than 10) to replace it. The reality is that software systems are often hard to upgrade. Yes, that's a problem, but ignoring reality doesn't make it go away.
The only solution we know of is to have large margins.
In the physical engineering world, where we have far better understanding (due to physical models), smart engineers include significant margins when designing things. In the crypto area, where we do not have good models showing that something cannot be broken and the impact of failure is large, it is wise to have much bigger margins.
I agree that sometimes cryptographers incorrectly ignore other attacks. And no matter what, impractical attacks are - by definition - impractical. But I think it's wise to assume that attacks will get better, and we cannot reasonably predict how much better they'll get over the years. Past performance is no guarantee of future results. Margins also increase the likelihood of a break being partial, giving people time to switch to another algorithm.
In special cases, maybe the margin doesn't need to be so big. But nobody likes dealing with special cases.