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

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

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

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

В продолжение недавней записки про X25519Kyber768 на TLS-сервере – подробности встраивания данной гибридной криптосистемы в схему работы TLS 1.3.

1. Как нетрудно догадаться, X25519Kyber768 состоит из X25519 и Kyber768, поэтому криптосистема и гибридная. X25519 – это хорошо известный вариант протокола Диффи-Хеллмана (DH), здесь используется без изменений, обычным образом (см. кстати, заметку с задачей про 2^255 – 19). Kyber768 – схема KEM (инкапсуляции ключа), построенная на криптосистеме Kyber с “постквантовой стойкостью”. Эта криптосистема реализует зашифрование с открытым ключом (важный момент).

2. В TLS рассматриваемая криптосистема используется для получения симметричного сеансового секрета. Открытый ключ передаётся клиентом в составе ClientHello, в расширении key_share, а ответная часть сервером – в ServerHello, key_share. В логике сообщений тут ничего не меняется.

3. Изменяется часть внутри key_share, соответствующая X25519Kyber768 – клиент передаёт результат конкатенации байтов, составляющих клиентскую часть DH X25519 и открытый ключ клиента Kyber768. Эти данные имеют фиксированную длину, определяемую алгоритмами: 32 начальных байта для X25519 и 1184 для Kyber768, 1216 байтов всего. На сервере данные разделяются (просто, по длине) и используются для обеих криптосистем. А именно: для X25519 сервер вычисляет общий секрет DH и серверную открытую часть DH (B), так же, как это делалось бы в случае отдельной криптосистемы X25519; для Kyber768 – сервер генерирует общий секрет и оборачивает его в KEM (то есть, зашифровывает исходное секретное значение, используя открытый ключ Kyber, присланный клиентом – тем самые 1184 байта). Два секрета сервер объединяет в один массив – здесь, опять же, простая конкатенация: BaseSecret = x25519[] + Kyber_Shared_Secret[]. Обратите внимание на важное техническое отличие: для X25519 общий секрет, на сервере, это результат умножения открытой части DH клиента (A) на секретный скаляр сервера d: s = d*A; а для Kyber – сервер выбирает исходное значение, которое отправляет клиенту в зашифрованном виде (очень похоже на устаревшую схему с RSA-шифрованием в TLS, но устроенную наоборот). При этом внутри KEM Kyber для вычисления секрета по исходному значению используется отдельная функция (KDF), подмешивающая ещё и значение открытого ключа, это необходимый шаг, но, с точки зрения логики получения секрета, это не так важно. Секрет, генерируемый в рамках Kyber768 в TLS – это тоже 32 байта (256 бит). После завершения данного этапа – сервер получил общий симметричный секрет, представляющий собой объединение выдачи двух алгоритмов: 32 байта и 32 байта. Также сервер получил открытую часть DH и зашифрованный Kyber симметричный секрет (это только часть, предназначенная для Kyber, результат X25519 сюда не попадает).

4. Сервер формирует ответное расширение key_share, присоединяя к 32 байтам открытой части DH X25519 байты шифротекста с симметричным секретом, который зашифрован Kyber – длина шифротекста 1088 байтов, всего 1120 байтов. Ответное key_share сервер отправляет клиенту в открытой части сообщений, в ServerHello, после чего генерирует на основе общего секрета набор симметричных сессионных ключей и переходит к зашифрованному обмену данными.

5. Клиент, получив key_share X25519Kyber768, разделяет данные на открытую часть обмена DH X25519 (B) и шифротекст Kyber768. По значению B DH клиент вычисляет общий секрет DH X25519 (здесь – 32 байта), который совпадает с серверным. Используя секретный ключ, клиент расшифровывает шифротекст и вычисляет общий секрет Kyber. Оба полученных значения объединяются, результат должен совпасть с серверным. (Тут слово “должен” использовано потому, что в Kyber, к сожалению, есть вероятностный элемент: так как это схема, концептуально происходящая из кодов с коррекцией ошибок, то имеется очень небольшая вероятность, что “ошибка” всё же останется, а клиент и сервер получат разные значения секрета.) На основе объединённого секрета клиент вычисляет набор симметричных ключей и может проверить подлинность и расшифровать следующие сообщения сервера.

Таким образом, Kyber простым и понятным способом добавляет 256 бит “постквантовой стойкости” к исходному симметричному секрету TLS-сессии, какие-то другие параметры – не изменяются.

Кстати, индекс 0x6399, который позволяет отличить ключи криптосистемы X25519Kyber768Draft00 в TLS-сообщениях, внесён в соответствующий реестр номеров IANA, в раздел под именем TLS Supported Groups. Название раздела – ещё один пример исторически сложившихся особенностей спецификаций: понятно, что X25519Kyber768 – никакая ни группа, а сразу две криптосистемы, построенные на различном математическом аппарате (но, естественно, группы нетрудно найти и в X25519, и в Kyber768). Изначально, упомянутый раздел параметров TLS содержал индексы именованных эллиптических кривых, то есть, сочетаний из параметров, определяющих конкретную кривую в прикладном смысле. Но так как для криптосистем существенны были именно операции в группе, а кроме эллиптических кривых ещё использовались (и используются) мультипликативные группы колец вычетов, то раздел, довольно давно, переименовали в “Поддерживаемые группы”, теперь туда записывают наборы криптосистем.

Развивающаяся “битва за банхаммер” приводит к тому, что в “этих интернетах” появляются новые плоскости для осуществления сегментации, поскольку блокирование сейчас модно делать на достаточно высоком уровне – на уровне приложений. Недавний пример – стена (временная) регистрации в Twitter. Есть масса других примеров, где администраторы вроде бы “глобального” массового сервиса ограничивают к нему доступ для некоторых IP-адресов, но не на уровне транспорта, а средствами HTTP или внутри приложения на смартфоне. Вообще, может показаться, что, с точки зрения “маршрутов” и BGP – ничего не меняется: пакеты если ходят, то так и ходят, как ходили. Для инженера NOC, допустим, прежде всего важно, что отправленный по заданному адресу пакет до этого адреса добрался, а что там происходит на уровнях, которые строятся из пакетов, HTTP это или QUIC какой-нибудь, – дело десятое.

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

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

Всё же я пока восстановил свой экспериментальный сервер TLS 1.3 – tls13.1d.pw (некоторое время назад я писал, что собираюсь его совсем отключить). А чтобы восстановление выглядело поинтереснее, я реализовал на сервере поддержку постквантовой схемы получения общего секрета (KEM) X25519Kyber768. TLS с Kyber768 там реализован вручную, но я, впрочем, использовал криптопримитивы из удобной библиотеки Cloudflare.

Криптосистему с постквантовой схемой KEM Kyber768 в конце августа Google внедрил в браузер Chrome (в порядке эксперимента), так что можете проверить – на сервере у X25519Kyber768 повышен приоритет, поэтому, при наличии соответствующего открытого ключа в сообщении клиента, выбираться она должна довольно часто.

Вообще, открытый блок клиентского KeyShare в X25519Kyber768 весит аж 1216 байтов (32 + 1184, потому что это ключ X25519, 32 байта, плюс ключ постквантовой части Kyber768, который большой). Тем не менее, я всё же пока что сделал вывод этого ключа без сокращений, что, возможно, выглядит тяжеловато, но видно будет только в браузере с поддержкой данной криптосистемы. (Дополнение, 12/09/2023: технические подробности об использовании криптосистемы.)

Поддержка есть только в самых свежих версиях Chrome (>=116), а включать её нужно через флаги: chrome://flags, набрать “TLS13” в поиске, флаг называется “TLS 1.3 hybridized Kyber support”.

(Не знаю, будет ли у меня возможность поддерживать сервер далее, так что в какой-то момент он может отключиться, теперь уже даже и без предупреждения, но посмотрим; ошибки подключения, естественно, могут быть и по другим причинам – это, всё ж, экспериментальный сервер.)

Обычно, DNS-резолвер должен работать внутри VPN-сервиса – то есть, это может быть буквально обособленный резолвер, используемый именно в составе VPN (желательно, с DNSSEC). Но так делается далеко не всегда. Напомню, что DNS-резолвер (в данном случае, речь про рекурсивный резолвер) – это сервис, который проводит опрос серверов DNS, отыскивая, например, IP-адреса по именам узлов – адрес, по которому нужно браузеру обращаться к веб-серверу под именем test.ru. Резолвер выполняет то, что называется рекурсивным опросом: обращается к авторитативным DNS-серверам разных уровней. Эти серверы видят IP-адрес резолвера, но не клиента резолвера, который (вероятно) будет подключаться к сервису по обнаруженному в DNS адресу. При этом, для целей балансировки нагрузки на “целевой” сервис, DNS-серверу удобно было бы знать что-то о клиенте, для которого работает конкретный резолвер – потому что балансировка выполняется именно для клиента сервиса, а не для клиента DNS (сервис доменных имён (DNS) в этот момент уже на нужной стороне отработал). Это особенно актуально для больших открытых сервисов DNS-резолверов, например, Google Public DNS, так как эти сервисы обслуживают клиентов из самых разных точек сети. Чтобы как-то помочь оптимизации, довольно давно придумали расширение DNS под названием EDNS Client Subnet (ECS).

Данная технология (ECS) позволяет резолверу передать в сторону авторитативного сервера сведения об IP-подсети клиента, который обратился с запросом. Проще говоря – авторитативный сервер увидит IP-адресный блок, который соответствует клиенту, находящемуся за резолвером, что позволит определить провайдера. ECS как раз поддерживается Google Public DNS (и не только). Предполагается, что авторитативный сервер, определив провайдера клиента резолвера, сможет применить какие-то правила оптимизации. Если VPN используется для сокрытия IP-адреса пользовательского подключения, но DNS-трафик направляется не через VPN в какой-то DNS-сервис, то наличие ECS в этом сервисе (при прочих равных) означает, что внешние авторитативные DNS-серверы увидят скрываемую подсеть. Об этом нередко забывают.

Технический пример (не учитывающий NAT и другие тонкие настройки): предположим, клиентское устройство использует провайдерский доступ с адресом 10.11.12.13, ему соответствует подсеть 10.11.12.0/24; выход из VPN использует подключение с IP 10.22.22.22 (подсеть 10.22.22.0/24); DNS-трафик направляется напрямую (не через VPN) резолверу 10.53.53.53, резолвер поддерживает ECS. Тогда, при попытке определить значение A-записи (адрес), внешние серверы DNS узнают, что к ним подключается резолвер с адресом 10.53.53.53 для клиента из подсети 10.11.12.0/24. А вот на веб-сервере, к которому обращение произойдёт через VPN, адрес клиента будет виден как 10.22.22.22 – внешняя точка VPN. Естественно, если DNS-трафик маршрутизируется устройством через VPN, то внешний DNS-сервис с ECS сможет передать наружу только подсеть точки выхода VPN (10.22.22.0/24), поскольку именно адрес из этой подсети он видит в качестве источника запроса. Но лучше, конечно, если вообще используется собственный резолвер без ECS в составе VPN-сервиса, потому что возможны и другие каналы утечки метаинформации.

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

Так вот, если у вас есть устройства “на местах”, которые приносят дополнительную информацию, а не только “координатные данные” GPS, то можно на центральном сервере выстраивать динамику изменения реального навигационного поля по сравнению с моделью, учитывающей только положение и состояние спутников. Это позволяет не просто получить корректирующую величину для всех участников системы, но также увидеть возникающие на местах пространственные дефекты и искажения с развёрткой по времени (то есть, не просто спуфинг), что весьма ценно.

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

Предположим, что при измерениях около нуля Цельсия наш датчик и схемы преобразования электрических сигналов могут давать “погрешность” (в кавычках – потому что это здесь условный технический термин для конкретного измерения) до 0.3 градуса, по сравнению с реальной температурой измеряемой среды (тут ещё вопрос, какая именно температура измеряется и как определяется равновесие, но ладно). Что означают эти 0.3 градуса “погрешности”? Они означают, что когда температура в измеряемой датчиком точке 1.0 градус ровно (Цельсия, но это не важно), схемы датчика могут показать 1.1, 1.21, 1.3 – ещё что-то похожее. При этом, чтобы как-то попытаться снять кавычки с “погрешности”, нужно ещё учитывать, какая у нас доступна разрешающая способность после датчика – видим ли мы разницу между 1.2 и 1.21 близко к датчику или этот 0.1 уже шум от последующих элементов схемы (а может и ошибка в Excel, кто знает). Так что считаем, что наша “погрешность” – 0.3. Всё это, естественно, умеют учитывать так или иначе, но корректные алгоритмы вычислений с погрешностями измерений достаточно сложны (есть специальные методы, теории и разные подходы).

Однако попробуем упростить ситуацию. Для примера. Если привычным способом “считать на компьютере”, то можно пронаблюдать занимательные эффекты. Предположим, что у нас пять датчиков. В измерении “А” датчики показали следующие значения (пусть, всё градусы Цельсия): 1.3, 2.3, 2.3, 3.3, 3.3, (много одинаковых значений почему-то, подозрительно); среднее арифметическое для этих измерений равно 2.5; а в измерении “Б” данные получились такие: 1.3, 2.3, 2.3, 3.3, 3.1; среднее – 2.46. Средние показатели отличаются на 0.04. Попробуем так и записать: “средняя температура, между измерениями “А” и “Б”, упала на 0.04 градуса”. И тут не только неожиданно вылезла точность в сотых долях, которая, на минуточку, в семь с лишним раз, если так можно выразиться, “лучше” заявленной выше “погрешности” (0.3), но и реально измеряемая температура могла при этом вовсе не поменяться (а могла и поменяться). Так что при вычислениях нужно учитывать модель измерений. При этом точное измерение конкретно “температуры”, чтобы это ни значило, обычно связано с большими технологическими трудностями (дополнение: особенно, если это измерение выполнено 70 лет назад), которые в СМИ не попадают.

(Кстати, что касается СМИ: замечание про модели измерений особенно актуально и для машинного обучения, которое про соответствующие модели тут ничего учитывать не может.)

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

Исходные тексты программ – ценный источник информации о возможной работе этих программ. Относится и к другим текстам. Ниже – два варианта записи одного и того же фрагмента из “Физики” Аристотеля на “языке оригинала”, то есть, это древнегреческий, но, конечно, переписанный много позднее Аристотеля и по другим источникам. В данном фрагменте Аристотель объясняет, что поскольку при падении через “пустоту” нет причин для того, чтобы разные тела набирали разную максимальную скорость падения, потому что отсутствует сопротивление среды, то и все тела будут “одинаково быстро” падать, а это, как считает Аристотель, невозможно – поскольку он так объясняет, что не может быть пустоты. Но это другая история, а здесь текст служит примером того, как могут различаться записи. Красными точками я отметил начало и конец фрагмента. Первый скриншот – из манускрипта, датируемого 12 веком:

Второй – из манускрипта, который “посвежее” и датируется, как я понимаю, чуть позже, то есть, 13 веком:

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

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