The Skein Hash Function

NIST is holding a competition to replace the SHA family of hash functions, which have been increasingly under attack. (I wrote about an early NIST hash workshop here.)

Skein is our submission (myself and seven others: Niels Ferguson, Stefan Lucks, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas, and Jesse Walker). Here's the paper:

Executive Summary

Skein is a new family of cryptographic hash functions. Its design combines speed, security, simplicity, and a great deal of flexibility in a modular package that is easy to analyze.

Skein is fast. Skein-512 -- our primary proposal -- hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core -- almost twice as fast as SHA-512 and three times faster than SHA-256. An optional hash-tree mode speeds up parallelizable implementations even more. Skein is fast for short messages, too; Skein-512 hashes short messages in about 1000 clock cycles.

Skein is secure. Its conservative design is based on the Threefish block cipher. Our current best attack on Threefish-512 is on 25 of 72 rounds, for a safety factor of 2.9. For comparison, at a similar stage in the standardization process, the AES encryption algorithm had an attack on 6 of 10 rounds, for a safety factor of only 1.7. Additionally, Skein has a number of provably secure properties, greatly increasing confidence in the algorithm.

Skein is simple. Using only three primitive operations, the Skein compression function can be easily understood and remembered. The rest of the algorithm is a straightforward iteration of this function.

Skein is flexible. Skein is defined for three different internal state sizes -- 256 bits, 512 bits, and 1024 bits -- and any output size. This allows Skein to be a drop-in replacement for the entire SHA family of hash functions. A completely optional and extendable argument system makes Skein an efficient tool to use for a very large number of functions: a PRNG, a stream cipher, a key derivation function, authentication without the overhead of HMAC, and a personalization capability. All these features can be implemented with very low overhead. Together with the Threefish large-block cipher at Skein core, this design provides a full set of symmetric cryptographic primitives suitable for most modern applications.

Skein is efficient on a variety of platforms, both hardware and software. Skein-512 can be implemented in about 200 bytes of state. Small devices, such as 8-bit smart cards, can implement Skein-256 using about 100 bytes of memory. Larger devices can implement the larger versions of Skein to achieve faster speeds.

Skein was designed by a team of highly experienced cryptographic experts from academia and industry, with expertise in cryptography, security analysis, software, chip design, and implementation of real-world cryptographic systems. This breadth of knowledge allowed them to create a balanced design that works well in all environments.

Here's source code, text vectors, and the like for Skein. Watch the Skein website for any updates -- new code, new results, new implementations, the proofs.

NIST's deadline is Friday. It seems as if everyone -- including many amateurs -- is working on a hash function, and I predict that NIST will receive at least 80 submissions. (Compare this to the sixteen NIST submissions received for the AES competition in 1998.) I expect people to start posting their submissions over the weekend. (Ron Rivest already presented MD6 at Crypto in August.) Probably the best place to watch for new hash functions is here; I'll try to keep a listing of the submissions myself.

The selection process will take around four years. I've previously called this sort of thing a cryptographic demolition derby -- last one left standing wins -- but that's only half true. Certainly all the groups will spend the next couple of years trying to cryptanalyze each other, but in the end there will be a bunch of unbroken algorithms; NIST will select one based on performance and features.

NIST has stated that the goal of this process is not to choose the best standard but to choose a good standard. I think that's smart of them; in this process, "best" is the enemy of "good." My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all 80 -- although I also expect that most of the amateur submissions will be rejected by NIST for not being "complete and proper." Otherwise, people will break the easy ones and the better ones will go unanalyzed.

EDITED TO ADD (10/30): Here is a single website for all information, including cryptanalysis, of all the SHA-3 submissions. A spoke to a reporter who told me that, as of yesterday, NIST had received 30 submissions. And three news articles about Skein.

Posted on October 29, 2008 at 6:35 AM • 148 Comments

Comments

crypto godOctober 29, 2008 5:06 AM

>> Our current best attack on Threefish-512 is on 25 of 72 rounds

Hah! I already see how to break 65 rounds, but I will never tell. :)

shadowfirebirdOctober 29, 2008 5:36 AM

Sooner or later some dumb ass is going to ask why Skein is based on Threefish, which was (apparently, according to the intertubes) broken.

I guess it might as well be me. Presumably it has to do with the differences in purpose of a hash as compared to a cipher?

da5idOctober 29, 2008 6:00 AM

>> My advice is this: immediately sort them based on performance and
>> features. Ask the cryptographic community to focus its attention on
>> the top dozen, rather than spread its attention across all 80

Great advice, but even if NIST doesn't do this, can't you (or some one else respected in the community) create this list anyway?

I look forward to your comments on other submissions and the process as a whole, I find this all very interesting.

RonKOctober 29, 2008 7:04 AM

@ shadowfirebird

> Threefish, which was (apparently, according to
> the intertubes) broken.

Er, I hope you're not talking about that joke paper which talks about "Fortytwofish". If you are, I'd better go look for a bomb shelter from the sonic boom generated by *that* whoosh!

Paul CrowleyOctober 29, 2008 7:04 AM

Oh hooray! I was starting to wonder where all the candidates were - this is only the second I know about after MD6, have I missed any others?

I know of at least one other author with a candidate in the works, and I'm really hoping for an entrant inspired by Trivium.

This should be fun!

RoxanneOctober 29, 2008 7:08 AM

The Skein Hash Function: What happens after the cats get into the yarn stash.

:-)

NyhmOctober 29, 2008 8:22 AM

In Practical Cryptography, you and Ferguson define a double-hashing technique to overcome weaknesses in the SHA family of algorithms. Is double-hashing a good general purpose approach to hashing, or only recommended for SHA? Does Skein overcome any need for your double-hashing technique?

I referenced your double-hashing algorithm on my game development blog: http://www.potentialgames.com/blog/2008/10/09/...

Clive RobinsonOctober 29, 2008 8:44 AM

Bruce,

So a nice quite competition taken at a leasurly pace, without spleen venting or blood baths.

After all how difficult is designing a hash, you just find a one way function and iterate...

Seriously though it should prove both interesting and instructive. Personaly I would still like to see all the entrants analysed including the ones NIST rejects as not being compleate sometimes the seeds of odd ideas have a habit of blooming in other ways and areas.

gregOctober 29, 2008 8:55 AM

@Clive Robinson

The problem is that there are a lot of would be cryptographers that sux. I mean the competition for stream ciphers, there where some that even failed the dieHard randomness tests!! Thats pretty bad and IMO as it should be just part of "due process".

I really like the use of a tweak able block cipher as the building block. The optional modes are great. HMAC is killing me in overhead for one of my apps.

Clive RobinsonOctober 29, 2008 9:15 AM

As for "Skein" it is a word you hear in and around the Kingdom of Fife (Scotland) and in quite a few contexts.

As Roxanne pointed out one use is for a twist of yarn usually used (but not exclusivly) for knitting or in the weaving process.

You will also hear it used when refering to a flock of wild/water fowl when in flight.

But when used as "Skein Dhu" it refers to something quite nasty with a bit of an edge on it that hides in a Scotsmans sock...

Most of which appear to be appropriate as metaphores for a hash function.

Henning MakholmOctober 29, 2008 9:25 AM

Everything in Skein is little-endian -- except the bit padding for odd-sized inputs: it puts the last data bits in the MOST significant bit positions of the last byte -- which are not adjacent to the bits in the next-to-last byte when both are part of the same 64-bit word.

The practical significance of this difference is extremely limited, but still: Why?

MikeyOctober 29, 2008 10:03 AM

From the footnote on page 1 of the paper: "1A \skein"|pronounced nskann and rhymes with \rain"|is a loosely coiled length of yarn or thread wound on a
reel."

Fred POctober 29, 2008 10:25 AM

@greg-

You mean that my wonderful hash function based off of the famous, trusted, widely-used ROT13 cipher isn't likely to be accepted? Well, at least my submission based on ROT26 should be safe (since 26 is twice the size of 13).

Seriously, Skein looks interesting. I look forward to analyzing the first few rounds.

MackenzieOctober 29, 2008 1:11 PM

"Fast" isn't a feature! Fast hashes mean faster brute forcing. If we make hashes slower, it takes a lot longer for an attacker to run a password cracker and figure out what combination of characters make that hash.

If you mean this just for integrity checks, that's one thing, but password hashes need to be nice and slow.

PaeniteoOctober 29, 2008 1:24 PM

@Mackenzie: "password hashes need to be nice and slow"

You can always make a hash function as slow as you want, if you apply it, say, 1.000.000 times to the password before storing it into a database or using it as a crypto key.
Whereas you cannot easily/securely make a slow hash function faster.
Therefore, having a fast hash function as a cryptographic primitive is desirable.

EricOctober 29, 2008 2:07 PM

Bruce, you mentioned in your summary that there can be parallel versions of Skein, as opposed to purely sequential versions. If I recall correctly, SHA and/or MD5 also had this trait, but the standard was to use a sequential version so it would require less memory on small devices. While small devices are still important, it seems that given the trend towards increasingly parallel machines, it's very important that this time around we develop a standard hash function that can be coded in an efficient sequential fashion, while also allowing it to take advantage of parallel computers, such as GPUs and manycore CPUs.

DudeOctober 29, 2008 3:13 PM

@Mackenzie

So hash 1000 times.

Or do some "hashcash" type thing.

Or hash it 1000000 times

Take your pick.

But a good hash needs to be fast to calculate. Otherwise it won't even be used.

Bruce SchneierOctober 29, 2008 4:51 PM

"I guess it might as well be me. Presumably it has to do with the differences in purpose of a hash as compared to a cipher?"

Hash functions are either based on block ciphers or they're native streaming. In Section 8.2, we talk about this decision.

Bruce SchneierOctober 29, 2008 4:52 PM

"In Practical Cryptography, you and Ferguson define a double-hashing technique to overcome weaknesses in the SHA family of algorithms. Is double-hashing a good general purpose approach to hashing, or only recommended for SHA? Does Skein overcome any need for your double-hashing technique?"

Double hashing secures SHA against a particular weakness. You don't need to do that with Skein, or any other stronger hash function.

Bruce SchneierOctober 29, 2008 4:53 PM

"Bruce, you mentioned in your summary that there can be parallel versions of Skein, as opposed to purely sequential versions. If I recall correctly, SHA and/or MD5 also had this trait, but the standard was to use a sequential version so it would require less memory on small devices."

There are no tree modes defined in either the MDx or SHA-x standards. It's certainly possible to define tree modes for any hash function -- and people have done that -- but for Skein it is part of the algorithm's definition.

suomynonaOctober 29, 2008 8:13 PM

I see only half of Twofish team listed as authors. What's with the rest of them? I understand that John Kelsey doesn't take part in the design of any submission, since he's at NIST now, but what about David Wagner?

Karl FogelOctober 29, 2008 8:42 PM

The headers and source files indicate that the code is partly under a variety of licenses and partly in the public domain. It might be good to put some sort of copyright notice in front of the download, so free software fans (like me) can tell before clicking that the entire package is open source.

That would also help clarify things and avoid duplicated effort. Right now, one has to examine every .h and .c file in the tree to determine the terms. Each downloader has to repeat that process, but it could be done once at the source, saving everyone time...

Good luck,
-Karl Fogel

WarLordOctober 30, 2008 12:25 AM

Greetings

'"best" is the enemy of "good."'

Funny I had a doctor tell me that very thing about treatment options

Its become my mantra of late

DanOctober 30, 2008 2:28 AM

I have been following recent presentations of several cryptographic groups in Europe (in different occasions) about their hash designs in progress. From all data that I have collected, it seems that Skein will be the one of the fastest (if not THE fastest) candidate. MD6 is doggy slow, Lars Knudsen's team will offer hash function 30% faster than SHA-2, performances of two other candidates are 30% - 50% faster than SHA-2. So good luck.

CombatFighterOctober 30, 2008 3:04 AM

I don't think that Skein has superior speed. It is just fastest in 64-bit mode. Look at the numbers in 32-bit mode (on page 25 of the documentation): Skein is SLOWER than SHA-2. Look at the numbers for 8-bit processors. Skein-1024 (equivalent to SHA-512) needs 940,000 clocks/block = 7343 cycles/byte ??!?! This is NOT fast. This is also DOGGY slow.

RogerOctober 30, 2008 5:19 AM

@CombatFighter:
> Look at the numbers in 32-bit mode (on page 25 of the documentation): Skein is SLOWER than SHA-2.

Que? Are we looking at the same paper? On a 32 bit machine, the reference version coded in C is about the same speed as SHA-2; the optimised assembler version is about 27% faster.

> Skein-1024 (equivalent to SHA-512)

Are, there's your problem! Skein-1024 is not supposed to be equivalent to SHA-512; it is the "ultra-conservative" version. The version that is supposed to be equivalent to SHA-512 is Skein-512-512. You were comparing apples and watermelons.

> needs 940,000 clocks/block = 7343 cycles/byte ??!?!

You perhaps missed the caption under that table, which remarked that these disappointing figures seem to be due to a problem in the C libraries; the assembler version is more than an order of magnitude faster, at 80 k-clocks/block (= 625 clocks/byte.) Further, as noted before, that is for the ultraconservative version. The version that is actually recommended for microcontrollers is Skein-256 (and with a 256 bit hash length, is still claimed to be comparable security to a 128 bit block cipher, i.e., extremely strong.) The best optimised version of Skein-256 used 9.5 k-clocks/block, or 297 clocks/byte. A fair crack faster than 7343 !!

CombatFighterOctober 30, 2008 5:44 AM

>> Skein-1024 (equivalent to SHA-512)

>Are, there's your problem! Skein-1024 is not supposed to be equivalent to SHA-512;
>it is the "ultra-conservative" version. The version that is supposed to be equivalent to
>SHA-512 is Skein-512-512. You were comparing apples and watermelons.


If I am comparing apples and watermelons then the authors of Skein have done that as well. Look at Table 1 (page 2). There, equivalent for SHA-512 are BOTH Skein-512 and Skein-1024. It depends what you need.

About the speed on 32-bit platforms, who is comparing apples and watermelons? Don't say that ASM Skein is faster than C SHA-2!!

CalumOctober 30, 2008 6:51 AM

Yes ut if your apples for apple comparison is unfair (due to bad cultivation, perhaps), then perhaps you're better off comparing with a nice juicy orange.

NiWOctober 30, 2008 8:54 AM

"From all data that I have collected, it seems that Skein will be the one of the fastest (if not THE fastest) candidate. MD6 is doggy slow, Lars Knudsen's team will offer hash function 30% faster than SHA-2, performances of two other candidates are 30% - 50% faster than SHA-2."
Certainly Dan (Be..n!?) has internal information but all this boasting is only for 64 new Intel (no surprise with such authors).
What about 32/16/8 bits CPUs or HW? NIST should choose a balanced solution not biased to Intel but suitable for wide range platforms - "so the overall equivalent chip area might be closer to about 80K gates" this is terrible!

WimOctober 30, 2008 9:04 AM

"My advice is this: immediately sort them based on performance and features. Ask the cryptographic community to focus its attention on the top dozen, rather than spread its attention across all." It will be not good if NIST makes such a list only by looking on performance and features or which the submitters are. I will be happy if somebody "a newborn crypto student" wins this competition against all these dinosaurs (which usurped all "top" crypto conferences) as it happened for AES. Cheers

Mark Wooding [mdw]October 30, 2008 2:06 PM

Looks pretty good. I especially like the emphasis on personalization, and generally separating the different uses hash functions get used for. In my own designs, I always prefix messages with a purpose string before hashing them, but it's nice to have a dedicated input.

The bibliography describes the paper containing the security proofs as being `in preparation'. Any idea how long we'll have to wait for that? I'm assuming that the proofs are already complete, or you wouldn't have released the spec...

Typo: 4.11 recommends that personalization strings begin with a date in YYYYDDMM form (para 2, p. 21). This is actually the first time I've ever seen this date order. However, the example uses 20081031, which must be in YYYYMMDD form. Please tell me that the example is correct and the text wrong!

Mark Wooding [mdw]October 30, 2008 2:19 PM

@Wim
"I will be happy if somebody "a newborn crypto student" wins this competition against all these dinosaurs (which usurped all "top" crypto conferences) as it happened for AES"

Uhh... Joan Daemen and Vincent Rijmen were hardly newcomers to the crypto world when they entered the AES. I recognized most of the names on the final five submissions (at least two from each) from previous good work.

And no, I wasn't a crypto `insider'. At the time, I was just a sysadmin at a bioinformatics institute who kept his eyes open.

Bruce SchneierOctober 30, 2008 7:06 PM

"Typo: 4.11 recommends that personalization strings begin with a date in YYYYDDMM form (para 2, p. 21). This is actually the first time I've ever seen this date order. However, the example uses 20081031, which must be in YYYYMMDD form. Please tell me that the example is correct and the text wrong!"

You're right, of course.

Bruce SchneierOctober 30, 2008 7:08 PM

"The bibliography describes the paper containing the security proofs as being 'in preparation.' Any idea how long we'll have to wait for that? I'm assuming that the proofs are already complete, or you wouldn't have released the spec..."

Turns out that writing them up was much more work than we anticipated. They were originially going to be a chapter in the document, but at the end we had to give up and save them for a separate document.

We promised them for the next NIST hash workshop in February. We will probably have them out sooner, but right now we're taking a few weeks off to think about something -- anything -- else.

Bruce SchneierOctober 30, 2008 7:09 PM

"I see only half of Twofish team listed as authors. What's with the rest of them? I understand that John Kelsey doesn't take part in the design of any submission, since he's at NIST now, but what about David Wagner?"

John, of course, can't participate. David Wagner isn't doing any real cryptography work anymore. We tried to entice him a few times, but he wasn't interested. Chris Hall, too, isn't doing cryptography work anymore. So it wasn't a complete reunion.

Bruce SchneierOctober 30, 2008 7:13 PM

"Skein-1024 (equivalent to SHA-512) ...."

Be careful about comparisons; those numbers mean different things. Skein-1024 refers to the internal state size: 1024 bits. SHA-512 refers to the output size: 512 bits. If you want a drop-in replacement for SHA-512, we recommend Skein-512-512: a 512-bit state size and a 512-bit output size. If you're ultra-paranoid use SHA-1024-512, but in my experience ultra-paranoid people don't care too much about speed.

Bruce SchneierOctober 30, 2008 7:16 PM

"I don't think that Skein has superior speed. It is just fastest in 64-bit mode. Look at the numbers in 32-bit mode (on page 25 of the documentation): Skein is SLOWER than SHA-2. Look at the numbers for 8-bit processors. Skein-1024 (equivalent to SHA-512) needs 940,000 clocks/block = 7343 cycles/byte ??!?! This is NOT fast. This is also DOGGY slow."

All the SHA-3 submissions will be optimized for 64-bit CPUs, because that's what NIST asked for. So they will be slower on 32-bit machines, and very slow on 8-bit machines. We think our performance on those smaller CPUs is pretty good, and will -- comparatively -- make us one of the fastest submissions. (Honestly, we were very happy when Skein-512 came in at half the speed of SHA-256 on a 32-bit CPU -- the latter is optimized for 32-bit CPUs.)

Bruce SchneierOctober 30, 2008 7:18 PM

"When will threefish and skein be available in commercial software?"

As soon as someone impleents the algorithms. They're free and open-source; so there's nothing stopping anyone.

Except that it would be foolish. The algorithms are much too new to be used in a commercial application. Don't trust us when we tell you Skein and Threefish are secure; we designed them. Give it a year or two; let the community start evaluating the submissions. Let some consensus start to develop. There's no rush.

Bruce SchneierOctober 30, 2008 7:23 PM

"I will be happy if somebody "a newborn crypto student" wins this competition against all these dinosaurs (which usurped all 'top' crypto conferences) as it happened for AES."

Um...Joan Daemen and Vincent Rijmen wrote Rijndael, which eventually became AES; not a newborn crypto student.

Bruce SchneierOctober 30, 2008 7:24 PM

"Sooner or later some dumb ass is going to ask why Skein is based on Threefish, which was (apparently, according to the intertubes) broken."

Threefish can't possibly be broken yet; we only just announced it yesterday. No one knew of its existence before then.

I think your intertubes are clogged.

Jon CallasOctober 31, 2008 3:12 AM

@Henning Makholm:

Because that's the way that NIST defined it. We wouldn't have done it that way on our own. Heck, we probably only would have done it for complete bytes if it were up to us.

Henning MakholmOctober 31, 2008 8:25 AM

@ John Callas:

Ah, I see. I hadn't noticed that NIST was micromanaging bit order to that degree.

(In case others are curious, the bit order definition is not in the main submission requirements document, but hidden away in the "ANSI C Cryptographic API Profile for SHA-3 Candidate Algorithm Submissions" that reference implementations must follow).

bpadalinoOctober 31, 2008 3:12 PM

On page 12, the definition of k_{s,i} uses t_{s mod 3} - should this be mod 2 as the tweak value is always 128 bits (2 words)?

Mike StayOctober 31, 2008 4:46 PM

While David Wagner is not doing cryptography, he's certainly doing cool security stuff. Check out Joe-E and Mark Miller's thesis.

Henning MakholmOctober 31, 2008 5:43 PM

@bpadalino: Look in the lower right corner of page 11. A third tweak word to alternate with is defined as the XOR of the two input ones.

(Incidentally, this means that for Threefish-512, the key rotation period is a multiple of the tweak rotation period. Thus, but for the addition of the subkey number, the key schedule would repeat itself after 9 cycles -- whereas the equivalent period of Threefish-256 is 15 cycles).

Bruce SchneierOctober 31, 2008 6:08 PM

"On page 12, the definition of k_{s,i} uses t_{s mod 3} - should this be mod 2 as the tweak value is always 128 bits (2 words)?"

No; the mod 3 is deliberate. This is accessing the third tweak word which is the xor of the two other ones. We define t_2 a few paragraphs earlier.

AkashNovember 1, 2008 9:11 AM

Skein hash algorithm looks simple and good. But the logic is not different from a new approach. So far, nobody produces a hash algorithm based on Chaos theory. I hope that there may be a hash algorithm based on Chaos theory in the NIST hash competition. Let us see.

Maarten BodewesNovember 1, 2008 11:12 AM

From the summary of the paper:

"Skein is fast. Skein-512 -- our primary proposal -- hashes data at 6.1 clock cycles per byte on a 64-bit CPU. This means that on a 3.1 GHz x64 Core 2 Duo CPU, Skein hashes data at 500 MBytes/second per core -- almost twice as fast as SHA-512 and three times faster than SHA-256."

Twice as fast as SHA-512 and three times faster than SHA-256? Should not that be the other way around? Or has SHA-512 some advantage I'm unaware of? Or is this - as I suspect - a typo?

Henning MakholmNovember 1, 2008 3:20 PM

@Maarten Bodewes: The paper's right. On the 64-bit reference platform, SHA-256 is actually slower than SHA-512. Both work on an 8-word state in virtually the same way, but in SHA-256 the words are 32 bits, and in SHA-512 they are 64 bits. Each individual 32-bit operation is not faster than a 64-bit one. So SHA-256 needs twice as many blocks for the same amount of data, which is only partially mitigated by the fact that it has slightly fewer rounds per block than SHA-512.

@Akash: What do you imagine that a "hash based on chaos theory" would look like? The chaos theory I know is about the dynamic behavior of systems with CONTINUOUS state, where the evolution law exhibits strong dependence on small variations of the initial state. Orthodox cryptographic hash constructions seem to be to be fairly close to that, given the constraint that the state must be discrete and finite-sized. In particular, "strong dependence on small variations of the initial state" is also important here; cryptographers call it "diffusion" and try to maximize it.

Maarten BodewesNovember 1, 2008 5:32 PM

@Henning Makholm: thanks. I don't normally use secure hash functions in a 64 bit environment (pretty much only in 8 and 32 bit). I didn't think the word size could have such a large impact.

I'm running through all the papers and so far the Skein paper seems to have the best of it all, although the security proof, especially of the block cipher, is still missing. I'm currently trying to determine if the hash tree principle of MD6 and Skein comes down to the same thing. I'm also wondering if the algorithm would run as well on a MSB machine (Sparc, Java VM). But I really like the flexibility of the design.

One thing that raised my eyebrows was the following statement" "Obviously, a company like Intel could use the same chip technology found in CPUs to make faster Skein hardware, but we doubt that will ever happen." That's a very negative statement that I would have left out. Maybe it is something like throwing down the gauntlet but I don't see any reason to put it into an otherwise scientific paper (even if it is right on the mark).

AkashNovember 2, 2008 12:19 AM

@Henning Makholm: I agree that orthodox hash functions with IVs produce random outputs. Can we design a collision resistant and robust hash function without IVs? It will be like a Tsunami wave (non linear dynamical system) without initial conditions ( no random elements involved).

AkashNovember 2, 2008 12:46 AM

We try to make IVs = 0 in all hash algorithms. Check their diffusion and nonlinear properties. For instance, let us perform cryptanalysis on Skein hash algorithm with IVs = 0. What will happen? Someone will come up with collision attacks.

AkashNovember 2, 2008 1:25 AM

@Bruce and Clive Robinson: NIST should not reject some improper hash submissions during the competition. These things happen due to time constraint / personnel reasons /non technical issues. NIST should allow them to prepare proper submissions and encourage them to participate. We should not blindly conclude that improper ones are bad.

neillNovember 2, 2008 8:17 AM

why not use AES and XOR each 256 bit output with the previous
IF AES is safe then XORing will not break it
that way one could reuse existing hardware, also validation would be cheap and easy
proposed name: ADAL
(ADvanced hash ALgorithm)

Maarten BodewesNovember 2, 2008 12:32 PM

neill: I presume this is for performance reasons. Skeil uses threefish which seems to perform pretty well, especially for encryption (decryption is not used for hashing anyway so you can use an unbalanced algorithm). Also note that the reference platform is the Core 2 from Intel, which does not have native cryptographic algorithms implemented. The other reason seems to me that they've designed threefish to be more flexible than AES. If I've got anything wrong here I'll be glad to be corrected.

I've already seen an AES based protocol (which is basically an advanced Whirlpool algorithm) as candidate, so there is also little reason to duplicate that effort.

Bruce SchneierNovember 2, 2008 5:10 PM

"Skein hash algorithm looks simple and good. But the logic is not different from a new approach. So far, nobody produces a hash algorithm based on Chaos theory. I hope that there may be a hash algorithm based on Chaos theory in the NIST hash competition."

Our feeling was that new approaches isn't what you want in a standard.

Bruce SchneierNovember 2, 2008 5:12 PM

"One thing that raised my eyebrows was the following statement: "Obviously, a company like Intel could use the same chip technology found in CPUs to make faster Skein hardware, but we doubt that will ever happen." That's a very negative statement that I would have left out. Maybe it is something like throwing down the gauntlet but I don't see any reason to put it into an otherwise scientific paper (even if it is right on the mark)."

We didn't think of it that way. The fact is that the new Intel CPUs will contain a single-instruction for a round of AES. They could do the same thing with SHA-3, but we don't think they will. That's why we said it.

We have an Intel employee on our team, and he didn't think anything of the statement.

Bruce SchneierNovember 2, 2008 5:15 PM

"I didn't think the word size could have such a large impact."

It really does. We optimize all our operations -- additions, rotates -- for the word size. So they take one instruction on the correct CPU, and many instructions on smaller CPUs.

"I'm running through all the papers and so far the Skein paper seems to have the best of it all..."

Thanks.

"...although the security proof, especially of the block cipher, is still missing."

I'm not sure what you mean by a security proof "of the block cipher." We don't prove that Threefish is secure; I don't know any block ciphers with proofs even remotely like that. What we do prove are reductions. And everything we prove is in the paper; only the details of the proofs are missing.

"I'm currently trying to determine if the hash tree principle of MD6 and Skein comes down to the same thing."

My guess is that, more or less, they do. Merkle described that basic tree hashing ideas decades ago, and we're all just implementing them. The only difference will be efficiency.

Bruce SchneierNovember 2, 2008 5:17 PM

"NIST should not reject some improper hash submissions during the competition. These things happen due to time constraint / personnel reasons /non technical issues. NIST should allow them to prepare proper submissions and encourage them to participate. We should not blindly conclude that improper ones are bad."

I don't know. NIST rejected six -- if I remember correctly -- submissions in the AES process. Of those, I only ever saw one of them.

My guess is that NIST will have more submissions than they can handle in any case.

Bruce SchneierNovember 2, 2008 5:18 PM

"why not use AES and XOR each 256 bit output with the previous. IF AES is safe then XORing will not break it that way one could reuse existing hardware, also validation would be cheap and easy proposed name: ADAL (ADvanced hash ALgorithm)."

I presume someone will make a SHA-3 submision based on AES. My guess is that it won't do well because AES is based on a 32-bit word size -- per NIST's requirements at the time -- and SHA-3 is based on a 64-bit word size.

But you could certainly define an AES variant with a 64-bit word size, and my guess is that someone submitted it.

It's not a bad idea, really.

PeterNovember 2, 2008 8:21 PM

@neill:"why not use AES and XOR each 256 bit output with the previous IF AES is safe then XORing will not break it"

If I understand the construction you propose correctly (I may have misread what you've written), then creation of collisions would be trivial, because in that scenario for message blocks, A and B, H( A | B ) = H( B | A ), this arises because XOR is commutative. Hash algorithms need different considerations from block ciphers.

While a proper chaining scheme would suffice to fix it, you still have the problem that the AES block size is too small to directly make a hash algorithm from - Whirlpool seems like the natural evolution of AES into a hash, so if you like AES then you're likely to like Whirlpool.

Thomas MuellerNovember 3, 2008 3:02 AM

Skein is slow for short messages - why?

Hashing short messages is relatively slow - because of computing the initial chaining values from config block. Even when hashing 1 bit, 3 blocks (3 times 72 rounds) are processed. I don't understand why not just 1 block.

Of course the first block can be pre-computed (for each required configuration), but that requires more memory - and it's just not an elegant solution.

Is there some specific reason? Is processing short blocks not an important use case?

AkashNovember 3, 2008 5:09 AM

A robust hash function should produce the entropy value between 3.9 and 4.1 for 28 byte hash outputs. For an empty file, Skein hash function (224 bits) shows the following statistical data:

Entropy = 3.881976 bits per byte.

Optimum compression would reduce the size
of this 62 byte file by 51 percent.

Chi square distribution for 62 samples is 1102.39, and randomly
would exceed this value 0.01 percent of the times.

Arithmetic mean value of data bytes is 51.3548 (127.5 = random).
Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).
Serial correlation coefficient is 0.713599 (totally uncorrelated = 0.0).

Clive RobinsonNovember 3, 2008 10:05 AM

@ Akash,

"WaMM hash algorithm is broken !"

And by a relativly simple (to explain) attack.

Bruce SchneierNovember 3, 2008 10:34 AM

"Skein is slow for short messages - why?"

Actually, we think Skein is pretty fast for short messages.

Hashing a message with Skein requires n+1 Threefish blocks. For any size message up to the block size, the speed is basically two Threefish blocks. For a message between one and two Threefish blocks in size, the speed is three Threefish blocks. And so on. The minimum procesing is two Threefish blocks.

We tried to get it down to a minimum of one Threefish block, but in the end we wanted the added security of an output transform.

Bruce SchneierNovember 3, 2008 10:36 AM

"Hashing short messages is relatively slow - because of computing the initial chaining values from config block. Even when hashing 1 bit, 3 blocks (3 times 72 rounds) are processed. I don't understand why not just 1 block.

"Of course the first block can be pre-computed (for each required configuration), but that requires more memory - and it's just not an elegant solution."

Of course it's an elegent solution. Look at the MD/SHA family. They all have different H_0 values. That's what we have. This is what we do, only instead of having random H_0 values we have one that has some justification to it. It's no different; we expect that hardly any implementations will calcualate the configuration block on the fly.

TorgoNovember 3, 2008 2:47 PM

Bruce,

Can you comment on the relative strengths/weaknesses of Threefish? Would you consider it is good general purpose cipher? Better/worse than Twofish? Thanks!

addictNovember 3, 2008 6:02 PM

I'm betting these (currently known) candidates will be selected for the competition by NIST:
CubeHash
Boole
Groestl
Keccak
Maraca
MD6
Skein
BLAKE

CombatFighterNovember 4, 2008 12:54 AM

I have noticed that several of the candidates have just the names of their functions, but they did not publicized the specifications. Why? Are they afraid that someone will break the algorithms before they even start the competition? I have noticed also that some of the algorithms (at least two) have significant differences between the C code and the specified documentation.

PiwotNovember 4, 2008 1:53 AM

I'm betting that the winner will be the fastest and the safest algorithm. Skein is its name!!!!

PiwotNovember 4, 2008 5:10 AM

Ups, new kids in the block: BLAKE is almost as fast as Skein in 64-bit mode, but 2 times faster in 32-bit mode. Blue Midnight Wish and Edon-R (it seems from the same authors) are much faster than Skein. BUT are they secure??!?!?!

addictNovember 4, 2008 11:50 AM

Update: weakness has also been shown in submission EnRUPT(http://lj.streamclub.ru/papers/hash/enrupt.pdf).
I think weak submissions will be weeded out fairly quickly.

I also think that NIST should publish all the submissions it has recieved now. This way the public could help with the selection and perhaps learn some new thing about hash functions.

Stumbling noviceNovember 4, 2008 4:38 PM

Some stupid? questions:

EnRupt-512 is stated as having 256bit security..
How much ram do I need? 2^384 words??
How is 2^480 operations = broken?


Maarten BodewesNovember 4, 2008 5:07 PM

In the paper it is stated that Skein could be used as a MAC function. Skein however seems to need the actual key material for this. One possible problem is that because of security reasons the data itself is not available to the hash function (e.g. because it is in a hardware device that only allows encryption). Do you see this as an issue? A possible solution could be to use a single block encryption of a known value (00h values as used for KCV's for instance) instead of the key. It would still perform well, because the answer would be static and can be cached. It also might prove important for certain ancient encryption techniques where the key may or may not contain spurious information (such as checksum bits). Of course, HMAC will always be available, but this will introduce an expensive encryption operation.

PS. For fun I'm creating a Java implementation of Skein directly out of the specification. I will first try to create a Java security provider around Threefish (implemented for the encryption operation, but not tested yet) and Skein (todo).

PeterNovember 4, 2008 5:19 PM

@Stumbling novice

The security of cryptographic hashes are usually measured against three basic criteria:

i) pre-image resistance, given a specific digest how much effort does it take to find a message that will hash to that same digest

ii) collision resistance, can you find two different messages that hash to the same digest

iii) second pre-image resistance; given a specific message, can you find a second different message that produces the same hash value

For an n-bit digest from a secure hash you'd expect to have to do as much computational work as 2^n hash invocations to solve (i), 2^(n/2) to solve (ii) and 2^n to solve (iii). Notice that solving (iii) implies you can solve (ii).

Now, in a practical sense that doesn't always mean the algorithm is weak - say for example you have a hash function which produces a digest of 512-bits in length, then you'd expect to have to do 2^256 work to find a collision. If you can find a collision in 2^250 work, say, then the algorithm is theoretically weak but that may have little practical relevance. Having said that, attacks on an algorithm are only going to get better so a theoretical attack may be an indicator for the future - which is why NIST has created the SHA-3 competition in the first place (there are serious questions over SHA-2 family).

PeterNovember 4, 2008 7:23 PM

Does anyone know when NIST is going to post the sucessful submissions? I'm guessing there will be a fair number we haven't seen as yet.

AkashNovember 4, 2008 9:50 PM

December 2008
---------------
NIST plans to initially do a completeness check to make certain that every entry satisfies the requirements set by the government. The resulting list of submissions will be posted online by the end of the year, Burr said. In early 2009, the agency will hold a cryptography workshop to discuss the submissions. A second workshop will likely be scheduled in early 2010, by which time NIST aims to have the field whittled down to 15 algorithms, Burr said.

http://www.securityfocus.com/news/11536/2

AkashNovember 5, 2008 9:31 AM

@Bruce
First one year, we should evaluate theoretical importance of each hash algorithm. We should not worry about speed.

"The contest, run by the National Institute of Standards and Technology (NIST), seeks to find a strong replacement for the current family of hash functions, some of which have been shown to be cryptographically weaker than originally thought."

Peter MaxwellNovember 5, 2008 6:11 PM

@Torgo:"Sgail broken"

Yes, that was one of my most momentous "Homer Simpson" moments... d'oh! Next time I spend the best part of a year on something I'll get someone else to double check that I didn't miss anything obvious out, and preferably before any submission deadline.

Guess I'll just have to amuse myself with analysis of the other candidates :-) Mwahahahaha!

Hagen FuerstenauNovember 6, 2008 7:22 AM

Perhaps I'm missing something, but I think the definition of the configuration block in the paper doesn't match the reference implementation and the provided precomputed config values.

In Section 3.5.2 a 32-byte config string is defined and Section 3.5.4 applies UBI to this string. The implementation however seems to pad the config string to a full block before applying UBI, therefore computing different results for Skein-512 and Skein-1024.

Doug WhitingNovember 6, 2008 9:41 PM

> I think the definition of the configuration block in the paper doesn't match the reference implementation and the provided precomputed config values.

I wrote the Skein code, and I'm don't see the problem you're referring to. Yes, the block is zero padded -- you have to pad with something known when you process a partial block. However, the LENGTH given to the block processing call is only 32 bytes. I'll be the first to admit that my code may not always be the easiest to follow, but I think in this case it is correct. If not, please point out the problem in more detail and I'll be happy to look at it.

Hagen FuerstenauNovember 7, 2008 4:30 AM

In line 273 of skein.c you call:

Skein_512_Process_Block(ctx,cfg.b,1,sizeof(cfg));

Since sizeof(cfg) is 64, Skein_512_Process_Block should get a length of 64 bytes here, which it then writes into the tweak value.

Doug WhitingNovember 7, 2008 1:22 PM

Whoops, you are right! Sorry about that. I think that my problem was that I needed a full-sized block buffer, so I ended up using cfg for two purposes and forgot that that changed its size.

Thanks for catching this. We'll have to change the code (and vectors) to match the spe, which is correct. I am a bit confused because somebody else on our team did a different implementation and matched my results (we did this just to catch such a bug), so somehow they must have made the same mistake.

CombatFighterNovember 7, 2008 7:50 PM

@ Doug Whiting

Does this means that Skein is out of the game as improper submission? If NIST allows you to make a minor fix, then they should allow minor fixes on many other submissions too, including broken ones!

PeterNovember 7, 2008 9:34 PM

@CombatFighter:"If NIST allows you to make a minor fix, then they should allow minor fixes on many other submissions too, including broken ones!"

Personally, I'm hoping that minor fixes are allowed as my own algorithm was "broken" by an oversight which I didn't pick up until after the deadline (was a very odd feeling publishing a collision for my own submission... anyway...).

Importantly, in this case, the security of Skein isn't affected so one (namely NIST) could decide whether the reference implementaton or the specification is authoratative and base the evalutation on that (which in the end wouldn't affect the analysis)

My own guess it that something as trivial as the error here isn't going to be an issue, and in other cases the issue will likely be determined over a longer period of time with regards to the amount of public interest and type of fix required, i.e. a coding or small specification error may not be important, but a major design flaw could be.

The process, as far as I see it, gains a lot of benefit from public involvement and as such any public support/disapproval should be the principal determining factor in these situations - although others may and probably will disagree with me here.

If the NIST submission criteria were taken in a very strict sense, then (from my own insight) a lot of the submissions will probably fail or be border-line on qualifying as a "complete and proper" submission - so we've still to see if there's a cull of algorithms when NIST publishes the candidates.

RainsfordNovember 7, 2008 9:44 PM

@CombatFighter

My general understanding is that an algorithm specification is considered authoritative, and that inadvertent mistakes in C code are not considered official components of the algorithm. This is to avoid confusion from unclear code or even incorrect implementation (for designers with less than perfect coding skills). Fixing a bad parameter in the reference code is not a minor fix to the algorithm, it's a minor fix to the reference implementation to make it match the algorithm.

PackagedBlueNovember 8, 2008 1:35 AM

Submitted code error proves why wise people pay lots for excellent and correct crypto code validated by many, rather than just using what is typically found.

A Gnupg/PGP with Skein related enhancements and a proven history before SHA-3 is chosen, would really be a great contribution. Sure will take a lot of people to make this happen.

I would hope NIST ignores code issues early in the submission stage, especially with 64 bit.

I wish Skein the best of implementations and review.

Clive RobinsonNovember 8, 2008 6:49 AM

@ Paeniteo,

"You can always make a hash function as slow as you want, if you apply it, say, 1.000.000 times to the password before storing it into a database or using it as a crypto key."

I do wish people would stop making the "just do it more" statment as it has some quite nasty little assumptions behind it which will turn around and byte people in the lower regions if they are not cautious.

As a possibly over simplistic explination (so all can join in),

Cpas = Ppas XOR Skey

As a single operation Shannon showed it was provably secure, which suggests it is quite a strong primative.

However if you do the operation twice, you get

Ppas = (Ppas XOR Skey) XOR Skey

Which is obviously not secure , but further it does not matter how often you do the function you get only one of two results Cpas or Ppas.

Now all crypto primitives are bounded in some way or another (usually by which ever is smallest, the size of their output or size of their state array).

However there is an assumption that under all conditions the primative when chained will behave like a counter that is mapped by some (encryption) function and will step through every possible output value in an apparantly random way.

Without considerable care this is usually not the case, and in most cases for less than obvious reasons.

For instance with a single type of primative operator as shown above with XOR it can be clearly seen chaining it is pointless.

likewise with ADD any Skey number that is not relativly prime to the size of the output will miss output values with some values of Ppas. Similarly with MUL.

However if you view MUL as being a logical extension of doing ADD a fixed but many number of times, you are in for a bit of a shock.

Under certain circumstances the repeated additions in a MUL can be replaced with an XOR and ADD. Effectivly the many times workload of the MUL is short circuited to a short cut using just a a couple of primatives with little workload.

Finding the short cut might be difficult but proving there is not one is a much more difficult task. And although It might take a lot of work to find the short cut an attacker only has to do it once...

Further there is an assumption made that "mix and match" of different primative operations will add "magic pixie dust" to the recipie (the original permutate, transpose and repeate).

There are occasions when they can cancel each others effects out, and spotting those is also difficult...

The point is, simple as the relationship between chaining and workload appears it is not.

PeterNovember 8, 2008 2:33 PM

@Clive Robinson, immediately above.

I think that Paeniteo, in this example at least, is correct in his assertion.

I may be wrong but the idea of iterating the hash function x number of times to increase the run-time is codified in PKCS #5 (PBKDF) and is even used in Bruce's PasswordSafe software.

This obviously operates under some assumptions; off the top of my head you would at least require the hash function to be resistant to pre-image attacks, it should be bijective (or very close) and it should have no short cycles either on the whole digest or on a sub-set of those bits. Which conveniently enough are all properties without which the hash function is weak in almost every other scenario as well.

The example you used of a one-time pad, I would suggest, isn't used correctly. I would argue that increasing the iterations" here would be analagous to using more than a single pad - which wouldn't necessarily increase the security but would certainly not weaken it. Again, with your example of addititive and multiplicative operators - this can be extended to exponentiation in a finite field giving the well known problem of discrete logarithms, or for that matter the factoring of two large primes.... both of which under the correct conditions are secure constructs.

Your point that there may not be a simple relationship between chaining and required workload I would certainly take as valid, but personally I think the main dangers are from the inappropriate use of primitives rather than the iteration of a secure primitive.

Maarten BodewesNovember 8, 2008 8:58 PM

Currently, with my own code, I do see the initial chaining values to be correct for 256-256, 512-512, 1024-512 and 1024-1024. I get different values for the other ones. I had a family party today so I could not get any work done, but I'll be investigating tomorrow. My first attempt at the threefish worked directly as expected (!), but I had some fun with converting to long values (I'm running Java) so my input was incorrect at first attempt. I *hate* working with LSB, it's just not natural. Also my tweak was off. Note that I haven't reproduced a hash yet, but I have still strong hopes that that's just me (working on Skein after having full working days at the company I work for).

Clive RobinsonNovember 9, 2008 3:06 AM

@ Peter,

"Your point that there may not be a simple relationship between chaining and required workload I would certainly take as valid, but personally I think the main dangers are from the inappropriate use of primitives rather than the iteration of a secure primitive."

The main danger I was trying to point out was that of "cryprography is easy if you follow the rules" mentality of the majority of people that implement it (ie software coders developing product).

They see something that looks like a "common sense rule" and apply it across the board without further understanding and consideration.

It's why I said,

"I do wish people would stop making the "just do it more" statment as it has some quite nasty little assumptions behind it which will turn around and byte [sic] people in the lower regions if they are not cautious."

As for the use of OTP as part of my explanation it was the simplest "provably secure" operation that I could think of that any working code cutter would understand. Thus showing that using something "provably secure" "crypto goodness" in one context does not carry forward into a similar but different context.

The problems with trying to find simple general understandable examples to explain the issue in a short blog post is not the easiest of things to resolve.

I guess I only get a B- for effort 8(

Maarten BodewesNovember 9, 2008 5:08 PM

OK, I got the initial chaining values & the hash function working now (for all simple Skein configurations). Can someone explain please why I need to have 64 instead of 32 as configuration size to get to the configuration values?

I'll further optimize the UBI -> threecipher interface and I will try and create a even more readable and logical implementation. Then I'll integrate it with Bouncy Castle.

Then I'll go for the decrypt of threefish and get it optimized even further.

Maarten BodewesNovember 10, 2008 5:50 AM

"OK, I got the initial chaining values & the hash function working now (for all simple Skein configurations). Can someone explain please why I need to have 64 instead of 32 as configuration size to get to the configuration values?"

Stupid, stupid, this was obviously the problem that Hagen Fuerstenau was referring to. This is why I was trying to create an implementation from scratch, without looking at the source code. If anyone wants to have the correct values, please ask. My code is written in such a way that it should be really easy to verify (configEncoding.length).

The only other thing I ran into was order of the tweak values. If the tweak is seen as one long number, then the ordering is correct. If it is seen as a byte array converted into two longs, then the ordering in the implementation is incorrect. Otherwise I had no problems that I could not blame on myself.

@Warlock: give what up?

Maarten BodewesNovember 10, 2008 12:40 PM

@Tomas
Could you send me a mail if I could use your code for a faster implementation for inclusion in the bouncy castle provider? I understand that its a port of the code from Doug Whiting, but I think it is only fair to ask (and I could not find your mail address on the site). My mail address is maarten.bodewes [at] xs4all.nl . Of course I'll put you & Doug in the "based on" section. Thanks.

Thomas MuellerNovember 10, 2008 11:26 PM

@Maarten
I sent you a mail. Of course you can use the code, it is public domain (see also the
source code "This algorithm and source code is released to the public domain"). Please CC me in case there are problems.

asdfNovember 12, 2008 3:39 PM

Of the listed co-authors, M. Bellare is the only one with any credentials in the cryptographic community.

gregNovember 13, 2008 8:06 AM

@Clive Robinson

I agree with your general point. However in this context of a "hash function is too fast" I think I still have a point. like with a hash cash type approach.

when i do hash chaining to make dictionary attacks less cpu easy, I include a counter..

ie H_{i+1}=HASH(salt|| counter|| H_i)

the number of chains is a password parameter like the salt. I use quite large salts...and set the iteration count to be about 0.5-1 sec on the machine...

Of course this is still not secure really. It just makes kiddie hackers slower...Preventing off line attacks is where the effort should be done. But I am giving up on the good passwords from users now (or forcing them to use good ones...).

PeterNovember 13, 2008 9:58 AM

@greg:' However in this context of a "hash function is too fast" I think I still have a point. like with a hash cash type approach.'

I think you're missing the point here Greg; you can make a fast hash function arbitrarily slow (your construction would be an example), you cannot make a slow hash function faster. So as long as the hash function itself obeys certain security criteria, the fast hash function is better as it covers both scenarios.


'Of course this is still not secure really. It just makes kiddie hackers slower...Preventing off line attacks is where the effort should be done'

The iterative idea is to do just that - make off-line attacks more difficult. If hashing a message m takes t time then doing a PBKDF style construction, then with i iterations it will take i times as much computing power for anyone - script kiddie or not.

Any basic timing issue would be down to the fact that the computational effort only grows linearly with the number of iterations - so 1,000 times more work on a desktop might be bad, but on a grid computer it may be proportionally smaller.


Clive RobinsonNovember 13, 2008 12:12 PM

@ greg,

Yes you do have a point and it is one way to go (if done the right way ;)

Now the real question is can it be done in a way where there is an exponential not linear rise in effort with the number of iterations so that we can get off Mr Moore's et al, downwards security slopes for a while?

@ Peter

Any thoughts on this?

PeterNovember 13, 2008 4:20 PM

@Clive Robinson:"Now the real question is can it be done in a way where there is an exponential not linear rise in effort with the number of iterations so that we can get off Mr Moore's et al, downwards security slopes for a while"

Personally, I would doubt it. I should probably expand my last post because I seem to have missed the crux of the problem.

Normally to verify a password the host will take the supplied user's password, hash it with a salt and compare the resulting digest with its recorded digest. If an attacker wants to brute force, he/she can begin by trying the password candidates in turn with the most likely first. Now assume that the attacker has to try k passwords (where k is assumed to be reasonable as compared to normal password complexities), and that the time taken (or more appropriately the work required) to compute a single hash result is l. Then for a host to verify a password it takes l time, whereas an attacker will expect to expend k.l.(1/2) time (or work - especially since the attacker will likely highly parallelise the computation).

In the PBKDF the initial password and salt are hashed i times, so the host has to do i.l work, while an attacker can expect to need i.k.l.(1/2) work.

Hence the linear growth. The problem arises because the host's effort in verifying a password also grows linearly, but a few seconds for a host to verify a password (usually) isn't a problem - whereas in an attack scenario that i factor may make an attack infeasible.

You could in theory create a construction (I think) where the computatal work required is exponential in i, but that would also mean the work required to verify the password on the host is also exponential in i - making it unworkable.

As far as I can tell the only way to improve this scheme without modification is to improve password complexity, hence increasing k which only affects an attacker.

As long as the hash function is pre-image resistant (and probably collision resistant, if we need to be strict about the argument), and that the block size contains more entropy than the assumed password set - then it also doesn't matter what hash function is being used (we can just change i to adapt). A result which is not necessarily intuitive.

There are other authentication methods availble which either move the password problem to the client (and thus negating the avanue of an attacker gaining another user's password), or remove the necessity for a password completely. Public key authentication (moving the password problem to the client - i.e. the password used to protect the private key) and certain token authentication (one-time password schemes) come to mind.

If you're serious about authentication security, I'd strongly suggest either a public key, or a decent token or cryptocard solution.

gregNovember 14, 2008 8:47 AM

@peter

I agree totally. The original comment came from a complaint about skein hashing too fast.

I say script kiddie because thats really the only attacker that won't use a cluster.... Password complexity is a great solution but even forcing some numbers in there is hard enough. I often got overruled etc. I try to encourage people to use words from other languages or acronyms from a pass phrase. But the weak link is always some high up manager who thinks no one will guess his mistress birth date.

These are also places where tokens are out....But then this is not a bank and we don't have gold....

My problem is that a password in a 100% online fashion is pretty good. Its the off line weak link...

Nicholas ParimoreNovember 19, 2008 6:56 PM

I have a thought regarding using a slower scheme. It involved building a set of secure ciphers and hash functions out of operations that run slow in software and hardware. I noticed that asymmetric algorithms can be thousands of times slower than symmetric ones. Likewise, some algorithms are faster than others in any implementation.

I was wondering if it would be possible to use similarly slow operations or difficult math to implement crypto primitives that could not be parallelized or easily sped up. On modern hardware, we'd be leaning more towards KBps rather than MBps. Such algorithms would then be reinforced with current iterative techniques. I think an algorithm that's nearly impossible to optimize would be nice for future-proofing efforts.

Can it be done? Are there any cryptographers working on this sort of thing? BCrypt hashing is similar in concept, slowing it down at the cipher level, but I don't know any others. Thanks ahead of time. ;)

PackagedBlueNovember 24, 2008 3:23 PM

Blowfish set up time can be ~ what you want. Might be some way to use this for hashes.

OpenBSD is easy to set rounds for localciper.

PeterNovember 28, 2008 7:43 AM

@Nicholas Parimore:Why try and design something slow when you can take something fast and iterate it 'n' number of times to make it as slow as you like? The PBKDF stuff I was talking about further up the list does what you're asking - its really only parallelisable in the number of attempts at one single time, which is pretty much algorithm independent anyway.


@PackagedBlue:There is a way to do this, I'd mentioned it further up the list... PBKDF (c.f. PKCS #5).

AlexNovember 30, 2008 12:47 PM

How to get Threefish sources? It's very nice algorithm, but no implementation worldwide... ((

Maarten BodewesDecember 2, 2008 6:52 PM

I've finally found the time to put my Simple Skein java implementation on line at http://www.xs4all.nl/~warper/. It has got a boolean switch to use either the block size (wrong) and the configuration size (correct) as input for the first tweak value. More info on the (very basic) page.

@Alex: It actually contains a file called Threefish.java (and ThreefishKey.java) that implements block encrypt/decrypt.

Maarten BodewesDecember 4, 2008 7:33 PM

My Skein page has been updated to include new source code because of a last minute bug that crept in. I've also published my generated test vectors for comparison with the official test vectors and some intermediate values for the Threefish encryption of a single block (4 rounds) so that other developers can compare their debug values.

Marc KaufmanDecember 10, 2008 11:45 AM

If you want to slow password processing on one machine only, you can pick an iteration count that gets you (say) 0.5-1 second of processing time on that machine. But it's harder if you want to process passwords on 64-bit machines and on handhelds/mobile phones. No one wants to wait 10 seconds for a file to open.

A more productive approach to inhibiting offline attacks is to use an algorithm of several hashes that changes with the key/salt, so that you can't run 100 in parallel on a GPU array.

KasilingamDecember 15, 2008 4:57 AM

@Bruce: Trivial Pseudo collisions happen when improper IVs are chosen. Suppose the algorithm sustains all attacks. But it is weak because of chosen bad IVs. What do you think about the hash algorithm?

KasilingamDecember 15, 2008 5:06 AM

@Bruce: Khichidi hash algorithm is good. It is mentioned in a generic manner that anyone can put random IVs. [Trivial pseudo collisions happen when IVs=0]. Let us discuss.

Nicholas ParimoreDecember 19, 2008 10:08 PM

@Kaufman. That is the problem with iteration-based hardening that I wanted to deal with. Since I can't know how weak the client device will be, I have to use the lowest common denominator to ensure they are supported. The multiple algorithm method you mentioned is probably the only way to do it at the moment, although I was more worried of FPGA's than GPU's. ;)

@Peter. Yeah, that would work. A philips-head screwdriver can also work with other kinds of screws given enough time, but it's convenient to have purpose-built tools for them. An algorithm that establishes a baseline speed that can't be significantly sped up provides extra assurance. That's unlike some modern MMX- or SSE-enhanced algorithms, or Skein's hash-tree mode. I'm currently looking into hardware ciphers like VEST that can't be implemented efficiently in software. That's a start, but I'd like more mature algorithms.

Sam TrenholmeDecember 23, 2008 12:40 AM

Looking over the Skein paper, section 5.4 talks about the possibility of a Skein variant that uses in 32-bit words. It states "At this point, we have not searched for rotation or permutation constants for a 32-bit variant, nor have we analyzed it to determine how many rounds would be required for security"; I know you guys are really busy (and I wish you all seasons greetings), but this is something I hope is done.

There are still a lot of 32-bit processors out there, and Keccak (which has most of the same flexibility as Skein) already has a 32-bit variant, albeit not as a SHA-3 submission.

PeterDecember 25, 2008 8:28 PM

@Nicholas Parimore:"An algorithm that establishes a baseline speed that can't be significantly sped up provides extra assurance. That's unlike some modern MMX- or SSE-enhanced algorithms, or Skein's hash-tree mode."

I think the point has been missed. There are very few applications where a hash algorithm being slow is actually preferred - PBKDFs are one of them. In that scenario, the attacker has to use the same hash in exactly the same manner as the implementation - which is unlikely to be a hash-tree. We can also tacitly assume that MMX or SSE gains have already been factored into the implementation's iteration count.

So in effect, the speed-ups you talk about are already accounted for. If brute-forcing, then the only way to really improve speed is to parallelise it (or create a massivly parallel hardware implementation) which means the benefits of any purpose built algorithm are essentially redundant.

Warlock Arkhinos RatazmusFebruary 15, 2009 11:16 AM

Maybe I should elaborate on my "give it up" comment posted earlier.

Simple.

I cracked MD5 long before rainbow tables, and more efficiently, by utilising 128bit code instead of plain old 16bit. In short, I was generating 4 hashes simultaniously. Then I decided to create a table made from the first byte (I count MD5 as 16bytes as, it is afterall, a hex output) and had a rather fast lookup table - albeit large - too large to finish I admit, but what the hey - I proved how useless MD5 is.

That principle stands sound with ANY hash you care to create.

Now, considering a "faster" hashing function is somewhat defeating the purpose of hashing it. WHY ? It means it'll be cracked a lot quicker - thus any deficiencies in the output is quicker to trace (collisions, blah).

Finaly, I've started work on my own hashing function stolen from the MD5 routine that i've dubbed MDx. It's taken me a year to "brain" it all out, but in essence it's not a hashing fucntion that will be broken quicker than most of the static routines you guys think are "safe". Mainly as it relies on randomisation and takes time to encode - on purpose.

Listening to you guys thinking "wow, speed is good" - wrong. "64bit" - why ? Most of us can code 128bit instructions, or did'nt you know that most systems are capable of this ?

I'm firstly a blackhat, i'm secondly a security guru. If I can find a fault then i'll exploit it, then fix the fault later. What i'm trying to point out to this thread is this ...

... you'll fall if you don't stop to think through EXACTLY what you're doing.

PLEASE THINK ABOUT IT FROM A CRACKERS ANGLE BEFORE SAYING HOW GOOD IT IS, PLEASE !

CollinMarch 2, 2009 4:22 PM

According to the article, the skein hash function is capable of producing arbitrarily long hash sizes. However, it has only a finite state. How do you prevent longer hash sizes (longer than the state) from having exactly the same number of collisions as normal ones (same size as the state)? Have I already answered my question for you?

aureMarch 24, 2010 10:16 AM

Hey there,
I refer to the source code version 1.1. In the implementation of the Skein block function there is missing a part of the key schedule: the addition of the subkey number to the last word of the subkey.

Am I right?

Greets, aure

I.LopitNovember 27, 2011 3:28 PM

Where i can find test vectors for each round and key shedule?
English not my native language and its diffical for me(

ashSeptember 21, 2012 12:16 PM

Hi,

I am trying to implement the tree hasing feature for larger files to use multi-core parallel processing. Are there any test vectors in v1.3 for verifying the results?

Vykintas ҆aknysOctober 22, 2013 3:44 AM

Hi,

I am wanting to implement Threefish and Skein hash function, and want to know if they patented ?

Thanks.

Leave a comment

Allowed HTML: <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre>

Photo of Bruce Schneier by Per Ervland.

Schneier on Security is a personal website. Opinions expressed are not necessarily those of Co3 Systems, Inc..