Анализ информационных систем: криптоанализ и скрытые аспекты

Введение

Изучение анализа информационных систем с целью выявления их скрытых сторон.

Криптоанализ (от греческого kryptós, "скрытый", и analýein, "анализировать") – это процесс анализа информационных систем для понимания скрытых аспектов этих систем. Криптоанализ используется для преодоления криптографической защиты и получения доступа к содержимому зашифрованных сообщений, даже если криптографический ключ неизвестен. Помимо математического анализа криптографических алгоритмов, криптоанализ включает изучение атак по сторонним каналам, которые не направлены на уязвимости самих криптографических алгоритмов, а эксплуатируют недостатки в их реализации. Хотя цель оставалась неизменной, методы и техники криптоанализа значительно изменились на протяжении истории криптографии, адаптируясь к возрастающей криптографической сложности – от ручных методов прошлого, через машины, такие как британские "Бомбы" и компьютеры "Colossus" в Блетчли-парке во время Второй мировой войны, до современных математически сложных компьютерных схем. Методы взлома современных криптосистем часто включают решение специально разработанных задач из чистой математики, наиболее известной из которых является целочисленное разложение на множители.

Обзор

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

Количество информации, доступной для злоумышленника

Криптоаналитические атаки могут быть классифицированы в зависимости от того, какая информация доступна атакующему. В качестве базовой отправной точки обычно предполагается, что для целей анализа известен общий алгоритм; это Максим Шеннона «враг знает систему», в свою очередь, эквивалентный принципу Керкхоффса. Это разумное предположение на практике – на протяжении истории существует множество примеров секретных алгоритмов, ставших широко известными различными путями, такими как шпионаж, предательство и обратная разработка. (Иногда шифры были взломаны посредством чистой дедукции; например, немецкий шифр «Лоренц», японский код «Пурпурный» и различные классические схемы):
Только шифротекст: криптоаналитик имеет доступ только к набору шифротекстов или кодотекстов. Известный открытый текст: у атакующего есть набор шифротекстов, для которых известен соответствующий открытый текст. Выбранный открытый текст (выбранный шифротекст): атакующий может получить шифротексты (открытые тексты), соответствующие произвольному набору открытых текстов (шифротекстов) по своему выбору. Адаптивный выбранный открытый текст: как атака с выбранным открытым текстом, но атакующий может выбирать последующие открытые тексты на основе информации, полученной из предыдущих шифрований, аналогично адаптивной атаке с выбранным шифротекстом. Атака на связанные ключи: как атака с выбранным открытым текстом, но атакующий может получить шифротексты, зашифрованные с использованием двух разных ключей. Ключи неизвестны, но известна связь между ними, например, два ключа, различающиеся одним битом.

Требуемые вычислительные ресурсы

Атаки также могут характеризоваться ресурсами, которые они требуют. Эти ресурсы включают:
Время – количество вычислительных шагов (например, тестовых шифрований), которые необходимо выполнить. Память – объем памяти, необходимый для проведения атаки. Данные – количество и тип открытых текстов и шифротекстов, требуемых для конкретного подхода. Иногда трудно точно предсказать эти величины, особенно когда атака не является практически реализуемой для тестирования. Однако академические криптоаналитики обычно приводят хотя бы примерную оценку сложности своих атак, например, говоря: "Коллизии SHA-1 теперь 252". Брюс Шнайер отмечает, что даже вычислительно непрактичные атаки можно считать взломами: "Взлом шифра просто означает обнаружение слабости в шифре, которую можно использовать со сложностью, меньшей, чем полный перебор. Неважно, что полный перебор может потребовать 2<sup>128</sup> шифрований; атака, требующая 2<sup>110</sup> шифрований, будет считаться взломом. Проще говоря, взлом может быть просто сертификационной слабостью: доказательством того, что шифр не работает так, как заявлено". Поэтому полная криптосистема может быть стойкой, даже если упрощенные варианты раундов слабы. Тем не менее, частичные взломы, приближающиеся к взлому исходной криптосистемы, могут означать, что полный взлом последует; успешным атакам на DES, MD5 и SHA-1 предшествовали атаки на ослабленные версии. В академической криптографии слабость или взлом схемы обычно определяется довольно консервативно: для этого может потребоваться непрактичное количество времени, памяти или известных открытых текстов. Также может потребоваться, чтобы атакующий мог выполнять действия, недоступные многим реальным злоумышленникам: например, выбирать конкретные открытые тексты для шифрования или даже запрашивать шифрование открытых текстов с использованием нескольких ключей, связанных с секретным ключом. Кроме того, атака может раскрывать лишь небольшое количество информации, достаточное для доказательства несовершенства криптосистемы, но недостаточное для практического использования злоумышленниками. Наконец, атака может быть применима только к ослабленной версии криптографических инструментов, например, к блочному шифру с уменьшенным количеством раундов, как шаг к взлому всей системы.

Attacks can also be characterised by the resources they require. Those resources include:
Time – the number of computation steps (e. g., test encryptions) which must be performed. Memory – the amount of storage required to perform the attack. Data – the quantity and type of plaintexts and ciphertexts required for a particular approach. It is sometimes difficult to predict these quantities precisely, especially when the attack is not practical to actually implement for testing. But academic cryptanalysts tend to provide at least the estimated order of magnitude of their attacks' difficulty, saying, for example, "SHA 1 collisions now 252." Bruce Schneier notes that even computationally impractical attacks can be considered breaks: "Breaking a cipher simply means finding a weakness in the cipher that can be exploited with a complexity less than brute force. Never mind that brute force might require 2128 encryptions; an attack requiring 2110 encryptions would be considered a break simply put, a break can just be a certificational weakness: evidence that the cipher does not perform as advertised." so it's possible for the full cryptosystem to be strong even though reduced round variants are weak. Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow; the successful attacks on DES, MD5, and SHA 1 were all preceded by attacks on weakened versions. In academic cryptography, a weakness or a break in a scheme is usually defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts. It also might require the attacker be able to do things many real world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or even to ask for plaintexts to be encrypted using several keys related to the secret key. Furthermore, it might only reveal a small amount of information, enough to prove the cryptosystem imperfect but too little to be useful to real world attackers. Finally, an attack might only apply to a weakened version of cryptographic tools, like a reduced round block cipher, as a step towards breaking the full system.

История

Криптоанализ развивался параллельно с криптографией, и это противостояние прослеживается на протяжении всей истории криптографии — новые шифры создаются для замены устаревших, взломанных, а новые методы криптоанализа разрабатываются для взлома усовершенствованных схем. На практике их рассматривают как две стороны одной медали: надёжная криптография требует разработки с учётом возможных методов криптоанализа.

Классические шифры

Хотя само слово "криптоанализ" относительно новое (оно было придумано Уильямом Фридманом в 1920 году), методы взлома кодов и шифров гораздо старше. Дэвид Кан отмечает в книге "Кодбрейкеры", что арабские ученые первыми систематически документировали криптоаналитические методы. Первое известное описание криптоанализа дал Аль-Кинди (ок. 801–873 гг., также известный как "Алькиндус" в Европе), арабский ученый-энциклопедист IX века, в трактате "Рисала фи Истихрадж аль-Муамма" (Трактат о извлечении смысла из криптографических сообщений). В этом трактате содержится первое описание метода частотного анализа. Таким образом, Аль-Кинди считается первым криптоаналитиком в истории. Его новаторская работа была вдохновлена Аль-Халилом (717–786), который написал "Книгу криптографических сообщений", содержащую первое применение перестановок и сочетаний для перечисления всех возможных арабских слов с гласными и без них. Частотный анализ – основной инструмент для взлома большинства классических шифров. В естественных языках одни буквы алфавита встречаются чаще других; в английском языке "E" – наиболее распространенная буква в любом образце открытого текста. Аналогично, диграф "TH" – наиболее вероятная пара букв в английском языке и так далее. Частотный анализ опирается на неспособность шифра скрыть эту статистику. Например, в простом шифре подстановки (где каждая буква просто заменяется другой), наиболее часто встречающаяся буква в шифротексте будет вероятным кандидатом на "E". Поэтому частотный анализ такого шифра относительно прост, при условии, что шифротекст достаточно длинный, чтобы обеспечить достаточно представительный подсчет букв алфавита, которые он содержит. Изобретение Аль-Кинди метода частотного анализа для взлома моноалфавитных шифров подстановки стало самым значительным криптоаналитическим достижением до Второй мировой войны. В "Рисала фи Истихрадж аль-Муамма" Аль-Кинди описал первые криптоаналитические методы, в том числе некоторые для полиалфавитных шифров, классификацию шифров, арабскую фонетику и синтаксис, и, что наиболее важно, дал первые описания частотного анализа. Он также рассматривал методы шифрования, криптоанализ определенных шифров и статистический анализ букв и буквенных сочетаний в арабском языке. Успешный криптоанализ, несомненно, оказал влияние на историю; возможность читать предполагаемые тайные мысли и планы других может быть решающим преимуществом. Например, в Англии в 1587 году Мария, королева Шотландии, была осуждена и казнена за измену в результате ее участия в трех заговорах с целью убийства Елизаветы I. Планы были раскрыты после того, как ее зашифрованная переписка с соучастниками была расшифрована Томасом Фелипсом. В Европе в XV и XVI веках идея полиалфавитного шифра подстановки была разработана, в частности, французским дипломатом Блезом де Виженером (1523–96). На протяжении трех столетий шифр Вигенера, использующий повторяющийся ключ для выбора различных алфавитов шифрования поочередно, считался абсолютно надежным ("le chiffre indéchiffrable" – "неразгадываемый шифр"). Тем не менее, Чарльзу Бэббиджу (1791–1871) и позже, независимо от него, Фридриху Казиски (1805–81) удалось взломать этот шифр. Во время Первой мировой войны изобретатели в нескольких странах разработали роторные шифровальные машины, такие как "Энигма" Артура Шербиуса, в попытке минимизировать повторения, которые использовались для взлома системы Вигенера.

Although the actual word "cryptanalysis" is relatively recent (it was coined by William Friedman in 1920), methods for breaking codes and ciphers are much older. David Kahn notes in The Codebreakers that Arab scholars were the first people to systematically document cryptanalytic methods. The first known recorded explanation of cryptanalysis was given by Al Kindi (c. 801–873, also known as "Alkindus" in Europe), a 9th century Arab polymath, in Risalah fi Istikhraj al Mu'amma (A Manuscript on Deciphering Cryptographic Messages). This treatise contains the first description of the method of frequency analysis. Al Kindi is thus regarded as the first codebreaker in history. His breakthrough work was influenced by Al Khalil (717–786), who wrote the Book of Cryptographic Messages, which contains the first use of permutations and combinations to list all possible Arabic words with and without vowels. Frequency analysis is the basic tool for breaking most classical ciphers. In natural languages, certain letters of the alphabet appear more often than others; in English, "E" is likely to be the most common letter in any sample of plaintext. Similarly, the digraph "TH" is the most likely pair of letters in English, and so on. Frequency analysis relies on a cipher failing to hide these statistics. For example, in a simple substitution cipher (where each letter is simply replaced with another), the most frequent letter in the ciphertext would be a likely candidate for "E". Frequency analysis of such a cipher is therefore relatively easy, provided that the ciphertext is long enough to give a reasonably representative count of the letters of the alphabet that it contains. Al Kindi's invention of the frequency analysis technique for breaking monoalphabetic substitution ciphers was the most significant cryptanalytic advance until World War II. Al Kindi's Risalah fi Istikhraj al Mu'amma described the first cryptanalytic techniques, including some for polyalphabetic ciphers, cipher classification, Arabic phonetics and syntax, and most importantly, gave the first descriptions on frequency analysis. He also covered methods of encipherments, cryptanalysis of certain encipherments, and statistical analysis of letters and letter combinations in Arabic. Successful cryptanalysis has undoubtedly influenced history; the ability to read the presumed secret thoughts and plans of others can be a decisive advantage. For example, in England in 1587, Mary, Queen of Scots was tried and executed for treason as a result of her involvement in three plots to assassinate Elizabeth I of England. The plans came to light after her coded correspondence with fellow conspirators was deciphered by Thomas Phelippes. In Europe during the 15th and 16th centuries, the idea of a polyalphabetic substitution cipher was developed, among others by the French diplomat Blaise de Vigenère (1523–96). For some three centuries, the Vigenère cipher, which uses a repeating key to select different encryption alphabets in rotation, was considered to be completely secure (le chiffre indéchiffrable—"the indecipherable cipher"). Nevertheless, Charles Babbage (1791–1871) and later, independently, Friedrich Kasiski (1805–81) succeeded in breaking this cipher. During World War I, inventors in several countries developed rotor cipher machines such as Arthur Scherbius' Enigma, in an attempt to minimise the repetition that had been exploited to break the Vigenère system.

Шифры из Первой и Второй мировых войн

В Первую мировую войну расшифровка телеграммы Циммермана сыграла решающую роль в вступлении Соединенных Штатов в войну. Во время Второй мировой войны союзники получили огромную выгоду от совместного успеха в криптоанализе немецких шифров, включая машину «Энигма» и шифр «Лоренц», а также японских шифров, в частности «Purple» и JN 25. Разведданные «Ultra» приписывают все, от сокращения окончания европейской войны до двух лет, до определения ее исхода. Война на Тихом океане также получила значительную помощь от разведки «Magic». Криптоанализ вражеских сообщений сыграл важную роль в победе союзников во Второй мировой войне. Ф. Уинтерботам цитировал Верховного главнокомандующего союзными войсками на Западном фронте, Дуайта Эйзенхауэра, который в конце войны описал разведку «Ultra» как «решающую» для победы союзников. Сэр Гарри Хинсли, официальный историк британской разведки во Второй мировой войне, сделал аналогичную оценку, заявив, что «Ultra» сократила войну «как минимум на два года и, вероятно, на четыре года»; более того, он отметил, что без «Ultra» исход войны был бы неопределенным. На практике частотный анализ опирается не только на статистику, но и на лингвистические знания, однако с усложнением шифров математика приобрела все большее значение в криптоанализе. Это изменение особенно проявилось перед и во время Второй мировой войны, когда для взлома шифров стран Оси требовался новый уровень математической подготовки. Кроме того, именно в эту эпоху автоматизация впервые была применена в криптоанализе – с помощью польского устройства «Bomba», британского «Bombe», оборудования с перфокартами и компьютеров «Colossus» – первых электронных цифровых компьютеров, управляемых программой.

Показатель

С помощью взаимных машинных шифров, таких как шифр Лоренца и машина «Энигма», использовавшиеся нацистской Германией во время Второй мировой войны, каждое сообщение имело свой собственный ключ. Как правило, оператор, осуществляющий передачу, сообщал оператору, принимающему сообщение, об этом ключе, передавая некоторое открытое и/или зашифрованное сообщение перед самим зашифрованным сообщением. Это называлось индикатором, поскольку он указывал оператору-получателю, как настроить свою машину для расшифровки сообщения. Недостаточно продуманные и реализованные системы индикаторов позволили сначала польским, а затем британским криптографам из Блетчли-парка взломать систему шифрования «Энигма». Аналогичные слабые системы индикации позволили британцам выявить параметры, которые привели к определению шифровой системы Lorenz SZ40/42 и полному взлому ее сообщений, даже не видя самой шифровальной машины.

Асимметричные шифры

Асимметричная криптография (или криптография с открытым ключом) – это криптография, основанная на использовании двух (математически связанных) ключей: одного закрытого и одного открытого. Такие шифры неизменно опираются на "сложные" математические задачи как основу своей безопасности, поэтому очевидной точкой атаки является разработка методов для решения этих задач. Безопасность криптографии с двумя ключами зависит от математических вопросов, в отличие от криптографии с одним ключом, и, наоборот, связывает криптоанализ с более широкими математическими исследованиями новым способом. Асимметричные схемы разрабатываются исходя из (предполагаемой) сложности решения различных математических проблем. Если удастся найти более эффективный алгоритм для решения проблемы, система будет скомпрометирована. Например, безопасность схемы обмена ключами Диффи — Хеллмана зависит от сложности вычисления дискретного логарифма. В 1983 году Дон Копперсмит обнаружил более быстрый способ нахождения дискретных логарифмов (в определенных группах), что потребовало от криптографов использовать более крупные группы (или группы другого типа). Безопасность RSA зависит (частично) от сложности факторизации целых чисел – прорыв в факторизации повлияет на безопасность RSA. В 1980 году факторизация сложного 50-значного числа требовала 10¹² элементарных компьютерных операций. К 1984 году алгоритмы факторизации достигли такого уровня, что 75-значное число можно было разложить на множители за 10¹² операций. Прогресс в вычислительной технике также означал, что эти операции можно было выполнять гораздо быстрее. Закон Мура предсказывает, что скорость компьютеров продолжит расти. Методы факторизации также могут совершенствоваться, но, скорее всего, будут зависеть от математической интуиции и творчества, которые невозможно успешно предсказать. 150-значные числа, ранее использовавшиеся в RSA, были успешно разложены на множители. Усилия были больше, чем ранее, но не были чрезмерными для современных быстрых компьютеров. К началу XXI века 150-значные числа больше не считались достаточным размером ключа для RSA. В 2005 году числа с несколькими сотнями цифр все еще считались слишком сложными для факторизации, хотя методы, вероятно, будут продолжать улучшаться, что потребует увеличения размера ключа или использования других методов, таких как криптография на эллиптических кривых. Еще одна отличительная особенность асимметричных схем заключается в том, что, в отличие от атак на симметричные криптосистемы, любой криптоанализ имеет возможность использовать знания, полученные из открытого ключа.

Asymmetric cryptography (or public key cryptography) is cryptography that relies on using two (mathematically related) keys; one private, and one public. Such ciphers invariably rely on "hard" mathematical problems as the basis of their security, so an obvious point of attack is to develop methods for solving the problem. The security of two key cryptography depends on mathematical questions in a way that single key cryptography generally does not, and conversely links cryptanalysis to wider mathematical research in a new way. Asymmetric schemes are designed around the (conjectured) difficulty of solving various mathematical problems. If an improved algorithm can be found to solve the problem, then the system is weakened. For example, the security of the Diffie–Hellman key exchange scheme depends on the difficulty of calculating the discrete logarithm. In 1983, Don Coppersmith found a faster way to find discrete logarithms (in certain groups), and thereby requiring cryptographers to use larger groups (or different types of groups). RSA's security depends (in part) upon the difficulty of integer factorization – a breakthrough in factoring would impact the security of RSA. In 1980, one could factor a difficult 50 digit number at an expense of 1012 elementary computer operations. By 1984 the state of the art in factoring algorithms had advanced to a point where a 75 digit number could be factored in 1012 operations. Advances in computing technology also meant that the operations could be performed much faster. Moore's law predicts that computer speeds will continue to increase. Factoring techniques may continue to do so as well, but will most likely depend on mathematical insight and creativity, neither of which has ever been successfully predictable. 150 digit numbers of the kind once used in RSA have been factored. The effort was greater than above, but was not unreasonable on fast modern computers. By the start of the 21st century, 150 digit numbers were no longer considered a large enough key size for RSA. Numbers with several hundred digits were still considered too hard to factor in 2005, though methods will probably continue to improve over time, requiring key size to keep pace or other methods such as elliptic curve cryptography to be used. Another distinguishing feature of asymmetric schemes is that, unlike attacks on symmetric cryptosystems, any cryptanalysis has the opportunity to make use of knowledge gained from the public key.

Приложения квантовых вычислений для криптоанализа

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