ПСП. ПСП papers11. Классификация генераторов псевдослучайных чисел, ориентированных на использование в задачах защиты информации
 Скачать 0.55 Mb.
|
Классификация генераторов псевдослучайных чисел, ориентированных на использование в задачах защиты информации М.А. Иванов, А.А. Скитев, А.В. Стариковский 2016 Abstract. Появление 2D и 3D стохастических преобразований требует пересмотреть существующую классификацию, как минимум, в части блочных (block type) генераторов псевдослучайных чисел (PRNG). По- мимо традиционной архитектуры Сеть Фейстеля необходимо учитывать архитектуры Квадрат и Куб, а также гибридную архитектуру, предполагающую использование Сети Фейстеля, раундовая функция которой реализо- вана по схеме 2D или 3D. Кроме того, появилось инновационное решение по принципу построения нелинейной функции PRNG, суть которого – использование последовательной и параллельной композиции раундовых пре- образований. В известной классификации также отсутствует деление генераторов по типу доступа. Такое свой- ство PRNG как произвольный доступ к любому элементу последовательности (иначе говоря, возможность вы- числения произвольного ее элемента) позволяет распараллелить процесс генерации, повысив тем самым быст- родействие блочных PRNG. Keywords: stochastic transformation, pseudo-random number generator, 2D transformation, 3D transfor- mation, taxonomy of PRNG 1. INTRODUCTION Жизнь современного общества немыслима без повсеместного использования ком- пьютерных систем (КС), связанных с вводом, хранением, обработкой и выводом инфор- мации, а также управлением сложными техническими объектами. Всеобщая компьютери- зация, помимо очевидных выгод, несет с собой и многочисленные проблемы, наиболее сложной из которых является проблема информационной безопасности. Высочайшая степень автоматизации, к которой стремится человечество и широкое внедрение КС, делают их чрезвычайно уязвимыми по отношению к деструктивным воздействиям, ставят современное общество в зависимость от степени безопасности используемых IT-технологий. Важнейшей характеристикой любой КС, независимо от ее сложности и назначения, стала безопасность обрабатываемой в ней информации. Особенно важны вопросы защиты информации (ЗИ) в критически важных КС. Кибербезопасность (КБ) давно стала самостоятельным направлением исследований и разработок. Однако, несмотря на это, проблем не становится меньше. Это объясняется появ- лением всё новых компьютерных технологий (суперкомпьютерных, киберфизических, RFID, мобильных и пр.), которые не только создают новые проблемы КБ, но и представляют, каза- лось бы, уже решенные вопросы совершенно в новом ракурсе. Кроме того, появление новых компьютерных технологий, новых математических методов дают в руки нарушителей и соз- дателей разрушающих программных воздействий (Malicious Software) все новые и новые возможности [1]. Анализ угроз КБ, тенденций развития компьютерных технологий позволяет сделать однозначный вывод о постоянно возрастающей роли стохастических методов защиты ин- формации. Стохастическими методами принято называть методы, прямо или косвенно осно- ванных на использовании непредсказуемых (unpredictable) генераторов псевдослучайных чи- сел (Pseudo-Random Number Generators, PRNG). В качестве примера универсального стохас- тического метода ЗИ можно упомянуть метод внесения неопределенности в работу средств и объектов защиты. С использованием PRNG успешно решаются все задачи ЗИ. Так, в некото- рых случаях стохастические методы – это единственно возможный механизм защиты ин- формации от активного противника. Термин «стохастический» применительно к задачам ЗИ впервые, по-видимому, стал применяться С.А. Осмоловским при построении кодов, обнаруживающих и исправляющих ошибки, возникающие при передаче данных по каналам связи [2, 3]. Предложенные им сто- хастические коды обладают уникальными свойствами, среди которых стоит выделить два: способность обеспечивать наперед заданную вероятность правильного приема информации и возможность решения помимо задачи обеспечения помехоустойчивости и двух других не менее важных задач ЗИ: обеспечения конфиденциальности и целостности передаваемой ин- формации. Тенденцией последних лет стало массовое появление 2D и 3D стохастических пре- образований, что подтверждает актуальность выбранной темы исследований. Все без ис- ключения появившиеся в ХХI веке государственные стандарты России и США, специфи- цируют алгоритмы, основанные на 2D и 3D преобразованиях (алгоритмы AES, Kuznechik, Keccak и Stribog), что позволяет сделать очевидный вывод о необходимости уточнения су- ществующей классификации PRNG, ориентированных на решение задач ЗИ. 2. TAXONOMY OF PRNG К PRNG, ориентированным на решение задач ЗИ, предъявляются наиболее жесткие требования, в первую очередь к непредсказуемости и статистической безопасности форми- руемых псевдослучайных последовательностей (ПСП, PRS – Pseudo-Random Sequences). Анализ таких PRNG позволяет сделать два основных вывода [4]: существует трудно разрешимое противоречие между качеством формируемых RNS, с одной стороны, и эффективностью программной и аппаратной реализации генераторов, с другой стороны; непредсказуемость PRNG основывается на недоказуемых предположениях о том, что у аналитика не хватит ресурсов (вычислительных, временных или стоимостных) для того, чтобы обратить (инвертировать) нелинейную функцию обратной связи или нелинейную функцию выхода PRNG. В [4] дана классификация PRNG, ориентированных на решение задач ЗИ. Генераторы классифицируются по следующим признакам: типу используемого нелинейного стохастического преобразования; структуре; наличию или отсутствию внешних источников случайности; принципу управления синхронизацией; принципу получения последовательности; количеству каскадов; принципу использования S- и R-блоков. Можно выделить два подхода при использовании в составе PRNG нелинейных преобразований: это использование нелинейной функции непосредственно в цепи обратной связи (рис. 1,а) и двухступенчатая структура (рис. 1,б), в которой задача первой ступени (по сути счетчика) заключается всего лишь в обеспечении максимально большого периода при данном количестве N элементов памяти генератора. Первая схема носит название OFB (Out- put FeedBack – обратная связь по выходу), вторая – СTR (Counter Mode) [4]. Обозначения на рис. 1: Q – элементы памяти PRNG, 0 Q – начальное состояние PRNG, t Q и 1 t Q – состояние генератора в моменты времени t и (t + 1) соответственно, F fb , F out – линейные или нелинейные функции обратной связи и выхода PRNG, F k – нелинейная функция, результат работы которой зависит от секретного параметра k (ключа), i – элемент выходной последовательности, t – значение выхода в момент времени t, F out – нелинейная функция выхода генератора. Уравнения работы генераторов, функционирующих в режимах OFB и CTR имеют соответственно вид (1.1) и (1.2) [4]. ; , t fb t t t Q F Q Q γ 1 (1.1) , t fb t t out t Q F Q Q F γ 1 (1.2) Необходимые свойства используемой нелинейной функции иллюстрируют рис. 2, где Δ – входной дифференциал, содержащий «1» в разрядах, соответствующих измененным битам, Δ – преобразованный (выходной) дифференциал. При случайном выборе ключа k при любых изменениях на входе значения преобразованных дифференциалов Δ равномерно распределены на интервале [1; 2 n – 1], где n – разрядность выходного слова (рис. 2,а). Аналогично, при случайном выборе входного слова x при любых изменениях ключа значения преобразованных дифференциалов Δ также равномерно распределены на интервале [1; 2 n – 1] (рис. 2,б). Такие свойства автоматически имеют место при использовании в роли F k функции зашифрования качественного блочного шифра, обеспечивающей рассеивание и перемешивание информации [4]. а S 0 F k F k Q k i S 0 F fb Q i k F out S 0 F fb Q i б в Рисунок 1 – Варианты построения PRNG: а – с нелинейной внутренней логикой (режим OFB), б – с нелинейной внешней логикой (Counter Mode), в – общая схема. F k y = F k (x) k F k k x F k y' = F k (x') k x' = x Δ Δ = x x' Δ ' = y y' F k y = F k (x) k F k x F k y' = F k' (x) x k' = k Δ Δ = k k' Δ ' = y y' x б а Рисунок 2 – Свойства нелинейной функции PRNG: а и б – входной и преобразованный (выходной) дифференциалы соответственно при изменении на входе и при изменении ключа k. Эффективность стохастических методов ЗИ определяется в первую очеред ь качеством используемых PRNG. Сформулируем, что входит в понятие «качественный PRNG». КачественныйPRNG, ориентированный на использование в задачах ЗИ, должен удовлетворять следующим требованиям [4]: непредсказуемость (Unpredictability); хорошие статистические свойства, PRS по своим статистическим свойствам не должна отличаться от истинно случайной последовательности; большой период формируемой последовательности, учитывая, что при преобразовании больших массивов данных каждому элементу входной последовательности необходимо ставить в соответствие свой элемент PRS; эффективная программная и аппаратная реализация. Непредсказуемость PRNG чрезвычайно сложно оценить количественно. Чаще всего обоснования стойкости нелинейной функции F k PRNG сводятся к недоказуемым предположениям о том, что у аналитика не хватит ресурсов (вычислительных, временных или стоимостных) для того, чтобы, при неизвестном k обратить (инвертировать) эту функцию. Теория сложности вычислений, к сожалению, не может дать строгую нижнюю границу трудоемкости решения подобных задач. В рамках другого подхода к построению качественного PRNG предлагается свести задачу построения непредсказуемого генератора к задаче построения статистически безопасного генератора [4]. Статистически безопасный генератор PRS должен удовлетворять следующим требованиям: ни один статистический тест не отличает эту последовательность от истинно случайной; нелинейное стохастическое преобразование F k , зависящее от секретной информации (ключа k), используемое для построения генератора, обладает свойствами рассеивания и перемешивания – все выходные (преобразованные) дифференциалы Δ возможны и равновероятны независимо от входного вектора Δ; при инициализации случайными значениями генератор порождает статистически независимые PRS. Блочные PRNG, нелинейные функции которых строятся по итерационному принципу, следует признать лучшими по совокупности двух критериев – непредсказуемости и быстродействию. Появление 2D и 3D стохастических преобразований требует пересмотреть существующую классификацию, как минимум, в части блочных PRNG. Помимо традицион- ной архитектуры «Сеть Фейстеля» необходимо учитывать архитектуру «Квадрат» (алгорит- мы Square, Rijndael, W, Кузнечик) [5-8] и «Куб» (алгоритмы Gate, DOZEN, 3D) [9-11], а так- же гибридную архитектуру, предполагающую использование «Сети Фейстеля», раундовая функция которой реализована по схеме 2D или 3D (алгоритм SHAvite-3) [4, 12]. Достоинст- вом 2D и 3D преобразований является высокая степень параллелизма на уровне элементар- ных операций. Кроме того, появилось инновационное решение по принципу построения не- линейной функции PRNG, суть которого – использование последовательной и параллельной композиции раундовых преобразований [13, 14]. На рис. 3 показан 2D алгоритм подобного типа. Основная идея данной конструкции – построение последовательностной машины, ко- личество элементов памяти которой превышает разрядность входной памяти. Подобный подход к построению блочных итеративных шифров ранее не применялся, его использова- ние при программной реализации криптографических преобразований стало возможным в связи появлением гибридных суперкомпьютерных технологий. В результате стало возмож- ным в пределах раунда параллельно (иначе говоря, без ущерба для быстродействия) выпол- нять различные траектории сложных преобразований, а затем на выходе осуществлять па- раллельную композицию полученных результатов. В результате задача инвертирования функции шифрования становится вычислительно неразрешимой при меньшем числе раундов преобразования. Внутри каждого раунда по сути происходит формирование N копий входного блока, каждая копия С ij подвергается стохастическому преобразованию С ij := E ij (С ij , K ij ), где K ij – ра- ундовые подключи i-го раунда, j = 1, 2, …, N. Преобразованные значения С ij поступают на входы комбинационной схемы F i , функцией которой является параллельная композиция раз- личных траекторий раундовых преобразований, результат действия комбинационной схемы С:= F i (С i1 , С i2 , …, С iN ) объявляется результатом i-го раунда. На рис. 3,б показан простейший случай, когда параллельная композиция осуществляется с использованием операции пораз- рядного сложения по модулю два. RF n K 1 K i1 K i2 K iN C i1 C i2 C iN F i Output Input K n K i RF i RF 1 а AddThreadKey AddThreadKey SubBytes SubBytes MixState MixState M2 Input RF 1 K 1N K 11 RF n RF 2 Output K 2N K nN K 21 K n1 С 1N С 11 б Рисунок 3 – Использование параллельной и последовательной композиции при построении итеративного стохастического преобразования данных: а – общая схема; б – пример построения на основе 2D преобразования. В известной классификации отсутствует деление генераторов по типу доступа. Свой- ство произвольного доступа к любому элементу PRS (иначе говоря, возможность вычисле- ния произвольного элемента PRS) позволяет распараллелить процесс вычисления PRS, по- высив тем самым быстродействие блочных PRNG. На рис. 4 показана уточненная классифи- кация PRNG, ориентированных не решение задач ЗИ. Появление названий хеш-функций на рисунке 4 объясняется просто: процесс хеширования можно рассматривать как наложение последовательности с выхода PRNG на входную последовательность M, как показано на рис. 5, где Q – элементы памяти PRNG, N – разрядность состояния PRNG, h 0 – начальное состоя- ние PRNG, n – разрядность блоков данных, m – разрядность хеш-образа h(M), F – функция наложения, например, bitwise XOR. На рис. 6 показаны две схемы PRNG с произвольным доступом: двухступенчатая (Counter Mode) и Sponge [15]. По типу нелинейной функции PRNG Криптографические Блочные На основе односторонних функций Поточные Архитектура "Сеть Фейстеля" Архитектура 2D Архитектура 3D Использование последовательной композиции раундовых преобразований Использование последовательной и параллельной композиции раундовых преобразований По типу доступа С последовательным доступом С произвольным доступом Block type PRNG Sponge, Block type two-stage PRNG (Counter Mode) Stochastic transformations GATE, DOZEN, DOZEN+, RDOZEN+ Block cipher 3D Hash function Keccak Space PRNG, Block ciphers Square, Rijndael, W, Kuznechik, ... Hash functions Wirlpool, Echo, Grostl, Stribog, ... Stochastic Transformation 3DOZEN+ Гибридная архитектура Hash function SHAvite-3 Некриптографические Рисунок 4 – Уточненная классификация PRNG n n N n Feedback Function Q M h(M) m F PRNG h 0 Рисунок 5 – Хеширование как наложение PRS на входную последовательность M. Key F 0 Element PRS # i F F IV i i E Element PRS # i Key a b Counter or LFSR Counter or LFSR Рисунок 6 – PRNG с произвольным доступом: а – двухступенчатая схема; б – генератор Sponge. E, F – нелинейные стохастические преобразования, соответственно зависящие и независящие от ключа. 3. CONCLUSION Показано, что массовое появление криптографических преобразований с архитек- турами Квадрат и Куб требует пересмотра существующей классификации PRNG, ориен- тированных на решение задач ЗИ. ГПСЧ блочного типа необходимо классифицировать по типу композиции раундовых преобразований. Помимо традиционной последовательной композиции стала все чаще ис- пользоваться последовательно-параллельная, ориентированная на использование гибридных суперкомпьютерных технологий (ГСКТ) и предполагающая параллельное выполнение вы- числений по нескольким трассам. Рассмотрен пример реализации такого преобразования на основе 2D алгоритма, аналогичного специфицированным в AES-128 и ГОСТ Р 34.12 –2015. В свою очередь при использовании последовательной композиции помимо тради- ционной архитектуры Сеть Фейстеля при построении PRNG блочного типа используются 2D и 3D архитектуры, особенностью которых является высокая степень параллелизма на уровне элементарных операций и хорошие рассеивающие и перемешивающие свойства, а также гибридная, суть которой – использование в качестве раундовой функции сети Фейстеля 2D или 3D преобразований. Необходимо деление генераторов по типу доступа. Свойство произ- вольного доступа к любому элементу PRS очень полезно, так как позволяет распараллелить процесс вычисления последовательности, повышая тем самым быстродействие блочных PRNG и таким образом расширяя область их использования. Например, становится возмож- ным использование блочных PRNG в схемах поточного шифрования. Рассмотрены две схе- мы PRNG с произвольным доступом: двухступенчатая (Counter Mode) и Sponge. Источник и информации 1. Vavrenyuk A.B. et. al., 2011. Malicious Software: Teaching Guide. Moscow: National Research Nuclear University MEPhI. http://www.aha.ru/msa/razrushayuschie.pdf. 2. Osmolovsky, S.A., 1991. Stochastic Methods of Data Transmission. Moscow: Radio i Svyaz. 3. Osmolovsky, S.A., 2003. Stochastic Methods of Information Defense. Moscow: Radio i Svyaz. 4. Ivanov, M.A. and I.V. Chugunkov, 2012. Cryptographic Methods of Information Defense in the Computer Systems and Networks: Teaching Guide. Moscow: National Research Nuclear University MEPhI. 5. Daemen, Joan, Lars Knudsen, Vincent Rijmen. The Block Cipher Square. Date Views 07.06.2016 www.ime.usp.br/rt/cranalysis/square.pdf 6. Daemen, Joan, Vincent Rijmen. AES Proposal: Rijndael. Date Views 07.06.2016 citeseerx.ist.psu.edu/viewdoc/download;jsessionid=53629D362985331263F38DB3A1667573?doi= 10.1.1.36.640&rep=rep1&type=pdf 7. Stallings, William. The Whirlpool Secure Hash Function. Date Views 07.06.2016 www.seas.gwu.edu/poorvi/Classes/CS381_2007/Whirlpool.pdf 8. GOST R 34.12-2015. Information Technology. Cryptographic Information Defense. Block Ci- phers, 2015. Moscow: Standartinform. 9. Ассемблер в задачах защиты информации. 2-е дополн. изд. /О.В. Бурдаев и др. – М.: Кудиц-образ, 2004. 10. Three-Dimensional Data Stochastic Transformation Algorithms for Hybrid Supercomputer Implementation / Ivanov M.A., Spiridonov A.A., Chugunkov I.V., et. al. – Proceedings of 17th IEEE Mediterranean Electrotechnical Conference (MELECON), 2014, Beirut, Lebanon, pp. 451 – 457. 11. Nakahara, Jorge Jr. 3D: A Three-Dimensional Block Cipher. Date Views 07.06.2016 infoscience.epfl.ch/record/128649/files/Nak08.pdf (07.06.2016). 12. Biham, Eli and Orr Dunkelman. The SHAvite-3 Hash Function. Date Views 07.06.2016 cs.technion.ac.il/orrd/SHAvite-3/Spec.15.09.09.pdf 13. Using Sequential and Parallel Composition for Stochastic Data Processing/ Ivanov M.A., Kozyrsky B.L., Komarov T.I., et.al. – Proceedings of The Radio-Electronic Devices and Systems for the Infocommunication Technologies (REDS-2013), Moscow, Russia, May 22-23, 2013, pp.144-148. 14. Three New Methods of Stochastic Data Transformaion/M.A. Ivanov, I.V. Matveychikov, A.A. Skitev, P.A. Strelchenko. – Proceedings of The Radio-Electronic Devices and Systems for the Infocommunication Technologies (REDS-2016), Moscow, Russia, May 25-26, 2016, pp.351-355. 15. Keccak sponge function family. Main document. Guido Bertoni, Joan Daemen, Michael Peeters, Gilles Van Assche. Date Views 07.06.2016 keccak.noekeon.org/Keccak-main-2.1.pdf |