Posted by: jonkatz | December 10, 2010

SHA-3 finalists announced

Big news in the world of real cryptography: the SHA-3 finalists were announced. (An email was sent out on the hash-forum mailing list earlier today.) The finalists are

  • BLAKE
  • Grøstl
  • JH
  • Keccak
  • Skein

(See here for more information about the competition and all the above candidates.)

I have been following the competition with interest, more as an “interested outsider” than as an expert in hash function design. Some off-the-cuff observations:

  • According to the announcement, the choice of finalists came down more to issues of efficiency than issues of security. Indeed, to the best of my knowledge there have not been any serious attacks on any of the 14 semi-finalists. Does this mean all 14 semi-finalists were really strong? Or that people didn’t spend sufficient time analyzing all the candidates? In particular, talking to some people (with more knowledge than me) over the past few months there was a sense of less activity as compared to the AES competition.
  • Given the above, NIST didn’t have much to go on, with regard to security, in making their decision. They even made what I find to be an unusual statement in their announcement: “in some cases [we] did not select algorithms … largely because something about them made us ‘nervous,’ even though we knew of no clear attack”.
  • According to the announcement, NIST consciously chose the finalists with diversity of design in mind. (I.e., they did not choose 5 finalists all sharing the same structure.)
  • Some surprises (to me): some submissions by very well-known cryptanalysts did not make it to the final round (e.g., Cubehash, Echo, Fugue, and SHAvite-3), while some by less well-known cryptanalysts did (I’ll leave you to guess which ones I mean).

On the lighter side, seems that I have won my bet…

Advertisements

Responses

  1. […] Source […]

  2. As you write, NIST didn’t seem to have much to go on with regards to security. I wonder whether they will be really able to justify their choices. Crypto still has a long way to go until we find ways to gain confidence in the security of designs.

  3. We do know of a way to gain confidence in the security of designs, and it’s called third-party cryptanalysis. This worked for the AES (all of the 5 finalists are still far from being broken), and this will work for SHA-3.

  4. Jean Philippe, I am certainly not saying that third-party cryptanalysis is a bat tool for evaluating security. In fact, I agree that given the current state of affairs this is the best way to go (and I do have a lot of respect and appreciation to the work that is being done in this field). The question is whether it is sufficient. Shouldn’t we be also looking for alternative methods for ascertaining the soundness of cryptographic designs?

    Suppose that tomorrow we wake up to a catastrophe in which AES is broken (not that I am claiming that this is likely). Would we then feel comfortable moving to the runner up? In particular, has the runner up been seriously cryptanalyzed by third parties since the AES winner has been declared 10 years ago? (I ask because I really don’t know. I did hear that Serpent had a more conservative design than other AES candidates.)

    Similarly to Jon, I haven’t followed the SHA-3 competition too closely (certainly not the most recent developments). Would it be fair to say that the majority of the non-finalists were not found to be inferior in terms of cryptanalysis (or, as NIST put it: “Security was our greatest concern, and we took this very seriously, but none of these candidates was clearly broken.”)? Could this lack of cryptanalysis be an artifact of the mutlitude of candidates? (Being a cryptanalyst, I hope you may be able to tell me whether having to consider many candidates has decreased the effectiveness of people’s ability to scrutinize specific designs more closely.)

    If this is indeed the case, then what precisely is it about lack of cryptanalysis that differentiates between the security of the candidates? (I hope that NIST’s report on the rationale for their choices will shed some light on this question). Again, it is not like I claim to have the answer to what should be done. I am just wondering whether such a (time limited) competition is the best/only way to go.

  5. In the absolute, you are right; “nobody could break it” is not a sufficient argument. But that’s all we have. Ideally, we would like to have a hash function that is simple to implement, efficient (whatever it means), and that admits (non-asymptotical) reductionist security arguments with respect to all significant notions of security. IMHO, some of the best attempts in this direction are functions like SWIFFT or VSH, and as you know they are rather limited (if I understood well, SWIFFT’s proof is asymptotical, VSH’s preimage resistance is unclear, etc.).

    Back to the SHA-3 competition: ‘Would it be fair to say that the majority of the non-finalists were not found to be inferior in terms of cryptanalysis (or, as NIST put it: “Security was our greatest concern, and we took this very seriously, but none of these candidates was clearly broken.”)?’

    It’s very difficult to say. For instance, several candidates admit “distinguishing attacks” on (some of) their building blocks. The designers argue that these are artifacts of the specific construction and sometimes even gave formal proofs to support their claims. Other would feel ‘nervous’, arguing that such attacks reduce the confidence in the algorithm (even if no one knows how to exploit them to attack the full hash). To illustrate this, a good example is Fugue: taken individually, the components of Fugue are far from being “ideal”, as they admit straightforward “distinguishing attacks”; but these seem to be very difficult to exploit to attack the hash function.

    “Could this lack of cryptanalysis be an artifact of the mutlitude of candidates?”

    I would not talk of a “lack of cryptanalysis”. There’s been tremendous efforts by cryptanalysts on _all_ of the second round candidates (but no one will publish a paper saying “I spent X month trying to attack Y, but failed”). Very advanced attacks have been discovered, and applied to some of the candidates (as “rebound attacks” or “zero-sum attacks”). Of course, the fewer candidates, the deeper the analysis, but I think that at this stage, NIST had enough information to make a good selection.

    We don’t need that SHA-3 be the most secure (or, maybe more correctly, the most confidence-inspiring) function, it needs just be good enough. The best pick for SHA-3 will be the best balance between confidence in security (also including security against physical attacks) and usability (that is, performance versatility, ease of implementation). I am confident that the five finalists include very good candidates for SHA-3, but the competition will be tough.

  6. You make it sound as if an asymptotic proof is a bad thing to have. I agree that asymptotic analysis is not always relevant/applicable to practical constructions. Nevertheless, all other things being equal, one is better off with it than without it. At the very least it provides a “sanity check” that the construction doesn’t have any flaws that result from oversight. Moreover, every asymptotic analysis can be in principle translated to a concrete one (admittedly not always with acceptable parameters – see next paragraph).

    The problem of course is that in reality ability to give a security reduction from some well established hardness assumption may come at the expense of loss in performance. Personally, I feel that paying this price may be something worth considering. But looking at the results of the SHA-3 competition, as well as at the discourse around it, it seems like performance took priority over asymptotic (or even concrete) analysis (this is just an observation, and it is not clear whether things could have been different given the current state of affairs). This is probably due to the perception that asymptotics are irrelevant to practice.

    One straightforward way to improve the situation is to design functions that satisfy specific security properties and functionalities (e.g. collision resistance, message authentication, pseudo-random number generation), as opposed to requiring a single multi-purpose construction (and additionally asking it to satisfy some ill defined properties such as being a random oracle). This has several advantages. Most importantly, it will require protocol designers to actually understand what it is about the function that would make the protocol secure. (I have heard the argument that this may be too much to ask from engineers, but are engineers actually supposed to design protocols? Don’t they mostly used protocol that have been designed by standardization bodies? And aren’t we giving too little credit to engineers here?). But another advantage, which is the one most relevant to this discussion, is that it may allow analysis and performance to co-exist.

    Personally, I have seen this happen with SWIFFT, which was designed to only satisfy collision resistance, and was quite fast. But once it was modified to SWIFFTX, which was designed to comply with all the requirements of the SHA-3 competition, it became significantly slower (to the extent of not really being competitive in terms of performance).

    I do understand that in reality a new hash function is constrained by existing standards and has to be “backwards compatible.” But I do wonder whether this is just a historical “accident,” and whether things would have evolved differently if we would have allowed different functions for different purposes.

    The result of all of this is that we still lack a theoretically sound methodology for assessing security of practical constructs. It may very well be that SHA-3 will not be broken in its lifetime. It is just unfortunate that we may never know what it was that made the chosen function more secure than the other candidates.

  7. My point is not that asymptotic proofs are bad to have (actually, I like the trade-off performance / provable security of SWIFFTX), just that they do not bring much more confidence. For example, AFAIU, a formal argument saying that any preimage attack must be exponential says nothing about the possibility of an attack with complexity (say) 2^{n-42} instead of 2^{n}.

    Several researchers previously argued that we are “asking too much” to hash functions: collision resistance, preimage resistance, pseudorandomness, RO-indifferentiablity, etc. Some believe that this can’t be achieved with reasonable speed. I tend to disagree, but that’s mostly just a matter of belief (on both sides).

    That said, I would be very much support your idea of having dedicated algorithms for each specific functionality, had we (more) efficient primitives with more convincing security reductions. But as you say, it will require some effort from engineers, and I’m not as optimistic as you are.

    “we still lack a theoretically sound methodology for assessing security of practical constructs. (…) It is just unfortunate that we may never know what it was that made the chosen function more secure than the other candidates”

    As you know better than me, no evidence of hardness does not mean no hardness. In theory, AES may be broken tomorrow, SHA-1 preimages may be found in seconds, SHA-2 may be broken as well. But facts are that we don’t even know how to break DES, let alone AES!

    I don’t think the chosen function will be more or less secure than the others. It may have a lower fraction of its total rounds broken, but I expect that all of the SHA-3 finalists will remain practically unbreakable. I would thus rephrase your statement to “it is just unfortunate that we may never know what makes these functions secure”. This seems to apply to a broader range of algorithms and problems.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: