mvladlin Jun 16 at 09:40

Особенность дискретного логарифма —> математический бэкдор в протоколе Диффи — Хеллмана

Easy

6 min

Mathematics*Cryptography*

Opinion

+13

Comments 29

vened Jun 16 at 10:17

Я не нашел в открытых источниках запрета на использование в качестве закрытого ключа (p-1)/2

В мультипликативном DH (FFDH) давно есть типовое требование: использовать для алгоритма циклическую подгруппу (простого) порядка (p-1)/2. Это то же самое. См., например, RFC 7919 (группы FFDH для TLS) или документы NIST 800.

mvladlin Jun 16 at 16:15

Спасибо, почитаю, не слишком ли глубоко спрятано "циклическую подгруппу (простого) порядка (p-1)/2 " и у меня в статье имеется ввиду классический DH

vened Jun 17 at 07:36

у меня в статье имеется ввиду классический DH

А в упомянутых документах - как раз тоже классический. FFDH (Finite Field DH) или "мультипликативный" - это и есть классический.

wataru Jun 16 at 10:18

Я правильно понимаю, что основная "новая не публичная информация" - это про то что задача обратного логарифма, оказывается, легко решается в для p-1 и p-2?

Я не нашел в открытых источниках запрета на использование в качестве закрытого ключа .

На практике p очень большое. Очень-очень большое. Сотни бит. И выбрать в качестве ключа именно (p-1)/2 - практически не возможно. Выбираются же закрытые ключи случайно для каждой сессии.

Кроме того, этот косяк давно известен и проверяется во всех криптографических системах. Например, openssh: https://github.com/openssh/openssh-portable/blob/master/dh.c#L260

Что касается p-2 - то этот случай тоже давно известен. Там открытый ключ окажется маленьким и маленькие открытые ключи тоже исключаются: https://github.com/openssh/openssh-portable/blob/master/dh.c#L275

mvladlin Jun 16 at 16:28

Спасибо, для математики не важно - большое или маленькое.

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

Что касается p-2 - то этот случай тоже давно известен. Там открытый ключ окажется маленьким

Сможете математически доказать?

wataru Jun 16 at 16:39

Сначала не то написал, сейчас подумаю.

Нет, оно не маленькое. Там получается публичный ключ g^(-1) = (p+1)/2.

Это какой-то очень частный случай. Так-то, действительно, можно руками найти логарифм для какого-нибудь (p-1)/2 и тоже его записывать в запрещенные.

Шанс что кому-то выпадет именно этот ключ - ничтожен.

seregablog Jun 16 at 15:00

Далее пойдет новая или непубличная информация

Информация далее не новая и известная

Я не нашел в открытых источниках запрета на использование в качестве закрытого ключа (p-1)/2.

Находится в гугле за минуту

Всю статью можно записать в одну строку: Если публичный ключ Алисы A = p-1, то её закрытый ключ a = (p-1)/2.

Это, конечно, верно. В плане атаки на ключ с таким же успехом можно рассчитать A42 = g^42 mod p, и когда публичный ключ Алисы совпадёт A = A42, сказать, что её закрытый ключ a = 42

mvladlin Jun 16 at 15:24

Находится в гугле за минуту

Ccылку пришлите где вы нашли запрет на использование в качестве закрытого ключа (p-1)/2 ?

seregablog Jun 16 at 15:34

https://crypto.stackexchange.com/questions/63569/in-the-diffie-hellman-key-exchange-why-is-a-value-of-a-fracp-12-a-bad-ch

mvladlin Jun 16 at 16:03

Спасибо, но это обсуждение с двумя минусовыми ответами, а не утверждение.

seregablog Jun 16 at 16:29

В этих "минусовых ответах" (в отличие от вашей статьи) доказано, что g^((p - 1) / 2) = p - 1 (mod p). Это лаконичнее и полезнее всех ваших таблиц-графиков-примеров

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

mvladlin Jun 16 at 16:40

Насчет (p-1)/2 точно не думаю - уж слишком "наверху" находится, смущает что не описано в какой-нибудь вики или открытой статье, чтобы быстро находилось.

Я думаю что и известен пример с (p-2) хотя спрятан дальше.

seregablog Jun 16 at 16:55

Утверждение о том, что g^(p-2) = g^(-1) известно, это простое следствие малой теоремы ферма, написано даже в википедии

Ключ p-2 "плохой" настолько же, насколько плох ключ 42 из моего примера выше

mvladlin Jun 17 at 08:14

Утверждение о том, что g^(p-2) = g^(-1) известно, это простое следствие малой теоремы ферма, написано даже в википедии

Да, и описана у меня в статье

seregablog Jun 17 at 11:01

А ещё у вас написано, что ключ p-2 плохой, что неверно

cpud47 Jun 16 at 23:12

Вам для понимания стоит сформулировать формально, что такое "уязвимость в криптосистеме DH". Тогда станет ясно, почему это не проблема.

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

$\lim_{n \to \infty} p(n) > 0$

В такой постановке, Ваши примеры не являются уязвимостями.

mvladlin Jun 17 at 08:17

Нет уязвимости в DH, есть (не уязвимость) а особенность DLOG.

А насчет вероятности стремящейся к 0 - Вы правы на 100%

cpud47 Jun 17 at 14:27

Я не очень понял, с чем Вы соглашаетесь, или что опровергаете :)

описанные уязвимости - математические

Прежде чем серьёзно говорить про "математические" уязвимости нужно строго (математически!) сформулировать, а что такое вообще уязвимость. А после этого математически доказать, что описанное в статье уязвимостями являются.

А статья будет полезна начинающим криптографам - к которым причисляю и себя

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

Потому что без определения, это просто махание руками, без какой либо математики. Так можно дойти и до того, что я объявлю функцию f(x), которая решает DLOG для заданной группы (просто предпосчитаю её например) - и у нас будет "математическая" уязвимость. И вот попробуйте мне доказать, что это не так? ;) (серьёзно - попробуйте опровергнуть этот тезис)

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

mvladlin Jun 18 at 09:11

Извините, просто некогда "воду в ступе толочь"

Imaginarium Jun 18 at 09:24

Хех. Вам предложили сделать из статьи что-то стоящее и даже указали как именно, чтобы статья обрела смысл и математическое содержание, потратили время на Вас и на объяснения Вам, а Вы отвечаете вот так))

Без предложенных корректировок как раз Ваша статья и является толчением воды в ступе)

MasterMentor Jun 17 at 07:40

Статья - норм! Нужно очень хорошо зубы на алгебраистике наточить, чтобы писать (и читать) такие статьи. :)

PS А был известен этот "баг" в математике DH либо нет, пофиг. :)

mvladlin Jun 17 at 08:18

Спасибо :)

mvladlin Jun 17 at 08:20

Наверное моя вина - в статье неправильно расставлены акценты.

У меня нет претензий к DH, описанные уязвимости - математические.

Они "пришли" в протокол DH вместе с дискретным логарифмом (DLOG).

Создатели DH всегда подчеркивали что зависят от DLOG.

И вообще протокол DH - прекрасная идея.

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

А статья будет полезна начинающим криптографам - к которым причисляю и себя.

VZ1 Jun 17 at 14:34

Остается только добавить, что золотое правило — не городить огород самому, а использовать уже существующие библиотеки, где такие бэкдоры уже предусмотрены. Например:

from cryptography.hazmat.primitives.asymmetric import dh

parameters = dh.generate_parameters(generator=2, key_size=2048)
private_key = parameters.generate_private_key()
public_key = private_key.public_key()

Эта библиотека автоматически избегает небезопасных значений ключей и поддерживает современные стандарты.

cpud47 Jun 17 at 16:39

Золотое правило - не использовать криптографические примитивы. Стоит сразу брать библиотеки высокого уровня с пуленепробиваемыми апи: всякие tls и sodium.

AES, DH, RSA и прочие - слишком тяжело использовать без ошибок.

lgorSL Jun 18 at 00:05

Имея ввиду экстраполяцию, можно предположить, что данная особенность распространяется на все множество таблиц степеней GF(p).

Так это же логично. Примерно как для обычных чисел у нас есть два корня из единицы (равные 1 и -1), а так же четыре корня четвёртой степени (-1, 1, i, -i), так и для вычетов простого числа так же, только вместо -1 там будет (p-1) и для четвёртой степени чуть сложнее.

Если внимательно посмотреть на таблицу степеней в gf(17), то в 8 колонке будут корни второй степени (которых ровно два и они 1 и 16), а в колонке 4 - корни четвёртой степени (1, 16, 4, 13)

А например в таблице степеней по модулю 19 можно корни третьей степени найти в колонках 6 и 12, их ровно три: 1, 7, 11

P. S. Ещё можно заметить что сумма всех корней степени n снова равна нулю, как и с комплексными числами.

P. P. S. а ещё можно в кольце вычетов по модулю простого числа найти подходящий корень из единицы и сделать преобразование Фурье на целых числах, примерно как с e(-ikw) на комплексных.

y_u_h Jun 18 at 05:35

Будем анализировать DLOG как таблицу степеней

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

mvladlin Jun 18 at 09:45

Дискретный логарифм (DLOG) по модулю $p \quad g^x \equiv a \pmod p$

Пример для GF(7) для примитива g = 3

$3^0 \equiv 1 \pmod 7$
$3^1 \equiv 3 \pmod 7$
$3^2 \equiv 2 \pmod 7$
$3^3 \equiv 6 \pmod 7$
$3^4 \equiv 4 \pmod 7$
$3^5 \equiv 5 \pmod 7$
$3^6 \equiv 1 \pmod 7$

Обычно для DLOG строят таблицу логарифмов, главный минус которой - можно построить только по одному .

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

таблица степеней слева, таблица логарифмов справа

По идее в таблицу степеней можно добавить колонку для x=0 но ее обычно опускают.

proleternal Jul 14 at 05:12

И никого не смутило, что в тривиальных случаях записан 0 и p-1 одновременно. То бишь два раза ноль. С тем же успехом можно дописать туда 2p-2 и 3p-3 и т.д. Только показатели степени — это значения по модулю p-1, то есть от 0 до p-2 включительно. По той же причине степень 0 НЕ опускают в подобной инфографике, в отличии как раз от p-1.