reflexive hash?

Is there a class of hash algorithms, whether theoretical or practical, such that an algo开发者_开发知识库 in the class might be considered 'reflexive' according a definition given below:

• hash1 = algo1 ( "input text 1" )
• hash1 = algo1 ( "input text 1" + hash1 )

The + operator might be concatenation or any other specified operation to combine the output (hash1) back into the input ("input text 1") so that the algorithm (algo1) will produce exactly the same result. i.e. collision on input and input+output. The + operator must combine the entirety of both inputs and the algo may not discard part of the input.

The algorithm must produce 128 bits of entropy in the output. It may, but need not, be cryptographically hard to reverse the output back to one or both possible inputs.

I am not a mathematician, but a good answer might include a proof of why such a class of algorithms cannot exist. This is not an abstract question, however. I am genuinely interested in using such an algorithm in my system, if one does exist.

---

Sure, here's a trivial one:

def algo1(input):
    sum = 0
    for i in input:
        sum += ord(i)
    return chr(sum % 256) + chr(-sum % 256)

Concatenate the result and the "hash" doesn't change. It's pretty easy to come up with something similar when you can reverse the hash.

---

Yes, you can get this effect with a CRC.

What you need to do is:

1. Implement an algorithm that will find a sequence of N input bits leading from one given state (of the N-bit CRC accumulator) to another.
2. Compute the CRC of your input in the normal way. Note the final state (call it A)
3. Using the function implemented in (1), find a sequence of bits that lead from A to A. This sequence is your hash code. You can now append it to the input.

[Initial state] >- input string -> [A] >- hash -> [A] ...

Here is one way to find the hash. (Note: there is an error in the numbers in the CRC32 example, but the algorithm works.)

And here's an implementation in Java. Note: I've used a 32-bit CRC (smaller than the 64 you specify) because that's implemented in the standard library, but with third-party library code you can easily extend it to larger hashes.

public static byte[] hash(byte[] input) {
    CRC32 crc = new CRC32();
    crc.update(input);
    int reg = ~ (int) crc.getValue();
    return delta(reg, reg);
}

public static void main(String[] args) {
    byte[] prefix = "Hello, World!".getBytes(Charsets.UTF_8);

    System.err.printf("%s => %s%n", Arrays.toString(prefix), Arrays.toString(hash(prefix)));

    byte[] suffix = hash(prefix); 
    byte[] combined = ArrayUtils.addAll(prefix, suffix);

    System.err.printf("%s => %s%n", Arrays.toString(combined), Arrays.toString(hash(combined)));
}

private static byte[] delta(int from, int to) {
    ByteBuffer buf = ByteBuffer.allocate(8);
    buf.order(ByteOrder.LITTLE_ENDIAN);
    buf.putInt(from);
    buf.putInt(to);
    for (int i = 8; i-- > 4;) {
        int e = CRCINVINDEX[buf.get(i) & 0xff];
        buf.putInt(i - 3, buf.getInt(i - 3) ^ CRC32TAB[e]);
        buf.put(i - 4, (byte) (e ^ buf.get(i - 4)));
    }
    return Arrays.copyOfRange(buf.array(), 0, 4);
}
private static final int[] CRC32TAB = new int[0x100];
private static final int[] CRCINVINDEX = new int[0x100];
static {
    CRC32 crc = new CRC32();
    for (int b = 0; b < 0x100; ++ b) {
        crc.update(~b);
        CRC32TAB[b] = 0xFF000000 ^ (int) crc.getValue();
        CRCINVINDEX[CRC32TAB[b] >>> 24] = b;
        crc.reset();
    }
}

---

Building on ephemiat's answer, I think you can do something like this:

Pick your favorite symmetric key block cipher (e.g.: AES) . For concreteness, let's say that it operates on 128-bit blocks. For a given key K, denote the encryption function and decryption function by Enc(K, block) and Dec(K, block), respectively, so that block = Dec(K, Enc(K, block)) = Enc(K, Dec(K, block)).

Divide your input into an array of 128-bit blocks (padding as necessary). You can either choose a fixed key K or make it part of the input to the hash. In the following, we'll assume that it's fixed.

def hash(input):
   state = arbitrary 128-bit initialization vector
   for i = 1 to len(input) do
      state = state ^ Enc(K, input[i])
   return concatenate(state, Dec(K, state))

This function returns a 256-bit hash. It should be not too hard to verify that it satisfies the "reflexivity" condition with one caveat -- the inputs must be padded to a whole number of 128-bit blocks before the hash is adjoined. In other words, instead of hash(input) = hash(input + hash(input)) as originally specified, we have hash(input) = hash(input' + hash(input)) where input' is just the padded input. I hope this isn't too onerous.

---

Well, I can tell you that you won't get a proof of nonexistence. Here's an example:

operator+(a,b): compute a 64-bit hash of a, a 64-bit hash of b, and concatenate the bitstrings, returning an 128-bit hash.

algo1: for some 128-bit value, ignore the last 64 bits and compute some hash of the first 64.

Informally, any algo1 that yields the first operator to + as its first step will do. Maybe not as interesting a class as you were looking for, but it fits the bill. And it's not without real-world instances either. Lots of password hashing algorithms truncate their input.

---

I'm pretty sure that such a "reflexive hash" function (if it did exist in more than the trivial sense) would not be a useful hash function in the normal sense.

For an example of a "trivial" reflexive hash function:

    int hash(Object obj) { return 0; }