Атаки на основе известного открытого текста в криптоанализе

Введение

Модель атаки для криптоанализа с доступом как к открытому, так и к зашифрованному тексту.

Атака по известному открытому тексту (KPA) — это модель атаки для криптоанализа, в которой злоумышленник имеет доступ как к открытому тексту (называемому исходным текстом), так и к его зашифрованной версии (шифротексту). Эти данные могут быть использованы для раскрытия секретных ключей и кодовых книг. Термин "исходный текст" возник в Блетчли-парке, британской операции по дешифрованию во время Второй мировой войны, где он был определен как:

История

Использование термина "подстилка" (crib) было адаптировано из сленгового выражения, обозначающего списывание (например, "Я списал ответ из твоей контрольной работы"). Изначально "подстилка" представляла собой буквальный или междустрочный перевод текста на иностранном языке — обычно латинского или греческого — который студентам могли задать для перевода с оригинала. Идея "подстилки" заключается в том, что криптологи анализируют неразборчивый шифротекст, но если у них есть намек на слово или фразу, которые, вероятно, должны содержаться в шифротексте, у них появляется "зацепка", способ взломать его. Если их случайные атаки на шифр иногда приводят к появлению этих слов или (что предпочтительнее) фраз, они понимают, что могут быть на правильном пути. Когда эти слова или фразы обнаруживаются, они используют настройки, которые позволили их выявить, для обработки всего зашифрованного сообщения с хорошим результатом. В случае с "Энигмой" немецкое высшее командование тщательно следило за общей безопасностью системы "Энигма" и понимало возможную проблему, связанную с "подстилками". Операторы же, работавшие ежедневно, были менее внимательны. Команда Блетчли-парка могла угадывать часть открытого текста, основываясь на времени отправки сообщения и распознавая стандартные оперативные сообщения. Например, ежедневный прогноз погоды передавался немцами каждый день в одно и то же время. Благодаря регламентированному стилю военных докладов, он содержал слово Wetter (немецкое "погода") в одном и том же месте в каждом сообщении. (Знание местных погодных условий помогало Блетчли-парку угадывать и другие части открытого текста.) Другие операторы также отправляли стандартные приветствия или представления. Офицер, дислоцированный в депрессии Каттара, постоянно сообщал об отсутствии новостей. Другим известным примером является фраза "Хайль Гитлер", встречающаяся в конце сообщения. В Блетчли-парке во время Второй мировой войны прилагались значительные усилия для использования (и даже для того, чтобы заставить немцев создавать) сообщения с известным открытым текстом. Например, когда "подстилок" не хватало, Блетчли-парк иногда просил Королевские ВВС "засеять" определенный район Северного моря минами (процесс, получивший название "садоводство" по очевидной аналогии). В вскоре отправленных сообщениях "Энигмы", скорее всего, содержалось название района или порта, которому угрожали мины. Сами немцы могли быть в этом отношении весьма услужливы. Всякий раз, когда один из завербованных немецких агентов "Двойного креста" отправлял сообщение (написанное британцами) своим кураторам, они часто перешифровывали его слово в слово на "Энигме" для дальнейшей передачи в Берлин. Когда захваченный немец сообщил во время допроса, что операторам "Энигмы" было предписано кодировать числа, записывая их прописью, Алан Тьюринг просмотрел расшифрованные сообщения и установил, что число "eins" ("один") является наиболее часто встречающейся строкой в открытом тексте (закон Бенфорда). Он автоматизировал процесс создания "каталога Эйнс", который предполагал, что "eins" кодируется во всех позициях открытого текста. Каталог включал все возможные положения различных роторов, начальные позиции и настройки ключей "Энигмы". Польское бюро шифров также использовало "подстилки" в "методе ANX" до Второй мировой войны (использование немцами "AN", немецкого "к", за которым следовал "X" в качестве разделителя для формирования текста "ANX"). Соединенные Штаты и Великобритания использовали системы с одноразовыми лентами, такие как 5 UCO, для своей наиболее конфиденциальной переписки. Эти устройства были невосприимчивы к атакам с использованием известного открытого текста; однако они были каналами связи от точки к точке и требовали огромных запасов одноразовых лент. Сетевые шифровальные машины считались уязвимыми для "подстилок", и для маскировки начала и конца сообщения использовались различные методы, включая разделение сообщений пополам и отправку второй части первой, а также добавление бессмысленного заполнения с обоих концов. Последняя практика привела к печально известному инциденту во время Второй мировой войны, когда бессмысленное заполнение, добавленное к сообщению, отправленному американскому адмиралу Уильяму Хэлси-младшему, "мир гадает", оказалось недостаточно бессмысленным и было интерпретировано как часть фактического сообщения, что привело Хэлси к изменению своих планов. KL 7, представленный в середине 1950-х годов, был первой американской шифровальной машиной, считавшейся безопасной против атак с использованием известного открытого текста. Классические шифры обычно уязвимы для атак с использованием известного открытого текста. Например, шифр Цезаря можно решить, используя одно соответствующее письмо открытого и шифротекста для полного расшифровки. Для общего моноалфавитного шифра подстановки требуется несколько пар символов и некоторое предположение, если имеется менее 26 различных пар.

The usage "crib" was adapted from a slang term referring to cheating (e. g., "I cribbed my answer from your test paper"). A "crib" originally was a literal or interlinear translation of a foreign language text—usually a Latin or Greek text—that students might be assigned to translate from the original language. The idea behind a crib is that cryptologists were looking at incomprehensible ciphertext, but if they had a clue about some word or phrase that might be expected to be in the ciphertext, they would have a "wedge," a test to break into it. If their otherwise random attacks on the cipher managed to sometimes produce those words or (preferably) phrases, they would know they might be on the right track. When those words or phrases appeared, they would feed the settings they had used to reveal them back into the whole encrypted message to good effect. In the case of Enigma, the German High Command was very meticulous about the overall security of the Enigma system and understood the possible problem of cribs. The day to day operators, on the other hand, were less careful. The Bletchley Park team would guess some of the plaintext based upon when the message was sent, and by recognizing routine operational messages. For instance, a daily weather report was transmitted by the Germans at the same time every day. Due to the regimented style of military reports, it would contain the word Wetter (German for "weather") at the same location in every message. (Knowing the local weather conditions helped Bletchley Park guess other parts of the plaintext as well.) Other operators, too, would send standard salutations or introductions. An officer stationed in the Qattara Depression consistently reported that he had nothing to report. "Heil Hitler," occurring at the end of a message, is another well known example. At Bletchley Park in World War II, strenuous efforts were made to use (and even force the Germans to produce) messages with known plaintext. For example, when cribs were lacking, Bletchley Park would sometimes ask the Royal Air Force to "seed" a particular area in the North Sea with mines (a process that came to be known as gardening, by obvious reference). The Enigma messages that were soon sent out would most likely contain the name of the area or the harbour threatened by the mines. The Germans themselves could be very accommodating in this regard. Whenever any of the turned German Double Cross agents sent a message (written by the British) to their respective handlers, they frequently obligingly re encrypted the message word for word on Enigma for onward transmission to Berlin. When a captured German revealed under interrogation that Enigma operators had been instructed to encode numbers by spelling them out, Alan Turing reviewed decrypted messages and determined that the number "eins" ("one") was the most common string in the plaintext (Benford's law). He automated the crib process, creating the Eins Catalogue, which assumed that "eins" was encoded at all positions in the plaintext. The catalogue included every possible position of the various rotors, starting positions, and keysettings of the Enigma. The Polish Cipher Bureau had likewise exploited "cribs" in the "ANX method" before World War II (the Germans' use of "AN", German for "to", followed by "X" as a spacer to form the text "ANX"). The United States and Britain used one time tape systems, such as the 5 UCO, for their most sensitive traffic. These devices were immune to known plaintext attack; however, they were point to point links and required massive supplies of one time tapes. Networked cipher machines were considered vulnerable to cribs, and various techniques were used to disguise the beginning and ends of a message, including cutting messages in half and sending the second part first and adding nonsense padding at both ends. The latter practice resulted in an infamous incident during World War II when the nonsense padding added to a message sent to American admiral William Halsey Jr., "the world wonders", was not nonsensical enough and was interpreted as part of the actual message, leading Halsey to change his plans. The KL 7, introduced in the mid 1950s, was the first U. S. cipher machine that was considered safe against known plaintext attack. Classical ciphers are typically vulnerable to known plaintext attack. For example, a Caesar cipher can be solved using a single letter of corresponding plaintext and ciphertext to decrypt entirely. A general monoalphabetic substitution cipher needs several character pairs and some guessing if there are fewer than 26 distinct pairs.