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've been recently looking into the creation (and theory) of hash functions, however I just can't figure out how to turn a message into something of a fixed length.

At the moment, my theory of a hash function is like so:

  1. Take in the message (e.g. "secret")

  2. Split it into different 'blocks' (e.g. "sec" + "ret")

  3. Mix them up, and interact different blocks depending on what block type they are (perhaps block type would be determined by mathematical calculations on the character values, and then certain blocks would interact with other blocks to merge in a weird way to create another block).

This creates a message which cannot be undone (since at the end, you don't know what the block types are - and even if you do, you don't know how they interacted to get to those blocks) - however it is not of a fixed length.

What would I do to create a fixed length digest?

share|improve this question

migrated from security.stackexchange.com Nov 23 '11 at 17:04

This question came from our site for Information security professionals.

    
Welcome to Cryptography Stack Exchange! Please register your account here, to be able to comment and accept an answer. –  Paŭlo Ebermann Nov 23 '11 at 17:19
    

3 Answers 3

up vote 2 down vote accepted

Create your one for learning, very simple?

a  = b = c = a0h;
for (every byte "byte" from input)
    a = a XOR byte;
    b = b XOR a XOR 55h;
    c = b XOR 94h;
end for

print a, b, c;

The output size here will be always only 3 bytes (assuming a, b, c are bytes), independent of the input size. In each step of the loop consumes one more byte of input, and somehow merges it into the state of the variables, finally outputting these variables.

(This is not a good hash function, don't use it for anything productively.)

Study a real one?

Do some search in google about the algorithms used in MD5, SHA1, RIPEMD-160, etc. You'll easily find some implementations.

share|improve this answer
    
I was hoping for more of an explanation of how it works. Why does your code make a fixed length digest? –  Joesavage1 Nov 23 '11 at 16:53
2  
Fixed-length: the output size is constant, no matter the size of the input. So, no matter how many bytes are processed, you'll have the output of 3 bytes: a + b +c (concatenated, not added). And even if your input is smaller than 3 bytes, the output will be 3 bytes. –  woliveirajr Nov 23 '11 at 17:17
1  
Just a note: In this very simple hash function's output, we (after the first input byte) always have $c = b \oplus 94h$, which means that more information is lost than necessary. Also, $b$, after an even number of bytes, is just the XOR of the even-numbered input bytes. After an odd number, it is the XOR of the odd-numbered input bytes (and 55). –  Paŭlo Ebermann Nov 23 '11 at 18:04
    
Thanks for the awesome chat @woliveirajr - I actually understand this script properly now, and it answers my question perfectly :D –  joesavage Nov 23 '11 at 20:16

Basically, typical hash functions produce a fixed-length output by the following method:

  1. They expand the input to some multiple of their block size by adding padding.

  2. They compress the first two blocks into a single block using a mixing function and repeat until only one block is left.

  3. The use a fixed finalizing function to turn that last block into their output.

As a simple example, consider a rather trivial and insecure hash function for decimal numbers that produces a one decimal digit output. It could work like this:

  1. Add a 9 onto the end of the input. Then add zeroes until the number of digits is even.

  2. If there are more than two digits, replace the first four digits with the two-digit sum of those four digits. Repeat until only two digits remain.

  3. Sum the final two digits to get the output.

This will produce a single decimal digit of output for any decimal input.

For example, take 123.

  1. Add a 9 on the end - 1239. The number of digits are even, so no zeroes appended.

  2. We replace the first four digits with their sum, 15. There are two digits, we're done.

  3. We sum the 1 and 5 to get 6. Our output is 6.

While this function is simple and insecure (because its mixing function is so bad and its block size so small) it illustrates how hash functions produce a fixed-sized output from a variable-sized input.

share|improve this answer
    
Thanks for this answer - it's really helped clear up for me how you could truncate the data. I'm a little confused at how modern day algorithms would go about this (presumably it'd need to be a lot more secure than just adding up the first four digits) - but I guess this isn't something I should be thinking about yet :P So you can truncate data using methods such as adding their 'values', but how would you go about creating filler content for content smaller than the hash? (Since it can't be random) –  joesavage Nov 23 '11 at 18:40
    
@Joesavage1 The "filler content" is the appending of 9 and 0 in step 1). –  Paŭlo Ebermann Nov 23 '11 at 19:28
    
Yep. And the reason for the '9' is so that it is not possible for any two inputs to produce the same output at the end of step 1. Everything after and including the last '9' is always the filler. Real-world mixing functions (often called 'compression' functions because their output is typically half the size of their input) are much more complicated than just summing, of course. Every output bit depends on every input bit in a complex way. –  David Schwartz Nov 23 '11 at 20:12
    
Ok, thanks :D /shortmessage –  joesavage Nov 23 '11 at 20:15

A hash function is a function with an arbitrary-length input size (e.g. $\{0,1\}^*$ or some subset), and a fixed length output (${0,1}^n$, with $n$ fixed for the function). (For cryptographic uses, we also want some more properties, like collision-resistance, preimage resistance and second-preimage resistance - for details see the linked Wikipedia article or other questions in the tag.)

How can we get something like this?

The "ideal" hash function, a random oracle, simply spits out a random fixed-size string whenever a new input string comes, and remembers all previously used inputs (returning the then-used output when one repeats). Of course, this is not usable in practice.

Most real-life hash functions work iteratively:

  • Split the input in blocks of fixed size (which might be bigger or smaller than the final output size). (This usually includes padding of the last block to get only full blocks.)
  • Take one block and some internal state, mix them together to get a new internal state. This "mixing" step is what is often called compression function, as it compresses state + block down to only state. (This is an one-way compression, not the thing used for zip and co.)
  • Repeat with the next block.
  • When all blocks are hashed, either directly output the internal state (or a part therof), or do some more (irreversible) calculations to derive the output from it (this is better to avoid some extension attacks).
share|improve this answer
    
Would you be available for a quick chat session so I can clear a few gaps in my knowledge up? –  joesavage Nov 23 '11 at 18:30
    
Feel free to come to our general Cryptography chat room, I'm almost always there when I'm online at all, and it is not too full. –  Paŭlo Ebermann Nov 23 '11 at 18:32
    
Thanks for the awesome chat @Paulo - I understand a lot more now :D –  joesavage Nov 23 '11 at 20:16

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.