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

Использование имеющихся сейчас посквантовых криптосистем в TLS существенно увеличивает объём передаваемых данных. Например, ключ Kyber768, используемый в первом же сообщении (ClientHello), требует более килобайта (1184 байта). При этом, в TLS 1.3 есть штатная возможность передать несколько ключей для разных криптосистем в одном сообщении ClientHello, чтобы сервер выбрал подходящее. Эта возможность постоянно используется на практике.

Например, клиент может сразу передать ключи X25519 (32 байта) и P-256 (32+32 == 64 байта). То есть, две криптосистемы – и лишь 96 байтов расходуется на запись ключей (небольшое количество дополнительных байтов нужно для записи тех структур, в которых передаются ключи, но это можно не учитывать). Если передавать ключи двух постквантовых криптосистем, – скажем, с теми же Kyber768 и стандартизованным вариантом ML-KEM, – то получается уже больше двух килобайт. Это много, но если регулярно переходить от одной поствкантовой криптосистемы к другой, то становится необходимым, рутинным элементом TLS-соединений. Заметьте, что сам перечень поддерживаемых клиентом криптосистем для обмена сессионными секретами передаётся в TLS отдельно. Обычно, в этом перечне указано значительно больше криптосистем, чем передано ключей. Так, браузер может передавать семь поддерживаемых вариантов и ключи только для трёх из них (так сейчас делает Firefox). Чтобы сервер мог выбрать криптосистему, ключи от которой отсутствуют в ClientHello, в TLS 1.3 предусмотрен механизм повторного согласования – HelloRetryRequest: сервер, в этом случае, запрашивает повторное ClientHello, где будет только ключ той криптосистемы, которая выбрана (это всё можно самостоятельно увидеть на тестовом сервере TLS 1.3 при помощи современного браузера).

Подобный перебор с постквантовыми криптосистемами ещё больше увеличивает трафик, поэтому уже рассматриваются варианты того, как бы данный момент переложить на DNS. Так, в сообщении Google про ML-KEM в браузере Chrome, на которое я недавно ссылался, упоминается соответствующий черновик RFC – там предлагается публиковать в DNS сведения о предпочитаемых криптосистемах для обмена сеансовыми ключами в TLS. Конечно, тут нужно учитывать возможную защиту DNS-ответов от подмены, то есть, всё это тянет за собой не только и не столько DNSSEC (которая сама не имеет пока что ничего “постквантового”), как DNS-over-TLS/DNS-over-HTTPS.

Развитие постквантового TLS очень бурное. Впрочем, пока что не совсем понятно, для чего вообще такой рост объёмов данных. Сама по себе “постквантовая стойкость” тут ничего не объясняет, как и популярные описания в стиле “зашифруй заранее, пока нет квантового компьютера”. Однако вот уже и DNS охвачена дополнением записей. С одной стороны, размещение предварительных сведений о настройках TLS в DNS выглядит более чем разумно: запрос в систему всё равно необходим для получения IP-адреса; с другой стороны – данное направление развития как-то быстро сводится к надстраиванию новых и новых, всё больших и больших “дополнений”. (Надстраивание происходит в ускоряющемся темпе: не успели год назад внедрить в браузеры Kyber, как его уже переименовали в ML-KEM и переделали.) Эти “дополнения” вытесняют привычную работу с DNS, заменяя её на другой процесс, который следует называть “обнаружением сервисов” (Service Discovery) – дело в том, что с появлением ECH даже и IP-адреса будут извлекаться из доступной сети по-другому.

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

Строка, вторая на скриншоте, в современной типографике выглядит так: “Κάλχας Θεστορίδης οἰωνοπόλων ὄχ᾽ ἄριστος”, то есть, “Калхас Фесторид – “птицевед” наилучший”. Фесторид, с “Ф” – это в русской традиции, а так-то можно прочитать и “Тэсторидис”, без мощного “th-фронтинга”, – выйдет больше похоже на греческую фамилию. “Птицевед” – это довольно условно: Калхас наблюдает птиц, как и уточняется в комментарии между строками (буквально: ὀρνεοσκόπων), однако он не орнитолог, а птицегадатель. Считается, что прорицатели, наряду с другими явлениями окружающей действительности, использовали наблюдение за полётом птиц для получения предмета толкования.

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

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

Google пишет, что в ближайших версиях Chrome отключит использование Kyber768, заменив его на ML-KEM. Речь про использование в гибридной криптосистеме с постквантовой стойкостью для обмена ключами TLS 1.3. То есть, вместо X25519+Kyber768 будет ML-KEM+X25519 (здесь “минус” это дефис, а “плюс” – это плюс). Связано решение с тем, что криптосистему, в постквантовой части, стандартизировал NIST, и вариант из стандарта (кто бы мог подумать!) не совместим с тем вариантом, который использовался до стандартизации под именем Kyber.

В частности, при стандартизации отказались от одного из “промежуточных” преобразований с хеш-функцией, которое, в теории, могло бы предотвращать утечки состояния генератора (псевдо)случайных чисел. Про это всё, естественно, написано в документе NIST. Формулировка выглядит занимательно для тех, кто следит за темой модификации криптосистем в стандартах. В цитате далее (из приложения к стандарту NIST) под словосочетанием “этот шаг” (this step) имеется в виду шаг алгоритма, на котором вычислялось значение SHA-256 от инициализирующего значения: “The purpose of this step was to safeguard against the use of flawed randomness generation processes. As this standard requires the use of NIST-approved randomness generation, this step is unnecessary and is not performed in ML-KEM”. Пересказ смысла: поскольку в стандарте NIST прописано требование использовать только генераторы случайных чисел, разрешённые NIST, то и дополнительная защита от “испорченных генераторов” (то есть, оборачивание значения в хеш-функцию) более и не требуется. Логично, чего уж там. Строго говоря, ничто не мешает применить хеш-функцию для маскировки состояния раньше, до передачи значения в KEM. (Тут, конечно, речь только про дополнительный шаг уровня реализации, а SHA-3, требуемая непосредственно внутри Kyber, осталась.)

Так что постквантовые криптосистемы не просто развиваются, но ещё и вот начали тасоваться их названия, порядок байтов, способы конкатенации и использования хеш-функций. Возможно, я через некоторое время добавлю ML-KEM+X25519 на свой тестовый сервер TLS 1.3.

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

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

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

Как понять, что факторизация числа 15 не может ничего говорить о реализации квантового алгоритма Шора? Понять это несложно: один из делителей числа 15 должен быть меньше 4 (потому что 4^2 == 16), единица не рассматривается по условиям задачи, и это не 2 (потому что только нечётные подходят). Так что любой процесс поиска, каким бы аналоговым он ни был, если вообще сходится, то неизбежно попадёт в 3, что и будет верным ответом.

Заметьте, что ещё и 5 = 3 + 2, а простых чисел, меньших 15, только шесть: поэтому, учитывая, что умножение здесь коммутативно (это очень важно для квантовых алгоритмов), число 2 отбрасывается, а схема поиска расщепляется на пары, то, в самом худшем случае, вероятность, что аналоговый аппарат, состояния которого переключаются по возможным узлам дерева, промахнётся – меньше трети. (На практике, ещё раз, для промахов там просто нет места.)

Представьте нехитрую схему с простым 8-битным микроконтроллером, семисегментным индикатором, сегменты которого подключены в произвольном, неизвестном заранее, порядке к выходам микроконтроллера, и с парой кнопок.

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

Комбинаций сегментов для семисегментного индикатора – не так много, даже по меркам микроконтроллера: 127. Опробованные состояния индикатора сохраняются в памяти, а “ошибочные” – второй раз не выводятся. “Успешные” состояния – записываются в отдельный массив, с индексом, соответствующим числовым значениям нужных цифр ({0,1,…,9}). Если достаточно долго нажимать кнопки, то в результате получится “знакосинтезирующий” массив. “Ещё пять тысяч вёдер и – золотой ключик у нас в кармане!”.

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

Минутка специфического интернет-технологического юмора:

A (печатая в консоли, случайно склеивает два IP-адреса, вот так: 192.168.11.12192.168.12.11.).
B (наблюдая за процессом, пишет в чат): Это был адрес в формате IPv010.
A: Почему десять?
B: Потому что два IPv4 склеились – то есть, четыре плюс четыре.
A: Тогда должно быть IP-8.
B: Вот я и пишу: IPv010.

Иногда спрашивают: почему (некоторые) УЦ TLS не поддерживают подтверждение права управления доменом с использованием WHOIS-запросов? Вот появился очередной практический пример, иллюстрирующий, почему тут не нужно использовать WHOIS ни в каком виде: исследователи зарегистрировали домен, ранее служивший хостнеймом для whois-сервиса зоны .MOBI, и, как утверждается, получили потенциальную возможность подтверждать право управления доменом по запросам от УЦ, подставляя произвольный адрес e-mail в ответ (“потенциальную” – потому что сертификат исследователи заказывать не стали).

Подтверждение (валидация) права управления доменом (DCV – Domain Control Validation) – основа процесса выпуска TLS-сертификатов публичным УЦ. Понятно, что и ответы из WHOIS должны дополнительно валидироваться, и актуальность хостнейма сервера – контролироваться. Однако, каждый новый поддерживаемый метод DCV создаёт риски, а особенно велики эти риски, когда метод подразумевает использование дополнительных протоколов. Вообще, для автоматического выполнения DCV сейчас есть только один полностью подходящий способ: публикация TXT-записи с заданным значением в DNS. Но и тут имеется куча оговорок, конечно. При этом, уже и близкий метод – HTTP-запрос, – существенно хуже, пусть и использует DNS для передачи A-записей.

Продемонстрировано извлечение данных, раскрывающих секретный ключ ECDSA, из аппаратных токенов YubiKey при помощи ПЭМИН (то есть, побочных электромагнитных излучений и наводок). Используется утечка информации о внутреннем состоянии микроконтроллера при выполнении математических операций (алгоритм Евклида при вычислении обратного элемента, которое необходимо в ECDSA). По ссылке выше – очень большое описание, потому что атака сложная, требуется достаточно хитрая аппаратура и нужен не просто физический доступ, но необходимо разобрать токен. (via)

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

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

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

Посмотрел, на какой домен можно было бы перенести dxdt.ru (поскольку RU-CENTER усиленно шлёт письма про привязку ЕСИА). Я ранее зарегистрировал несколько подходящих имён в других зонах верхнего уровня (например, .blog), однако и на этом направлении просматриваются проблемы, пусть и другого рода: вполне вероятно, что в скором времени интернет-санкции расширят очередной раз, а в результате – регистратуры (не регистраторы даже) заблокируют домены администраторов с неподходящим “подсанкционным” адресом (как уже было и с хостингами, и со многими иностранными регистраторами). Я недавно писал, что оператор реестра, – регистратура, – не только может отключить доступ регистраторов (уже происходит), но и заблокировать/удалить имена по своему выбору.

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

Знак “¬” – это логическое отрицание, проще говоря – “не”, или “!”, как будет во многих привычных языках. То есть, казалось бы, тут, во второй части, написано, что “не-не-P”, а тогда, если P имеет значение TRUE, то “не-не-P” тоже TRUE; то же верно и для P == FALSE. Понятное двойное отрицание, поэтому, что P, что ¬¬P – разницы нет: одно и то же. Это, впрочем, не совсем так.

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

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

b = 14; 
for(a = 0; a < 8; a++){ 
 b = b + a;
} 

заменяется на эквивалентное

b = 42;

(или это не эквивалентная замена?)

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

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