Хэш-функция без ключа

Хэш-функция

можно

Чтобы сэкономить время:, где H(m) – хэш-функция (сжимает сообщение), (m, S) – сообщение незначительно удлиняется.

Что надо?

Мошенник подобрать m₁≠m₂:.

Предъявить (m₁, S) и отказаться от (m₂, S).

=> Требование: сложно подобрать 2 различных сообщения с одинаковым значением хэш-функции.

Парольная защита:

Пользователь предъявляет свой идентификатор (Id) и пароль (P).

Требования:

- нельзя восстановить аргумент хэш-функции по значению (хэш-функция – односторонняя функция);

- нельзя подобрать другой аргумент с тем же значением хэш-функции.

Слабая и сильная хэш-функция:

Определение 1: Слабая хэш-функция называется односторонняя функция, где – набор векторов произвольной длины, V_n – набор бинарных векторов длины n над Z_n, n – некоторая константа.

* - любые (произвольные) строки.

Свойства:

1) легко вычислить H(x);

2) трудно найти,

Определение 2: Сильная хэш-функция – односторонняя функция, (n – константа) удовлетворяющая свойству 1) и 2’) трудно найти пару x’,

Пара называется коллизией хэш-функции.

Различия сильной и слабой хэш-функции:

1) Коллизий бесконечно много;

2’) => 2) (сильная также является слабой за счет 2-го условия, т.к. найти фиксированные коллизии нельзя).

Атака на свойство 2): есть x; противник перебирает и проверяет на совпадение значения хэш-функции:.

Перебор значений, выглядит как случайный выбор из множества V_n.

До совпадения с H(x) перебор в среднем равен;

=.

Стойкая слабая хэш-функция => =>

=>.

Атака на свойство 2’): перебор значений H(x) до повторения, запоминая все предыдущие.

Парадокс (эффект) близнецов: если случайно выбрать элемент из n, то до первого повторения с вероятностью 0,63 придется перебрать раз.

До первого повтора противник должен перебрать.

С вероятностью 0,63.

Для стойкой сильной хэш-функции

=>.

Следствие: У сильной хэш-функции требования на длину в 2 раза больше чем у слабой.

SHA-1

SHA-2 (расширение значений с 160 до 224,256,384,512)

SHA-3.

Типовая конструкция хэш-функции:

ISO/IEC 10118 1 часть – общая конструкция.

Мериль-Демгард

Обозначения:

- L_h – длина значения H;

- m – аргумент;

- L_m – длина m;

- L₁ и L₂ – целые числа ϵ Z, L_h ≤ L₂;

- – стартовый вектор;

- – шаговая функция хэширования;

- – финальное преобразование.

Алгоритм:

1. m дополняется до кратности L₁ бит;

2. разбить дополненную последовательность на блоки m=m₁|…|m_q: |m₁| = L₁;

3. определяем стартовое значение H₀=IV;

4. для i=1…q, H_i=φ(m_i, H_i-1);

5. H(m)=T(H_q)

Для конкретного х необходимо определить:

- L₁, L₂, L_h;

- метод дополнения L1;

- стартовый вектор IV;

- шаговая функция φ;

- финальные преобразования T;

- методы дополнения.

Как правило, L₁ = L₂ = L_h.

Методы дополнения описаны в ISO/IEC 10118-1, самое простое – дополнение нулями.

IV выбирается либо нулевой, либо заранее оговоренное значение.

T: часто T(H_q)=L_m бит H_q, T – односторонняя функция.

φ:

- 10118-2: построение блочного шифра для φ (ГОСТ Р 34.10-94).

- 10118-3: заказные хэш-функции, специально построенные φ

(SHA-1, SHA-2, RIPEMD-*).

- 10118-4: использование модулярной арифметики для φ;

, K_i зависит от.

Для модулярной арифметики:;

B_i строится по m; A – константа; N=pq; e=2.257; MASH-1,-2.