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

У меня есть аккаунт в Facebook, где я размещаю разные заметки. Большинство из тех заметок совсем не подходят для публикации здесь, на сайте dxdt.ru, однако некоторые – хочется как-то сохранить, тем более, что перспективы сервиса Facebook несколько туманны. Поэтому я решил попробовать подходящие заметки иногда копировать сюда, даже если они достаточно старые (Facebook отдельно показывает прошлые заметки, которые опубликованы на актуальную дату, так что можно выбирать).

Например, вот заметка от 28.09.2018, про алгоритм Шора.

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

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

“В магазин привезли два ящика с апельсинами. В каждом ящике – пять апельсинов. Сколько всего апельсинов привезли в магазин?”. Эта задача для начальной школы, а точнее – обсуждение её требуемого способа решения, как выясняется, несёт с собой много занимательных трактовок. Задача существует в различных вариантах (“диваны/подушки”, “полки/книги” и пр.), а её решение с постоянством обсуждается “в интернетах” уже несколько лет. Обсуждение вращается вокруг следующего момента: вариант решения “5*2 == 10” – учитель признаёт неверным; требуется решать так: “2*5 == 10 (апельсинов)”, поскольку в первом варианте “получаются ящики, а не апельсины“. Возможна и иная трактовка, в которой левое умножение заменяется правым, но для нас это не важно, поскольку причина бурных обсуждений состоит в том, что результат вообще зависит от порядка множителей. Почему-то считается, что это невозможно, поскольку умножение в натуральных числах коммутативно. Вообще, если отвлечься от неясных вопросов преподавания в начальной школе, то задача, взятая вместе с методикой решения, оказывается связанной с интересными аспектами математики и их проекцией в привычный опыт.

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

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

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

Распространённое конструктивное возражение такое: у нас же даны не апельсины, а “апельсины на ящик”. Да, это весьма разумный довод, опирающийся на введение некоторого понятия “размерности”. Действительно, умножаем число с размерностью “апельсины/ящик” на число с размерностью “ящик”, “ящики” сокращаются – получаем искомые апельсины, вне зависимости от порядка множителей (операндов). Это очень привычно (м/сек., кг/м² и др.), поэтому мало кто замечает, что введение такой “размерности” подразумевает построение некоторой дополнительной теории. Почему при умножении “апельсины/ящик”*”ящик” – сокращаются именно “ящики”? Что такое “сокращаются”? А можно ли записать наоборот “ящик/апельсины”? Заметьте, что привычное деление, которое приходит тут на ум, мало того, что легко выводит за пределы натуральных чисел, так ещё и является некоммутативной операцией! (В алгебре деление вообще не рассматривают в “повседневном” смысле, а только умножение на обратный элемент. В частности, поэтому в натуральных числах универсального деления, в строгом смысле, просто нет. Что, конечно, никак не запрещает утверждать, что оно там всё же имеется, поскольку 12/3 == 4.) Другими словами, для того, чтобы реализовать коммутирующее преобразование типов при помощи только что описанного понятия “размерности”, потребуется принять некоторые вспомогательные соглашения, например, что a/b*b == a, и ситуация не отличается от соглашения про выбор типа правого (или левого) операнда.

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

Представьте гипотетический язык программирования, в котором предложения { 2 + “3” } и { “2” + 3 }, после преобразования компилятором, дают разные результаты: первый вариант – строку “23”, а второй – число 5. Исходя из рассмотренной выше задачи, нетрудно догадаться, почему такое происходит. Дело в том, что компилятор не только выполняет неявное преобразование типов, но ещё и “подгоняет” операции. В качестве главного типа компилятор выбирает тип правого операнда, приводя левый операнд к нему. Поэтому, в предложении { 2 + “3” } числовой тип двойки преобразуется в строку из символа “2”, а операция сложения превращается в конкатенацию (некоммутативная операция, кстати). Да. Не очень-то удобно, не то что апельсины по ящикам.

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

В новой версии:
1) добавлено описание режима использования шифров CCM;
2) актуализировано описание механизма защиты поля имени сервера (SNI);
3) добавлен небольшой фрагмент про постквантовую криптографию в TLS (это существенное направление, которое заметно изменит практику применения протокола).

Описание доступно здесь: tls.dxdt.ru/tls.html

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

В заметке, посвящённой этому событию, Брюс Шнайер пишет:
“Imagine a government using this sort of attack against another government, coordinating a series of fake tweets from hundreds of politicians and other public figures the day before a major election, to affect the outcome”. (Представьте, что правительство использует атаку такого типа в отношении другого правительства, скоординировав серии поддельных “твитов” от лица сотен политиков или других публичных фигур за день до важных выборов, чтобы повлиять на их результат.)

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

Интересно, что, как пишут, аккаунт Президента США Трампа не был затронут атакой. Если это произошло потому, что, силами Секретной службы и АНБ, государственные аккаунты особой важности отдельно защищены, то получается, что определённое регулирование в Twitter уже внедрено. Конечно, подобное скрытое и как бы “неформальное” регулирование – оно, во многих случаях, гораздо удобнее.

На dxdt.ru есть страница “Избранные записки” – добавил на эту страницу несколько новых ссылок. Конечно, записки сейчас выходят редко, тем не менее, потихоньку, но набралось количество, достаточное для обновления перечня избранных публикаций.

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

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

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

Одним из весьма эффективных вариантов оказывается использование в качестве источника такого сигнала большого количества космических аппаратов с общими синхронными часами, находящихся на низкой орбите, с которыми возможен обмен широкополосными сигналами. То есть, это уже не GPS. Это – в точности схема “спутникового Интернета”, предложенная, например, SpaceX (Starlink).

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

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

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

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

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

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

Естественно, Starlink – только один из примеров реализации подходящей технологии.

(Кстати, в 2012 году я писал о гипотетическом навигаторе, работающем без GPS.)

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

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

Что именно отображено на картинке (см. рисунок выше)? Каждой точке соответствует пара значений — элементов конечного поля. Сами эти элементы, обозначенные натуральными числами, формируют горизонтальную и вертикальную оси. А поскольку значения отображаются парами, то вся картинка соответствует F×F. Пары элементов — это пары, удовлетворяющие уравнению кривой: y² = x³ + 2020x² + x. Обратите внимание, что слева здесь квадрат, и уже из этого вытекает необходимость симметрии на картинке.

Возьмём более наглядный пример. На картинке ниже – нарисованы точки эллиптической кривой y² = x³ + 17x² + 1 над полем из 101 элемента; горизонтальная черта – разделяет “график” на верхнюю и нижнюю части (симметричные). Для двух точек – написаны их координаты: (26, 53) и (26, 48).

Почему точки симметричны? Потому что они обратные, их сумма в группе точек эллиптической кривой равна нулю (нейтральному элементу группы). Координаты X у этих точек совпадают, а координаты Y – обратные по сложению в базовом поле: 53 + 48 == 101, а это 0 (mod 101). Как уже упоминалось выше, левая часть уравнения – квадрат. Это означает, что у нас обязательно есть два элемента поля, соответствующих подстановке элемента 26 в правую часть. Полностью аналогично привычному 2² == (-2)² == 4. Проверяем: 53² (mod 101) == 48² (mod 101) == 82, а 82 == (26³ + 17*26² + 1) (mod 101). Понятно, что в группе, по определению, у каждого элемента есть обратный, поэтому картинка “ветвится” таким образом.

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

В качестве развития технологии ESNI, которая так и не вышла из статуса черновика (draft), сейчас разрабатывается вариант с передачей полного дополнительного сообщения ClientHello, но в зашифрованном виде. Предлагаемая сейчас схема выглядит чрезмерно сложной, в основном, из-за того, что логические составляющие вложены одна в другую, при этом есть ссылки из внутреннего сообщения на элементы внешнего. Вряд ли это удастся реализовать без множества ошибок, порождающих уязвимости. Тем не менее, само направление интересное. Вообще, в теории, большинство прикладных протоколов современной Сети можно сделать полностью зашифрованными, включая этап установления соединения. Конечно, на практике такое если и возможно, то не скоро, однако можно рассмотреть гипотетическую картину, которая возникнет, если схему всё же воплотить. Сейчас, в TLS 1.3, зашифрованы не все сообщения, но, если сравнить с предыдущими версиями, то на защищённый обмен стороны переходят гораздо раньше. Например, в случае развития TLS в выбранном направлении, первое же сообщение клиента будет передаваться полностью в зашифрованном виде.

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

То есть, опять же, на примере TLS, – клиент извлекает серверные криптографические параметры для установления соединения из DNS, генерирует нужные ключи и зашифровывает первое же сообщение, которое направляет серверу. Это сообщение может вообще не содержать фиксированных заголовков в открытом виде (кроме, понятно, относящихся к TCP/IP или UDP). Третья сторона видит только факт обмена узлов псевдослучайными данными. Более того, даже на уровне DNS – тоже видны только псевдослучайные данные, поскольку обмен защищён TLS, в том числе, на пути между рекурсивным резолвером и авторитативным сервером.

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

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

В-третьих, полностью исчезнут современные возможности по приоритизации разных типов трафика силами DPI: никаких сигнатур отдельных протоколов не останется, кроме самых базовых – номеров портов и IP-адресов (ну, ещё количество потоков можно как-то измерить).

Кроме того, гораздо сложнее станет отлаживать работу сетевого ПО и обнаруживать ошибки, поскольку типы прикладного трафика полностью потеряют “различимость”. Недоступным окажется пассивное блокирование ресурсов на уровне протокола (опять же, с использованием DPI).

И тем не менее, переход на такой уровень – вполне возможен в ближайшие годы.