Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Skein uses an additional compression function call to finalize the output, even when the output isn't larger than the native output size.

The Skein paper says:

Due to Skein’s output transformation, it remains an open problem how to create collisions or second preimages for the Skein hash function, even if one can create pseudo-collisions or pseudo-second-preimages for the compression function.

and

Output transformation. Originally we applied the output transformation only if the output size was larger than the state size. Unfortunately, without the output transform, you can construct two messages $M$ and $M'$ such that $H(M) ⊕ H(M')$ is the same as the XOR of the last blocks of $M$ and $M'$. (A similar property has recently been described for SHA-1 [101].) This violates the requirement that the hash function behave like a random mapping.

At a high level Blake has a very similar construction but doesn't use such an expensive finalization. Is there a technical reason why Skein needs such a finalization, but Blake doesn't? In particular does the non randomness issue that Skein prevents with the output transform exist in Blake? Why (not)? Is it related to the way Skein turns a blockcipher into a compression function?

share|improve this question
2  
Part of the answer might be that the block-cipher in blake has twice the hash-size, whereas in skein they're equal. –  CodesInChaos Oct 12 '12 at 11:53
add comment

1 Answer

The main reason for designing a cryptographic hash function using an output transformation is flexibility. In the following, I try to motivate the need for an output transformation.

For example, SHA-256 has no output transformation and a fixed output size of 256-bit. What happens if you truncate a SHA-256 hash value? In this case, there are no security claims at all. If something goes wrong it is YOUR fault, since you have used SHA-256 in an unspecified mode.

However, the designers of Skein claim the following levels of security against standard attacks: preimage $2^m$, collision resistance $2^{m/2}$, where m is the minimum of state and output size. It is safe to claim this, as long as the compression and output transformation are secure. It is hard to claim such a level of security without an output transformation.

Another problem is the full domain hash (FDH). Assume you are using an FDH based on RSA-2048. You want to sign messages of arbitrary length. For the sake of performance, you first have to hash and then sign the hash values. If your hash value is smaller then 2048-bit you need a secure padding. To avoid this, Skein allows to invoke the output transformation multiple times. In our case you will call the output transformation -- over and over again -- until you have an 2048-bit hash value.

share|improve this answer
1  
Your arguments are not convincing to me. The last paragraph only applies to output sizes larger than the natural output size. You don't explain why truncation requires an output transform. I'm pretty sure it doesn't. Skein's extra features and the use of an output transform for short outputs are orthogonal, as far as I can see. –  CodesInChaos Oct 22 '12 at 9:51
    
You do not need any output transformation at all. :-) In the case of SKEIN, the authors claim the following: "Originally we applied the output transformation only if the output size was larger than the state size. Unfortunately, without the output transform, you can construct two messages M and M' such that H(M) xor H(M) is the same as the XOR of the last blocks of M and M . (A similar property has recently been described for SHA-1 [101].) This violates the requirement that the hash function behave like a random mapping." -- The Skein Hash Function Family, Version 1.3. –  Christian Forler Jan 28 '13 at 10:33
    
I already quoted that section in my question. But I don't know why Skein without output transform has this property, and other hash functions constructed from a blockcipher with counter do not. –  CodesInChaos Jan 28 '13 at 10:48
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.