Reflective Hash?

Question

Is there a class of hash algorithms, be it theoretical or practical, so the class algorithm can be considered “reflexive” as defined below:

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

The + operator can be concatenation or any other given operation to combine the output (hash1) back into the input ("input text 1") so that the algorithm (algo1) produces exactly the same result. those. collisions at the input and input + output. The + operator must combine all both inputs, and the algorithm cannot cancel part of the input.

The algorithm should output 128 bits of entropy. It may be, but not necessarily, cryptographically difficult to cancel the output back to one or both of the possible inputs.

I'm not a mathematician, but a good answer may include proof of why such a class of algorithms cannot exist. However, this is not an abstract question. I am sincerely interested in using such an algorithm in my system, if one exists.

Answer 1

Of course, here is trivial:

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

Combine the result, but the "hash" will not change. It's very easy to come up with something like this if you can change the hash.

Answer 2

Based on the ephemiat answer , I think you can do something like this:

(: AES). , 128- . K Enc (K, block) Dec (K, block) , block = Dec (K, Enc (K, block)) = Enc (K, Dec (K, )).

128- ( ). K . , .

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))

256- . , "" - 128- . , (input) = hash (input + hash (input)), , hash (input) = hash (input '+ hash (input)), input' . , .

Answer 3

, CRC.

:

• , N , ( N- CRC) .
• CRC . ( A)
• , (1), , A A. - -. .

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

. (: CRC32 , .)

Java. . 32- CRC (, 64), , .

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();
    }
}

Answer 4

, , . :

operator + (a, b): 64- a, 64- b , 128- .

algo1: 128- 64 64.

Informally, any algo1 that gives the first + operator as the first step will do. It may not be such an interesting class as you were looking for, but it matches the bill. And this is not without real cases. Many password hashing algorithms truncate their input.

Answer 5

I am sure that such a “reflexive hash function” (if it existed in a more than trivial sense) would not be a useful hash function in the normal sense.

An example of a “trivial” reflective hash function:

    int hash(Object obj) { return 0; }