7 ms·
Why Keccak is not ARX
- dchest 9y agoShots fired. Here's an tweet from Jean-Philippe Aumasson, one of the authors of BLAKE(2) (uses ChaCha ARX construction) and NORX (uses modified ChaCha replacing addition with an approximation based on XOR, AND, shift operations): "where @KeccakTeam misses a big point: MD5 and SHA-1 got broken because of Boolean operations (AND/OR), not because of ARX operations" https://twitter.com/veorq/status/910255284920180736 https://twitter.com/veorq/status/910255284920180736
- projectant 9y agoOk but, in reply to that tweet, one point keccak.team make, which seems valid for non-classified cryptanalysis, is that researchers don't invest time in trying to analyse ARX because the propagation of addition makes it too complicated. One thing I got from that is that ARX designs are less likely to be broken, not because they are necessarily more secure, but because ARX is often less analysed than designs which yield more concise mathematical representations.
- gcp 9y agoI think there's an implication here of "less likely to be broken by public research".
- mfukar 9y agoThat would be getting causality backwards.
- gcp 9y agoI have no idea what you mean.
- SkyMarshal 9y agoExactly, ARX's less analyzed complexity is a potential information asymmetry arbitrage for serious attackers.
- Confiks 9y agoShots fired indeed, although the 132-character argument is a bit of a straw man; the original argument was that using ARX operations in cryptographic primitives makes it harder to analyze the primitive, regardless of whether the actual weakness is in a boolean or an ARX operation.
- npscalar 9y agoAgreed. No contradiction. keccak.team does not say ARX is broken, only harder to analyze (and slow in HW, and getting obsoleted).
- raverbashing 9y agoWell, AND and OR "lose information" more than XOR x.0 is 0 and x+1 is 1 (to use combinational logic notation) Now XOR(x,y) depend on x and y and there are no values that cause the other value to be ignored I also think the point they make about speed is kinda picking at straws, it's valid for an FPGA, but not so much for a CPU
- crb002 9y agoAm I the only one that remembers coding Autocad Object ARX?
- dianthrow 9y agoARX in this case is referring to Add Rotate XOR, which is a common construction for hash functions. You are referring to the language.
- iaabtpbtpnn 9y agoIs ARX a common term in the literature? I have never seen it used before this post (though I'm not exactly up to date on the latest crypto...)
- cmrx64 9y agoyes. https://www.nist.gov/sites/default/files/documents/2016/10/18/perrin-paper-lwc2016.pdf https://www.nist.gov/sites/default/files/documents/2016/10/1... https://www.cosic.esat.kuleuven.be/ecrypt/courses/albena11/slides/nicky_mouha_arx-slides.pdf https://www.cosic.esat.kuleuven.be/ecrypt/courses/albena11/s...
- nullc 9y agoThis kind of marketing approach lowers the world's collective intelligence. Keccak is a good enough construction that it doesn't need to be promoted with low quality FUD.
- jameskegel 9y agoIs there marketing when it comes to hashing? That's absurd; it seems more like a hard stop being put to an unfair comparison.
- gopalv 9y ago> Is there marketing when it comes to hashing? Hashing is pretty much a market for lemons - the adopting user is confronted by a complex math they don't understand and there is a definite problem if you drive out with the wrong hash function. And there is no way to tell without actually being miles down the road when you find out whether it was a peach or a lemon. The choice by a user might come down to the same sort of vague arguments in a used car lot - "I hear Hondas don't break down much". There's always some "academic influencing" to do more research based off your own papers, which in turn drives more grants to your own branch of research. At least that's what I read off the following quote > "We feel that the cryptanalysis of more structured designs such as Rijndael/AES or Keccak/SHA-3 leads to publications that provide more insight."
- baby 9y agoThe final line refers to agl' "maybe skip SHA-3" blogpost. I think there is a lot of FUD about SHA-3 (including SHAKE) being too slow for mortals to use, I'm guessing the Keccak team is pushing back with some marketing. Honnestly this is how the world works. Nobody understand anything about crypto and people take decisions based on standards and public opinions (which are often based on articles and blog posts). If you want your primitive to have some weight, you have to give people an excuse to use it.
- gcp 9y agoBad press can kill a primitive even if it's incorrect. The Keccak guys had this happen to them with Noekeon. They're still sore over it, presenting this about 10 years later: https://www.cryptolux.org/mediawiki-esc2010/images/7/7a/Noekeon-ESC.pdf https://www.cryptolux.org/mediawiki-esc2010/images/7/7a/Noek... To be honest, if I'd design something this elegant, and nobody considers if because of an irrelevant attack, I'd be very sore and alert for it happening again, too.
- powera 9y ago"But even software ARX gets into trouble when protection against power or electromagnetic analysis is a threat." - I still don't get this. If attackers have physical access to your machine, you should consider it compromised. Switching from SHA2 to SHA3 is irrelevant.
- cakoose 9y agoEM radiation and power draw patterns from your device can leak information about what the device is doing. The NSA takes this stuff seriously: https://en.wikipedia.org/wiki/Tempest_(codename) https://en.wikipedia.org/wiki/Tempest_(codename) There are situations where an attacker doesn't have full physical access to a device but can still observe EM radiation. For example, someone sitting next to you with an EM receiver, observing emissions from your 2FA token.
- xoa 9y ago>If attackers have physical access to your machine, you should consider it compromised. This bit of "wisdom" dates back to the very, very old days when security wrt computers was primarily a consideration for servers in physically secure locations. It is utterly obsolete, and every more so with each passing year. HSMs, CPU-level trusted modules, etc. have long since been a thing, as for that matter has even basic software measures like FDE. All exist in part or in whole to help with certain kinds of physical access. It is not in fact straight forward, reliable or for most attackers even possible to pull bits directly off a well designed physically secure chip with an STM or whatever. I don't think looking back the actual weaknesses in MD5/SHA were related to ARX, but I'm not equipped to judge whether ARX might introduce TEMPEST related issues. It is not a fundamentally invalid consideration however. Side-channel attacks are one of the most classic and fiendishly difficult issues in cryptography and EM emissions are a known domain problem that can't always be solved merely via use of shielding. It's better even then to have it considered right down the primitive level. Layers and all that.
- aidenn0 9y agoThere are plenty of real-world examples that are hardened against physical access; smartcards are the most ubiquitous example. You ought not be able to recover key material from a smart card just by analyzing the power-draw, or you could skim chips just as easily as stripes.
- snakeanus 9y agoThe old site from the keccak team was nice, light, easy to use (you could easily find the paper or post that you wanted) and cute. The new one can't even be accessed with js disabled. Why that huge step backwards? And referring to DJB just by his twitter handle, seriously?
- baby 9y agoI like the new site. It feels more organized to me.
- drxzcl 9y agoI’m guessing the article was edited, because now it says “Daniel J. Bernstein”.
- deleted 9y ago[deleted]
- ghusbands 9y agoFor better or worse, javascript (enabled) is now an expected feature in all browsers, just like HTML and CSS; if you browse with it disabled, you can expect many things to break and don't really have cause for complaint.
- minitech 9y ago> just like HTML and CSS And yet if you browse this website with CSS also disabled, you get to enjoy the content without the pointless, distracting, time-consuming, and resource-wasting full-page second loading indicator (the browser already includes one!) and animations.
- snakeanus 9y ago> is now an expected feature in all browsers If you use the tor browser you are actually expected to have it disabled.
- pwg 9y agoIn the case of this site, disabling stylesheets will let you read the article while keeping JS disabled.
- trapperkeeper74 9y agoThere is a subtle cargo cult fallacy that occurs in many crypto construction competitions: that resource light (time, RAM & operations) in hw/sw is "good." Certainly, minimum performance is necessary but being too cheap means brute-forcing is also cheaper. I wish resource-adaptive algorithms that require a minimum of RAM and ops in both hw and sw optimized implementations a-la scrypt were the rule, not the exception. State actors can easily afford ASIC AES and SHA2 brute-force farms, and that's a concern, especially with monocultural recommendations to "always use AES/SHA2." Now that Keccak's been chosen as the basis for SHA3 in-lieu of more hw expensive alternatives like ECHO, the cost of cracking has been reduced for future scenarios. Do we really want to slash the security margin for a modest bump in runtime performance?
- baby 9y agoBrute force is irrelevant in hashing. The faster the better. PS: this is because the complexities for attacks are too high. For SHA-3-256 you need 2^128 operations to approach finding a collision. Whatever your speed you will never reach this amount of computation (or storage).
- Dylan16807 9y agoWhen one hash is a billion times too fast to securely store passwords, and another hash is ten billion times too fast to securely store passwords, the speed difference doesn't matter. All the hashes you'd care to look at are within an order of magnitude of speed. They all need to be repeated a very large number of times to fight brute forcing. Using more repetitions for a faster hash is so utterly trivial it's not even worth mentioning in the context of security. There is zero difference in security margin from the speed of a hash. And yes, memory-intensive algorithms are good for passwords, so you shouldn't be caring about normal hashes at all.
- tptacek 9y agoYou've confused password hashes with general-purpose cryptographic hashes. The latter is a building block of the former. SHA-3 is the latter: a general-purpose hash.
- baby 9y agoNote to admins: should probably add "(SHA-3)" to the title for the laymans :)
- nieksand 9y agoIf the authors happen to read this... Please, please darken your font color. The contrast is so bad that it makes my eyes hurt. I actually had to pop dev tools and tweak your css to make this site readable.
- grzm 9y agoYou might contact them directly via the address listed on their About Us page.
- topbagsvk 9y agoYou shouldn't be caring about normal hashes at all - http://www.handbagsbing.com http://www.handbagsbing.com
- amelius 9y ago> (...) (crypt)analyzing ARX, despite its merits, is relatively unrewarding in terms of scientific publications: It does not lend itself to a clean mathematical description and usually amounts to hard and ad-hoc programming work. A substantial part of the cryptographic community is therefore reluctant to spend their time trying to cryptanalyze ARX designs. We feel that the cryptanalysis of more structured designs such as Rijndael/AES or Keccak/SHA-3 leads to publications that provide more insight. Ok, but this also holds for possible attackers.
- gcp 9y agoThe nuance that's being made here is that the public cryptanalytic results we have are from researchers that need to publish. However blackhats (be it government or private) have no such need. Thus, they do not care if the analysis is elegant or neat. This means that ARX functions will have less published analysis, but may still be successfully attacked. This isn't even a new argument they're making here. It's been well understood that simple cipher designs are better, because they are easier to understand. If you can understand it well, yet not break it, that gives confidence. If you don't understand it, it might break as soon as you do.
- Confiks 9y agoWhile security by obscurity might be a valid security layer in some systems [1], it rarely is considered a good one when designing cryptosystems; Kerckhoff's principle [2] is usually adhered to thoroughly. [1] https://danielmiessler.com/study/security-by-obscurity/ https://danielmiessler.com/study/security-by-obscurity/ [2] https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle
- baby 9y agoThere are two schools: * make your cipher complicated, so that analysis and attacks are hard * make your cipher easier to analyze and attack The second one usually brings more confidence in the strength of the algorithm after a long period of peer review and cryptanalysis. PS: not sure but I think I remember reading that Ketje was designed specifically to make theoretical attacks and analysis easier: https://keccak.team/ketje_contest.html https://keccak.team/ketje_contest.html
- Cut_N_Paste 9y agoAs an aside, I coded a Keccak implementation in JavaScript if anyone is interested. It was a great learning experience, and I've tried to comment the code thoroughly. https://github.com/jeffallen6767/keccak-p-js/blob/master/src/keccak.js https://github.com/jeffallen6767/keccak-p-js/blob/master/src... Previous to this I did sha256, and I have to say that the Keccak algorithm was a bit easier to reason about ( as to what it was doing at the bit level, and why )...at least it was for me. https://github.com/jeffallen6767/sha-256-js/blob/master/src/sha256.js https://github.com/jeffallen6767/sha-256-js/blob/master/src/...