Простое шифрование - Сумма хэшей в C

Question

Я пытаюсь показать простое доказательство концепции относительно уязвимости в куске кода в игре написанной на C.

Давайте предположим, что мы хотим для одобрения символьный логин. Вход пользователя обрабатывается пользователем, выбирая n пунктов (предположим, теперь n=5) из графического меню. Элементы все средневековые тематические:

например:

_______________________________ 
|   |   |  | 
| Bow  | Sword  | Staff | 
|-----------|-----------|-------| 
| Shield | Potion | Gold | 
|___________|___________|_______| 

пользователь должен нажать на каждый элемент, а затем выбрать номер для каждого пункта.

Алгоритм проверки затем выполняет следующие действия:

1. определяет, какие были выбраны пункты
2. капли каждой строки в нижний регистр (то есть: Bow становится bow, и т.д.)
3. Расчет простой строки хэша для каждого (т. е.: лук => b = 2, o = 15, w = 23, sum = (2 + 15 + 23 = 40)
4. Умножает хэш на значение, выбранное пользователем для соответствующего элемента; значение называется key
5. Суммы вместе keys для каждого из выбранных предметов; это окончательный хэширование валидации.
6. ВАЖНО: валидатор примет этот хэш вместе с ненулевыми кратными его значениям (то есть: если конечный хеш равен 1111, тогда также действуют 2222, 3333, 8888 и т. д.).

Так, к примеру, скажем, я выбираю:

Bow (1) 
Sword (2) 
Staff (10) 
Shield (1) 
Potion (6) 

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

например:

Final_Validation_Hash = 1*HASH(Bow) + 2*HASH(Sword) + 10*HASH(Staff) + 1*HASH(Shield) + 6*HASH(Potion)

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

в моем случае, на 5 пунктов, я бы по существу пытается вычислить:

(B)(y) = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)

Где:

B is arbitrary 
A_j are the selected coefficients/values for each string/category 
x_j are the hash values for each string/category 
y is the final validation hash (eg: 1111 above) 
B,y,A_j,x_j are all discrete-valued, positive, and non-zero (ie: natural numbers) 

Может кто-либо мне помочь в решении этой проблемы или мне точку к аналогичному примеру (т.е.: код, выработанные уравнения и т. д.)? Мне просто нужно решить последний шаг (т. Е.: (B) (Y) = ...).

---

В конце концов, я написал рекурсивный алгоритм, который идет n уровней в глубине, а затем обрабатывает приращение, тестирования и т.д., для всех остальных возможных комбинаций. Не очень эффективный, но он работает. Я мог бы предоставить его по запросу (слишком большой для публикации здесь).

Answer 1

Мне кажется, что большинство пользователей будут выбирать довольно маленькие цифры для каждого элемента (в конце концов «им легче запомнить», чем «438483»).

Учитывая это ограничение, грубая сила, вероятно, на самом деле разумна.

Простое создание всех возможных входных значений для 5 символов плюс число, скажем, в диапазоне 1.99, вычисление полученного хеша и подсчет (например, с использованием словаря) числа различных комбинаций, которые дают заданный хеш должен дать эмпирическое понимание распределения хешей для наиболее вероятных входных значений.

Оттуда я бы посмотрел, сколько фактических значений хэша было создано (из 2 возможных возможных хеш-значений 2^32, если хеш является Int32), а также искать значения хэша, которые генерируются с определенной частотой (имеют высокий счет в Словаре).

Answer 2

Ну это может и не быть уникальным в зависимости от пунктов меню x_j, коэффициенты A_j и хэш проверки y и количества выбранных элементов n.

Например, что произойдет, если ваш хеш проверки будет 1? Тогда все будет проверяться.

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

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

Answer 3

Это довольно тривиально, поскольку алгоритм принимает ненулевые кратные. Если умножить все входы на два вы будете иметь конфликт:

Bow (1) 
Sword (2) 
Staff (10) 
Shield (1) 
Potion (6) 

y = (A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5) 

Затем умножьте их на 2:

Bow (2) 
Sword (4) 
Staff (20) 
Shield (2) 
Potion (12) 

2(A_1)(x_1) + 2(A_2)(x_2) + 2(A_3)(x_3) + 2(A_4)(x_4) + 2(A_5)(x_5) 
= 2((A_1)(x_1) + (A_2)(x_2) + (A_3)(x_3) + (A_4)(x_4) + (A_5)(x_5)) 
= 2y 

Answer 4

Хотя это не является формальным доказательством, но у меня есть идея.

Пусть хэши различных строк будут h_1, h_2 ..., h_n линейная сумма будет

y = h_1 + h_2 + ... + h_n

После того как мы y мы всегда можем найти h_1', h_2' ... , h_n' такой, что по крайней мере для пары i и jh_i != h_j' в серии.

Для того, чтобы получить окончательную сумму, у нас есть дубликаты h.

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

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

Поэтому мы можем генерировать один хэш из многих строк.

Answer 5

Установить все, кроме последнего коэффициента к 1, так что вы получите что-то формы Ап * х = г (мод у), а затем использовать расширенный алгоритм Евклида, чтобы найти решение, см Wikipedia