Компьютерная безопасность. Криптографические методы защиты - Петров А.А.
ISBN 5-89818-064-8
Скачать (прямая ссылка):
• хэш-функция должна быть стойкой против атаки методом «грубой силы»;
• программная реализация хэш-функции должна быть оптимизирована под использование на современной аппаратно-программной базе.
Этим требованиям должен удовлетворять как сам алгоритм выработки хэш-значения, так и хэширующая функция.
В современных условиях алгоритмическое повышение скорости выработки хэш-значения может быть достигнуто за счет применения простого
84
Общие сведения по классической криптографии
преобразования, которое переводит одно сообщение в другое посредством элементарной операции, например удаления произвольного блока сообщения. Подобными преобразованиями можно также описать зависимость между двумя практически не отличающимися друг от друга сообщениями. Данный тип сообщения очень часто встречается в банковском деле, например с целью заполнения бланков платежных поручений. Отсюда следует, что для увеличения скорости обработки необходимо, чтобы алгоритм выработки хэш-значения включал в себя также алгоритм вычисления хэш-значения одного сообщения из хэш-значения другого сообщения, которое получается из начального с помощью элементарного преобразования.
1.5.4. Стойкость хэш-функций
С точки зрения криптографической стойкости важным свойством хэш-функций является отсутствие коллизий, то есть невозможность найти такие значения х ^ у, чтобы h(x) = h(y). В криптографических приложениях важным понятием является криптографически стойкая хэш-функция, для которой не существует эффективного алгоритма нахождения значений х & у, где выполнялось бы условие h(x) = h(y) (функция, стойкая в сильном смысле), или не существует эффективного алгоритма нахождения коллизии при заданном х такого у ^ х, что h(x) - h(y) (функция, стойкая в слабом смысле). Росс Андерсон показал, что отсутствие коллизий не позволяет судить о практической стойкости хэш-функций. Другими словами, данное требование носит формальный характер. Практически значимым является отсутствие у хэш-функции корреляции. Свободной от корреляции называется хэш-функция, у которой невозможно найти пары таких значений х ^ у, что вес Хэмминга двоичного вектора h(x) хог h(y) будет меньше веса Хэмминга применительно к двоичному вектору h(M) для некоторого малого М. Свобода от корреляции с точки зрения криптографической стойкости является гораздо более сильным свойством хэш-функции, чем свобода от коллизий. Данный факт подтверждается тем, что из любой хэш-функции, являющейся свободной от коллизий и одновременно свободной от корреляций, можно построить другую хэш-функцию, которая тоже будет свободной от коллизий, но при этом может не сохранить свойство свободы от корреляции.
Пример
Возьмем функцию h, обладающую двумя вышеперечисленными свойствами, зафиксируем небольшое по сравнению с длиной входной последовательности значение к. Разобьем входную последовательность S на S1,
Ключевая информация
85
состоящую из первых к бит, и на S2 - оставшуюся часть входной последовательности (S = SiIlS2).
Теперь определим функцию Ir1 как H1(S) = S11| h (S2). Таким образом, в выходной последовательности первые к бит останутся без изменений. Очевидно, что ht свободна от коллизии, поскольку таковой является функция h. Однако IT1 не унаследовала свойство свободы от корреляции, так как можно легко построить X и Y, при которых значение h(X) отличается от h(Y) на к бит.
Необходимо отметить, что основным способом поиска коллизий у хэш-функций является метод, основанный на «парадоксе дня рождения». Суть его заключается в генерации двух наборов по 2п/2 сообщения в каждом. Согласно парадоксу дня рождения вероятность того, что в этих наборах найдется пара сообщений, имеющих одинаковые хэш-значения, больше 1/2. Из недостатков метода следует отметить значительные временные затраты для генерации данных наборов сообщений, необходимость иметь большой объем памяти для их хранения и наличие быстрых алгоритмов сортировки. Этот метод в случае короткой длины хэш-значения является эффективным как для хэш-функций, построенных с нуля, так и для хэш-функций, построенных на основе известных алгоритмов блочного шифрования. Хотя к хэш-функциям, построенным на основе алгоритмов блочного шифрования, применимы методы криптоанализа алгоритмов блочного шифрования.
7.6- Ключевая информация
1,6.1. Общие сведения
При создании и эксплуатации систем криптографической защиты потока данных приходится сталкиваться с проблемой создания, хранения и распределения ключей или исходной ключевой информации, на основе которой в дальнейшем создаются непосредственно сами ключи. Повышенное внимание к решениям подобных проблем вызвано тем, что злоумышленнику бывает гораздо проще провести атаку на ключевую систему, нежели на криптографические алгоритмы. По своему назначению ключи бывают нескольких типов (в соответствии со стандартом ANSI Х9.17):
• для зашифрования ключей;
• для зашифрования данных.
86
Общие сведения по классической криптографии
Кроме того, при использовании криптографических средств защиты межмашинного взаимодействия приходится создавать так называемые сеансовые ключи, которые применяются только в рамках одного сеанса связи. В зависимости от того, к какой категории принадлежит ключ, будут меняться и пути решения вышеперечисленных проблем.
