Решение задачи о словаре. Задача о словаре состоит в следующем: имеется набор объектов и описаний. Эти объекты



Скачать 206.8 Kb.
Pdf просмотр
Дата13.02.2017
Размер206.8 Kb.
Просмотров235
Скачиваний0

ЛЕКЦИЯ 5
КРИПТОГРАФИЧЕСКИЕ
ХЕШ-ФУНКЦИИ
Хеш-функции впервые упоминаются в середине XX-го века как решение задачи о словаре.
1. Задача о словаре
Задача о словаре состоит в следующем: имеется набор объектов и описаний. Эти объекты хранятся в оперативной памяти или на жёстком диске. Требуется по описанию объектов быстро найти эти объекты (это могут быть файлы в файловой системе, записи в базе данных).
В 1953 году этим занимался
Дональд Кнут. В 1956 году это было явно опи- сано именно как хеш-функция. В 1968 году на эту тему появляется публикация в
«Communications of the ACM» — большая обзорная статья работника Bell Labs, кото- рый позже переходит в организацию NSA. Эта статья считается ключевой: в ней впервые подробным образом описывается, какие бывают хеш-функции, для чего они предназна- чены, какие плюсы и минусы у них есть.
2. Хеш-функции в программировании
2.1. Требования к хеш-таблицам и хеш-функциям
С точки зрения программиста,
хеш-функция — это некий алгоритм, который пере- водит строку произвольной длины в строку фиксированной длины (вектор из бит или байт). Если есть файл размером несколько мегабайт или в гигабайт, то с помощью хеш- функции можно получить строчку определённого размера (например, 64 бита, 128 бит,
256 бит). Этот процесс называется
хешированием. Причём к функции хеширования,
которую используют в программировании, предъявляется два требования:
1.
Быстрота вычисления функции — она не должна требовать каких-то серьёз- ных ресурсов.

!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
2
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
2.
Минимум коллизий.
2.2. Хеш-таблица
Предположим, что необходимо сохранить какое-нибудь соотношение «ключ-строка»,
причём этих значений имеется несколько десятков или сотен тысяч. Необходимо раз- местить их в оперативной памяти компьютера, а потом иметь возможность быстро на- ходить значение по ключу.
…ту ячейку, на которую он указывает. В этой ячейке хранится односвязный или двусвязный список, список дублетов «ключ-значение». Если этот список пустой, то туда просто помещается новая пара «ключ-значение». Если список непустой, тогда прохо- дим по всему списку и проверяем, нет ли совпадений по какому-то ключу. Если нет,
то добавляем новый элемент; если есть, тогда заменяем элемент. По такому принципу работают хеш-таблицы.
Теперь рассмотрим подробнее понятие
коллизий. Предположим, что объектов не 100
тысяч, а 1000 — столько же, сколько корзин выделили для хранения в хеш-таблице. Если в результате вычисления хеш-кода для всех ключей этот хеш-код будет одинаковый, то они все попадут в одну ячейку, а все остальные будут пустые. И тогда операция вставки,
поиска, обновления приведёт к постоянному пролистыванию списка. Никакой пользы от введения хеш-таблицы не получится, то есть это плохая хеш-функция, у которой очень много коллизий.
У хорошей хеш-функции должно быть минимальное число коллизий: все пары «ключ- значение» должны равномерно распределяться по хеш-таблице. В зависимости от ключа,
его хеш-значения (разных ключей) должны быть максимально различны насколько это возможно с учётом того, что хеш-код принимает ограниченное число значений.
В программировании по мере разрастания хеш-таблицы в неё добавляются новые ячейки, а у хеш-кода увеличивается область допустимых значений. Таким образом, ста- раются, чтобы в одной ячейке содержалось максимум одно значение, т. е. ключ-значение.
Для этого и используется хеш-код в программировании.
Ключ может быть произвольной структуры данных — строчка, число с десятью зна- ками после запятой или какая-то более сложная структура. Если нужно использовать её в качестве ключа для хеш-таблицы, необходимо реализовать у этого ключа метод хеш-кода.
В языке Java есть функции hashcode() (для вычисления этого ключа) и equals() (для сравнения). Hashcode() возвращает 32-битное значение, то есть может принимать зна- чения от
−2 31
до
(2 31
–1). Но количество ячеек меньше, поэтому хеш-код, после того,
как его вычислили для ключа, ещё повторно вычисляется. Самый простой способ — это поделить на
??????, где ?????? — число корзин в хеш-таблице.
На самом деле этот алгоритм немножко сложнее: он пытается распространить по максимуму значения по всей хеш-таблице, делает определённые предположения о том,
какая же функция хеш-кода — плохая или хорошая. Для поиска в таблице функция hashcode() должна быть быстро вычислима, и для того, чтобы эта таблица была запол- нена оптимальным образом, число коллизий должно быть минимальным.

3
!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
3. Примеры «хороших» хеш-функций
1.
Контрольная сумма — это число фиксированной длины. Например, в DES ис- пользуется ключ длиной в 56 бит и контрольная сумма ключа размером 8 бит. Эти
8 бит можно рассматривать как хеш-код от предыдущих 56 бит, который сокращает область значений.
2.
Cyclic redundancy check — от самых разных длин: от 1-го бита до 64-х бит.
3.
Алгоритм Пирсона для строк — популярный алгоритм для вычисления хеш- суммы от строки.
4.
Деление на простое число. Если вычислять хеш-код по модулю числа вида
10
n или числа вида
2
n
, то получится слишком много коллизий для таких чисел
(хеш-код от них одинаковый). Поэтому используют деление именно по модулю простого числа.
4. Криптографические хеш-функции
Если рассматривать с точки зрения криптографии, то хеш-функция — это такая функ- ция, которая устойчива ко криптографическим атакам двух типов.
1.
Атака на восстановление первого прообраза. Предположим, что злоумыш- ленник знает хеш-код некоторого сообщения, то есть он знает, что
ℎ — это результат вычисления хеш-функции от какого-то сообщения. Сложность вычисления прооб- раза — это сложность поиска такого сообщения
??????, что для него хеш-функция равна заданной.
2.
Устойчивость второго рода. Когда ничего не задано, кроме алгоритма крип- тографического хеширования, злоумышленник ищет два таких сообщения, у кото- рых совпадает хеш-функция (задача поиска коллизий). Если такие коллизии легко найти алгоритмически или вычислительно, то рассматриваемая хеш-функция счи- тается плохой с криптографической точки зрения.
Более серьёзное определение использовалось при разработке современного россий- ского стандарта
«Стрибог»:
1.
Сложность к вычислению прообраза: есть известно значение функции, то- гда должно быть сложно найти такое сообщение, хеш-функция от которого равна известному.
2.
Стойкость вычисления второго прообраза: пусть есть одно значение, и изве- стен хеш-код этого значения. Тогда злоумышленнику должно быть сложно найти еще одно такое значение, чтобы его хеш-функция совпадала с хеш-функцией пер- вого значения.
3.
Сложность к поиску коллизий: должно быть сложно найти два таких сообще- ния, которые не равны, но у них равны хеш-коды.

!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
4
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
4.
Стойкость к удлинению прообраза: если злоумышленник не знает сообщение,
но знает его длину и хеш-код от него, то ему должно быть сложно подобрать та- кое сообщение, которое, будучи дописанным к оригинальному, даст какую-нибудь известную хеш-функцию. Другими словами, не должно быть возможно злоумыш- леннику что-то менять путём дополнения в сообщении, получая известный выход.
Это можно сформулировать по-другому: хеш-функция не должна быть хорошо аддитируема.
5. Идеальная хеш-функция
Будем говорить об идеальной хеш-функции с криптографической точки зрения, у кото- рой длина
?????? (то есть на выходе ?????? бит). Тогда вычисление прообраза должно требовать как минимум
2
n операций (под одной операцией имеются в виду операции, сравнимые с вычислением хеширования).
Злоумышленник будет искать прообраз для идеальной хеш-функции следующим об- разом: у него есть число
ℎ, и ему надо найти такое ??????, что ??????(??????) = ℎ. Если это идеальная хеш-функция, то злоумышленнику остается лишь перебирать все возможные
?????? и про- верять, чему равна хеш-функция от этого сообщения. Результат вычисления, если
??????
перебирается полностью, есть фактически случайное число. Если число
ℎ лежит в диа- пазоне от
0 до 2
n
, то тогда в среднем злоумышленник будет тратить на поиски нужного

2n
2
= 2
n-1
итераций. Таким образом, вычисление прообраза займёт в два раза меньше итераций, чем в идеальном случае.
Вычисление второго прообраза останется с числом
2
n
В поиске коллизий оценка даст

2
n
, причём это не совсем точный результат. Это связано с
парадоксом дней рождения, который состоит в следующем: чтобы хотя бы у двух человек в классе вероятность совпадения даты рождения превышала
1 2
, нуж- но чуть более 20-ти человек, а не 180, как кажется на первый взгляд. Это происходит из-за того, что нужно анализировать не совпадения у одного человека с другим, а про- водить анализ всех возможных пар, которые создаются. Добавление одного человека увеличивает количествой сочетаний не на одну пару, а на
?????? пар, где ?????? — число уже существующих. Число таких пар растёт примерно квадратично. Поэтому, самая грубая оценка числа человек в классе —

365. Чем больше это число, тем точнее эта оценка
(по закону больших чисел). Таким образом, при достаточно больших числах (
2
n
) оценка

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

2
n
. Для поиска прообразов используются так называемые
радужные
таблицы.
Удлинение прообраза займёт
2
n операций, потому что придётся перебирать все воз-

5
!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
можные удлинения суффикса
??????.
6. «Стрибог»
У стандарта на хеш-функцию ГОСТ Р 34.11-94 были обнаружены уязвимости. Ожида- емая стойкость была одна, а фактическая стойкость (необходимое количество операций для поиска прообраза) оказалась другой.
Чтобы пройти соответствие международным стандартам, была придумана новая функция, которую условно назвали «Стрибог». Концепция этой криптографической хеш-функции состоит в использовании минимального числа элементов, но необходимого для того, чтобы обеспечить устойчивость ко всем известным криптографическим атакам на хеш-функцию.
Принципы построения хеш-функции «Стрибог»:
1. Неприменимость известных атак.
2. Использование хорошо изученных конструкций и преобразований.
3. Обеспечение каждого структурного элемента конкретными свойствами.
4. Использование самого простого для анализа и реализации варианта (если их несколько).
5. Максимальная производительность программной реализации.
В этой хеш-функции используются разные конструкции.
6.1. Конструкция Меркле – Дамгарда
Рис. 5.1
?????? — раундовая функция сжатия, |??????| — битовая длина сообщения, ??????

— завершающее преобразование.
Сообщение разбивается на блоки. Используется вектор инициализации и раундовая функция, куда подаются два входа. Подаётся некий блок сообщений и то, что получи- лось на предыдущем этапе. На первом блоке используется вектор инициализации. Таких этапов проводится много, пока всё сообщение не обработается. Затем проводится завер- шающее преобразование.
Если длина сообщения не кратна 64 битам, то оно дополняется некоторым блоком, а в конце дописывается число целых блоков. Это проводится для того, чтобы было трудно провести атаку на удлинение прообраза.
Свойства MD-конструкции:

!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
6
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
1. Если длины двух разных сообщений различны, последние блоки после дополнения должны гарантированно различаться.
2. При этом хеш-функция устойчива к коллизии, если раундовая функция устойчива к коллизии.
3. Без завершающего преобразования при известной коллизии можно легко найти другие коллизии, удлинняя сообщение; при известной коллизии можно найти муль- тиколлизии; если известно
??????(??????) при неизвестном ??????, то нетрудно найти ??????(??????||?????? )
для любого
?????? .
Сложность поиска прообраза и сложность удлинения прообраза составляют
2
n
, кол- лизии —

2
n
. Поиск второго прообраза —
2n u???
, где
?????? — длина сообщения. Именно из-за этого ограничения для каждой криптографической хеш-функции, которая основана на
MD-кодах, всегда указывают, какова максимальная длина файлов, которые можно ис- пользовать в качестве аргумента хеширования.
6.2. Завершающее преобразование
Рис. 5.2
Все блоки сообщения суммируются по модулю
2 512
, и в конце результат используется как вход для завершающей функции. Сложение происходит непобитово. Это обеспечи- вает защиту от нескольких атак: защита от удлинения прообраза, от мультиколлизий и от дифференциального криптоанализа.
6.3. Конструкция Миагучи – Пренели
Надёжная хеш-функция должна обечпечивать шифрование так, чтобы не было возмож- ности восстановить предыдущий блок
??????
i-1
и вход
??????, зная выход ??????. Также не должно быть возможно восстановить предыдущий блок, зная
?????? и ??????.
Любая функция шифрования (DES, GOST, AES) обеспечивает выполнение данных условий.
Однако существуют дополнительные требования специально для хеш-функций.
Конструкция
Миагучи – Пренели выглядит следующим образом.
Используется некая функция шифрования, но кроме того, что сообщение и преды- дущий результат передаются как аргументы функции шифрования, само сообщение и предыдущий результат складываются по модулю 2 с результатом шифрования. Это делается для обеспечения отсутствия фиксированных точек (пара
(??????
i
, ??????) называется

7
!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
Рис. 5.3
Рис. 5.4
фиксированной точкой, если
??????(??????
i
, ??????) = ??????
i
).
Если не использовать сложение сообщения и предыдущего результата, то злоумыш- ленник сможет понять, что если выход совпадает с предыдущим блоком, тогда он сможет сделать определённые выводы о самом сообщении. Или наоборот, он может пытаться по- добрать такие сообщения, чтобы на выходе получались одинаковые блоки.
6.4. Функция сжатия
Рис. 5.5
Здесь на каждом раунде меняется функция сжатия.
Функция сжатия в новом стандарте ГОСТ основана на
XSPL-шифре — это шифр,
основанный на таких операциях как побитовое сложение, SP-сеть и линейное преобра- зование.

!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
8
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
Рис. 5.6
Расписание ключей является важной частью этого шифра. Здесь функция генерации ключа такая же, как функция раунда шифрования. Используется некое инициализиру- ющее значение. Шифруя это значение с некоторыми константами, получаем раундовые ключи. Причём первой константой
?????? здесь выступает число раундов функции хеширо- вания. Это как раз то число, которое меняется для каждой функции сжатия.
??????
1
…??????
12

это некие константы, которые заданы в стандарте.
Результат этого шифрования используется как раундовые ключи. Есть фрагмент сообщения, который подвергается хешированию (оно используется как аргумент шиф- рования). В качестве ключа используются ключи
??????
1
,
??????
2
и т. д.
Для того, чтобы хеш-функция была устойчивой, используется надёжный блочный шифр в качестве элемента конструкции хеш-функции.
Существует множество криптографических атак, и чтобы от них защититься, необ- ходимо использовать такие сложные конструкции как блочные шифры.
В
XSPL-шифре 13 итераций. В нём используется сложение по модулю 2 векто- ров по 512 бит, нелинейная взаимнооднозначная замена байтов, перестановка внутри
512-битного вектора, преобразование
??????-го бита (?????? → 8?????? mod 63) и умножение векторов по 64 бит на фиксированную матрицу.
Этот шифр используется для того, чтобы предотвратить различные атаки на хеш- функцию: атаки скольжения, атаки отражения, разностных связных ключей и т. д. (ата- ки и на сам блочный шифр, и на результирующую функцию).
В этом шифре, в отличие от ГОСТа 1994-го года, блок дополняется нулями с единицей в конце (00…01) (раньше добавлялись только нули). Это усложняет атаку удлинением.
Ранее вектор инициализации не был фиксирован, то есть он не был описан в стан- дарте, но сейчас вектор инициализации состоит либо из всех нулей и единицы в конце для функции длиной 256 бит, либо из одних нулей для 512-битной функции.
Стандарт внедряет две функции хеширования разной длины, то есть из одного сооб- щения можно получить либо хеш-функцию длиной 256 бит (это минимальная возможная длина) либо 512 бит, которая считается более надёжной. Для них используются немного разные векторы инициализации.
XSPL обладает производительностью 51 такт на 1 байт исходного текста. Это намного медленнее, чем какие-нибудь генераторы псевдослучайной последовательности, но более надёжно.

9
!
Конспект не проходил проф. редактуру, создан студентами и,
возможно, содержит смысловые ошибки.
Следите за обновлениями на
lectoriy.mipt.ru
.
!
Для подготовки к экзаменам пользуйтесь учебной литературой.
Об обнаруженных неточностях и замечаниях просьба писать на
pulsar@ phystech. edu
7. Практическое применение хеш-функций
7.1. Проверки целостности
Многие организации, выкладывая файлы на сервер, дополнительно указывают его
чек-
сумму — это код, который человек, скачав файл, может вычислить самостоятельно и сравнить с тем, что указано на сайте. Если этот код совпадает, значит файл как мини- мум был скопирован с того же сайта, то есть его не подменили по пути и не внедрили в него вирусы.
Указывают обычно две чексуммы. Например CRC32 (это стандартный циклический код), MD5. В последнее время указывают SHA-2 или SHA-3 (SHA-256 либо SHA-512).
Допустим, имеется файл, который представляет из себя сообщение
??????, и злоумыш- ленник хочет внедрить в него вирус. Если на сайте выложен код
CRC32 (он не стоек с криптографической точки зрения), то злоумышленник, внедрив вирус в файл, мо- жет дополнительно поменять файл таким образом, чтобы CRC совпали с предыдущим файлом. Более того, CRC32 короткий — 32 бита на выходе (можно перебрать полным перебором).
С
MD5 ситуация обстоит сложнее, но, тем не менее, для MD5 уже найдено множество коллизий, составлены радужные таблицы, и подменить файл достаточно просто.
SHA считаются надёжными с криптографической точки зрения. Если злоумыш- ленник поменял в сообщении
?????? несколько байт, то хеш-код полностью изменится. Зло- умышленник будет пытаться дополнить этот файл бессмысленными наборами символов,
которые не повлияют на работу вирусов и программы, таким образом, чтобы хеш-код от нового файла совпадал со старым файлом. Но он это сможет сделать, только если здесь будет использоваться ненадёжная хеш-функция. Если хеш-функция надёжная, то перебор файлов займёт слишком много времени.
7.2. Электронная подпись
Чтобы убедиться, что сообщение отправил конкретный отправитель, вместе с сообще- нием передаётся так называемая электронная подпись. Получатель проверяет, действи- тельно ли электронная подпись относится к данному сообщению. Используя криптогра- фию с открытыми ключами, такую электронную подпись построить возможно.
Но операции с открытыми ключами (подписывание, проверка подписей и т. д.) очень медленные (40 Кбайт/с). Более того, если подписывать всё сообщение целиком, то раз- меры этой подписи будут сопоставимы с размером сообщения. Поэтому подписывают не сообщение, а хеш-функцию от сообщения. И далее получатель, когда расшифровывает подпись, получает хеш-функцию. Далее он сравнивает хеш-функцию от того сообщения,
которое он получил, и хеш-функцию, которая была получена в результате расшифров- ки. За счет того, что хеш-функция имеет фиксированную длину, она меньше, чем само сообщение. За счёт этого можно быстро вычислить электронную цифровую подпись.
Размер этой подписи будет мал по сравнению с размером сообщения.
Если хеш-функция плохая, тогда злоумышленник сможет подменить сообщение та- ким образом, чтобы хеш-функция осталась прежней. А если хеш-функция хорошая,
тогда этот алгоритм будет работать.


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


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

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


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