41761fdc |
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} |
53aa10b5 |
32 | \item An \emph{existential forgery} occurs when an adversary creates a |
41761fdc |
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 = |
56c48de4 |
133 | \sigma^e$. Then $(m, \sigma)$ is a valid signed message. |
41761fdc |
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; |
56c48de4 |
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 |
41761fdc |
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} |
53aa10b5 |
186 | \head{\PKCS1 signature padding (cont.)} |
41761fdc |
187 | |
53aa10b5 |
188 | Diagrammatically, \PKCS1 signature looks like this: |
41761fdc |
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, |
56c48de4 |
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). |
41761fdc |
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]. \]% |
53aa10b5 |
317 | From the above discussion, we have |
41761fdc |
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)$; \\ |
56c48de4 |
373 | $h' \gets (r \cat 0^{8n-2k}) \xor H'(h)$; \\ |
41761fdc |
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)$; \\ |
56c48de4 |
380 | \PARSE $y$ \AS $z, k\colon h, 8n - k\colon h'$; \\ |
381 | \PARSE $h' \xor H'(h)$ \AS $k\colon r, z$; \\ |
41761fdc |
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)$; \\ |
56c48de4 |
498 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
499 | \PARSE $g \xor H'(h)$ \AS $k\colon r, z'$; \\ |
41761fdc |
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}$; \\ |
56c48de4 |
514 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
515 | \PARSE $g$ \AS $k\colon r', g'$; \\ |
41761fdc |
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)$; \\ |
56c48de4 |
527 | \PARSE $x$ \AS $m, k\colon r$; \- \\ |
41761fdc |
528 | \UNTIL $y' < 2^{8n}$; \\ |
56c48de4 |
529 | \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ |
530 | \PARSE $g$ \AS $k\colon r', g'$; \\ |
41761fdc |
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 |
53aa10b5 |
566 | unless the signature is a duplicate of one we already gave. |
41761fdc |
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: |