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.

I understand that for example MD5 produces a 128 bit hash value from a given text of variable size. My question is if there is a hash-like algorithm that will produce a hash value where one can specify the length of the outcome? So one would specify that that given any input the hash value (output) should be say 1000 bits.

For example, I would like to produce a hash value of the same length as the input. One way that I had thought of doing this would be to just encrypt the input somehow, but this would probably be easy to break, since one would just decrypt.

Another way I had thought about would be to divide the input up into say 128 bit chunks and then do MD5 (or some other hash) on each part and then just create one long string with the hashes of all the strings. However, I can see that a change in the input in one byte only would change 128 bits of the output.

share|improve this question

5 Answers 5

up vote 7 down vote accepted

As D.W. notes, you can use the output of any conventional hash function to key a stream cipher (or a block cipher in a streaming mode like CTR), and then take the output of the cipher as your digest.

However, there has been a trend in modern hash function design to support arbitrary-length output directly, without the need for additional layers. For example, the cryptographic sponge construction has this feature built in: you absorb the input into the sponge and then squeeze as much output out of it as you want.

Out of the five SHA-3 finalists, two — Skein and Keccak — support arbitrary output lengths. Keccak does this by virtue of being a sponge hash; Skein instead internally uses a system very similar to D.W.'s CTR-mode construction, reusing its Threefish tweakable block cipher for both input compression and output generation.

The SHA-3 competition is still running, even if the original schedule called for the winner to have been announced a few months ago. Still, the fact that all the finalists have survived so far does indicate that they're most likely all more than secure enough for practical purposes.

share|improve this answer
    
Actually, the SHA-3 schedule is "by the end of 2012" so it's about where one would expect. –  Jon Callas Aug 21 '12 at 19:19
    
Note that the arbitrary output length unfortunately is not considered by NIST, so it remains to be seen if this feature will receive as much scrutiny as the use of specific size hashes. And if a finalist actually contains the feature, then it may not be present in many implementations, as the method of generating a random output is not defined. –  owlstead Aug 25 '12 at 16:30
1  
As a note to future readers, here we are a year after most of the answers to this question were written, and the SHA-3 contest has now been decided. Keccak was selected. –  Reid Sep 4 '13 at 13:18

Sure. If you want a $b$-bit hash of the message $m$, then use the first $b$ bits of AES-CTR(SHA256($m$)). That'll do the trick.

In other words, compute SHA256($m$) and treat the resulting 256-bit string as a 256-bit AES key. Next, use AES in counter mode (with this key) to generate an unending stream of pseudorandom bits. Take the first $b$ bits from this stream, and call it your hash. (Make sure you don't treat the IV as part of this stream, as the IV won't be pseudorandom. You may need to manually remove the IV first before taking the first $b$ bits.)

Security. This should be secure as long as $b \ge 160$ or so. In particular, a collision attack is expected to take about $2^{\min(b,256)/2}$ steps of computation, given our current knowledge of AES and SHA256. So, as long as you don't choose a value of $b$ that is too small, you should be good. Choosing a value of $b$ larger than 256 does not give you greater security against collisions, but that's irrelevant: the level of security will already be way more than enough for any reasonable application, so you're good.

share|improve this answer
    
This might be a silly question, but can you pass a zero-filled buffer as plain-text (of size b bits) to an AES block cipher (say CBC or whatever), use the SHA-256 hash to derive the key and initialization vector, and then take the first b bits of cipher-text to be used as your output? Is this just as secure? See gist.github.com/4600432 for Node.js implementation. –  BMiner Jan 23 '13 at 0:35
    
@BMiner, it depends upon the mode. For CBC mode, this will work as long as you make sure to first remove the IV (since the IV won't be random), and take the first $b$ bits of the remaining ciphertext. I would expect something similar to hold for other reasonable modes too but I haven't thought about it carefully. –  D.W. Jan 23 '13 at 9:30
    
thanks for your response. What did you mean by, "make sure to first remove the IV?" In Node.js, if you pass a "password" into the Cipher's constructor, a key and IV is derived using EVP_BytesToKey. This means that the IV won't be random, but isn't that the idea? If the IV was random, you wouldn't get consistent, predictable hash results? –  BMiner Jan 24 '13 at 15:51
1  
@BMiner, sometimes some crypto libraries will generate the IV for you and include the IV in the ciphertext. In other words, when you encrypt, you pass in a key and a message, and you get back a ciphertext, where the ciphertext includes the IV somewhere in it. If your library is like that, you need to remove the IV (and make sure that the IV always starts at 0). This gets easier if you implement AES-CTR yourself, so you can force it to start at IV 0 and make sure that the output only includes the generated pseudorandom stream (and not the IV). –  D.W. Jan 24 '13 at 19:11
1  
@curious, that's a different question, which is probably best answered separatately, but the concise answer is: treat the output of SHA256(m) as a 256-bit integer, reduce it modulo 360, and use the remainder a syour random number. –  D.W. Mar 18 at 17:41

In general, each combination of a (secure) hash function for input with a (deterministic) pseudo random number generator for output will work here - one "state of the art" example is the one given by D.W. (using AES-CTR as PRNG and SHA-256 as hash).

Another way is similar to what PBKDF-2 does to have output with the right length: hash the input (or a hash of the input) multiple times, each with a different prefix, and concatenate these outputs:

output = H(1 || M) || H(2 || M) || H(3 || M) || ...

(One could say that this is a special case of the general case before, at least when H is already a hash of the original message.)

There are some hash functions with a "arbitrary output length" mode, such as Skein (one of the SHA-3 candidates). (This mode of Skein internally works just like the scheme above, but it is hidden in one standardized primitive, you don't have to build this yourself.)

share|improve this answer

I'm curious about your purpose. Generally the primary operation involving a message digest is ultimately to compare two digest values. Hashing passwords allows comparing the digest values instead of carrying the super secret password around the systems. Hashing messages allows the transmitter and sender to verify the data was correctly received without resending the whole message. Encrypting a hash with a private key allows them to be decrypted with the public key and then compared to verify the signer's identity. Even hashing strings in a database allows an efficient indexed search by comparing and sorting digest values.

In every case of comparison, having the digest values be of equal size enables the comparison - unequal sizes would never result in an equal result.

If it's a size constraint, a cryptographically secure digest value can always be truncated with the understanding that there is a corresponding loss in fidelity. (A non secure digest algorithm might not have the bit dispersal properties that would make such an assumption safe.)

But you've said you want a "larger" digest. When I think about the meaning of digest, to me that is a "summary", which is always smaller than that which it summarizes. What are you hoping to gain by making it larger? Is it a matter of not trusting in the anti-collision properties of 2^256 possibilities? You have piqued my curiosity.

share|improve this answer
    
Thanks for the answer. Since you asked: The reason for my questions wasn't deep at all. I had thought about padding of keys/passwords, and was thinking that instead of padding key, one could just generate a hash of a specific length of a key. Thereby all key lengths should be "allowed", but I don't know if this is secure. I will probably ask a question about this later after I have thought more about it. –  Thomas Aug 20 '12 at 23:21
    
I see what you were going for. Random bytes are now generally used for key padding instead of a fixed value, to avoid providing a crib to an attacker. The key attribute to those bytes is unpredictability so they can't be used against you. I can see why a hash could be something you'd consider using instead of random values, but it would still have to be the hash of something random so the attacker couldn't use it. When you get that deep, cryptographically random bytes are already a very good solution to this problem. –  John Deters Aug 26 '12 at 5:15

Yes, there are hash-like algorithms that are able to produce variable-length outputs without any extra efforts. This is something "sponge functions" do. One such sponge construction is KeccaK which is one of five finalists in the SHA-3 competition.

share|improve this answer
    
What is the hash value of SHA-3? or how big a hash value do sha3 produce? –  user8238 Sep 4 '13 at 12:28
1  
SHA3 is not yet standardized, the resulting digests are therefore not available. Keccak test values range between 1 bit and 1599 bits in theory with a single "squeeze" –  Richie Frame Sep 4 '13 at 16:46

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.