Mar. 16th, 2017

ogn_slon: (Default)

Вскрыл дешифровальное упражнение, опубликованное в декабре прошлого года с последующей подсказкой. Было сдано три ответа (все правильные), в том числе один до подсказки.

Правильный ответ — ЙЙЙЙЙ...ЙЙЙЙЙ, то есть искомое сообщение представляет из себя многократный повтор буквы «й». Как можно было это выяснить?

Ключевой уязвимостью «имперского кода», создающей возможность для успешной криптоаналитической атаки, является его «антирефлексивность», то есть гарантия, что при шифровании буква никогда не отображается в себя. Казалось бы, это свойство не должно значительно ослаблять алгоритм шифрования — в конце концов, имперский алфавит состоит из 32 букв, и при шифровании любой букве разрешено отобразиться в любую из 31 других букв. Если бы код не был антирефлексивен, имелось бы 32 возможности, а не 31 — так ли это важно? Выясняется, что очень важно, особенно с учетом того, что люди, в том числе и шифровальщики, иногда ведут себя легкомысленно. Упражнение демонстрирует, как можно продвинуться в раскрытии секретного кода, отталкиваясь лишь от одного его простого свойства и воспользовавшись небольшой человеческой неосторожностью.

Итак, представим себя на месте криптоаналитика, изучающего описанный в задании код. Аналитик понимает, что имеет дело со сложным полиалфавитным шифром, в общем и целом, обладающим высокой устойчивостью к атакам. Но аналитику все равно требуется раскрыть шифр, и он пытается придумать, что могло бы помочь решить задачу. В числе прочего, аналитик замечает (или предполагает), что имперские корабли периодически посылают бессмысленные зашифрованные сообщения, чтобы убедиться в работоспособности своих каналов связи, а также чтобы загрузить дешифровщиков противника никчемной работой. Но что такое «бессмысленное сообщение»? При правильной шифровальной процедуре — это просто случайная последовательность букв, каждый раз новая. Расшифровка такой абракадабры не представляется возможной. Но аналитик понимает и надеется, что люди есть люди, и иногда они ленятся и упрощают себе задачу.

Вообразим легкомысленного шифровальщика, который печатает рутинное тестовое сообщение. Предположим, что он курит сигарету или пьет чай, так что одна рука у него занята. Он откинулся на спинку стула, свободная рука лежит у клавиатуры. Предположим, что он задумался о чем-то или просто устал и хочет скорее покончить с отправкой бессмыслицы, не содержащей полезной информации. Какое конкретное бессмысленное сообщение мог бы отпечатать такой расслабившийся оператор шифровальной машины одним пальцем одной руки? Быть может, он просто стал бы много раз нажимать на одну и ту же клавишу, например, на крайнюю в одном из рядов? Если так, то каким могло бы оказаться соответствующее зашифрованное сообщение?

С учетом антирефлексивности кода, ответ на последний вопрос в какой-то степени известен. Точнее, известно одно его характерное свойство: если исходное сообщение представляет из себя многократный повтор единственной буквы, то в зашифрованном образе именно эта буква совершенно точно не появится ни разу! Обратное не обязательно, но возможно. То есть, если в зашифрованном сообщении нет одной буквы, то исходное сообщение не обязательно является многократным повтором этой буквы, — но может оказаться таким повтором.

Таким образом, вырисовывается идея криптоаналитической атаки на сеть с антирефлексивным кодом. Нужно дождаться перехвата шифровки, не содержащей одной буквы. Если повезет, то исходное сообщение окажется «ленивым тестом», то есть многократным повтором единственной буквы — ровно той, которая отсутствует в шифрованном перехвате. И тогда в руках у дешифровщиков окажется ценная информация о коде: они узнают образ данной буквы во всех позициях сообщения (в пределах длины однобуквенной шифровки). Конечно, никто не гарантирует, что шифровальщик хотя бы один раз поведет себя столь неосмотрительно, — но если это произойдет, глупо было бы отказываться от его щедрого подарка!

В предложенном упражнении все так и произошло: «шифровка», составленная скромным автором этих строк, содержала все буквы алфавита, кроме Й. Этот факт был замечен и правильно истолкован тремя участниками игры. Возможно, они также учли, что Й является одной из шести крайних букв имперской клавиатуры — самой левой в верхнем ряду, — так что для набора тестового сообщения легкомысленный шифровальщик вполне мог многократно отпечатать именно Й.

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

Возможно, приведенная схема выглядит упрощенно и искусcтвенно. Однако, я воспроизвел реальную криптоаналитическую задачу времен Второй мировой войны, решенную указанным способом. Речь идет о дешифровке секретного трафика, генерировавшегося в 1941 г. одной из сетей связи стран «оси», оснащенной знаменитыми немецкими шифровальными машинами «энигма». Эта был эпизод работы британской дешифровальной службы, во время войны размещавшейся в Блетчли-Парке, к северо-западу от Лондона. Когда в 1970-е правительство Ее величества частично рассекретило сведения о дешифровальных операциях Блетчли-Парка, выяснилось, что британские криптоаналитики довольно успешно читали немецкий и итальянский секретный трафик. Рассекречивание семидесятых позволило бывшим сотрудникам, которые до тех пор обязаны были хранить молчание, опубликовать собственные воспоминания, так что в дополнение к официальным отчетам и документам появились и личные истории.

Предложенная задача составлена по мотивам эпизода из воспоминаний Мэвис Бэйти (Левер), сотрудницы Блетчли-Парка с 1940 г. Про эту реальную историю я надеюсь как-нибудь написать отдельный пост. А пока что спасибо трем ЖЖ-криптоаналитикам, успешно решившим задачку, и всем, кто нашел время поразмышлять над ней.



















Profile

ogn_slon: (Default)
Konstantin Krayn

October 2017

S M T W T F S
1234567
891011121314
15161718 192021
22232425262728
293031    

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Oct. 22nd, 2017 03:29 pm
Powered by Dreamwidth Studios