BC/NW 2016 № 1 (28):11.2
ИССЛЕДОВАНИЕ СОВМЕСТНОГО ПРИМЕНЕНИЯ МЕДОВОГО ШИФРОВАНИЯ И ШИФРОВАНИЯ RSA
Зубов И.А.
Введение
В начале 2014 года американские учёные Ари Джулс и Томас Ристенпарт выдвинули новую идею в криптографии, которая потенциально может иметь заметное практическое приложение. Эта идея носит название «медовое шифрование» («honey encryption») и заключается в таком шифровании, которое при неверно введённом ключе выдаёт ложные, но правдоподобно выглядящие данные. В своей работе [1] они приводят леммы и теоремы, доказывающие, что предлагаемая ими идея с математической точки зрения вполне имеет право на жизнь. Для быстрого знакомства с работой учёных хорошо подходит их презентация для конференции Eurocrypt 2014 [6]. На русском языке об этой интересной концепции писал портал ThreatPost [3].
При распространённом сегодня подходе полный перебор всех ключей шифрования обязательно даёт результат. Даже если не используются имитовставки, электронные подписи или дополнения при шифровании, говорящие о правильности или неправильности расшифровки, при использовании неверного ключа осмысленные данные расшифровываются в последовательность псевдослучайных чисел, часто легко отличимых от реальных данных компьютером или человеком. Длина ключей многих алгоритмов такова, что провести полный перебор просто невозможно, однако нередко из-за проблем криптографического алгоритма или его реализации можно заменить полный перебор сокращённым, сильно ускорив процесс [4]. Сокращённый перебор по словарю показан на рис. 1.
Рис. 1. Процесс подбора пароля путём перебора по словарю (на основе [5])
В своей статье учёные предлагают подход, при котором не только частичный, но даже полный перебор всех возможных ключей может оказаться бесполезным за счёт хитрого трюка: при использовании любого ключа (правильного или неправильного) для расшифрования данных всегда получается правдоподобный результат, и из-за этого крайне сложно отличить правильно расшифрованные данные от подложных (рис. 2). Это может быть очень полезно в системах, где трудно обеспечить стойкое шифрование, например при генерации ключа шифрования из пароля, а также во многих других приложениях.
Рис. 2. Схема медового шифрования (на основе [5])
Как и любая другая концепция, медовое шифрование опирается на некоторые предположения. В данном случае важным предположением является то, что при расшифровке шифротекста неверным ключом мы получаем псевдослучайные данные, и именно из-за этого мы можем отсечь множество результатов дешифрования как неправдоподобные. В разделе 2 данной работы это предположение будет подвергнуто проверке при использовании алгоритма шифрования RSA [2]. Помимо этого, в разделе 1 будут рассмотрены вопросы совместного применения медового шифрования и алгоритма RSA в целом, без привязки к конкретным типам данных.
1. О совместном применении медового шифрования и шифрования RSA
В оригинальной работе о медовом шифровании [1] сказано, что совместно с медовым шифрованием могут использоваться не все криптографические примитивы. Во-первых, мы разумеется не должны использовать имитовставки, электронные подписи или дополнения при шифровании, говорящие о правильности или неправильности расшифровки, а во-вторых, используемый алгоритм шифрования должен удовлетворять свойству «шифрование равномерно распределённых открытых текстов даёт равномерно распределённые шифротексты». Группа студентов Массачусетского технологического института в своей статье [7] утверждает, что данное условие выполняется для асимметричного алгоритма шифирования RSA. Это известный, хорошо исследованный и стандартизированный асимметричный алгоритм, широко используемый на протяжении нескольких десятилетий.
Для работы с этим алгоритмом будет разумнее всего применить самый популярный продукт в своей области – мощнейшую свободную библиотеку OpenSSL [8]. При использовании этой библиотеки перед нами встаёт вопрос выбора длины ключа. Длина ключа в 2048 бит сегодня считается относительно безопасной [9] и активно используется при шифровании в протоколе TLS, защищающем большинство зашифрованных соединений в сети Интернет.
Алгоритм RSA обычно не используется для шифрования больших пакетов данных – гораздо более эффективной во всех отношениях (скорость, длина шифротекста, безопасность) является гибридная криптосистема, в которой асимметричный алгоритм (например, RSA) используется для шифрования ключа симметричного алгоритма (например, AES), который и используется собственно для шифрования данных. Алгоритм шифрования RSA накладывает жёсткие ограничения на размер открытого текста, который должен быть равен размеру ключа, то есть в случае 2048-битного ключа открытый текст тоже должен быть равен 2048 битам (256 байт). При этом открытый текст, представленный как число, должен быть меньше модуля n = p*q, длина которого (модуля) в битах равна длине ключа, что ещё сильнее сужает пространство открытых текстов [10]. Например, открытый текст, состоящий из 2048 единичных бит, не может быть зашифрован без дополнительных ухищрений при использовании 2048-битного ключа. Нам придётся учесть всё это.
Библиотека OpenSSL предоставляет возможность использования криптографического дополнения при шифровании, что позволяет усилить безопасность алгоритма, а также шифровать данные длиной меньше, чем размер ключа [11]. Более конкретно, OpenSSL позволяет использовать дополнение в соответствии со стандартом PKCS #1 v2.0 (алгоритм EME-OAEP), в соответствии со стандартом PKCS #1 v1.5, модификацию последнего для протокола SSL версий 2 и 3, а также не использовать дополнение вообще [12]. Использование дополнения здесь является не просто правилом хорошего тона, но насущной необходимостью. Перечисленные выше три вида дополнений имеют строгую структуру, которая нарушит свойство «медовости» шифрования — если строго заданные в стандарте байты дополнения будут неверными, то злоумышленник поймёт, что текущий результат дешифрования недостоверен. Хорошим решением было бы ввести своё дополнение, максимально подходящее для задачи медового шифрования.
Каким было бы хорошее дополнение в данном случае? Во-первых, хотелось бы избавиться от ситуации, когда число, получающееся из открытого текста, будет больше модуля n. Поскольку модуль n скорее всего имеет единичные старшие биты, которые хранятся в первом байте, то для того, чтобы открытый текст заведомо был меньше модуля, нужно дополнить его слева нулевыми битами. В случае использования OAEP, например, первый байт дополнения равен 0 (0x00), и мы поступим так же. Для нас введение такого байта является вынужденной необходимостью, поскольку из-за него в среднем лишь одна попытка дешифрования из 2^8 = 256 даст правдоподобный результат, но всё же стоит сделать это.
Во-вторых, использование RSA без дополнения не является безопасным, в частности из-за возможной атаки на основе адаптивно подобранного шифротекста [13]. После обнуления первого байта мы могли бы осуществить дополнение псевдослучайными байтами со второго байта, причём для борьбы с атакой дней рождений число байт должно быть не менее 32 (таким образом, получаем 256 псевдослучайных бит). Длину реальных данных придётся хранить в открытом или зашифрованном виде в другом месте, поскольку хранение его непосредственно в дополнении поможет злоумышленнику отделить правильные попытки расшифровки от неправильных. Итак, минимум 33 из 256 байт нам придётся отвести под дополнение, тогда для осмысленных данных нам остаётся лишь не более 223. Если нам нужно зашифровать меньшее число байт, например, 200, то мы будем использовать 32 + 23 = 55 псевдослучайных байт вместо 32.
Возможно, высказанные выше предположения о том, что нам нужно обнулить не менее 8 первых бит открытого текста, а затем заполнить не менее 32 байт псевдослучайными данными, были слишком параноидальными. В этом случае можно повысить эффективность нашего дополнения — усложнить злоумышленнику задачу отделения реальных данных от ложных и/или шифровать больше полезных данных в одном шифротексте.
Итак, алгоритм RSA допускает совместно с ним использование медового шифрования, однако его применение сильно затруднено и ограничено, вследствие чего гораздо лучшим решением было бы использование гибридной криптосистемы. При внедрении медового шифрования перед шифрованием данных симметричным алгоритмом и после расшифровки данных им же мы получим улучшение удобства использования, усиление безопасности и увеличение скорости, а сам ключ симметричного алгоритма можно без особых проблем зашифровать с помощью того же RSA.
2. Проверка утверждения о результатах расшифровки
Итак, покажем вычислительно, что при расшифровке шифротекста неверным ключом в алгоритме RSA мы получаем псевдослучайные данные, и именно из-за этого мы можем отсечь множество результатов расшифрования как неправдоподобные. Для решения этой задачи была написана программа [18].
Сначала эта программа составляет открытый текст для шифрования. Он состоит из дополнения (обнулённый первый байт, затем 32 псевдослучайных байта) и собственно данных (223 оставшихся байта), его общая длина таким образом составляет 256 байтов. В байтах данных для чистоты эксперимента будут каждый раз лишь одно повторяющееся однобайтовое значение, причём это будут крайние и средние значения из возможного диапазона (0, 1, 50, 100, 150, 200, 255). Именно в случае шифрования этих сильно неравномерных открытых текстов наиболее вероятно проявится неравномерное распределение результатов дешифрования, если оно действительно имеет место быть. Итак, полученное сообщение шифруется только что сгенерированным открытым ключом, затем расшифровывается соответстующим ему закрытым ключом, чтобы подтвердить правильность расшифровки.
После этого мы совершаем атаку на зашифрованный алгоритм, пытаясь расшифровать шифротекст свежесгенерированными секретными ключами. Программная реализация алгоритма RSA является весьма медленной, поскольку RSA – асимметричный алгоритм, так что при моделировании атаки нам придётся ограничиться 256 попытками подобрать ключ (сложность атаки – 2^8), а также не брать в расчёт значение первого байта (как уже упоминалось, если его значение не нулевое, то результат расшифровки уже неправдоподобен, но мы игнорируем это). В случае, если получившийся расшифрованный текст будет больше модуля (что невозможно при правильной расшифровке), мы подбираем ключ для этой итерации заново. После каждого расшифрования, кроме случая “расшифрованный текст больше модуля“, мы будем собирать статистику по частоте встречаемости различных байт в расшифрованных данных, то есть в последних 223 байтах (дополнение нас не интересует). Для проверки соответствия получившегося и равномерного распределения данных (именно его дали бы идеальные случайные данные) мы будем использовать функцию CHITEST редакторов таблиц Microsoft Excel / OpenOffice alc / LibreOffice Calc, осуществляющую статистическую проверку гипотезы по критерию хи-квадрат [14, 15].
Результаты несколько разнятся от опыта к опыту в силу случайности генерации 32 байт из дополнения, ключа шифрования и ключей дешифрования, но всё же качественно, по своей сути они остаются прежними и при повторении опытов. Степень сходства между расшифрованными и псевдослучайными данными при шифровании чисел 0 – 0,24 (в другом тесте – 0,02), чисел 1 – 0,70, чисел 50 – 0,80 (в другом тесте – 0,11), чисел 100 – 0,58, чисел 150 – 0,79, чисел 200 – 0,64, чисел 255 – 0,73 (в другом тесте – 0,10).
Возьмём, пожалуй, худший случай из перечисленных выше – шифрование чисел 0, и проведём для него более длительный опыт – будем пытаться подобрать ключ 8192 раза (в 32 раза больше, чем ранее). Получим, что степень сходства по критерию хи-квадрат равна 0,61, что является ещё одним подтверждением нашей гипотезы.
Собрав в этом же опыте отдельную статистику по первым байтам сообщений (в исходном сообщении на этом месте стоял обнулённый байт дополнения), получим очень близкую к нулю степень (9E-320) сходства реального и равномерного распределений, показывающую их сильное отличие. Пристальный взгляд на результаты говорит сам за себя (рис. 3). Первый байт не принял значения в диапазоне [205; 255] ни разу за 8192 итерации, то есть его значение жёстко ограничено сверху. По-видимому, подобное ограничение является неотъемлемым свойством алгоритма RSA. Первый байт принял значение 0 всего в 45 из 8192 итераций, то есть злоумышленник, знающий об используемом дополнении, в нашем опыте cмог бы отсечь (8192-45) / 8192 * 100% ~ 99,45% полученных результатов как недостоверные уже на этом шаге. Однако, как мы уже упоминали, в нашей работе мы не учитываем это обстоятельство при сборе статистики. Стоит упомянуть, что в данном опыте мы получаем всего 8192 различных первых байт, и при равномерном распределении каждому возможному значению от 0 до 255 соответствует лишь 32 вхождения, что является весьма небольшим числом для статистики. Увы, проводить более длительные (и, соотвественно, более достоверные) опыты для нас затруднительно.
Рис. 3. Распределение первого байта сообщения. Синим показано реальное распределение, красным – равномерное
Подводя итог, если бы у нас была возможность проводить большее количество объёмных опытов за разумные промежутки времени, то возможно мы получили бы большее соответствие. С другой стороны, опыт показывает, что некоторые ключи шифрования вызывают значительно более частое появление ошибки “открытый текст больше модуля” при дешифровании, чем другие: эта ошибка либо не появляется в ходе запуска программы вообще, либо появляется редко, либо появляется часто. Есть предположение, это тоже может влиять на статистические свойства результатов дешифрования.
Таким образом, даже с учётом заметного разброса значений в целом предположение о псевдослучайности расшифрованных неверным ключом данных является в целом верным, что подтверждают диаграммы, построенные на основе полученных данных. Распределение не является строго равномерным, но близко к нему.
3. Наброски для математического рассмотрения вопроса
Разумеется, идеальным было бы доказать равномерность распределения при расшифровке неверным ключом не только вычислительно, но и строго математически. К сожалению, это является очень сложным вопросом, выходящим за компетенцию автора данной работы. Подтверждением сложности является, например, статья французских учёных [16], которые рассматривают значительно более узкие вопросы, и тем не менее сложность оказывается очень высокой.
Тем не менее, хотелось бы представить некоторые наброски, могущие быть полезными для будущих работ по этой теме. Была написана программа [18], с помощью которой можно сделать некоторые выводы о распределении результатов выражения x^y mod p, где y>=2, p и y фиксированы в каждом опыте. Дело в том, что если результаты этого выражения при описанных выше условиях не повторяются для всех x из отрезка [0; p-1], то распределение результатов будет равномерным; напротив, хотя бы одно повторение сделает распределение неравномерным.
Проведём следующий эксперимент: p находится в промежутке [2; 100]; y находится в промежутке [2; 40]; x находится в промежутке [0; p-1], пробегая в каждом опыте все свои возможные значения. Получим следующие результаты:
1. Если p = 2, то при любой степени y из интервала [1; 40] получаем равномерное распределение. Всё просто: 0^y mod 2 = 0 при любой степени y>=1, 1^y mod 2 = 1 при любой степени y>=1, так что равномерное распределение здесь будет при любых y>=1.
2. Если p = 3, то при любой нечётной степени y из интервала [1; 40] получаем равномерное распределение. Это объясняется тем, что 0^y mod 3 = 0 при любой степени y>=1, 1^y mod 3 = 1 при любой степени y>=1, а вот 2^y mod 3 = 2 только при нечётных степенях y, так что равномерное распределение здесь будет при любых нечётных y>=1.
3. Если p принимает значение из множества {4, 8, 9, 12, 16, 18, 20, 24, 25, 27, 28, 32, 36, 40, 44, 45, 48, 49, 50, 52, 54, 56, 60, 63, 64, 68, 72, 75, 76, 80, 81, 84, 88, 90, 92, 96, 98, 99, 100}, то даже при любом y из отрезка [2; 500] равномерное распределение не встречается ни разу. Легко заметить закономерность – все эти числа кратны как минимум одному из следующих чисел: 4 (2^2), 9 (3^2), 25 (5^2) и 49 (7^2), то есть квадратам простых чисел. Судя по всему, эта закономерность соблюдается и далее.
4. Если p не удовлетворяет описанному выше условию кратности квадратам простых чисел, то для него обязательно существует множество нечётных значений y, при которых распределение будет равномерным. Например, если p = 29, то в нашем опыте y может принадлежать множеству {1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39}. Здесь можно увидеть закономерность, если мы найдём разности между соседними членами: 3-1 = 2, 5-3 = 2, 9-5 = 4, 11-9 = 2, 13-11 = 2, 15-13 = 2, 17-15 = 2, 19-17 = 2, 23-19 = 4, 25-23 = 2, 27-25 = 2, 29-27 = 2, 31-29 = 2, 33-31 = 2, 37-33 = 4, 39-37 = 2. Сначала разница два раза равна 2, затем равна 4; затем пять раз равна 2, затем равна 4; затем пять раз равна 2, затем равна 4. Аналогичным образом ситуация обстоит и с другими подходящими p – для них y также может принадлежать множеству значений, которые связаны между собой каким-то законом. Судя по всему, упомянутые выше закономерности соблюдается и далее.
В алгоритме RSA при расшифровке роль модуля p из построений выше играет число n = p*q, где p и q – простые числа; роль степени y играет секретная экспонента d, а роль x играет шифротекст x из интервала [0; n-1]. В стандарте RSA [2] сказано, что p !=q: «In a valid RSA public key, the RSA modulus n is a product of u distinct odd primes». Отсюда прямо вытекает, что мы имеем дело с ситуацией 4, рассмотренной выше (раз модуль равен произведению различных простых чисел, то он не может быть кратен квадрату какого-либо простого числа). Поскольку d = e^(-1) mod ф(n) = e^(-1) mod (p-1)*(q-1), то скорее всего d может быть любым числом (вообще-то это требует дополнительного исследования!), и соответственно распределение результатов расшифровки одним ключом различных сообщений может быть как равномерным, так и неравномерным (соответственно в общем случае оно будет неравномерным).
Нас, однако, куда больше интересует распределение результатов расшифровки одного сообщения различными ключами: хотелось бы рассмотреть ситуацию, когда в выражении x^y mod p значение y меняется в диапазоне [0; p-1], а x и p остаются постоянными на протяжении каждого опыта. Переработав для этой цели ранее описанную программу [18] и рассматривая числа в отрезке [2; 50], мы обнаружим, что в ряде случаев (но далеко не всегда!) распределение действительно будет очень близким к равномерному. В тех случаях, когда p является простым числом (в наших опытах это были числа 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47), при некоторых значениях x результат выражения будет равномерно распределён между значениями [1; p-1] при степенях y в интервале [0; p-2]. Другими словами, в этих случаях при степенях y в интервале [0; p-2] результат никогда не принимает нулевого значения, зато принимает все другие возможные значения лишь однажды, так что распределение будет практически равномерным. Закономерности в подходящих значениях x тут найти не удалось: например, при p = 23 подходящие x принадлежат множеству {5, 7, 10, 11, 14, 15, 17, 19, 20, 21}. Можно лишь сказать, что их сравнительно немало — в нашем эксперименте от четверти до половины всех возможных значений x. Стоит отметить, что не стоит считать такие числа x первообразными корнями по модулю p [17], поскольку в общем случае они ими не являются.
Однако в алгоритме RSA в качестве модулей используются полупростые числа (произведения двух простых чисел), а не простые, так что судя по нашим опытам такие благоприятные ситуации возникать не будут, а значит строго говоря распределение нельзя будет назвать равномерным.
Заключение
В данной статье были рассмотрены вопросы применимости медового шифрования к алгоритму RSA в целом, без привязки к конкретным типам данных, а также подвергнуто проверке предположение, что при использовании алгоритма шифрования RSA при расшифровке шифротекста неверным ключом мы получаем псевдослучайные данные.
Был получен и обоснован вывод о том, что алгоритм RSA допускает совместно с ним использование медового шифрования, однако его применение сильно затруднено и ограничено, вследствие чего гораздо лучшим решением было бы использование гибридной криптосистемы. При внедрении медового шифрования перед шифрованием данных симметричным алгоритмом и после расшифровки данных им же мы получим улучшение удобства использования, усиление безопасности и увеличение скорости, а сам ключ симметричного алгоритма можно без особых проблем зашифровать с помощью того же RSA.
Предположение о равномерном распределении результатов при дешифровании неверным ключом подтвердилось на практике с некоторой точностью, но теоретического доказательства привести не удалось.
Литература
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. PKCS #1 v2.2: RSA Cryptography Standard by RSA Laboratories. October 27, 2012.
https://www.emc.com/collateral/white-papers/h11300-pkcs-1v2-2-rsa-cryptography-standard-wp.pdf
3. Медовое шифрование обманывает хакеров ложной дешифровкой
https://threatpost.ru/medovoe-shifrovanie-obmany-vaet-hakerov-lozhnoj-deshifrovkoj
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. N. Tyagi, J. Wang, K. Wen, D. Zuo. Honey Encryption Applications: Implementation of an encryption scheme resilient to brute-force attacks.
http://www.mit.edu/~ntyagi/papers/honey-encryption-cc.pdf
8. Официальный сайт проекта OpenSSL https://openssl.org
9. Key size — Википедия https://en.wikipedia.org/wiki/Key_size
10. RSA Encryption Problem [Size of payload data] http://stackoverflow.com/questions/5866129/rsa-encryption-problem-size-of-payload-data
11. Дополнение (криптография) — Википедия https://ru.wikipedia.org/wiki/Дополнение_(криптография)
12. RSA_public_encrypt — справка проекта OpenSSL https://www.openssl.org/docs/manmaster/crypto/RSA_public_encrypt.html
13. RSA (cryptosystem) — Википедия https://en.wikipedia.org/wiki/RSA_(cryptosystem)
14. Функция ХИ2ТЕСТ/CHITEST https://support.office.com/ru-ru/article/ХИ2ТЕСТ-функция-ХИ2ТЕСТ-981ff871-b694-4134-848e-38ec704577ac15. Критерий хи-квадрат — Википедия https://ru.wikipedia.org/wiki/Критерий_хи-квадрат
16. P.-Al. Fouque, J.-C. Zapalowicz. Statistical Properties of Short RSA Distribution and Their Cryptographic Applications. Computing and Combinatorics, Aug 2014, Atlanta, United States. Springer, LNCS 8591, pp.525 - 536, 2014, COCOON 2014.
https://hal.inria.fr/hal-01094059/file/micali.pdf
17. Первообразный корень (теория чисел) — Википедия
https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел)
18. Репозиторий honeyrsa на хостинге GitHub