Об очень шпионском методе аутентификации

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

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

Но как тогда им опознать своего товарища по штабу?

TL;DR — изобретаем механизм аутентификации пользователей с помощью стеганографии для воображаемого трехсимвольного агентства несуществующей страны.

О волках и овечьих шкурах

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

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

Что делать?

Конечно, такая задача не нова, она счастливо существовала и решалась задолго до появления этих ваших интернетов. И мало того, что решалась, так некоторые решения укрепились в культуре и до сих пор встречаются в книгах, фильмах и играх.

Посмотрим хотя бы на такую сцену: два человека в длинных пальто сходятся в публичном месте и обмениваются очень странными фразами. Если инициирующая фраза и ответ верны, то аутентификация прошла успешно, а люди обмениваются папками с пометкой "Top Secret" и расходятся в неизвестных направлениях.

Сразу очевиден недостаток такой схемы — фразы надо хранить в секрете и часто менять, что не очень-то и просто на вражеской территории. При этом для того, чтобы не быть произнесенными случайно и не привести к случаю с КДПВ, они делаются довольно выделяющимися и случайными, а значит, могут выдать агентов, их произносящих.

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

Стеганография (опять?)

Ежу понятно, что возможность скрыть одно в другом в такой ситуации выглядит как никогда привлекательно. И в самом деле, даже описанный метод является ее подвидом — кодовые фразы можно рассматривать как контейнеры со всего одним битом информации внутри.

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

А о чем тогда?

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

Вооружившись лишь такими идеями, мы уже можем составить простой протокол стеганографической аутентификации на основе общего ключа:

• А -> Б: миловидное сообщение с запросом стеганографического контейнера определенных параметров;
• Б: выбирает контейнер C, соответствующий запрошенному контексту и параметрам;
• Б: аналогичным образом создает сообщение M;
• Б -> А: C' = Embed(C, M, K);
• А: Проверяет C' на соответствие поставленным параметрам;
• А -> Б: M' = Extract(C', K);
• Б: Проверяет, совпадают ли M и M'.

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

Исполнитель не черепашка

Если читатель учился в школе после появления компьютерных классов, то он должен помнить обучение основам алгоритмизации с помощью исполнителя черепашки, муравья и подобных. Их идея заключалась в демонстрации возможностей оптимизации большого числа ручных одиночных действий с помощью создания простых программ. Для решения нашей же задачи нужно пойти в обратную сторону.

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

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

Для встраивания же данных нам нужна последовательность формы: (f1, S1, i, D1), (f2, S2, j, D2)..., где:

• Di — некоторая часть встраиваемых данных;
• i, j — индексы элементов контейнера;
• fi: (State, Element, D) -> (State, Element) — функция встраивания;
• Si — некоторое состояние, контекст операции, (El', S[i+1]) = fi(Si, El, Di).

Для извлечения не нужно хранить части данных (К.О.), поэтому достаточно троек: (g1, S1, I1), (g2, S2, I2)... с аналогичными значениями, только gi: (State, Element) -> (State, D).

Все это можно изобразить симметричной диаграммой ниже. Если по каким-то причинам понятности достичь мне не удалось, то не страшно, просто читай дальше.

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

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

Если для алгоритма не требуется состояние, то все вышесказанное остается в силе, просто без одной буквы и блока на диаграмме. Без него даже проще, на самом деле.

И зачем оно нам?

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

Добавляем асимметричность

Даже исполнитель черепашка может нарисовать квадрат сотнями разных способов, просто меняя порядок операций и добавляя новые. А значит, никто не мешает и нам сделать то же самое с описанными последовательностями для фиксированных входных данных.

То есть, мы можем взять последовательность встраивания, добавить новые операции, перемешать это все, да так, что результат останется тем же. Разве что, при наличии состояния, нужно будет его отслеживать и добавлять отдельно необходимые изменения в последовательность. Именно поэтому без него проще, да.

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

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

При чем тут асимметричность? Дело в том, что теперь каждой извлекающей последовательности сопоставляется бесконечное число встраивающих. А восстановление одной по другой — в общем случае задача неразрешимая.

Эксплуатируем

Забываем про любую около-математику и возвращаемся к исходной задаче — как же нам заслать Алису с Бобом на вражескую территорию, чтобы:

• в лицо друг друга не знали
• никаких секретных алгоритмов на руках не имели
• но могли удостовериться друг в друге при связи по открытому каналу?

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

Выработка аутентификационной информации до начала миссии со штабом в роли доверенной стороны Трента:

• Т: выбирает секретный алгоритм и секретный ключ K, создает с их помощью:
  
  • извлекающую последовательность Ex;
  • подходящий для проведения аутентификации (ниже) контекст Ctx;
• Т -> А: Ctx, Ex;
• Т: используя Ex и созданный контекст, генерирует:
  
  • не использованное ранее для выбранных агентов сообщение M из числа частей |Ex|;
  • одноразовую последовательность Em, делая ее открытой описанным выше методом;
• Т -> Б: Em, h(M), при желании создает дополнительные наборы.

Таким образом, у Алисы оказывается лишь одна последовательность на все случаи жизни и контекст будущего контакта, а Боб становится счастливым обладателем набора одноразовых последовательностей и хэшей сообщений, ими встраиваемых.

Протокол аутентификации уже во время миссии выглядит так:

• А -> Б: инициирующее сообщение IM на основе контекста Ctx с описанием контейнера;
• Б: выбирает подходящий C ~ IM;
• Б -> А: C' = Em( C );
• А: проверяет на соответствие C' ~ IM (так как изменения незаметны, должно сохраниться);
• А -> Б: M' = Ex( C' ), помечает M' как использованное;
• Б: проверяет, h(M') == h(M), уничтожает Em, h(M).

Внимательный читатель заметит, что до проведения протокола что Алиса, что Боб обладают просто набором информации, которая сама по себе ничего не значит ни для них, ни для потенциального противника, и лишь во время проведения "играет красками".

Каждый открытый набор Боба используется только раз, что контролируется предпоследним шагом Алисы. При встрече ранее использованного M (а значит, и невидимой ею Em) другим лицом она понимает, что один из ее "соратников" — фальшивка.

Повторное использование одним и тем же лицом говорит ей, что оно не в курсе тонкостей проведения протокола и уж точно не является тем, с кем ей нужно было вступить в контакт. Что ж, лучше поздно, чем никогда.

Окей, вот так вот это все выглядит слишком сложным и непонятным. Кто-нибудь до сюда добрался?

Давайте лучше продемонстрирую на практике, потому что даже самим шпионам детали протокола знать для использования не надо, что уж про бедных читателей говорить. Только сначала немного о том, как оно все было реализовано.

Высокие технологии

Итак, осталось лишь написать все необходимое для проведения протокола. Ну не руками ведь все делать (хотя и так можно). И сегодня жертвой моего кода станет… крутит колесо фортуны… Джава? Ну и ладно, заодно все в STL'е будет, ничего искать не придется.

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

class MyContainer implements StegoContainer<MyElement> {
    public MyElement get(int i) {
        // получить i-й элемент
    }
    public void set(int i, MyElement v) {
        // задать i-й элемент
    }
    public int size() {
        // получить количество элементов
    }
}

Дальнейшее использование сводится к созданию обертки стеганографического автомата над нужным контейнером и подачи на его вход функций встраивания и извлечения:

StegoMachine<MyState, MyElement> myMachine = new StegoMachine(
    initialState, new MyContainer<MyElement>(/* загружаем контейнер */)
);
final StegoEmbed myEmbed = (st, el, dp) -> {
    // встраивание части данных dp в элемент el при состоянии st
};
final StegoExtract myExtract = (st, el) -> {
   // извлечение части данных из el при состоянии st
    return dp;
};

// Встраиваем части сообщения
MyDataPart part = /* Создаем элемент данных */;
myMachine.exec(1337, myEmbed, part);
//...

// Получаем состояние для изменения/сброса, если хотим
// сохранить изменения перед другими операциями
State currState = myMachine.getState();
//...

// Извлекаем части сообщения
part = myMachine.exec(80085, myExtract);
//...

// Получаем контейнер для перезаписи или еще чего
MyContainer container = (MyContainer) myMachine.getContainer();

Аналогичным образом используются классы с суффиксом Stateless, в случае, если для реализации алгоритма не требуется поддерживать внутреннее состояние.

Генераторы последовательностей могут работать как угодно и не обладают общим API. Частью данных может являться в общем случае вообще что угодно, от одиноких битов до наскальной живописи в отдельной кодировке.

Пример реализации

О методе

В качестве примера реализации, с использованием созданных интерфейсов я реализовал простой алгоритм из семейства LSB для растровых изображений со сжатием без потерь. Их элементами являются пиксели, не имеющие соседов по младшему биту всех компонент RGB. Функция встраивания работает с одинокими битами исходных данных и просто изменяет младший бит значения одной из компоненты (на какую укажет индекс).

Довольно просто, но отлично подходит для реализации протокола, так как изменение любого элемента одинаково незаметно по их выбору, так что индексы изменяемых элементов генерировать с помощью случайного генератора. В случае джавы, с помощью SecureRandom, но при желании он легко меняется на свой источник энтропии.

Тем не менее, это очень простой метод, не советую его использовать настоящим шпионам.

О хэшах

Так как текст имеет свойство искажаться в зависимости от симулируемой личности агента (некоторые не ставят заглавные, другие любят ставить смайлики и пр, третьи вообще неграмотны), то для расчета хэша я предлагаю использовать sha256, но только от печатных слов, переведенных в нижний регистр:

h("Hello world?...") == h("hello, world!11")

Об интерфейсе

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

Работа с обеими происходит из командной строки посредством ее аргументов и потоков ввода-вывода, других интерфейсов не завезли (страх и ужас). Все-таки быть что работником штаба, что шпионом — означает иметь какую-никакую квалификацию. Ну а если нет — все равно покажу на примере.

Что им всем делать-то?

Для начала, Тренту в штабе надо выработать аутентификационную информацию. В частности, продумать заранее ситуацию, в которой агенты будут работать.

Например, пусть Боб будет фрилансером, занимающимся графикой, а Алиса — его заказчиком. Аутентификация же будет происходить под видом заказа создания графики / дизайна / чего-нибудь еще.

Сообщаем эту полезную информацию обоим и возвращаемся к самому протоколу. Подготовим заранее подходящее встраиваемое сообщение M.txt, минимизируя число знаков в нем: "отлично мне подходит куда перечислять деньги". Генерируем Em и Ex с помощью утилиты для Трента:

Trent@HQWorkstation:~$ java -jar HQUtil.jar -ex $(stat -c%s "M.txt") 4096  > Ex.txt
Trent@HQWorkstation:~$ cat Ex.txt | java -jar HQUtil.jar -em "$(cat M.txt)" 0.25 4096 > Em.txt
Trent@HQWorkstation:~$ cat M.txt | java -jar HQUtil.jar -h > hash.bin

Тут $(stat -c%s "M.txt") возвращает размер сообщения в байтах, а 4096 — ограничение для диапазона генерируемых индексов (чтобы позволить использовать контейнеры поменьше). Аналогично, $(cat M.txt) используется для передачи самого сообщения в параметр командной строки. В принципе, можно обойтись и без баша, используя свой ручной труд, но кому как удобнее.

Ex.txt передается Алисе, Em.txt и hash.bin — Бобу. Теперь представим, что агенты успешно внедрились и хотят связаться друг с другом — переходим к выполнению протокола. Боб размещает свое резюме или предложение работы на какой-нибудь бирже, а Алиса начинает общение:

Алиса: Привет, я нашла тебя на %фриланс_бирже%
Алиса: Мне нужно качественное изображение красного зонта на боку, с металлической ручкой. Сможешь сделать?
Боб: Хорошо, как дойдут руки

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

Bob@PC:~$ cat Em.txt | java -jar SpyUtil.jar -e umbrella.png

Подождав некоторое время, симулируя работу, если в реальности ее не делал, он отправляет Алисе полученный контейнер, естественно, придерживаясь контекста:

Боб: Сделал, вот превью, полную версию отправлю после оплаты

Та, в свою очередь, извлекает хранимое внутри сообщение:

Alice@PC:~$ cat Ex.txt | java -jar SpyUtil.jar -e umbrella.png
отлично мне подходит куда перечислять деньги

Превращает набор слов в нормальное предложение и отправляет его Бобу:

Алиса: Отлично, мне подходит, куда перечислять деньги?

Тот проверяет верность сообщения:

Bob@PC:~$ java -jar SpyUtil.jar -c hash.bin "Отлично, мне подходит, куда перечислять деньги?"
Отлично, мне подходит, куда перечислять деньги? - Correct

И продолжает непринужденное общение, если все окей. Весь диалог со стороны наблюдателя выглядит как-то так:

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

-> GitHub