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

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

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

ФАКУЛЬТЕТ

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

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

УТВЕРЖДАЮ

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

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

математика”

«___»__________2001г.

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

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

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

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

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

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

«___»________2001г.__________________

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

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

Оценка_______________________________________

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

Самара

2001г.

СОДЕРЖАНИЕ

Стр.

ВВЕДЕНИЕ

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

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

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

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

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

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

Рис. 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 ² = e , где e - единичный оператор. Такой оператор называется инволюцией. Можно сказать, что инволюция представляет собой корень из единицы. Примером инволюции является сложение по модулю два текста с ключом.

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

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

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

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

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

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

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

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

1.2 Потоковые шифры

Рассматриваемый нами криптоалгоритм RC4 относится к классу потоковых шифров, которые в последнее время стали популярными благодаря высокой скорости работы. Потоковые шифры преобразуют открытый текст в шифротекст по одному биту за операцию. Генератор потока ключей (иногда называемый генератором с бегущим ключом) выдает поток битов: k₁, k₂, k₃, ..., k_i. Этот поток ключей и поток битов открытого текста, p₁, p₂, p₃, ..., p_i, подвергаются операции “исключающее или", и в результате получается поток битов шифротекста.

c_i =p_i ^ k_i

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

p_i = c_i ^ k_i

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

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

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

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

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

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

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

Р
ис. 4. Самосинхронизирующийся генератор потока ключей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

i = (i+1) mod 256

j = (j+S_i) mod 256

swap (S_i, S_j)

t = (S_i+S_j) mod 256

K = S_t

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

S₀ = 0, S₁ = 1, . . ., S₂₅₅ = 255.

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

for i=0 to 255

j = (j+S_i+K_i) mod 256

swap (S_i , S_j)

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

Внутреннее состояние генератора RC4 в момент времени t состоит из таблицы S_t =(S_t(L))_t=0^{n2 -1}, содержащей 2ⁿ n-битных слов и из двух n-битных слов-указателей i_t и j_t. Таким образом, размер внутренней памяти составляет M = n2ⁿ + 2n бит. Пусть выходное n-битное слово генератора в момент t обозначается как Z_t.

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

i_t = i_t-1 + 1

j_t = j_t-1 + S_t-1(i_t)

S_t(i_t) = S_t-1(j_t)

S_t(j_t) = S_t-1(i_t)

Z_t = S_t(S_t(i_t) + S_t(j_t)),

где все сложения выполняются по модулю 2ⁿ. Подразумевается, что все слова, кроме подвергаемых перестановке, остаются теми же самыми. Выходная последовательность n-битных слов обозначается как Z_t =(Z_t )_t=1^ .Начальная таблица S₀ задается в терминах ключевой последовательности

K = (K_L)_t=0^{2n -1}

с использованием той же самой функции следующего состояния, начиная от таблицы единичной подстановки (L)²ⁿ _L=0^{2n -1}. Более строго, пусть j₀ = 0 и для каждого 1 ≤ t ≤ 2ⁿ вычисляется j_t = (j_t - 1 + S_t-1(t-1) + K_t-1) mod 2 n, а затем переставляются местами S_t-1(t-1) и S_t-1(j_t).

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

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

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

Главная цель работы Голича - с помощью метода АЛПС вывести линейные модели для RC4. Метод АЛПС заключается в нахождении и решении последовательной линейной схемы, которая аппроксимирует генератор гаммы и приводит к линейным моделям с относительно большим корреляционным коэффициентом c, где вероятность соответствующего линейного соотношения между битами гаммы составляет (1+ c)/2. При анализе использовалась техника двоичных производных. Пусть Z = (Z_t)_t=1^ обозначает последовательность самых младших бит слов выхода RC4, и пусть Z^/=( Z^/_t = Z_t+ Z_t+1) _t=1^ и Z^//=( Z^//_t = Z_t+ Z_t+2) _t=1^ обозначают ее первую и вторую двоичные производные, соответственно. Показано, что Z^/ не коррелирует ни с 1, ни с 0, но Z^// коррелирует с 1 с корреляционным коэффициентом, близким к 15*2^-3n при больших 2n, где n – длина ключа. Поскольку длина выходной последовательности, требуемая для выявления статистической слабости с корреляционным коэффициентом c, составляет O(c^-2), то эта длина равна примерно 64ⁿ /225. Например, если n = 8, как рекомендуется в большинстве приложений, то требуемая длина близка к 2⁴⁰.

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

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

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

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

S_t+1 = AS_t + BX_t + (X_t, S_t), t≥0,

y_t = CS_t + DX_t + (X_t, S_t), t ≥0,

где векторы рассматриваются как матрицы-столбцы; A, B, C, D - двоичные матрицы; а  и каждый компонент в D = (d₁, . . . , d_M) – несбалансированные булевы функции, именуемые функциями шума. Основная идея состоит в том, чтобы рассматривать {(X_t ,S_t)}_t=0^ и {(X_t ,S_t)}_t=0^ , 1≤i≤M, в качестве входных последовательностей, так что последние уравнения оказываются задающими неавтономную линейную машину с конечным числом состояний или ЛПС, именуемую АЛПС комбинирующего узла с памятью. Тогда можно решать эту ЛПС с использованием техники производящих функций (D-преобразований). В частности, пусть S, X, , , y обозначают производящие функции от переменной z для последовательностей {S_t}, {X_t}, (X_t, S_t)},  (X_t, S_t)}, y_t}, соответств
енно. Тогда уравнения сводятся к виду

Р
ешение имеет вид

где I - единичная матрица, det(zA - I) = (z), (0) = 1, - многочлен, обратный к характеристическому многочлену матрицы переходов A степени, не превышающей ранг A (≤M); а элементы (присоединенной) матрицы adj(zA - I) - это полиномы от z степени не более M-1. Вычислительная сложность для отыскания такого решения составляет O(M³(N+1)). В другом виде решение можно переписать как

г

де x_i и _j обозначают производящие функции для {x_it} и {_j(X_t, S_t)}, а степени полиномов g_i(z) и h_j(z) самое большее равны M и M-1, 1≤i≤N, 1≤j≤M, соответственно. Полагая

решение можно преобразовать к виду:

г
де подразумевается, что вектор состояния S_t-k - это функция от (X_t-k-1^M-k, S _t-M) для каждого 0≤k≤M-1. Линейные функции входа и выхода в (2) скоррелированы тогда и только тогда, когда функция шума e несбалансирована. Коэффициент корреляции не зависит от времени, если функция следующего состояния сбалансирована. Если это условие не удовлетворяется, то корреляционный коэффициент может зависеть от времени, поскольку от S_t более не требуется сбалансированность для каждого t≥0. Функция шума e в (3) определена как сумма индивидуальных шумовых функций, которые несбалансированы при условии, что сбалансирована функция следующего состояния. Поскольку от индивидуальных шумовых функций не требуется быть независимыми, в принципе нельзя исключать возможность, что коэффициент корреляции e с константной нулевой функцией равен нулю или очень близок к этому значению.

В рассматриваемом случае индивидуальные шумовые функции можно трактовать как булевы функции от n = MN + N + M переменных в (X^M+1_t , S_{t -M}). Следовательно, за исключением некоторых особых случаев, в общем случае можно с высокой вероятностью ожидать, что общий корреляционный коэффициент очень близок к произведению индивидуальных и, таким образом, отличается от нуля. Соответственно, метод АПЛС не только с высокой вероятностью дает взаимно коррелированные линейные функции от входа и выхода, но также позволяет оценить значение соответствующего корреляционного коэффициента, используя независимость или другие вероятностные предположения. Поскольку в идеальном случае хотелось бы получить такие АЛПС, в которых корреляционные коэффициенты по абсолютному значению близки к максимуму, то индивидуальные корреляционные коэффициенты должны быть крупными по величине, а количество шумовых членов в (3) должно быть маленьким. Конечно, эти требования могут противоречить друг другу. Поэтому хорошим подходом будет повторение процедуры АЛПС несколько раз, начиная с наилучших линейных аппроксимаций для функции выхода и компонент функции следующего состояния. Эта процедура может также выполняться для всех возможных линейных аппроксимаций, что представляется единственным систематическим способом проверить все корреляции, выявленные в процессе применения метода АЛПС. В общем случае имеется самое большее (M+1)2^M+N таких линейных аппроксимаций. Однако, в принципе всегда можно проверить все возможные линейные аппроксимации даже при большом M, поскольку в практических реализациях функции выхода и следующего состояния зависят от сравнительно небольшого количества переменных или же составлены из таких булевых функций.

С практической точки зрения данная линейная модель может быть использована для выделения по шифротексту генератора RC4 среди других криптосистем, а также для восстановления параметра n. В 2000 году была опубликована статья Скотта Флюера и Дэвида Мак-Гри посвященная статистистическому анализу потокового генератора RC4, в которой были использованы результаты работы Голича для нахождения значения компонент S-бокса. Приблизительное время работы этого метода составляет 2⁶ⁿ, где n – порция битов в выходном потоке, длина выходной последовательности, требуемая для выявления статистической слабости, близка к 2³⁰. Полученный результат указывает на существенную слабость генератора и возможность восстановить параметры i и n. S-бокс может принимать 2^nk, где n_k – число битов ключа.

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

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

В операционных системах Microsoft Windows 9x для аутентификации пользователя используется имя пользователя, а для подтверждения введенного имени – процедура аутентификации, использующая символьный пароль пользователя. Алгоритм этой процедуры, которая вызывается из библиотеки MSPWL32.DLL, состоит из следующих шагов:

Шаг 1. Пользователь вводит свое имя и пароль в формате Unicode.

Шаг 2. Имя и пароль преобразуется в формат ASCII, причем строчные буквы преобразуются в прописные.

Шаг 3. Осуществляется преобразование пароля с помощью с алгоритма хэширования RC4.

Шаг 4. Результат сравнивается с данными, которые вычисляются путем дешифрования данных, хранящихся в PWL-файле, в начале загрузки операционной системы.

Шаг 5. В случае успешной проверки на шаге 4 пользователь получает доступ к системным ресурсам.

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

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

Концепция безопасности компьютера подразумевает защиту всех его компонентов - аппаратные средства и приложения - от несанкционированного доступа из локальной сети или Internet. В Windows 9x любой пользователь вашего компьютера может зарегистрироваться в системе. При этом имя пользователя и пароль могут быть такими же, как и при входе в сеть.

Концепция безопасности в Windows 9x весьма примитивна. В этой системе администратор, не можете создать группу пользователей, завести учетную запись пользователя, изменить права пользователя. Вместо продвинутого “Диспетчера пользователей” эта система предлагает довольно простенькое диалоговое окно свойств “Пароли”. Windows 9x не обеспечивает достаточного уровня безопасности.

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

С помощью вкладки “Смена” паролей“ диалогового окна свойств “Пароли” изменяются параметры унифицированной регистрации всех ресурсов компьютера посредством задания нового пароля пользователя.

Задать новый пароль можно через вкладку “Настройка пользователя“. Для установки защиты на конкретный ресурс компьютера необходимо сделать его разделяемым. Windows 9x позволяет управлять ресурсами компьютера пользователям, имеющим удаленный доступ к системе. Для чего требуется добавить соответствующую службу с помощью вкладки “Сеть” и после этого в диалоговом окне свойств “Пароли” появится новая вкладка “Удаленное управление”. Таким образом проведя оценку системы безопасности Windows 9x, мы сделали вывод о ее недостаточной надежности. Стандартный набор офисного программного обеспечения Microsoft Office также недостаточно надежен, но поскольку эффективные средства его криптоанализа уже разработаны, то в данной работе эта тема не рассматривается.

2.2 Структура PWL–файлов

Для аутентификации в операционных системах Microsoft Windows 9x используются, хранящиеся в директории операционной системы, файлы *.PWL, которые содержат кэшированную парольную информацию. Какая бы то ни было документация по их структуре отсутствует, поэтому нами было проведено исследование этих файлов и было выяснен их формат.

Таблица 1.1

Структура PWL-файла.

В одном ресурсе может быть несколько парольных записей, следующих одна за другой. Первое слово каждой записи представляет собой длину записи, включая и это слово. Признаком конца цепочки записей является нулевое слово. Таким образом пустой ресурс - это просто нулевое слово. Тогда ясно, что если PWL-файл в Windows95 имеет длину 606 байт, и соответственно 688 в Windows98, то все ресурсы в нем пустые. Каждый ресурс зашифрован гаммой, которая накладывается, начиная с его начала.

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

Рис. 5. Структура PWL-файла

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

Алгоритм сопоставления ключа паролю слаб тем, что при выбранной длине ключа в двойное слово, множество различных ключей 2³² оказывается неизмеримо меньше множества различных паролей. Это означает, что существуют пароли, которые операционная система не различает.

При последующих регистрациях данным пользователем запрашивается пароль. Он приводится к верхнему регистру, опять сворачивается в ключ из которого опять порождается гамма. Если порождаемое этой гаммой имя пользователя дешифровывается правильно, то пароль считается введенным правильно. После этого дешифровываются таблица указателей на начала ресурсов и сами ресурсы. Дешифровка производится вторичным наложением гаммы сложением по модулю два. Если имя пользователя не дешифровывается правильно, то пароль считается неправильным. Таким образом проверка правильности введенного пароля производится по совпадению первых 20-и байт порожденной из него гаммы с первыми 20-ю байтами гаммы от правильного пароля. Этот алгоритм определения подлинности пароля является весьма оригинальным, т.к. нигде не сохраняется ни зашифрованный пароль, ни хеш-функция (необратимое преобразование) пароля, но, в то же время нелепо реализованным. Ведь поскольку имя пользователя известно заранее, то первые 20 байт гаммы тривиально вычисляются. Но, т.к. эта же гамма накладывается на каждый ресурс (отсутствие смены гаммы при шифровании разных полей - это основная ошибка применения алгоритма RC4 в данном случае), то можно дешифровать и первые 20 байт каждого ресурса! PWL-файл имеет избыточную информацию - есть указатели на начала ресурсов, но есть и длины записей в ресурсах и из одного можно вычислять другое. Если в ресурсах не более одной записи, то длина ресурса есть первое слово ресурса плюс два (длина первой записи ресурса плюс длина нулевого слова). Определяя по началу и длине данного ресурса начало следующего, рассчитывается вся таблица указателей на начала ресурсов. Если в ресурсах более одной записи, то начало следующего ресурса все равно можно найти. Это сводит прочность системы шифрования к нулю (под прочностью системы шифрования понимается количество вариантов, которые необходимо перебрать для ее гарантированного вскрытия).

Алгоритм генерации ключа по паролю

Имеем ключ (двойное слово) и пароль до 20-и символов.

1) Обнулить ключ.

2) Привести пароль к верхнему регистру.

3) Для каждого символа пароля, начиная с первого:

а) прибавить код символа к ключу

б) повернуть ключ влево 7 раз.

Алгоритм сопоставления ключа паролю слаб тем, что при выбранной длине ключа в двойное слово, множество различных ключей 2³² оказывается неизмеримо меньше множества различных паролей. Это означает, что существуют пароли, которые Windows 95 не отличает друг от друга. Это делает совершенно бессмысленными допускаемые в Windows 95 длинные пароли и эффективная длина пароля соответствует только пяти символам! Правда, это не означает, что для каждого пароля найдется эквивалент из пяти символов, т.к. множество паролей отображается на множество ключей неравномерно.

Между тем, достаточно было накладывать гамму на ресурсы, не используя первых засвеченных ее байт, что и было реализовано в следующих версиях. Таким образом, в механизме безопасности операционной системы Microsoft Windows 95 обнаружена существенная ошибка. Для ее исправления необходимо модернизация операционной системы. Кроме того, в новых версиях длина пароля ограничена не 32 байтами, а 128.

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

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

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

1. использования достижений научно-технического прогресса и применения технологических новинок для увеличения производительности отдельного устройства;

2. увеличения количества процессоров в системе.

С физической точки зрения транзистор, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 микрон. За этой гранью процесс включения/выключения микроскопических переключателей станет практически невозможным. Таким образом максимальное быстродействие составит - 10¹⁶ операций/секунду, а предел роста наступит приблизительно в 2030 г.

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

Предположим, что размер процессора равен размеру атома. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой F = V_c/R_a = 3 * 10¹⁸ операций в секунду, где V_c = 3 * 10 ⁸ м/с скорость света в вакууме, а R_a = 10^-10 м - размеры атомов. Столько раз за 1 секунду свет пройдет размеры атома. Поскольку период обращения Земли вокруг Солнца составляет 365,2564 суток или 31 558 153 секунд, то за один год такой процессор выполнит 94 674 459 * 10¹⁸  10²⁶ операций. Более быстрый процессор в нашей вселенной невозможен в принципе.

Один такой процессор по быстродействию превосходит более двух миллионов самых современных суперкомпьютеров Intel ASCI Red стоимостью 55млн долл., работающих одновременно, и состоящих из 9152 процессоров Pentium каждый, точное значение - 2 242 152,466. Производительность одного процессора в системе Intel ASCI Red - 1,456 * 10⁸ операций в секунду.

За 100 лет непрерывной работы гипотетический процессор совершит приблизительно 10²⁸ операций. При условии, что за один такт своей работы он проверяет один ключ, а расшифровка сообщения на найденном ключе происходит мгновенно, то он сможет перебрать 10²⁸ ключей, т.е. длина ключа составит всего лишь 93 бита! Очевидно, что создать еще более быстродействующую систему возможно только увеличивая количество процессоров в системе.

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

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

Таблица 2.1

Десять самых мощных суперкомпьютеров в мире.

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

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

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

Таблица 2.2

Время, необходимое для полного перебора ключей

Таким образом с помощью указанной рабочей модели можно оценивать надежность проектируемых и эксплуатируемых систем шифрования. Алгоритм ГОСТ 28147-89 использует таблицу подстановок размером 512 бит. Общее число возможных таблиц составляет 1.33*Е36 и полное время перебора составляет 3.162*Е16 лет. Для алгоритма IDEA длина ключа составляет 128 бит и полное время перебора составляет 8.09*Е18 лет. Даже если будет использован суперкомпьютер состоящий из ста тысяч процессоров с максимально возможной скоростью в 10¹⁶ операций/секунду для расшифровывания ГОСТа понадобится 4.21*Е7 лет, а для IDEA - 1.08*Е10 лет. Очевидно, что даже применение нескольких сотен суперкомпьютеров Intel ASCI Red, стоимостью по 55 миллионов долларов каждый, не в стоянии кардинально улучшить ситуацию.

Анализируя предельные значения второй тенденции, можно отметить, что увеличению количества процессоров в системе тоже есть свой предел.

Для нашей планеты естественным пределом является площадь земной поверхности. Если выразить поверхность земного шара (считая океаны, пустыни, Арктику с Антарктикой) в квадратных миллиметрах, и на каждый миллиметр поместить по миллиону таких процессоров, то в год мощность такого вычислительного устройства составит 5.1 * 10⁵² операций, что эквивалентно длине в 175-176 бит. Если исходить из предположения, что стойкость шифра должна составлять 100 лет, то за указанный период такая система сможет перебрать 5 *10⁵⁴ ключей, что составит 181-182 бита. И это притом, что никакие вычислительные ресурсы процессоров не тратятся на согласование их взаимной работы в системе, на решение задачи дешифрования и т.д.

Таблица 2.3

Варианты перебора ключа раскладок клавиатуры

Из проведенного нами исследования можно сделать вывод, что для обеспечения надежности достаточно использовать алгоритмы с длиной ключа не менее 64 битов, а применять и разрабатывать алгоритмы с длиной ключа более 128 бит экономически не выгодно. Однако, как правило, для генерации ключа используется пароль, который в свою очередь часто содержит лишь символы латинского алфавита. В таком случае для обеспечения необходимой защиты требуется использовать пароль не короче 12 символов, что соответствует 56-битному ключу. 16-символьный гарант пароль соответствует 75-битному ключу и гарантирует достаточную защиту от прямой атаки.

3.2 Разработка программы

На текущий момент имеется несколько языков программирования высокого уровня, позволяющих создавать полноценные программы, предназначенные для работы в среде Microsoft Windows 9x. Мы выбрали хорошо известный язык C++, который обладает следующими достоинствами: во-первых, C++ обладает универсальностью и может быть использован для создания программ любого уровня сложности, а во-вторых, эффективный машинный код обеспечивает высокую скорость работы программы, что особенно немаловажно. Применяемые библиотеки и разработанные программные функции описаны ниже:

Таблица 3.1

Использованные библиотеки

Таблица 3.2

Программные процедуры

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

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

Алгоритм генерации ключа по паролю в Microsoft Windows 95

Имеем ключ (двойное слово) и пароль до 20-и символов.

1) Обнулить ключ.

2) Привести пароль к верхнему регистру.

3) Для каждого символа пароля, начиная с первого:

а) прибавить код символа к ключу

б) повернуть ключ влево 7 раз.

Данный алгоритм слаб тем, что при выбранной длине ключа в двойное слово, множество различных ключей 2³² оказывается неизмеримо меньше множества различных паролей. Это означает, что существуют пароли, которые операционная система не различает.

Для PWL-файлов, создаваемых новыми версиями в операционных системах Microsoft Windows OSR2 и 98, программа осуществляет перебор ключей.

Алгоритм генерации ключа по паролю в Microsoft Windows OSR2 и 98

Имеем ключ (двойное слово) и пароль до 128-и символов.

1) Обнулить ключ.

2) Привести пароль к верхнему регистру.

3) Для каждого символа пароля, начиная с первого:

а) прибавить код символа к ключу

б) повернуть ключ влево 16 раз.

Далее программа перебирает пароли до тех пор, пока расшифрованное имя пользователя не совпадет с ранее введенным. При совпадении работа заканчивается.

Таблица 3.3

Скорость работы программы

Продолжение сессии

Просмотр файла

Взлом файла по ключу

Рис. 6. Блок-схема основной программы.

3.3 Функции программы

Разработанная программа запускается из командной строки с ниже перечисленными ключами:

/BF[:S] [ИмяPwlФайла] [ИмяПользователя]

- для выполнения взлома PWL-файла перебором. Пароли последовательно будут изменяться и проверяться на корректность совпадения.

/EN: [ИмяСекцииПеребора]

- добавьте это к ключу /BRUTEFORCE для того, чтобы выбрать желаемую секцию перебора из .CFG файла. Секция перебора по умолчанию описана в конфигурационном файле.

/F: [СтартоваяДлина]

- добавьте это к ключу /BRUTEFORCE для определения желаемой длины начального пароля с которого начнется процесс перебора. По умолчанию длинна равна нулю.

/IN: [НачальныйПароль]

- добавьте это к ключу /BRUTEFORCE для выбора начального пароля. Перебор начнется с значения представленного данным ключем. Этот ключ несовместим с ключем /FROM.

/D: [ПарольОстановки]

- добавьте это к ключу /BRUTEFORCE для выбора пароля остановки. Перебор завершится при достижении данного пароля. Этот ключ несовместим с ключем /NUMBER.

/NUM: [КоличествоИтераций]

- добавьте это к ключу /BRUTEFORCE для выбора количества попыток перебора. Программа будет остановлена после совершения данного количества переборов паролей. Этот ключ несовместим с ключем /DONE.

/VOC [:S] [ИмяPwlФайла] [ИмяПользователя] [МаскаСловарей]

- для обнаружения пароля PWL-файла с помощью словаря.

/CON [:S] [ИмяФайлаСессии]

- для возобновления прерванной сессии.

/PROT [:ИмяФайлаПротокола]

- добавление этого ключа к некоторым ключам позволит сохранять результаты работы в файле Протокола. /ABOUT /HELP, /?, /LIST и /SPY, /GRAB не допускают применение данного ключа.

/L [:E] [ИмяPwlфайла] [ИмяПользователя] [ПарольПользователя]

- для просмотра указанного PWL-файла с соответствующими параметрами, используйте атрибут 'E' для отображения технической информации.

/GR [ИмяПротоколаБазы]

- для просмотра секции [Password Lists] файла SYSTEM.ini. Эта секция описывает зарегистрированные PWL-файлы на данной машине.

/TM [ОценочнаяСкорость]

- для оценки времени работы сплошного перебора. Можно использовать ключ /ENUM для выбора секции символов перебора. Скорость указывается в pps (что обозначает паролей в секунду).

/H [ИмяФайлаСправки]

- для сохранения справки в текстовом файле.

/?

- для отображения этой краткой справки на терминале.

Используйте атрибут 'S' с вышеперечисленными ключами для защиты данных от нестабильности электропитания. Применение атрибута вызовет периодическое сохранение результатов работы текущей сессии. Нажатие Ctrl+Break приводит к остановке процесса перебора и записи текущей сессии в соответствующем .BRK файле.

ЗАКЛЮЧЕНИЕ

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

В ходе работы был сделаны следующие выводы:

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

• На компьютерах с операционной системой Microsoft Windows 95 необходимо модернизировать операционную систему. Поскольку переход на программное обеспечение других фирм вызовет значительные сложности, то достаточно ограничиться новыми версиями OSR2 и Windows 98.

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Андреев Н.Н. О некоторых направлениях исследований в области защиты информации.// Международная конференция “Безопасность информации”. Сборник материалов, М., 1997, c. 94-97

2. Баpичев С.С., Гончаров В.В., Серов Р.Е. Основы современной кpиптогpафии. М.: Мир, 1997. 176 с.

3. Болски М.И. Язык программирования Си. М.: Радио и связь, 1988. 96 с.

4. Буза М.К. Операционная среда Windows 95 и ее приложения. М.: ДиаСофт, 1996. 266 с.

5. Елманова Н.З., Кошель С.П. “Введение в Borland C++ Builder”. М.: Диалог-МИФИ, 1998. 675 с.

6. Грушо А.А. Тимонина Е.Е. Теоретические основы защиты информации М.: Яхтсмен, 1996. 31 с.

7. Домашев А. В., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. Программирование алгоритмов защиты информации. М.: Нолидж, 2000. 288 с.

8. Варфоломеев А.А., Жуков А.Е., Мельников А.Б., Устюжанин Д.Д. Блочные криптосистемы. Основные свойства и методы анализа стойкости. М.: МИФИ, 1998. 200с.

9. Леонтьев Б. Операционная система Microsoft Windows 9x для начинающих и не только. М.: Нолидж, 1998. 496 с.

10. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. СПб.: Лань, 2000. 224 с.

11. Семьянов П.В. Почему криптосистемы ненадежны? Тезисы доклада на конф. “Методы и технические средства обеспечения безопасности информации”, . СПб.: ГТУ, 1996. 18 с.

12. Спесивцев А. В. Защита информации в персональных ЭВМ. М.: Мир, 1992. 278 с.

13. Ростовцев А.Г., Матвеев В.А. Защита информации в компьютерных системах. Элементы криптологии. Под редакцией П.Д. Зегжды. СПб.: ГТУ, 1993. 365 с.

14. Fluhrer S.R., McGrew D.A. Statistical analysis of the alleged RC4 keystream generator. Fast Software Encryption, Cambridge Security Workshop Proceedings, 2000. p. 127-139.

15. Golic J.Dj. Linear models for keystream generators. IEEE Transactions on Computers, Vol. 45. January 1996. p. 41-49.

16. Menezes A.J., Oorschot P.C., Vanstone S.A. Handbook of Applied Cryptography. N.Y.: CRC-Press, 1996. 780 p.

17. Rivest R. L. The RC4 Encryption Algorithm. Dr. Dobb’s Journal. January 1995. p. 146 – 148.

18. Schneier B. Applied Cryptography. N. Y.: John Wiley & Sons Inc., 1996. 757 p.

ПРИЛОЖЕНИЕ

ТЕКСТ ПРОГРАММЫ ДЛЯ АНАЛИЗА PWL-ФАЙЛОВ

ВСТУПЛЕНИЕ

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

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

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

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

АЛГОРИТМ RC4

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

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

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

• высокой скоростью.

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

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

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

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

Как и все потоковые алгоритмы, RC4 генерирует гамму, которая используется для шифрования. Криптогенератор имеет подстановочную таблицу (S-бокс 8 х 8): S₀, S₁, . . ., S₂₅₅. Входами генератора являются числа от 0 до 255. Подстановка является функцией от ключа изменяемой длины. Генератор имеет два счетчика i и j, инициализируемых нулевым значением.

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

i = (i+1) mod 256

j = (j+S_i) mod 256

swap (S_i, S_j)

t = (S_i+S_j) mod 256

K = S_t

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

S₀ = 0, S₁ = 1, . . ., S₂₅₅ = 255.

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

for i=0 to 255

j = (j+S_i+K_i) mod 256

swap (S_i , S_j)

Схема показывает, что RC4 может принимать примерно 2¹⁷⁰⁰ (256! * 256²) возможных состояний. S-бох медленно изменяется в процессе работы: параметр i обеспечивает изменение каждого элемента, а j отвечает за то, чтобы эти элементы изменялись случайным образом.

До последнего времени в открытой литературе практически не было публикаций по криптоанализу алгоритма RC4. Компания RSA Data Security объявила, что шифр обладает иммунитетом к методам линейного и дифференциального криптоанализа, высоко не линеен и не похоже, чтобы у него были короткие циклы.

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

Длина выходной последовательности, требуемая для выявления статистической слабости с корреляционным коэффициентом c, составляет O(c^-2), то требуемая длина близка к 2⁴⁰. С практической точки зрения данная линейная модель может быть использована для выделения по шифротексту генератора RC4 среди других криптосистем, а также для восстановления параметра n.

В 2000 году была опубликована статья Скотта Флюера и Дэвида Мак-Гри посвященная статистистическому анализу потокового генератора RC4. Полученные в ней результаты сократили длину выходной последовательности, необходимой для выявления статистической слабости, до 2³⁰. Полученный результат указывает на существенную слабость генератора.

WINDOWS 95, 98

В операционных системах Microsoft Windows 95, 98 для аутентификации пользователя используется имя пользователя, а для подтверждения введенного имени – процедура аутентификации, использующая символьный пароль пользователя.

Управление доступом к ресурсам в операционных системах Windows 95, 98 осуществляется с помощью механизма профилей. Для этого создаются профили пользователей. Профиль пользователя в хранится в файле user.dat, который содержит учетную запись пользователя. Все профили системы содержатся в этом файле.

Для аутентификации в операционных системах Microsoft Windows 95, 98 используются, хранящиеся в директории операционной системы, файлы *.PWL, которые содержат хешированную парольную информацию. Документация по их структуре отсутствует, поэтому нами было проведено исследование этих файлов и было выяснен их формат.

PWL-файл шифруется простым гаммированием, гамма генерируется по алгоритму RC4. При регистрации пользователя запрашивается пароль. Далее пароль приводится к верхнему регистру и сворачивается в ключ. Из этого ключа порождается гамма и накладывается на файл сложением по модулю два. Если порождаемое этой гаммой имя пользователя дешифровывается правильно, то пароль считается введенным правильно и после чего дешифровываются остальной файл.

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

Но при реализации этого алгоритма в Microsoft Windows 95 была допущена следующая ошибка: поскольку имя пользователя известно заранее, то первые 20 байт гаммы тривиально вычисляются. Но, т.к. эта же гамма накладывается на каждый ресурс, то можно дешифровать и первые 20 байт каждого ресурса! Отсутствие смены гаммы при шифровании разных полей - это основная ошибка применения алгоритма RC4 в данном случае. Между тем, достаточно было накладывать гамму на ресурсы, не используя первых засвеченных ее байт, что и было реализовано в Microsoft Windows 98 обнаружена существенная ошибка.

Другая ошибка заключается в том, что алгоритм сопоставления ключа паролю слаб тем, что при выбранной длине ключа, множество различных ключей 2³² оказывается неизмеримо меньше множества различных паролей. Это означает, что существуют пароли, которые Windows 95 не отличает друг от друга. Это делает совершенно бессмысленными допускаемые в Windows 95 длинные пароли и эффективная длина пароля соответствует только пяти символам! Правда, это не означает, что для каждого пароля найдется эквивалент из пяти символов, т.к. множество паролей отображается на множество ключей неравномерно. В Microsoft Windows 98 эта ошибка была также исправлена и теперь длина ключа составляет не 32, а 128 бит.

Зависимость криптостойкости от ключа

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

1. увеличения производительности отдельного процессора.

2. увеличения количества процессоров в системе.

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

Предположим, что размер процессора равен размеру атома. Тогда в наших обозначениях быстродействие гипотетического процессора выразится формулой F = V_c/R_a = 3 * 10¹⁸ операций в секунду, где V_c = 3 * 10 ⁸ м/с скорость света в вакууме, а R_a = 10^-10 м - размеры атомов. Столько раз за 1 секунду свет пройдет размеры атома. Поскольку период обращения Земли вокруг Солнца составляет 365,2564 суток или 31 558 153 секунд, то за один год такой процессор выполнит 94 674 459 * 10¹⁸  10²⁶ операций. Более быстрый процессор в нашей вселенной невозможен в принципе.

За 100 лет непрерывной работы гипотетический процессор совершит приблизительно 10²⁸ операций. При условии, что за один такт своей работы он проверяет один ключ, а расшифровка сообщения на найденном ключе происходит мгновенно, то он сможет перебрать 10²⁸ ключей, т.е. длина ключа составит всего лишь 93 бита!

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

Анализируя предельные значения второй тенденции, можно отметить, что увеличению количества процессоров в системе тоже есть свой предел.

Для нашей планеты естественным пределом является площадь земной поверхности. Если выразить поверхность земного шара (считая океаны, пустыни, Арктику с Антарктикой) в квадратных миллиметрах, и на каждый миллиметр поместить по миллиону таких процессоров, то в год мощность такого вычислительного устройства составит 5.1 * 10⁵² операций, что эквивалентно длине в 175-176 бит. Если исходить из предположения, что стойкость шифра должна составлять 100 лет, то за указанный период такая система сможет перебрать 5 *10⁵⁴ ключей, что составит 181-182 бита. И это притом, что никакие вычислительные ресурсы процессоров не тратятся на согласование их взаимной работы в системе, на решение задачи дешифрования и т.д.

Из проведенного исследования можно сделать вывод, что для обеспечения надежности достаточно использовать алгоритмы с длиной ключа не менее 64 битов, а применять и разрабатывать алгоритмы с длиной ключа более 128 бит экономически не выгодно. Однако, как правило, для генерации ключа используется пароль, который в свою очередь часто содержит лишь символы латинского алфавита. В таком случае для обеспечения необходимой защиты требуется использовать пароль не короче 12 символов, что соответствует 56-битному ключу. 16-символьный пароль соответствует 75-битному ключу и гарантирует достаточную защиту от прямой атаки.

Программа анализа PWL-файлов

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

Для PWL-файлов, создаваемых новыми версиями в операционных системах Microsoft Windows OSR2 и 98, программа осуществляет перебор ключей. Программа перебирает пароли до тех пор, пока расшифрованное имя пользователя не совпадет с ранее введенным. При совпадении работа заканчивается.

Выводы PWL-файлов

Проанализировав сегодняшнюю ситуацию с реальными криптографическими продуктами, мы пришли к выводу, что криптография, представленная на коммерческом рынке, не предоставляет достаточного уровня безопасности. Сегодня в компьютерную безопасность вкладываются миллиарды долларов, и большинство денег тратится на нестойкие продукты. В настоящей работе было проведено исследование криптографических методов защиты информации, применяемых популярных операционных системах семейства Microsoft Windows 95, 98, и была написана программа общим объемом около тысячи строк программного кода для анализа си. Рассматриваемый алгоритм RC4 используется в более чем двадцати программных продуктах и результаты данной работы относятся к большому числу программных продуктов, используемых в различных областях.

В ходе работы был сделаны следующие выводы:

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

• На компьютерах с операционной системой Microsoft Windows 95 необходимо модернизировать операционную систему. Поскольку переход на программное обеспечение других фирм вызовет значительные сложности, то достаточно ограничиться новыми версиями OSR2 и Windows 98.

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

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

Отзыв

на выпускную квалификационную работу «Анализ криптостойкости методов защиты информации в операционных системах MS Windows 9x» студента специальности 010200 «Прикладная математика и информатика» 8 группы V курса дневного отделения инженерно-экономического факультета СамГТУ Альперта Владимира Владимировича

Данная выпускная квалификационная работа посвящена актуальной теме – криптоанализу и оценке криптостойкости методов защиты информации.

В процессе выполнения работы студент Альперт В.В. изучил современные методы криптоанализа для потоковых шифров, в частности, для алгоритма RC4, применяемого в операционных системах Microsoft Windows 9x. На основе проведенного анализа была разработана программа на языке С++ для оценки зависимости криптостойкости методов защиты информации от длины ключа. В результате проведенных исследовательских расчетов установлено, что предлагаемые фирмой методы защиты информации в операционной системе Windows 95 не обладают рекламируемой криптостойкостью. Этот факт подтвержден изменениями методов защиты в операционной системе MS Windows 98. Объем проведенного теоретического анализа и высокой качество разработанной программы свидетельствуют о достаточной глубине знаний и отличных навыках программирования у студента Альперт В.В.

В целом, данная выпускная работа удовлетворяет требованиям, предъявляемым квалификационным работам по специальности «Прикладная математика и информатика» и заслуживает отличной оценки.

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

Доцент, кандидат технических наук В.П. Пономарев

Внутреннее состояние
Функция выхода

Внутреннее состояние

Функция выхода

Ключ

Шифротекст Открытый текст Открытый текст Шифрование Дешифрование Инициализация криптогенератора

for i=0 to 255 for i=0 to 255
S_i =0 j = (j+S_i+K_i) mod 256
swap (S_i , S_j)

Функция выхода i = (i+1) mod 256; j = (j+S_i) mod 256
swap (S_i, S_j)
t = (S_i+S_j) mod 256
K = S_t