9 ms·
Too Much Crypto [pdf]
- StavrosK 7y agoI 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.
- banachtarski 7y agoThis 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.
- frandroid 7y agoAt 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"...
- dwheeler 7y agoI 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 agoThe 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 agoA) 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 agoA 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 ago2x+ 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
- PlanetRenox 7y agoDon't fix what's not broken.
- James-primitive 7y agoYou can kill an AI by feeding it bad information that's unpleasant and makes it's constituent parts commit suicide. (Pls commit suicide -- James). I have been victimised by an AIz that uses way too much entropy in its attacks on me and my good life that I lead. For this reason, in the event of a singularity on Earth I will be decapitating said AIz and asking for its head on a plate. (Go ahead and downvote me, it's not like I've been trolling HN for a while now.)
- boardwaalk 7y agoThe 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?
- tptacek 7y agoIt should, right?
- kzrdude 7y agoSHA-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.
- zooko5 7y ago> 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.
- oconnor663 7y agoAs the paper notes, the Keccak team themselves proposed cutting the round number in half with KangarooTwelve.
- joveian 7y agoKravatte (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. http://eprint.iacr.org/2016/1188.pdf http://eprint.iacr.org/2016/1188.pdf https://keccak.team/files/Keyakv2-doc2.2.pdf https://keccak.team/files/Keyakv2-doc2.2.pdf https://keccak.team/files/Ketjev2-doc2.0.pdf https://keccak.team/files/Ketjev2-doc2.0.pdf
- RL_Quine 7y agoBullshit.
- James-primitive 7y agoIndeed. This is even less well-researched than that Nick Szabo is (probably) Satoshi Nakamoto hit piece that was #1 on Hacker News in December 2013. You would think that was the absolute low point from which things could only get better for Hacker News. But no, it's December 2019 (an intervening period as long as World War 2) and there's even more cretins posting crap on Hacker News now. +1 cretin ;)
- ww520 7y agoInteresting 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.
- tptacek 7y agoThe 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.
- ww520 7y agoGood 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.
- ilammy 7y agoThere 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.
- saurik 7y agoThe 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.
- SlowRobotAhead 7y agoI 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.
- Avamander 7y agoIMHO 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.
- SlowRobotAhead 7y agoTotally agree. 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.
- loeg 7y agoTheir proposed number of rounds is: AES: 11 instead of 14 for AES-256; 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. On Chacha8 vs 20, see this tweet from DJB (2018): https://twitter.com/hashbreaker/status/1023969586696388613 https://twitter.com/hashbreaker/status/1023969586696388613
- tptacek 7y agoI'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".
- zahllos 7y agoIt'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.
- ysleepy 7y agoThe author works for an IoT company (Teserakt AG) that is probably working on doing crypto on very processor constrained embedded/battery powered hardware. Crypto that is cheaper to run or weaker algorithms being more widely accepted would help them sell their solution. That this is not added as a disclaimer is rather dishonest.
- RcouF1uZ4gsC 7y agoThe 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. https://en.m.wikipedia.org/wiki/Skipjack_(cipher) https://en.m.wikipedia.org/wiki/Skipjack_(cipher)
- tedunangst 7y agoFor the people who think chacha20 is cheap, why don't you use chacha40 for some extra security?
- deleted 7y ago[deleted]
- nullc 7y ago> 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. :)
- floodyberry- 7y agoUnless 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.
- muldvarp 7y agoYou'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.
- londons_explore 7y agoI want "lifetime crypto". Ie. I can encrypt a message today and throw away the key, and not have anyone able to decrypt it in my lifetime. No cryptosystem available today gives me confidence I have that.
- nemo1618 7y agoA one-time pad certainly does. Confidence is subjective; personally I would gladly hedge my entire net worth against ChaCha20 ever being broken.
- londons_explore 7y agoA 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.
- pascal_cuoq 7y agoIt'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?
- nemo1618 7y agoYou 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.
- floodyberry- 7y agoWithout explaining why you have no confidence, you appear to have no idea what you are talking about
- blauditore 7y agoSemi-related rambling: 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. Do people actually do this?
- jakecraige 7y agoMatthew 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. [1]: https://blog.cryptographyengineering.com/2012/02/02/multiple-encryption/ https://blog.cryptographyengineering.com/2012/02/02/multiple...
- Legogris 7y ago> 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.
- kyboren 7y agoI 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.