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

В продолжение предыдущей заметки – посмотрим, как устроены симметричные блочные шифры. Примером послужит шифр “Магма”, в версии ГОСТ Р 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.

Больше и больше пишут про “квантовые каналы” связи, которые “абсолютно” защищены “квантовой криптографией”, и только они смогут спасти от “квантового компьютера”. Здесь интересны несколько моментов.

1.

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

2.

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

3.

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

4.

Квантовые компьютеры. Симметричные системы (шифры), вроде AES, сохраняют стойкость: сейчас считается, что появление квантовых компьютеров достаточной мощности приведёт лишь максимум к “квадратичной” оптимизации перебора. Это очень оптимистичная, в отношении квантового компьютера, оценка, потому что речь идёт о квантовых операциях, реализующих алгоритм поиска – а это совсем другое дело, по сравнению с классическим CPU. То есть, для сохранения стойкости, разрядность ключа симметричного шифра нужно будет увеличить в два раза. Соответственно, AES с 256-битным ключом обеспечит достаточную степень защиты (эквивалентную 128 битам). Если стороны успели в защищённом режиме обменяться гигабайтом ключевого потока, то его, даже при расточительном использовании в качестве ключей AES, хватит надолго. (256 бит – это 32 байта, которые можно смело использовать для шифрования AES примерно 2^32 блоков, каждый блок – это 16 байтов, то есть, одного ключа хватит для 16 * 2^32 ≈ 64 гигабайт передаваемых данных; и это только один ключ, 64 байта из гигабайта).

5.

Квантовые компьютеры достаточной разрядности – полностью побеждают распространённые сейчас асимметричные криптосистемы. Если только такие компьютеры возможны. Как ни странно, первыми падут суперсовременные криптосистемы на эллиптических кривых: это связано с тем, что они имеют малую разрядность, а способность квантового компьютера взламывать такие системы находится в прямой зависимости от числа доступных кубитов. То есть, компьютера, взламывающего ECDSA с ключами в 256 бит, ещё недостаточно для того, чтобы атаковать RSA с разрядностью в 2048 бит. Так что тут у RSA есть преимущество. Другое дело, что как только сумеют построить квантовый компьютер с разрядностью в 256 кубитов, масштабирование на 2048 – вряд ли потребует долгих лет.

6.

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

Про “квантовую проблему” давно известно. Поэтому сейчас очень активно разрабатывают классические криптосистемы, обладающие “квантовой стойкостью”. Это постквантовая криптография. Так как основную угрозу составляет возможное раскрытие симметричных ключей, защищающих трафик, прежде всего будут внедряться постквантовые протоколы обмена ключами (выработки общего секрета). Это, например, варианты протокола Диффи-Хеллмана, работающие на другом математическом аппарате. В экспериментальной версии браузера Google Chrome в реализацию TLS уже добавлен постквантовый протокол генерации общего секрета. Так что не стоит доверять громким заявлениям, будто “появление квантового компьютера уничтожает классическую криптографию” – квантового компьютера пока что нет и на горизонте, а постквантовые криптосистемы уже добрались до реализации в экспериментальном браузере (но до массового внедрения, конечно, там тоже далеко).

7.

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

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

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

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

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

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

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

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

Конечно, сходные схемы давно реализованы в разном виде: например, передали зловреда через WiFi. Но прорывным вариантом было бы как раз прямое навязывание в память. Когда целевая компьютерная система штатно не использует каких-то контролируемых атакующим способов связи, а код, достаточного объёма, тем не менее, “наводится” в компьютерной памяти и исполняется. Каким образом? Фундаментальных запретов, как ни странно, нет: например, можно направлять заряженные частицы в ячейки памяти, они станут перещёлкивать значения битов. Отправили нужный поток – получили нужный код. Используя достаточно сложный источник частиц (что-то вроде ускорителя), нужный поток можно сгенерировать. Информацию о расположении модулей памяти компьютера, – а тут потребуется очень точная трёхмерная реконструкция, – берём из технической документации (предполагается, что компьютер типовой). Тут есть огромное количество технических проблем, конечно. Но и способ, наверняка, не единственный.

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

Появился новый робот, быстро собирающий кубик Рубика – он справляется примерно за секунду (по ссылке с картинки – видео на Youtube.com):

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

Если я не путаю, то сейчас известно, что из любой конфигурации кубик (3×3) собирается не более, чем за 26 ходов, если ходом называется поворот грани на 90 градусов. При этом большинство конфигураций лежат на два-три хода ближе к собранному кубику. Для оценки точное число ходов не так важно. Примем, что типичная сложная конфигурация – 25 ходов. То есть, если поворачивать грань за 10 миллисекунд на 90 градусов, то с преобразованиями конфигурации можно уложиться в 250 мс (плюс затраты на “переключение” граней – но не будем их учитывать). 10 мс – это 9000 градусов или 25 оборотов в секунду. Сама по себе, скорость вращения не очень большая, добротный кубик её наверняка выдержит. Заметные потери времени при “миллисекундном разрешении” будут связаны с разгоном грани – отсюда и идеи с механическим зацеплением. Для немодифицированного кубика быстрый разгон при начале вращения грани составит серьёзную техническую проблему.

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

В общем, тема эта весьма интересная, а особенное техническое развитие она получает после преодоления секундного барьера. (Человеческий рекорд, кстати, чуть менее 5 секунд.)

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

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

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

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

Дело в том, что пока упомянутый специалист утверждает, что почта нынче ходит между продвинутыми серверами в зашифрованном виде, через TLS и прочие заклинания, настоящие техномаги (80 lvl) “кастуют” подмену DNS и заменяют интересующие их почтовые серверы на свои прокси. Эти прокси отменяют TLS (почтовые протоколы позволяют) и – хлоп! – опять читают “секретную” переписку пользователя, что грозит последнему проблемами, хоть он этого и не понимает.

Вывод и мораль: не используйте математических методов, если вы не понимаете их сути (из известного анекдота про математиков и физиков). Да. Лучше уж подсуньте записку под дверь.

Кстати, про фотографии. Нередко приходится видеть, как на фотографиях сетевого оборудования замазывают имена серверов и названия портов/линий. В принципе, это полезная практика: потому что также приходилось наблюдать и скандалы, когда на фотографиях из некоторого дата-центра, опубликованных в СМИ, специалисты узнали оборудование, которого в этом дата-центре (как бы) не должно было находиться. Так вот, на сайте ЦРУ есть статья, повествующая об одном рабочем эпизоде аналитика стратегической разведки, занимавшегося, в конце 50-х годов прошлого века, реконструкцией параметров советской электрической энергосистемы на Урале (некоторый перевод удалось найти готовый, но лучше, конечно, читать оригинал; зато страница с переводом очень дополняет оригинал важными картинками в высоком разрешении).

Если в двух словах, то история вертится вокруг фотографии, опубликованной в журнале “Огонёк” 1958 года. На этой фотографии запечатлена центральная диспетчерская “Уралэнерго”, находившаяся в Свердловске. Используя схему системы энергоснабжения, которая составляет основное содержание фотографии, аналитику ЦРУ Чарльзу В. Ривзу удалось составить план энергосистемы, на основе которого, используя теорию электросетей, он смог вычислить потребляемую мощность советских секретных атомных объектов, находившихся на Урале, а также подтвердить, что некоторые объекты – являются атомными. Ради этого, собственно, всё и затевалось. Фотография в “Огоньке”, конечно, была отретуширована перед печатью: на ней, как пишут, закрасили все названия и шкалы (или “индикаторы”) приборов. Зацепкой послужил состав схемы: обозначения, соответствовавшие генераторам, позволили сопоставить их с электростанциями – так как информация о числе генераторов на некоторых из них была известна из других источников. Новые станции, а также станции, о которых было мало информации (неизвестно число генераторов), оказалось возможным сопоставить со схемой методом исключения, анализируя взаимные подключения, на фотографии и на разведывательных аэрофотоснимках.

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

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

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

Вот.

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