dxdt.ru: занимательный интернет-журнал

Многие слышали про криптографию на эллиптических кривых. Но эллиптические кривые, которые давно являются мощным инструментом теории чисел, можно успешно применить к решению элементарной (по формулировке) арифметической задачки про бананы, яблоки и ананасы. Текст ниже – несколько сокращённая версия моего перевода ответа Quora.com, который дал Alon Amit (англ.).
Читать полностью

Немного теорий заговора. Сетевого уровня.

Маршрутизаторы – эффективное направление атак на сети, которые являются сегментами глобальной Сети. В подавляющем большинстве случаев, если “погасить” несколько умело выбранных маршрутизаторов, сеть падает полностью, несмотря на попытки резервирования, предпринятые при проектировании и построении сегмента. Хрестоматийная ситуация: резервные маршрутизаторы не справляются с изменившейся конфигурацией сети; причин может быть много разных – от возросшего трафика, до невозможности обмена управляющей информацией в результате возникших в сети “штормов”. Например, предполагается, что довольно давний случай с глобальной аварией сети в Сирии был вызван тем, что специалисты АНБ, во время операции по удалённому внедрению (обновлению?) программных закладок, случайно “уронили” ключевой маршрутизатор.

Интересно, как можно обнаруживать подобные действия?

Предположим, доверять маршрутизатору нет оснований, поэтому сразу считаем, что там есть закладки. Естественно, крайний вариант закладки – это продвинутый kill switch, срабатывающий по какой-нибудь последовательности в проходящих через маршрутизатор данных. Обнаружить его до срабатывания – чрезвычайно сложно, поэтому противодействовать не получится. Можно рассчитывать, что нет универсального “выключателя”, поэтому взамен вышедших из строя, удастся быстро ввести новые маршрутизаторы. (Наличие подобного инструмента, конечно, вообще выглядит довольно фантастично. Тем не менее, совсем не рассматривать его тоже нельзя.)

С универсальным выключателем – мало что можно сделать. Но возможен более мягкий вариант: наличие несанкционированного удалённого доступа к маршрутизатору (через недокументированные возможности). Такой доступ позволяет управлять настройками и, скажем, выстраивать хитрые логические атаки. Каналы, реализующие доступ, могут быть хорошо замаскированы средствами стеганографии. Быстрый поток там не нужен, достаточно передавать несколько десятков коротких команд в минуту. Поэтому набор транспортов – радует свой широтой. Можно передавать биты “полезной нагрузки” в заголовках пакетов (TCP, IP, UDP и т.п. – выбирайте сами). Для этого нужно знать маршруты и располагать узлами, находящимися по разные стороны от контролируемого маршрутизатора: пакеты должны ходить через маршрутизатор, чтобы процессоры могли считывать недокументированные команды и отвечать на них. Естественно, можно ограничиться и отправкой пакетов только снаружи, лишь бы они достигали маршрутизатора, но вариант с трафиком, проходящим “через пару портов”, гораздо более привлекателен с точки зрения реализации недокументированных возможностей: во-первых, так проще реализовать скрытую обработку (из-за архитектуры маршрутизатора); во-вторых, больше способов отправить ответ. С ответами – вообще отдельная задача. Маршрутизатор не может просто так заменять какие-то параметры в заголовках, допустим, произвольных пакетов – велика вероятность ненамеренно испортить значимые данные, тем самым демаскировав всю операцию. Но зато специально выделенные пакеты – можно заменить (или сгенерировать) полностью, даже вместе с содержимым. Выделить пакеты для связи помогут ранее отправленные команды, сам пакет – будет передан узлом, находящимся за одним из портов, но данные в пакете заменяются маршрутизатором (пакет передаётся для того, чтобы не рисковать поднятием флагов во всяких системах учёта трафика, повсеместно внедрённых – они считают именно пакеты и иногда их длину; впрочем, перекос даже в один процент – вряд ли вызовет подозрения).

IP или, например, UDP, оказываются универсальными в силу того, что работают на общем для всех узлов IP-сети логическом уровне. При этом другие протоколы спускаются на несколько уровней ниже. Так, есть инструменты VLAN (виртуальные сети) и другие логические элементы, невидимые для IP. Связанные с ними протоколы также можно было бы использовать для передачи недокументированных сигналов. Однако из-за того, что свойства даже соседствующих сетей на соответствующих уровнях очень сильно разнятся, тут встречаются трудности. С другой стороны, можно представить ситуацию, когда использование расширений стандарта Ethernet (например) позволяет скрывать от анализаторов трафика, работающих параллельно маршрутизаторам, целый пласт ходящих по физической линии связи данных. Элементарный пример, понятный каждому: представим, что для анализа трафика используется обычный компьютер и Wireshark, но продвинутая сетевая карта – игнорирует часть пакетов, например, обнаружив в заголовке Ethernet некоторый заранее зашитый в процессор карты индекс (заметьте, что такое поведение аналогично штатной функции, позволяющей разграничивать VLAN-ы). Понятно, что Wireshark в таком случае не будет видеть часть трафика, и обнаружить, что видны не все пакеты, вряд ли получится. Конечно, пакеты могло бы прятать и ядро ОС, но аппаратная фильтрация сетевой картой – куда как более эффективна: зафиксировать передачу данных теперь можно только при помощи логического анализатора, подключенного непосредственно к проводам. А вот уже представить себе логический анализатор, который прячет сигналы, гораздо сложнее, чем только что описанную конфигурацию с продвинутой сетевой картой. Но многие ли мониторят сети при помощи логических анализаторов? (Вопрос даже не риторический, а скорее похож на шутку.)

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

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

И все те же параметры отдельного спутника – отлично подходят для создания орбитального радара. При этом, для решения SpaceX заявлена высокоскоростная связь между спутниками (судя по всему, речь вообще идёт об оптических каналах) и особое внимание уделяется точности определения положения спутников в пространстве (если там будут оптические каналы, то взаимное расположение можно измерять чрезвычайно точно). Это означает, что спутники смогут эффективно осуществлять согласованную обработку сигналов. Очевидно, что связь между спутниками является критическим параметром и в смысле обеспечения высокоскоростного доступа к Сети. А для гипотетического радара – это мощная платформа, позволяющая реализовать алгоритмы цифровой обработки сигналов и построить все мыслимые конфигурации радиолокационных систем. Если нужна бистатическая радиолокация, то одни спутники могут передавать зондирующий сигнал, другие – принимать его, корректируя результат на основе опорных данных, полученных по внутренней сети группировки. Предположим, что требуется синтезировать апертуру (это метод повышения чувствительности и разрешающей способности РЛС, заменяющий огромную физическую антенну на перемещение приёмника) – для этого тоже имеется отличный фундамент: есть точное общее время, известно положение всех приёмников в пространстве и приёмники-спутники постоянно движутся по довольно стабильным траекториям. Сложно придумать что-то лучше.

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

Киберпанковская история про обезличивание персональных данных. Предположим, есть база данных, в которой содержатся сведения о мгновенном расходе электроэнергии в домохозяйстве, привязанные ко времени, сведения собираются с “умных счётчиков”. К базе данных получают доступ хакеры, их цель – выяснить, по какому адресу находится стиральная машина, удалённый доступ к которой они уже получили ранее, в рамках целевой атаки. Метод, впрочем, довольно очевидный: ночью стиральную машину включают и выключают несколько раз, записывая время включения и выключения. На втором шаге – в базе данных электропотребления ищется соответствующая сигнатура (скачки потребляемого тока), а уже по ней определяется адрес, где установлен счётчик и находится стиральная машина.

Занятно, что новомодные “умные города”, в перспективе, предоставляют огромное количество незащищённых источников информации, позволяющих распутывать клубки из разрозненных данных, удалённо идентифицируя что угодно и как угодно. Основная причина тут в том, что паттерны использования техники довольно сильно различаются, поэтому сигнатура, построенная на нескольких источниках, не поддаётся анонимизации на практике (только в теории, да и то, с серьёзными ограничениями).

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

Предположим, что присутствует третья сторона, которая имеет и спутниковые средства, и различные РЛС, но эта сторона не должна запускать собственных ракет. Однако эта третья сторона может различными способами помочь с наведением чужой ракеты (негласно). Осуществлять командное наведение, подняв прямой радиоканал к ракете – не самый лучший вариант. Во-первых, он требует полного доверия со стороны запускающих ракету – ведь навести её теперь можно не только на предназначенную цель (понятно, что остаются варианты с самоликвидацией и прочими схемами “управления доверием”, но это излишнее усложнение). Во-вторых, даже если радиоканал зашифрован, факт прямой передачи управления ракетой может быть обнаружен и задокументирован, а это совсем не то, что хотелось бы афишировать нашей “третьей стороне”, формально “сохраняющей нейтралитет”.

Есть другое решение: третья сторона может непрерывно выдавать в эфир навигационный радиосигнал, который привязан к текущим координатам цели. Скажем, это может быть даже набор сигналов, которые кодируют координаты цели относительно некоторой заранее оговоренной точки с известным положением в виде разности опорных сигналов, с той или иной модуляцией. То есть, фактически, получается развитие классической системы радионавигации (Loran-C, “Чайка/Тропик” и др.), которая может работать на относительно небольшой частоте, при этом возможны загоризонтные варианты. На борту ракеты находится приёмник, который корректирует работу инерциальной навигационной системы, принимая опорный навигационный сигнал. Понятно, что сигнал будет доступен для приёма всем, но так как речь идёт о подвижной цели, то вычисление координат можно засекретить, заранее передав необходимые коды коррекции стороне, которая проводит пуск ракеты. Впрочем, тут тоже есть подводные камни: передача кодов коррекции, если она будет задокументирована и сопоставлена с записанным из эфира навигационным сигналом, приводит к прямому раскрытию роли “нейтральной” стороны.

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

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

Модуляция, наводимая колебаниями мембраны, считывается тем или иным процессором в качестве “ошибки”. Результат фильтруется, сжимается с использованием некоторого кодека, записывается в память. Вовсе не обязательно использовать для решения этих задач основной процессор смартфона – тем более, что это может вызвать подозрения. Процессоров и микроконтроллеров в современном смартфоне немало, годится модуль GPS или WiFi: очень хорошо подходит всякий сигнальный процессор, потому что обработка интересующих нас данных тут может быть хорошо замаскирована – она производится системным программным обеспечением модуля (“прошивкой”), которое исследовать весьма непросто, и которое невидимо даже для основной операционной системы.

Пусть кодирование речевого сигнала с приемлемым уровнем качества требует (с запасом) 500 байт/сек. Периоды, когда ничего не слышно, не пишутся, поэтому активности в сутки будет где-то часов пять, в самом напряжённом графике. Тогда требуемый объём памяти для хранения данных за сутки составит: 3600*5*500=9*10⁶ байтов, или около 9 Мбайт/сутки. Сохранять такой объём в современном смартфоне труда не составляет: типичные объёмы памяти измеряются гигабайтами. Естественно, хранить запись можно незаметно для пользователя, например, зарезервировав часть памяти. И девять мегабайт – это очень большой объём речи, подавляющее большинство сценариев использования будут выдавать меньше.

Как незаметно передать несколько мегабайт информации? Неплохим вариантом является маскировка данных под случайные – шум. Для этого достаточно шифровать выходной поток, соответственно, он будет практически неотличим от (псевдо)случайных данных. Хорошим носителем для дальнейшей передачи данного “шума” являются цифровые изображения – фотографии, сделанные встроенной камерой. В них, кстати, полезный сигнал и записываться может без ведома операционной системы, непосредственно в схемах камеры. Фотографии загружаются “в облако”. Получаем стеганографический канал. Обнаруживать наличие скрытых данных может только та сторона, у которой есть соответствующий секретный ключ – для всех других “шум” выглядит как шум, обычный для цифровых камер. Проблема лишь в том, что “плотность записи” в подобных стеганографических схемах невелика, не более нескольких процентов от объёма данных, выступающих в роли носителя. Соответственно, чтобы передать 10 мегабайт скрытых данных, потребуется исходящий трафик вплоть до 500 Мбайт. С другой стороны, все 9 мегабайт разом можно было бы передать в виде одной “испорченной” фотографии – данная схема вполне реализуема, так как её тоже можно замаскировать под сбой (главное, чтобы пользователь не удалил фотографию раньше, чем она будет загружена “в облако”).

Естественно, есть и другие способы передачи “дополнительной нагрузки” на сервер: блоки с данными можно прицеплять к загружаемым “в облако” файлам как “мусор” – целый ряд широко используемых форматов позволяют так делать. Не вызывая излишних подозрений можно передавать до 20% от файла носителя, что, соответственно, уже укладывается в типичные объёмы исходящего трафика.

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

Известна концепция “навязанной” радиолокации: для зондирования используются сигналы уже существующих систем, например, телевизионный сигнал или сигнал сети GSM. Интересно следующее развитие темы. Предположим, что у нас есть небольшие (до десяти сантиметров) боты, построенные на передовых достижениях твёрдотельной электроники. Боты замаскированы под “природные объекты”. Например, это могут быть мелкие “камешки”. Они полностью автономны, используют подходящую схему электропитания. Полезная функция: боты принимают сигнал выбранного опорного поля, в том числе, отражения, тщательно измеряют его, оцифровывают и записывают результат. Накопленный результат боты раз в сутки передают в коротком импульсе на пролетающий спутник. Собранные измерения проходят предварительную обработку, потому что нужно извлечь полезную информацию, дабы эффективно использовать короткое окно связи. Все боты поддерживают (при помощи сигнала GPS, например) точное синхронное время, метки времени записываются вместе с собираемыми радиоданными.

А забрасываются данные изделия, например, со стратосферного “метеозонда”, который “случайно” пересёк границу на высоте около 27 тысяч метров. Замаскированные под камешки боты просто сбрасываются над заданным районом (малонаселённым): они не обязательно должны иметь плотность типичного камня, поэтому могут падать без парашюта. Кассета с ботами позволяет засеять несколько квадратных километров с борта одного “метеозонда”.

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

На случай обнаружения бота каким-нибудь грибником (хотя, кто будет каждый камень осматривать, не получив соответствующей ориентировки?) – предусмотрена система ликвидации электронной начинки. Нет, вовсе не обязательно подрывать бота, делая его опасным для грибника. Достаточно при вскрытии корпуса тихо и тщательно сжечь всю микроэлектронную начинку, превратив её в “кусочек смолы”, уничтожив ценные следы. Сам по себе искусственный камень не несёт особой информации: мало ли кто баловался – может, это кусок сбежавшего квадрокоптера. (Электроника с эффективной функцией самоуничтожения – это перспективная тема DARPA, между прочим.)

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

Основную проблему составляет источник питания. Конечно, напрашивается радиоизотопный вариант. Но он тут вряд ли подходит. Во-первых, сложно экранировать, чтобы бот не светил. Во-вторых – радиоизотопы представляют собой прочный след: часто по их составу и свойствам можно однозначно определить производителя. В-третьих – опасно для “грибника”. Питание от самого принимаемого ЭМ-поля, конечно, чисто теоретически возможно, но относится к области научной-фантастики, так как что-то вычислять о питающем поле, да ещё результаты передавать на спутник, уже точно не получится на практике. Возможно, годятся какие-то термоэлектрические решения. И главный инженерный конфликт тут в том, что для сложных вычислений нужна большая энергия (да, это достаточно фундаментальный вопрос физики, но пока никто не выяснил, можно ли вообще вычислять, не расходуя энергию, – хотя, классические основы термодинамики как бы прозрачно намекают, что нет, нельзя; но вопрос, тем не менее, остаётся открытым с квантовой стороны).

Как можно обнаружить такую сеть? Полупроводники можно детектировать дистанционно по наведённому излучению (так работают нелинейные локаторы, или детекторы нелинейных переходов). Но для этого потребовалось бы облучать “район залегания” ботов достаточно мощным ВЧ-излучением, пытаясь как-то вычленить из отражённого сигнала слабые вторичные гармоники, связанные с полупроводниками. Вряд ли это удастся сделать с большого расстояния, например, с борта пролетающего самолёта. Кроме того, полупроводниковую часть бота можно хорошо экранировать: если мы имитируем камень, то место для экранов имеется. Неустранимый элемент только один – приёмная антенна бота (передающая – открывается только в момент отправки данных на спутник). Но приёмную антенну можно моментально отключать, как только бот “услышал” подозрительный мощный зондирующий сигнал (решение известно по продвинутым “жучкам”).

Что за информацию можно было бы собирать при помощи таких ботов? Как минимум, подобная пассивная радиолокация позволит фиксировать самолёты и другие летательные аппараты, на достаточно большом расстоянии от крайнего бота – многие километры. Точность определения траектории будет невелика, но о перемещениях, направлении полёта судить можно. Впрочем, полёты самолётов – и так секрет Полишинеля: они вполне обнаруживаются спутниковыми РЛС. Боты могли бы наблюдать поезда, но тут помешает рельеф местности. Впрочем, при наличии сейсмодатчиков фиксировать движение наземной техники можно (такая схема используется на практике), но это уже не радиолокация. И тем не менее, придумать полезную цель наблюдения, которая недоступна другим методам, более традиционным, для такой сети радиоботов весьма сложно. В случае с воздушными целями – преимущество может быть разве что в ракурсе наблюдения, который позволяет “видеть” объекты снизу и принимать сигналы, направленные к земле.

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

В продолжение предыдущей заметки – посмотрим, как устроены симметричные блочные шифры. Примером послужит шифр “Магма”, в версии ГОСТ Р 34.12-2015, с картинками. Симметричными называют шифры, для которых ключ расшифрования можно легко получить из ключа зашифрования. В современных симметричных шифрах – эти ключи просто совпадают. Блочный шифр, в отличие от потокового, работает с блоками данных фиксированной длины (разрядности), измеряемой в битах. Например, шифр AES работает с блоками разрядности 128 бит. А “Магма” – 64 бита.

Получив на вход блок открытого текста и ключ, преобразование, называемое шифром, выводит блок шифротекста, той же разрядности. Соответствие между блоками открытого текста и блоками шифротекста задаёт значение ключа. “Магма” использует ключ длиной 256 бит. Современные шифры строятся из некоторых элементарных операций над блоками. Наборы таких операций обычно объединяют в раунды. Раунды повторяются несколько раз.

В “Магме” 64-битный блок разделяется на две равные части, над которыми производятся операции раунда. Эти операции включают в себя (в порядке выполнения): сложение с ключом раунда; подстановки; циклический сдвиг; сложение с половиной блока. Заканчивается раунд перестановкой полублоков местами. Раунд показан на схеме ниже:

A₁ и A₀ – две части входного блока: соответственно, они содержат по 32 разряда каждая. На вход цепочки раундовых операций поступает значение полублока A₀. Для каждого раунда используется свой ключ. На схеме ключ обозначен K_i. Раундовый ключ также имеет длину 32 бита (разряда), то есть, совпадает с разрядностью половины блока. Сложение блока со значением ключа (операция обозначена символом ⊞) выполняется по модулю 2³² – это эквивалентно “естественному”, для вычислительной техники, сложению двух 32-битных чисел (без знака). Над результатом сложения выполняются подстановки по таблице подстановок. Таблицы часто называют S-boxes. “Магма” использует 4-битные подстановки, отдельные для каждого полубайта из 32-битного блока. Логика тут следующая: 32-битный блок разбивается на 8 4-битных частей, каждое из получившихся значений (0..15, так как битов – четыре) заменяется на соответствующее ему значение из таблицы подстановок; таблиц восемь – по одной для каждой позиции 4-битного значения внутри 32-битного блока.

В версиях шифра, предшествовавших ГОСТ Р 34.12-2015, таблицы подстановок предлагалось выбирать отдельно для каждой сети обмена сообщениями и держать в секрете. То есть, таблицы позволяли повысить стойкость шифра. При этом, впрочем, неверно выбранные подстановки стойкость могут заметно снизить, а раскрыть секретные подстановки реально, если атакующий может зашифровывать произвольные тексты с известным ключом. В ГОСТ Р 34.12-2015 – значения подстановок зафиксированы.

Значение 32-битного блока после подстановок циклически сдвигается влево на 11 разрядов (то есть, биты сдвигаются влево, а выбывшие разряды вдвигаются справа в том же порядке). После операции сдвига, значение поразрядно суммируется с блоком A₁ по модулю 2, это логическая операция XOR (обозначена символом ⊕ на схеме).

В заключении раунда – A₁ и A₀ меняются местами. То есть, A₀ переходит в следующий раунд без изменений, но становится на место A₁. Всего раундов 32. Последний раунд отличается тем, что 32-битные блоки не меняются местами, а просто объединяются: A₀ присоединяется к A₁ справа. Это замыкает всю конструкцию, позволяя использовать её без изменений для расшифрования: операция расшифрования отличается только обратным порядком раундовых ключей.

Раундовых ключей – 32. Каждый имеет разрядность 32 бита. Эти ключи получаются из основного ключа шифрования при помощи алгоритма развёртывания ключа. В “Магме” этот алгоритм очень простой. Исходный ключ содержит 32 байта (256/8=32). 32 байта – это 8 раундовых ключей, каждый по четыре байта; на 32 раунда – ключи копируются, с той лишь разницей, что последние восемь используются в обратном порядке. Схема:

Работа шифра выражается в “перемешивании” битов открытого текста, схему перемешивания определяет ключ (и таблицы подстановок, но мы считаем, что они неизменны). Преобразования можно визуализировать. На картинке ниже – разным значениям битов соответствуют синий и жёлтый цвета, раунды выполняются сверху вниз (самая верхняя строка – открытый текст).

Посмотрим, насколько важны параметры и базовые преобразования, выбранные для построения шифра. Важным инструментом криптоанализа является изучение работы шифра при малых отличиях открытых текстов. На картинке ниже – распространение изменений между раундами “Магмы”: два открытых текста отличаются значением одного бита, ключ используется одинаковый; синим цветом отображены разряды, значения которых совпали между собой; зелёным – отличающиеся разряды.

Хорошо видно, что уже на седьмом раунде различия между значениями блоков сравнимы (визуально) с типичным расстоянием между двумя случайными 64-битными значениями. При этом решающий вклад в “разделение” блоков вносят подстановки (собственно, в этом их основное назначение). Попробуем выключить подстановки (кроме последнего раунда; без подстановок, естественно, данный шифр использовать нельзя).

Результат – плачевный. Несмотря на то, что это лишь схема для двух открытых текстов, понятно, что ни о каком “лавинном эффекте” от замены одного бита говорить уже не приходится. Сходного результата можно добиться и использованием “плохих” таблиц подстановок (но нестойкие таблицы, в общем случае, не обязательно приводят к такому эффекту).

Попробуем изменить другой параметр – число разрядов, на которые циклически сдвигается блок в каждом раунде. Используем сдвиг на 12 разрядов, вместо 11 (подстановки и другие преобразования – без изменений).

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

Российский шифр “Магма” известен также под названием ГОСТ 28147-89. В новом ГОСТ Р 34.12-2015 данный шифр приведён вместе с более современным шифром “Кузнечик”. “Магма” весьма старый блочный шифр, ещё советский, он родом из 70-х годов прошлого века. Некоторым образом шифр связан с электромеханическими шифровальными машинами. Например, таблицы подстановок ведут своё происхождение от “перемешивающих” дисков этих машин. Несмотря на солидный возраст, шифр до сих пор выглядит неплохо по соотношению таких характеристик, как практическая стойкость и требуемое количество операций. Шифр достаточно простой и может быть реализован на базе микроконтроллера. В качестве базового устройства используем распространённую платформу – Arduino (конкретно – Arduino Uno, на котором я проверял исходный код).

“Магма” имеет разрядность блока 64 бита и разрядность ключа 256 бит. По современным меркам 64 бита – малая разрядность блока, но она сохраняет актуальность для встроенных применений (“Интернета вещей”), где короткие криптограммы очень распространены и обусловлены техническими ограничениями. 256 бит ключа и на современном уровне являются излишне большим значением, при условии, конечно, что шифр обеспечивает стойкость, эквивалентную полному перебору. Я не буду приводить обзор литературы по криптоанализу данного “ГОСТового” шифра в этой заметке. Отмечу только, что до сих пор для шифра не предложено универсального метода криптоанализа, который снизил бы криптостойкость, с точки зрения практической атаки, до неприемлемого уровня. Все известные эффективные атаки – академические, требуют чрезвычайно больших ресурсов, при этом лучший результат: снижение стойкости до 101 бита. Примем, что в наихудшем практическом случае данный шифр обеспечивает стойкость около 115 бит, а этого вполне достаточно для, например, передачи данных от датчиков температуры “при ведении подсобного хозяйства”. Другими современными “малыми” шифрами, которые ориентированы на использование в маломощных микроконтроллерах, являются, например, шифры Speck и Simon, предложенные АНБ.

Технически, “Магма” представляет собой итеративную конструкцию Фейстеля, состоящую из 32 раундов. Входной блок разделяется на две равные части, в каждом раунде к одной из частей последовательно применяются раундовые преобразования, а результат суммируется со второй частью. Перед следующим раундом – части меняются местами (кроме последнего раунда). Преобразования включают в себя сложение (по модулую 2³²) с ключом раунда, подстановку по таблице подстановок, циклический сдвиг влево. При расшифровании работа шифра отличается только порядком ключей. Раундовые ключи имеют разрядность половины блока – 32 бита. Набор ключей раундов получается из основного ключа копированием его 32-битных подмножеств по достаточно простой схеме: первые 24 раунда используют “подключи” последовательно в прямом порядке (то есть, k₁..k₈), а заключительные 8 раундов – в обратном порядке (k₈..k₁). (Более подробное описание работы шифра – в отдельной записке.)

Сам шифр я реализовал на ассемблере AVR, воспользовавшись inline-вариантом – то есть, команды ассемблера включены в исходный код на языке C (исходный код прилагается, см. ниже, функция DoCipher()). Шифр работает быстро, реализацию можно ещё улучшить. Микроконтроллер Arduino Uno очень ограничен в объёме оперативной памяти для данных, при этом “Магма” только для хранения основного ключа требует 256/8 = 32 байта. Набор раундовых ключей, если его полностью развернуть в памяти, съедает ещё 4*32 = 128 байтов. Таблица подстановок (я, кстати, использовал таблицу из ГОСТ Р 34.12-2015) включает восемь наборов по 16 значений, однако так как подстановки полубайтовые (по четыре бита), их можно объединить попарно: получаем 4*16 = 64 байта. Итого – 224 байта только на окружение, которое требуется для использования шифра. Оптимизации тут можно подвергнуть только раундовые ключи – в принципе, можно их не разворачивать, а прямо использовать байты из основного ключа (так работала бы аппаратная реализация).

Реализация непосредственно шифра называется криптопримитивом. Наличие криптопримитива позволяет строить на базе шифра полезные конструкции. При этом, использовать блочный шифр прямо для зашифрования блоков открытого текста – в подавляющем большинстве случаев нельзя: такой режим называется режимом простой замены (или ECB) и не обладает нужным уровнем секретности, даже если вы с помощью зашифрованных команд лампочки в доме переключаете. Например, одна и та же команда, при использовании одного ключа, будет соответствовать одинаковому шифротексту. Запись с повторной передачей позволит третьей стороне переключать ваши лампочки. Для предотвращения подобных атак существует ряд методов: например, использование уникальных значений (счётчиков) для команд, различные схемы с подтверждением (но тут требуется отправка дополнительных пакетов). Наличие шифра и секретных ключей позволяет все их реализовать безопасно. Также на базе шифра реализуются схемы вычисления/проверки кодов аутентификации сообщений, которые защищают от подделки данные, передаваемые в открытом виде.

В исходном коде в качестве примера дана реализация функций шифрования в режиме счётчика – MagmaEncrypt(), MagmaDecrypt(). Такой режим пригоден для практического использования, однако он не обеспечивает аутентификации сообщений. Предполагается, что обменивающиеся данными устройства знают общий секретный симметричный ключ и используют синхронное значение nonce (оно может передаваться в открытом виде). Соответственно, код содержит пример вызова данных функций.

Некоторые сценарии использования шифров в разных “домашних устройствах”, работающих на базе микроконтроллеров: передача команд, с аутентификацией (сами команды не шифруются); передача данных от датчиков, в зашифрованном виде, также с аутентификацией; подключение новых устройств к сети датчиков (так сказать, опознавание “свой-чужой”).

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

Update 12/12/16: сделал библиотеку с шифром ГОСТ Р Р 34.12-2015 “Магма” для Arduino.