Full domain hash (Full domain hash)

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

Введение

С момента открытия Уитфилдом Диффи (англ. Whitfield Diffie) и Мартином Хеллманом (англ. Martin Hellman) криптографии с открытым ключом одной из наиболее важных тем исследования является разработка практичных и доказуемо (в практическом понимание) безопасных криптосистем. Доказательством практичной безопасности обычно является вычислительная сложность от решения хорошо известной задачи до взлома криптосистемы. Хорошо известные задачи включают в себя факторизацию больших целых чисел, вычисление дискретного логарифма по модулю простого числа p или извлечение корня по модулю составного целого числа, на которой основана криптосистема RSA.

Очень распространённая практика для подписи с RSA — сначала хешировать сообщение, добавить к сообщению соль , а затем возвести в степень открытого ключа. Эта парадигма «хеширования и расшифровки»(hash and decrypt) является основой многочисленных стандартов, таких как PKCS # 1 v2.0. Схема состоит в том, чтобы взять хеш-функцию, выходной размер которой точно равен размеру модуля: это полнодоменная схема хеширования (FDH), введённая Белларом и Рогэвеем в статье "Random oracles are practical: a paradigm for designing efficient protocols". Схема FDH доказуемо безопасна в модели случайного оракула, предполагая, что инвертировать RSA, то есть извлечь корень по модулю составного целого числа, сложно. Методология случайного оракула была введена Белларом и Рогэвеем в "Random oracles are practical: a paradigm for designing efficient protocols", где они показывают, как разрабатывать надёжно защищённые схемы подписи из любой функции с потайным входом. В модели случайного оракула хеш-функция рассматривается как оракул, который выдаёт случайное значение для каждого нового запроса . В оригинальной статье случайный оракул преобразует последовательность из 0 и 1 фиксированной длины в последовательность бесконечной длины и случайным образом выбирает из последовательности подпоследовательность необходимой длины${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$. Основополагающая работа Беллара и Рогэвея подчёркивает, что для практического применения доказуемой безопасности важно учитывать «жёсткое» снижение безопасности. Снижение безопасности является «жёстким», когда любые действия криптоаналитика для взлома схемы подписи приводит к решению хорошо установленной задачи с достаточной вероятностью, в идеале с вероятностью, равной 1. В этом случае схема подписи почти так же безопасна, как и устоявшаяся задача. Напротив, если сокращение является «слабым», то есть вышеупомянутая вероятность слишком мала, гарантия на схему подписи может быть довольно слабой.

Определение

Схема подписи полного доменного хеша (Gen, Sign, Verify) определяется следующим образом. Алгоритм генерации ключей запускает RSA для получения $(N,e,d)$. Он выводит $(pk,sk)$, где $pk=(N,e)$ и $sk=(N,d)$. Алгоритм подписи и проверки имеет доступ к оракулу c хеш-функцией $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$

Подпись и проверка выполняются следующим образом:

${\textstyle {\begin{aligned}SignFDH_{N,d}(M)\\y\leftarrow H_{FDH}(M)\\return:y^{d}modN\\\\VerifyFDH_{N,e}(M,x)\\y\leftarrow x^{e}modN;\\y'\leftarrow H_{FDH}(M)\\if(y=y')then\\return:1\\else\\return:0\end{aligned}}}$

Анализ безопасности схемы FDH

Подход Беллара и Рогвея

Теорема 1 Предположим, что RSA $(t',\varepsilon ')$-безопасен (на взлом с вероятностью ɛ′ потребуется t′ времени ) Тогда схема FDH-подписи является $(t,\varepsilon )$ -безопасным, где

${\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\varepsilon &=(q_{\text{hash}}+q_{\text{sig}})*\varepsilon '\end{aligned}}$.

Недостатком данного результата является то, что $\varepsilon '$ может быть намного меньше $\varepsilon$. Например, если мы предположим, что криптоаналитик может запрашивать $q_{\text{sig}}=2^{30}$количество подписей и вычислять хеши на $q_{\text{hash}}=2^{60}$сообщениях , даже если вероятность инверсии RSA составляет всего $2^{-61}$, то все, что мы получаем, это что вероятность составляет почти $1/2$, что не является удовлетворительным. Чтобы получить приемлемый уровень безопасности, мы должны использовать больший размер модуля, который будет положительно влиять на эффективность схемы.

Чтобы получить наиболее подходящую границу безопасности, Беллар и Рогавей разработали новую схему — схему вероятностной подписи $(PSS)$, которая обеспечивает строгое снижение безопасности: вероятность подделки подписи практически также мала как и при инвертировании $RSA(\varepsilon =\varepsilon ')$. Вместо этого, существует альтернативный подход, который может быть применён по отношению к FDH схеме для получения лучшей границы.

Альтернативный подход

Иное сокращение, которое даёт лучшую оценку безопасности для FDH, основано на доказательстве теоремы

Теорема 2 Пусть RSA $(t',\epsilon ')$ — безопасен. Тогда схема FDH подписи является $(t,\epsilon )$ -безопасной, где

${\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\epsilon &={\frac {1}{\left(1-{\frac {1}{q_{\text{sig}}}}\right)^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}$.

Для больших $q_{\text{sig}}$, $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$.

Определение 1

Инвертором $I$ $(t,\epsilon )$ - будем называть алгоритм взламывающий RSA , вероятность успеха которого по истечении не более t времени обработки составляет не менее ɛ .

Определение 2

Фальсификатором $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ - будем называть алгоритм нарушающий схему подписи (Gen, Sign, Verify), если после не более чем $q_{\text{hash}}$запросов к хеш-оракулу, $q_{\text{sig}}$ подписанных запросов и $t$ времени обработки, выводит подделку подписи с вероятностью не менее ɛ .

Доказательство Пусть $F$ — фальсификатор $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ , который взламывает FDH. Мы предполагаем, что $F$ никогда не повторяет один и тот же запрос хеш-оракулу или запрос на подпись. Строим инвертор $I$ $(t',\epsilon ')$, который взламывает RSA. Инвертор $I$ получает в качестве входных данных $(N,e,y)$, где $(N,e)$ — открытый ключ, а $y$ выбирается случайным образом в $\mathbb {Z} _{N}$(подмножества всех хешированных сообщений) . Инвертор $I$ пытается найти $x=f^{-1}(y)$, где $f$ — функция RSA, определённая из $N,e$. Инвертор $I$ запускает $F$ для этого открытого ключа. Фальсификатор $F$ делает запросы к хеш-оракулу и запросы на подпись. $I$ получая ответ от хеш-оракула самостоятельно подписывает их.

Для простоты мы предполагаем, что когда $F$делает запрос на подпись сообщения $M$, он уже сделал соответствующий запрос хеш-оракулу для $M$. Если нет - продолжаем и самостоятельно создаём запрос хеш- оракулу для сообщения $M$.В инверторе $I$используется счётчик $i$, изначально установленный на ноль. Когда $F$ делает запрос хеш-оракулу для сообщения $M$, инвертор $I$ увеличивает $i$, устанавливает соответствие хешированного сообщения и изначального сообщения $M_{i}=M$, а также выбирает случайное число $r_{i}$ в $\mathbb {Z} _{N}$. $I$затем возвращает $h_{i}=r_{i}^{e}modN$ с вероятностью $p$ и $h_{i}=y*r_{i}^{e}modN$ с вероятностью $1-p$. Здесь $p$ — фиксированная вероятность, которая будет определена позже. Когда $F$ делает запрос на подпись для $M$, он уже запросил хеш $M$, так что $M=M_{i}$для некоторых $i$.Если $h_{i}={r_{i}}^{e}modN$, тогда $I$возвращает $r_{i}$ в качестве подписи. В противном случае, процесс останавливается и происходит сбой инвертора.

В конце концов, $F$ заканчивает работу и выводит подделку $(M,x)$. Мы предполагаем, что $F$ запрашивал хеш $M$ ранее. Если нет, $I$самостоятельно делает запрос хеш-оракулу, так что в любом случае $M=M_{i}$ для некоторого $i$. Тогда, если $h_{i}=y*{r_{i}}^{e}modN$, мы получаем,$x={h_{i}}^{d}=y^{d}*r_{i}modN$ и $I$ выводит $y^{d}={\frac {x}{r_{i}}}modN$ в качестве обратной величины для $y$. В противном случае процесс останавливается и происходит сбой инвертора.

Вероятность того, что мы ответим на все запросы сигнатур, составляет не менее $p^{q_{\text{sig}}}$. Затем $I$ выводит обратное $y$ для $f$ с вероятностью $1-p$. Таким образом, с вероятностью, по крайней мере, $\alpha (p)=p^{q_{\text{sig}}}*(1-p)$, $I$ выводит обратное $y$ для $f$. Функция $\alpha (p)$ максимальна для $p_{\text{max}}=1-1/(q_{\text{sig}}+1)$ и

$\alpha (p_{\text{max}})={\frac {1}{q_{\text{sig}}}}(1-{\frac {1}{1+q_{\text{sig}}}})^{1+q_{\text{sig}}}$

Следовательно, мы получаем:

${\begin{aligned}\epsilon (k)&={\frac {1}{\left(1-{\frac {1}{q_{\text{sig}}+1}}\right)^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}$.

Для больших $q_{\text{sig}}$,

$\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$.

Время работы $I$ — это время работы $F$, добавленное ко времени, необходимому для вычисления значений $h_{i}$. По сути, это одно вычисление RSA, которое является кубическим временем (или лучше). Это даёт формулу для $t$.

Итоговое сокращение

Качество нового сокращения не зависит от количества хеш-вызовов, выполненных фальсификатором, и зависит только от количества запросов на подписи. Это имеет практическое значение, поскольку в реальных приложениях число вызовов хеш-функции ограничено только вычислительной мощностью фальсификатора, тогда как количество запросов на подпись может быть ограничено: подписывающее лицо может отказаться подписывать более $2^{20}$ или $2^{30}$ сообщений. Тем не менее, сокращение по-прежнему не является жестким и остаётся значительный разрыв между точной безопасностью FDH и точной безопасностью PSS.

Во многих доказательствах безопасности в модели случайного оракула инвертор должен «угадать», какой хеш-запрос будет использоваться противником для подделки, что приводит к коэффициенту $q_{\text{hash}}$ в вероятности успеха. Доказано, что лучшим методом является включение запроса $y$ в ответ на многие хеш-запросы, чтобы подделка с большей вероятностью была полезна для инвертора. Это наблюдение также применимо к схеме подписи Рабина , схеме подписи Пейе, а также к схеме подписи Дженнаро-Галеви-Рабина , для которой коэффициент $q_{\text{hash}}$ в доказательстве безопасности случайного оракула также может быть уменьшен до $q_{sig}$.