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

Посмотрим на классический вариант DH: s = Gab == Gba (mod P), а именно – мы выбрали некоторое большое простое число P, выбрали натуральное G < P (это значение называют генератором), а в рамках операций протокола возводим G в секретную степень a или b по модулю P. Другими словами – вычисляем остаток от деления на P. Из привычного свойства степеней выводится нужное равенство, означающее, что стороны придут к одинаковому значению секрета s. Уже при разборе классического варианта можно обнаружить первое важнейшее общее свойство, о котором нередко забывают.

Действительно, стороны обмениваются значениями Ga и Gb по открытому каналу, соответственно, атакующему нужно вычислить a или b, по известному значению Ga или Gb. Почему же атакующий не может просто последовательно возводить G в натуральные степени, чтобы на каком-то шаге получить Ga (или Gb, но для примера возьмём только a), определив, таким образом, секретное значение? Ответ на этот вопрос такой: будем выбирать значение a достаточно большим, чтобы полный прямой перебор оказался вычислительно недоступным. Например, последовательно перебрать уже 2128 значений, для нашей задачи, весьма и весьма затруднительно. (Техническая оговорка: классический протокол DH на практике использует значения гораздо большей разрядности – 4096 бит и больше; это связано с особенностями криптоанализа именно классического DH, и не должно нас смущать: 4096 бит, после применения некоторых оптимизаций, как раз превращаются, примерно, в 196 “честных” битов.) Итак, атакующий не может перебрать все показатели степени последовательно, потому что это очень долго. Но как же тогда быть сторонам, использующим DH, они же тоже возводят G в степень большой разрядности? Это и есть первое арифметическое свойство, необходимое для успешного обобщения DH.

Так как каждая сторона протокола знает своё секретное значение, она может воспользоваться тем, что, например, 16 == (22)2. То есть, вместо трёх умножений – ограничиться всего двумя: (2*2)*(2*2). Очевидно, что один раз вычислив 4 == 2*2, можно использовать 4 дальше. Зная нужное значение показателя, процесс вычисления нетрудно разбить на повторное “удвоение” (здесь – в смысле степени, но это весьма важный и более общий термин) и умножение на основание: 35 == 32*32*3 == 243. Существенная экономия вычислительных ресурсов, которая выводится из того, что умножение в целых числах не зависит от расстановки скобок: a×a×a×a×a == (a×a)×(a×a×a) == a×(a×a×a×a). Вместо того, чтобы 128 раз умножать 3 на 3, вычисляя 3129, можно поступить проще: 3129 == 3128*3 == (364)2*3 и т.д., рекурсивно. Всё это может показаться очевидным для целых чисел, особенно, если учесть тот факт, что описанный метод естественным образом отображается на двоичное представление, привычное для компьютерных вычислений. Однако при обобщении протокола DH данное свойство трансформируется: необходимо, чтобы арифметические операции в новой структуре позволяли выполнять “быстрое удвоение”. “Быстрое” – в смысле количества вычислительных операций.

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

Итак, следующая особенность DH – это протокол достаточно высокого уровня, чтобы его можно было переносить на другие структуры, с подходящей арифметикой. Обычно – на группы. Естественным препятствием здесь является наличие сложности решения обратной задачи. Если у нас есть функция DH с параметром, отображающая элемент новой структуры в другой элемент, задаваемый параметром, то эту функцию должно быть сложно обратить. В случае классического варианта протокола, скажем, что параметр – это показатель степени, а функция может быть представлена как S = Gx. Тогда обратная задача – это задача дискретного логарифмирования: нужно отыскать x, по известным G и S. Для эллиптической кривой обратная задача, обеспечивающая возможность переноса обобщённого DH, это задача вычисления показателя кратности (скаляра) x по двум известным точкам: S = xG. Например, в случае суперсингулярных (не будем вдаваться в технические подробности) эллиптических кривых протокол ECDH может оказаться уязвимым, поскольку существуют практические методы быстрого решения задачи дискретного логарифмирования для некоторых из этих кривых (методы эти позволяют свести задачу к вычетам, то есть, к области классического DH, но это детали). Как ни странно, это совсем не означает, что суперсингулярные эллиптические кривые не годятся для реализации DH.

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



Комментировать »

Немного занимательных математических основ криптографии.

Российская криптосистема электронной подписи (ГОСТ 34.10-2012) работает в группе точек эллиптической кривой над конечным полем, как и криптосистема ECDSA, широко используемая в TLS и в других протоколах защиты информации. Можно ли устроить так, чтобы открытый и секретный ключи для ГОСТ-подписи и ECDSA – совпадали? Дело в том, что если ключи одинаковые, то это добавляет удобства: например, можно использовать некие унифицированные сертификаты. Естественно, это чисто теоретической вопрос, но он довольно занятный. Если вынести за скобки криптографические параметры и способ интерпретации битовых строк, то главное отличие между ГОСТ-подписью и ECDSA состоит в уравнениях, используемых этими криптосистемами. Упростим ситуацию и рассмотрим лишь уравнения вычисления значения подписи:

ECDSA: s = k^(-1)(h + rd)

ГОСТ: s = (rd + kh)

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

Итак, сразу видно, что секретные ключи d для обоих вариантов математически эквивалентны, так как секретный ключ – это натуральное число. Это так и есть на практике, с оговоркой, что значение секретного ключа должно лежать в некотором интервале, но это технические детали. На практике, вряд ли имеет смысл использовать небольшое значение d, которое может оказаться угадываемым. То есть и для ГОСТ-подписи, и для ECDSA в качестве секретного ключа можно использовать одно и то же значение. Если оно находится в подходящем интервале, то в работе алгоритмов, реализующих криптосистемы, равным счётом ничего не поменяется.

Как быть с соответствующими открытыми ключами? С открытыми – уже не так просто. Открытый ключ в обоих криптосистемах – это точка кривой, полученная в результате “умножения” точки-генератора G на число d (значение секретного ключа): открытый ключ Q == dG. “Умножение” здесь взято в кавычки по той причине, что для точек кривой никакого умножения не определяется, но есть “повторное сложение” точек: так, 3*A == A + A + A, где A – точка кривой. Повторное сложение и позволяет ввести умножение на скаляры (на целые числа). Итак, открытый ключ – точка кривой Q – это пара координат (x, y). Значения координат, x и y, – элементы поля, над которым рассматривается кривая. Именно здесь и кроется отличие: штатно, обсуждаемые криптосистемы используют разные кривые и разные поля, поэтому полученные значения открытого ключа будут различными, если, конечно, мы хотим сохранить корректность прочих операций (а корректность сохранить необходимо).

Таким образом, из-за использования разных криптографических параметров (уравнения кривой, базового поля, точки-генератора), для одного и того же значения секретного ключа значения открытых ключей, вообще говоря, в ECDSA и ГОСТ-подписи не совпадут. Однако, если использовать одно и то же поле, одну и ту же кривую и генератор, то и значения открытых ключей будут равны, поскольку и в одной, и в другой криптосистеме – открытый ключ Q == dG. Обе криптосистемы могут работать на общей кривой – математические операции не отличаются. Понятно, что так как уравнения подписи разные, то подписи для одного и того же значения не будут совпадать, даже если ключи удалось привести к “единому формату”. (Естественно, подписи для сообщений могут отличаться и из-за использования разных хеш-функций.) Однако все операции (вычисление подписи, проверка) останутся корректными и для ECDSA, и для ГОСТ-подписи. Поэтому использовать, буквально, одну и ту же пару ключей (секретный – для вычисления подписи, а открытый – для проверки) уже окажется возможным.

Конечно, так как практические криптосистемы включают в свой состав не только математические операции, но и конкретные значения параметров, подобное объединение ключей вряд ли реализуемо за пределами занимательного упражнения.



Комментировать »

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

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

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

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



Комментарии (2) »

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

Эллиптическая кривая над конечным полем.

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

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

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

Кривая над полем из 101 элемента.

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

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



Комментировать »

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

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

Выберем уравнение, задающее эллиптическую кривую E:
y2 = x3 + 2020x2 + x.
Это уравнение в форме Монтгомери, общий вид таких уравнений:
y2 = x3 + Ax2 + x, где A – элемент базового поля; в нашем примере A == 2020.

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

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

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

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

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

Кривая E

Введём умножение на скаляр: 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) – называется задачей дискретного логарифмирования в конечной группе и, для произвольных групп точек эллиптической кривой достаточно большого порядка, вычислительно трудна. На практике используются параметры с порядками, близкими к 2256 (и более). Методов, позволяющих даже на специализированном суперкомпьютере за разумное время решить задачу дискретного логарифмирования для произвольных параметров и групп таких порядков – пока не найдено. Однако для некоторых специальных случаев – методы известны. Некоторые из этих методов элементарны, как будет видно из примера ниже.

Попробуем теперь взломать нашу “криптосистему” 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 на практике – нужно только аккуратно выбирать кривую, поле и генератор: если порядок генератора является достаточно большим простым числом, то данная конкретная атака уже не работает. Поиск безопасной кривой, подходящей для практического применения, представляет собой задачу гораздо более сложную, чем наш “игрушечный” пример.



Комментировать »

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

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

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

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

Например, когда говорят о задаче криптографии с открытым ключом, речь идёт об алгоритме Шора. Квантовая часть этого алгоритма позволяет найти значение (период известной функции), знание которого делает возможным быстрое вычисление разложения заданного числа на множители уже на классическом компьютере. Искомый период функции здесь и есть отражение структуры, соответствующей разложению на множители. Собственно, разложение на множители актуально для криптосистемы 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).

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



Комментировать »

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

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

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

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

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

Итак, какими свойствами и механизмами должен обладать скрытый протокол в таких (весьма жёстких) условиях?

1.

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

2.

Для сокрытия трафика необходимо использовать стеганографию. В принятой модели угроз, если один из узлов просто передаёт зашифрованное сообщение вне прочих сеансов, то этот факт тут же оказывается обнаружен. Стеганографический канал маскирует сеанс обмена сообщениями под трафик другого типа. Это означает, что протокол не может прямо использовать привычные виды транспорта, а должен подразумевать наличие дополнительного трафика. Простой пример: сообщения могут быть скрыты внутри текстов веб-страниц и веб-форм, в качестве базового трафика используется имитация работы с веб-сайтом. В данном случае, веб-трафик может передаваться по TCP или UDP, с использованием TLS/HTTPS или QUIC, экзотические варианты вместо веб-трафика используют непосредственно TLS, или даже служебные заголовки IP-пакетов и DNS, всё это не так важно для стеганографии. Важны достаточный объём данных и наличие симметричных ключей, позволяющих организовать стойкий стеганографический канал. При наличии ключей – такой канал организовать всегда можно. (Ключи используются для задания псевдослучайной последовательности, которая необходима для работы механизма встраивания скрытых данных в поток трафика.)

3.

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

4.

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

5.

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

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



Комментарии (1) »

Подробное описание того, как работает (на практике) технология ESNI (зашифрованное поле SNI TLS), в текущей draft-версии. В качестве примера я использую тестовый сервер tls13.1d.pw, где ESNI поддерживается (а поддерживающий браузер – это Firefox свежих версий, но ESNI там нужно включить, вместе с DNS-over-HTTPS).

Введение

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

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

Логика работы следующая: браузер получает из DNS открытый ключ DH (протокола Диффи-Хеллмана), генерирует сеансовый симметричный ключ, зашифровывает имя сервера и некоторое уникальное значение, которые, вместе со своим открытым ключом DH, передаёт серверу в расширении ESNI ClientHello. (Я описывал этот процесс в отдельной записке.)

Часть DNS

Сейчас в качестве DNS-записи используется запись типа TXT. Возможно, в дальнейшем для ESNI выделят новый тип записи.

Структура записей, размещаемых в DNS, следующая (в нотации языка Go):

type KeyShare struct {
Group uint16
Key []byte
}
type ESNIKeys struct {
Version uint16
Checksum [4]byte
Keys []KeyShare
Ciphers []uint16
PaddedLength uint16
NotBefore uint64
NotAfter uint64
Extensions []byte
}

Данные кодируются в Base64 и публикуются в TXT-записи под именем, содержащим префикс _esni. Для tls13.1d.pw это _esni.tls13.1d.pw. Сейчас для tls13.1d.pw опубликована ESNI-запись с двумя ключами (X25519 и P-384).

Подробные описания полей:

Version

длина: два байта; значение: 0xFF01 (действующая версия, draft).

Checksum

длина: четыре байта; это контрольная сумма – первые четыре байта значения SHA-256 от всех данны структуры ESNI (для вычисления контрольной суммы поле Checksum во входных данных заполняется нулями).

Keys

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

Рассмотрим список ключей для ESNI-записи _esni.tls13.1d.pw (здесь используется два ключа – X25519, P-384):

длина списка: 0x0089;

тип первой криптосистемы (X25519): 0x001D;
длина записи ключа (32 байта): 0x0020;
значение ключа: […] /32 байта, в криптосистеме X25519 – ключи записываются 32-байтовыми последовательностями/;

тип второй криптосистемы (P-384): 0x0018;
длина записи ключа (97 байтов): 0x0061;
значение ключа (97 байтов): 0x04[…] /ключ является точкой на кривой, записываются координаты точки, первый байт обозначает тип представления (04 – несжатое), далее – две координаты по 48 байтов: 48 + 48 +1 = 97; 48 байтов – соответствуют разрядности криптосистемы).

Ciphers

это тоже список, длина зависит от количества поддерживаемых шифров. Для tls13.1d.pw используется один шифр:

длина списка: 0x0002 (два байта – идентификатор шифра);
идентификатор шифра (AES_128_GCM): 0x1301.

PaddedLength

два байта, поле содержит максимальную длину записи списка имён в ESNI, значение, которое поддерживает сервер tls13.1d.pw: 0x0080.

NotBefore, NotAfter

всем привычные таймстемпы по восемь байтов. Интервал валидности записи.

Extensions

расширения ESNI. Они пока не определены спецификацией. Поле является списком, соответственно, пустой список представляется двумя нулевыми байтами (список, имеющий длину нуль): 0x0000.

Часть TLS

Обработка ESNI TLS-сервером, который действует на tls13.1d.pw, проводится при получении ClientHello. Это сообщение содержит список расширений, для каждого расширения указывается тип (подробнее про то, как работает TLS можно почитать в техническом описании протокола). Тип расширения ESNI – 0xFFCE (это Draft-версия!). Внутренняя логика обработки: расширения передаются в виде списка TLS-структур, длина списка задаётся первыми байтами, далее идут типы расширений и соответствующие им поля данных, каждое поле начинается байтами, содержащими длину.

Например, вот тип, описывающий клиентское расширение ESNI (представление внутри сервера):

type TLS_ESNI struct{
Cipher uint16
Group uint16
KeyShare []byte
Digest []byte
Data []byte
}

Клиент передаёт в ESNI идентификатор шифра (Cipher), тип криптосистемы (Group) и свой ключ DH (KeyShare), а также контрольную сумму (Digest) и, собственно, полезные данные (Data) – nonce и зашифрованное имя сервера. Значение nonce (16 байтов) – это то самое значение, которое сервер должен передать в ответном ESNI-расширении.

При разборе полей KeyShare, Digest, Data – используется обычный для TLS подход: первые два байта интерпретируются как длина записи, далее, в зависимости от типа, аналогичным способом разбираются поля данных.

Конкретно в моём тестовом сервере обнаружение и обработка ESNI устроены так: на первом шаге читаются поступившие TLS-записи, делается попытка разобрать их по TLS-сообщениями и построить список таких сообщений, если попытка удалась, то в списке выполняется поиск ClientHello; если удалось найти ClientHello, то для него вызывается парсер, который разбирает сообщение, выделяя “голову” и список расширений (здесь речь про все расширения, не только про ESNI); на втором шаге – делается попытка в списке расширений ClientHello найти расширения, необходимые для сессии TLS 1.3 (SupportedVersions и др.), это позволяет распознать нужную версию протокола; если минимальный набор расширений найден, то делается попытка обнаружить расширение ESNI. И, соответственно, если расширение обнаружено, то оно передаётся парсеру ESNI, который разбирает его по полям. Далее, используя секретный ключ для ESNI, сервер, выполняя алгоритм DH, вычисляет симметричный ключ и пытается расшифровать данные (поле Data). Если расшифрование завершилось успешно, то заполняется структура с данными из ESNI и генерируется ответное серверное расширение. (Отмечу, что это логика работы, подходящая именно для тестового сервера.)

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

Успешно расшифрованное имя из ESNI используется сервером, собственно, оно просто позже выводится на страницу результатов. Расшифрованное значение nonce – сервер записывает в ответное ESNI-сообщение. На этом обработка ESNI заканчивается. Если же расширение ESNI не обнаружено, то сервер продолжает обрабатывать соединение по обычной схеме. Все сообщения можно посмотреть на веб-странице, которую выводит сервер.

Да, кстати, из недавно добавленных улучшений на tls13.1d.pw: сейчас там выводятся симметричный ключ и вектор инициализации ESNI.



Comments Off on Техническое: разбор реализации ESNI

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

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

Сходную схему можно построить и на уровне TLS (но, опять же, применительно к веб-узлу). Например, так (ниже – копия моего текста, который я некоторое время назад публиковал в Facebook).

Используем TLS, поверх которого работает HTTPS на некотором сервере: то есть, это 443/tcp и всё должно выглядеть как веб-сервер для внешнего сканера. Для упрощения, считаем, что у нас TLS 1.3, вообще, это не так важно, но 1.3 подходит лучше.

В TLS, при установлении соединения, передаются специальные сообщения. В них есть разные поля, мы будем использовать те, которые предназначены для отправки (псевдо)случайных данных – клиентская пара: ClientRandom и SessionID, серверная – ServerRandom и SessionID (значение не изменяется). Оба поля, в общем случае, содержат 32 байта данных (там есть всякие ограничения, но мы будем считать, что их нет). Цель – получить наложенный протокол, который активируется внутри TLS-трафика и только при наличии некоторых ключей, а в прочих случаях – неотличим от HTTPS/TLS. Механизм следующий.

Конфигурация: сервер, реализующий веб-узел – показывает произвольный сайт, например, трансляции новостей; клиент, планирующий использовать скрытый сервис (прокси), подключается к серверу по 443/tcp через TLS.

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

Клиент, устанавливая TLS-соединение, использует серверный ключ Pk (он должен быть известен заранее – это важно) для получения общего секрета протокола Диффи-Хеллмана (DH), вычисленную открытую часть DH клиент отправляет в поле ClientRandom, а на основе полученного секрета – генерирует сеансовый симметричный ключ (Tk) и зашифровывает свой идентификатор, который, в зашифрованном виде, записывает в поле SessionID.

Получив TLS-сообщение, сервер вычисляет секрет DH (из ClientRandom), на его основе получает симметричный ключ и расшифровывает идентификатор из SessionID. На данном этапе сервер просто запоминает полученные значения: так как возможны атаки с повтором, сервер продолжает обработку TLS-соединения, запомнив полученные ключи и идентификатор. Очевидно, что это могут быть и не ключи вовсе. В ответном TLS-сообщении – сервер отправляет свою часть DH (от другого ключа) в ServerRandom (SessionID сервер использовать не может, потому что, согласно спецификации TLS, должен передать в ответ то же значение, которое получил от клиента).

К этому моменту, клиент уже может перейти на защищённый обмен сообщениями на уровне TLS (согласно спецификации). Клиент аутентифицирует сервер средствами TLS. Если аутентификация прошла успешно, то клиент переходит к следующему шагу получения доступа к скрытому сервису (если нет, то клиент просто закрывает TLS-сессию). На основе ответа сервера, клиент вычисляет вторую итерацию DH (это DH для скрытого сервиса) – получает второй общий секрет DH_2, используя ServerRandom, и второй открытый параметр DH_s, который нужно передать серверу (см. ниже). Итак, клиент, на настоящий момент, аутентифицировал сервер и получил следующие (дополнительные) криптографические параметры: общий секрет DH_2, сеансовый симметричный ключ Tk, общий с сервером симметричный ключ Ck. На основе этих значений, используя ту или иную хеш-функцию (например, SHA-256), клиент генерирует секретный тег (256-битное значение). Клиент соединяет это значение с параметром DH_s и записывает в начало полезной нагрузки первого TLS-сообщения, это, условно говоря, magic number. Полезная нагрузка передаётся в зашифрованном виде, поэтому третья сторона тег (magic number) – не видит.

Сервер, получив TLS-сообщение, расшифровывает его штатным образом, интерпретирует начальные данные как тег, выделяет DH_s, вычисляет общий секрет DH_2, генерирует ключи (секретный ключ Ck, соответствующий клиенту, сервер определил ранее – теперь этот ключ пригодился), вычисляет значение хеш-функции и сравнивает результат с тегом. Если значения совпали, то сервер считает, что осуществляется доступ к скрытому сервису и начинает проксировать полезные данные TLS в сторону этого сервиса (там уже есть своя аутентификация и пр.) Если тег не совпал, то сервер вспоминает, что он является веб-сервером с HTTPS и отвечает обычной (подходящей) HTTP-ошибкой, так как подставной тег выглядит как неверный HTTP-запрос.

Посмотрим, что видит третья сторона, пассивно просматривающая трафик: третья сторона видит, что установлено TLS-соединение на 443/tcp (HTTPS) и узлы обмениваются информацией по TLS, внутрь заглянуть нельзя, так что проксируемый трафик не виден. Так как, при правильно выбранной криптосистеме, значения ClientRandom, ServerRandom и SessionID вычислительно неотличимы от случайных (но при этом реально являются параметрами DH и зашифрованным идентификатором), то никаких подозрений, сами по себе, вызвать не могут.

Что видит активная третья сторона, проводящая сканирование узлов? Такой сканер не знает клиентских ключей, поэтому, даже попытка имитировать доступ к скрытому сервису, путём записи произвольных значений в поля TLS-заголовков и в данные сессии – будет приводить к ошибке HTTP (либо к ошибке TLS). Понятно, что обычное HTTPS-сканирование показывает, что там какой-то веб-сайт. Таким образом, узел, реализующий скрытый сервис, неотличим от обычного веб-узла с HTTPS. Более того, если сканеру известна часть ключей, например, открытый ключ сервера Pk, то сканер всё равно не сможет сгенерировать корректный тег, так как должен для этого знать ещё и валидный клиентский ключ. До момента появления корректного тега сервер ведёт себя в точности как HTTPS-узел, поэтому, опять же, не отличается от обычного сайта.

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

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



Комментарии (1) »
Навигация по запискам: Раньше »