Генерация ключа для шифра Вернама с помощью хеш-функций

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

Однако у шифра Вернама есть еще одно требование: ключ должен использоваться однократно. Чтобы обеспечить это, при шифровании добавим к мастер-ключу достаточно длинное случайное число, которое будет уникальным для каждого шифруемого сообщения. При этом возникает необходимость как-то сохранить или передать это случайное число для того, чтобы можно было расшифровать сообщение. Очевидно, что сохранять его в открытом виде нельзя, но можно наложить на него мастер-ключ с помощью операции "исключающее ИЛИ", и добавить получившийся результат в начало или конец сообщения. При расшифровке при знании мастер-ключа это случайное значение можно будет снова легко получить, тогда как без знания оказываемся перед необходимостью сделать исключающее ИЛИ для двух неизвестных величин.

В итоге я получил следующий алгоритм шифрования:



  1. Получаем мастер-ключ Master. В простейшем случае это может быть результат хеш-функции от пароля, вводимого с клавиатуры.
  2. Генерируем случайное значение Rnd.
  3. Вычисляем значение Buffer=Xor(Master,Rnd) и сохраняем Buffer в выходном файле
  4. Вычисляем начальное значение ключа, зависимого от предыдущего блока: Prev=Hash(Rnd+Master)
  5. Читаем из входного файла 1 блок в Buffer,
  6. Если достигнут конец файла и ничего не прочиталось, переходим к п. 11.
  7. Генерируем ключ для шифрования очередного блока из Master, Rnd и Prev: Stage_Key=Hash(Prev+Rnd+Master)
  8. Шифруем этим ключом прочитанный из файла блок: Buffer=Xor(Buffer,Stage_Key) и сохраняем Buffer в выходной файл
  9. Обновляем значение Prev=Xor(Prev,Buffer) (Buffer здесь содержит уже зашифрованные данные), также возможен вариант реализации Prev=Buffer, но он является менее безопасным
  10. Переходим к пункту 5
  11. Закрываем выходной файл и завершаем работу.

Примечание: Xor — это операция побитового ИЛИ, Hash — операция взятия хеш-функции, оператор + означает конкатенацию двух блоков данных.



Таким образом, даже одно и то же исходное сообщение, зашифрованное дважды одинаковым мастер-ключом, даст совершенно различные зашифрованные сообщения. Кроме этого, побочным эффектом данного алгоритма является также обеспечение целостности зашифрованного сообщения (кроме последнего блока). Из-за свойства хеш-функции изменение хотя бы одного бита в шифрованном сообщении приведет к тому, что существенно изменится значение Prev, которое повлияет на Stage_Key на последующем шаге, и все последующие блоки после расшифровки будут содержать нечитаемые данные.

Тем не менее, ряд потенциальных уязвимостей у данного алгоритма все же имеются. Во-первых, уязвимости хеш-функций и генератора случайных чисел. Во-вторых, если каким-то образом станет доступным текст хотя бы одного блока одного сообщения, станет возможно вычислить значение мастер-ключа перебором, но это крайне сложная вычислительная задача: для первого блока сообщения потребуется перебор 2N*2 вариантов (где N — длина блока в битах), для последующих — 2N*3, в частности, если использовать хеш-функцию SHA-512, получаем 21024 для первого блока и 21536 вариантов для последующих. Для защиты от этого можо принять ряд дополнительных мер:


  1. добавлять перед шифрованием собственно сообщения шифрование случайного числа длиной в один блок
  2. организовать циклический сдвиг байтов внутри блока в зависимости от значения i-ого бита случайного числа Random
  3. увеличить размер случайного числа Random до размера, кратного нескольким блокам.


В приложенном файле содержится экспериментальная реализация данного алгоритма на языке C с использованием хеш-функции SHA-512.

Добавлено позже: строго говоря, формальному определению шифра Вернама предложенная схема все же не соответствует. Однако при использовании уникального мастер-ключа для каждого сообщения она позволяет максимально приблизиться к нему в плане безопасности.


0
Цитировать