Криптоанализ и суперкомпьютеры
Было бы несправедливо обойти в истории развития суперкомпьютеров и тот малоизученный, в силу своей глухой и непроницаемой завесы тайны и абсолютной секретности, но крайне важный для интересов национальной безопасности США, раздел прикладной области применения сверхпроизводительных вычислений, которым по праву считается во всем мире криптоанализ. Хотя проблема раскрытия зашифрованного сообщения возникла примерно в одно время с появлением первых шифров за несколько сот лет до создания первого компьютера научное обоснование ее решения было сформулировано только после Второй мировой войны в математической теории связи американца Клода Шеннона и нашего соотечественника В.Котельникова.
Главной в этих работах является концепция избыточности информации, согласно которой в сообщении содержится больше символов, чем в действительности требуется для его передачи по каналу связи: хорошо известные нам лексические обороты в личных и деловых письмах (дорогая, уважаемый, искренне ваш, целую и т.п.) являются серьезной зацепкой в раскрытии любого шифра. Одновременно Шеннон первым сумел объяснить постоянство частот встречаемости букв и, тем самым, разработал теоретические основы современного криптоанализа: например, в английском языке частота появления буквы E составляет 12,5%, а буквы Z 0,09%().
Саломаа А. Криптография с открытым ключом: Пер. с англ. М.: Мир, 1995.
Рисунок 7. Гистограмма частот использования букв латинского алфавита в английском языке
Строго говоря, первый электромеханический компьютер был разработан англичанами для раскрытия немецкого шифра Энигма (в переводе на русский загадка). Руководил этим направлением работ на невидимом фронте один из лучших математиков Великобритании того времени Алан Тьюринг, в тихом и уединенном месте в пригороде Лондона Блетчли, а его услугами пользовался никто иной, как премьер-министр Уинстон Черчиль.
Известное всем пристрастие сэра У.Черчиля к дорогим кубинским сигарам, хорошему армянскому коньяку и длительному пребыванию в утренние часы в постели не помешало первому лорду адмиралтейства и заклятому врагу советской власти трезво оценить масштабы угрозы, нависшей над туманным Альбионом после 1 сентября 1939 года. Немецкие подводные лодки и бомбардировщики, по планам Г итлера, получившим название операция Морской лев, должны были блокировать Англию с моря, разрушить ее военно-промышленный потенциал с воздуха и деморализовать население, после чего германскому вермахту оставалось только повторить переправу легионов Цезаря через Ла-Манш и завоевать непокорных англичан. Но немцы ошиблись в своих расчетах, самонадеянно посчитав, что содержание шифрованных телеграмм (до 2 тысяч в сутки) с секретными приказами на потопление морских конвоев из Америки и бомбежки английских городов оставались известными только им.
Англичане читали все немецкие шифртелеграммы благодаря находчивости капитана британских ВМС Яна Флеминга будущего автора книжной эпопеи про подвиги агента 007 Джеймса Бонда. Флеминг предложил дерзкий план захватить на тонущей немецкой подводной лодке в Атлантике шифровальную машину и использовать ее для вскрытия замыслов противника.
У.Черчиль. Вторая мировая война, т.3. М.: Воениздат, 1991 г.
Энигма () в первоначальном промышленном варианте фирмы Сименс, созданном берлинским инженером Артуром Кирхом, представляла собой четыре вращающихся на одной оси барабана, что обеспечивало более миллиона вариантов ключа, которые определялись текущим положением барабанов. На каждой стороне барабана по окружности располагались 26 электрических контактов (сколько букв в алфавите).
Контакты с обеих сторон барабана соединялись попарно случайным образом 26 проводами, формировавшими замену символов. Колеса складывались вместе, и их контакты, касаясь друг друга, обеспечивали прохождение электрических импульсов сквозь весь пакет колес.
В.В. Бондаренко.
Введение в криптографию. СГУ, 2000
Рисунок 8. Немецкая шифровальная машина Энигма (фото)
При нажатии клавиши и кодировании очередного символа роторный механизм Энигмы генерировал для каждого знака открытого текста сообщения уникальную последовательность шифра, который имел теоретически свыше 1026 комбинаций замены.
Но без ключа к своему шифру, в котором использовалась так называемая многоалфавитная система замены, Энигма так и осталась бы загадкой, если бы англичане не построили свой, пусть, несовершенный по современным меркам, но фактически первый электромеханический компьютер Бомба для нахождения одной заветной последовательности цифр и букв, открывавшей им планы противника. Тьюринг на основе методов математической статистики и разработанной им теории дискретных автоматов предложил очень изящный и, вместе с тем, весьма эффективный алгоритм криптоанализа, существенно ограничивавший количество комбинаций ключа. Не последнюю роль в разгадке секрета Энигмы сыграли излишняя педантичность и аккуратность немецких радистов, проставлявших в начале телеграмм условные обозначения положения роторов шифровальной машины, что, в сочетании с ежедневными метеосводками для кораблей и самолетов, давало хорошее подспорье англичанам для атаки на шифр противника.
Так с помощью математики и прообраза современного компьютера была выиграна битва за Англию, в которой во имя сохранения своей необычной технологии в тайне У.Черчиль был вынужден пожертвовать жизнями сотен обитателей маленького городка Ковентри, подвергшегося варварской бомбардировке немецкой авиации.
Программный эмулятор Энигмы, написанный автором на языке Visual Basic, можно найти на сайте - Classical Ciphers Encoding Demo, Alexander Levakov
Б.Анин, А.Петрович. Радио-шпионаж.
Москва, Международные отношения, 1996.
Знаменитый советский разведчик Ким Филби, работавший в это время в британской разведке, с помощью своих товарищей снабжал Красную Армию стратегической информацией, полученной англичанами с помощью Бомбы. Один из помощников Филби Джон Кернкросс провел почти год в Блетчли, редактируя расшифрованные машиной Тьюринга материалы Энигмы. До сих пор историки спорят о том, было ли это хитростью У.Черчиля, передававшего таким образом И.Сталину, как своему союзнику по антигитлеровской коалиции, важную информацию или же величайшим провалом английской разведки во Второй мировой войне.
Известно одно летом 1943 года в ходе сражения под Курском немцы потерпели сокрушительное поражение, переломившее весь последующий ход войны, во многом благодаря информации, своевременно полученной от группы Филби.
В.Попов. Советник королевы суперагент Кремля.
Москва, 1995.
Но не только англичане занимались криптоанализом во время Второй мировой войны, где от одной своевременно расшифрованной кодограммы зависели жизни тысяч людей. В ходе войны с Японией на Тихом океане криптоанализ получил в США мощный стимул для своего развития в прикладное направление математики и теории связи: американцам удалось перехватить и уничтожить над океаном самолет командующего японских ВМС адмирала Ямомомото, выиграть морские сражения в Коралловом море и у атолла Мидуэй.
Результаты криптоанализа в США (как и во всех странах) могут держаться в тайне многие десятилетия в интересах национальной безопасности, а для их раскрытия требуется решение специальной комиссии и личная подпись американского президента. К числу таких рассекреченных работ относится проект Венона, в ходе которого в течение 1943 1946 гг. американские спецслужбы вели радиоперехват шифрованных сообщений советской разведки в США, сумевшей глубоко проникнуть в тайны атомного проекта Манхэтэн.
Только совсем недавно стало известно о том, что успех спецслужб США в операции Венона во многом был связан с использованием первого лампового компьютера Эниак (), который по иронии судьбы разрабатывался первоначально для проведения расчетов атомной бомбы, за секретами которой в свою очередь охотилась советская разведка.
Рисунок 9. Первый цифровой ламповый компьютер Эниак (фото)
Интересно, что по теории Шеннона криптоанализ системы одноразовых шифрблокнотов, которые использовала советская разведка в этот период, теоретически имеет шансы на успех равные нулю при условии регулярной смены ключей и аккуратном обращении с исходным текстом. Американцам просто повезло, когда в их руках оказались шифрблокноты, которые, как выяснилось позже, печатались машинистками преимущественно одной рукой со смещением частот цифр, отдельные страницы были продублированы и использовались шифровальщиками с грубыми нарушениями и повторяющимися ошибками. Не исключено, что на эту мысль их мог натолкнуть все тот же А. Тьюринг.
Некоторые историки считают, что дело супругов Розенбергов, обвиненных в атомном шпионаже в пользу СССР и казненных на электрическом стуле в июне 1953 года, было сфабриковано ФБР для того, чтобы скрыть сам факт раскрытия секрета шифра советской разведки. А спустя год скоропостижно скончается от отравления всеми гонимый и забытый А.Тьюринг, потерявший к тому времени допуск к секретным работам.
Неправда ли, в этом есть какая-то своя фатальная закономерность? Как бы там ни было, но победа американских криптоаналитиков оказалась запоздалой: в августе 1949 г. Советский Союз успешно провел испытание атомного, а всего через год, опередив США, ядерного оружия.
Случайная последовательность цифр не имела равномерного закона распределения.
Venona: Soviet Espionage and the American Response, 1939-1957.
Сегодня криптоанализом, этой трудоемкой и малопонятной для непосвященных, но крайне увлекательной для математиков, лингвистов и программистов задачей, в США занимается специальное ведомство Агентство национальной безопасности (National
Security Agency), штаб-квартира которого размещается в Форт-Миде (шт. Мэриленд), на полпути между Вашингтоном и Балтимором.
Основатель первого в истории США черного кабинета, знаменитый американский криптоаналитик Герберт Ярдли был бы просто поражен той техникой и масштабами слежки за своими согражданами, которыми сегодня обладает АНБ.
Покров таинственности, которым это учреждение окутано с момента своего появления на свет в ноябре 1952 года, существует и в наши дни: лишь в 1957 году в справочник Правительственные учреждения США впервые было включено краткое описание агентства, которое осуществляет в высшей степени специализированные технические и координационные функции, связанные с национальной безопасностью. АНБ, по признанию его бывших сотрудников, еще более молчаливая, секретная и мрачная организация, чем ЦРУ.
Как шутят сами американцы, упоминая в разговорах между собой аббревиатуру агентства: никому ничего не говори (Never Say Anything) или нет такого агентства (No Such Agency).
Здесь за прочными и непроницаемыми практически для всех видов электромагнитных и звуковых волн стенами днем и ночью работают над раскрытием чужих государственных, политических, военных, экономических и научно-технических тайн тысячи высококвалифицированных специалистов, собирая, расшифровывая и анализируя информацию, перехваченную специальными постами радиотехнической разведки, разбросанными по всему миру. По официальным данным до 11 сентября 2001 года бюджет АНБ, в штате которого числилось около 35 тысяч человек, составлял величину порядка $5 млрд., в то время как на все программы радиоэлектронного шпионажа тратилось свыше $10 млрд. или примерно одна треть бюджета разведывательного сообщества США.
Одной из таких глобальных систем радиоэлектронной разведки является скандально известный Эшелон, чуткие уши которого улавливают малейший сигнал в радиоэфире за тысячи километров от берегов США ().
B. Drogin. America's eavesdropper loses lead in a world it helped create.
Los Angeles Times, 16.3.2000.
Рисунок 10. Посты системы радиоэлектронной разведки Эшелон (фото)
Сейчас в доках судоверфи Норфолка стоит новая малошумная атомная многоцелевая подводная лодка класса Си вульф (Морской волк) SSN-23 водоизмещением 9 тысяч регистровых тонн, на оснащение которой современной аппаратурой радиотехнической разведки производства компании Дженерал дайнэмикс Конгресс США по заказу АНБ выделил почти $1 млрд. Субмарина-шпион, крестником которой стал экс-президент Джимми Картер, будет оснащена специальным глубоководным автономным спускаемым подводным аппаратом для подключения к кабелям связи на дне океана и вступит в боевой состав американского флота в середине 2004 года.
Как удастся джентльменам из Форт-Мида незаметно подключиться к волоконно-оптическим кабелям бесконтактным способом (без разрыва защитной оболочки и стекловолокна) автору не известно.
Может быть для этого будет использован физический эффект магнито-ядерного резонанса или поток нейтрино? Г лава АНБ генерал-лейтенант Хайден и командование ВМС США отказываются комментировать эти технические подробности, хотя и так понятно суперлодка могла бы пригодиться АНБ для прослушивания телефонных разговоров и перехвата трафика Интернета накануне событий 11 сентября.
Spy agency taps into undersea cable, ZD Net News, May 23, 2001.
Рисунок 11. Подводная лодка класса Си вульф" SSN-23 (фото)
АНБ наряду с ЦРУ, ФБР и другими спецслужбами составляет ядро разведывательного сообщества, выполняя в нем одну из самых важнейших функций сбор информации с помощью подводных, надводных, наземных, воздушных и космических радиотехнических средств контроля электромагнитных излучений, для обработки которой и используются самые мощные, высокопроизводительные компьютеры в мире. По оценкам зарубежных экспертов, АНБ входит в первую десятку ведущих организаций, связанных с проектами в области высокопроизводительных вычислений.
Не случайно один из первых экземпляров суперкомпьютера Cray-1 появился именно здесь, где джентльмены так любят читать чужие зашифрованные послания. Сегодня этот чудо-компьютер середины 70сх годов 20го столетия занимает одно из самых почетных мест в экспозиции местного музея, где можно увидеть и более древние экспонаты из истории криптографии и криптоанализа.
Хотя номенклатура, количество и характеристики установленных в этом ведомстве суперкомпьютеров засекречены, специалисты полагают, что их суммарная производительность составляет величину порядка 156 Гфлоп. АНБ принадлежит одна из самых мощных по количеству процессоров (1024) моделей суперЭВМ Cray-T3D.
Принимая во внимание тот факт, что за последние 10 лет общее количество суперкомпьютеров в мире, связанных с секретными проектами (в том числе и в области криптоанализа), по официальной статистике колебалось в пределах от 19 в 1993 г. до 46 в 1998 г. и составляет в настоящее время 25 единиц, не трудно оценить в первом приближении количество ЭВМ этого класса и в АНБ, взяв за основу долю США в их общей массе (46%) 12 ед.
Но ни один компьютер не в силах заменить человеческой интуиции. Вот как выглядит рутинная технология криптоанализа в АНБ, описанная американским журналистом Дэвидом Каном.
Криптоаналитики работают группами. Сложные современные шифры превратили работу одиночки в дело прошлого.
Руководитель группы распределяет задания между подчиненными, проводит совещания, решает, является ли данный метод более продуктивным, чем другие. Работа отдельно взятого криптоаналитика в составе группы заключается в отыскании статистически устойчивых и значимых закономерностей (частот, периодов повторений, корреляций и других статистик), которые дают значительные отклонения от случайного текста".
Добавим, что даже самый совершенный машинный генератор случайных чисел обладает таким неприятным свойством, как период вырождения, когда через сотни тысяч и даже миллионы итераций он начинает повторять всю последовательность заново, давая криптоаналитикам возможность найти путь к раскрытию шифра. А еще существует так называемый эффект групповой автокорреляции, при котором сочетания букв или цифр периодически также повторяются.
И это тоже одна из изюминок криптоанализа. Поклонников так называемой системы двух ключей или несимметричного шифра хочу разочаровать найти (за приемлемое время) два больших простых числа, произведение которых лежит в основе шифра Фила Циммермана PGP (Pretty good privacy) на обычном персональном компьютере, ограниченном в быстродействии и разрядности, действительно практически невозможно, но не на суперкомпьютере Cray-T3D. Всего пару десятилетий назад, на заре криптографии с открытым ключом считалось, что для реализации альтернативного PGP алгоритма RSA достаточно даже 128-битовых чисел.
Сейчас эта граница отодвинута до 1024-битовых чисел практически на порядок и это далеко еще не предел.
Bruce Schneier. Applied Cryptography, John Wiley Sons, 1994 and 1996.
С.Баричев, Р.Серов. Основы современной криптографии, М., Горячая линия Телеком, 2001.
Но и это еще не все. Если в Форт-Миде получают несколько экземпляров одного и того же сообщения, перехваченных разными радиостанциями, редакторы пытаются устранить в нем все имеющиеся искажения. Затем осуществляется сравнение и сопоставление местонахождения отправителей и получателей сообщений, маршруты их прохождения и служебные пометки, присутствующие в этих сообщениях для сведения шифровальщиков и операторов связи. Это позволяет отсортировать перехваченные сообщения по принципу принадлежности к одинаковым шифрсистемам.
Собранная картина переписки во всей ее полноте позволяет выявить общую структуру сети связи и получить другую полезную информацию.
Дэвид Кан. Взломщики кодов, Москва, Центрполиграф, 2000.
Что и говорить слишком велик соблазн у любого разведчика, прочитав заметку в газете, зашифровать и передать ее в Центр под видом ценного донесения агента Х: не каждому удается завербовать дипломата или члена парламента лучше, конечно, шифровальщика. Анекдотичность подобной жизненной ситуации в работе спецслужб хорошо и убедительно показана Грэмом Грином в его романе Человеческий фактор, где главный герой офицер английской разведки Ми-6 посылает в Лондон секретные чертежи иностранного ядерного центра, скопированные с технического описания... пылесоса.
К слову сказать, арсенал современной криптографии за последнее время изрядно пополнился, и в моде теперь так называемая стеганография, когда текст открытого сообщения прячется в звуковом, видео или графическом файле. Но все новое это хорошо забытое старое: еще Геродот описывает хитрость персидского царя Ксеркса, использовавшего в 5 веке до н.э. для этого обритую голову своего раба.
В наши дни нет смысла ждать, когда отрастут волосы проще надеть парик. Во всяком случае специалисты АНБ утверждают, что члены террористической организации Аль-Каида использовали стеганографию для планирования и организации ударов 11 сентября, обмениваясь сообщениями... через порнографические сайты Интернета.
Может быть поэтому сейчас в США началась такая активная компания борьбы за нравственные устои электронных средств СМИ.
Jack Kelley. Terror groups hide behind Web encryption, USA TODAY, 06/19/2001
И все же, основной урок, который извлекли для себя обитатели Форт-Мида, впрочем, как и других американских спецслужб, после 11 сентября, заключается в том, что гигантские массивы информации таинственные и поражающие воображение терабайты, собранные агентурными и техническими методами разведки, нуждаются не только в очень тщательной и скрупулезной обработке, но и ... в своевременном обмене со своими коллегами по разведывательному сообществу в интересах предотвращения террористических актов. Недаром говорится дорога ложка к обеду. Как это будет осуществлено на практике покажет время. Во всяком случае технология многомерного анализа (добычи) данных (data mining), которую сегодня вслед за АНБ взяли на вооружение ЦРУ и ФБР, в сочетании с технологией высокопроизводительных вычислений и Интернетом таят в себе огромные возможности, упустить которые было бы не разумно.
Кроме расшифровки чужой корреспонденции, АНБ разрабатывает рекомендации и стандарты по информационной безопасности и закрытию технических каналов утечки информации в собственной стране, используя для этого богатый опыт охоты за чужими секретами: известно, что в течение длительного времени АНБ перехватывало и расшифровывало секретную информацию почти 120 стран, пользовавшихся оборудованием подставной швейцарской фирмы Crypto AG. Одним из таких стандартов является серия нормативных документов с описанием технических условий эксплуатации радиоэлектронных устройств под аббревиатурой TEMPEST, полное название которой до сих пор остается секретным. Все компьютеры, на которых обрабатывается информация в высшем эшелоне государственного и военного управления США, имеют защиту от излучения по стандарту TEMPEST.
Этот же стандарт используется для защиты важнейших радиоэлектронных систем от электромагнитного импульса, источником которого могут быть атмосферные электрические разряды как естественного (грозового), так и искусственного (от ядерного взрыва) происхождения.
Wayne Madsen. Crypto AG: The NSA's Trojan Whore?, CovertAction Quarterly
NSTISSAM TEMPEST/2-95, 12 December 1995.
Питток Б., Акермен Т., Крутцен П., Мак-Кракен М., Шапиро Ч., Турко Р. Последствия ядерной войны: Физические и атмосферные эффекты. М.: Мир, 1988.
Решая практические задачи криптоанализа на чужих шифрованных сообщениях, АНБ постоянно совершенствует национальные криптографические алгоритмы, привлекая для этого в открытых конкурсах лучших специалистов во всем мире. Примером такого международного проекта является разработка нового стандарта для так называемой коммерческой криптографии AES (Advanced Encryption Standard), победителем в котором по итогам двух раундов в течение последних четырех лет среди 15 алгоритмов стал блочный симметричный шифр Рейндален (RIJNDALEN), авторами которого являются бельгийские математики Винсент Раймен и Джон Даемен. Впервые за всю современную историю криптографии американцы пошли на беспрецедентный шаг, допустив к участию в конкурсе на национальный стандарт иностранных специалистов.
Впрочем, в этом нет ничего удивительного, если принять во внимание тот факт, что Бельгия является союзником США по НАТО, и, кроме того, одним из условий конкурса была полная прозрачность алгоритма с точки зрения математических операций, а также отсутствие патента на его изобретение в США: лучшей наградой и рекламой победителям стали отзывы ведущих криптоаналитиков АНБ, проверявших стойкость алгоритма на суперкомпьютерах с использованием специальных математических методов анализа.
Bryan Weeks, Mark Bean, Tom Rozylowicz, Chris FickeHardware. Performance Simulations of Round 2 Advanced Encryption Standard Algorithms, National Security Agency, May 15, 2000.
По оценкам экспертов, для вскрытия нового шифра с длиной ключа 256 бит потребуется непрерывная работа самого мощного компьютера в течение времени, превышающего возраст нашей Вселенной (20 млн. лет). Впрочем, в свое время, когда АНБ принимало в качестве национального криптографического стандарта алгоритм DES (патент США N3958081), основанный на так называемых цепях Фейстеля (), в качестве гарантии его стойкости давалось время последовательного перебора комбинаций ключа длиной 56 бит не менее 100 лет непрерывного машинного счета Cray-1.
Рисунок 12. Схема цикла сети Фейстеля
В классической цепи Фейстеля каждый двоичный блок делится на две половины, поочередно крест-накрест перемешивая которые и одновременно закрывая одну половину случайными последовательностями бит на основе ключа, за несколько циклов (16 и более) шифруется весь блок информации. Такая схема шифрования информации гарантирует уникальность ключа и целостность блока: в случае несовпадения хотя бы одного бита (ключа или блока) информация в блоке полностью теряется.
Во избежании искажений информации при передаче в канале связи используются контрольные проверки на четность.
А.Леваков. Шифрование как средство информационной гигиены, Известия N75 (25913) 26.4.2001.
Менее чем через четверть века гарантированный специалистами рубеж стойкости алгоритма DES был пройден с помощью Интернета и параллельной обработки данных всего за несколько часов. Но не все шифры так легко и быстро вскрываются.
Не так давно ФБР призналось в том, что даже специалистам АНБ понадобилось больше года на расшифровку двух файлов, найденных в компьютере одного из организаторов взрыва в Международном торговом центре в 1993 году. Тогда спецслужбам удалось предотвратить взрывы 11 американских авиалайнеров. Как любил повторять отец кибернетики Ноберт Винер любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит затраченных средств, усилий и времени.
Видимо поэтому алгоритмы и программы, реализующие изощренные математические методы атаки на шифры, являются еще более охраняемой тайной, чем сами шифры. История Тьюринга и его машины служит наглядным примером этому.
Jack Kelley. Terror groups hide behind Web encryption, USA TODAY, 06/19/2001.
Вот почему, принимая новый стандарт криптографического алгоритма, AES исключительно в интересах его коммерческого использования (цифровой аудио и видеозаписи, финансовых и биллинговых транзакций и др.), АНБ дает гарантию его стойкости (секретности) с поправкой на быстродействие современных суперкомпьютеров, о непрерывно возрастающих возможностях которых речь пойдет впереди.
Announcing the ADVANCED ENCRYPTION STANDARD (AES). Federal Information Processing Standards Publication, 2001.
