Помоги проекту - поделись книгой:
В качестве примера рассмотрим велосипедный замок, который открывается набором ключевой комбинации из трех цифр. Каждая цифра – это число от 0 до 9. Открыть замок нетрудно, если располагать временем и если ключевая комбинация во время вскрытия замка не изменяется. Общее число всевозможных комбинаций (ключей) – 10 3 , или 1000. Предположив, что велосипедный вор способен перебирать 30 комбинаций в минуту, определим, что в худшем для него случае он откроет замок приблизительно через 1000: 30 = 33 мин. При этом имейте в виду, что после выбора очередной комбинации число возможных комбинаций (ключевое пространство) уменьшается, а шансы угадать ключевую комбинацию на следующем шаге увеличиваются.
Метод «грубой силы» всегда приводит к успеху, потому что ключевое пространство, как бы велико оно ни было, всегда конечно. Противостоять «грубой силе» можно, увеличивая длину ключа и тем самым время расшифровки сообщения. В случае примера с велосипедным замком три цифры ключевого пространства позволят велосипедному вору украсть велосипед максимум за 33 мин. Поэтому для велосипедного вора в данном случае метод «грубой силы» выглядит привлекательным. Рассмотрим велосипедный замок с ключевой комбинацией из пяти цифр, для которого число возможных комбинаций равно 100 000. Теперь для подбора ключевой комбинации методом «грубой силы» потребуется 55,5 ч. Ясно, что большинство воров отказалось бы от этой затеи и искало бы более легкую добычу.
Суть метода «грубой силы» применительно к симметричным алгоритмам, например к DES, аналогична подбору ключевых комбинаций велосипедного замка. Именно таким образом алгоритм DES был взломан компьютером «Deep Crack» («Искусный взломщик»). Ключ DES состоит из 56 бит, поэтому при взломе проверялись все битовые комбинации ключа между строкой из 56 нулей и 56 единиц, пока не был найден нужный ключ.
В случае распределенных попыток взлома DES пример с пятицифровым велосипедным замком должен быть слегка изменен. Идею метода распределенной «грубой силы» можно проиллюстрировать на примере подбора ключевой комбинации несколькими ворами, действующими одновременно и имеющими в своем распоряжении точную копию велосипедного замка, закрытого одной и той же ключевой комбинацией оригинала. Предположим, что 50 воров пытаются одновременно подобрать ключевую комбинацию. Каждый из них должен перебрать 2000 комбинаций (подпространство ключей). Причем ни у каких двух воров подпространства ключей не пересекаются. В таком случае каждую минуту тестируется ни 30 комбинаций, а 1500 комбинаций в минуту, и все возможные комбинации могут быть проверены приблизительно за 67 мин. Вспомните, что ранее одному вору требовалось для подбора ключевой комбинации 55 ч, а 50 совместно подбирающих комбинации воров смогут украсть велосипед за время, едва превышающее 1 ч. Распределенные компьютерные приложения, основанные на тех же принципах, позволили Distributed.net взломать DES менее чем за 24 ч.
Использовать метод «грубой силы» к RSA и к другим криптосистемам с открытым ключом сложнее. Поскольку алгоритм RSA может быть раскрыт разложением ключа на сомножители, то при небольшой длине используемых ключей (намного меньше, чем любая программная реализация RSA смогла бы себе позволить) человек с помощью карандаша и бумаги сможет взломать алгоритм. Но для ключей с большим количеством битов время нахождения сомножителей ключа (время факторизации) резко возрастает. Кроме того, факторизацию трудно реализовать распределенными вычислениями. Атаки, основанные на распределенной факторизации, потребуют большей координации действий участников атаки, чем при параллельном подборе ключей из ключевого пространства. Известны проекты, например проект www-факторизации (www.npac.syr.edu/factoring.html), предназначенные для решения этих вопросов. В настоящее время в рамках проекта www-факторизации предпринимаются попытки разложить на сомножители ключи со 130 цифрами. Для сравнения 512-битовые ключи приблизительно состоят из 155 цифр.
Применение метода «грубой силы» для расшифровки паролей
Часто, особенно если доступен список зашифрованных паролей, для расшифровки паролей используется метод «грубой силы». Обычно точное число символов в пароле неизвестно, но в большинстве случаев справедливо полагать, что в пароле от 4 до 16 символов. Одному символу пароля может быть присвоено около 100 значений, поэтому число паролей изменяется от 1004 до 10016. Несмотря на внушительные числа, они конечны, поэтому пароль может быть определен с помощью атаки методом «грубой силы».
Перед обсуждением применения специальных методов «грубой силы» следует кратко пояснить вопросы шифрования паролей. Большинство современных операционных систем в интересах безопасности применяют кэширование паролей. Безопасность систем усиливается в результате того, что пароли никогда не хранятся на сервере в открытом виде. Даже если неавторизованный пользователь получит доступ к списку паролей, то он не сможет немедленно воспользоваться им. Поэтому у администратора всегда будет возможность поменять важные пароли до того, как ими воспользуются в зловредных целях.
Обычно пароли хранятся в формате
Определение паролей методом «грубой силы» обычно сводится к следующему. Крадутся копии имен пользователей и список кэшированных значений паролей. А затем при помощи известной функции кэширования методично вычисляются кэш-величины всевозможных паролей. Пароль считается взломанным при совпадении украденной и вычисленной кэш-величины. Некоторые варианты метода грубой силы предполагают простой перебор всевозможных паролей при попытке подключения через удаленный доступ. Но такие случаи наблюдаются редко из-за предусмотренной в системе блокировки учетной записи и имеющихся в распоряжении системного администратора средств, позволяющих легко определить и отследить подобные попытки (блокировка учетной записи – элемент безопасности Windows NT, блокирующий учетную запись пользователя, если в течение определенного интервала времени было предпринято определенное число неудачных попыток входа в систему). К тому же они слишком медленны.
Правильный выбор пароля уменьшает его шансы оказаться взломанным, но не исключает их совсем. Выбор простых паролей, например осмысленных слов языка, облегчает подбор пароля в результате простой
Наиболее часто для вскрытия паролей методом «грубой силы» используются программы L0phtcrack для Windows и Crack and John the Ripper для UNIX. Их применяют не только зловредные хакеры. Специалисты в области безопасности считают их полезными при аудите компьютерных систем. Ведь зная, сколько времени потребуется на взлом пароля специалисту в области безопасности, можно приблизительно оценить время, необходимое злоумышленнику для того, чтобы сделать то же самое. Далее будет кратко рассказано о каждой их этих программ. Но помните, что всегда следует получить письменное разрешение системного администратора на их использование до начала применения любой из этих программ.
Программа L0phtcrack
Организация L0pht выпустила в 1997 году программу L0phtCrack – инструментальное средство аудита паролей для Windows NT. В ней реализовано несколько способов восстановления паролей по их кэш-величинам, основанным главным образом на методе «грубой силы». Выбираемый набор символов определяет время и производительность, необходимые для перебора ключевого пространства. Очевидно, что чем больше символов в пароле, тем больше времени уйдет на атаку. Но атаки со словарем, которые для взлома паролей используют слова из базы данных паролей, обычно эффективны и не требуют много времени для вскрытия «слабых» паролей. В таблице 6.1 показана зависимость времени вскрытия паролей программой L0phtcrack 2.5 от выбранного набора символов.
Таблица 6.1.
Время взлома паролей программой L0phtcrack 2.5 в результате атаки методом «грубой силы» на процессоре Quad Xeon 400 МГц
L0pht Heavy Industries – разработчик L0phtcrack продала права на программу @stake Security. После покупки @stake Security выпустила программу под названием LC3, которая является преемником L0phtcrack. LC3 – это усовершенствованная версия L0phtcrack 2.5, в которую добавлены возможности распределенного поиска паролей и простое приложение пассивного прослушивания сети, позволяющее перехватывать передаваемые по Ethernet кэши паролей. Дополнительно в состав LC3 включен мастер взлома паролей, помогающий в проведении аудита системных паролей менее квалифицированным пользователям. На рисунке 6.2 представлен отчет атаки со словарем на простые пароли пользователя программной LC3.
В программе LC3 можно найти ряд усовершенствований программы L0phtcrack 2.5. Перепроектированный пользовательский интерфейс – одно из них. L0phtCrack и LC3 – коммерческие пакеты программ, но 15-дневную пробную версию программы можно получить по адресу www.atstake.com/research/lc3/download.html. Утилита Crack
Одна из самых ранних и широко используемых утилит взлома паролей называется просто
John the Ripper – очередная программа взлома паролей. Она отличается от Crack тем, что работает под управлением UNIX, DOS и Win32. Crack больше подходит для систем старшего поколения, использующих алгоритмы crypt(), а John the Ripper – для современных систем, работающих по алгоритму MD5 и соответствующих ему форматов паролей. В основном John the Ripper используется против паролей UNIX, но выпущены расширения программы, позволяющие взламывать другие типы паролей, например кэш-величины паролей Windows NT LanManager (LANMAN) или пароли сервера Netscape LDAP (Netscape Lightweight Directory Access Protocol – реализация компанией Netscape упрощенного протокола службы каталогов). Программа John the Ripper поддерживает режим запоминания результата
Пример экранной формы программы John the Ripper показан на рис. 6.3, где дана вскрытая простая секция файла паролей в формате OpenBSD. Показанный ниже фрагмент файла паролей – отчет работы программы John the Ripper. На консоль выводится каждый подобранный пароль. Выведенное на консоль время подбора четырех паролей едва превышает 1 мин только потому, что автор поместил действующие пароли в начало списка паролей, используемого программой как словарь паролей. В действительности подбор паролей займет намного больше времени. После взлома файла паролей при помощи опции show его можно отобразить в читаемом виде.
Неверное использование алгоритмов шифрования
Теоретически, имея достаточно времени, атакой «грубой силы» можно взломать любой криптографический алгоритм, но не стоит этим обольщаться, если время взлома больше времени существования вселенной. Поэтому любой «разумный» метод, позволяющий хакеру сократить время расшифровки сообщения, предпочтительнее метода «грубой силы».
Ни один из упомянутых в этой главе алгоритмов не имеет каких-либо серьезных недостатков. Но иногда некорректное использование алгоритма приводит к возникновению уязвимостей. Именно благодаря ошибкам реализации признанных криптографических алгоритмов разработчиками программного обеспечения или неверной конфигурации пользователя «разумные» методы расшифровки сообщений приводят к успеху. В этой секции будет рассказано о нескольких случаях неправильного использования алгоритмов шифрования, с которыми, возможно, столкнется читатель.
Неверно организованный обмен ключами
Поскольку в алгоритме Диффи-Хеллмана не предусмотрена проверка подлинности участвующих в обмене ключами лиц, то он уязвим к атакам типа MITM – «злоумышленник посередине» (man-in-the-middle attacks). Протокол SSH-1 – наиболее известный пример, подтверждающий сказанное. Поскольку в протоколе не предусмотрено подтверждение подлинности клиента или сервера, то нельзя исключить возможность прослушивания коммуникаций. Именно это стало одной из главных причин пересмотра протокола SSH-1 и замены его на протокол SSH-2. В протоколе SSH-2 предусмотрено установление подлинности сервера или клиента. В зависимости от настроек протокола SSH-2 предупреждает или предотвращает атаки типа MITM, после того как клиент и сервер связались между собой хотя бы один раз. Но даже протокол SSH-2 уязвим к атакам типа MITM до первого ключевого обмена между клиентом и сервером.
В качестве примера атаки типа MITM рассмотрим следующую ситуацию. Пусть Алиса, используя алгоритм Диффи-Хеллмана, впервые обменивается ключами с Чарли, и их трафик проходит через сегмент сети, контролируемый Бобом. Если Боб не вмешался в обмен ключами, то он не сможет расшифровать и прочитать сообщения Алисы и Чарли, передаваемые через контролируемый им сегмент сети. Но предположим, что Боб, перехватив открытые ключи Алисы и Чарли, послал им свой собственный открытый ключ. Тогда Алиса будет уверена, что открытый ключ Боба – это открытый ключ Чарли, а Чарли будет думать, что открытый ключ Боба – это открытый ключ Алисы.
При пересылке Алисой сообщения Чарли она зашифрует его открытым ключом Боба. Боб перехватит это сообщение и расшифрует его, используя свой секретный ключ. Прочитав сообщение, он зашифрует его открытым ключом Чарли и перешлет ему. По своему желанию он может даже изменить сообщение. Чарли, получив подмененное Бобом сообщение, полагает, что оно пришло от Алисы, и отвечает ему, шифруя ответное сообщение открытым ключом Боба. Боб снова перехватывает сообщение, расшифровывает его своим секретным ключом, изменяет и зашифровывает сообщение открытым ключом Алисы и отсылает его. Алиса, получив сообщение, уверена, что оно от Чарли.
Ясно, что такой обмен нежелателен, потому что третье лицо не только может получить доступ к конфиденциальной информации, но и изменить ее по своему желанию. При этом типе атак криптографические алгоритмы не взламываются, потому что для Боба секретные ключи Алисы и Чарли остались неизвестными. Так что фактически алгоритм Диффи-Хеллмана не взломан. Следует осторожно подходить к использованию механизма обмена ключами, реализованному в любой криптосистеме с открытым ключом. Если протокол обмена ключами не поддерживает установления подлинности одной, а лучше двух сторон, участвующих в обмене информации, то он может быть уязвим к атаке типа MITM. В системах аутентификации используются цифровые сертификаты (обычно X.509 – стандарт на шифрование данных при их передаче в сетях), например поставляемые Thawte или VeriSign.
Кэширование пароля по частям
Ранние версии клиентов Windows запоминали пароли в формате кэш-величин LanManager (LANMAN), который на самом деле чрезвычайно опасен с точки зрения безопасности аутентификации. Но поскольку эта глава посвящена криптографии, то обсуждение аутентификации LANMAN будет ограничено обсуждением уязвимостей хранения паролей.
Так же как и в UNIX, пароли LANMAN никогда не хранятся в читаемом формате. Они всегда записаны в формате кэш-величин. Ошибка заключается в том, что, несмотря на использование для шифрования паролей криптостойкого алгоритма DES, формат хранения кэшированных величин таков, что его можно относительно просто вскрыть. Каждый пароль должен состоять из 14 символов. Если в пароле менее 14 символов, то он дополняется до 14 символов. При шифровании пароль разбивается на две половинки по 7 символов в каждой, каждая из которых зашифрована алгоритмом DES. Результирующая кэш-величина пароля состоит из двух соединенных половинок пароля, зашифрованных алгоритмом DES.
Поскольку известно, что DES – это криптостойкий алгоритм, то в чем ошибка реализации? Разве просто взломать алгоритм DES? Не все так просто. Вспомните, что существует приблизительно 100 символов, которые можно использовать для записи пароля. Выбирая пароли из 14 символов, получается около 100 14 или 1.0x10 28 возможных вариантов. Пароли LANMAN сильно упрощены, потому что в них прописные и строчные буквы не различаются: все символы представлены прописными буквами. Более того, если пароль состоит менее чем из 8 символов, то вторая половинка всегда идентична первой и нет необходимости в ее взломе. Если используются только буквы (без цифр и знаков пунктуации), то число всевозможных комбинаций пароля сокращается до 26 7 (грубо говоря, до 8 млрд). Это число может показаться слишком большим для атаки «грубой силы», но вспомните, что это теоретическая оценка наибольшего числа возможных комбинаций. А поскольку большинство паролей пользователей повторяются, то атака со словарем приведет к успеху быстрее. Суть в том, что атака со словарем на два пароля из 7 символов (или даже на один) приведет к взлому пароля намного быстрее, чем та же атака на пароль из 14 символов.
Предположим, что в процедуре кэширования паролей LANMAN используются сильные пароли из двух и более символов. К сожалению, среди пользователей распространена привычка добавлять в конец пароля дополнительные символы. Например, если пользователь добавит в строку чисел или символов свой день рождения, например «MONTANA45 %», то пароль безопаснее от этого не станет. LANMAN разобьет его на две строки: «MONTANA» и «45 %». Вероятно, и первая, и вторая строки будут быстро определены. Первая – в результате атаки со словарем, а вторая – атаки «грубой силы», потому что она состоит только из трех символов. Поэтому в операционных системах Windows NT и Windows 2000 следует по возможности исключить кэширование LANMAN, но при этом клиенты Win9x не смогут установить их подлинность.
Генерация длинного ключа из короткого пароля
Про качество паролей уже говорилось во время обсуждения «грубой силы». С появлением схем шифрования PKE, как, например, программы PGP, большинство открытых и секретных ключей генерируются на основе паролей или ключевых фраз, уязвимых к атаке «грубой силы». Если в выбранном пароле недостаточно символов, то он может быть вскрыт в результате атаки «грубой силы». Поэтому системы PKE, как, например, RSA, могут быть взломаны при помощи «грубой силы». Причем это произойдет (если вообще произойдет) не из-за ошибки в алгоритме, а из-за дефектов генерации ключей. Лучшая защита от подобных «косвенных» атак – использование сильных паролей при генерации любых ключей. Сильный пароль – это пароль, образованный из строчных и прописных букв, чисел и символов, желательно встречающихся на протяжении всего пароля. Принято считать, что 8 символов – минимальная длина сильного пароля, но, принимая во внимание серьезность последствий выбора слабых паролей, для генерации ключей рекомендуется использовать, по крайней мере, 12 символов.
Про высококачественные пароли часто говорят, что у них высокая энтропия. Энтропия – это мера измерения его неопределенности, с помощью которой оценивают качество пароля. Обычно у длинных паролей энтропия выше, чем у коротких. Случайный выбор символов, образующих пароль, также увеличивает энтропию пароля. Например, у пароля «albatross» (энтропия приблизительно равна 30 единицам) разумная длина, но энтропия могла быть больше, если в пароле такой же длины каждый символ выбирать случайным образом, как, например, «g8 %=MQ+p» (около 48 единиц энтропии). Первый пароль может оказаться в списке широко известных имен птиц, в то время как второй – никогда. Очевидно, второй пароль предпочтительнее, и поэтому лучше его использовать. А вывод таков: хорошие алгоритмы шифрования, как, например, 3-DES c 168-битным секретным ключом, могут быть легко взломаны, если энтропия его секретного ключа составляет несколько единиц.
Ошибки хранения частных или секретных ключей
Предположим, что вами используются надежные криптографические алгоритмы, инструментальные средства производителей проверены на отсутствие ошибок реализации и при генерации ключей соблюдены все меры предосторожности. Безопасны ли ваши данные? Их безопасность определяется безопасностью частного или секретного ключей. Безопасность этих ключей должна быть гарантирована любой ценой. В противном случае нет смысла в шифровании данных.
Поскольку ключи – обычные данные, то, как правило, они хранятся где-нибудь в файле на жестком диске вашей системы. Например, секретные ключи протокола SSH-1 запоминаются в файле идентификации, размещенном в поддиректории. ssh домашней директории пользователя. Если файловая система позволяет всем читать этот файл, то пароли могут быть скомпрометированы. Как только кто-нибудь завладеет секретным ключом, чтение зашифрованных сообщений станет тривиальным. (Отметим, что файл идентификации SSH используется для установления подлинности, а не для шифрования. Но идея понятна.)
В некоторых реализациях ключи могут быть скомпрометированы из-за невозможности обеспечения безопасности хранения данных в оперативной памяти (RAM). Как известно, обработка любой информации, в том числе секретных или частных ключей, так или иначе затрагивает оперативную память компьютера. Если ядро операционной системы не хранит эти ключи в защищенной области памяти, то, вероятно, ими можно завладеть, переписав образ оперативной памяти в файл и проанализировав его на досуге. Такие файлы в UNIX называются
Инструментарий и ловушки…
Реализация компанией Netscape оригинального протокола SSL: как избежать выбора случайных чисел
В этой секции попытаемся объяснить, почему иногда хороший криптографический алгоритм не обеспечивает необходимой безопасности. При неправильном использовании алгоритма возможны бреши в системе защиты. Это хорошо иллюстрирует некорректный выбор начального числа при генерации псевдослучайных чисел в реализации протокола защищенных сокетов SSL (SSL – Secure Sockets Layer) браузера Netscape версии 1.1 (SSL – протокол, гарантирующий безопасную передачу данных по сети. Комбинирует криптографическую систему с открытым ключом и блочное шифрование данных). Без всякого сомнения, читатель знает, что этому недостатку безопасности браузера несколько лет и поэтому сегодня его значение сильно ограничено. За внешним проявлением этого специфического недостатка скрывается классический пример того, как и поныне разработчики программ ухудшают криптографические алгоритмы. Поэтому его разбор уместен и в настоящее время. Несмотря на аналогичную уязвимость протокола SSL для PC и Macintosh, в книге будет рассмотрена найденная Ианом Голдбергом (Ian Goldberg) и Дэвидом Вагнером (David Wagner) уязвимость UNIX-версии протокола SSL компании Netscape.
Перед рассмотрением сути этой уязвимости следует осветить некоторые второстепенные вопросы технологии SSL и генерации случайных чисел. SSL – это сертифицированная система аутентификации и шифрования, разработанная Netscape во времена неоперившейся электронной коммерции. Она предназначалась для защиты коммуникаций, например транзакций сделок по кредитной карточке, от прослушивания потенциальными ворами. Более криптостойкая и практически не вскрываемая версия протокола со 128-битными ключами не получила широкого распространения в мире из-за экспортных ограничений США. Фактически даже внутри США большинство пользователей Netscape имели дело со слабой международной версией программы с 40-битовыми ключами.
В большинстве случаев для генерации ключей, включая генерацию ключей протокола SSL, применяется одна из разновидностей случайных процессов. Сгенерировать на компьютере последовательность случайных чисел сложнее, чем научить его говорить. Поэтому на практике обычно используются псевдослучайные числа, которые получают в результате обработки интервалов времени между нажатиями клавиш клавиатуры при вводе информации или координат курсора мыши при его перемещении на экране монитора.
Для версии браузера Netscape версии 1.1 для UNIX была использована следующая совокупность величин: текущее время, идентификаторы (PID) процесса и его родителя. Предположим, что злоумышленник и пользователь Netscape одновременно получили доступ к машине, что является нормой для многопользовательской архитектуры UNIX-систем. Для злоумышленника не составит особого труда просмотреть список процессов на машине и определить PID процесса Netscape и PID его родителя. Если злоумышленник сможет перехватить поступающие в компьютер пакеты TCP/IP и прочитать отметки времени в заголовках пакетов, то он сможет вполне точно узнать время генерации сертификата по протоколу SSL. Перечисленных сведений хватит для уменьшения ключевого пространства приблизительно до 10 6 комбинаций, среди которых найти ключ методом «грубой силы» достаточно просто даже в почти реальном масштабе времени. После определения начального числа генерации псевдослучайных чисел, используемых для построения сертификата по протоколу SSL компании Netscape, злоумышленник сможет сначала сгенерировать аналогичный сертификат для себя, а затем прослушать или похитить текущую сессию.
Очевидно, что рассмотренное – серьезная ошибка нарушения безопасности, которую Netscape обязана была исправить в последующих версиях, что и было сделано. Netscape выпустила патчи для браузеров версий 1.x и разработала совершенно новый генератор случайных чисел для браузеров версии 2.x. Детальнее об этом специфическом недостатке браузера можно узнать в архиве журнала доктора Добба по адресу www.ddj.com/documents/s=965/ddj9601h.
Любительская криптография
Если данные не защищены современным криптографическим алгоритмом, ранее рассмотренным в этой главе или ему аналогичным, то скорее всего данные в опасности. В этой секции будет показано, как простые методы шифрования могут быть взломаны в результате применения элементарных методов криптоанализа.
Классификация зашифрованного текста
Даже плохо зашифрованное сообщение часто выглядит непонятным на первый взгляд. Но иногда можно расшифровать сообщение, анализируя не только напечатанные символы. Часто то, что можно прочитать между строк в отрытом сообщении, сохраняется и в зашифрованном.
Ниже рассмотрены алгоритмы шифрования, безопасность которых определяется алгоритмом, а не секретным ключом. Для прочтения зашифрованного таким алгоритмом сообщения нужно взломать его. В большинстве случаев взлом алгоритма подразумевает преобразование ключа или открытого текста в соответствии с алгоритмом, который доступен исследователю в виде программы или «черного ящика». Управляя входными данными и анализируя результаты, можно определить алгоритм. Впоследствии, зная алгоритм, можно будет по произвольному результату (зашифрованному сообщению) определять входные данные (расшифрованное сообщение).
Примечание
Использование описанных в этой секции методов против современных криптографических алгоритмов типа DES и его преемников в большинстве случаев неэффективно. Те немногие методы, которые могут оказаться полезными для взлома современных криптографических алгоритмов, очень сложны и приводят к положительному результату только при соблюдении определенных условий.
Частотный анализ
Частотный анализ (frequency analysis) – наиболее эффективный и часто используемый метод расшифровки сообщений, зашифрованный простым алгоритмом. Он основан на том, что одни буквы в словах встречаются чаще, чем другие. Например, в английском языке трудно найти слово без буквы е. Каким образом, зная частоту букв, можно расшифровать сообщение? Для ответа на этот вопрос нужно выбрать достаточно большое зашифрованное сообщение и составить таблицу частоты встречаемости букв в словах, в которой будет указана частота использования каждой буквы. А затем сравнить полученную таблицу c аналогичной таблицей частоты использования букв языка, на котором было написано сообщение. В результате можно догадаться, какие буквы зашифрованного сообщения соответствуют буквам открытого текста.
Проницательный читатель обнаружит, что некоторые буквы появляются с почти одинаковой частотой. Как в этом случае определить букву? Для этого нужно или проанализировать все, что сопутствует появлению букв в сообщении (контекст сообщения), или воспользоваться таблицей частот сочетаний букв, например
Обычно криптографические алгоритмы этого типа ненамного сложнее шифра Цезаря, упомянутого в начале главы. Он был хорош сотни лет тому назад. Сейчас подобные шифровки публикуются на страницах ежедневных газет для развлечения пассажиров пригородного сообщения под заголовками «Криптограммы». До сих пор подобный и слегка усложненный шифр можно обнаружить в новых версиях вирусов и червей.
Анализ зависимости между длинами зашифрованного и открытого текстов (Ciphertext Relative Length Analysis)
Иногда анализ зашифрованного сообщения может подсказать способ его расшифровки даже в случае отсутствия каких-либо сведений об использованном алгоритме шифрования. Например, предположим, что в руки исследователя попали незашифрованный и зашифрованный неизвестным ему способом пароли. Если длины зашифрованного и незашифрованного паролей совпадают, то можно предположить, что входные данные алгоритма и результат его работы связаны отношением 1: 1. Можно попробовать, подавая на вход алгоритма символы, получить для них зашифрованный эквивалент. В крайнем случае можно узнать количество символов в неизвестном пароле, если планируется взломать его методом «грубой силы».
Зная, что при шифровании длина текста не изменяется, можно воспользоваться этим для выбора части шифротекста, которую можно расшифровать на основании тех или иных предположений. Например, во время Второй мировой войны союзники использовали похожий способ разгадки попавшего в их руки кода немецкой шифровальной машинки Enigma, потому что знали, что, вероятнее всего, фраза «Heil Hitler» встретится в конце каждого зашифрованного текста.
Анализ сходства зашифрованного и открытого текстов
Анализ сходства зашифрованного и открытого текстов (Similar Plaintext Analysis), применяемый для взлома неизвестных алгоритмов, основан на анализе изменений зашифрованного сообщения в зависимости от изменений открытого текста. Конечно, для этого необходимо, чтобы у исследователя была возможность выборочного шифрования тщательно подобранных образцов открытого текста. Например, пусть он зашифровал строки «AAAAAA», «AAAAAB» и «BAAAAA» и проанализировал различия в зашифрованных текстах. В случае моноалфавитного шифра естественно было бы ожидать, что первые две строки различаются только последним символом. Если это так, то несложно построить таблицу трансляции символов в соответствии с исследуемым алгоритмом, которая отражала бы соответствие между символами открытого и зашифрованного текстов и наоборот. После того как таблица была бы готова, не составило бы труда написать программу расшифровки зашифрованного текста.
Что делать в случае полиалфавитного шифра, когда при изменении одного символа незашифрованного сообщения изменяются несколько символов зашифрованного? Конечно, это более сложный случай, и сложность расшифровки зависит от числа изменяемых символов зашифрованного сообщения при изменении одного в незашифрованном. Возможно, что в этом случае для раскрытия логики работы неизвестного криптографического алгоритма можно попытаться объединить рассматриваемый метод анализа с методом «грубой силы».
Моноалфавитные шифры
Моноалфавитный шифр – это шифр, в котором каждый символ алфавита заменяется другим символом в отношении 1: 1. Ранее рассмотренные в главе шифры Цезаря и ROT13 – классические примеры моноалфавитных шифров. Некоторые моноалфавитные шифры скремблируют алфавит (шифруют путем перестановки групп символов), изменяя порядок букв в алфавите
Из-за легкости взлома сегодня редко можно встретить подобный шифр. Такие шифры раскрываются перебором всевозможных комбинаций букв алфавита или использованием лингвистического анализа (language analysis). Моноалфавитные шифры легко поддаются частотному анализу, благодаря тому что, несмотря на замену одних букв другими, частота появления каждого символа в сообщении будет соответствовать известной частоте использования букв в языке.
Другие способы скрытия информации
Иногда разработчики следуют древнему способу обеспечения безопасности – тотальной секретности. И вместо применения испытанных криптографических алгоритмов они пытаются скрыть данные при помощи хорошо известных обратимых алгоритмов, как, например, UUEncode, Base64 или комбинации каких-нибудь простых методов. В этом случае все, что нужно для расшифровки, – это повторно преобразовать зашифрованное сообщение при помощи алгоритма, ранее использованного для его зашифровки. Часть разработчиков пользуется кодировкой данных при помощи операции исключающего ИЛИ (XOR) вместо применения криптографических алгоритмов с ключом. Для кодировки сообщения ключ не нужен. Ниже рассмотрены некоторые широко известные алгоритмы кодирования.
XOR
В качестве промежуточного шага многие сложные и безопасные алгоритмы шифрования используют операцию XOR. Часто можно встретить данные, которые пытались скрыть операцией XOR. XOR – сокращение от английских слов ИСКЛЮЧАЮЩЕЕ ИЛИ
Таблица 6.2.
Таблица истинности операции XOR
Посмотрите на простой пример кодировки и восстановления данных с помощью операции XOR. В примере используется один ключевой символ («A») для преобразования сообщения, состоящего из единственного символа («B»). В результате получится зашифрованное сообщение «ciphertext» (см. табл. 6.3).
Таблица 6.3.
Операция XOR над «А» и «В»
Предположим, что известны величина «B» и результат шифрования сообщения «ciphertext». Как найти неизвестный ключ «A»? Требуется восстановить ключ для раскодирования другого закодированного сообщения «ciphertext2», битовое представление которого 00011010. Для этого нужно выполнить операцию XOR с операндами «B» и «ciphertext» и восстановить ключ «A». Результат воcстановления показан в табл. 6.4.
Таблица 6.4.
Результат операции XOR на операндах «ciphertext» и «В»
После восстановления ключа им можно воспользоваться для декодирования «cipher2» и в результате закодировать символ «Z» (см. табл. 6.5).
Таблица 6.5.
Результат операции XOR на операндах «cipher2» и «А»
Конечно, это слишком простой пример. Скорее всего, на практике придется столкнуться с ключами, состоящими из нескольких символов. Кроме того, кодирование сообщений операцией XOR может выполняться последовательно несколько раз.
Манипуляции над абстрактными 0 и 1 могут оказаться трудными для восприятия, если ранее читатель не сталкивался с двоичными числами и величинами. Поэтому автор решил привести пример простой программы, которая выполняет серию из трех операций XOR на различных перестановках ключа для кодирования сообщения. В этой короткой программе на языке Perl используется свободно распространяемый модуль IIIkey для обращения к внутренней функции шифрования XOR. Для того чтобы воспользоваться приведенной программой, следует загрузить модуль IIIkey по адресу www3.marketrends.net/encrypt.#!/usr/bin/perl
#!/usr/bin/perl
# Encodes/Decodes a form of XOR text
# Requires the IIIkey module
# Written specifically for HPYN 2nd Ed.
# by FWL 01.07.02
# Use the IIIkey module for the backend
# IIIkey is available from http://www3.marketrends.net/
encrypt/
use IIIkey;
# Simple input validation
sub validate() {
if (scalar(@ARGV) < 3) {
print “ Error: You did not specify input correctly!\n” ;
print “ To encode data use ./xor.pl e \“ Key\” \“ String
to Encode\”\n”;
print “ To decode data use ./xor.pl d \“ Key\” \“ String
to Decode\”\n”;
exit;
}
}
validate();
$tmp=new IIIkey;
$key=$ARGV[1];
$intext=$ARGV[2];
if ($ARGV[0] eq “e”) { # encode text
$outtext=$tmp->crypt($intext, $key);
print “Encoded $intext to $outtext”;
} elsif ($ARGV[0] eq “d”) { # decode text
$outtext=$tmp->decrypt($intext, $key);
print “Decoded $intext to $outtext”;
} else { # No encode/decode information given!
print “To encode or decode? That is the question.”;
exit;
}А вот пример отчета работы программы.
$ ./xor.pl e “my key” “secret message”
Encoded secret message to 8505352480^0758144+510906534
$ ./xor.pl d “my key” “8505352480^0758144+510906534”
Decoded 8505352480^0758144+510906534 to secret message
Алгоритм UUEncodeUUEncode – алгоритм, который обычно используется для преобразования двоичных данных в текстовый формат для передачи по электронной почте. (UUEncode – кодирование Unix-Unix (метод преобразования файлов из двоичного формата в текстовый и обратно для обеспечения пересылки по сети Internet посредством электронной почты)). Вероятно, читателю известно, что большинство программ электронной почты не могут непосредственно обрабатывать двоичные вложения к письмам электронной почты. Поэтому в случае присоединения двоичного файла (как, например, рисунка в формате JPEG) к письму электронной почты клиент электронной почты преобразует двоичные данные в текстовый эквивалент, возможно, с помощью алгоритма, подобного UUEncode. Присоединенный файл преобразуется из двоичного формата в поток печатаемых символов, который может быть обработан почтовой программой. После получения письма вложение преобразуется обратным алгоритмом кодирования (UUDecode) для преобразования к оригинальному двоичному файлу.
Иногда разработчики используют алгоритм UUEncode для кодирования обычного печатаемого текста для скрытия смысла сообщения. В этом случае для восстановления сообщения достаточно преобразовать закодированный текст сообщения программой UUDecode. Клиенты UUEncode/UUDecode с интерфейсом командной строки доступны почти для каждой когда-либо созданной операционной системы.
Алгоритм Base64Алгоритм Base64, так же как и UUEncode/UUDecode, используется для кодирования вложений электронной почты MIME-расширений (Multipurpose Internet Mail Extensions (MIME) – многоцелевые расширения электронной почты в сети Internet. Набор стандартов для передачи мультимедийной информации посредством электронной почты). Вероятно, читатель еще столкнется с паролями и другой интересной информацией, скрываемой кодированием Base64. Примечательно, что часто встречаются Web-сервера с возможностью HTTP-аутентификации, которые хранят пароли в формате Base64. Если в руки злоумышленника попадет имя пользователя и его пароль, закодированный алгоритмом Base64, то он сможет в течение нескольких секунд раскрыть их. Характерным признаком кодировки Base64 служит наличие одного или двух знаков равенства (=) в конце строки. Знаки равенства часто используются как символы дополнения данных.
Посмотрите на простой пример программы раскодирования данных в формате Base64. Этот фрагмент программы должен выполняться на любой операционной системе, на которой установлен Perl5 или, еще лучше, модуль MIME::Base64 компании CPAN (www.cpan.org). Приведены также примеры использования программы и отчет ее работы.#!/usr/bin/perl
# Filename: base64.pl
# Encodes/Decodes Base-64 text
# Requires the MIME::Base64 module
# Written specifically for HPYN 2nd Ed.
# by FWL 01.07.02
# Use the MIME module for encoding/decoding Base-64 strings
use MIME::Base64;
# Simple input validation
sub validate() {
if (scalar(@ARGV) < 2) {
print “Error: You did not specify input correctly!\n”;
print “To encode data use ./base64.pl e \“String to
Encode\”\n”;
print “To decode data use ./base64.pl d \“String to
Decode\”\n”;
exit;
}
}
validate();
$intext=$ARGV[1];
if ($ARGV[0] eq “e”) { # encode text
$outtext=encode_base64($intext);
print “Encoded $intext to $outtext”;
} elsif ($ARGV[0] eq “d”) { # decode text
$outtext=decode_base64($intext);
print “Decoded $intext to $outtext”;
} else { # No encode/decode information given!
print “To encode or decode? That is the question.”;
exit;
}А вот пример отчета работы программы.
$ ./base64.pl e “Secret Password”
Encoded Secret Password to U2VjcmV0IFBhc3N3b3Jk
$ ./base64.pl d “U2VjcmV0IFBhc3N3b3Jk”
Decoded U2VjcmV0IFBhc3N3b3Jk to Secret Password
Алгоритмы сжатия данных Иногда может показаться, что для скрытия данных алгоритмов сжатия недостаточно. В прошлом некоторые разработчики игр сжимали файлы состояния игры не только для сокращения необходимой для их хранения памяти, но и для затруднения внесения в них изменений при помощи разнообразных редакторов игр. В те годы для этих целей наиболее часто использовались алгоритмы SQSH (Squish or Squash) и LHA. Сами алгоритмы были унаследованы от консольных игр 1980-х, когда их использовали для сжатия образа постоянного запоминающего устройства (ROM – Read Only Memory) в картриджах. Как правило, в случае невозможности расшифровать текст стандартными методами следует проверить, а не был ли он сжат одним из многочисленных общедоступных алгоритмов сжатия.Приоткрывая завесу
Криптографические средства, ориентированные на пользователя
SDMI бросает вызов хакерам
Иногда принимается решение использовать криптографические средства, которые хотя и нельзя назвать любительскими, но тем не менее не соответствующими профессиональному уровню. Например, организация «Инициатива обеспечения безопасности музыкальных произведений» SDMI (SDMI – Secure Digital Music Initiative) попыталась разработать способ маркировки цифровой музыки «водяными знаками» при помощи специального закодированного сигнала. По замыслу разработчиков, «водяной знак» должен был защитить музыкальные произведения от неавторизованного прослушивания или копирования. В процессе разработки SDMI предложила сообществу хакеров взломать шесть схем «водяных знаков» за $10 000. Музыкальное произведение считалось взломанным при предъявлении музыкальной записи без «водяных знаков», которая была получена из образца записи с «водяными знаками». В распоряжение соискателей были предоставлены только образцы записей с «водяными знаками» без разглашения принципов их построения. До и после каждого образца записи были использованы различные схемы «водяных знаков», для того чтобы можно было найти в них различия.
Две из шести схем «водяных знаков» были отклонены сразу же после начала конкурса, а оставшиеся четыре были взломаны почти одновременно группой ученых под руководством профессора Принстонского университета Эдварда В. Фелтена (Edward W. Felten) через несколько недель. Фелтен и его партнеры решили отказаться от $10 000 и представить общественности результаты своих исследований, воспользовавшись небольшой неточностью в договоре на проведение исследований. В договоре было сказано, что приз в $10 000 может быть получен при условии сохранения результатов исследования в тайне. Но при этом ничего не говорилось об обязательствах конкурсанта при отсутствии его материальной заинтересованности. По всей видимости, SDMI намеревалась возбудить судебный процесс в соответствии с Актом авторского права цифрового тысячелетия (DMCA). Акт предусматривает ответственность за разглашение сведений, которые могут использоваться в интересах обхода средств защиты авторского права. В конечном счете SDMI приняла решение не возбуждать судебный процесс, а Фелтен и его партнеры представили свои результаты на 10-м Симпозиуме по вопросам безопасности пользователей UNIX (10th USENIX Security Symposium). Выводы Фелтена, полностью разделяемые сообществом безопасности, свидетельствуют о неизбежном взломе схем шифрования, основанных на «водяных знаках». Интересно отметить замеченный Фелтеном и его партнерами факт о том, что для взлома схем «водяных знаков» не требуется специальных знаний в области информатики. Достаточно знать общую теорию обработки сигналов.
Эта история – еще один пример попытки производителя использовать «собственные доморощенные особо безопасные алгоритмы защиты информации» и постоянного развития криптографии. Даже если утверждается, что безопасность новых приложений криптографии основана на новых криптоалгоритмах, следует проявить осторожность, скептически отнесясь к новым, до конца не проверенным алгоритмам. Особенно если они хранятся в тайне.
Резюме
В этой главе приведена краткая историческая справка о развитии криптографии, описан известный шифр Цезаря, а также подробно рассказано о значении криптографии в наши дни. Современная криптография представлена
В настоящее время широко используются симметричные криптографические алгоритмы DES, AES и IDEA. В главе было рассказано о приложенных NIST усилиях по замене DES, который постепенно сдавал свои позиции, на современный алгоритм, о том, как алгоритм Rijndael был отобран из пяти финалистов конкурса и был признан стандартом AES. Было сказано несколько слов о стартовавшей с начала 1990-х годов истории создания перспективного Европейского стандарта криптографического алгоритма IDEA и показаны его преимущества по сравнению с DES.
Впервые об асимметричных алгоритмах заговорили с середины 1970-х годов, когда Диффи и Хеллман опубликовали названный в их честь алгоритм обмена ключами (алгоритм Диффи-Хеллмана, или DH-алгоритм), предназначенный для безопасного обмена ключами в сетях общего пользования. Вслед за алгоритмом Диффи-Хеллмана появился алгоритм RSA, который провозгласил начало новой эры криптографии с открытым ключом. Алгоритмы и методы криптографии с открытым ключом впоследствии были реализованы в популярной криптосистеме PGP. Фундаментальное отличие криптосистем с открытым ключом от симметричных систем основано на проблеме факторизации (разложении на сомножители) очень больших целых чисел.
Метод «грубой силы» эффективен для взлома большинства криптографических алгоритмов, если в распоряжении исследователя достаточно времени для перебора всех ключей из ключевого пространства. На перебор ключей может потребоваться от нескольких минут до миллиарда лет. Наиболее часто этот метод используется для вскрытия паролей. Для подобных целей широко используются программы LOphtcrack и John the Ri pper.
Ошибки в реализации криптостойких алгоритмов или не предусмотренные разработчиками алгоритмов способы их использования способствуют повышенной уязвимости построенных на их основе криптографических систем. Так, для алгоритма Диффи-Хеллмана опасны атаки «злоумышленник посередине» (man-in-the-middle-type attacks). Сравнительно легко могут быть раскрыты пароли в формате кэш-величин LanManager (LANMAN), зашифрованные с помощью DES. К малоприятным результатам приводит использование легко вскрываемых паролей или ключевых фраз в симметричных криптосистемах. А неверное хранение секретного или личного паролей может вообще сделать бессмысленным шифрование сообщений.
Иногда для хранения информации в тайне используются обратимые или недостаточно криптостойкие алгоритмы. В главе было рассказано об уязвимости недостаточно криптостойких шифров к частотному анализу (frequency analysis), при котором для расшифровки сообщений используются частотные характеристики языка. Известны атаки, основанные на анализе длин открытого и зашифрованного текстов (ciphertext relative lengthanalysis) или анализе сходства зашифрованного и открытого текстов (similar plaintext analysis). Были рассмотрены примеры, когда разработчик пытался сохранить данные в тайне при помощи операций XOR или алгоритма кодирования Base64, и приведены простые примеры программ обратимого кодирования, основанные на этих принципах. Попутно было рассказано об алгоритмах сжатия данных как средства их защиты.
Конспект
Концепции криптографии
Поделиться книгой: