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.
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?
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...
Multiple finalists in the AES competition (which selected Rijndael) had significant weaknesses found in the decade since, despite receiving relatively little attention (MARS, Serpent).
B) very,very debatable, especially this piece: "understand the space well-enough"
C) I tend to agree, but then (especially with hardware-supported crypto) there is not much to be gained by reducing the number of rounds
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.
"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
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!
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.
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.
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
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.
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.
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.
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.
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.
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.
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.
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.
(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.
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.
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?
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.
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 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?"
fewer
We can cringe 20 years out about ECC, RSA and AES.
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.