Многозначное шифрование с использованием хеш-функций: продолжение

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

Идея

Для начала напомню идею метода (теперь уже с конкретной реализацией). Для усеченных хеш-функций мы без труда можем генерировать коллизии, и чем меньше разрядность выхода хеш-функции, тем быстрее коллизия может быть получена. В практической реализации за основу я взял усечение до двух байт хеш-функции md5, назовем ее md5R.

Таким образом, md5R(‘test’) = 098f, но и md5R(‘d43912ad6e9a34f2c8178cbe49c73029’) тоже равна 098f. Такие коллизии получаются в среднем за 256^2/2 (что равно 32768) итераций применения хеш-функции, что на современных компьютерах почти «мгновенно».

Мы можем разбить исходную строку для шифрования на символы, и каждый символ закодировать значением md5R(ключ_шифрования + этот_символ). Для строки test и ключа key мы получим

md5R('keyt') = f244 md5R('keye') = 2070 md5R('keys') = 14f8 md5R('keyt') = f244 

Процесс дешифровки заключается в получении коллизии для значений справа от равенства и разделения коллизии на пару «предположительный ключ» + «символ исходного текста».
Но пока ничего хорошего мы не видим: во-первых одинаковые символы представляются как одинаковые коды, во-вторых однозначности дешифровки нет, опять же из-за легкости получения коллизии (с некоторой, хоть и очень небольшой вероятностью).

Например значение f244 может быть восстановлено как md5R(‘95fcc7f085941bceaaeba18f08a024b5′), что дает ключ ’95fcc7f085941bceaaeba18f08a024b’ и расшифрованный символ ‘5’. А если мы фиксируем ключ (который мы знаем), мы все равно можем подобрать другое значение расшифрованного символа из-за случайной коллизии.

Для того чтобы решить эту проблему используется фиксированный и однозначный алгоритм перебора для поиска коллизии при известном ключе: грубо говоря, перебираем все символы из алфавита и выдаем первый подходящий за результат. Назовем этот процесс decrypt(key, data) = char.

Задача шифрования encrypt(key, char) = data, получить такой результат, чтобы достигалась взаимная однозначность применения функций: decrpyt(key, encrypt(key, data)) = data.

Для этого вводится специальная «плавающая» переменная: контрольное значение (control_value), и используется специальный трюк; функция decrypt выполняет перебор шифрованного символа вместе с контрольным значением по фиксированному алгоритму до достижения коллизии. Таким образом, decrypt(key, data) = {char, control_value}:

char decrypt(string key, string data, int& control_value) { 	for (int control = CONTROL_VALUE_MIN; control <= CONTROL_VALUE_MAX; control++) 	{ 		for (int CHAR = MIN_CHAR_INDEX; CHAR < MAX_CHAR_INDEX; CHAR++) 		{ 			buffer = key + control + CHAR; 			if (md5R(buffer) == data) 			{ 				control_value = control; 				return CHAR; 			} 		} 	} } 

Функция шифрования (encrypt) тоже усложняется: она ищет перебором такое значение control_value, что если выполнить decrypt(key, md5R(key + control_value + char)), мы получим {char, control_value}. Весь смысл контрольного значения: добавить новую переменную, которую функция шифрования вольна изменять, для уверенного достижения корректной расшифровки. Корректность гарантируется моделированием результата дешифровки. Таким образом, если мы зашифруем текст заданным ключом (посимвольно), а затем расшифруем тем же ключом то получим набор коллизий в точности соответствующий исходному тексту, при условии, что порядок перебора control_value в функциях шифрования и дешифровки согласован. Но в последнем требовании и нет ничего особенного — в большинстве методов несогласованное изменение методов шифрования и дешифровки могут дать произвольный результат; разве что здесь, глядя на исходный код — это не очевидно:

string encrypt(string key, char CHAR) { 	for (int control = CONTROL_VALUE_MIN; control < CONTROL_VALUE_MAX; control++) 	{ 		string buffer = key + control + CHAR; 		string hash = md5R(buffer); 		int control_value_temp; 		if (decrypt(key, hash, control_value_temp) == CHAR) 			return hash; 	} } 

Теперь это работает, но вся магия метода, заключается в том, что шифрование может моделировать несколько различных параметров дешифровки (различные ключи), что позволяет зашифровать несколько текстов с разными ключами в одно выходное значение. Но «плотность информации» никто не отменял, и если размера выхода недостаточно, чтобы представить набор исходных данных, то зашифровать их не получится. А при усечении выхода md5R до двух байт мы можем гарантированно сохранить до двух однобайтовых символов с различными ключами (при условии, что диапазон контрольных значений больше чем размер входного множества; в данном случае — 256^2, количество возможных значений для одного символа в степени количества входных символов).
Алгоритм усложняется совсем незначительно:

		... 		if (decrypt(key1, hash, control_value_temp1) == CHAR1  			&& decrypt(key2, hash, control_value_temp2) == CHAR2) 		... 

При этом значительно увеличивается время работы: в случае шифрования одного текста контрольные значения почти всегда равны CONTROL_VALUE_MIN, то есть их перебор останавливается на первом шаге. А в случае двух текстов нужно перебрать в среднем квадрат(число_итераций_для_коллизии (выше уже считали, что это около 32768) * информационное_заполнение_выхода). Оно равно 1, если исходные символы лежат в полном диапазоне 0..255, но уменьшается, если исходные символы лежат в некотором подмножестве (CHARSET). Для набора из 96 символов информационное заполнение будет 0,375^2 ~= 0,14, что даст нам до 4608 итераций в среднем в худшем случае. Квадрат возникает из-за вызова в функции шифрования функции дешифровки с теми же параметрами.

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

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

for (size_t i = 0; i < message.size(); i += BLOCK_MAX_LEN) { 	key_alter_stream = md5(key_alter_stream); 	... 	result += encrypt_block(key_alter_stream, message.substr(i, BLOCK_MAX_LEN)); } 

Реализация

Скачать исходный код можно по ссылке: dl.dropbox.com/u/243445/hash_crypt/HashCodeCpp.cpp
Бинарник (Win32) здесь: dl.dropbox.com/u/243445/hash_crypt/HashCodeCpp.exe

После запуска без параметров программа выполняет «демонстрационный режим»; шифрует два текста с различными ключами в один поток и показывает, что будет, если расшифровать поток другим «случайным» ключом:

Режимы использования утилиты следующие:
HashCodeCpp -d ключ шифртекст — дешфировка
HashCodeCpp -e ключ сообщение — шифрование
HashCodeCpp -e2 ключ1 сообщение1 ключ2 сообщение2 — шифрование одновременно двух сообщений в один информационный поток
И еще один интересный режим:
HashCodeCpp -b сообщение шифртекст — подбор такого ключа, что шифртекст расшифровывается им в заданное сообщение (работает долго, экспоненциальная сложность относительно длины шифртекста).

Анализ

• security through obscurity? — нет, это совсем не оно, алгоритм не скрывается, а единственной секретной частью остается ключ шифрования;
• идея стойкости — стойкость алгоритма опирается на невозможность узнать ни один бит входных данных md5 по ее выходу. Если это не так, то криптостойкость алгоритма отсутствует, однако при неизвестном ключе и неизвестности ни одного байта шифрованного сообщения восстановить ни ключ ни сообщение не удастся, т.к. шифртекст соответствует бесконечному набору пар (ключ; сообщение) без возможности определить, какая именно является «истинной». Далее будем считать, что возможность получения информации о входном значении md5 по выходному отсутствует (пока это так, но если возникнут причины опасения, мы можем поменять хеш-функцию на другую);
• при наличии шифртекста и открытого входного сообщения получить ключ шифрования практически невозможно — ключ можно получить только полным перебором (исходя из свойств хеш-функции), но и найденный вариант не обязан соответствовать реальному ключу шифрования. Длина шифртекста уменьшает вероятность нахождения случайной коллизии ключа экспоненциально, и линейно увеличивает время, необходимое на проверку ключа при переборе. При условии достаточной сложности исходного ключа время перебора будет слишком большим (если помните, функция decrypt делает тысячи вызовов md5 на каждый символ текста);
• можно ли узнать, что в шифртексте есть еще пара (ключ, сообщение), зная одну пару? — в текущей реализации да, по распределению полученных control_value можно сделать предположение о наличии еще одной пары (они будут сильно отличаться от нуля), но в следующей версии я постараюсь это исправить (нужно аккуратно рассчитать начальное смещение контрольных значений, в зависимости от значения ключа, при шифровании);
• поможет ли первая пара восстановить вторую? — нет, получение пары ключ-значение все равно будет сводиться к перебору;
• не разрушает ли стойкость алгоритма посимвольное шифрование? — нет, до тех пор, пока по выходу md5 нельзя узнать данные о его входе, кроме как перебором;
• какую информацию можно получить зная только шифртекст — длину исходного сообщения;

Одним из важных вопросов является возможность приведения времени шифрования к приличным значениям (по несколько секунд на символ — все же неприлично), над чем я еще подумаю. Практически это возможно (оптимизации, использование GPU), но алгоритмическая сложность не поменяется (я не вижу, как это можно сделать, сохранив свойства метода).

Критика

Одной из существенных проблем является вопрос, «а нужен ли этот метод вообще?». И да, у него есть два важных свойства: возможность алгоритмически «укрыть» два текста в одном контейнере без использования методов security through obscurity (как например скрытые разделы TrueCrypt, стеганография и т.п.), и очень низкая скорость расшифровки by-design (с известным ключом), препятствующая возможности эффективного прямого перебора.