Рейтинг:3

Безопасно ли раскрывать произвольную точку EC, умноженную на секретный ключ?

флаг jp

У нас есть группа ЕС первого порядка. Необходимо выполнить (своего рода) протокол DH, тогда как ключ является постоянным, а не одноразовым (одноразовый эфемерный ключ).

Итак, мы получаем произвольный групповой элемент (точку ЕС) от недоверенной стороны и раскрываем его, умноженный на секретный ключ.

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

Maarten Bodewes avatar
флаг in
Я думаю, вы можете вывести это из того факта, что эфемерно-статический DH был бы крайне нарушен, если бы это было не так. Если я правильно помню, нет никакой другой проверки эфемерного открытого ключа, кроме того, что он находится на кривой.
флаг jp
@MaartenBodewes: обычно в DH у однорангового узла нет стимулов для извлечения вашего одноразового номера.
fgrieu avatar
флаг ng
@valdo: В вашем описании отсутствуют две важные детали: смогут ли злоумышленники выполнить много (скажем, $ 2 ^ {24} $) запросов? И будут ли это повторяющиеся запросы или нет? Это имеет значение, потому что $k$ итерированных запросов позволяют вычислить $(d^{k+1})\,G$, где $d$ — закрытый ключ, а $d\,G$ — известный открытый ключ, тогда как Предустановленные запросы $k\ge1$ позволяют вычислить $(d^2)\,G$, но не $(d^j)\,G$ для $j\ge3$ независимо от $k$. Самостоятельно: если бы результат DH (до функции вывода ключа) стал публичным, то противники в эфемерном DH оказались бы примерно в описанном вами положении.
флаг jp
@fgrieu: Да и Да. Таким образом, противник может легко вычислить `(d^n)G` для произвольной степени `n`. Что это меняет? Позволяет ли это злоумышленнику извлечь какую-либо информацию о ключе?
fgrieu avatar
флаг ng
@valdo: если $k$ делит $p-1$ и у противника есть $G, d\,G, (d^k)\,G$, то, согласно моему прочтению резюме _Security Analysis Чон Хи Чеона Сильная проблема Диффи-Хеллмана_ (в [материалах Eurocrypt 2006](https://doi.org/10.1007/11761679_1)), есть атака в $\sqrt k$ быстрее, чем Baby Step/Giant Step для восстановления $d$ . Как видно из резюме, атака требует непрактично большого объема памяти, как и BSGS, однако поиск коллизий решает эту проблему и позволяет распространять; так что это может стать практичным. Примечание. Я не должен получать признание за то, что пришел с этой идеей для этого вопроса.
флаг jp
@MaartenBodewes: да, но зависит от того, что вы подразумеваете под «сломанным». Основная цель AFAIK DH не в защите секретного ключа, а в выводе общего секрета с сотрудничающей стороной по общедоступному каналу связи, верно?
Maarten Bodewes avatar
флаг in
Можем ли мы использовать «(эфемерный/статический) закрытый ключ вместо «одноразовый номер» или «секретный ключ»? Эти термины путают воду. Пока мы на этом, результатом является действительно «общий секрет» или производный «секретный ключ». "s после использования KDF. Для *статического* DH, конечно, все о защите закрытых ключей. Если у вас есть закрытый ключ, вы также утечете общий секрет, например, поскольку следует учитывать открытые ключи (или точки открытых ключей). Если он также используется для аутентификации одной стороны — как это часто бывает в эфемерно-статическом DH — тогда утечка статического закрытого ключа разрушает эту подлинность.
флаг jp
@fgrieu: большое спасибо! Это отличный момент. Хорошо знать. Я считаю, что в моем конкретном случае это все еще хорошо. Практически противник может вызвать этот протокол несколько миллионов раз, возможно, даже миллиарды, но не триллионы. Мы говорим о порядке p 2 ^ 256. Таким образом, сложность атаки уменьшается примерно на 30/2 = 15 бит. от 128 бит до примерно 113 бит. Все еще достаточно хорошо для нашего конкретного случая.
fgrieu avatar
флаг ng
@valdo: вам будет интересна информация [там] (https://chat.stackexchange.com/transcript/message/59152377#59152377) (и в этом [связанном материале] (https://mailarchive.ietf.org /arch/msg/cfrg/YDVS5Trpr6suig_VCFEOH6SOn8Q/)). Я понимаю, что это в основном подтверждает то, что я подозревал выше, но я слишком далек от своей зоны комфорта, чтобы написать ответ.
Рейтинг:2
флаг kr

Если предположить, что под «первичным порядком» вы подразумеваете «первичный порядок», то это называется статической проблемой Диффи-Хеллмана, и против нее известны некоторые атаки. Основные из них, которые следует учитывать с макушки моей головы, это:

  • Чхон DLP с дополнительными входами атака: есть несколько вариантов, но, например, если основной порядок $р$ ваших эллиптических кривых удовлетворяет тому, что $д$ является делителем $p-1$, затем атакующий делает много запросы могут решить проблему дискретного журнала во времени $\widetilde{O}(\sqrt{p/d} + \sqrt{d})$, что в худшем случае $d = \Тета(p^{1/2})$ является $\widetilde{O}(p^{1/4})$. В принципе, это может быть довольно плохо, но есть разные причины, по которым атака не является чрезвычайно опасной в этой обстановке. Во-первых, из-за требований к памяти атаки и того факта, что большинство значений $р$ был бы довольно далек от худшего случая, его, вероятно, будет трудно смонтировать на практике в большинстве сценариев. Во-вторых, если $\альфа$ является секретным ключом, злоумышленнику необходимо как-то получить оба $\альфа G$ и $\alpha^dG$ за $G$ генератор группы, и единственный способ сделать это, похоже, $д$ последовательные адаптивные запросы $G \to \alphaG \to \alpha^2 G \to \cdots \to \alpha^d G$. Этого можно ожидать от оракула, и, поскольку это требует времени $ О (г) $, это снижает оптимальную $д$ к $\тета(р^{1/3})$ и увеличивает результирующую сложность до $\widetilde{O}(p^{1/3})$ (опять же при условии, что $p-1$ имеет требуемую форму). Не так много настроек, при которых оракул ответил бы $2^{85}$ запросов от противника. Вот почему атака Cheon обычно более актуальна в условиях, когда групповые элементы формы $\альфа^jG$ легко доступны в виде открытого ключа, а не получены с помощью последовательных запросов;

  • Грейнджер поле расширения атаковать, если вы используете кривые над полями расширения степени $\geq 3$ (что скорее всего не так).


Спасибо @fgrieu за правильное указание на то, что несколько комментариев, которые я сделал по этому поводу, были неверными, а также за указание на соответствующие обсуждения в списке рассылки IETF.

fgrieu avatar
флаг ng
Я не понимаю, почему атака Cheon, о которой вы упоминаете, не сработает в какой-то степени, когда в вопросе используются повторяющиеся запросы, а $p-1$ имеет умеренный простой множитель.
флаг jp
@fgrieu: в моем конкретном случае чрезмерное количество запросов не очень практично. Как я уже сказал, верхняя граница количества запросов порядка миллиона.
флаг jp
P.S. чтобы быть конкретным: у нас есть приложение, которое вызывает «плагин». Этот плагин не может иметь прямого доступа к ключу, но мы позволяем ему получить его образ (k*G). Недавно мы решили позволить ему получить (k*P), тогда как P — произвольный элемент группы. Время работы плагина ограничено (т.е. не может работать несколько дней). Пользователь может извлечь любую информацию в любом случае, если он / она хочет. Так что речь идет о защите пользователя от вредоносного плагина.
fgrieu avatar
флаг ng
@valdo: я понимаю. Хотя вы, возможно, только недавно видели [мой комментарий выше] (https://crypto.stackexchange.com/posts/comments/206590), он старый, предшествующий [этому, который вы сделали] (https://crypto.stackexchange .com/posts/comments/206603) с указанием количества запросов, которые может сделать злоумышленник.

Ответить или комментировать

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