Лекция 6 бсит Представьте себе ситуацию : вам отправили по электронной почте документ с конфиденциальной информацией по финансированию



Pdf просмотр
Дата13.02.2017
Размер0.65 Mb.
Просмотров175
Скачиваний0
ТипЛекция

1
Лекция
6
БСит
Представьте себе ситуацию
: вам отправили по электронной почте документ с
конфиденциальной информацией по финансированию на будущий год
Вам необходима абсолютная уверенность в
том
, что полученный файл совершенно идентичен оригиналу и
содержащиеся в
нем цифры не были изменены
«
в пути
».
Подозрение
, что документ был подделан
, появляется
, если некоторые цифры не сходятся
, а
электронная передача велась через внешнюю почтовую систему
Для этого существуют алгоритмы идентификации цифровой информации
Такие алгоритмы работают только с
цифровой информацией
При необходимости идентификации текстового документи или изображения
, нужно с
помощью кодирования вначале получить цифровой аналог данной информации
Различают несколько способов идентификации
: контрольные суммы
, контроль
CRC, хэширование и
цифровая подпись
– таковы базовые средства аутентификации при цифровой передаче данных
Контрольные

суммы
– наиболее простой способ проверки целостности данных
, передаваемых в
цифровом виде
, при котором вычисляется контрольная сумма сообщения
(
определенное значение
, которое и
идентифицирует цифровую информацию
).
Контроль

CRC
– более надежный способ цифровой идентификации данных
Это вычисление контрольного значения циклического избыточного кода данных
(cyclic redundancy check – CRC) .
Наиболее совершенный способ идентификации цифровой информации
– алгоритмы цифровой подписи и
хеширование

§ 1.
КРИПТОГРАФИЧЕСКИЕ

ХЭШ
-
ФУНКЦИИ

Функция

хэширования
( )
H m
или
хэш
-
функция
(hash-function) – это детерминированная функция
, на вход которой подается строка битов произвольной длины
, а
выходом всегда является битовая строка фиксированной длины
n
Значение хэш
- функции
( )
H m
для входа
m
называют
хэшем

2
В
литературе можно широко распространены и
другие названия
, а
именно
Хэш
=
хэш
-
образ
=
хэш
-
код
=
свертка
=
=
дайджест

сообщения
=
криптографическая

контрольная

сумма
=
=
цифровой

от

печаток
=
=
код

аутентичности

сообщения
=
=
код

обнаружения

манипуляций
.
Исходная строка
m
, для которой вычислено хэш
- значение
, называется
прообразом
хэш
- функции
Свойства
, которые должны быть присущи криптографическим хэш
- функциям
:
1.
Стойкость

к

поиску

первого

прообраза
– отсутствие эффективного полиномиального алгоритма вычисления обратной функции
, т
е нельзя восстановить текст
m
по известной его свертке
( )
H m
за реальное время
(
необратимость
).
Это свойство эквивалентно тому
, что хэш
- функция является односторонней функцией
2.
Стойкость

к

поиску

второго

прообраза
(
коллизиям

первого

рода
) – вычислительно невозможно
, зная сообщение
m
и его свертку
( )
H m
, найти такое другое сообщение
m
m
′ ≠
, чтобы
( )
(
)
H m
H m

=
3.
Стойкость

к

коллизиям
(
коллизиям

второго

рода
) –.
Коллизией

для хэш
- функции называется такая пара значений
m
и
m

,
m
m


, для которой
( )
(
)
H m
H m

=
Так как количество возможных открытых текстов больше числа возможных значений свертки
, то для некоторой свертки найдется много прообразов

коллизии для хэш
- функций обязательно существуют
Например
, пусть длина хэш
- прообраза
6
битов
, длина свертки
4
бита
Тогда число различных сверток

4 2
16
=
, а
число хэш
- прообразов

6 2
64
=
, т
е в
4
раза

3 больше

хотя бы одна свертка из всех соответствует
4 прообразам
Стойкость

хэш
-
функции

к

коллизиям
означает
, что нет эффективного полиномиального алгоритма
, позволяющего находить коллизии
Замечание
: свойства не являются независимыми
:

Обратимая функция неустойчива к
восстановлению второго прообраза и
коллизиям

Функция
, нестойкая к
восстановлению второго прообраза
, нестойка к
коллизиям
; обратное неверно

Функция устойчивая к
коллизиям
, устойчива к
нахождению второго прообраза

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

эффект
Значение хеша не должно давать утечки информации даже об отдельных битах аргумента
§ 2.

ПРИМЕНЕНИЕ

ХЕШ
-
ФУНКЦИЙ

ДЛЯ

ПРОВЕРКИ

ИСТИННОСТИ

СООБЩЕНИЙ


Основные шаги процесса хэширования
:
Отправитель
А
подает сообщение на вход функции хэширования и
находит его свертку
(
хэш
).
Свертка сообщения добавляется к
сообщению
Отправитель
А
отправляет получателю сообщение
+
свертку
Получатель пропускает сообщение через функцию хэширования
Получатель
В
генерирует свое собственное значение свертки сообщения и
сравнивает две свертки сообщения
Если они совпадают
, сообщение не было изменено
Возможная

атака
: криптоаналитик
, перехватив сообщение
, изменяет его
, рассчитывает новый хэш
, присоединяет его к
измененному сообщению и
отправляет получателю
В
Когда тот получит такое сообщение
, он проверит хеш
, но так и
не узнает о
подделке
Для более высокого уровня защиты
, надо использовать код аутентификации сообщений
(
МАС
– Message Authentication Code).
Вопросы
:
1.
Можно ли использовать обычный метод сжатия без потерь
, например
ZIP, в
роли криптографической хэш
- функции
?
Ответ
: нет
, сжатие без потерь создает сжатое сообщение
, которое должно быть обратимо
2.
Можно ли использовать функцию контрольной суммы как криптографическую хэш
- функцию
?

4
Ответ
:
Нет
, функция контрольной суммы дает не стойкий прообраз
, так как можно найти несколько сообщений
, контрольная сумма которых одинакова
3.
Хэш
- функция
( )
(mod )
H m
m
n
=
,
1
(
)
H m
и
2
(
)
H m
– свертки сообщений
1
m
и
2
m
Можно ли выбрать в
роли значения свертки сообщения
3 1
2
m
m
m
=
+
значение
1 2
(
(
)
(
))(mod )
H m
H m
n
+
?
Ответ
:
Нет
, нарушается свойство перемешивания
4.
Будет ли стойкая к
коллизиям функция обязательно односторонней
?
Ответ
: нет
, например
, функция
(
)
H M
M
=
стойкая к
коллизиям и
определению второго прообраза
, но не односторонняя

§
3.
СХЕМА

МЕРКЕЛЯ

ДАМГАРДА


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

функцией

сжатия
Функция сжатия
– это функция двух переменных
)
,
(
2 1
x
x
f
y
=
, где
2 1
, x
x
– битовые строки длины
m
,
y
– битовая строка длины
n
(
n
– длина свертки
).
Наиболее распространенной криптографической функцией хэширования на основе одношаговой функции сжатия является итеративная схема
Меркеля

Дамгарда
Схема

Меркеля

Дамгарда


В
конец хэшируемого сообщения
M
приписывается длина сообщения и
дополнение
, так чтобы длина увеличенного сообщения была кратна числу
m
, где
m

длина строки
, которую может обработать функция сжатия
Пусть сообщение разбито на
t
m
- битовых блоков
(
строк
):
1 2
,
,...,
t
M M
M
Свертки
, получаемые в
ходе итераций
, обозначим
1 2
,
,...,
t
H H
H
, результирующая свертка всего сообщения
(
)
H M
. Последовательная процедура вычисления свертки
:
0
H
IV
=
;
)
,
(
1

=
i
i
i
H
M
f
H
,
1,...,
i
t
=
;
(
)
t
H M
H
=
, где
IV
– начальное значение свертки
(
фиксированный вектор
),
f
– функция сжатия
Получаемая по такой схеме хэш
- функция называется
итерированной
Доказано
, что если функция сжатия устойчива к
коллизии
, то хэш
- функция также устойчива к
коллизии

5



§ 4.
ДВА

ТИПА

КРИПТОГРАФИЧЕСКИХ

ХЭШ
-
ФУНКЦИЙ

Разработка хэш
- функций
, удовлетворяющих всем требованиям
, – сложная задача
Практически отвечают этим требованиям хэш
- функции из группы алгоритмов
MD и
SHA.
Алгоритм
Описание
Длина хэша
, бит
Примечание
MD2
Одностороння функция
128
Медленнее
, чем
MD4 и
MD5
MD4
Одностороння функция
128
MD5
Одностороння функция
128
Сложнее
, но медленнее
, чем
MD4.
Н
AVAL
Одностороння функция
Длина различна
Модификация
MD5, но более стойкая к
атакам
SHA
Одностороння
160
Используется в
Ключевые

хеш
-
функции

или
коды

аутентификации


сообщений
(Message
А
uthentication
Code - MAC)
Используются в
системах с
доверяющими друг другу пользователями
Бесключевые

хеш
-
функции


или
коды

обнаружения

ошибок
(Modification Code – MDC или
Message Integrity Code –MIC)
Используются в
системах как с
доверяющими друг другу
, так и
с недоверяющими пользователями
Типы криптографических хэш
- функций

6 функция
DSA
SHA-1, SHA-256,
SHA-384, SHA-
512
Обновленная версия
SHA
SHA-1 создает хэш длиной
160 бит
,
SHA-256 – длиной
256 бит и
т д
Алгоритмы группы
MD
разработаны
Роном
Ривестом
Название обозначает
«
дайджест сообщения
».
Алгоритм

безопасного

хэширования
(SHA Secure Hash Algorithm)
стандарт
, разработанный
NIST и
принятый как федеральный стандарт обработки информации в
США
. SHA
основан на схеме
Меркеля
-
Дамгарда
§ 5.
АЛГОРИТМ

БЕЗОПАСНОГО

ХЭШИРОВАНИЯ
SHA-1


Основные характеристики алгоритма
:
Длина хэш
- кода

160
бит
Длина обрабатываемых блоков

512
бит
Число шагов алгоритма
-
80
(4 раунда по
20 шагов
)
Максимальная длина хэшируемых данных

2 64

1.


7
1.
Логика

выполнения
SHA-1
Алгоритм получает на входе сообщение максимальной длины
64 2
1

бит и
создает в
качестве выхода дайджест сообщения длиной
160 бит
Алгоритм состоит из следующих шагов
:
Логика выполнения
SHA-1

2.
Добавление

недостающих

битов

и

указание

длины
(
шаг
1)

Исходное
m
- битовое сообщение
1 2
( ,
,...,
)
m
a a
a
расширяется до длины
, кратной
512, по принципу
:
1 2
1 2 64 1
( ,
,...,
,1,0,0,...,0, , ,...,
)
m
s
a a
a
l l
l

14 2 43
, где
1 2 64
( , ,...,
)
l l
l
– двоичная запись числа
m
,
s
– наименьшее число
, при котором
(
64) 512
m
s
+ +
M
Пример
1.
На вход алгоритма хеширования
SHA-1 подается сообщение длиной
2590 битов
Сколько битов будет содержать дополнение сообщения
?
Р
е ш
е н
и е
64 0(mod 512)
m
s
+ +


64(mod 512)
s
m
= − −
2590 64(mod 512)
2654(mod 512)
418
s
= −

= −

Дополнение состоит из одной
1 и
417 нулей
Пример
2.
Нужно ли добавлять дополнение
, если длина первоначального сообщения уже кратна
512 битам
?
Ответ
:
Да
, так как надо еще приписать длину
m
исходного сообщения
Дополнение необходимо
, чтобы сделать и
новый блок кратным
512 битам
Пример
3.
Какое минимальное и
максимальное число битов дополнения можно добавить к
сообщению
?

8
Ответ
:
Минимальная длина дополнения
– 0, это в
случае когда
64(mod 512)
0
m
− −

, тогда
64 448(mod 512)
m
= − ≡
Максимальная длина заполнения
– 511 битов
, когда
64(mod 512)
511(mod 512)
m
− −

и
449(mod 512)
m
=
Итак
, результатом первого шага является сообщение
, длина которого кратна
512 битам
Далее расширенное сообщение делится на
512- битные блоки
0 1
1
, ,...,
N
Y Y
Y

, поэтому общая длина расширенного сообщения есть
512
N
бит
Этот результат кратен шестнадцати
32- битным словам
3.
Инициализация

буфера
(
шаг
2)
В
алгоритме используется
160- битный буфер для хранения промежуточных и
окончательных результатов хэш
- функции
Буфер может быть представлен как пять
32- битных регистров
, , , ,
A B C D E
Эти регистры инициализируются следующими шестнадцатеричными числами
:
67 45 23 01
A
=
;
89
B
EF CD AB
=
;
98
C
BA DC FE
=
;
10 32 54 76
D
=
;
3 2
1 0
E
C D E F
=
Вектор инициализации
, подаваемый на вход
1- го раунда

результат конкатенации
0
||
||
||
||
SHA
A B C D E
=
4.
Обработка

сообщения

в
512-
битных

блоках
(
шаг
3)

Основой алгоритма является модуль
, состоящий из
80 циклических обработок
, обозначенный как
SHA
H
Все
80 циклических обработок имеют одинаковую структуру
Каждый цикл получает на входе текущий
512- битный обрабатываемый блок
i
Y
и
160- битное значение буфера
ABCDE
, и
изменяет содержимое этого буфера
В
каждом цикле используется дополнительная константа
t
K
, которая принимает только четыре различных значения
:

9
Обработка очередного
512- битного блока
5 827999,
0 19;
6 9
1,
20 39 ,
8 1
,
40 59;
62 1 6,
60 79.
t
A
t
ED EBA
t
K
F BBCDC
t
CA
C D
t
≤ ≤


≤ ≤

=

≤ ≤


≤ ≤

Для получения
1
i
SHA
+
выход
80- го цикла складывается со значением
i
SHA
Сложение по модулю
32 2
выполняется независимо для каждого из пяти слов в
буфере с
каждым из соответствующих слов в
i
SHA
5.
Выход
(
шаг
4)

После обработки всех
512- битных блоков выходом является
160- битный дайджест сообщения



10
6.
Описание

раунда

обработки

одного

512-
битного

блока

даннях


Рассмотрим более детально логику в
каждом из
80 раундов обработки одного
512- битного блока
Каждый раунд можно представить в
виде
:
5
( , , , , ,
,
)
( )
( , , )
t
t
t
t
t
TEMP A B C D E K W
S
A
f B C D
E
K
W
=
+
+
+
+
;
E
D
=
;
D
C
=
;
30
( )
C
S
B
=
;
B
A
=
;
A
TEMP
=
, где
t
– номер раунда
;
5
( )
S
A
– циклический левый сдвиг
32- битового аргумента
A
на
5 бит
;
30
( )
S
B
– циклический левый сдвиг
32- битового аргумента
B
на
30 бит
; символ
+
означает сложение по модулю
32 2
;
t
f
– элементарная логическая функция
(
описана ниже
);
t
K
– пошаговые константы
, равные
t
W
–32- битные слова
, получаемые из очередного
512- битного блока сообщения
(
способ генерации слов приведен ниже
).
Логика работы одного раунда

11
Замечание
: значения пошаговых констант
t
K
в алгоритме были выбраны по принципу
(
[ ]
x
– целая часть числа
)
30 5 827999
[2 2]
A
=

,
30 6
9 1 [2 3]
ED EBA
=

,
30 8 1
[2 5]
F BBCDC
=

,
30 62 1 6
[2 10]
CA
C D
=

.
6.
Логические

функции

t
f
,
используемые

в

раунде

Каждая элементарная функция получает на входе три
32- битовых слова и
создает на выходе одно
32- битовое слово
Элементарная функция выполняет набор побитовых логических операций
(
побитовое умножение и
сложение
), т
е
n
- ый бит выхода является функцией от
n
- ых битов трех входов
Функции следующие
(
t
номер раунда
):
(
)
(
),
0 19;
( , , )
,
20 39 , 60 79;
(
)
(
)
(
),
40 59.
t
B
C
B
D
t
f B C D
B
C
D
t
t
B
C
B D
C
D
t




≤ ≤

=
⊕ ⊕
≤ ≤
≤ ≤







≤ ≤

(
B
получено из
B
инвертированием бит
).
Пример
.
Крайние левые шестнадцатеричные цифры переменных
, ,
B C D
равны
07
h
,
0
h
A
и
0
h
E
соответственно
Какие цифры будут крайними левыми в
значении функции
43
( , , )
f
B C D
, используемой в
алгоритме
SHA?
Р
е ш
е н
и е
2 07 0111
h
=
,
2 0
1010
h
A
=
,
2 0
1110
h
E
=
(
)
(
)
(
)
(0 1)
(0 1)
(1 1)
0 0 1 1
B
C
B
D
C
D





= ∧ ∨ ∧ ∨ ∧ = ∨ ∨ =
(1 0)
(1 1)
(0 1)
0 1 0 1
∧ ∨ ∧ ∨ ∧ = ∨ ∨ =
;
(1 1)
(1 1)
(1 1) 1 1 1 1
∧ ∨ ∧ ∨ ∧ = ∨ ∨ =
;
(1 0)
(1 0)
(0 0)
0 0
0 0
∧ ∨ ∧ ∨ ∧ = ∨ ∨ =
Результат
2 1110 0
h
E
=
7.
Формирование

входных

значений

раунда

из

очередного

блока

Перед началом первого раунда блок расширяют до
80 слов по
32 бита
Для этого вначале сам входной блок данных делят на
16 слов

12 0
1 15
, ,...,
Y Y
Y
по
32 бита и
далее к
ним присоединяют еще
64 слова по
32 бита
В
результате образуются слова
:
0 1
79
,
,...,
W W
W
Принцип образования новых слов
:
t
t
W
Y
=
, при
0,1,...,15
t
=
;
1 3
8 14 16
(
)
t
t
t
t
t
W
S W
W
W
W




=



при
16,...,79
t
=
, где
1
S
– операция циклического сдвига аргумента на один разряд влево
Алгоритм
SHA-1 можно суммировать следующим образом
:
0 1
1
;
32(
,
);
,
i
i
i
N
SHA
IV
SHA
SHA ABCDE
SHA
SHA
+

=
=
=

где
IV
- начальное значение буфера
ABCDE
;
i
ABCDE
- результат обработки
і
- того блока сообщения
;
N
- число блоков в
сообщении
, включая поля добавления и
длины
;
32

- сумма по модулю
32 2
, выполняемая отдельно для каждого слова буфера
;
SHA
- значение дайджеста сообщения

13
(
Способ

быстрого

подбора

коллизий

для
HAVAL, RIPEMD
и
MD5
нашли

китайские

исследователи
,
выложив

в

Сети

файлы
,
которых

до

этого

официально

не

мог

видеть

ни

один

человек

на

Земле
(
ну

разве

что

тайно
) –
два

разных

файла
,
создающих

одинаковое

хэш
-
значение

алгоритмом
MD5!
Удивленные

пользователи

скачивали

файлы

с

примерами

и

убеждались
,
что

это

все

правда
.
На

подбор

коллизии

по
"
китайскому

методу
" (
его

подробности
,
кстати
,
китайцы

не

хотят

публиковать

целиком
)
уходит

от
15
секунд

до

пары

часов

на

персональном

компьютере
! ).
Упражнения

1.
Каково дополнение для
SHA-512, если длина сообщения
: o
5120 битов o
5121 бит o
6143 бита
2.
Найдите результат функции
47
( , , )
f
B C D
, если
B = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
C = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
D = 3234 5678 ABCD 2345 34564 5678 ABCD 2468 3.
Найдите результат функции
13
( , , )
f
B C D
, если
B = 1234 5678 ABCD 2345 34564 5678 ABCD 2468
C = 2234 5678 ABCD 2345 34564 5678 ABCD 2468
D = 3234 5678 ABCD 2345 34564 5678 ABCD 2468

§ 5.
ХЕШ
-
ФУНКЦИИ

НА

ОСНОВЕ

БЛОКОВЫХ

ШИФРОВ

(
КЛЮЧЕВЫЕ

ХЕШ
-
ФУНКЦИИ
)

Ключевые хэш
- функции строят с
помощью блокового
n

битового шифра
k
E
(
далее запись
( )
k
E
X
означает
, что шифр работает на ключе
k
).
Сначала сообщение
M
дополняют до нужной длины и
разбивают на блоки
1 2
,
,...,
N
x x
x
, длина которых совпадает с
размером блока или ключа блокового шифра
(
это зависит от вида хэш
- функции
).
При построении ключевой хеш
- функции используют все туже схему
Меркеля

Дамгарда
:
0
H
IV
=
;
1
(
,
)
i
i
i
H
f x
H

=
,
1,...,
i
t
=
;
(
)
t
H M
H
=
, где
IV
– начальное значение свертки
(
фиксированный вектор
),
f
– функция сжатия
Обобщенная схема формирования хеш
- функции с
помощью блокового шифра изображена на рисунке
:

14
В
роли
,
A B
и
C
могут выступать блоки входного текста
, результаты
i
- ой итерации свертки
, а
безопасность хеш
- функции базируется на безопасности используемого шифра
Определение функции сжатия
, участвующей в
итерациях
, зависит от используемой схемы
Наиболее безопасные хеш
- функции такие
:
1)
1 1
(
)
( ,
)
( )
i
i
i
g H
i
i
f x H
E
x
x


=

– функция
Матиаса

Мейєра

Осиса
(
роль ключа в
шифре играют элементы свертки
, полученной на предыдущей итерации
);
2)

1 1
1
( ,
)
(
)
i
i
i
x
i
i
f x H
E
H
H



=


– функция
Давиэса
-
Мейєра
(
роль ключа играют элементы сообщения
);
3)

1 1
(
)
1
( ,
)
( )
i
i
i
g H
i
i
i
f x H
E
x
x
H



=
⊕ ⊕
– функция
Миягучи
-
Пренила
Здесь
g
некоторая функция
, которая переводит вектор длины
m
в вектор длины
n
Основной недостаток хеш
- функций
, спроектированных на основе блоковых шифров
, – низкая скорость работы
(
по сравнению с
бесключевыми функциями
).

§ 6.
ОСНОВНЫЕ

МЕТОДЫ

КРИПТОАНАЛИЗА

ОДНОСТОРОННИХ

ХЭШ
-
ФУНКЦИЙ


1.
Лобовая

атака
.
Имея

свертку

1
(
)
H m

сообщения

1
m
,
криптоаналитик

должен

методом

подбора

найти

сообщение

2
m

(
2 1
m
m

),
для

которого

1 2
(
)
(
)
H m
H m
=
(
тогда

он

может

заявлять
,
что

предъявленная

свертка

соответствует

сообщению

2
m
,
а

не


15 1
m
).
Если

хэш
-
функция

на

выходе

дает

n
-
битовую

строку
,
то

сложность

этого

метода

(2 )
n
O
.
2.
Атака

на

основе
«
парадокса

дней

рождений
».
Для

хэш
-
функций

универсальным

методом

поиска

коллизий

является

метод
,
основанный

на

известной

статистической

задаче
– «
парадоксе

дня

рождения
».
Парадокс дней рождения
— это кажущееся парадоксальным утверждение
, что вероятность совпадения дней рождения
(
даты
) хотя бы у
двух членов группы из
23 и
более человек
, превышает
0,5.
Для
60 и
более человек вероятность такого совпадения превышает
0,99, хотя
1,0 она достигает
, только когда в
группе не менее
367 человек
Такое утверждение может показаться неочевидным
, так как вероятность совпадения дней рождения двух человек в
любой день года
(1/365 =
0,0027 ), помноженная на число человек в
группе из
23, даёт лишь
23/365 = 0,063.
Это рассуждение неверно
, так как число возможных пар
(253) значительно превышает число человек в
группе
Логического противоречия в
этом нет
, а
парадокс заключается лишь в
различиях между интуитивным восприятием и
математическим расчётом
Рассчитаем сначала вероятность
( )
P n
того
, что в
группе из
n
человек дни рождения всех людей будут различными
Если
n > 365, то
( )
0
P n
=
При
n

365 выберем наугад одного человека из группы и
запомним его день рождения
Затем выберем наугад второго человека
, при этом вероятность того
, что у
него день рождения не совпадёт с
днем рождения первого человека
, равна
1 — 1/365.
Затем возьмём третьего человека
, при этом вероятность того
, что его день рождения не совпадёт с
днями рождения первых двух
, равна
1 — 2/365.
Рассуждая по аналогии
, мы дойдём до последнего человека
, для которого вероятность несовпадения его дня рождения со всеми предыдущими будет равна
1 — (n — 1)/365.
Перемножая все эти вероятности
, получаем вероятность того
, что все дни рождения в
группе будут различными
:
1 2
1
( ) 1 1 1
... 1 365 365 365
n
P n


 



= ⋅ −
⋅ −
⋅ ⋅ −
=

 




 



365 364 ... (365 1)
365!
365 365 (365
)!
n
n
n
n

⋅ ⋅
− +
=
=

Тогда вероятность того
, что хотя бы у
двух человек из
n
дни рождения совпадут
, равна
( ) 1
( )
P n
P n
= −
Интересно
, что при
23
n
>

эта вероятность

( )
0,5
P n
>

16
Используя разложение экспоненты в
ряд
Телора
2 1
2!
x
x
e
x
= + +
+
, полученное выражение можно аппроксимировать
1 2
1 1 2 ... (
1)
( (
1)) 2 365 365 365 365 365
( ) 1
n
n
n n
P n
e
e
e
e
e

+ + + −







≈ ⋅

⋅ ⋅
=
=
.
( (
1)) 2 365
( ) 1
( ) 1
n n
P n
P n
e



= −
≈ −

и при более грубой оценке
2 2 365
( ) 1
n
P n
e


≈ −
Сведем задачу криптоанализа хэш
- функций к
задаче поиска коллизии
:
сколько сообщений надо просмотреть
, чтобы найти сообщения с
двумя одинаковыми хэшами
?
Вероятность встретить одинаковые хэши для сообщений из двух разных наборов
, содержащих
1
n
и
2
n
текстов
, равна
1 2 2
1
l
n n
P
e

≈ −
Если
/ 2 1
2 2
l
n
n
=
=
, то вероятность успеха атаки
1 1
0,63
P
e

≈ −

, а
сложность проведения атаки
1 2
2
l
+
операций
Чтобы найти коллизию
, надо сгенерировать два псевдослучайных множества сообщений
(
в каждом множестве
/ 2 2
n
сообщений
) и
найти для них хэши
Тогда согласно парадоксу дня рождения
, вероятность того
, что среди них найдется пара сообщений с
одинаковыми хэшами
, больше
0,5.
Атака требует большого объема памяти для хранения текстов и
эффективных методов сортировки

Примеры
.
1.
Противник перехватил хєш
1
(
)
H
H M
=
Длина хэша
n
битов
Он хочет найти любое сообщение
2
M
, для котрого
1 2
(
)
(
)
H M
H M
=
, для чего генерирует
k
сообщений и
вычисляет их хэши
Какова вероятность успеха
?
Ответ
: вероятность успеха
/
1
k n
P
e

= −
2.
Противник перехватил определенное число хєшей разных сообщений
Длина хэша
n
битов
Сколько новых сообщений и
их хэшей надо сгенерировать
, чтобы найти коллизию для
50 % перехваченных хешей
?
Ответ
:
0,63 2
n
k


3.
Противник перехватил хєш
1
(
)
H
H M
=
и сообщение
1
M
Он хочет найти другое сообщение
2
M
, для котрого

17 1
2
(
)
(
)
H M
H M
=
, для чего генерирует
1
k

сообщений и
вычисляет их хэши
Какова вероятность успеха
?
Ответ
:
Вероятность успеха
1 (
1) /
1
k
n
P
e
− −
= −
4.
Противник хочет создать два любых разных сообщения
1
M
и
2
M
, для которых
1 2
(
)
(
)
H M
H M
=
, для чего генерирует
k
сообщений и
вычисляет их хэши
Какова вероятность успеха
?
Ответ
:
Вероятность успеха
1 (
1) / 2 1
k
n
P
e
− −
= −
5.
Хэш
- функция дает хэш длиной
64 бита
Сколько хэшей надо сгенерировать
, чтобы найти коллизию двух любых сообщений
?
Ответ
:
/ 2 32 1,18 2 1,18 2
n
k




Если проверять
220 сообщений за секунду
(
почти
10 6
опер
/
сек
.), то потребуется
12 1,18 2


секунд
<
2 часов
Хэш

сообщения в
64 бита небезопасен относительно атаки коллизии
Сценарий

проведения

атаки

хеш
-
функции
,
на

основе

«
парадокса

дня

рождения
».
Пусть мошенник

А
хочет подвергнуть атаке банкира
В
и подписать у
него контракт
, невыгодный для
В
1).
А
готовит две версии контракта
– «
хорошую
»
1
M
и
«
плохую
»
2
M
, делает несколько малозначительных изменений к
каждому документу
, манипулируя с
точками
, запятыми
, пробелами
, предлогами и
др
2).
А
считает для всех версий контракта хэши
, сравнивает наборы хэшей
, подыскивая одинаковые пары
Если длина хэша
64 бита
, то обычно хватает
32 2
пар
А

выбирает пару с
одинаковым хэшем
3).
А

выбирает пару с
одинаковым хэшем и
дает на подпись банкиру
В

плохую версию
2
M
Тогда
А

в суде может доказывать
, что
В
подписал невыгодный контракт сознательно

При работе с
ключевыми хэш
- функциями небезопасно дописывать ключ в
начало или конец исходного сообщения
Пусть ключ
k
добавлен в
начале сообщения
, а
сжимающая функция построена по схеме
Меркеля

Дамгарда
Тогда по известным сообщению
M
и его свертке
( ||
)
H
H k M
=
можно найти значения свертки для всех сообщений вида
||
M
M

, где после
M
дописано любое сообщение
M

Действительно
, в
силу итерационного характера хеш
- функции для нахождения
( ||
||
)
H
H k M
M


=
не нужно знать ключ
Достаточно использовать у
вычисленное
«
промежуточное
» значение
H

18
Пусть ключ
k
добавлен в
конец сообщения
(
|| )
H
H M
k
=
Знание коллизии для хэш
- функции
, т
е пары
1 2
,
M M
,
1 2
M
M

, но
1 2
(
)
(
)
H M
H M
=
, позволяет вычислить хэши
1 2
(
, )
(
, )
H M k
H M
k
=
для любого ключа
k

трудоемкость изменения сообщения
1
M
уже оценивается не величиной
(2 )
n
O
Атакуя хэш
- функцию на основе
«
парадокса дней рождения
» можно снизить трудоемкость до
/ 2
(2
)
n
O
Чтобы уйти от этих опасностей
, рекомендуют ключ приписывать несколько раз
:
( ||
||
|| )
H
H k
y M
k
=
или
1 2
( ||
||
( ||
||
))
H
H k
y
H k
y
M
=
, где
1 2
,
,
y y y
– дополнение ключа до размера
, кратного длине блока
Так построенные бесключевые функции устойчивы к
атакам коллизии
, но их недостаток
– большая длина свертки


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал