Реферат: Анализ криптостойкости методов защиты информации в операционных системах Microsoft Window 9x

МИНИСТЕРСТВО ОБРАЗОВАНИЯРОССИЙСКОЙ ФЕДЕРАЦИИ

САМАРСКИЙГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ

ФАКУЛЬТЕТ

КАФЕДРА “ВЫСШАЯ И

ПРИКЛАДНАЯМАТЕМАТИКА”

УТВЕРЖДАЮ

Заведующий кафедрой

“Высшая и прикладная

математика”

«___»__________2001г.

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА

студента АЛЬПЕРТАВЛАДИМИРА ВЛАДИМИРОВИЧА

на тему: АНАЛИЗКРИПТОСТОЙКОСТИ МЕТОДОВ ЗАЩИТЫ ИНФОРМАЦИИ В ОПЕРАЦИОННЫХ СИСТЕМАХ MICROSOFTWINDOW 9x

по специальности 01.02.00 “Прикладная математика”

Научныйруководитель: к. т. н.

ПОНОМАРЕВ ВЛАДИМИР ПЕТРОВИЧ

«___»________2001г.__________________

Студент___________________ «___»________2001г.

Дипломная работа защищена «___»________2001г.

Оценка_______________________________________

Председатель ГЭК_____________________________

Самара

2001г.

СОДЕРЖАНИЕ

Стр.

TOC o«1-3»

___________________________________________________________ PAGEREF _Toc517456195 h

1.Теоретические основы криптоанализа_____________________________________ PAGEREF_Toc517456196 h 7

1.1 Методы криптоанализа______________________________________________ PAGEREF _Toc517456197 h

1.2 Потоковые шифры________________________________________________ PAGEREF _Toc517456198 h

1.3 Алгоритм RC4 и его криптоанализ___________________________________ PAGEREF _Toc517456199 h

2. Защита информации в операционных системах Microsoft Windows 9x__________ PAGEREF_Toc517456200 h 24

2.1 Аутентификация, безопасность и доступ к ресурсам воперационных системах семейства Microsoft Windows 9x_________________________________________________ PAGEREF _Toc517456201 h

2.2 Структура PWL–файлов____________________________________________ PAGEREF _Toc517456202 h

3. Программа анализа PWL-файлов________________________________________ PAGEREF_Toc517456203 h 31

3.1 Оценка надежности криптоалгоритмов в зависимости от длиныключа______ PAGEREF _Toc517456204 h

3.2 Разработка программы_____________________________________________ PAGEREF _Toc517456205 h

3.3 Функции программы_______________________________________________ PAGEREF _Toc517456206 h

ЗАКЛЮЧЕНИЕ_______________________________________________________ PAGEREF _Toc517456207 h

БИБЛИОГРАФИЧЕСКИЙ СПИСОК________________________________________ PAGEREF _Toc517456208 h

ПРИЛОЖЕНИЕ_______________________________________________________ PAGEREF _Toc517456209 h 5

ВВЕДЕНИЕ

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

Другойважной проблемой применения криптографии является противоречие между желаниемграждан защитить свою информацию и стремлением государственных спецслужб иметьвозможность доступа к некоторой информации для пресечения незаконнойдеятельности. Чрезвычайно трудно найти неоспоримо оптимальное решение этой проблемы.Как оценить соотношение потерь законопослушных граждан и организаций от незаконногоиспользования их информации и убытков государства от невозможности получениядоступа к защищенной информации отдельных групп, скрывающих свою незаконную деятельность?Можно ли гарантированно не допустить незаконное использование криптоалгоритмовлицами, которые нарушают и другие законы? Кроме того, всегда существуют способыскрытого хранения и передачи информации.

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

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

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

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

Рис. 1. Почему криптосистемы ненадежны.

Внастоящей работе проведен анализ криптостойкости методов защиты информации воперационных системах семейства Microsoft Windows 9x, кроме того, былопроведено исследование по поиску необходимой длины ключа и пароля, а такжерассматриваются проблемы криптоанализа потокового шифра на примере популярногоалгоритма RC4. Разработанная программа по исследованию PWL-файлов позволитвосстанавливать забытые пароли и упорядочить имеющиеся сетевые ресурсы.

1.Теоретические основы криптоанализа1.1 Методыкриптоанализа

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

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

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

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

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

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

Стойкостьдоказуемо стойких криптоалгоритмов определяется сложностью решения хорошоизвестной математической задачи, которую пытались решить многие математики икоторая является общепризнанно сложной. Примером могут служить системыДиффи-Хеллмана или Ривеста-Шамира-Адельмана, основанные на сложностяхсоответственно дискретного логарифмирования и разложения целого числа намножители. Достоинством доказуемо стойких алгоритмов является хорошаяизученность задач, положенных в их основу. Недостатком их являетсяневозможность оперативной доработки криптоалгоритмов в случае появления такойнеобходимости.

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

Криптографическиеалгоритмы обычно строятся с использованием простых и быстро выполняемыхоператоров нескольких типов. Множество обратимых операторов, преобразующихтекст длиной n бит в текст длиной n бит, являются элементами группы обратимыхоператоров по умножению (подстановок n-разрядных слов). Пусть f, g, h — обратимыеоператоры, то есть существуют f-1, g-1, h-1. Поэтому hgf — последовательное выполнение операторов f, g, h — тоже обратимыйоператор (операторы выполняются справа налево) с обратным оператором к этомупроизведению f-1, g-1, h-1. Поэтомудешифратор выполняет те же операции, что и шифратор, но в обратном порядке, икаждый оператор дешифрования является обратным к соответствующему операторушифрования. Некоторые операторы являются взаимно обратными, то есть выполнениеподряд два раза некоторой операции над текстом дает исходный текст. В терминахтеории групп это записывается уравнением f 2 = e, где e — единичныйоператор. Такой оператор называется инволюцией. Можно сказать, что инволюцияпредставляет собой корень из единицы. Примером инволюции является сложение помодулю два текста с ключом.

Существуетеще одно важное применение одноключевой криптографии. Это осуществлениевычислимого в одну сторону преобразования информации. Такое преобразованиеназывается хэш-функцией. Особенность этого преобразования заключается в том,что прямое преобразование y=h(x) вычисляется легко, а обратное x=h-1(y)- трудно. Вообще говоря, обратное преобразование не является функцией, поэтомуправильнее говорить о нахождении одного из прообразов для данного значенияхэш-функции. В этом случае ключа, понимаемого как некоторая конфиденциальнаяинформация, нет. Однако стойкие хэш-функции, для которых прообраз по данномузначению функции тяжело найти, реализуются криптографическими методами итребуют для обоснования стойкости проведения криптографических исследований.Типичное применение хэш-функции — создание сжатого образа для исходного текстатакого, что найти другой текст, обладающий таким же образом, вычислительноневозможно. Задача создания стойкой хэш-функции возникает, например, прицифровой подписи текстов.

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

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

Обычнокриптоалгоритмы разрабатывают так, чтобы они были стойкими по отношению ккриптоанализу на основе специально выбранных открытых текстов.

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

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

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

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

Рассматриваемый нами криптоалгоритм RC4 относится кклассу потоковых шифров, которые в последнее время стали популярными благодарявысокой скорости работы. Потоковые шифры преобразуют открытый текст в шифротекстпо одному биту за операцию. Генератор потока ключей (иногда называемыйгенератором с бегущим ключом) выдает поток битов: k1, k2,k3, ..., ki. Этот поток ключей и поток битов открытого текста,p1, p2, p3, ..., pi, подвергаютсяоперации “исключающее или", и в результате получается поток битов шифротекста.

ci =pi ^ ki

При дешифрировании операция XOR выполняется над битамишифротекста и тем же самым потоком ключей для восстановления битовоткрытого текста.

pi = ci ^ ki

<img src="/cache/referats/9412/image004.jpg" v:shapes="_x0000_s1101">
Безопасность системы полностью зависит от свойствгенератора потока ключей. Генератор потока ключей создает битовый поток,который похож на случайный, но в действительности детерминирован и может бытьбезошибочно воспроизведен при дешифрировании. Чем ближе выход генератора потокаключей к случайному, тем больше времени потребуется для взлома шифра.

Рис. 2. Потоковый шифр.

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

<img src="/cache/referats/9412/image006.jpg" v:shapes="_x0000_s1102">
Генератор потока ключей состоит из трех основных частей.Внутреннее состояние описывает текущее состояние генератора потока ключей. Двагенератора потока ключей, с одинаковым ключом и одинаковым внутренним состоянием,выдают одинаковые потоки ключей. Функция выхода по внутреннему состояниюгенерирует бит потока ключей. Функция следующего состояния по внутреннемусостоянию генерирует новое внутреннее состояние.

Рис. 3. Устройство генератора потока ключей.

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

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

<img src="/cache/referats/9412/image008.jpg" v:shapes="_x0000_s1103">
Рис.4. Самосинхронизирующийся генератор потока ключей.

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

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

Существенное повышениепроизводительности микропроцессоров в 1980-е годы вызвало в криптографииусиление интереса к программным методам реализации криптоалгоритмов каквозможной альтернативе аппаратным схемам на регистрах сдвига. Одним из самыхпервых подобных криптоалгоритмов, получившим широкое распространение, стал RC4.Алгоритм RC4 — это потоковый шифр с переменной длиной ключа, разработанныйв 1987 году Рональдом Райвистом для компании RSA Data Security. Он обладаетследующими свойствами:

• адаптивностью для аппаратныхсредств и программного обеспечения, что означает использование в нем толькопримитивных вычислительных операций, обычно присутствующих на типичных микропроцессорах.

• алгоритм быстрый, т.е. в базисныхвычислительных операциях операторы работают на полных словах данных.

• адаптивностью на процессорыразличных длин слова.

• компактностью в терминах размеракода, и особо удобен для процессоров с побайтно-ориентированной обработкой.

• низким требованием к памяти, чтопозволяет реализовывать алгоритм на устройствах с ограниченной памятью;

• использованием циклических сдвигов,зависимых от данных, с «переменным» числом.

• простотой и легкостью выполнения.

В течение семи лет этот алгоритмбыл фирменным секретом и детали о его конструкции предоставлялись только послеподписания договора о неразглашении, но в сентябре 1994 года кто-то анонимнораспространил исходный код алгоритма через Internet. Пользователи Сети, имеющиелегальные криптосредства фирмы RSA, реализующие RC4, подтвердили совместимостькода с криптопрограммой. В настоящее время алгоритм RC4 реализован в десяткахкоммерческих криптографических продуктов, включая Lotus Notes, Apple Computer'sAOCE, Oracle Secure SQL, а также является частью спецификации стандарта сотовойсвязи CDPD.

Криптогенератор функционируетнезависимо от открытого текста. Генератор имеет подстановочную таблицу (S-бокс8 х 8): S0, S1,.. ., S255. Входамигенератора являются замененные по подстановке числа от 0 до 255, и эта подстановкаявляется функцией от ключа изменяемой длины. Генератор имеет два счетчика i иj, инициализируемых нулевым значением.

Для генерации случайного байтагаммы выполняются следующие операции:

i = (i+1)mod 256

j = (j+Si)mod 256

swap (Si,Sj)

t = (Si+Sj)mod 256

K = St

Байт K складывается операцией XOR с открытым текстомдля выработки шифротекста, либо с шифротекстом для получения байта открытоготекста. Шифрование происходит весьма быстро — примерно в 10 раз быстрееDES-алгоритма. Инициализация S-бокса столь же проста. На первом шаге он заполняетсялинейно:

S0= 0, S1 =1,.. ., S255 = 255.

Затем еще один 256-байтный массив полностьюзаполняется ключом, для чего ключ повторяется соответствующее число раз взависимости от длины: K0, K1,.. ., K255.Индекс j обнуляется. Затем:

for i=0 to 255

j = (j+Si+Ki)mod 256

swap (Si, Sj)

Схема показывает, что RC4 можетпринимать примерно 21700 (256! * 2562) возможныхсостояний. S-бох медленно изменяется в процессе работы: параметр i обеспечиваетизменение каждого элемента, а j отвечает за то, чтобы эти элементы изменялисьслучайным образом. Фактически, RC4 представляет собой семейство алгоритмов,задаваемых параметром n, который является положительным целым с рекомендованнымтипичным значением n = 8.

Внутреннее состояние генератора RC4в момент времени t состоит из таблицы St =(St(L))t=0n2-1, содержащей 2n n-битных слов и из двух n-битныхслов-указателей it и jt. Таким образом, размер внутреннейпамяти составляет M = n2n + 2n бит. Пусть выходное n-битное словогенератора в момент t обозначается как Zt.

Пусть начальные значения i0= j0= 0. Тогда функция следующего состояния и функция выхода RC4для каждого t ≥ 1 задается следующими соотношениями:

it= it-1 + 1

jt= jt-1 + St-1(it)

St(it)= St-1(jt)

St(jt)= St-1(it)

Zt= St(St(it) + St(jt)),

где все сложения выполняются помодулю 2n. Подразумевается, что все слова, кроме подвергаемыхперестановке, остаются теми же самыми. Выходная последовательность n-битныхслов обозначается как Zt =(Zt )t=1¥

.Начальнаятаблица S0задается в терминах ключевой последовательности

K = (KL)t=02n -1

с использованием той же самойфункции следующего состояния, начиная от таблицы единичной подстановки (L)2nL=02n -1. Более строго, пусть j0= 0 и длякаждого 1 ≤ t ≤ 2n вычисляется jt = (jt — 1 + St-1(t-1) + Kt-1) mod 2 n, а затем переставляютсяместами St-1(t-1) и St-1(jt).

На последнем шаге порождается таблица,представляющая S0. Ключевая последовательность K составляется изсекретного ключа, возможно повторяющегося, и случайного ключа, передаваемого воткрытом виде в целях ресинхронизации.

До последнего времени в открытойлитературе практически не было публикаций по криптоанализу алгоритма RC4.Компания RSA Data Security объявила, что шифр обладает иммунитетом к методамлинейного и дифференциального криптоанализа, высоко не линеен и не похоже,чтобы у него были короткие циклы. Обычно цитируется заключение закрытой работыкриптографа RSA Labs Мэтта Робшоу: «Не имеется известных слабых ключей и,хотя нет доказательства для нижней границы периодов последовательностей RC4,проведенный теоретический анализ показывает, что период в подавляющем большинствеслучаев превышает 10100. Тщательный и всеобъемлющий анализ стойкостиRC4 не выявил никаких оснований подвергать сомнению стойкость, обеспечиваемуюгенератором RC4».

Первой открытой публикацией можносчитать работу Йована Голича, представленную на конференции Eurocrypt '96. Вней отмечается, что для последовательностей, генерируемых RC4, не подходятметоды статистического анализа. Но, с другой стороны, как показано в работах,для блоков, размер которых превышает M (размер внутренней памяти генератора),всегда существует линейная статистическая слабость или так называемая«линейная модель». Такую модель можно эффективно определять с помощьюметода аппроксимации линейной последовательной схемой. Линейная статистическаяслабость — это линейное соотношение между битами гаммы, которое выполняется свероятностью, отличающейся от 1/2.

Главная цель работы Голича — спомощью метода АЛПС вывести линейные модели для RC4. Метод АЛПС заключается внахождении и решении последовательной линейной схемы, которая аппроксимируетгенератор гаммы и приводит к линейным моделям с относительно большимкорреляционным коэффициентом c, где вероятность соответствующего линейногосоотношения между битами гаммы составляет (1+ c)/2. При анализе использоваласьтехника двоичных производных. Пусть Z = (Zt)t=1¥

обозначаетпоследовательность самых младших бит слов выхода RC4, и пусть Z/=( Z/t= Zt+ Zt+1)t=1¥и Z//=(Z//t = Zt+ Zt+2)t=1¥обозначаютее первую и вторую двоичные производные, соответственно. Показано, что Z/не коррелирует ни с 1, ни с 0, но Z// коррелирует с 1 скорреляционным коэффициентом, близким к 15*2-3n при больших 2n, гдеn – длина ключа. Поскольку длина выходной последовательности, требуемая длявыявления статистической слабости с корреляционным коэффициентом c, составляетO(c-2), то эта длина равна примерно 64n /225. Например,если n = 8, как рекомендуется в большинстве приложений, то требуемая длинаблизка к 240.

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

В 1997 годуопубликована большая работа Йована Голича, посвященная криптоанализу обобщеннойсхемы комбинирующего узла с произвольным размером памяти. Исследованыкорреляционные свойства таких узлов, обоснованы новые конструктивные критерии,предъявляемые к схемам подобного типа. Разработан эффективный метод аппроксимациилинейной последовательной схемой для построения линейных функций от входа ивыхода со сравнительно большим коэффициентом взаимной корреляции. Этопрактичная процедура, позволяющая с высокой вероятностью находить пары взаимнокоррелированных линейных функций (от самое большее M + 1 последовательных выходныхбит и самое большее M + 1 последовательных векторов входа) со сравнительнобольшими коэффициентами корреляции. Метод АЛПС состоит в задании и решении линейнойпоследовательной схемы (ЛПС), которая аппроксимирует комбинирующий узел спамятью. Эта ЛПС имеет добавочные несбалансированные входы и основана на линейныхаппроксимациях функции выхода и всех компонент функции следующего состояния.Линейная аппроксимация булевой функции — это любая линейная функция, с которойзаданная булева функция скоррелирована. Описанный метод применим к произвольнымкомбинирующим узлам с памятью без ограничений на функции выхода и следующего состояния.

Сначалаотыскиваются линейные аппроксимации функции выхода f и каждой из функций-компонентфункции следующего состояния F. Это эквивалентно выражению каждой из этих M+1функций в виде суммы линейной функции и несбалансированной функции. Еслиподлежащая декомпозиции функция уже несбалансированна, то можно выбратьконстантно-нулевую линейную функцию. Если подлежащая декомпозиции функция статистическинезависима от некоторого подмножества переменных, то каждая линейная аппроксимацияс необходимостью должна задействовать по крайней мере одну из переменных этогоподмножества. Основное требование – чтобы соответствующие корреляционныекоэффициенты отличались от нуля. Также желательно, чтобы выбирались линейныеаппроксимации с корреляционными коэффициентами, абсолютные значения которыхблизки к максимальным. Корреляционные коэффициенты можно определять с помощьютехники преобразования Уолша.

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

St+1= ASt + BXt + D

(Xt, St),t≥0,

yt= CSt + DXt + e

(Xt, St),t ≥0,

где векторырассматриваются как матрицы-столбцы; A,B, C, D — двоичные матрицы;а e

и каждый компонент в D = (d1,..., dM) – несбалансированныебулевы функции, именуемые функциями шума. Основная идея состоит в том, чтобырассматривать {e(Xt ,St)}t=0¥и {d(Xt ,St)}t=0¥, 1≤i≤M, в качестве входных последовательностей, так чтопоследние уравнения оказываются задающими неавтономную линейную машину сконечным числом состояний или ЛПС, именуемую АЛПС комбинирующего узла спамятью. Тогда можно решать эту ЛПС с использованием техники производящихфункций (D-преобразований). В частности, пусть S, X, D, e, yобозначают производящие функции от переменной z

еще рефераты

Еще работы по программному обеспечению

Реферат по программному обеспечению

Разработка АРМ научно-технической библиотеки университета

29 Августа 2013

Реферат по программному обеспечению

Организация изучения основных алгоритмических конструкций в среде Лого Миры

29 Августа 2013

Реферат по программному обеспечению

Разработка отказоустойчивой операционной системы реального времени для вычислительных систем с максимальным рангом отказоустойчивости

29 Августа 2013

Реферат по программному обеспечению

Использование гиперссылок при создании Веб-страницы

29 Августа 2013