Full domain hash

In cryptography, Full Domaine Hash ( FDH or full domain hash ) is an RSA- based signature scheme that follows the hashing and signature paradigm. It is provably protected (that is, it did not succumb to the influence of adaptive attacks using selected messages) in the random oracle model. FDH involves hashing a message using a function whose image size is equal to the size of the RSA module, and then raising the result to the power of the RSA secret exponent.

Introduction

Since the discovery by Whitfield Diffie of Whitfield and Martin Hellman of public key cryptography ^[1], one of the most important research topics has been the development of practical and provable (in practical understanding) secure cryptosystems. Proof of practical security is usually computational complexity from solving a well-known problem to breaking a cryptosystem. Well-known tasks include factorization of large integers , computing a discrete logarithm modulo a prime number p, or extracting a root modulo a composite integer on which the RSA cryptosystem is based ^[2] .

A very common practice for signing with RSA is to hash the message first, add salt to the message, and then raise it to the public key level. This hash and decrypt paradigm is the foundation of numerous standards such as ^[3] . The scheme is to take a hash function whose output size is exactly equal to the size of the module: this is the full-domain hash scheme (FDH) introduced by and in the article "Random oracles are practical: a paradigm for designing efficient protocols " ^[4] . The FDH scheme is provably safe in the random oracle model, assuming that it is difficult to invert RSA , that is, extract the root modulo a composite integer. The random oracle methodology was introduced by Bellar and Rogaway in "Random oracles are practical: a paradigm for designing efficient protocols" ^[4] , where they show how to develop highly secure signature schemes from any secret input function . In the random oracle model, the hash function is considered as an oracle that produces a random value for each new request. In the original article, a random oracle converts a sequence of 0 and 1 of fixed length into a sequence of infinite length and randomly selects from the sequence a subsequence of the required length ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$ ${\ displaystyle {\ {0,1 \}} ^ {*} \ longrightarrow {\ {0,1 \}} ^ {\ infty}}$ ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$ . The fundamental work of Bellar and Rogaway emphasizes that for the practical application of provable security, it is important to take into account the “hard” decline in security. The security decrease is “tough” when any cryptanalyst's actions to crack the signature scheme lead to the solution of a well-established task with sufficient probability, ideally with a probability of 1. In this case, the signature scheme is almost as safe as the established task. On the contrary, if the reduction is “weak”, that is, the aforementioned probability is too small, the guarantee on the signature scheme may be rather weak.

Definition

The signature scheme of the full domain hash (Gen, Sign, Verify) is defined as follows. The key generation algorithm launches RSA to obtain $(N,e,d)$ ${\ displaystyle (N, e, d)}$ . He outputs $(pk,sk)$ ${\ displaystyle (pk, sk)}$ where $pk=(N,e)$ ${\ displaystyle pk = (N, e)}$ and $sk=(N,d)$ ${\ displaystyle sk = (N, d)}$ . Signature and verification algorithm has access to oracle with hash function $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$ ${\ displaystyle H_ {FDH}: {\ {0,1 \}} \ to {\ mathbb {Z} _ {N}}}$

Signature and verification are performed as follows:

{\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}}}

{\ 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 Schema Security Analysis

Bellar and Rogway Approach

Theorem 1 Assume that RSA $(t',\varepsilon ')$ ${\ displaystyle (t ', \ varepsilon')}$ -safe (hacking with probability ɛ ′ takes t ′ of time) Then the FDH signature scheme is $(t,\varepsilon )$ ${\ displaystyle (t, \ varepsilon)}$ -safe where

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

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

.

The disadvantage of this result is that $\varepsilon '$ ${\ displaystyle \ varepsilon '}$ could be much smaller $\varepsilon$ ${\ displaystyle \ varepsilon}$ . For example, if we assume that a cryptanalyst can request $q_{\text{sig}}=2^{30}$ ${\ displaystyle q _ {\ text {sig}} = 2 ^ {30}}$ number of signatures and calculate hashes on $q_{\text{hash}}=2^{60}$ ${\ displaystyle q _ {\ text {hash}} = 2 ^ {60}}$ messages, even if the probability of RSA inversion is only $2^{-61}$ ${\ displaystyle 2 ^ {- 61}}$ , then all we get is that the probability is almost $1/2$ ${\ displaystyle 1/2}$ that is not satisfactory. To obtain an acceptable level of security, we must use a larger module size, which will positively affect the efficiency of the circuit.

To get the most appropriate security margin, Bellar and Rogaway developed a new scheme - a probabilistic signature scheme. $(PSS)$ ${\ displaystyle (PSS)}$ , which provides a strict security reduction: the probability of a fake signature is almost as low as when inverting $RSA(\varepsilon =\varepsilon ')$ ${\ displaystyle RSA (\ varepsilon = \ varepsilon ')}$ . Instead, there is an alternative approach that can be applied to the FDH scheme to get a better border. ^[five]

Alternative Approach

Another abbreviation that provides the best safety rating for FDH is based on the proof of the theorem.

Theorem 2 Let RSA $(t',\epsilon ')$ ${\ displaystyle (t ', \ epsilon')}$ - safe. Then the FDH signature scheme is $(t,\epsilon )$ ${\ displaystyle (t, \ epsilon)}$ -safe where

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

For large $q_{\text{sig}}$ ${\ displaystyle q _ {\ text {sig}}}$ , $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$ ${\ displaystyle \ epsilon \ sim \ exp (1) \ cdot q _ {\ text {sig}} \ cdot \ epsilon '}$ .

Definition 1:

Inverter $I$ ${\ displaystyle I}$ $(t,\epsilon )$ ${\ displaystyle (t, \ epsilon)}$ - we will call the algorithm cracking RSA, the probability of success of which after no more than t processing time is at least ɛ.

Definition 2:

Counterfeiter $F$ ${\ displaystyle F}$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ ${\ displaystyle (t, q _ {\ text {sig}}, q _ {\ text {hash}}, \ epsilon)}$ - we will call the algorithm violating the signature scheme (Gen, Sign, Verify), if after no more than $q_{\text{hash}}$ ${\ displaystyle q _ {\ text {hash}}}$ requests to the hash oracle, $q_{\text{sig}}$ ${\ displaystyle q _ {\ text {sig}}}$ signed requests and $t$ ${\ displaystyle t}$ processing time, displays a fake signature with a probability of at least ɛ.

Proof let $F$ ${\ displaystyle F}$ - counterfeiter $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ ${\ displaystyle (t, q _ {\ text {sig}}, q _ {\ text {hash}}, \ epsilon)}$ that hacks FDH. We assume that $F$ ${\ displaystyle F}$ never repeats the same oracle hash request or signature request. Build an inverter $I$ ${\ displaystyle I}$ $(t',\epsilon ')$ ${\ displaystyle (t ', \ epsilon')}$ that hacks the RSA. Inverter $I$ ${\ displaystyle I}$ receives as input $(N,e,y)$ {\ displaystyle (N, e, y)} where $(N,e)$ ${\ displaystyle (N, e)}$ Is the public key, and $y$ ${\ displaystyle y}$ randomly selected in $\mathbb {Z} _{N}$ ${\ displaystyle \ mathbb {Z} _ {N}}$ (subsets of all hashed messages). Inverter $I$ ${\ displaystyle I}$ trying to find $x=f^{-1}(y)$ ${\ displaystyle x = f ^ {- 1} (y)}$ where $f$ ${\ displaystyle f}$ - RSA function defined from $N, e$ ${\ displaystyle N, e}$ . Inverter $I$ ${\ displaystyle I}$ starts up $F$ ${\ displaystyle F}$ for this public key. Forger $F$ ${\ displaystyle F}$ makes requests to the oracle hash and requests for signature. $I$ ${\ displaystyle I}$ receiving a response from the hash oracle independently signs them.

For simplicity, we assume that when $F$ ${\ displaystyle F}$ makes a request to sign a message $M$ ${\ displaystyle M}$ he has already made the corresponding request to the hash oracle for $M$ ${\ displaystyle M}$ . If not, continue and independently create a request to the hash oracle for the message $M$ ${\ displaystyle M}$ .In inverter $I$ ${\ displaystyle I}$ counter is used $i$ ${\ displaystyle i}$ initially set to zero. When $F$ ${\ displaystyle F}$ makes an oracle hash request for a message $M$ ${\ displaystyle M}$ inverter $I$ ${\ displaystyle I}$ increases $i$ ${\ displaystyle i}$ , matches the hashed message with the original message $M_{i}=M$ ${\ displaystyle M_ {i} = M}$ , and also selects a random number $r_{i}$ ${\ displaystyle r_ {i}}$ at $\mathbb {Z} _{N}$ ${\ displaystyle \ mathbb {Z} _ {N}}$ . $I$ ${\ displaystyle I}$ then returns $h_{i}=r_{i}^{e}modN$ ${\ displaystyle h_ {i} = r_ {i} ^ {e} modN}$ with probability $p$ ${\ displaystyle p}$ and $h_{i}=y*r_{i}^{e}modN$ ${\ displaystyle h_ {i} = y * r_ {i} ^ {e} modN}$ with probability $1-p$ ${\ displaystyle 1-p}$ . Here $p$ ${\ displaystyle p}$ - a fixed probability, which will be determined later. When $F$ ${\ displaystyle F}$ makes a request for a signature for $M$ ${\ displaystyle M}$ he already requested a hash $M$ ${\ displaystyle M}$ , so that $M=M_{i}$ ${\ displaystyle M = M_ {i}}$ for some $i$ ${\ displaystyle i}$ .If a $h_{i}={r_{i}}^{e}modN$ ${\ displaystyle h_ {i} = {r_ {i}} ^ {e} modN}$ then $I$ ${\ displaystyle I}$ returns $r_{i}$ ${\ displaystyle r_ {i}}$ as a signature. Otherwise, the process stops and the inverter fails.

Finally, $F$ ${\ displaystyle F}$ finishes work and displays a fake $(M,x)$ ${\ displaystyle (M, x)}$ . We assume that $F$ ${\ displaystyle F}$ requested a hash $M$ ${\ displaystyle M}$ earlier. If not, $I$ ${\ displaystyle I}$ independently makes a hash oracle request, so anyway $M=M_{i}$ ${\ displaystyle M = M_ {i}}$ for some $i$ ${\ displaystyle i}$ . Then if $h_{i}=y*{r_{i}}^{e}modN$ ${\ displaystyle h_ {i} = y * {r_ {i}} ^ {e} modN}$ , we get, $x={h_{i}}^{d}=y^{d}*r_{i}modN$ ${\ displaystyle x = {h_ {i}} ^ {d} = y ^ {d} * r_ {i} modN}$ and $I$ ${\ displaystyle I}$ displays $y^{d}={\frac {x}{r_{i}}}modN$ ${\ displaystyle y ^ {d} = {\ frac {x} {r_ {i}}} modN}$ as the reciprocal of $y$ ${\ displaystyle y}$ . Otherwise, the process stops and the inverter fails.

The probability that we will respond to all signature requests is at least $p^{q_{\text{sig}}}$ ${\ displaystyle p ^ {q _ {\ text {sig}}}}$ . Then $I$ ${\ displaystyle I}$ deduces the opposite $y$ ${\ displaystyle y}$ for $f$ ${\ displaystyle f}$ with probability $1-p$ ${\ displaystyle 1-p}$ . Thus, with a probability of at least $\alpha (p)=p^{q_{\text{sig}}}*(1-p)$ ${\ displaystyle \ alpha (p) = p ^ {q _ {\ text {sig}}} * (1-p)}$ , $I$ ${\ displaystyle I}$ deduces the opposite $y$ ${\ displaystyle y}$ for $f$ ${\ displaystyle f}$ . Function $\alpha (p)$ ${\ displaystyle \ alpha (p)}$ maximum for $p_{\text{max}}=1-1/(q_{\text{sig}}+1)$ ${\ displaystyle p _ {\ text {max}} = 1-1 / (q _ {\ text {sig}} + 1)}$ and

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

{\ displaystyle \ alpha (p _ {\ text {max}}) = {\ frac {1} {q _ {\ text {sig}}}} (1 - {\ frac {1} {1 + q _ {\ text { sig}}}}) ^ {1 + q _ {\ text {sig}}}}

Therefore, we get:

{\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 {\ 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}}}

.

For large $q_{\text{sig}}$ ${\ displaystyle q _ {\ text {sig}}}$ ,

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

Working hours $I$ ${\ displaystyle I}$ Is work time $F$ ${\ displaystyle F}$ added to the time needed to calculate the values $h_{i}$ ${\ displaystyle h_ {i}}$ . Essentially, this is one RSA calculation that is cubic time (or better). This gives the formula for $t$ ${\ displaystyle t}$ .

Final reduction

The quality of the new reduction does not depend on the number of hash calls made by the falsifier, and depends only on the number of requests for signatures. This is of practical importance, since in real applications the number of hash function calls is limited only by the forger’s processing power, while the number of signature requests may be limited: the signer may refuse to sign more $2^{20}$ ${\ displaystyle 2 ^ {20}}$ or $2^{30}$ ${\ displaystyle 2 ^ {30}}$ messages. However, the reduction is still not tough and there is a significant gap between the exact security of FDH and the exact security of PSS .

In many security proofs in the random oracle model, the inverter must “guess” which hash request the adversary will use to fake, resulting in a coefficient $q_{\text{hash}}$ ${\ displaystyle q _ {\ text {hash}}}$ in the likelihood of success. It is proven that the best method is to include a query $y$ ${\ displaystyle y}$ in response to many hash requests, so that a fake is more likely to be useful for the inverter. This observation also applies to the signature scheme of Rabin ^[6] , the signature scheme of Peyet ^[7] , as well as the signature scheme of Gennaro-Halevi-Rabin ^[8] , for which the coefficient $q_{\text{hash}}$ ${\ displaystyle q _ {\ text {hash}}}$ in evidence of the safety of an accidental oracle can also be reduced to $q_{sig}$ ${\ displaystyle q_ {sig}}$ .

Notes

↑ New directions in cryptography (neopr.) .
↑ A method for obtaining digital signatures and public key cryptosystems (neopr.) .
↑ RSA cryptography specifications (neopr.) .
↑ ¹ ² Random oracles are practical: a paradigm for designing efficient protocols (neopr.) .
↑ The exact security of digital signatures - How to sign with RSA and Rabin (neopr.) .
↑ Digitalized signatures and public-key functions as intractable as factorization ( unspecified ) .
↑ Public-key crypto systems based on composite degree residuosity classes. Proceedings of Eurocrypt'99 (neopr.) .
↑ Secure hash-and-sign signatures without the ran- dom oracle, proceedings of Eurocrypt'99 (unspecified) .

[1] New directions in cryptography (neopr.) .

[2] A method for obtaining digital signatures and public key cryptosystems (neopr.) .

[3] RSA cryptography specifications (neopr.) .

[:4-4] ¹ ² Random oracles are practical: a paradigm for designing efficient protocols (neopr.) .

[5] The exact security of digital signatures - How to sign with RSA and Rabin (neopr.) .

[6] Digitalized signatures and public-key functions as intractable as factorization ( unspecified ) .

[7] Public-key crypto systems based on composite degree residuosity classes. Proceedings of Eurocrypt'99 (neopr.) .

[8] Secure hash-and-sign signatures without the ran- dom oracle, proceedings of Eurocrypt'99 (unspecified) .