Приключения Люцифера во «Дворце головоломок»
Трудно переоценить фундаментальный вклад Клода Шеннона в наше время. При этом Шеннон наш современник, а не какая-то совсем уж историческая личность. Безусловно, Да Винчи и Ньютон — не менее мощные фигуры в масштабах человеческой истории, но жили они давно. Шеннон не зря считается одним из «отцов информационной эпохи». Его труды легли в её основу, но сегодня речь пойдёт не о нём, а об одном из тех, кто развивал некоторые его идеи. Одними из важнейших результатов работы Клода Шеннона являются заложенные им основы современной криптографии. Именно его подход к криптографии как к науке и послужил её переходу из искусства в ремесло. В «теории связи в секретных системах» Шеннон впервые ввёл фундаментальные понятия криптографии.
Доподлинно неизвестно, кто первым придумал такой криптографический примитив, как блочный шифр, поскольку на протяжении веков многие криптографы разбивали открытый текст на блоки для шифрования, однако современные блочные шифры своим появлением обязаны именно Шеннону. В статье, на которую я сослался выше, он сформулировал условия стойкости блочного шифра. Такой шифр должен обладать свойствами перемешивания и рассеивания. Рассеивание — это свойство шифра, при котором один символ открытого текста влияет на несколько символов зашифрованного текста, в идеальном случае на все символы в пределах одного блока. При выполнении этого условия шифрование двух минимально различающихся между собой блоков текста даёт различные блоки зашифрованного текста. Свойство перемешивания влияет на способность шифра скрывать зависимости между символами открытого и зашифрованного текста, то есть снижает статистические и функциональные закономерности.
До 1970-х, по меткому выражению Дэвида Кана, криптография практически полностью находилась на службе бога войны Марса. Гражданское применение криптографии являлось уделом редких энтузиастов. Появление общих вычислений в начале 1970-х годов ясно показало, что гражданским правительственным учреждениям, банкам и другим организациям тоже необходимо защищать свои данные, однако большая часть полезной информации о шифровании находилась под колпаком силовых структур. В США на рынке существовало некоторое количество проприетарных систем, однако за пределами АНБ вряд ли кто-то знал, что такое надёжный алгоритм шифрования. При этом в других странах ситуация была ещё хуже.
Итак, гражданская сфера сформировала ярко выраженный спрос, а с предложением было всё очень грустно. Нужен был единый, сильный стандарт, вызывающий доверие. Принятие и внедрение такого стандарта серьёзно бы повлияло на темпы роста рынка информационных технологий и подтянуло бы за собой смежные отрасли. Поэтому NBS (национальное бюро стандартов, сегодня NIST) сформировало конкурсный запрос на разработку таких алгоритмов шифрования. В конечном итоге победил стандарт на основе сети Фейстеля, предложенный IBM, и сегодня мы знаем его как DES (Data Encryption Standard). И хоть оригинальный алгоритм приказал долго жить, история его появления и падения интересна и достаточно подробно описана в Википедии. Я же хочу в этой статье чуть подробнеe затронуть историю его создателя — Хорста Фейстеля, а также добавить немного «интриг, скандалов и расследований».
Странно, но факт, материалов как на Хабре, так и, в общем, в сети о нём не так уж и много. В большинстве его имя упоминается между делом, хотя практически все блочные алгоритмы шифрования строятся с помощью одного из двух методов — сеть Фейстеля или подстановочно-перестановочная сеть (SP-сеть), а оба этих метода предложил именно Хорст Фейстель.
В принципе в Вики русскоязычная статья о нём входит в число добротных статей в отличие от куцей английской версии. Переписывать её смысла нет, а вот дополнение не только уместно, но и познавательно. Прежде всего, Фейстелю с одной стороны повезло родиться в то время, когда криптографии как науки не существовало, однако не очень повезло с местом рождения. Он родился в Германии в 1915 году в протестантской семье среднего класса. Его тётя вышла замуж за богатого немецкого еврея Франца Мейера, и ещё до 1931 года они оба бежали из Германии в Швейцарию.
Хорст и его тётя Гертруда
ДворецКогда Гитлер пришел к власти в 1933 году и была восстановлена обязательная военная служба, Мейер разработал «хитрый» план, согласно которому Фейстель начал посещать летнюю школу для изучения английского языка, а затем поступил в высшую техническую школу в Цюрихе (ETH). В процессе обучения он перевёлся в университет США для завершения обучения, с перспективой получения гражданства. План сработал и Фейстель стал студентом MTI осенью 1936 года. Мейер и его жена последовали его примеру и переехали в Нью-Йорк.
Фейстель окончил институт в 1937 году по специальности физика и оставался аспирантом до 1938 года, после чего поступил в Гарвард. Он стал гражданином США 31 января 1944 года. «Как он мне говорил, на следующий день после получения гражданства ему дали допуск к совершенно секретной информации», — вспоминал Диффи. Тем не менее Фейстель подвергался определённой дискриминации из-за своего немецкого происхождения. Хотя он с детства интересовался кодами и криптографией, работать по этому профилю он не мог. Также, по словам Уитфилда Диффи, ещё во время войны он пытался заниматься криптографией, однако ему прямым текстом указывали на то, что немцу в Америке сейчас не самое лучшее время говорить о криптографии.
Наконец он получил свой шанс. После работы в радиационной лаборатории Массачусетса Фейстель устроился на работу в Кембриджский исследовательский центр ВВС (AFCRC), которому было поручено оценить авиационную систему идентификации «свой-чужой» (Identification friend or foe, IFF). Группа Фейстеля обнаружила недостатки системы и разработала исправления, основанные на криптографических началах. О развёртывании исправленной системы ничего неизвестно, тем более через несколько лет криптографическая группа AFCRC была закрыта, вероятно, из-за монополизации криптографических исследований под эгидой АНБ Министерства обороны. Хотя совершенно точно известно, что современные системы распознавания «свой-чужой» в своей основе повторяют оригинальные исследования группы Фейстеля.
В ноябре 1957 года Фейстель устроился на работу в лабораторию Линкольна MTI, где подготовил отчёт, обобщающий работу средств IFF, проделанную группой AFCRC. «Каким бы ни было конкретное применение, любая схема секретной связи должна быть тщательно проанализирована и оценена на предмет её достоинств и недостатков», — заключал Хорст. «Лучше знать, своё действительное положение, чем быть обманутым ложным чувством безопасности из-за недостатка информации или, возможно, даже какой-то изобретательской гордости».
Однако в лаборатории Линкольна Фейстель не прижился так же, как и в MITRE, куда он перешёл в 1961 году. Опять же, учёный периодически сталкивался с дискриминацией, хотя он гордился своим немецким наследием и немецкой инженерией. Послевоенный мировой порядок также не вызывал у него восторга. В личных беседах с коллегами и семьёй он неоднократно называл ООН «клубом победителей».
Возможно, именно во время работы в MITRE Фейстель сделал свои первые серьёзные шаги в криптографической науке, но это не точно))
По словам дочери, спустя годы работы на правительственные структуры Фейстель был очень осторожен при демонстрации своего криптографического алгоритма LUCIFER, поскольку любая работа в области криптографии плотно контролировалась АНБ, но об этом немного ниже. А пока Фейстель устроился в IBM, которая наняла его специально для работы над коммерческими криптографическими приложениями. 30 июня 1971 года компания подала заявку на патент «криптографической системы с блочным шифром». АНБ сначала выпало в осадок, а потом всё-таки рассмотрело заявку и попыталось засекретить исследования, блокирующие публикацию патента. Но ребята прозевали. Приказ АНБ от 17 октября 1973 года появился через пять месяцев после публикации статьи в Scientific American, и уже 14 ноября этого же года был отменён, а 19 марта следующего года был опубликован патент США № 3798359, держателем которого был указан Фейстель.
«Дворец головоломок»
Чтобы понимать сеттинг, в котором оказался учёный, нужно немного рассказать о «Дворце головоломок». 4 ноября 1952 года появилось новое федеральное ведомство США — National Security Agency (АНБ). Его появление прошло незамеченным, не было объявлений в прессе, дебатов в конгрессе или даже слухов. Вплоть до 1957 года в официальных документах о его существовании не было вообще никаких упоминаний. Некоторые шутники позже даже расшифровывали аббревиатуру NSA как «No Such Agency» или «Never Say Anything». Агентство до сих пор остаётся наиболее «мутной» организацией среди всех американских спецслужб, а его устав засекречен. Для примерной оценки уровня этого ведомства, достаточно упомянуть, что через некоторое время после его образования произошло постепенное смещение фокуса власти и влияния от ЦРУ к АНБ. Даже члены Конгресса были очень удивлены, когда из одного доклада сенатского комитета по разведке стало известно, что с точки зрения бюджета, наиболее влиятельным должностным лицом разведывательного сообщества США является директор АНБ. В книге Виктора Марчетти «ЦРУ и культ разведки» упоминается, что директор ЦРУ Ричард Хелмс был так расстроен отсутствием реальной власти, что в открытую обмолвился своим сотрудникам, что в то время как он в качестве директора ЦРУ теоретически несёт всю ответственность за разведывательную деятельность страны, в действительности контролирует меньше 15% операций, а оставшиеся 85% находятся в ведении Министерства обороны в лице АНБ. Однако сенатский комитет по разведке вообще предполагал, что ЦРУ контролирует не более 10% разведывательной деятельности.
С завершением проекта «Молния» (высокоскоростная логика и вычисления) в 1962 году прекратилась и поддержка АНБ несекретных публичных исследований. «Молния» помогла раскачать научные исследования в связанных областях. Считалось, что конкуренция в гражданском секторе гарантирует поток технологических достижений в компьютерных и смежных областях. АНБ дистанцировалось от большинства таких исследований и с помощью подконтрольных консультантов и подрядчиков сосредоточило внимание и средства на науке, в которой у него не было конкурентов, но тут как чёрт из табакерки появился LUCIFER)))
Одним из первых массовых применений компьютеров того времени отметилась банковская сфера. Компьютеры использовались достаточно широко, начиная с осуществления множественных межбанковских переводов и заканчивая простыми записями ночных транзакций территориально удалённых банкоматов. Компьютерная преступность уже появилась, хотя до сегодняшнего размаха ей было ещё очень далеко. Обладая достаточными знаниями и доступом к терминалу, можно было обманом провести средства на фиктивный счёт или снять в банкомате наличные. Чтобы противостоять таким действиям и осознавая, что передача данных обладает огромным рыночным потенциалом, председатель правления «голубого гиганта»Томас Уотсон-младший в конце 1960-х годов создал исследовательскую группу в лаборатории IBM в Йорктаун-Хайтс. Эта группа под руководством Хорста Фейстеля и разработала шифр под кодовым названием LUCIFER, который почти сразу был закуплен Lloyd’s для использования в системе выдачи наличных, также разработанной IBM. Вдохновлённое этим успехом, руководство IBM предложило одному из своих инженеров Уолтеру Тачмэну возглавить группу разработки продуктов для защиты данных, которая должна была превратить LUCIFER в высоколиквидный товар. Следующие два года команда потратила на доведение алгоритма до ума, чтобы итоговый продукт смог выйти в свободное коммерческое плавание. В ходе испытаний эксперты подвергали шифр различным криптоаналитическим атакам, и наконец, в 1974 году рубикон был пройден.
Примерно в то же время, когда IBM обратила свой взор на криптографию, другая группа в полосатых купальниках с большим интересом начала изучать этот же предмет. В 1968 году Национальное бюро стандартов (сегодня NIST), которому с 1965 года было поручено разрабатывать различные стандарты для использования федеральным правительством, инициировало серию исследований для определения потребностей правительства в компьютерной безопасности. В результате проведённых исследований бюро пришло к выводам, что алгоритм шифрования, который мог бы послужить общегосударственным стандартом для хранения и передачи несекретных данных, нужен кровь из носу. В итоге, как я уже упоминал в начале статьи, был сформирован конкурсный запрос на такой алгоритм.
Для IBM, у которой уже всё было на мази, момент оказался как нельзя более удачным. Названный Дэвидом Каном «самой крошечной когда-либо созданной шифровальной машиной», LUCIFER как продукт представлял собой небольшой чип, содержащий сложную интегральную схему. Изначально шифр разрабатывался со 128-битным ключом, но прежде чем он попал в бюро стандартов, ключ «загадочным» образом похудел чуть более чем в два раза до 56 бит.
С самого начала «Дворец головоломок» проявлял огромный интерес к проекту Фейстеля, косвенно даже приложив руку к разработке структур S-блоков. «IBM постоянно сотрудничала с АНБ», — признавал старший сотрудник лаборатории IBM в Йорктаун-Хайтс Алан Конхейм. «Они приходили каждые пару месяцев, чтобы узнать, чем занимается IBM». Впервые за свою историю АНБ столкнулось с конкуренцией внутри собственной страны. Причём конкуренты были высококвалифицированными профессионалами, поддерживаемыми серьёзными средствами и больше заинтересованными в совершенстве, чем в скорости. В течение многих лет «Дворец головоломок» становился всё более зависимым от постоянно расширяющегося потока международных данных, содержащих информацию, которую АНБ считало напрямую касающейся национальной безопасности. Сообщения о нефтяных сделках с Ближнего Востока, финансовых операциях из Европы, торговых стратегиях из Японии и, конечно, любая информация из-за «железного занавеса» аккумулировалась в стенах агентства. Ему приходилось постоянно расширять свои сети и собирать ценную экономическую информацию. Не меньшее или даже большее значение имела дипломатическая и военная разведка в странах третьего мира. Сообщения из Африки, Южной Америки и Азии, зашифрованные по большей части старинными, дешёвыми или простейшими средствами, становились лёгкой добычей АНБ. Время от времени через такие «чёрные ходы» проходили такие жемчужины, как доклад министра страны третьего мира своему министерству иностранных дел о приватном разговоре с советским или китайским коллегой. Как говорили сотрудники АНБ, «вы будете удивлены количеством информации, которую мы получаем о коммунистических объектах из некоммунистических стран».
Разработка и широкое использование экономичного и хорошо защищённого устройства шифрования данных грозило превратить этот полноводный информационный поток в мутный и жалкий ручей. Однако нервозность по поводу конкуренции извне этим не ограничивалась. Криптографы агентства были обеспокоены не меньше, хотя и по противоположной причине. Для них главным опасением было то, что сторонние исследователи случайно могли наткнуться на методы, используемые самим АНБ, тем самым скомпрометировав его коды. В результате закрытых переговоров представителей агентства с IBM, компания согласилась уменьшить размер ключа со 128 до 56 бит и засекретить некоторые подробности выбора S-блоков для шифрования. После того как был представлен усечённый шифр, бюро стандартов передало его в АНБ для «глубокого анализа». Агентство, в свою очередь, сертифицировало алгоритм как «свободный от каких-либо статистических или математических недостатков» и горячо рекомендовало его в качестве наилучшего кандидата на национальный стандарт шифрования данных.
Это решение вызвало немедленную бурю в научном сообществе. Некоторые критики, указывая на кургузый ключ, обвиняли АНБ в подлоге. По их мнению, агентство добивалось того, чтобы шифр был достаточно сильным для предотвращения корпоративных угроз, но простым для криптоаналитиков агентства. Другие указывали на то, что агентство приложило ручонки к критически важным S-блокам, и выражали опасения, что АНБ легко и непринуждённо могло встроить бэкдоры, позволяющие без труда вскрыть шифр. Отсюда и сопротивление АНБ длинным ключам алгоритма. Причина его, по мнению критиков, была проста. Поскольку DES в конечном итоге должен был использоваться в коммерческих целях и устанавливаться на широкий ассортимент оборудования, продаваемого за границей, АНБ не хотело создавать себе проблем, допустив распространение за рубежом сильного шифра, а слабые его места позволят агентству проникать в каждую линию связи и банк данных, использующие стандарт.
По предположению Дэвида Кана в АНБ боролись две группы сотрудников. Сторона, занимающаяся взломом, хотела, чтобы шифр был достаточно слаб для расшифровки при использовании его за рубежом, а группа, ответственная за сертификацию шифров для использования американцами, хотела, чтобы шифр был действительно сильным. Результатом стал компромисс: часть шифра — S-блоки, была усилена, другая часть шифра, то есть ключ, была ослаблена. Главными критиками модифицированного Люцифера стали Хеллман и Диффи.
Некоторое время продолжались напряжённые споры. На первом этапе, в августе 1976 года, чиновники бюро защищали выбор DES, заявляя, что, учитывая существующий технологический уровень, брутфорс шифра займет неадекватно большое количество времени. Однако состав конкурсной комиссии бюро немного бросает тень на беспристрастность её решений. Руководителем проекта был Деннис Бранстад, бывший сотрудник АНБ, а Артур Левенсон, консультант бюро по проекту, был, по крайней мере, до конца 1960-х годов, одним из самых высокопоставленных взломщиков АНБ, прежде чем ушёл в IBM.
Спорщики расходились во мнениях относительно стоимости, времени разработки и времени, необходимого для создания компьютера, способного взломать алгоритм. Наконец, сенатский комитет по разведке изучил разногласия и пришёл к выводу, что, хотя АНБ «убедило» IBM в достаточности усечённого ключа и поучаствовало в доработке структур S-блоков, никаких косяков в алгоритме не обнаружено. Дебаты по поводу DES утихли, и 15 июля 1977 года он стал официальным государственным гражданским шифром, а как минимум полдюжины фирм начали выпускать оборудование, заряженное этим алгоритмом.
Одержав победу в битве за DES, безопасники нацелились на ещё большую потенциальную угрозу — академические исследования в области криптографии. Внезапно во многих университетских городках начали посвящать значительную энергию и ресурсы предмету, который раньше был уделом узкого круга людей и организаций. Исследования носили как теоретический, так и прикладной характер. Некоторые учёные разрабатывали оборудование, другие глубже копали математические основы. Тема настолько зашла, что несколько колледжей начали предлагать курсы по криптографии, а в 1977 году появился научный журнал, посвящённый исключительно этой теме. Самый большой удар АНБ, должно быть, нанесли в 1976 году Хеллман и Диффи, выступавшие против DES, опубликовав свои «Новые направления в современной криптографии».
Основная проблема, с которой столкнулось АНБ, пытаясь остановить эти исследования и таким образом восстановить свою гегемонию, заключалась в том, что, в отличие от корпоративного мира с сильной зависимостью от оборонных контрактов и консервативных советов директоров, университетские исследователи были по большей части независимы. Рукопожатные отношения, которые «дворец головоломок» установил с IBM, оказались невозможны с относительно независимой и строптивой учёной вольницей. Тем не менее кое-какие рычаги влияния у АНБ сохранились, но это уже совершенно другая история.
По мнению многих криптографов, Хорст Фейстель сыграл ключевую роль в криптографических исследованиях IBM. Мартин Хеллман говорил, что публикация Фейстеля в Scientific American открыла глаза многим исследователям, работавшим в этой области. Прошло много времени, но до сих пор базовая конструкция многих алгоритмов шифрования строится на структурах, получивших его имя.
Так рецепт Клода Шеннона по достижению надёжности засекречивания от 1949 года лёг в основу LUCIFER и его преемников. 26 мая 2002 года DES был заменён новым алгоритмом AES (Advanced Encryption Standard), а борьба за коммерческую доступность высококлассных алгоритмов шифрования не утихает и по сей день.
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
-15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
