MD6 Withdrawn from SHA-3 Competition

In other SHA-3 news, Ron Rivest seems to have withdrawn MD6 from the SHA-3 competition. From an e-mail to a NIST mailing list:

We suggest that MD6 is not yet ready for the next SHA-3 round, and we also provide some suggestions for NIST as the contest moves forward.

Basically, the issue is that in order for MD6 to be fast enough to be competitive, the designers have to reduce the number of rounds down to 30-40, and at those rounds, the algorithm loses its proofs of resistance to differential attacks.

Thus, while MD6 appears to be a robust and secure cryptographic hash algorithm, and has much merit for multi-core processors, our inability to provide a proof of security for a reduced-round (and possibly tweaked) version of MD6 against differential attacks suggests that MD6 is not ready for consideration for the next SHA-3 round.

EDITED TO ADD (7/1): This is a very classy withdrawal, as we expect from Ron Rivest—especially given the fact that there are no attacks on it, while other algorithms have been seriously broken and their submitters keep trying to pretend that no one has noticed.

EDITED TO ADD (7/6): From the MD6 website:

We are not withdrawing our submission; NIST is free to select MD6 for further consideration in the next round if it wishes. But at this point MD6 doesn’t meet our own standards for what we believe should be required of a SHA-3 candidate, and we suggest that NIST might do better looking elsewhere. In particular, we feel that a minimum “ticket of admission” for SHA-3 consideration should be a proof of resistance to basic differential attacks, and we don’t know how to make such a proof for a reduced-round MD6.

Tags: , , , ,

Posted on July 1, 2009 at 2:27 PM • 33 Comments

Comments

W • July 1, 2009 2:33 PM

Do similar proofs of resistance to differential attacks available for competing hashfunctions such as skein?

Bruce Schneier • July 1, 2009 3:01 PM

“Do similar proofs of resistance to differential attacks available for competing hashfunctions such as skein?”

Not really, and that’s what’s puzzling about this whole thing.

I’m not impressed by these sorts of proofs. It’s not hard to prove specific security properties about block ciphers, including resistance to differential attacks. The problem is with the model. What ends up happening is that an algorithm has a proof of security with respect to a class of attacks, and then the attacker responds with an attack that’s not in that class. So any proof against differential attacks may not include everything that cryptanalysts call “differential” and certainly will not include other attacks.

Proofs of security are overrated.

Clive Robinson • July 1, 2009 5:22 PM

@ Bruce,

“… given the fact that there are no attacks on it …”

Hmm, that we know of (yet).

Ron Rivest is generaly credited with being “one of the brighter bulbs in the corridor” as well as a “class act”. It is entirely possible he has seen something new from looking at ways to attack the other entrants.

I guess we will find out one way or the other at some point in the future

Oh and withdrawing in this way probably enhances his reputation more than any loss from withdrawing his entrant.

Muffin • July 1, 2009 5:25 PM

“other algorithms have been seriously broken and their submitters keep trying to pretend that no one has noticed”

I haven’t been following the contest, but I’m curious – which?

Brian • July 1, 2009 6:04 PM

I must admit I’m a little surprised by this. I don’t know a lot of cryptographers that put stock in proofs of security, and I honestly didn’t imagine Ron Rivest as one who would. As Bruce pointed out, there are remaining algorithms that don’t have that proof either, and MD6 has suffered no actual attacks. Why Rivest is withdrawing MD6 is a mystery to me…

Bruce Schneier • July 1, 2009 6:23 PM

“Why Rivest is withdrawing MD6 is a mystery to me.”

The problem with MD6 is that, compared to other submissions and even SHA-2, it’s very slow. That consideration alone would have prevented it from winning, although it might have made it into the next round on the strength of its design and designers. (That’s something I would certainly give consideration to.)

But I admit that I don’t understand it, either.

dolphinling • July 1, 2009 6:54 PM

@ Bruce:
“Proofs of security are overrated.”

What about proofs of security of the form “If you can (e.g.) find a preimage of this hash, then you can also solve the Diffie-Hellman problem for a certain set of related integers”? My cryptography teacher at UVM showed us one hash with (I think) that particular property—too slow for routine use, of course, but still, I’d expect that to be the kind of promise hash designers would be working towards.

@Muffin:
See the SHA-3 Zoo: http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo

Randall • July 1, 2009 7:58 PM

I want to float an argument for defaulting to a tree mode for Skein-512. Aside from the tricky-to-exploit multicore parallelism, there’s SIMD parallelism in current and new processors that’s easier to exploit. It’s already used in crypto libraries like Crypto++, and to speed up some other SHA-3 candidates.

On today’s processors you can get 10 cpb doing two Threefish-512 encryptions at once in the 128-bit SSE registers. (That’s a measurement, not an estimate: the SSE2 implementation of Skein for 32-bit processors gets 20 cpb by doing two Threefish encryptions, using the results of one and throwing the other away.)

Intel’s Sandy Bridge processors, due out in late 2010, will have 256-bit registers handling four Threefish encryptions per core at once. AMD is also planning to support the same 256-bit instruction set (AVX) as Intel (and a 128-bit instruction set with a rotate instruction, which may be faster for Threefish). Intel’s Larrabee GPU — if it ever comes out — will have “many” Pentium cores, each with 512-bit registers handling eight encryptions per core at once.

One downside to a tree mode is the cost in memory on smartcard-ish devices. One approach is to use a serial mode for Skein-256 — already the low-memory variant — and a tree mode for Skein-512.

Grande Mocha • July 1, 2009 8:05 PM

Technically, Ron did not withdraw MD6. Read his message carefully. He indicated that MD6 could not meet his own standards of security while beating the serial performance of SHA-2.

Alice Bobson • July 1, 2009 11:28 PM

Ron is saying something more in his latest post to SHA-3 hash forum, talking about “clean” submissions.
He is going in the line of the recent post from Keccak designers, claiming that AXR designs in “clean” designs will be much more slower than designs that avoid additions as a part of their nonlinearity source.

It seems to me that as the competition goes on, these types of arguments (the resistance against side channel attacks) will be used more frequently against hash functions based on AXR.

Clive Robinson • July 2, 2009 12:57 AM

@ Alice Bobson,

“It seems to me that as the competition goes on, these types of arguments (the resistance against side channel attacks) will be used more frequently against hash functions based on AXR.”

I certainly hope so.

The AES has been slated a number of times due to issues to do with loop unrolling and cach attacks making key recovery practical via timing attacks.

Side channel attacks in the various forms are perhaps the most (if not only) practical attacks against online crypto systems currently.

Alice Bobson • July 2, 2009 2:44 AM

@Clive Robinson

Well – the primary goal (and use) of crypto hash functions is to be collisiona and (second)preimage resistant, and there we do not use any secret keys.
Only the HMAC constructions use secret keys, and side-channel attacks for HMACs using AXR construction although effective, are much less powerful as side-channel attacks on e.g. AES.

Protection of hash implementations against side channel attacks is important – but not so practically important as the protection of block-ciphers against side-channel attacks.

Eve wears a badge • July 2, 2009 9:51 AM

@Alice Bobson

I believe you are ignoring the real danger of a side channel attack on a HF. The real danger is that the HT will leak the input and/or output details to an attacker listening to the sidechannel. This is especially deadly since passwords/PK are commonly hashed to protect them.

Of course breaking HMACS are nice as well.

Alice Bobson • July 2, 2009 11:29 AM

@Eve wears a badge

Hi. I am not ignoring the real danger of a side channel attacks on Hash Functions (HF). I am just giving them a realistic weight (and that is: low weight). Why? Because NIST have done the same thing too.

Read carefully NIST call for SHA-3 competition! Can you find a single explicit mentioning for the need of resistance against sidechannel attacks of submitted SHA-3 candidate hash functions?

I repeat: It is important issue, BUT not so important. Imagine what will happen in 2012, 2013, 2014, …, if we have SHA-3 resistant on sidechannel attacks BUT slower or equally fast as SHA-2!
My answer: Probably MD5 will still be considered as acceptable alternative instead of SHA-1, SHA-2 or SHA-3.

Clive Robinson • July 2, 2009 4:02 PM

@ Alice Bobson & Eve wears a badge,

As Eve has pointed out there is a risk when hash functions are used for other security related functions such as the case she mentions of password/ticket protection.

There is also the HF use for “entropy spreading” (which I strongly disaprove of). Any side channel attack on the HF would effectivly enable the entropy pool or source to be seen at some level.

HF’s also get used for other activities such as crypto primatives for stream and block ciphers (think pre whitend CTR or Fiestel round structures etc).

The fact that NIST has yet again ignored the current most likley threat against system security at all levels is a large open question that at some point will have to be debated and answered.

Writing it off as an “implementation issue” or “to obvious to mention” or worse still “a casualty of the ‘need for speed'”, is quite frankly a bit of an eyebrow raiser.

With regards “the need for speed” in many cases hash functions are more than fast enough for the common uses they are put to. In fact you could argue that for some very popular applications they are very much to fast (password protection etc).

NIST also apear to still be “hung up” on “small model” and embedded microprocessors. To be quite honest I don’t realy care about single chip or 16bit or less microprocessors. For two main reasons,

1, By the time SHA3 gets accepted and then considered for new products, new designs will be mainly 32bit.

2, Invariably there are other more cost effective engineering soloutions to the issues of crypto which also in the process get rid of many side channel issues.

Arguably NIST’s hangup in this area is to do with the likes of Smart Cards and RFIDs. Well as history has shown over and over again the silcon suppliers and their purchasors want “low cost” as the primary requirment so “security by obscurity” wins 9 time out of ten.

And not being nasty to NIST or the entrants but history has also shown we badly under estimate just how fast these “standard methods” age. And instead of having just one winner a standard framework with two or three initial dropin HF’s would serve industry better.

Randall • July 2, 2009 7:22 PM

@Clive: Maybe one of the best things NIST and other standards bodies could do is try to ensure there’s a less painful migration path next time we have to change crypto primitives.

Randomized hashing is another protocol-level change that could extend the useful life of today’s hash functions. It would mean fewer applications would depend on collision resistance.

Alice Bobson • July 2, 2009 9:51 PM

@Clive Robinson

“And instead of having just one winner a standard framework with two or three initial dropin HF’s would serve industry better.”

I really like this part of your post. It is probably the most optimal approach. In 100s of scenarios and protocols where cryptographic hash functions are used – 2 or 3 SHA-3 functions can cover “all” those areas more effectively: Speed, small size, resistance against side-channel attacks, …

But I think there are some SHA-3 submissions that offer all those properties in one single primitive.

Cheers.

Paeniteo • July 3, 2009 2:36 AM

@Clive: “a standard framework with two or three initial dropin HF’s would serve industry better”

I’m not sure whether to fully agree with that. More cryptographic primitives mean more costly implementations, more room for implementation mistakes and complicated algorithm choice / negotiation (think: downgrading attacks in protocols).

Anyway, one could argue that your wish is already somewhat true. We will have many new hash functions as a result of the competition and I’m quite sure that all finalists will be solid choices for actual implementations – just as they have been with AES.

@pe • July 3, 2009 4:00 AM

“other algorithms have been seriously broken and their submitters keep trying to pretend that no one has noticed”

Is this your opinion? Are there any proves for your statement? Sources?

Jonadab the Unsightly One • July 3, 2009 6:34 AM

The problem with MD6 is that, compared to other
submissions and even SHA-2, it’s very slow.

In other words, when he says “MD6 isn’t ready”, what he really means is, “the world’s computing systems aren’t ready for MD6”. And that’s a valid point. For a cryptographic algorithm to become widely deployed, it has to be usable in practice by the computer systems that are out there.

I mean, if I design a block cipher that uses a thirty-two gigabyte key, nobody’s going to give it the time of day, no matter how secure it might be.

By withdrawing it with the words “not ready”, he leaves open the possibility of submitting it for consideration later (say, for SHA-4).

Luna • July 6, 2009 7:59 PM

@Clive Robinson

” 1, By the time SHA3 gets accepted and then considered for new products, new designs will be mainly 32bit. ”

Yes, that is true. Actually, in this moment ARM based products outnumber Intel or other processor base systems with ration 3:1 and that trend is continuing as iPhone, Android and other products appear with rapid tempo. BUT, look at most of the SHA-3 submissions: their speed in 32-bit mode is 2-3 times slower than SHA-2.

” 2, Invariably there are other more cost effective engineering solutions to the issues of crypto which also in the process get rid of many side channel issues. ”

My standing is that if the focus for SHA-3 is put on resistance against side-channel attacks (not on the speed), we will have a SHA-3 that is “tank” instead of having a Formula 1 Ferrari.

Scott Contini • July 7, 2009 12:16 AM

I agree with Rivest’s group that proofs of resistance to differential attacks are highly desirable for the eventual choice of the SHA-3 algorithm. It is worth noting that MD6 is not the only candidate that attempted to provide such proofs. Others include ECHO, Fugue, and Grøstl. Another interesting design is SWIFFTX, which accomplishes much more than a proof of resistance to differential cryptanalysis: it has an asymptotic security proof that finding a collision is at least as hard as finding short vectors in cyclic/ideal lattices in the worst case. This is presumably a hard problem, which would imply in the asymptotic case that finding collisions in SWIFFTX is also a hard problem (i.e. the proof is not restricted to certain types of attacks such as differential cryptanalaysis).

There are others algorithms submitted with proofs that I have not mentioned. In all honesty, I have not read these proofs (that’s why I used the word “attempted” above), but I do appreciate what they are trying to do.

It is easy to say proofs are overrated and point out examples where the proofs weren’t enough to prevent a design from being cryptanalyzed. Let me emphasize that I am not trying to suggest that proofs preclude the need for cryptanalysis. But what I am saying is a design with a proof that resists cryptanalysis attempts is much more desirable than a design with no proof that resists cryptanalysis.

The science itself needs to advance. The idea of presenting an algorithm and judging its trustworthiness mainly based upon the lack of cryptanalysis failed pretty badly with algorithms like SHA1 and MD5. The problem was that it was easy to design something that nobody knew how to analyze and resisted attack for a long time, but once someone figured out how to analyze it, the algorithms were found to have quite serious flaws. So the first question I have in my mind for any new potential hash function is “Given that we have very little time to analyze the algorithm, why should I believe that it will not suffer the same fate that SHA1 and MD5 did?” A proof of resistance to the types of attacks that worked on MD5 and SHA1 earns credibility points for me.

I want to make one last point. When NIST had the AES competition, it came down to five finalists: MARS, RC6, Twofish, Serpent, and Rijndael. There were certainly some disagreements about what was most important in deciding the winner: performance on low-end platforms, simplicity, flexibility, security margin, etc…. But only one candidate ranked well on all of these categories and also provided a security proof (under very reasonable assumptions) of resistance to differential and linear attacks. Yes, it was Rijndael — the eventual winner. While it is not clear how important those proofs were considered back then, it should be becoming more clear how important they are now, given how hash functions submitted to SHA3 took Rijndael-type design strategies. So in short I say that not only did NIST made the right decision of choosing Rijndael as the AES, but it was at least one large step above all other candidates because it had the proofs in addition to having the good engineering properties. I hope the eventual SHA-3 is some algorithm that stands out above the others just like Rijndael did for the AES.

(Remark: I had some connection with an AES candidate, but I have not at all been involved with any SHA-3 candidates)

Luna • July 7, 2009 4:09 AM

@Scot

“There were certainly some disagreements about what was most important in deciding the winner: performance on low-end platforms, simplicity, flexibility, security margin, etc…. ”

Exactly the same principles are considered also in the SHA-3 competition but they are accompanied by the following request too: “NIST expects SHA-3 to have a security strength that is at least as good as the hash algorithms currently specified in FIPS 180-2, and that this security strength will be achieved with significantly improved efficiency”. Note: SIGNIFICANTLY IMPROVED EFFICIENCY!!!! And taking this request into account, none of MD6, ECHO, Fugue, Grøstl or SWIFFTX offer significantly improved efficiency. I think Ron is specifically referring to this part of SHA-3 call.

“But only one candidate ranked well on all of these categories and also provided a security proof (under very reasonable assumptions) of resistance to differential and linear attacks.”

In this competition there are also few candidates ranked well on all of these categories that also provide security proofs of resistance to differential attacks.

Clive Robinson • July 7, 2009 4:24 AM

@ Luna,

“My standing is that if the focus for SHA-3 is put on resistance against side-channel attacks (not on the speed), we will have a SHA-3 that is “tank” instead of having a Formula 1 Ferrari.”

Arguably a tank is a much more effective vehical than an F1 car and importantly no where as easy to break by incorect usage.

However most if not all theoretical attacks against modern crypto systems are just that theoretical, they are not practical to implement either now or in the foreseable future.

Or put it another way do I care if my theoretical security went down from say 2^192 to 2^182?

Sure it’s a thousand times weaker which sounds serious, but the margin to a practical attack is still probably up around 2^80.

Do I care that timing based side channel attackes across a network have been shown to break AES?

Most definatly YES, because it’s not theoretical it’s practical and it has been done in a fairly short time on comodity PC’s

From a security perspective what worries me are,

1, Poor implementations
2, Difficult if not impossible to upgrade systems.
3, Side Channel attacks
4, Known plain/cipher text attacks caused by proprietry formats in office etc products.

The first two can be significantly improved by a well thought out framework which most if not all code cutters and engineers can follow.

The last can be solved by the use of appropriate cipher modes and simple techniques (plain text rotation and padding followed by compression).

The hard one to solve even for security proffesionals is the third one “side channel” attacks in their various classes and forms.

My personal feeling is the number one cause of side channel attacks is “efficiency”.

To be “efficient” systems need to be shared or multi-functional. This gives rise to various techniques being employed to reduce cycle count such as loop unrolling and code optomisation by the compiler. Little or no thought has been given in the past to branch or power balancing. With the result that data or power timeing starts to revel things like plaintext or keytext.

Asside from the usual EmSec (TEMPEST) limiting of signal energy and bandwidth, you also must must must clock data in and out of the cipher system on any online system irrespective of what cipher class is used.

Luna • July 7, 2009 5:35 AM

@Clive

I can agree with you, but I think you are over-emphasizing the need of keyed hashing over non-keyed hashing. For non-keyed hashing you do not need a “tank”, but for the race (fast hashing of huge documents, huge databases, huge files, huge partitions, huge hard disks …) you indeed need F1 racer.

That is why we still have MD4 and MD5 in many industrial pieces of software, although they have been practically broken long time ago.

Imagine the digital forensics practice around 2015, when 1, 2, 4, .. TBytes hard disks will be in common use. The team of FBI agents have seized the hard disk from a child-pornography suspect and in order to properly follow the procedures and make a proper court case they have to produce a hash value of the entire disk (or several hash values from the entire disk).

Hehe, imagine that they are using “tank” SHA-3??!?! (that is resistant against side-channel attacks??!?!?! )

How much time would they spend producing those hash values? 24 hours, 36 hours, …

Clive Robinson • July 7, 2009 9:17 AM

Luna,

What you need for documents is “non repudiation” that is good for the effective life of the document, which could be 100years or more for a lease on a property. Or 50 or more years for complex comercial contracts (look up PPI/PFI for some real heavy weights on that score).

For forensics what you need is a method by which it can be shown that the copy “is as the original” to the degree required by a court (which lets face it these days is not a very high standard at all).

Both of these requirments effectivly require not just the contents be the same but the same order, however the speed by which they are hashed is not actually that important providing it’s less than it takes to make a cup of coffee or “do lunch”.

However for most documents the size is usually limited to less than a thousand pages (4 million chars of text) and for these speed is of little or no value compared to the security asspects.

The next step up is pictorial information and this can vary but realisticaly 300bpi 24bit colour is sufficient giving aprox .25Mbyte/Sq Inch with most images being 6×4 or less you are looking at a 6Mbyte raw image which normaly would be compressed or encoded to reduce it’s size down to as little as 1Mbyte.

Likewise audio and video, high quality MP3 is around 1Mbyte/min and video can be as low as 2.5Mbyte/min depending on what type of image (a 40min cartoon can compress down to 1Mbyte/min or less with little trouble). So even with a movie weighing in at just under 5Gbyte you are still not stretching existing hash functions

Most databases although apparently large can usually compress down losslessly by significant amounts (10:1) due to the nature (or lack) of normalisation.

However as you note storage is on the up and up and by 2015 you would be looking at 32Tbyte in both HD’s and SD/MMC/etc Flash drives as potentialy the upper limit (Oh and Flash memory presents quite a bit of a problem for both security and forensics due to redundancy and wear leveling algs inherent in their functioning and the fact that it inherantly contains a CPU the functioning of which is “unknown”).

However the raw performance of CPU’s will not have gone up by as much nor will most other forms of backup device.

The need for hashing such large quantities of data in one go is actually quite small and is usually not Real Time. If it is it can (should) easily be carried out on either special purpose hardware, or on multiple CPU cores (providing the hash function can be made to run that way).

So the need for your F1 hash is actually quite small and actually fairly easily solvable for most cases.

However as I noted before hash functions have a habbit of being used for other parts of crypto where any side channel weakness would criticaly effect the whole system (including random hashes). Very frequently these are “online” uses where timing attacks are easily possible, and as a comms engineer I’m acutely aware of these issues (and lack of realistic solutions in a comercial environment).

I guess you and I are not going to see eye to eye on this.

However there was one area of forensics you neglected to mention where F1 hashing would be not just desirable but critical and that is the “real time”, “full packet” logging of network traffic at the likes of a major node or portal.

And yes I can see the rising need for this as CyberCrime becomes a higher priority and major node logging standard practice (though what the heck we do with the data gathered is another issue all together).

Which is why I feel we need to look for different hash functions tuned for specific applications, after all most of us drive different types of car and you would not use either an F1 or tank for day to day activities in much the same way you would not use a motorbike to move house.

Just a few of us need HGv’s tanks or F1’s to do our jobs and that is also the case for HFs.

Alice • July 12, 2009 10:30 AM

“I don’t know a lot of cryptographers that put stock in proofs of security, and I honestly didn’t imagine Ron Rivest as one who would.”

You mean proofs of security for primitives? Because for constructions the situation is completely different. For instance, proofs of blockcipher modes of operation are widely seen as a must for inclusion into standards, I’d say. GCM and OCB have proofs, for example. So do submissions to IEEE P1619.2, AFAIR.

Gavin • July 28, 2009 11:43 AM

@Luna
We will always be able to hash faster than our non-volatile storage will be able to give us data.

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.