BC/NW 2016 № 1 (28):11.1

МЕДОВОЕ ШИФРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЁННЫХ 8-БИТНЫХ ЦЕЛЫХ ЧИСЕЛ БЕЗ ЗНАКА

Зубов И.А.

Введение

Медовое шифрование («honey encryption») — новаторская концепция в криптографии, предложенная американскими учёными А. Джулсом и Т. Ристенпартом в начале 2014 [1, 5, 6, 7]. В её центре лежит предложение создать такое шифрование, которое при вводе неправильного ключа при расшифровке выдаёт ложные, но правдоподобные данные.

Дело в том, что при использовании традиционного шифрования полный перебор всех возможных ключей злоумышленником обязательно приведёт к взлому шифротекста. Для отделения правильно расшифрованных данных проще всего эксплуатировать применяемые имитовставки, электронные подписи или дополнения при шифровании, говорящие о правильности или неправильности расшифровки. Однако даже если они не применяются, у злоумышленника есть другой путь — так как при использовании неверного ключа осмысленные данные расшифровываются в последовательность псевдослучайных чисел, то он всё равно часто может найти исходные данные. Разумеется, современные алгоритмы шифрования стараются сделать полный перебор невозможным за счёт большой длины ключа, но из-за проблем криптографических алгоритмов или их реализаций часто можно заменить полный перебор на сокращённый [4].

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

Применяемые алгоритмы кодирования и декодирования

Итак, мы имеем самый миниатюрный и простой тип числовых данных, который позволяет хранить в одном байте целые числа от 0 до 255. Предположим, что в шифруемом массиве по логике возможны лишь некоторые значения чисел — например, от 100 до 200, причём вероятность их появления примерно одинакова (либо мы просто не хотим давать злоумышленнику более точных метаданных об этих числах в силу конфиденциальности этих метаданных). Если злоумышленник будет дешифровывать массив таких чисел путём атаки по словарю или полного перебора, то получив в любом члене массива значение от 0 до 99 или от 201 до 255, он будет точно знать, что текущий ключ дешифрования неверен, и продолжит поиск. Поскольку операция дешифрования при неверном ключе даёт псевдослучайные данные, то вероятность появления любого из чисел от 0 до 255 равна 1/256. Для массива из одного элемента вероятность правдоподобной дешифровки произвольным ключом в этом случае равна (200 - 100 + 1) / 256 = 101 / 256 = 0.39453125, для массива из пяти элементов — 0.39453125 ^ 5 = 0.00955888072, для массива из пятидесяти — 0.39453125 ^ 50 = 6.3689879 * 10 ^ (-21). Для запутывания злоумышленника нам хотелось бы, чтобы попытка дешифровки любым ключом давала бы правдоподобный результат.

Первый наивный подход к достижению этой цели следующий (рис. 1):

1. На основе минимального и максимального возможных значений в массиве находим размер полной группы элементов (group_size = max - min + 1), а также число групп, которые поместятся в кодовое пространство от 0 до 255 (group_num = округление_с_избытком(256 / group_size) ). Если 256 нацело делится на размер группы, то последняя группа будет полной (т. е. будет иметь ровно group_size элементов), однако скорее всего она будет неполной (т. е. будет иметь от 1 до (group_size - 1) элементов).

2. При кодировании элемента массива мы сначала нормализуем его — вычитаем из него минимальное значение min, получая значение в диапазоне от 0 до (max - min), после чего помещаем это значение в случайно выбранную группу. Это можно сделать прибавлением к нормализованному элементу случайного неотрицательного числа, умноженного на размер группы (rand * group_size), при условии что результат не превышает 255.

3. При декодировании элемента сначала найдём его значение по модулю group_size, получая значение в диапазоне от 0 до (max - min). После этого денормализуем его, прибавив к нему минимальное значение min, получая значение в диапазоне от min до max.

Рис. 1. Наивный подход к медовому шифрованию 8-битных целых чисел без знака

К сожалению, такой подход имеет существенный минус: результирующее распределение скорее всего будет иметь повышенные вероятности в левой части и пониженные в правой, так как последняя группа почти наверняка будет неполной. Скажем, если мы кодируем числа от 0 до 254, то вероятность дешифровки числа 0 будет в два раза больше, чем чисел от 1 до 254, поскольку число 0 в отличие от всех остальных чисел кодируется двумя числами: 0 и 255.

Для решения этой проблемы Джулс и Ристенпарт предлагают использовать для кодирования большее кодовое пространство, чем для изначальных чисел [1] — например, кодировать однобайтовые числа двумя байтами. Именно этим путём стоит пойти для решения возникшей проблемы. Разумеется, это потребует в два раза больших затрат памяти, но существенное повышение безопасность оправдывает такие затраты. Несложно увидеть, что при использовании кодового пространства от 0 до 255 в худшем случае (размер группы от 129 до 255) есть 1 полная и 1 неполная группа, в результате чего вероятности появления части чисел будут на 50% выше, чем другой части чисел. При использовании кодового пространства от 0 до 65 535 в худшем случае (размер группы, равный 255) есть 257 полных и 1 неполная группа, в результате чего вероятности появления части чисел будут не более чем на 0,3875969% выше, чем других. Если нас не устраивает даже такой небольшой перекос, мы можем использовать ещё большее кодовое пространство, но для большинства приложений этого должно хватить.

Возможны также несколько особых ситуаций, которые необходимо рассмотреть отдельно: это ситуации, когда group_size = 256 (т. е. возможны любые значения чисел от 0 до 255) и когда group_size = 1 (т. е. возможно лишь одно значение чисел). В первом случае мы копируем массив входных данных в массив выходных данных, а затем дополняем его массивом псевдослучайных байт той же длины — раз уж все значения уже допустимы, то опция медового шифрования таких данных фактически уже активирована, осталось лишь скрыть факт появления этой особой ситуации. Во втором случае мы вместо описанных выше операций просто записываем в выходной массив псевдослучайные числа, поскольку все они при расшифровании будут переведены в это единственное допустимое значение. Для скрытия факта появления этой особой ситуации размерность выходного массива в байтах должна быть в 2 раза больше оригинального. Таким образом получим, что при кодировании N однобайтовых чисел преобразуются в N двухбайтовых чисел (то есть 2N байт), и наоборот, при декодировании N двухбайтовых чисел преобразуются в N однобайтовых чисел.

Детали реализации

Вторая, усложнённая версия алгоритма, использующая кодовое пространство от 0 до 65 535, была реализована автором данной статьи программно для более детального анализа. При разработке данной программы особое внимание было уделено тестированию. Была написана тестовая программа, которая:

1) кодирует и декодирует псевдослучайные данные в определённом поддиапазоне типа uint8_t, проверяя их совпадение до и после этих операций;

2) кодирует, зашифровывает, расшифровывает, декодирует псевдослучайные данные в определённом поддиапазоне типа uint8_t, проверяя их совпадение до и после этих операций;

3) проводит атаку методом «грубой силы» [4] со сложностью 2^16 вариантов на данные, зашифрованные с применением медового шифрования для демонстрации преимуществ медового шифрования;

4) проверяет работу библиотеки в фиксированных обычных ситуациях;

5) проверяет работу библиотеки в особых ситуациях — когда возможны все значения исходных данных (group_size = 256) и когда возможно только одно значение исходных данных (group_size = 1);

6) проверяет работу библиотеки в случае неправильных данных на входах процедур;

7) собирает статистические данные по результатам пунктов 1 и 3 для оценки эффективности разработанных процедур.

Для использования медового шифрования требуется использование вполне определённых криптографических примитивов: авторы оригинальной работы [1] рекомендуют использовать блочный шифр в режимах CBC (режим сцепления блоков шифротекста) или CTR (режим счётчика) без дополнений. В данной работе для шифрования использовался блочный шифр AES-256 в режиме CBC без дополнений. Этот шифр является действующим американским стандартом шифрования [8], широко применяющимся во всём мире. Длина ключа выбрана равной 256 битам, поскольку это минимум, обеспечивающий защиту от атак на квантовом компьютере, который может стать реальностью в ближайшие десятилетия [3].

Текущие исходные коды данной программы опубликованы на хостинге GitHub [9] под лицензией BSD из 2-х пунктов [2]. Открытая публикация программы в виде исходных кодов важна для того, чтобы другие разработчики могли как-либо использовать её в составе своих проектов. Именно лицензия BSD из 2-х пунктов была выбрана среди множества лицензий для проектов с открытым исходным кодом за её понятность и за возможность использования кода в проприетарном программном обеспечении, что представляется автору очень важным для подобных проектов. Для того, чтобы исходными кодами программы могли пользоваться люди по всему миру, все файлы с исходными кодами (включая комментарии к ним) были написаны с ориентацией на англоговорящего читателя.

Заключение

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

Литература

1. A. Juels, T. Ristenpart. Honey Encryption: Security Beyond the Brute-Force Bound. Advances in Cryptology - EUROCRYPT 2014, pp. 293-310, Springer-Verlag Berlin Heidelberg, 2014.
https://eprint.iacr.org/2014/155.pdf

2. Лицензия BSD

https://ru.wikipedia.org/wiki/Лицензия_BSD

3. Daniel J. Bernstein. Introduction to post-quantum cryptography. Post-Quantum Cryptography, pp. 1-14, Springer-Verlag Berlin Heidelberg, 2009.

http://pqcrypto.org/www.springer.com/cda/content/document/cda_downloaddocument/9783540887010-c1.pdf

4. Атака методом «грубой силы»

https://ru.wikipedia.org/wiki/Полный_перебор

5. T. Ristenpart. New Encryption Primitives for Uncertain Times. Презентация для конференции FCE 2014.

http://fse2014.isg.rhul.ac.uk/slides/slides-10_2.pdf

6. A. Juels, T. Ristenpart. Honey Encryption: Security Beyond the Brute-Force Bound. Презентация для конференции Eurocrypt 2014.

http://ec14.compute.dtu.dk/talks/19.pdf

7. Медовое шифрование обманывает хакеров ложной дешифровкой

https://threatpost.ru/medovoe-shifrovanie-obmany-vaet-hakerov-lozhnoj-deshifrovkoj