8 ms·

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. Fir

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.

vlovich123 7y ago
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.
- mr__y 7y ago
  A) debatable 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
  - tptacek 7y ago
    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.
    - mr__y 7y ago
      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
      - tptacek 7y ago
        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.
        mr__y 7y ago
ChikkaChiChi 7y ago
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?"
- ofcourseianal 7y ago
  One time pad is pretty fast
- tptacek 7y ago
  No, I don't think that's one of the cardinal rules of crypto.
- Simon_says 7y ago
  > less fewer
tialaramex 7y ago
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.
- charleslmunger 7y ago
  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.
- zooko5 7y ago
  > 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-attacks-on-secure-hash-functions/ 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.
amelius 7y ago
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.
- tptacek 7y ago
  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.
  - sroussey 7y ago
    People advocating putting sensitive data on blockchains in encrypted form do not understand this.
twotwotwo 7y ago
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-playstation-work-led-to-a-big-security-feature-in-epyc 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.
- tptacek 7y ago
  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.
  - twotwotwo 7y ago
    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?
dzink 7y ago
What if you have a disproportionality large public bounty on each algorithm?
chris123 7y ago
FUD. Bitcoin will continue to evolve, it is not static.
- fireflies_ 7y ago
  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.
HashThis 7y ago
Not long ago, we trusted RC4 and DES. We didn't laugh back in the 1980s and 1990s. But those would be crazy to use now. We can cringe 20 years out about ECC, RSA and AES.
- wbl 7y ago
  That's fake history. Deep crack was 1993 and RC4 was shown insecure in the Usenet thread that revealed it.
  - tptacek 7y ago
    Not to mention that literally the first sentence in the paper observes that DES has never been broken through cryptanalytic attack.
haecceity 7y ago
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.
- fanf2 7y ago
  Algorithm agility is a feature of most cryptographic protocols, and it is hard to do well. https://tools.ietf.org/html/rfc7696 https://tools.ietf.org/html/rfc7696
  - haecceity 7y ago
    Why is it difficult? TLS 1.3 has a much smaller set of cipher suites than previous versions. Does that help?
    - bjoli 7y ago
      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.
deleted 7y ago
[deleted]

vlovich123 7y ago

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.

mr__y 7y ago
A) debatable 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
- tptacek 7y ago
  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.
  - mr__y 7y ago
    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
    - tptacek 7y ago
      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.
      - mr__y 7y ago

ChikkaChiChi 7y ago

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?"

ofcourseianal 7y ago
One time pad is pretty fast
tptacek 7y ago
No, I don't think that's one of the cardinal rules of crypto.
Simon_says 7y ago
> less fewer

tialaramex 7y ago

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.

charleslmunger 7y ago
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.
zooko5 7y ago
> 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-attacks-on-secure-hash-functions/ 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.

amelius 7y ago

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.

tptacek 7y ago
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.
- sroussey 7y ago
  People advocating putting sensitive data on blockchains in encrypted form do not understand this.

twotwotwo 7y ago

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-playstation-work-led-to-a-big-security-feature-in-epyc 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.

tptacek 7y ago
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.
- twotwotwo 7y ago
  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?

dzink 7y ago

What if you have a disproportionality large public bounty on each algorithm?

chris123 7y ago

FUD. Bitcoin will continue to evolve, it is not static.

fireflies_ 7y ago
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.

HashThis 7y ago

Not long ago, we trusted RC4 and DES. We didn't laugh back in the 1980s and 1990s. But those would be crazy to use now. We can cringe 20 years out about ECC, RSA and AES.

wbl 7y ago
That's fake history. Deep crack was 1993 and RC4 was shown insecure in the Usenet thread that revealed it.
- tptacek 7y ago
  Not to mention that literally the first sentence in the paper observes that DES has never been broken through cryptanalytic attack.

haecceity 7y ago

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.

fanf2 7y ago
Algorithm agility is a feature of most cryptographic protocols, and it is hard to do well. https://tools.ietf.org/html/rfc7696 https://tools.ietf.org/html/rfc7696
- haecceity 7y ago
  Why is it difficult? TLS 1.3 has a much smaller set of cipher suites than previous versions. Does that help?
  - bjoli 7y ago
    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.

deleted 7y ago

[deleted]