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 have some ideas floating around my head for exploring hashing functions, but I want to make sure what I think I know is actually true, before basing a house of cards on it :)

Let’s start with some things I’m reasonably sure of, but are still probably wrong:

  • A hash function is one such that for any given state $S$, and input bit $X$, we generate a new state $$S' = H(S,X)$$
  • This can be generalised into two functions, we’ll call them $F_a$ and $F_b$ $$H[S,0] -> F_a[S]$$ $$H[S,1] -> F_b[S]$$
  • $F_a(X) \ne F_b(X)$, for all values of $X$.
  • Selecting between different implementations for $F_a$ and $F_b$ each round is equivalent to just adding state bits
  • Hash functions that work with padded blocks of input rather than single bits are simply a performance optimisation, and can be replicated as a (more convoluted) single-bit hash by adding (blocksize-1) bits of “counter" state.
  • Any hash algorithm used for cryptographic purposes would be salted with a random initial state, and that not all state bits would be used as output (NIST SHA-3 is 2 state bits for every output bit).

These things I’m not so sure of. Given a state size of $N$ bits:

  • Recursive application of $F_a(F_a(F_a(F_a(S) \ldots)$ would ideally yield every possible value for $S$ before repeating
    • Ditto for $F_b$, of course they must be different sequences.
    • Mixing in length counter state or using a block mode is effectively an attempt to approach this goal
  • For all values of $S$, $F_a(S)$ and $F_b(S)$ would have ideally different but close hamming distances from $S$, and the average hamming difference between $S$ and $S’$ for both functions should be $\frac{1}2 N$
  • On average, the hamming distance between $F_a(S)$ and $F_b(S)$ should be $\frac{1}2 N$

I’m not sure if the above list of desirable qualities is correct, and I’m damn sure it’s not complete. I also think they may be contradictory.

Can anybody shed some light on my understanding, and let me know if I'm miles off-base?

Update:

  1. Apologies for my inability to express what I mean more clearly! The answers and comments are a big help in seeing where I'm leaving too much out.
  2. I shouldn't have mentioned the salt side of things, it's clouding the issue, as I was thinking of things like protecting passwords in stolen databases. Forget about the random start state :)
  3. I understand that the high-level definition of a hash concerns an arbitrarily long input message, and also that current hash methods work on a combination of state and padded n-blocks of input. I'm trying to satisfy my intuition that this (and the required padding) are simply internal details, and could all be generalised into a bigger state and a 1-bit block size.
  4. The reason for all this is because I'm going to do some exhaustive exploration of possible hash functions using small state sizes, to see if I can discover some general criteria for evaluating more practical large-state / large block hash functions - and also to satisfy my curiosity :)
share|improve this question
    
The initial state is usually not random, but fixed in the specification. Also, often the input is also padded at the end. –  Paŭlo Ebermann Mar 4 at 23:39
    
Your "not so sure" properties don't work as well when including a counter to the state. –  Paŭlo Ebermann Mar 4 at 23:41
    
@PaŭloEbermann understood, I only mean that the random initial state is when used for cyrpto purposes- Salting your input is just (I believe) an inefficient method to get to that random start state. –  Sophistifunk Mar 5 at 1:48
    
If the first goal is achieved maximally (iterate every possible value), counter state is unnecessary, as you will permute every possible state even with unchanging input bits? –  Sophistifunk Mar 5 at 1:50

1 Answer 1

up vote 3 down vote accepted

I'm not sure if you want to model existing hash functions with a general model, or invent a new one.

The usual general definition of hash function is a function which takes a variable length input bit string and produces a fixed length output bit string: $h : \mathbb{Z}_2^* → \mathbb{Z}_2^n$ ($n$ being the output length).

All real-live hash functions I know have some input block size (often larger than the output size), and process the input in blocks of this size. One could model this as a "processing function" $$p : S × B → S,$$ i.e. a function which maps a state and a block of input to a new state. Often part of this state is some kind of counter or other bookkeeping information, and another part is what is the cryptographically interesting one, where the pseudo-random shuffling goes on (and where you want to have your hamming criteria going on).

At the end, when we want to produce output, another transformation $o : S → O$ is used, which transforms the state to the output. In some hash functions this is a simple projection (throw away the bookkeeping part of the state and output the rest of it), in other cases it does more processing.

We also need some initial state $S_0$ (usually fixed in the specification of the hash function), and some input padding rule $pad$, to make the input a multiple of the block size.

The whole hash function can then be modeled as this:

$$h(M) = o(p(p(\dots p(p(S_0, M_0), M_1), \dots ), M_{k-1}, M_{k}))$$ with $$M_0||M_1|| \dots ||M_k = pad(M)$$ and each $M_i$ having the hash input block size.

Due to the iterative nature of the construction, we can process the input as it comes, block by block, assuming $pad$ only changes the end of the message (or at least all changes for a block depend only on the current block (and maybe earlier ones) and not the future ones).

If a programming interface allows supplying the input in smaller chunks, these are stored in some cache until a full input block is filled, and then the processing function $p$ is evaluated. If a programming interface allows supplying the input in larger chunks, these are splitted into the input block size. It is easy to create such interfaces which allow arbitrary sized input chunks, for any input block size, so the programmer (user of the hash function) doesn't even have to know that size.

Of course, we could view a programming interface which allows single-bit input as a "hash function" $H : S \times \mathbb Z_2 \to S$ like in your question, but then in most cases the state would change only by adding this single bit to a cache (and updating some input cache counter) – your hamming distance criteria is not valid at all.

This is not a problem, as long as the internal processing function $p$ comes near it, or the output transformation $o$, which is run at the end. After all, the user of a hash function is only interested in the final output, not in the internal state changes.

So your hash function model is not that useful as you imagine.

About your other points:

  • For a (cryptographic) hash function to be generally useful, it is important that it produces the same output for the same input. Using a random initial state makes this impossible. So normally some "random-looking" (or simply zero) initial state is fixed in the definition of each hash function.

    If you want a random output, you can use different primitives based on a hash function (like a keyed hash, or a hash-based stream cipher).

  • As the state is finite, if your processing function is defined everywhere, you eventually get into a loop. Usually this loop will not contain every possible state, but be a lot shorter. This is not a weakness, as it is still longer than anyone could possible evaluate in his lifetime, assuming sufficiently random behavior and a large enough state.

    In practice often the total input size is limited by some huge number so you actually don't get your loop.

share|improve this answer
    
Not trying to invent a new (useful) hash function yet, just making sure experiments in small finite hash functions might yield useful insights. –  Sophistifunk Mar 6 at 4:08
    
I know that loops will occur before you exhaust every state value in practice, and that so long as they're long enough it's not an attackable weakness, but I'm trying to get confirmation from those that know more than I do that in general the longer the state loops are, the better? –  Sophistifunk Mar 6 at 4:24
    
To reach a longer loop size (longer than the expected value in relation to the total state space), you'll need more structure in your processing function, which might make your total hash function attackable. Also, the hash of a "ones-only" or "zeros-only" string of really long length is not really representative, or more important than other strings. –  Paŭlo Ebermann Mar 6 at 11:13

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.