Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Оптимальная защита от коллизий при хешировании с двойной длиной блока с ключом единичной длины.
Барт Менник
Dept. Electrical Engineering, ESAT/COSIC, KU Leuven, and IBBT, Belgium
bart.mennink@esat.kuleuven.be
Реферат.
Идея хеширования двойного блока состоит в том, чтобы построить функцию сжатия на 2n-битах, используя блочный шифр с длиной блока n. Все оптимально безопасные хэш-функции с двойной длиной блока, известные в литературе, используют шифр с пространством ключей размером в два блока, 2n-бит. С другой стороны не известно не одной оптимально безопасной функции сжатия, основанной на шифре с пространством ключей в n-бит. Данная работа относится к этой проблеме. Сначала в ней доказывается, что для широкого класса функций сжатия с двумя вызовами лежащего в её основе блочного шифра с ключом в n-бит, коллизии могут быть найдены за 2n/2 запросов. Эта атака применима, кроме прочих, к тем функциям, в которых результат линейно выводится из выходных данных блочного шифра. Это наблюдение показывает, что все показатели защищенности разработок, использующих шифр с пространством ключей в 2n-бит, полностью опираются на эти дополнительные n-бит ключа. Основной вклад этой работы заключается в доказательстве того, что эта проблема может быть решена путем позволения функции сжатия совершить один дополнительный вызов шифра. Предлагается семейство функций сжатия, совершающих три вызова блочного шифра, асимптотически приближающихся к оптимальной устойчивости к коллизиям на интервале до 2n(1-ε) запросов и устойчивости прообраза на интервале до 23n(1-ε)/2 запросов для любого ε > 0. Насколько известно, это первая конструкция с блоком двойной длины и пространством ключей единичной длины, обладающая оптимальной защищенностью от коллизий.
1 Введение.
Хэширование с двойной длиной блока является признанным методом построения функции сжатия с выходными данными в 2n-бит, основанной на n-битных блочных шифрах. Идея хеширования c двойной длиной блока относится к работе Мейера и Шиллинга [19], в которой представлены функции сжатия MDC-2 и MDC-4. В последние годы эта методология снова получила распространение в работах [2,4,7,9,10,12,16,21,27]. Хеш-функции с двойной длиной блока имеют очевидное преимущество перед функциями, основанными на классическом блочном шифре, такими как функция Дэвиса-Мейера и функция Матиаса-Мейера-Осиса [22,26]: тот же тип основных примитивов позволяет получить лучшую функцию сжатия. Тем не менее, для функции сжатия двойной длины сложнее достичь оптимальной защищенности от нахождения n-битных коллизий и 2n-битных прообразов.
Данная работа фокусируется на самом простом и более изученном типе функций сжатия, а именно функциях, которые сжимают 3n-бит в 2n-бит. Они могут быть разделены на два класса:
класс DBL2n - функции сжатия, которые используют блочный шифр с 2n-битным ключом: E: {0, 1}2n × {0, 1}n → {0, 1}n, класс DBLn - функции сжатия, которые используют блочный шифр с n-битным ключом: E: {0, 1}n × {0, 1}n → {0, 1}n.
Класс DBL2n достаточно понятен. Он включает классические функции сжатия Tandem-DM и Abreast-DM [8] и функцию Хироси [6], а так же усовершенствованную функцию сжатия типа I с единичиным вызовом, разработанную Стемом [25, 26] (пересмотрена в [14]), общие разработки Хироси [5] и Озена и Стема [21]. Как показано в таблице 1, все перечисленные функции гарантируют оптимальную защищенность от коллизий (вплоть до 2n запросов), а для Tandem-DM, Abreast-DM и функции Хироси также доказана оптимальная устойчивость прообраза (вплоть до 22n запросов). Эти оценки справедливы и для итерации, при применении надлежащего расширителя домена [1]. Лаксом [15] была представлена функция сжатия, в которой возможны коллизии после 2n/2 запросов, но при этом достигается оптимальная устойчивость к коллизиям за итерацию. К класса DBLn относятся функции сжатия MDC-2 и MDC-4 [19], конструкция MJH [10] и конструкция Жетчева. [7]. Для функций сжатия MDC-2 и MJH коллизии прообраза могут быть найдены за 2n/2 и 2n запросов соответственно1. (Сноска: За итерацию устойчивость к коллизиям доказана для 23n/5 запросов для MDC-2 [27] и для 22n/3 запросов для MJH [10]. ) Функция сжатия MDC-4 позволяет получить большую степень устойчивости прообразов и устойчивости к коллизиям, чем MDC-2 [16], но в отличие от других функций она делает четыре вызова блочного шифра. Конструкция Жетчева делает два вызова блочного шифра и достигает устойчивости к коллизиям на 22n/3. Стем также представил разработку, основанную на двух вызовах, и доказал для неё оптимальность устойчивости к коллизиям на ограниченной модели безопасности, в которой атакующий должен определить все запросы заранее. Вследствие этого мы не включили эту разработку в таблицу. Дальнейшие результаты в этой области включают работу группы, под руководством Нанди [20], в которой представлена функция сжатия 3n-в-2n-бит. Данная функция выполняет три вызова однонаправленной функции 2n-в-n-бит, которая достигает устойчивости к коллизиям на 22n/3 запросах. Также в этой работе полученный результат был расширен на на функцию 4n-в-2n-бит засчет использования трех блочных шифров с 2n-битным ключом.
В отличие от класса DBL2n, для класса DBLn не известны оптимально безопасные функции сжатия. Ситуация остается той же и для итерации, где ни для одной из этих разработок не было доказано достижение оптимальной устойчивости. Определяющей для этого пробела является разница в основных примитивах: в классе DBL2n основные примитивы отображают 3n бит в n бит и, таким образом, достигают большего сжатия. В частности, если мы рассмотрим функции Tandem-DM, Abreast-DM и функцию Хироси, первый вызов шифра уже сжимает все входные данные функции сжатия, а второй вызов шифра используется просто для гарантированного 2n-битного выхода. В действительности эти разработки достигают своего уровня устойчивости только за счет этого свойства, а доказательство полностью основывается на нём (см. Раздел 4).
Таким образом, с теоретической точки зрения бессмысленно сравнивать DBL2n и DBLn. Но различия между двумя классами оставляет нерешенной интересную проблему: начиная с одноблочного шифра E: {0, 1}n × {0, 1}n → {0, 1}n, возможно ли построить функцию сжатия с двойной длиной блока, для которой достигается устойчивость к коллизиям и устойчивость прообразов? Это основной исследовательский вопрос этой работы. Заметим, что оценка Стема [25] не применима к данной проблеме: она показывает, что коллизии могут быть найдены не более чем за (2n )(2r-1)/(r+1) запросов, где r соответствует количеству вызовов блочного шифра, что приводит к тривиальной оценке для r ≥ 2. Для r ≥ 2 обозначим функцию сжатия, которая делает r вызовов к примитиву E, как Fr: {0,1}3n → {0,1}2n.
Таблица 1. Гарантии устойчивости асимптотически идеальных моделей шифров для известных функций сжатия с двойной длиной блока в классах . Более подробное сравнение некоторых из этих функций представлено в [3, приложение А].
|
Функция сжатия |
Вызовы Е |
Устойчивость к коллизиям |
Устойчивость прообраза |
Основной шифр |
|
Лакс Стем Tandem-DM Abreast-DM Хироси Класс Хироси Класс Озена-Стема |
1 1 2 2 2 2 2 |
2n/2 2n [26] 2n [12] 2n [4,9] 2n [6] 2n [5] 2n [21] |
2n 2n [26] 22n [2,13] 22n [2,13] 22n [2,13] 2n [5] 2n [21] |
|
|
MDC-2 MJH Жетчев MDC-4 Данная работа |
2 2 2 4 3 |
2n/2 2n/2 22n/3 [7] 25n/8 [16] 2n |
2n 2n 2n [7] 25n/4 [16] 23n/2 |