Beta

Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

SHA-3 Second Round Candidates Released

Soulskill posted about 5 years ago | from the narrowing-the-field dept.

Encryption 62

Jeremy A. Hansen writes "NIST just announced their selections for algorithms going to the second round of the SHA-3 competition. Quoting: 'NIST received 64 SHA-3 candidate hash function submissions and accepted 51 first round candidates as meeting our minimum acceptance criteria. We have now selected 14 second round candidates to continue in the competition. Information about the second round candidate algorithms will be available here. We were pleased by the amount and quality of the cryptanalysis we received on the first round candidates, and more than a little amazed by the ingenuity of some of the attacks. ... In selecting this set of second round candidates we tried to include only algorithms that we thought had a chance of being selected as SHA-3. We were willing to extrapolate higher performance for conservative designs with apparently large safety factors, but comparatively unforgiving of aggressive designs that were broken, or nearly broken during the course of the review. We were more willing to accept disquieting properties of the hash function if the designer had apparently anticipated them, than if they were discovered during the review period, even if there were apparent fixes. We were generally alarmed by attacks on compression functions that seemed unanticipated by the submitters.'"

cancel ×

62 comments

Decode this! (-1, Offtopic)

Shikaku (1129753) | about 5 years ago | (#28815489)

d008960fa6b395dca1c8362165bb31be

Re:Decode this! (1)

FooAtWFU (699187) | about 5 years ago | (#28815531)

"First Post".

Don't attack the encryption: attack how it's used!

Re:Decode this! (0)

Anonymous Coward | about 5 years ago | (#28815597)

You fail, google came up with "first post" not "First Post". Please hash before you post, or google :P

Re:Decode this! (-1)

Anonymous Coward | about 5 years ago | (#28815577)

d008960fa6b395dca1c8362165bb31be

We're talking about hash functions here, buddy.

Re:Decode this! (1)

Shikaku (1129753) | about 5 years ago | (#28815615)

e30830f3776f02798a92a2a7a2a6bce455b28e18

It would be less funny and harder to decode if I did this version.

Re:Decode this! (1)

Goaway (82658) | about 5 years ago | (#28815623)

MD5 isn't a hash function now?

I was a little worried (3, Interesting)

Omnifarious (11933) | about 5 years ago | (#28815513)

I was a little worried by the plethora of submissions. I was worried it would take them forever to decide. But luckily they've been rather ruthless in culling for the third round. Given the data available on the The SHA-3 Zoo [tugraz.at] they chose wisely.

Personally, I think Skein [skein-hash.info] is interestingly feature rich, which both worries and intrigues me. Looking it appears that all the features are built on a core in which the real security lies, so I'm not too worried. Skein's core in fact appears to be extremely simple.

Re:I was a little worried (3, Funny)

OverlordQ (264228) | about 5 years ago | (#28815551)

Well Bruce Schneier helped write it, this is the same man that once decrypted a box of AlphaBits [schneierfacts.com] .

Re:I was a little worried (4, Interesting)

Omnifarious (11933) | about 5 years ago | (#28815611)

I consider Bruce Scheier as a cryptographer to be sort of like Carl Sagan as an astronomer. I think he is a competent cryptographer, but I think he has much greater value as a person who can speak cogently about the issues surrounding cryptography.

In this case, my guess is that he led the overall vision of how Skein should work but that the other people who worked on the algorithm filled in the details. In particular, I strongly suspect that Niels Ferguson is principally responsible for the core algorithm. Of course, pulling apart any particular collaboration and looking for the efforts of individuals can be tricky and error prone at best.

Re:I was a little worried (0, Offtopic)

Threni (635302) | about 5 years ago | (#28816999)

> I consider ...I think...my guess...I strongly suspect

Yeah, thanks for that.

Re:I was a little worried (0)

Anonymous Coward | about 5 years ago | (#28820593)

"I consider Bruce Scheier as a cryptographer to be sort of like Carl Sagan..."

Nice, he smokes too? :)

Re:I was a little worried (0)

Anonymous Coward | about 5 years ago | (#28815869)

I c

Re:I was a little worried (0)

Anonymous Coward | about 5 years ago | (#28816063)

Well Bruce Schneier helped write it, this is the same man that once decrypted a box of AlphaBits [schneierfacts.com] .

I think we're safe until he figures out how to decrypt cheerios.

Re:I was a little worried (4, Interesting)

mTor (18585) | about 5 years ago | (#28815627)

Skein is getting a lot of attention because Bruce Schneier is one of it's authors. It's a fine algorithm. Personally, after going through a bunch of them, I like BLAKE [131002.net] the best since its extremely simple and relies on old and proven functions that have withstood the test of time. Not to mention that it's extremely fast. I also like Blue Midnight Wish. I think the NIST will pick one of these three.

Re:I was a little worried (3, Interesting)

Omnifarious (11933) | about 5 years ago | (#28815721)

The thing I like about Skein is its tree mode. I've been working on a parallelizing version of sha256sum to see if I can speed up the generation of hashes 4-fold with my dual-core dual-processor system.

I also like the ways you can make it unique for a given usage. This will help make it more resistant to various kinds of attacks when used in particular applications and mitigate the effect of certain kinds of algorithm weaknesses if they're discovered.

But yeah, there are other candidates, and I'm more interested in the highest possible quality algorithm coming out of the process than I am in having my particular horse win.

Re:I was a little worried (3, Informative)

Skuto (171945) | about 5 years ago | (#28816699)

>The thing I like about Skein is its tree mode.

Pretty much every hash in the competition can work in tree mode. Not all submitters defined a tree mode, but that shouldn't stop NIST from defining a good one.

There are better performers than Skein, so unless those are all seriously weakened I doubt it can win. Skein looks good on high end hardware, and not so good on anything else (compared to some other top competitors).

Re:I was a little worried (1)

badkarmadayaccount (1346167) | about 5 years ago | (#28828827)

How much is paralelizable, anyway? I'd really love it if I could offload stuff like that to the GPU. If only someone would get some actual good quality drivers out.
*cough*ATiI'mLookingAtyou*cough*

Re:I was a little worried (3, Interesting)

Martin Blank (154261) | about 5 years ago | (#28815781)

I knew about Schneier being involved from early on, but I just noticed Bernstein made the last cut. Considering Bernstein's thoroughness (64-bit timestamps in his programs, and didn't he once talk about writing his own filesystem to address an external limitation that slowed down qmail?), I am very intrigued at how well CubeHash will do. He apparently admits that it suffers from some performance problems, but also says that he over-engineered it, and that it can be scaled back to improve speed while losing little in the way of security.

Of the 14 candidates going into this round, his is one of only six that hasn't had to be revised so far. Of course, that he seems to have designed it completely on his own may work against him.

Re:I was a little worried (3, Interesting)

letsief (1053922) | about 5 years ago | (#28816043)

Depending on what you call a revision, Bernstein just revised CubeHash. A few days ago he posted a parameter tweak that significantly increases performance at the cost of some security. You can read about his tweak on his website at: http://cubehash.cr.yp.to/submission/tweak.pdf [cr.yp.to]

Re:I was a little worried (1)

Skuto (171945) | about 5 years ago | (#28816663)

It's unclear this tweak lowers security, probably the opposite. It has more rounds than the original submission.

Re:I was a little worried (2, Informative)

letsief (1053922) | about 5 years ago | (#28819125)

In a practical sense, yes, but the generic preimage attacks against the 512-bit variant of CubeHash work better as the "b" parameter increases. It's still well above the birthday bound, so maybe people shouldn't care. But, it does mean CubeHash16/32-512 "only" provides 384 bits of preimage resistance. That's probably beyond theoretical computation limits for the universe, so I think there's a pretty good argument we shouldn't care. At the same time, all the attacks, and preimage attacks in particular, we're likely to see on 512-bit variants are likely to be well beyond anything that could seen as remotely practical.

Re:I was a little worried (1)

mrmeval (662166) | about 5 years ago | (#28823643)

djb admitted a flaw? But his stuff is perfect and precious according to him! He may be getting senile if he's admitting flaws.

Has he ever developed anything as part of a team and not as either a dictator or a team of one?

SHA-3? (1, Funny)

Anonymous Coward | about 5 years ago | (#28815583)

Pff. I'm already using SHA-256.

Re:SHA-3? (1)

the donner party (1000036) | about 5 years ago | (#28817233)

There may only be three bits in a SHA-3 key, but those bits are extremely hard to guess.

Way to go, Bruce (1)

billh (85947) | about 5 years ago | (#28815585)

Congratulations.

Let that be a lesson to you. (1)

girlintraining (1395911) | about 5 years ago | (#28815595)

We were generally alarmed by attacks on compression functions that seemed unanticipated by the submitters.

Just when you think Entropy's a bitch...

Where's Whirlpool? (1)

CaptSaltyJack (1275472) | about 5 years ago | (#28815689)

Why didn't Whirlpool make the list of candidates? That sucker is fort knox.

Re:Where's Whirlpool? (2, Informative)

compro01 (777531) | about 5 years ago | (#28815913)

It appears that whirlpool was never submitted to the competition.

Re:Where's Whirlpool? (1)

letsief (1053922) | about 5 years ago | (#28816095)

I think WHIRLPOOL is probably too slow for the SHA-3 competition. NIST said they are looking for something that is at least as fast as SHA-2, and WHIRLPOOL is quite a bit slower.

Re:Where's Whirlpool? (2, Interesting)

Skuto (171945) | about 5 years ago | (#28816667)

Because the Rijndael guys submitted something much better: Keccak.

Re:Where's Whirlpool? (1)

owlstead (636356) | about 5 years ago | (#28817557)

There have been a few AES based candidates for SHA-3. Basically they improve on Whirlpool. So the ideas of Whirlpool were taken and enhanced for the competition.

Using AES certainly has advantages. It may be possible to use current hardware acceleration and a lot is known of the algorithm. Newer hardware may combine the two. The disadvantages are also numerous.

AES was never designed with hashing in mind and may have unknown vulnerabilities. Current hardware may not be resistant against some attacks that are particular to hash methods. That is, if it can be used efficiently at all in hashing mode - most of the time the candidates use part of the AES method, not the block encrypt in its totality.

Of course Skein uses Threefish. It can also be used for encryption and decryption, but it has not been standardized for those uses.

Re:Where's Whirlpool? (0)

Anonymous Coward | about 5 years ago | (#28819421)

AES was never designed with hashing in mind and may have unknown vulnerabilities.

The recent related key attacks against AES should almost certainly disqualify it from being used for hashing.

Re:Where's Whirlpool? (1)

compro01 (777531) | about 5 years ago | (#28821939)

Whirlpool wasn't based on rijndael (AES). It was based on square, which rijndael was also based on.

Hey, cool! (3, Interesting)

jd (1658) | about 5 years ago | (#28815881)

One of my favourites (Blue Midnight Wish) made it through, and one of the others with a really cool name (SandSTORM) wasn't broken in the 1st round.

Yes, I know, that's NOT how to pick hash functions, but you've got to admit that cryptography isn't capturing the popular imagination at the present time, leaving data dangerously insecure. I believe that part of this is because most popular crypto-related functions (and cryptographic hashing is definitely one) have names that are a turnoff.

Once upon a time, computing was for "the Egg Heads" and anyone daring to mention computers was automatically One Of Them. The Apple made computing sexy and it became fashionable.

Cryptography has to do the same thing, if security is to be meaningful. Otherwise, it will remain for "Egg Heads Only" and we will continue to see horrific losses from naive and pathetic practices by people trying to avoid being tarred as geeky.

Re:Hey, cool! (1)

fuzzyfuzzyfungus (1223518) | about 5 years ago | (#28815965)

I suspect that, as with many other parts of computing, the people at large will use it once it becomes largely automatic, and not much before(crypto has the additional complication that it makes it even easier for n00bs to lose large amounts of data).

As for crypto marketing, "military grade" seems to be the appellation of choice. Pity it means absolutely nothing...

Re:Hey, cool! (1)

Fyzzler (1058716) | about 5 years ago | (#28815999)

Well, since crypto was considered a munitions for export from the USA, calling it military grade kind of fits.

Re:Hey, cool! (1)

letsief (1053922) | about 5 years ago | (#28816121)

Encryption was considered a munition for export-control purposes (technically, I think it still is), but that didn't extend to hash functions. It will be interesting to see what NSA does with the eventual SHA-3. NSA has cleared AES for Top Secret classified information. We'll see if they do the same thing with SHA-3. If so, then you really could call it military-grade. Though, really its tamper-resistant hardware chips that sets military-grade stuff apart from commercial stuff.

Re:Hey, cool! (2, Interesting)

jd (1658) | about 5 years ago | (#28816049)

Military grade, according to ITAR, means the key is more than 56 bits (used to be 40 bits). Which, you're right, means nothing.

Now, if I use the term "military-grade" for crypto, I would mean an algorithm that is certified NIST/NESSIE-approved for Secret or above (for mundane usage) or NIST/NESSIE-approved for Top Secret (for information that is commercially sensitive). That is still arguably market-babble, but at least it has a measure of respectability because NIST and NESSIE are reasonably trustworthy organizations for evaluating crypto.

Re:Hey, cool! (1)

nhytefall (1415959) | about 5 years ago | (#28828683)

As for crypto marketing, "military grade" seems to be the appellation of choice. Pity it means absolutely nothing...

Really?

http://en.wikipedia.org/wiki/United_States_Military_Standard [wikipedia.org] That should help explain what MIL-SPEC actually means, and why it does have value.

Doesn't matter (1)

pjt33 (739471) | about 5 years ago | (#28816781)

It doesn't matter how cool the name is: once the winner is picked it will be SHA-3, in the same way that Rijndael became AES. In fact, the name Rijndael had slipped my memory and I had to Google it - and I'm interested in crypto.

Besides, the general public might be able to name WEP and WPA as "types of encryption", but to hope for more than that, no matter how cool the name, is optimistic.

Re:Hey, cool! (1)

JSlope (1180805) | about 5 years ago | (#28817003)

Cryptography must be simple, now it's too complicated to install and configure. And most end users don't see why they should bother. I think that there should be a separated encrypted mail network where everything is encrypted by default and you can't turn encryption off. This way you can set all your relatives on this system and be sure that nothing will be sent unencrypted.
[shameless plug on]

I'm trying to fix it. You can try ResoMail.com [resomail.com]

[shameless plug off]

What about TIB3? (0)

Anonymous Coward | about 5 years ago | (#28816203)

I was disappointed that TIB3 wasn't selected. It had a great performance profile and a lot of novel design features -- e.g., long-pipe, a message expansion function that couldn't easily be reversed, etc.

Re:What about TIB3? (1)

Skuto (171945) | about 5 years ago | (#28816677)

It had too strong attacks against it.

MD6 (2, Interesting)

imbaczek (690596) | about 5 years ago | (#28816847)

I'm quite surprised Rivest didn't make it to round 2. Could anybody share some details about this decision?

Re:MD6 (2, Informative)

Dj (224) | about 5 years ago | (#28816935)

It was withdrawn from the contest [h-online.com]

Re:MD6 (1)

owlstead (636356) | about 5 years ago | (#28817513)

Hmm, please do not read the last part of that article.

If you do, I'll offer my opinion on it.

Basically if MD6 is withdrawn it will not have too much value left for the immediate future. It will only live on in the minds of crypto-analysts for their next algorithms. It won't be adopted in any cryptographic products (both the all important libraries and hardware).

Nobody in their right mind is using both MD5 and SHA-1 together, and even if they do they are both standardized hash methods. Combining hash methods is dangerous at least and should not be done haphazardly. It would be much better to use SHA-2 256 instead, if only because it is a standardized hash and not some weird combination of two.

Re:MD6 (2, Insightful)

six (1673) | about 5 years ago | (#28817971)

Nobody in their right mind is using both MD5 and SHA-1 together, and even if they do they are both standardized hash methods. Combining hash methods is dangerous at least and should not be done haphazardly. It would be much better to use SHA-2 256 instead, if only because it is a standardized hash and not some weird combination of two.

I think the author doesn't mean to combine SHA-1 and MD5 to make one hash, but instead using both hashes. This may be weaker for preimage attacks, but a lot stronger against collisions, so if it's what you're after it's one of the best ways to achieve it.

Re:MD6 (0)

Anonymous Coward | about 5 years ago | (#28848257)

Nobody in their right mind? So Stuart Haber is not in his right mind?
    http://csrc.nist.gov/groups/ST/hash/documents/HABER_renewal-reminder.pdf

Re:MD6 (1)

owlstead (636356) | about 5 years ago | (#28859297)

If he gets it standardized and included in standard implementations of cryptographic software and hardware - he would definitely have something there. But I would take opt for SHA-2 instead. It's well defined and present in more devices that having MD5 and SHA-1 work together. Of course that does not mean it cannot be included in proprietary or closed protocols, but for those anything goes. I agree that I may have put that a bit too strong though. But pretty please (with sugar on top) don't opt for these kind of combinations.

Anyway, the paper you pointed to seems to be for using two signatures each with a different hash method, which is different form just concatenating the two. I've just browsed over it (and it is quite late) but if it doesn't mean that than the paper is pretty unclear.

Re:MD6 (1)

Jonathan_S (25407) | about 5 years ago | (#28857985)

Nobody in their right mind is using both MD5 and SHA-1 together, and even if they do they are both standardized hash methods.

So you're saying that nobody who uses SSL or TLS is in their right mind?

(The SSL and TLS specifications require the use of both MD5 and SHA-1 during key derivation)

Re:MD6 (1)

owlstead (636356) | about 5 years ago | (#28859039)

I *know*, it has given me endless nightmares getting it work with various hardware devices. That's exactly why it should not be used. Use SHA-2 instead.

I've got more than 8 years of experience with security around HSM's and smart cards.

But can we "prove" that any of these are "one way" (1)

shic (309152) | about 5 years ago | (#28818055)

I've been doing a fair bit of reading about secure hashes recently... as I'm interested in one specific property of hash functions that, as far as I can tell, is not discussed as widely as I'd expect... While collisions seem to draw a lot of attention, they are not of particular interest to me... since collisions (for me) affect only performance - not security.

The closest term for what I'm interested in is preimage resistance [wikipedia.org] - but, as far as I can tell, this property is often disregarded as it is considered implausible to reconstruct a large input from a small output.

In a context in which I'm interested, however, the input to my hash function is itself a hash. I'm interested to know if I can rely on attackers being unable to compute the inverse of the hash function. Is there any work on formally establishing that any hash function is 'one way'?

Re:But can we "prove" that any of these are "one w (2, Interesting)

TheTurtlesMoves (1442727) | about 5 years ago | (#28818339)

It is trivial to prove that a function is one way. If the input is from a larger domain than the output. ie a^b=c is one way. given c I cannot recover a and b. Of course this is not a good function to use for other reasons....

If however the input is the same length then its a little harder...The only way we know how to do is the way this competition is doing it. Propose a "one way" function, others then try and break it. Otherwise you need a collision which in this context is a bad thing due to reduced randomness. ie f(a)=b and f(a')=b which a b and a' are the same bit length.

Re:But can we "prove" that any of these are "one w (0)

Anonymous Coward | about 5 years ago | (#28819521)

It's an open mathematical/theoretical computer science question about whether there can truly be a one way function with NP-hard computational bounds (which is probably what you mean). If P = NP then there are no one way functions. Many problems that are NP complete are not NP-hard for the vast majority of particular instances of the problem. Encryption algorithms based on NP-complete problems are generally easy to break because the particular problems that are generated have a relatively fast solution by the best algorithms.

In general, preimage resistance is equivalent to one-wayness for hash functions. This is clear because the straightforward way to generate a preimage of a hash is to find an input that generates the known output. The security implication is more obvious for HMACs; if you know only the output of a HMAC function and the function is not one-way, it is not secure for message authentication. Since all modern HMACs basically operate by hashing a secret key along with the message (which may be known by the attacker), I'd say you could consider modern hash functions to be one-way.

Re:But can we "prove" that any of these are "one w (1)

shic (309152) | about 5 years ago | (#28826021)

Everything you say makes sense, and I'm familiar with this technical background.

If I were to re-phrase my question, in the context of your reply, I'd be asking if equivalences have been shown between known-hard problems and the inverse to standard HMACs.

The particular issue that interests me is extremely similar to (type-1) preimage... but it is slightly easier to break. T1-preimage requires me to find m where H(m) is known. In my specific situation, we also know the length of m - it's the same as H(m) - or, equivalently, it is longer than H(m) but all except length(H(m)) bits are known to the attacker.

This might sound uninformed, but it simply makes me feel uneasy that I can't find any work (from a theoretical perspective) to show how hard a problem this is for specific HMACs... just a hypothesis and an open challenge. This might be good enough for the day-to-day, but is it OK if trying to put together a system that I want to remain robust for 50 years or longer?

Re:But can we "prove" that any of these are "one w (0)

Anonymous Coward | about 5 years ago | (#28842239)

Hash functions in general are not meant to hash an input that is the same size as the output. That is essentially encryption. RSA will do this and is provably (or close enough anyway) secure. You can get the same functionality by encrypting with the public key (so it is verifiable, like a hash function) and just throwing the private key away.

Did anybody else read that as... (1)

Thelasko (1196535) | about 5 years ago | (#28818461)

3 Second Rule Candidates Released?

SHA-Ultimate (1)

Nom du Keyboard (633989) | about 5 years ago | (#28821073)

The ultimate SHA should have a hash space as large as the count of atoms in the universe - then you can just select the atom involved and use its assigned number. Of course, collisions between atoms might be an issue.

Re:SHA-Ultimate (1)

dirvine (1008915) | about 5 years ago | (#28822805)

SAH512 is roughly 1.2 X 10^154, atoms in visible universe is on the order of 10^80, job done :-)
Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Create a Slashdot Account

Loading...