Повышение эффективности стохастических методов защиты программных систем тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Тан Найнг Со

• Тан Найнг Со
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Тан Найнг Со

Введение

Глава 1. Теория, применение и оценка качества стохастических алгоритмов защиты информации

1.1. Области использования стохастических алгоритмов

1.2. Требования к качественному генератору ПСП

1.3. Разработка классификации генераторов ПСП

1.4. Анализ существующих генераторов ПСП

1.4.1. Генератор ПСП «Mother-of-AII»

1.4.2. Генератор ПСП Mersenne Twister (МТ, МТ19937)

1.4.3. Генератор ПСП AES

1.4.4. Блочный генератор ПСП «Di-Tech»

1.5. Обзор систем оценки качества генераторов ПСП

1.6. Формулировка целей работы и постановка задач исследования

1.7. Выводы

Глава 2. Разработка и исследование алгоритмов генерации ПСП на основе стохастических сумматоров

2.1. Нелинейные генераторы М-последовательностей

2.1.1. Генераторы ПСП на основе блоков стохастического преобразования (R-блоков)

2.1.2. Стохастический генератор ПСП RFSR

2.1.3. Построение генератора нелинейной последовательности максимальной длины

2.2. Обеспечение гарантированной нижней границы значения периода формируемой последовательности

2.3. Исследование генераторов ПСП на основе R-блоков

2.4. Выводы

Глава 3. Разработка программного комплекса для оценки качества 53 стохастических алгоритмов

3.1. Требования к программному комплексу оценки качества 53 стохастических алгоритмов

3.2. Разработка статистических графических тестов

3.2.1. Тест сравнения групп (Groups Comparison Test)

3.2.2. Тест самых длинных серий (Longest Runs of All Test)

3.2.3. Тест появлений (вправо) (Appearance (Forward) Test)

3.3. Разработка программных средств оценки качества 61 генераторов ПСП

3.4. Разработка программных средств оценки качества S- и R- 68 блоков

3.5. Выводы

Глава 4. Исследование алгоритмов формирования S- и R-блоков

4.1. Критерии выбора S-блоков

4.2. Формирование ключевой таблицы S- и R-блоков 82 по алгоритму RC

4.3. Разработка алгоритма формирования ключевой таблицы 84 S- и R-блоков с использованием ПСП

4.4. Разработка тестов для оценки качества S- и R-блоков

4.5. Исследование алгоритмов формирования ключевой таблицы S- и R-блоков с использованием программного комплекса «S-Вох Testing»

4.6. Выводы 91 Заключение 94 Список источников информации

Введение диссертации (часть автореферата) на тему «Повышение эффективности стохастических методов защиты программных систем»

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

• техническое диагностирование компонентов КС (в том числе встроенное диагностирование);

• оперативный контроль хода выполнения программ и микропрограмм с использованием сторожевых процессоров (Watchdog Processors);

• моделирование;

• помехоустойчивое стохастическое кодирование;

• обеспечение безопасности информации (ОБИ).

Именно от свойств генераторов ПСП, особенно в тех случаях, когда необходимо обеспечить устойчивую работу КС при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки, хранения и передачи информации. К программным средствам генерации ПСП предъявляются жесткие требования, в первую очередь по таким параметрам, как непредсказуемость, безопасность реализации, статистические и периодические свойства.

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

1) Национальный Институт Стандартов и Технологий США (НИСТ) выпустил многосотстраничное руководство по статистическому тестированию генераторов ПСП ответственного назначения.

2) При проведении многолетнего открытого международного конкурса (завершившегося в 2001 году) на принятие американского стандарта AES для оценки алгоритмов-кандидатов активно использовались статистические исследования ПСП.

3) Появились программные комплексы для проведения статистических испытаний генераторов ПСП (наиболее известные из них -DIEHARD, CRYPT-X, СОК).

Однако существующие программные комплексы являются либо узкоспециализированными (например, DIEHARD предназначен для исследования лишь конгруэнтных генераторов), либо малофункциональными (например, CRYPT-X содержит всего лишь пять тестов, в то время как в руководстве НИСТ описано шестнадцать). В наиболее функциональном комплексе СОК, разработанном И.В. Чугунковым, отсутствуют встроенные генераторы ПСП, нет возможности проводить исследования основных строительных элементов генераторов ПСП - S- и R-блоков.

Поэтому актуальными научными задачами являются:

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

Стохастические генераторы ПСП сочетают в себе высокое качество формируемых последовательностей и эффективную программную реализацию.

2) Разработка структуры и определение функций отдельных компонентов программного комплекса, позволяющего проводить полнофункциональное статистическое исследование ПСП, в том числе проводить испытания на всех существующих графических и оценочных тестах, оценивать качество основных строительных элементов генераторов ПСП.

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

Для достижения поставленных целей необходимо решение следующих задач: разработка классификации генераторов ПСП; анализ методов оценки качества стохастических алгоритмов; разработка структуры, состава и интерфейса пользователя программного комплекса, предназначенного для исследования стохастических алгоритмов; разработка программных средств оценки качества S-блоков; разработка и исследование генераторов ПСП на основе R-блоков; исследование существующих алгоритмов генерации ПСП. Методами исследований являются: теория конечных полей, теория линейных последовательностиых машин, математическая статистика.

Научная новизна работы состоит в том, что: разработана классификация существующих алгоритмов генерации

ПСП; сформулированы требования, предъявляемые к системе оценки качества ПСП, и проведен анализ существующих систем аналогичного назначения; разработана структура и определен состав компонентов программного комплекса для оценки качества генераторов ПСП; разработан новый алгоритм генерации ПСП, обеспечивающий гарантированную нижнюю границу значения периода формируемой последовательности; предложен новый стохастический итерационный алгоритм генерации ПСП, сочетающий достоинства двух существующих архитектур, использующихся при построении блочных преобразований, -«Петли Фейстеля» и «Квадрата»; впервые проведено исследование R-блоков на предмет выявления тех таблиц стохастического преобразования, которые порождают нелинейные ^-последовательности.

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

Реализация результатов. Результаты диссертационной работы внедрены в учебный процесс кафедры «Компьютерные системы и технологии» МИФИ. Практическое использование результатов диссертации подтверждено актом о внедрении.

Апробация работы. Основные результаты работы докладывались и обсуждались на научных сессиях МИФИ (Москва, 2005 г., 2006 г. и 2007 г.); на 62-й научной сессии Российского НТО радиотехники, электроники и связи имени А.С.Попова, посвященной Дню радио (Москва, 2007 г) демонстрировались на выставке «Телекоммуникации и новые информационные технологии в образовании» (Москва, 2006 г.).

Публикации. По теме диссертационной работы опубликовано 7 печатных работ, в том числе 4 тезиса докладов на научной сессии МИФИ, материалы в каталоге экспонатов выставки «Телекоммуникации и новые информационные технологии в образовании», статья в журнале «Инженерная физика» и доклад в сборнике научных трудов Российского НТО РЭС имени А.С.Попова.

Структура работы. Диссертация состоит из введения, четырех глав, заключения и приложений. Основной материал изложен на 100 страницах и содержит 31 рисунков. Список литературы включает 65 наименований. В приложения включены результаты исследований, руководства пользователя по созданным программным продуктам и акт о внедрении результатов диссертационной работы. На защиту выносятся: • структура программного комплекса для исследования статистических свойств ПСП и оценки качества S- и R-блоков, включающего в себя систему для проведения графических и оценочных статистических тестов, встроенные генераторы ПСП различных типов;

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Тан Найнг Со

Основные результаты работы:

1) Проанализированы области использования стохастических алгоритмов защиты программных систем, основанных на использовании генераторов ПСП. Сформулированы требования к качественному генератору ПСП, ориентированному на использование в защищенных программных системах.

2) Разработана классификация генераторов ПСП, в которой в качестве параметров выбраны: тип используемой нелинейной функции; структура генератора; характер использования внешних источников случайности; принцип управления синхронизацией; принцип получения выходной последовательности; принцип использования блоков замены и блоков стохастического преобразования (S- и R-блоков); наличие каскадов.

3) Выделены направления совершенствования блочных алгоритмов формирования ПСП, в том числе разработан новый блочный алгоритм генерации ПСП, основанный на совместном использовании архитектур «Сеть Фейстеля» и «Квадрат». Основным преимуществом алгоритма по сравнению с аналогами является более интенсивное рассеивание и перемешивание информации за счет использования оригинальной раундовой операции «Перемешивание строк» (MixColumns).

4) Проведено исследование генераторов ПСП, основанных на использовании регистров сдвига со стохастическими сумматорами в цепи обратной связи. Продемонстрирован важный факт существования таблиц стохастического преобразования, на основе которых появляется возможность строить нелинейные генераторы ПСП длиной 2° - 1, где Q - число элементов памяти генератора.

5) Разработаны новые алгоритмы генерации ПСП на основе стохастических сумматоров, гарантированно обеспечивающие заданную минимальную величину периода формируемой последовательности, равную 2N -1, где N - число регистров генератора.

6) Впервые проведены экспериментальные исследования генераторов ПСП на основе стохастических сумматоров в части определения ключевых таблиц, обеспечивающих получение нелинейных М-последовательностей.

7) Проведен анализ существующих систем, предназначенных для статистического исследования генераторов ПСП, к которым предъявляются наиболее жесткие требования. Выделены их недостатки, основными из которых являются узкая специализация, недостаточное количество реализованных статистических тестов, отсутствие встроенных генераторов ПСП различных типов, отсутствие возможности оценки качества основных строительных элементов генераторов ПСП.

8) Сформулированы требования к полнофункциональному программному комплексу для оценки качества стохастических алгоритмов. На основе сформулированных требований разработаны структура и состав программного комплекса, в составе которого выделяются программные средства для анализа статистической безопасности генераторов ПСП и программные средства для оценки качества блоков замены и блоков стохастического преобразования.

9) Проведен анализ критериев выбора S-блоков и алгоритмов формирования ключевых таблиц S- и R-блоков. Разработаны статистические тесты для оценки качества ключевых таблиц S- и R-блоков. Проведено исследование качества алгоритмов формирования ключевой таблицы S- и R-блоков.

10) Проведено исследование статистической безопасности алгоритмов генерации ПСП. Основной вывод по результатам исследований - качество ПСП, формируемых генераторами, основанными на использовании R-блоков, приемлемо для большинства приложений.

Теоретические и практические результаты диссертации обеспечивают повышение технической эффективности средств защиты программных систем по сравнению с общеизвестными решениями:

• Разработанные генераторы ПСП на основе R-блоков обеспечивают заданную минимальную величину периода формируемой последовательности, равную 2N - 1, где N - число регистров генератора;

• Разработанный программный комплекс оценки качества генераторов ПСП содержит в своем составе средства анализа статистической безопасности S- и R-блоков, ряд новых статистических тестов, встроенные генераторы ПСП, имеет развитую систему помощи. Разработанные программные комплексы для оценки качества стохастических алгоритмов («PRNG Analyzer» и «S-Вох Testing»), а также программный комплекс для демонстрации принципов использования стохастических алгоритмов в задачах защиты программных систем («Crypto Protocols Package») внедрены в учебный процесс каф. 12 МИФИ.

Заключение

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

Список литературы диссертационного исследования кандидат технических наук Тан Найнг Со, 2007 год

1. Ассемблер в задачах защиты информации / И. Ю. Жуков, М.А. Иванов, Ю.В. Метлицкий и др. М.: КУДИЦ-ОБРАЗ, 2004. 540 с.

2. Беннетс Р.Дж. Проектирование тестопригодных логических схем. М.: Радио и связь, 1990.

3. Брассар Ж. Современная криптология: Пер. с англ. М.: ПОЛИМЕД, 1999.

4. Введение в криптографию / Под общ. ред. В. В.Ященко. М.: МЦНМО, «ЧеРо», 1998.

5. Герасименко В.А., Малюк А.А. Основы защиты информации. М.: МИФИ, 1997.

6. Гилл А. Линейные последовательностные машины: Пер. с англ. М.: Наука, 1974.

7. Грибунин В.Г., Оков И.Н., Туринцев И.В. Цифровая стеганография. М.: Солон-Пресс, 2002.

8. Дисман A.M., Иванов А.А., Иванов М.А. Принципы построения и свойства генераторов L-ричных последовательностей максимальной длины //Автоматика и вычислительная техника, 1990, № 4, с. 65-73.

9. Жуков И.Ю., Иванов М.А., Осмоловский С.А. Принципы построения криптостойких генераторов псевдослучайных кодов // Проблемы информационной безопасности. Компьютерные системы. 2001, № 1.

10. Зензин О. С., Иванов М. А. Стандарт криптографической защиты -AES. Конечные поля. Серия СКБ (специалисту по компьютерной безопасности). Книга 1. М.: КУДИЦ-ОБРАЗ, 2002. 176 с.

11. Иванов М. А., Криптографические методы защиты информации в компьютерных системах и сетях. М.: КУДИЦ-ОБРАЗ, 2001. 368с.

12. Иванов М. А., Куликов С. С., Тан Найнг Со. Классификация генераторов псевдослучайных последовательностей. Научная сессия МИ

13. ФИ-2005. Сборник научных трудов. Т.12. Компьютерные системы и технологии. М.: МИФИ, 2005, с.153-154.

14. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей. Серия СКВ (специалисту по компьютерной безопасности). Книга 2. М.: КУДИЦ-ОБРАЗ, 2003. 240 с.

15. Иванов М.А., Тан Найнг Со, Тун Мья Аунг. Разработка и исследование стохастических алгоритмов защиты информации. Инженерная физика, 2007, №1, с. 64-68,.

16. Иванов М.А., Тан Найнг Со, Тун Мья Аунг. Разработка и исследование стохастических алгоритмов защиты информации. Сборник трудов Российского НТО радиотехники, электроники и связи имени А.С.Попова. 2007 г.

17. Кнут Д. Искусство программирования для ЭВМ: в 3-х томах. Пер. с англ. М.: Мир, 1977.

18. Материалы с сайта http://www.random-art.com.

19. Осмоловский С.А. Стохастические методы передачи данных. М.: Радио и связь, 1991.

20. Осмоловский С.А. Стохастические методы защиты информации. М.: Радио и связь, 2003.

21. Поликарпов С.В., Кафедра РЭС ЗиС, Статистическое тестирование генераторов псевдослучайных чисел с использованием набора статистических тестов NIST STS. http://www.infotecstt.ru/~fibres/artic7.html.

22. Поточные шифры / А. А. Асосков, М. А. Иванов, А. Н. Тютвин и др. Серия СКБ (специалисту по компьютерной безопасности). Книга 3. -М.: КУДИЦ-ОБРАЗ, 2003.

23. Тан Найнг Со, Тун Мья Аунг, Иванов М. А. Генераторы псевдослучайных последовательностей в задачах защиты информации. Научная сессия МИФИ-2006. Сборник научных трудов. Т.12. Компьютерные системы и технологии. М.: МИФИ, 2006, с.115-116.

24. Тан Найнг Со. Разработка инструментальных средств оценки качества стохастических алгоритмов обеспечения безопасности информации. Научная сессия МИФИ-2006. Сборник научных трудов. Т.12. Компьютерные системы и технологии. М.: МИФИ, 2006, с. 117.

25. Тан Найнг Со. Разработка и исследование стохастических алгоритмов генерации псевдослучайных последовательностей (ПСП). -Научная сессия МИФИ-2007. Сборник научных трудов. Т.12. Компьютерные системы и технологии. М.: МИФИ, 2007, с. 135-136.

26. Ярмолик В.Н., Демиденко С.Н. Генерирование и применение псевдослучайных сигналов в системах испытаний и контроля. / Под ред. П.М. Чеголина. Минск: Наука и техника, 1986.

27. Ярмолик В.Н. Контроль и диагностика цифровых узлов ЭВМ. Минск: Наука и техника, 1988.

28. Adams С., "Constructing Symmetric Ciphers Using the CAST Design Procedure", in Selected Areas in Cryptography, Kluwer Academic Publishers,1997, pp.71-104 (reprinted from Designs, Codes and Cryptography, vol. 12, no.3, November 1997).

29. Adams C., Tavares S., "The Structured Design of Cryptographically Good S-boxes", To appear in J. of Cryptology, 1990.

30. Agner Fog, Chaotic Random Number Generators with Random Cycle Lengths, December 2000, revised November 25, 2001. http://www.agner.org/random/theory/chaosran.pdf.

31. Ayoub F., "Probabilistic Completeness of Substitution-Permutation Encryption Network", IEEE, Vol.129, Е, 5, pp195-199, Sep., 1982.

32. A. Menezes, P. van Oorschot, and S. Vanstone, Handbook of Applied Cryptography, CRC Press, 1996.

33. Brickell E. F., Moore J. H., Purtill M. R., "Structures in the S-boxes of the DES", Proc. of CRYPTO'86, Springer-Verlag, pp. 3-8, 1986.

34. Colin Plumb, "Truly Random Numbers", Dr. Dobb's Journal, November 1994.

35. Couture R., L'Ecuyer P., Distribution properties of multiply-with-carry random number generators. Math. Сотр. 66 (1997), pp. 591-607. http://citeseer.ist.psu.edu/couture97distribution.html.

36. Coveyou R., MacPherson R., Fourier analysis of uniform random number generators. J. ACM 14 (1967), pp.100-119. http://portal.acm.org/citation.cfm?id=321379&coll=portal&dl=ACM.

37. Daemen J., Rijmen V., "AES Proposal: Rijndael", Document version 2, 03-09-99, http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael.pdf.

38. Feistel H., "Cryptography and Computer Privacy", Scientific American, Vol.228, No.5, pp 15-23, 1973.

39. Hellman M., Merkle R., Schroeppel R., Washington L., Diffie W., Pohlig S. and Schweitzer P., "Results of an Initial Attempt to Analyze the NBS Data Encryption Standard", Information Systems Laboratory Report, Stanford University, 1976.

40. Information Security Research Centre (ISRC), Faculty of Information Technology, CRYPT-X. http://www.isrc.qut.edu.au/resource/cryptx/.

41. Kam J. В., Davida G. I., "Structured Design of Substitution-Permutation Encryption Network", IEEE Trans, on Comput., Vol.C-28, No.10, pp.747753, Oct., 1979.

42. Klapper A., Goresky M., Efficient Multiply-With-Carry Random Number Generators with Optimal Distribution Properties. http://www.math.ias.edu/~goresky/MWC.pdf.

43. Klapper A., Goresky M., Feedback shift registers, 2-adic span, and combiners with memory. J. Crypt. 10 (1997), pp. 111-147. http://citeseer.ist.psu.edu/335979.html.

44. Marsaglia G., "A New Class of Random Number Generators", The Annals of Applied Probability, vol. 1, 1991, pp. 462-480.

45. Marsaglia G., DIEHARD: a battery of tests for random number generators. http://stat.fsu.edu/~geo/diehard.html.

46. Marsaglia G., Yet another rng, posted to electronic bulletin board www.sci.stat.math, Aug1, 1994.

47. Matsumoto M., Kurita Y., "Twisted GFSR generators", ACM Trans, on Modeling and Computer Simulation, 2(1992),http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/tgfsr3.pdf.

48. Matsumoto M., Kurita Y., "Twisted GFSR generators II", ACM Trans, on Modeling and Computer Simulation, 4(1994),http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/ttgfsr7.pdf.

49. Meier W., Staffelbach O., "Nonlinearity Criteria for Cryptographic Functions", Proc. of EUROCRYPT'89, 1989.

50. National Institute of Standards and Technology (NIST), "A Statistical Test Suite For Random And Pseudorandom Number Generators For Cryptographic Application", NIST Special Publication 800-22. May 15, 2001.

51. National Institute of Standards and Technology (NIST), Random Number Generation and Testing, http://csrc.nist.gov/rng/.

52. National Institute of Standards and Technology (NIST), Errata for Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST Special Publication 800-22. May 15, 200.

53. National Institute of Standards and Technology (NIST), Statistical Testing of Random Number Generators. Juan Soto. 100 Bureau Drive, Stop 8930. Gaithersburg, MD 20899-8930.

54. National Institute of Standards and Technology, "Secure Hash Standard", FIPS 186-1, US Department of Commerce, April 1995.

55. Pieprzyk J., "Nonlinear Function and their Application to Cryptography", Archiwum Automatykii Telemechaniki, 3-4, pp. 311-323,1985.

56. Rivest, R., "The MD4 message digest algorithm", in A.J. Menezes and S.A. Vanstone, editors, Advances in Cryptology CRYPTO '90 Proceedings, pp. 303-311, Springer-Verlag, 1991.

57. Rivest R., The MD5 Message-Digest Algorithm, MIT Laboratory for Computer Science and RSA Data Security, Inc. April 1992, www.faqs.org/ftp/rfc/pdf/rfc1321 .txt.pdf.

58. Ritter's Crypto Glossary and Dictionary of Technical Cryptography, Technical Cryptographic Terms Explained. http://www.hackpaIace.com/encryption/general/glossary.html.

59. Schneier, Bruce, "Applied Cryptography Second Edition: protocols, algorithms, and source code in C". John Wiley & Sons, Inc. Copyright 1996 by Bruce Schneier.

60. Secure Hash Standard, Federal Information Processing Standards Publication 180-2, 2002 August 1, http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf.

61. Serge Mister, Carlisle Adams, "Practical S-Box Design", http://citeseer.ist.psu.edu/mister96practical.html.

62. Ueli Maurer, "A Universal Statistical Test for Random Bit Generators," Journal of Cryptology, Vol. 5, No. 2, 1992, pp. 89-105.

63. Webster A. F., "Plaintext/Ciphertext Bit Dependencies in Cryptographic Systems", Master's Thesis, Department of Electrical Engineering, Queen's University, CANADA, 1985.