| 1 | \xcalways\section{Digital signatures}\x |
| 2 | |
| 3 | \xcalways\subsection{Definitions and security notions}\x |
| 4 | |
| 5 | \begin{slide} |
| 6 | \topic{syntax} |
| 7 | \head{Syntax of digital signature schemes} |
| 8 | |
| 9 | A \emph{digital signature scheme} is a triple $\mathcal{S} = (G, S, V)$ of |
| 10 | algorithms: |
| 11 | \begin{itemize} |
| 12 | \item The \emph{key-generation} algorithm $G$ is a probabilistic algorithm |
| 13 | which, given no arguments (or a security parameter $1^k$ represented in |
| 14 | unary, in the asymptotic setting) returns a pair $(P, K)$ of public and |
| 15 | private values. |
| 16 | \item The \emph{signing} algorithm $S$ is a probabilistic algorithm. |
| 17 | If $(P, K) \in G$, and $m \in \{0, 1\}^*$ is some message, then $S(K, m)$ |
| 18 | (usually written $S_K(m)$) returns a \emph{signature} $\sigma$ on $m$. |
| 19 | \item The \emph{verification} algorithm $V$ is a deterministic algorithm |
| 20 | returning a single bit. If $(P, K) \in G$ then $V(P, m) = 1$ iff $\sigma |
| 21 | \in S_K(m)$. We usually write $V_P(M)$ instead of $V(P, M)$. |
| 22 | \end{itemize} |
| 23 | There are many other similar formulations of digital signature schemes. |
| 24 | \end{slide} |
| 25 | |
| 26 | \begin{slide} |
| 27 | \topic{forgery goals} |
| 28 | \head{Forgery goals} |
| 29 | |
| 30 | We recognize several different types of forgeries which can be made: |
| 31 | \begin{itemize} |
| 32 | \item An \emph{existential forgery} occurs when an adversary creates a |
| 33 | valid signature for some arbitrary message not of its choosing. |
| 34 | \item An \emph{selective forgery} occurs when an adversary creates a valid |
| 35 | signature for a message that it chooses. |
| 36 | \item A \emph{universal forgery} occurs when an adversary creates a valid |
| 37 | signature for some specific given message. |
| 38 | \item A \emph{total break} occurs when the adversary acquires the secret |
| 39 | key $K$, or equivalent information, and can continue to sign given |
| 40 | messages. |
| 41 | \end{itemize} |
| 42 | The formal definitions don't quite match up to these categories. |
| 43 | \end{slide} |
| 44 | |
| 45 | \begin{slide} |
| 46 | \topic{attack types} |
| 47 | \head{Types of attacks} |
| 48 | |
| 49 | We recognize a number of different types of attack: |
| 50 | \begin{itemize} |
| 51 | \item In a \emph{key-only} attack, the adversary is given only a public |
| 52 | key. |
| 53 | \item In a \emph{known-signature} attack, the adversary given the public |
| 54 | key and a collection of messages with valid signatures. |
| 55 | \item In a \emph{chosen-message} attack, the adversary is provided with an |
| 56 | oracle which signs messages of the adversary's choosing. |
| 57 | \end{itemize} |
| 58 | In order to have `won' the game, we require that the adversary return a |
| 59 | signature on a message which wasn't one of the known-signature messages or |
| 60 | a query to the signing oracle. |
| 61 | \end{slide} |
| 62 | |
| 63 | \begin{slide} |
| 64 | \topic{funny abbreviations} |
| 65 | \head{Funny abbreviations} |
| 66 | |
| 67 | For each goal/attack type pair, we have a notion of security for digital |
| 68 | signature schemes. To save typing, there are standard (ish) abbreviations |
| 69 | for these notions, e.g., EUF-CMA. |
| 70 | |
| 71 | The first part is the forger's goal: EUF, SUF, UUF for existentially, |
| 72 | selectively and universally unforgeable, respectively. |
| 73 | |
| 74 | The second part is the attack time: KOA, KSA, CMA for key-only, |
| 75 | known-signature and chosen-message attack, respectively. |
| 76 | |
| 77 | The strongest notion is EUF-CMA, and that's what we concentrate on. |
| 78 | \end{slide} |
| 79 | |
| 80 | \begin{slide} |
| 81 | \topic{formal definitions} |
| 82 | \head{Formal definition of EUF-CMA} |
| 83 | |
| 84 | Consider this experiment involving a signature scheme $\mathcal{S} = (G, S, |
| 85 | V)$ and an adversary: |
| 86 | \begin{program} |
| 87 | Experiment $\Expt{euf-cma}{\mathcal{S}}(A)$: \+ \\ |
| 88 | $(P, K) \gets G$; \\ |
| 89 | $\Xid{m}{list} \gets \emptyset$; \\ |
| 90 | $(m, \sigma) \gets A^{\id{sign}(\cdot)}(P)$; \\ |
| 91 | \IF $m \notin \Xid{m}{list} \land V_P(m, \sigma) = 1$ |
| 92 | \THEN \RETURN $1$; \\ |
| 93 | \ELSE \RETURN $0$; \- \\[\smallskipamount] |
| 94 | Oracle $\id{sign}(m)$: \+ \\ |
| 95 | $\Xid{m}{list} \gets \Xid{m}{list} \cup \{m\}$; \\ |
| 96 | \RETURN $S_K(m)$; |
| 97 | \end{program} |
| 98 | \end{slide} |
| 99 | |
| 100 | \begin{slide} |
| 101 | \head{Formal definition of EUF-CMA (cont.)} |
| 102 | |
| 103 | We define: |
| 104 | \begin{eqnarray*}[rl] |
| 105 | \Succ{euf-cma}{\mathcal{S}}(A) |
| 106 | &= \Pr[\Expt{euf-cma}{\mathcal{S}}(A) = 1]; \\ |
| 107 | \InSec{euf-cma}(\mathcal{S}; t, q) |
| 108 | &= \max_A \Succ{euf-cma}{\mathcal{S}}(A). |
| 109 | \end{eqnarray*} |
| 110 | where the maximum is taken over adversaries $A$ running in time $t$ and |
| 111 | issuing $q$ signing queries. |
| 112 | |
| 113 | If $\InSec{euf-cma}(\mathcal{S}; t, q) \le \epsilon$ then we say that |
| 114 | $\mathcal{S}$ is a \emph{$(t, q, \epsilon)$-secure EUF-CMA digital |
| 115 | signature scheme}. |
| 116 | \end{slide} |
| 117 | |
| 118 | \xcalways\subsection{Signature schemes from trapdoor one-way functions}\x |
| 119 | |
| 120 | \begin{slide} |
| 121 | \topic{RSA} |
| 122 | \head{RSA as a digital signature scheme} |
| 123 | |
| 124 | RSA is, we assume, a one-way trapdoor permutation. We'd like to be able to |
| 125 | turn this into a signature scheme. |
| 126 | |
| 127 | The obvious thing to do is just define $S_{(n, d)}(m) = m^d \bmod n$ and |
| 128 | $V_{(n, e)}(m, \sigma) = 1 \iff \sigma^e \equiv m \pmod{n}$. But this |
| 129 | doesn't work. |
| 130 | \begin{itemize} |
| 131 | \item It allows key-only existential forgery. Suppose we're given a public |
| 132 | key $(n, e)$. Choose a signature $\sigma \in \Z/n\Z$. Compute $m = |
| 133 | \sigma^e$. Then $(m, \sigma)$ is a valid signed message. |
| 134 | \item It allows universal forgery under chosen message attack. Suppose |
| 135 | we're given a public key $(n, e)$, and asked to forge a signature for |
| 136 | message $m$. Choose $k \inr (\Z/n\Z)^*$, and request a signature |
| 137 | $\sigma'$ of $m' = m k^e$. Then $\sigma' = m^d k^{ed} = m^d k$, so |
| 138 | $\sigma = \sigma' k^{-1}$ is a valid signature on $m$. |
| 139 | \end{itemize} |
| 140 | \end{slide} |
| 141 | |
| 142 | \begin{slide} |
| 143 | \topic{hash-then-sign} |
| 144 | \head{Hash-then-sign} |
| 145 | |
| 146 | We could fix the problems with RSA if we preprocessed the message before |
| 147 | signing. The first idea is to use a collision-resistant hash function $H$, |
| 148 | and to produce a signature on a message $m$, you compute $\sigma = H(m)^d |
| 149 | \bmod n$. |
| 150 | |
| 151 | This doesn't work either. |
| 152 | \begin{itemize} |
| 153 | \item Collision-resistance isn't sufficient for security. Just because $H$ |
| 154 | is collision-resistant doesn't mean that $H(x) H(y) \ne H(x y)$ with |
| 155 | non-negligible probability. If $H$ is partially multiplicative then |
| 156 | universal or selective forgery is still possible. |
| 157 | \item Recall the definition of a one-way function: if $x \inr \dom f$ then |
| 158 | finding $x'$ such that $f(x') = f(x)$ is hard, given only $f(x)$. But |
| 159 | the range of a hash function like SHA-1 is only a tiny portion of the |
| 160 | domain of RSA. |
| 161 | \end{itemize} |
| 162 | \end{slide} |
| 163 | |
| 164 | \begin{slide} |
| 165 | \topic{\PKCS1 padding} |
| 166 | \head{\PKCS1 signature padding \cite{RSA:1993:PRE}} |
| 167 | |
| 168 | Let $n = p q$ be an RSA modulus, with $2^{8(k-1)} < n < 2^{8k)}$ -- i.e., |
| 169 | $n$ is a $k$-byte number. Let $m$ be the message to be signed. |
| 170 | |
| 171 | We compute $\hat{m} = 0^8 \cat T \cat 1^z \cat 0^8 \cat I_H \cat H(m)$ for |
| 172 | some hash function $m$, where: |
| 173 | \begin{itemize} |
| 174 | \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string; |
| 175 | \item $0^8$ is the string of 8 zero-bits; |
| 176 | \item $T = 00000001$ is an 8-bit \emph{type} code; |
| 177 | \item $1^z$ is a padding string of one-bits (with $z$ chosen so that |
| 178 | $\hat{m}$ has the right length; \PKCS1 requires $z \ge 64$); and |
| 179 | \item $I_H$ is an identifier for the chosen hash function $H$. |
| 180 | \end{itemize} |
| 181 | This bit string is then converted into an integer, using a big-endian |
| 182 | representation. Note that $\hat{m} < n$, since its top byte is zero. |
| 183 | \end{slide} |
| 184 | |
| 185 | \begin{slide} |
| 186 | \head{\PKCS1 signature padding (cont.)} |
| 187 | |
| 188 | Diagrammatically, \PKCS1 signature looks like this: |
| 189 | \begin{tabular}[C]{r|c|c|c|c|c|} \hlx{c{2-6}v} |
| 190 | \hex{00} & \hex{01} & |
| 191 | \hex{FF} \hex{FF} \ldots \hex{FF} & |
| 192 | \hex{00} & |
| 193 | $I_H$ & |
| 194 | $H(m)$ |
| 195 | \\ \hlx{vc{2-6}} |
| 196 | \end{tabular} |
| 197 | |
| 198 | This partially obscures the multiplicative structure of RSA, but doesn't |
| 199 | expand the range of the transform at all. \PKCS1 padding only uses a tiny |
| 200 | part of the domain of the RSA function. |
| 201 | |
| 202 | In \cite{Brier:2001:CRS}, Brier, Clavier, Coron and Naccache analyse |
| 203 | general affine padding schemes, of which the \PKCS1 scheme is an example, |
| 204 | and show that the schemes can be broken if the `message' -- the hash -- is |
| 205 | more than a third the size of the modulus. In particular, existential |
| 206 | forgery is possible in polynomial time, and selective forgery in |
| 207 | subexponential time (though much faster than factoring the modulus). |
| 208 | \end{slide} |
| 209 | |
| 210 | \xcalways\subsection{Full-domain hashing}\x |
| 211 | |
| 212 | \begin{slide} |
| 213 | \topic{description} |
| 214 | \head{Full-domain hashing} |
| 215 | |
| 216 | Suppose we have an \emph{ideal hash}, whose range covers the whole of the |
| 217 | domain of our RSA transformation. Would this be secure? If we model the |
| 218 | ideal hash as a random oracle, the answer is yes. |
| 219 | |
| 220 | Let $\mathcal{T} = (G, f, T)$ be a trapdoor one-way function generator. |
| 221 | Then we define the signature scheme $\Xid{\mathcal{S}}{FDH}^{\mathcal{T}, |
| 222 | H} = (\Xid{G}{FDH}^{\mathcal{T}, H(\cdot)}, \Xid{S}{FDH}^{\mathcal{T}, |
| 223 | H(\cdot)}, \Xid{V}{FDH}^{\mathcal{T}, H(\cdot)})$ as follows: |
| 224 | \begin{itemize} |
| 225 | \item $\Xid{G}{FDH}^{\mathcal{T}, H(\cdot)}(\cdot) = G(\cdot)$, i.e., we |
| 226 | use $\mathcal{T}$'s key generator directly. |
| 227 | \item $\Xid{S}{FDH}^{\mathcal{T}, H(\cdot)}_K(m) = T_K(H(m))$: we |
| 228 | implicitly (and deterministically) coerce $H$'s output so that $H(\cdot)$ |
| 229 | is uniformly distributed over $\ran f_P$. |
| 230 | \item $\Xid{V}{FDH}^{\mathcal{T}, H(\cdot)}_P(m, \sigma) = 1 \iff |
| 231 | f_P(\sigma) = H(M)$. |
| 232 | \end{itemize} |
| 233 | \end{slide} |
| 234 | |
| 235 | \begin{slide} |
| 236 | \topic{security results} |
| 237 | \head{Security results for FDH} |
| 238 | |
| 239 | The full-domain hash signature scheme $\Xid{\mathcal{S}}{FDH}^{\mathcal{T}, |
| 240 | H}$ is EUF-CMA if $\mathcal{T} = (G, f, T)$ is a trapdoor one-way |
| 241 | permutation. The standard quantitative result is: |
| 242 | \[ \InSec{euf-cma}(\Xid{\mathcal{S}}{FDH}^{\mathcal{T}, H}; t, q_S, q_H) |
| 243 | \le |
| 244 | q_H \InSec{owf}(\mathcal{T}; t + O(q_H t_f)). \]% |
| 245 | Here, $t_f$ is the length of time required to compute $f$. The additional |
| 246 | $q_H$ term is the number of random oracle (hashing) queries. This doesn't |
| 247 | count queries made by the signing oracle. |
| 248 | |
| 249 | This isn't a terribly promising bound. The problem comes because there is |
| 250 | a conflict between getting the adversary to invert the required point, and |
| 251 | being able to answer signing queries. |
| 252 | \end{slide} |
| 253 | |
| 254 | \begin{proof} |
| 255 | Let $A$ be an adversary against $\Xid{\mathcal{S}}{FDH}^{\mathcal{T}}$ |
| 256 | making $q_S$ signing and $q_H$ random oracle queries: we present an |
| 257 | inverter $I$ for $\mathcal{T}$. |
| 258 | \begin{program} |
| 259 | Inverter $I(P, y)$: \+ \\ |
| 260 | $n \getsr \{0, 1, \ldots, q_H - 1\}$; \\ |
| 261 | $i \gets 0$; \\ |
| 262 | $\Xid{I}{map} \gets \emptyset$; \\ |
| 263 | $\Xid{H}{map} \gets \emptyset$; \\ |
| 264 | $(m, \sigma) \gets A^{\id{sign}(\cdot), \id{hash}(\cdot)}(P)$; \\ |
| 265 | \RETURN $\sigma$; |
| 266 | \newline |
| 267 | Oracle $\id{sign}(m)$: \+ \\ |
| 268 | \IF $m \notin \dom \Xid{H}{map}$ \THEN \\ \quad \= \+ \kill |
| 269 | $h' \getsr \dom f_P$; \\ |
| 270 | $h \gets f_P(h')$; \\ |
| 271 | $\Xid{H}{map} \gets \Xid{H}{map} \cup \{m \mapsto h\}$; \\ |
| 272 | $\Xid{I}{map} \gets \Xid{I}{map} \cup \{h \mapsto h'\}$; \- \\ |
| 273 | $h \gets \Xid{h}{map}(m)$; \\ |
| 274 | \IF $h \notin \dom \Xid{I}{map}$ \THEN \ABORT; \\ |
| 275 | \RETURN $\Xid{I}{map}(h)$; |
| 276 | \next |
| 277 | Oracle $\id{hash}(x)$: \+ \\ |
| 278 | \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\ |
| 279 | \IF $i = n$ \THEN $h \gets y$; \\ |
| 280 | \ELSE \\ \quad \= \+ \kill |
| 281 | $h' \getsr \dom f_P$; \\ |
| 282 | $h \gets f_P(h')$; \\ |
| 283 | $\Xid{I}{map} \gets \Xid{I}{map} \cup \{h \mapsto h'\}$; \- \\ |
| 284 | $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\ |
| 285 | \RETURN $h$; |
| 286 | \end{program} |
| 287 | Note that the inverter `cheats' a little. One of its random oracle replies |
| 288 | is chosen to be the inverter's input $y$. This is OK, because the rules of |
| 289 | the inverter's game say that that $y = f(x)$ for some $x$ chosen uniformly |
| 290 | at random from $\dom f_P$, and hence $y$ is also uniformly distributed and |
| 291 | independent, as required. |
| 292 | |
| 293 | The inverter also `cheats' because it ensures that it knows inverses for |
| 294 | all of the queries except for the $n$-th. |
| 295 | |
| 296 | Let the $q_H$ query strings to the oracle \id{hash} be $M = \{m_0, m_1, |
| 297 | \ldots, m_{q_H-1}\}$. Let $m$ be the message returned by $A$ and let |
| 298 | $\sigma$ be the returned signature. |
| 299 | |
| 300 | Consider the event $N$ that $m \notin M$; i.e., the random oracle was not |
| 301 | queried on the returned message. Then, since $A$ has knowledge of neither |
| 302 | $H(M)$ nor $y$, and both are uniformly distributed over $\dom f_P$, the |
| 303 | probability that it succeeds in producing a valid forgery is equal to its |
| 304 | probability of successfully returning a correct inversion of $y$. |
| 305 | |
| 306 | Now consider the complement event $\lnot N$. Then there is at least a |
| 307 | $1/q_H$ probability that $m = m_n$ -- the one which the inverter must |
| 308 | invert -- in which case $I$ succeeds if $A$ does. (The probability might |
| 309 | be greater in the event that the adversary queries on the same string |
| 310 | several times, though doing so doesn't make a great deal of sense.) |
| 311 | |
| 312 | Let $F$ be the event that $A$ returns a correct forgery, and let $V$ be the |
| 313 | event that $I$ returns a correct inversion. Obviously, |
| 314 | \[ \Pr[F] = \Pr[F \land N] + \Pr[F \land \lnot N] |
| 315 | \quad \text{so} \quad |
| 316 | \Pr[F \land \lnot N] = \Pr[F] - \Pr[F \land N]. \]% |
| 317 | From the above discussion, we have |
| 318 | \[ \Pr[V \land N] = \Pr[F \land N] |
| 319 | \quad \text{and} \quad |
| 320 | \Pr[V \land \lnot N] \ge \frac{1}{q_H} \Pr[F \land \lnot N]. \]% |
| 321 | Finally, |
| 322 | \begin{eqnarray*}[rl] |
| 323 | \Pr[V] &= \Pr[V \land N] + \Pr[V \land \lnot N] \\ |
| 324 | &\ge \Pr[F \land N] + \frac{1}{q_H} \Pr[F \land \lnot N] \\ |
| 325 | &\ge \frac{1}{q_H} |
| 326 | (\Pr[F \land N] + \Pr[F] - \Pr[F \land \lnot N]) \\ |
| 327 | &= \frac{1}{q_H} \Pr[F]. |
| 328 | \end{eqnarray*} |
| 329 | The result follows. |
| 330 | \end{proof} |
| 331 | |
| 332 | \begin{remark*} |
| 333 | Most statements of this result seem to charge the adversary for hash |
| 334 | queries made by the experiment and by the constructed inverter, which seems |
| 335 | unreasonable. The above result shows that the standard security bound |
| 336 | still holds, even under more generous accounting. |
| 337 | \end{remark*} |
| 338 | |
| 339 | \xcalways\subsection{The Probabilistic Signature Scheme}\x |
| 340 | |
| 341 | \begin{slide} |
| 342 | \head{The Probabilistic Signature Scheme \cite{Bellare:1996:ESD}} |
| 343 | |
| 344 | We can improve the security bounds on FDH by making the signing operation |
| 345 | randomized. |
| 346 | |
| 347 | Let $\mathcal{T} = (G, f, T)$ be a trapdoor one-way function generator, as |
| 348 | before, but this time we require that the problem of inverting $f$ be |
| 349 | \emph{self-reducible}. |
| 350 | |
| 351 | For some public parameter $P$, choose $n$ such that $2^{8n} \le |
| 352 | |{\dom f_P}| < 2^{8n+1}$, and fix a security parameter $k$. Then we need |
| 353 | two random oracles $H\colon \{0, 1\}^* \to \{0, 1\}^k$ and $H'\colon \{0, |
| 354 | 1\}^k \to \{0, 1\}^{8n-k}$. |
| 355 | \end{slide} |
| 356 | |
| 357 | \begin{slide} |
| 358 | \topic{description} |
| 359 | \head{Definition of PSS} |
| 360 | |
| 361 | We define the signature scheme $\Xid{\mathcal{S}}{PSS}^{\mathcal{T}} = |
| 362 | (\Xid{G}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}, |
| 363 | \Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}, \Xid{V}{PSS}^{\mathcal{T}, |
| 364 | H(\cdot), H'(\cdot)})$: |
| 365 | \begin{program} |
| 366 | $\Xid{G}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(x)$: \+ \\ |
| 367 | $(P, K) \gets G(x)$; \\ |
| 368 | \RETURN $(P, K)$; |
| 369 | \newline |
| 370 | $\Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(K, m)$: \+ \\ |
| 371 | $r \getsr \{0, 1\}^k$; \\ |
| 372 | $h \gets H(m \cat r)$; \\ |
| 373 | $h' \gets (r \cat 0^{8n-2k}) \xor H'(h)$; \\ |
| 374 | $y \gets 0^8 \cat h \cat h'$; \\ |
| 375 | \RETURN $T_K(y)$; |
| 376 | \next |
| 377 | $\Xid{V}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)} |
| 378 | (P, m, \sigma)$: \+ \\ |
| 379 | $y \gets f_P(\sigma)$; \\ |
| 380 | \PARSE $y$ \AS $z, k\colon h, 8n - k\colon h'$; \\ |
| 381 | \PARSE $h' \xor H'(h)$ \AS $k\colon r, z$; \\ |
| 382 | \IF $z = 0 \land z' = 0 \land h = H(m \cat r)$ |
| 383 | \THEN \RETURN $1$; \\ |
| 384 | \ELSE \RETURN $0$; |
| 385 | \end{program} |
| 386 | \end{slide} |
| 387 | |
| 388 | \begin{slide} |
| 389 | \head{Diagram of PSS} |
| 390 | |
| 391 | %% m <- {0,1}^* r <-R {0, 1}^k |
| 392 | %% | | |
| 393 | %% | | |
| 394 | %% v | |
| 395 | %% [H]<---------------------------| |
| 396 | %% | | |
| 397 | %% | | |
| 398 | %% | v |
| 399 | %% | [||]<---- 0^{8n-2k} |
| 400 | %% | | |
| 401 | %% | | |
| 402 | %% v v |
| 403 | %% |-----------[H']------------>(+) |
| 404 | %% | | |
| 405 | %% | | |
| 406 | %% | v |
| 407 | %% < 00 > < s = H(m || r) > < (r || 0^{8n-2k}) (+) H'(s) > |
| 408 | |
| 409 | \vfil |
| 410 | \[ \begin{graph} |
| 411 | []!{0; <1cm, 0cm>:} |
| 412 | {m \in \{0, 1\}^*}="m" [rrrr] {r \inr \{0, 1\}^k}="r" |
| 413 | "m" :[d] *+[F]{H}="h" |
| 414 | :[ddd] *+=(2, 0)+[F:thicker]{\strut s = H(m \cat r)} |
| 415 | []!{-(2.5, 0)} *+=(1, 0)+[F:thicker]{\strut \hex{00}} |
| 416 | "r" :[dd] *{\ocat}="cat" [r] *+[r]{\mathstrut 0^{8n-2k}} :"cat" |
| 417 | :[d] *{\xor}="x" [uu] :"h" |
| 418 | "m" [ddd] :[rr] *+[F]{H'} :"x" |
| 419 | :[d] *+=(4, 0)+[F:thicker]{\strut t = (r \cat 0^{8n-2k}) \xor H'(s)} |
| 420 | \end{graph} \] |
| 421 | \vfil |
| 422 | \end{slide} |
| 423 | |
| 424 | \begin{slide} |
| 425 | \topic{security results} |
| 426 | \head{Security results for PSS} |
| 427 | |
| 428 | For the PSS scheme we've seen, we have |
| 429 | \begin{eqnarray*}[Ll] |
| 430 | \InSec{euf-cma}(\Xid{\mathcal{S}}{PSS}^{\mathcal{T}}; |
| 431 | t, q_S, q_H, q_{H'}) \le \\ |
| 432 | & \InSec{owf}(\mathcal{T}; t + O(t_n (q_S + q_H) + q_{H'})) + |
| 433 | \frac{3(q_H + q_{H'} + 2)}{2^k}. |
| 434 | \end{eqnarray*} |
| 435 | Here, $q_H$ and $q_H$ are the number of queries to the random oracles $H$ |
| 436 | and $H'$, and $t_n$ is a magical constant relating to, among other things, |
| 437 | the time required for the self-reduction on the original problem and the |
| 438 | difference between $|{\dom f_P}|$ and $2^{8n}$. For RSA or Rabin with a |
| 439 | multiple-of-8-bit modulus, $t_n$ will be some small multiple of $k$ times |
| 440 | the length of time for a public key operation. |
| 441 | \end{slide} |
| 442 | |
| 443 | \begin{proof} |
| 444 | Suppose $A$ can forge a signature under the |
| 445 | $\Xid{\mathcal{S}}{PSS}^{\mathcal{T}}$ scheme. We present an inverter $I$ |
| 446 | which inverts $\mathcal{T}$. |
| 447 | |
| 448 | We shall need to make use of the self-reducibility property of inverting |
| 449 | $\mathcal{T}$. To do this in an abstract way, we require two algorithms: |
| 450 | \begin{itemize} |
| 451 | \item $\id{sr-choose}(P, y)$ returns a pair $(s, y')$, where $s$ is some |
| 452 | state information, and $y'$ is a new problem instance uniformly selected |
| 453 | from the domain of $f_P$; and |
| 454 | \item $\id{sr-solve}(s, x)$ solves an instance of the problem given a |
| 455 | solution to the instance created by \id{sr-choose}. |
| 456 | \end{itemize} |
| 457 | If $P$ is a public parameter for $f$, $y$ is some point in $\ran f_P$, |
| 458 | $\id{sr-choose}(P, y)$ returns $(s, y')$ and $f_P(x') = y'$ then we require |
| 459 | that $\id{sr-solve}(s, x')$ returns an $x$ such that $f_P(x) = y$. |
| 460 | |
| 461 | By way of example, we present implementations of these algorithms for the |
| 462 | RSA function, where $P = (n, e)$: |
| 463 | \begin{program} |
| 464 | Algorithm $\id{sr-choose}(P, y)$: \+ \\ |
| 465 | $(n, e) \gets P$; \\ |
| 466 | \REPEAT $z \getsr \{1, 2, \ldots, n - 1\}$; \\ |
| 467 | \UNTIL $\gcd(z, n) = 1$; \\ |
| 468 | $s \gets (n, z^{-1} \bmod n)$; \\ |
| 469 | \RETURN $(s, y z^e \bmod n)$; |
| 470 | \next |
| 471 | Algorithm $\id{sr-solve}(s, x')$: \+ \\ |
| 472 | $(n, i) \gets s$; \\ |
| 473 | \RETURN $x' i \bmod n$; |
| 474 | \end{program} |
| 475 | (The loop in \id{sr-choose} hardly ever needs more than one iteration. |
| 476 | Indeed, if the condition $\gcd{z, n} = 1$ fails, we've found a factor, |
| 477 | and could use that to solve the problem instance directly.) We shall |
| 478 | assume that the \id{sr-choose} algorithm effectively completes in |
| 479 | deterministic time.) |
| 480 | |
| 481 | We shall also need to be able to convert between elements of $\ran f_P$ and |
| 482 | binary strings. We shall assume that there is a `natural' mapping between |
| 483 | the integers $\{0, 1, \ldots, |{\ran f_P}| - 1\}$ and the elements of $\ran |
| 484 | f_P$, and omit explicit conversions. |
| 485 | |
| 486 | The inverter algorithm is shown in figure~\ref{fig:pss-inverter}. |
| 487 | |
| 488 | \begin{figure} |
| 489 | \begin{program} |
| 490 | Inverter $I(P, y)$: \+ \\ |
| 491 | $\Xid{H}{map} \gets \emptyset$; \\ |
| 492 | $\Xid{H'}{map} \gets \emptyset$; \\ |
| 493 | $\Xid{I}{map} \gets \emptyset$; \\ |
| 494 | $\Xid{m}{list} \gets \emptyset$; \\ |
| 495 | $(m, \sigma) \gets A^{\id{sign}(\cdot), H(\cdot), H'(\cdot)}(P)$; \\ |
| 496 | \IF $m \in \Xid{m}{list}$ \THEN \ABORT; \\ |
| 497 | $y' \gets f_P(\sigma)$; \\ |
| 498 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
| 499 | \PARSE $g \xor H'(h)$ \AS $k\colon r, z'$; \\ |
| 500 | $x \gets m \cat r$; \\ |
| 501 | \IF $z \ne 0 \lor z' \ne 0$ \THEN \ABORT; \\ |
| 502 | \IF $h \ne H(x)$ \THEN \ABORT; \\ |
| 503 | \IF $x \notin \dom \Xid{I}{map}$ \THEN \ABORT; \\ |
| 504 | \RETURN $\id{sr-solve}(\Xid{I}{map}(x), \sigma)$; |
| 505 | \newline |
| 506 | Oracle $\id{sign}(m)$: \+ \\ |
| 507 | $r \getsr \{0, 1\}^k$; \\ |
| 508 | $x \gets m \cat r$; \\ |
| 509 | \IF $x \in \dom \Xid{H}{map}$ \THEN \ABORT; \\ |
| 510 | \REPEAT \\ \quad \= \+ \kill |
| 511 | $\sigma' \getsr \ran f_P$; \\ |
| 512 | $y' \gets f_P(\sigma')$; \- \\ |
| 513 | \UNTIL $y' < 2^{8n}$; \\ |
| 514 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
| 515 | \PARSE $g$ \AS $k\colon r', g'$; \\ |
| 516 | $h' \gets (r \xor r') \cat g'$; \\ |
| 517 | \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\ |
| 518 | $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\ |
| 519 | $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\ |
| 520 | $\Xid{m}{list} \gets \Xid{m}{list} \cup \{m\}$; \\ |
| 521 | \RETURN $\sigma'$; |
| 522 | \next |
| 523 | Oracle $H(x)$: \+ \\ |
| 524 | \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\ |
| 525 | \REPEAT \\ \quad\=\+\kill |
| 526 | $(s, y') \gets \id{sr-choose}(P, y)$; \\ |
| 527 | \PARSE $x$ \AS $m, k\colon r$; \- \\ |
| 528 | \UNTIL $y' < 2^{8n}$; \\ |
| 529 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
| 530 | \PARSE $g$ \AS $k\colon r', g'$; \\ |
| 531 | $h' \gets (r \xor r') \cat g'$; \\ |
| 532 | \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\ |
| 533 | $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\ |
| 534 | $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\ |
| 535 | $\Xid{I}{map} \gets \Xid{I}{map} \cup \{x \mapsto s\}$; \\ |
| 536 | \RETURN $h$; \- \\[\smallskipamount] |
| 537 | Oracle $H'(x)$: \+ \\ |
| 538 | \IF $x \in \dom \Xid{H'}{map}$ \THEN \RETURN $\Xid{H'}{map}(x)$; \\ |
| 539 | $h' \gets \{0, 1\}^{8n - k}$ \\ |
| 540 | $\Xid{H'}{map} \gets \Xid{H'}{map} \cup \{h \mapsto h'\}$; \\ |
| 541 | \RETURN $h'$; |
| 542 | \end{program} |
| 543 | \caption{From the security proof of PSS -- the inverter for the trapdoor |
| 544 | one-way function} |
| 545 | \label{fig:pss-inverter} |
| 546 | \end{figure} |
| 547 | |
| 548 | The oracle $H$ constructs related instances of the original inversion |
| 549 | problem and uses them to build the random oracle results. Because the |
| 550 | subroutine \id{sr-choose} selects problem instances uniformly over $\{0, |
| 551 | 1, \ldots, |{\ran f_P}| - 1\}$, and we iterate until $y' < 2^{8n}$, the |
| 552 | selected instance $y'$ is uniform over $\{0, 1\}^{8n}$. We then construct |
| 553 | $H$ and $H'$ replies as appropriate for the adversary to construct $y'$ as |
| 554 | a message representative for its chosen message $m$, such that if it |
| 555 | responds with a signature for $m$ then we can use \id{sr-solve} to solve |
| 556 | our initial problem. |
| 557 | |
| 558 | The oracle \id{sign} chooses oracle responses in order to fit in with a |
| 559 | previously chosen inverse (computed the easy way, by choosing a point in |
| 560 | the domain of $f_P$ and computing its image). |
| 561 | |
| 562 | The oracle $H'$ just chooses random values. |
| 563 | |
| 564 | Most of the \ABORT statements in the main inverter routine detect incorrect |
| 565 | signatures. The final one, asserting $x \notin \Xid{I}{map}$, can't happen |
| 566 | unless the signature is a duplicate of one we already gave. |
| 567 | |
| 568 | The \ABORT{}s in $H$ and \id{sign} detect conditions in which the |
| 569 | adversary has successfully distinguished its simulated environment from |
| 570 | that of the standard forging experiment. |
| 571 | |
| 572 | The inverter succeeds whenever a correct forgery is made. To conclude the |
| 573 | proof, we must bound the probability that an \ABORT occurs in $H$ or |
| 574 | \id{sign}. |
| 575 | |
| 576 | The \ABORT in $H$ occurs when the chosen $H(x)$ collides with a value for |
| 577 | which $H'$ is already defined. Since $H(x)$ values are chosen uniformly |
| 578 | from $\{0, 1\}^k$, this occurs with probability no more than $(q_H + |
| 579 | q_{H'} + 2)/2^k$. |
| 580 | |
| 581 | The first \ABORT in \id{sign} occurs when the chosen point $x = m \cat r$ |
| 582 | already has an image defined in $H$: this happens with probability at most |
| 583 | $q_H/2^k$. The second occurs when $h$ already has an image in $H'$, and |
| 584 | occurs with probability at most $(q_H + q_{H'})/2^k$. |
| 585 | |
| 586 | The loops in $H$ and \id{sign} don't complete in a deterministic amount |
| 587 | of time. But we can abort if they appear to be taking too long, and choose |
| 588 | the maximum number of iterations to achieve any given failure probability. |
| 589 | Let $d = |{\dom f_P}|$. Then the probability that any particular iteration |
| 590 | fails to select an appropriate problem instance is $1 - 2^{8n}/d$. For RSA |
| 591 | or Rabin with a modulus bit length which is a multiple of 8, this is less |
| 592 | than $\frac{1}{2}$. We choose the number of iterations in the entire |
| 593 | program to be such that we have a $2^{-k}$ probability of failure. Thus, |
| 594 | we set our maximum as $-k/\log_2 (1-2^{8n}/d)$ iterations in the entire |
| 595 | program. |
| 596 | |
| 597 | Fitting all of this together, we see that |
| 598 | \[ \Succ{owf}{\mathcal{T}}(I) \ge |
| 599 | \Succ{euf-cma}{\Xid{\mathcal{S}}{PSS}^{\mathcal{T}}} - |
| 600 | \frac{3(q_H + q_{H'} + 2)}{2^k}. \]% |
| 601 | completing the proof. |
| 602 | \end{proof} |
| 603 | |
| 604 | \endinput |
| 605 | |
| 606 | %%% Local Variables: |
| 607 | %%% mode: latex |
| 608 | %%% TeX-master: "ips" |
| 609 | %%% End: |