рефлексивный хэш?

Question

Существует ли класс алгоритмов хеширования, теоретический или практический, такой, чтобы алгоритм в классе можно было считать «рефлексивным» согласно определению, данному ниже:

• hash1 = algo1 ("входной текст 1")
• hash1 = algo1 ("входной текст 1" + hash1)

Оператор + может быть конкатенацией или любой другой указанной операцией для объединения вывода (hash1) обратно во ввод («входной текст 1»), так что алгоритм (algo1) будет давать точно такой же результат. то есть столкновение на входе и на входе + выходе. Оператор + должен объединять все оба входа, и алгоритм не может отбрасывать часть ввода.

Алгоритм должен выдавать 128 битов энтропии на выходе. Может быть, но не обязательно, криптографически трудно преобразовать выход обратно в один или оба возможных входа.

Я не математик, но хороший ответ может включать доказательство того, почему такой класс алгоритмов не может существовать. Однако это не абстрактный вопрос. Я искренне заинтересован в использовании такого алгоритма в моей системе, если таковой существует.

Answer 1

Да, вы можете получить этот эффект с помощью CRC .

Что вам нужно сделать, это:

1. Реализуйте алгоритм, который найдет последовательностьиз N входных битов, ведущих из одного данного состояния (из N-разрядного аккумулятора CRC) в другое.
2. Рассчитайте CRC вашего входа обычным способом.Обратите внимание на конечное состояние (назовите его A)
3. Используя функцию, реализованную в (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 2

Опираясь на ответ эфемиата , я думаю, вы можете сделать что-то вроде этого:

Выберите свой любимый блочный шифр с симметричным ключом (например, AES). Для конкретности скажем, что он работает на 128-битных блоках. Для данного ключа K обозначим функцию шифрования и функцию дешифрования через Enc (K, блок) и Dec (K, блок) соответственно, так что block = Dec (K, Enc (K, block)) = Enc (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-битных блоков перед присоединением хеша. Другими словами, вместо hash (input) = hash (input + hash (input)), как было указано изначально, мы имеем hash (input) = hash (input '+ hash (input)), где input' - это просто дополненный ввод. Надеюсь, это не слишком обременительно.

Answer 3

Конечно, вот тривиальный:

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

Конкатенируйте результат, и "хэш" не изменится.Довольно просто придумать что-то похожее, когда вы можете изменить хеш.

Answer 4

Я почти уверен, что такая "рефлексивная хеш-функция" (если бы она существовала в более чем тривиальном смысле) не была бы полезной хеш-функцией в обычном смысле.

Для примера «тривиальной» рефлексивной хэш-функции:

    int hash(Object obj) { return 0; }

Answer 5

Ну, я могу вам сказать, что вы не получите доказательства небытия.Вот пример:

operator + (a, b): вычислить 64-битный хеш a, 64-битный хэш b и объединить цепочки битов, возвращая 128-битный хеш.

algo1: для некоторого 128-битного значения проигнорируйте последние 64 бита и вычислите некоторый хэш первых 64.

Неофициально, любой algo1, который возвращает первый оператор + в качестве первого шага, сделает.Может быть, не такой интересный класс, как вы искали, но он отвечает всем требованиям.И это тоже не без реальных примеров.Многие алгоритмы хеширования паролей обрезают их ввод.