I\'ve been recently looking into the creation (and theory) of hash functions, ho

Question

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?

Explanation / Answer

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,1n, 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 hash 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).

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.