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

Мы рассмотрим конкретный (хоть и игрушечный) пример реализации протокола Диффи-Хеллмана (DH) в группе точек эллиптической кривой (ECDH), а потом проведём на этот пример элементарную алгебраическую атаку, основанную на свойствах выбранных параметров, тем самым выясним, что параметры требуется выбирать аккуратно.

В качестве базового поля выберем GF(8191) – конечное поле порядка 8191 (8191 – простое число). Это поле изоморфно вычетам по модулю 8191, то есть, мы рассматриваем остатки от деления на 8191: 0, 1, 2… – поэтому далее элементы поля обозначаются целыми числами.

Выберем уравнение, задающее эллиптическую кривую E:
y² = x³ + 2020x² + x.
Это уравнение в форме Монтгомери, общий вид таких уравнений:
y² = x³ + Ax² + x, где A – элемент базового поля; в нашем примере A == 2020.
Не всякую эллиптическую кривую над конечным полем можно представить в форме Монтгомери. (Нетрудно заметить, что все кривые в форме Монтгомери вполне определяются значением коэффициента А, это удобно.)

Точки кривой соответствуют парам (X, Y) элементов базового поля, удовлетворяющим уравнению, включая особую точку “бесконечность”, которая в группе точек является нейтральным элементом. Пример точки: (839, 7305). Можно проверить (например, в WoframAlpha), что 7305² (mod 8191) == (839³ + 2020*839² + 839) (mod 8191). Заметьте, что пара (0,0) лежит на кривой, но не является нейтральным элементом! Нейтральный элемент мы будем обозначать пустой парой () или буквой O, а точка (0,0), если её сложить с точкой (839, 7305), даст точку (1523,5367). Групповую операцию на E обозначим символом “+”.

Группа точек нашей кривой E имеет порядок 8176, то есть, состоит из 8176 элементов. Сразу заметим, что эта кривая не подходит для практического использования, и не только потому, что здесь “мало точек”, но и из-за разложения числа 8176 == 2⁴ * 7 * 73. Однако для нашего примера – именно это и нужно. Кроме базового поля и эллиптической кривой, параметры протокола ECDH включают точку кривой, которая называется генератором. Поскольку генератор – это точка на кривой, он является элементом её группы. Выбираем точку (1029, 895) на роль генератора. Обозначим генератор буквой G. Если генератор G складывать с самой собой, то на каком-то шаге получим нейтральный элемент группы. Количество экземпляров G, которые нужно сложить, чтобы получить нейтральный элемент, называется порядком элемента. Для выбранного значения G порядок равен 1022. Обратите внимание, что порядок точки-генератора меньше порядка группы. G – генерирует подгруппу в E, порядок подгруппы всегда делит порядок группы (теорема Лагранжа): 8176 == 8*1022.

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

Итак, мы выбрали поле GF(8191), уравнение кривой E y² = x³ + 2020x² + x, и генератор G = (1029, 895).

Введём умножение на скаляр: G + G + G = [3]G == 3*G. То есть, мы определили, что сложение трёх экземпляров точки с самой собой – записывается как 3*G. Важно заметить, что такое умножение – это не операция в группе точек кривой, а некоторая дополнительная конструкция.

Перейдём к протоколу ECDH между двумя сторонами. Стороны выбирают секретные скаляры – m и n, это целые положительные числа, меньшие порядка генератора G (понятно, что брать в качестве секретного скаляра единицу – особого смысла тоже нет). Стороны обмениваются по открытому каналу значениями m*G и n*G. Эти значения – точки на кривой, соответствующие n- и m-кратному сложению генератора G. Общий секрет стороны вычисляют так: m*(n*G) == n*(m*G) == (n*m)*G. Ограничение по порядку генератора вызвано тем, что нет смысла использовать числа, превышающие порядок: соответствующая точка всё равно будет находиться в подгруппе генератора.

Пример в числах:

m = 731
n = 395

m*G == (5720, 2990)
n*G == (6695, 8044)

m*(n*G) = [731](6695, 8044) == (4647, 2580) == n*(m*G) = [395](5720, 2990)

Таким образом, стороны получили общий секрет – точку на кривой с координатами (4647, 2580). Эта точка равна точке [731*395]G. Обратите внимание, что произведение 731 * 395 == 288745, можно привести по модулю 1022, то есть, по модулю порядка генератора G. (Но можно и не приводить – результат не изменится.) Значение общего секрета используется в качестве входных данных для вычисления ключей симметричного шифра. Именно так ECDH применяется в TLS. Точке соответствует пара (X, Y) элементов поля, но в качестве источника данных для ключа может использоваться только один элемент, обычно, это X-координата.

Сторона, прослушивающая канал, получила значения n*G и m*G, знает параметры поля, кривую, значение G, но не знает n и/или m. Вычисление n (или m) по известному n*G (или m*G) – называется задачей дискретного логарифмирования в конечной группе и, для произвольных групп точек эллиптической кривой достаточно большого порядка, вычислительно трудна. На практике используются параметры с порядками, близкими к 2²⁵⁶ (и более). Методов, позволяющих даже на специализированном суперкомпьютере за разумное время решить задачу дискретного логарифмирования для произвольных параметров и групп таких порядков – пока не найдено. Однако для некоторых специальных случаев – методы известны. Некоторые из этих методов элементарны, как будет видно из примера ниже.

Попробуем теперь взломать нашу “криптосистему” ECDH на эллиптической кривой. Конечно, в случае использованных параметров, не составляет труда простым перебором найти нужное значение секретного скаляра (оно лежит в интервале [2..1021]). Однако простой перебор здесь работает только потому, что порядок далёк от практических значений. Но есть гораздо более эффективный метод, который, с некоторыми упрощениям, и описан ниже.

Заметим, что число 1022 == 2 * 7 * 73. Это означает, что внутри нашей подгруппы генератора G могут быть меньшие подгруппы, порядок которых делит порядок генератора. Всякий элемент подгруппы представим в виде l*G – то есть: G + G+…+ G (l раз). Так что, возможно, найдутся такие элементы, которые конструируются из G, но при этом их порядок гораздо меньше 1022. Пусть такой элемент – P = (6736, 4842) == 14*G, где 14 == 1022/73 == 2 * 7. Используя P, мы можем “разбить” все элементы подгруппы генератора на подмножества с меньшим количеством элементов, каждый из которых соответствует той или иной “кратности” P. P имеет порядок 73, то есть 73*P == O, где O – нейтральный элемент группы (или, в других обозначениях: P + P + … + P = O). Это всего 73 различных значения (включая нейтральный элемент). Атака работает следующим способом. Сгенерируем и запишем в опорную таблицу все пары (k, k*P), где k пробегает [1..72]. Получив значение m*G (открытый ключ ECDH Q == m*G), мы будем вычитать из него G до тех пор, пока не обнаружим элемент, кратный P, который находится в опорной таблице. (Вычитание в группе эквивалентно сложению с обратным элементом, то есть -G, обратный к данному элемент группы кривой нетрудно вычислить.) Пусть мы на шаге q последовательного вычитания нашли подходящее k*P в таблице, тогда, зная k, мы можем вычислить секретный скаляр m == k * 1022/73 + q.

Проверим для m == 731, как в примере выше.

731*G == (5720, 2990). Вычитаем генератор G равный (1029, 895). Обратная к G точка – (1029, 7296), т.к. 7296 + 895 = 0 (mod 8191).

(5720, 2990) + (1029, 7296) == (5623, 8124)
(5623, 8124) + (1029, 7296) == (6316, 6614)
(6316, 6614) + (1029, 7296) == (7183, 6772)

Точка (7183, 6772) является кратной точкой для элемента P, который выбран нами выше в качестве опорного: [52]P == (7183, 6772). Таким образом, мы провели три операции сложения точек кривой (q == 3) и нашли заранее вычисленную опорную точку. Теперь мы можем определить секретный скаляр: 52 * 1022/73 + 3 == 731. Заметьте, что в одно значение P как бы “входит” 14 экземпляров G, то есть, чтобы гарантированно попасть в одну из точек опорной таблицы, потребуется не более 13 операций сложения точек. Для определения значения m == 731 прямым полным перебором – пришлось бы выполнить 730 сложений (если, конечно, не оптимизировать процесс поиска другим способом). Очевидно, что можно использовать и другие подгруппы для этой атаки – в каких-то случаях потребуется больше памяти для хранения опорной таблицы, но меньше операций с точками для поиска элемента таблицы; в других случаях – меньше памяти, но больше операций с точками.

Посмотрим, почему это работает, с другой стороны. В группе точек генератора все элементы представимы в виде l*G, для некоторого целочисленного l. Мы выбрали точку P == l*G. На следующем шаге мы вычисляем все значения k*P (их конечное количество) и записываем их в таблицу вместе с соответствующим k. То есть, мы построили таблицу дискретных логарифмов для P. Каждое из значений в таблице равно k*(l*G), что можно переписать как (k*l)*G (важно понимать, что здесь использованы два различных умножения: в целых числах, для k*l, и умножение скаляра на точку кривой для G). Соответственно, открытый ключ ECDH Q == m*G можно переписать как (k*l + r)*G, где k*l + r == m – представление целого m, где r – остаток от деления на l (0 <= r < l). Перепишем выражение: Q = (k*l)*G + r*G. (Здесь знак “+” уже превратился в обозначение операции сложения точек, но общий смысл не поменялся.) Мы вычитаем из значения Q генератор G до тех пор, пока полученный результат не совпадёт с каким-то из элементов нашей таблицы логарифмов для P, таким образом – подсчитывается значение остатка r. Как только мы нашли подходящий элемент в таблице, мы знаем все значения, нужные для вычисления секретного ключа m: значение k – из таблицы, l – известно из построения P, r – остаток, равный количеству операций вычитания, потребовавшихся для того, чтобы Q указало на тот или иной элемент таблицы. Таблица логарифмов содержит всего 72 элемента, что значительно меньше, чем 1022.

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

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

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

Эволюция телефонного аппарата продолжается.

Ракета.

Сейчас принято многие идентификаторы строго связывать с конкретной персоной, то есть, с человеком. Например, телефонный номер (мобильного телефона). Или адрес e-mail. Эту контактную информацию просят указывать едва ли не повсеместно для получения доступа ко многим необходимым сейчас сервисам. И это не просто “контакт” – на практике нередко выходит так, что доступ невозможно получить, если у вас, например, нет мобильного телефона. А далее считается, что человек непосредственно идентифицируется по этим “контактам”. Естественно, в таком подходе есть существенная доля практического смысла. Но есть и занятные хитрости, которые принято не замечать. Не замечать – хотя бы до тех пор, пока в списке контактов мессенджера, идентифицирующего пользователей по телефонным номерам, вместо знакомого человека вдруг появляется совсем другой.

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

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

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

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

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

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

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

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

По состоянию на декабрь 2019 года для веб-узлов Рунета более 80% TLS-сертификатов (HTTPS) выпущены всего двумя удостоверяющими центрами (УЦ): Let’s Encrypt и Cloudflare Inc. Соответствующую статистику TLS можно посмотреть на сайте проекта Statdom.ru (да, там тоже сертификат Let’s Encrypt).

Лидерство этих УЦ – довольно интересный показатель. Доля Let’s Encrypt, предоставляющего бесплатные сертификаты, уже более двух лет находится в интервале 61 — 68%, а вот Cloudflare – набрали почти 15% примерно за год. Конечно, в случае Cloudflare, это просто переход от одного названия к другому – ранее они использовали сертификаты УЦ Comodo, а потом перешли на собственное имя, – но это никак не отменяет достижений.

Такое “сосредоточение” процедур по выпуску сертификатов может вызвать различные опасения. Поэтому, думаю, полезно коснуться некоторых популярных вопросов по теме.

Означает ли это, что наступила некая “сверхцентрализация” и почти все HTTPS-узлы – захвачены? И да, и нет. Дело в том, что в выборе TLS-сертификатов и УЦ участвует несколько сторон, а определяющую роль играет браузер и операционная система. То есть, чтобы УЦ смог выпускать доверенные сертификаты, корневые ключи этого УЦ должны попасть в перечень доверенных браузера (либо операционной системы – зависит от конкретной среды, но в нашем случае это не важно). То есть, говорить о “сверхцентрализации” рано – теоретически, браузеры могут исключить, например, Let’s Encrypt из списка доверенных (прецеденты известны). Другое дело, что данный УЦ стал слишком большим, чтобы его просто так взяли и исключили: даже в случае существенных обстоятельств – такое исключение будет проводиться постепенно (если вообще будет проводиться).

Можно ли говорить, что эти УЦ теперь имеют доступ к данным почти всех HTTPS-сайтов, потому что там установлены их сертификаты? Нет, так говорить нельзя. Хотя и тут есть тонкости. Let’s Encrypt вообще не получает, при штатном способе выпуска сертификата, доступа к секретным ключам сервера (эти ключи просто не нужны УЦ для выпуска сертификата), соответственно, как-то расшифровать и перехватить данные этот УЦ не может. А вот у Cloudflare доступ к данным веб-узла с их сертификатом, конечно, есть, но совсем по другим причинам, не связанным с работой УЦ: основная услуга Cloudflare – проксирование соединений, предоставление веб-фронтенда; соответственно, они и так имеют доступ к трафику своих клиентов, вне зависимости от того, какой сертификат установлен на узле. (Интересно, что Cloudflare первыми массово внедрили технологию, позволяющую клиенту не передавать провайдеру копию секретного ключа для осуществления проксирования HTTPS-запросов. Addon /07.02.2020/: точнее, они первыми внедрили такую технологию на своём массовом сервисе, но не факт, что она получила большое распространение – это нужно смотреть отдельно.)

Более того, угроза прозрачного перехвата трафика, при помощи подмены TLS-сертификата, связана с любым УЦ, входящим в список доверенных, и никак не зависит от популярности УЦ. (Это общий дефект современной реализации PKI в вебе, с которым давно пытаются бороться отдельными методами.)

Да, в случае каких-то глобальных проблем – сайты смогут перейти на сертификаты других УЦ. Вряд ли переход будет быстрым и простым, но он возможен. А сайты, использующие Cloudflare, так или иначе полностью зависят от работоспособности данного провайдера, поэтому для них использование сертификатов “карманного” УЦ вообще не создаёт существенных дополнительных рисков. Но всё же: 80% узлов – это четыре пятых всех сайтов с HTTPS. С другой стороны, распространённых браузеров тоже всего два.

Обновления на сервере tls13.1d.pw, который предназначен для тестирования реализаций TLS версии 1.3 и сопутствующих технологий:

1) появилась поддержка ротации (обновления) симметричных ключей сессии. Речь про механизм Key Update, который в TLS применяется для того, чтобы узлы могли перейти на новые ключи внутри уже установленной сессии. Новое поколение ключей вычисляется на основе данных предыдущего поколения. Есть два варианта схемы обновления: на новые ключи либо переходит только один узел, либо оба узла. Для управления обновлением служит TLS-сообщение KeyUpdate. Сервер tls13.1d.pw поддерживает инициированное клиентом обновление (в двух вариантах – с обновлением серверных ключей и без оного), а также, с вероятностью примерно 1/3, может сам передать сообщение KeyUpdate, соответствующее замене серверных ключей (и заменить ключи);

2) теперь сервер перемешивает на своей стороне приоритеты шифронаборов при каждом соединении. Это означает, что могут быть выбраны разные шифры для разных соединений, но для одних и тех же настроек на стороне клиента. В предыдущих версиях приоритеты были зафиксированы, а наивысшее значение имел шифронабор CHACHA20_POLY1305_SHA256. Поэтому, если в качестве клиента выступал, например, браузер Chrome со стандартными настройками, то всегда согласовывался шифронабор с CHACHA20. При этом сервер поддерживает ещё AES в вариантах с 128- и 256-битным ключом. Теперь AES тоже будет иногда выбираться и для клиентов, у которых есть CHACHA20 (естественно, клиент должен заявить поддержку AES);

3) в части, реализующей элементарный веб-сервер, появилась чуть более развитая поддержка URL и кодов статуса HTTP. Теперь сервер различает адреса документов и даже умеет отдавать разные файлы при обращении по разным адресам. Это последнее новшество позволило добавить передачу файла стилей (CSS) и сделать некоторое минимальное оформление страницы результатов (но, собственно, эта часть обновлений не имеет отношения к TLS).

Что касается KeyUpdate, то здесь поддержка браузерами имеет некоторые ограничения: инициировать ротацию ключей на стороне браузера пользователь не может, однако успешная замена серверных симметричных ключей будет отражена на странице результата – там дописывается сообщение о такой замене (интересно, что если браузер на своей стороне ключ не поменял, то расшифровать данные страницы окажется невозможно и пользователь так или иначе не увидит сообщения об успешной ротации ключей). При желании, посмотреть на то, как работает KeyUpdate, можно с помощью утилиты s_client из OpenSSL (нужна современная версия): в s_client есть специальные интерактивные команды ‘k’ и ‘K’ (строчная и заглавная буквы), которые позволяют отправить KeyUpdate с флагами двух видов – замена ключей только одним узлом (k) или обоими узлами (клиентом и сервером).

Описание возможностей сервера есть в отдельной записке.

ESNI – это технология, предотвращающая утечку имени сервера при установлении TLS-соединения. Технология пока находится в фактическом статусе эксперимента, но ещё нет RFC, а только черновик (draft). Поддержка ESNI (в версии черновика) уже более года есть на веб-серверах Cloudflare и в браузере Firefox (в основной ветке). Также, около года назад, я реализовал ESNI на тестовом сервере TLS 1.3 – https://tls13.1d.pw/. (Кстати, мой тестовый сервер – один из очень немногих серверов, поддерживающих ESNI, но не принадлежащих при этом Cloudflare.)

За год RFC для ESNI не появилось, но прогресс в разработке есть. Например, ESNI, судя по всему, получит собственный тип ресурсной записи DNS – сейчас ESNI-данные публикуются в DNS-записях типа TXT. Размещение в TXT создаёт некоторые проблемы, поскольку нередко доменные зоны настроены таким образом, что отдают TXT-записи произвольного содержания на запросы для всех имён внутри этих зон (это неверная, но распространённая практика). Кроме того, у тех администраторов, которые управляют достаточно большими пулами доменов и веб-серверов, проблемы возникают из-за различных конфликтов между именами в ESNI, именами внутри TLS-сессий на стороне сервера, и именами (хостнеймами) логических узлов. Отдельный тип DNS-записи поможет бороться с этими проблемами.

Интересно, что из задачи публикации ESNI-параметров в DNS – выросло отдельное направление, в рамках которого предлагается добавить механизм, позволяющий размещать в DNS целый набор дополнительных параметров, описывающих доступ к веб-ресурсам по HTTP(S) (в том числе, указание на перечень протоколов, нестандартных номеров портов, веб-фронтендов и т.д.).

В рамках развития ESNI, появится комплект сигналов в TLS, которые позволят серверу и клиенту работать в конфигурации, где использование ESNI является обязательным (и, в частности, эффективно выбирать различные наборы криптографических ключей). То есть, работа ESNI становится более гибкой и удобной для провайдеров CDN.

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

К наступающему новому году – подборка ранее опубликованных записок:

• DNS-over-HTTPS в браузере Firefox, блокировки и будущее Сети
• “Спутниковые интернеты” и обнаружение наземных станций доступа
• TLS, зашифрованные протоколы и DPI
• Кто видит как кошка
• Скрытые сервисы и прокси

И ещё одна важная ссылка – в начале 2019 года в “Открытых системах” опубликована моя статья про будущее блокировок доступа к ресурсам глобальной Сети: “За час до закрытия Интернета”.

С наступающим Новым годом! Спасибо, что читаете!

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

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

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

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

Например, когда говорят о задаче криптографии с открытым ключом, речь идёт об алгоритме Шора. Квантовая часть этого алгоритма позволяет найти значение (период известной функции), знание которого делает возможным быстрое вычисление разложения заданного числа на множители уже на классическом компьютере. Искомый период функции здесь и есть отражение структуры, соответствующей разложению на множители. Собственно, разложение на множители актуально для криптосистемы RSA, однако тот же алгоритм позволяет взломать и криптосистемы, основанные на задаче дискретного логарифмирования, например, подпись ECDSA или распространённые сейчас реализации алгоритма Диффи-Хеллмана.

Итак, алгоритм Шора, в теории, позволяет взять произвольный открытый ключ RSA, за часы или дни найти для него разложение на простые множители, после чего практически мгновенно получить соответствующий секретный ключ. В чуть больших деталях этот процесс мог бы выглядеть так: открытый ключ RSA уже известен, он состоит из модуля M и “шифрующей экспоненты” e – это два целых числа; модуль является произведением двух простых чисел M = p*q; секретный ключ представляет собой “расшифровывающую экспоненту” d (опять целое число), которая соответствует “шифрующей”. Знание p и q позволяет очень быстро вычислить d для заданной экспоненты e на обычном компьютере (собственно, это вычисление проводится всякий раз, когда генерируется пара ключей RSA).

Сколько кубитов потребуется для атаки на практически используемые ключи RSA? Типичная битовая длина RSA-модуля сейчас 2048 бит. А вот оценки для количества кубитов – очень разные. Из свойств алгоритма Шора понятно, что потребуется, как минимум, двойная разрядность, то есть, 4096 кубитов. Однако эта оценка очень оптимистична: предполагается, что в зависимости от физического воплощения квантового компьютера и реализации алгоритма Шора может потребоваться и десятикратное увеличение (то есть, 20480 кубитов), и даже миллионы кубитов. Так или иначе, сейчас, когда говорят об универсальных квантовых компьютерах, имеют в виду единичные устройства с несколькими десятками кубитов (например, 53 кубита у Google и IBM). Поэтому до практических разрядностей ещё далеко. Тут, впрочем, есть два интересных момента: во-первых, вполне вероятно, что получив работающий универсальный квантовый компьютер с сотней кубитов, его смогут быстро масштабировать на тысячи и далее; во-вторых, для атаки на широко применяемые сейчас криптосистемы, использующие арифметику эллиптических кривых (ECDSA), кубитов нужно меньше, чем в случае с RSA, потому что меньше разрядность.

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

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

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

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

Скорее всего, на практике будет использован тот или иной вариант криптосистемы на эллиптических кривых. Для генерации общего секрета – протокол Диффи-Хеллмана (DH). С этим протоколом связано одно из расхожих заблуждений, что, якобы, он не обладает постквантовой стойкостью. В реальности, уязвимости возникают вовсе не в протоколе Диффи-Хеллмана, а в применении алгоритма Шора к математическими объектами, стоящим за классическими реализациями DH. Криптоанализ на квантовом компьютере позволяет быстро решать задачу дискретного логарифмирования в конкретном математическом окружении, но протокол Диффи-Хеллмана прекрасно обобщается на другие математические конструкции. Поэтому сразу несколько кандидатов в постквантовые криптосистемы используют DH (примеры: SIDH, CSIDH).

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

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

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