Full domain hash

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

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

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

Схема подписи полного доменного хеша (Gen, Sign, Verify) определяется следующим образом. Алгоритм генерации ключей запускает RSA для получения ${\displaystyle (N,e,d)}$. Он выводит ${\displaystyle (pk,sk)}$, где ${\displaystyle pk=(N,e)}$ и ${\displaystyle sk=(N,d)}$. Алгоритм подписи и проверки имеет доступ к оракулу c хеш-функцией ${\displaystyle 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}}}$

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

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

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

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

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

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

${\displaystyle {\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}}}$.

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$.

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

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

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

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

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