X-Git-Url: https://git.distorted.org.uk/~mdw/doc/ips/blobdiff_plain/41761fdc7bb8f1ed87f5e1116d389158513ee280..014f5211bd99f07f2bc962adb9edfded92d31b2b:/auth-sig.tex diff --git a/auth-sig.tex b/auth-sig.tex index b3322ac..17f0bad 100644 --- a/auth-sig.tex +++ b/auth-sig.tex @@ -29,7 +29,7 @@ We recognize several different types of forgeries which can be made: \begin{itemize} - \item An \emph{existiential forgery} occurs when an adversary creates a + \item An \emph{existential forgery} occurs when an adversary creates a valid signature for some arbitrary message not of its choosing. \item An \emph{selective forgery} occurs when an adversary creates a valid signature for a message that it chooses. @@ -130,7 +130,7 @@ \begin{itemize} \item It allows key-only existential forgery. Suppose we're given a public key $(n, e)$. Choose a signature $\sigma \in \Z/n\Z$. Compute $m = - \sigma$. Then $(m, \sigma)$ is a valid signed message. + \sigma^e$. Then $(m, \sigma)$ is a valid signed message. \item It allows universal forgery under chosen message attack. Suppose we're given a public key $(n, e)$, and asked to forge a signature for message $m$. Choose $k \inr (\Z/n\Z)^*$, and request a signature @@ -174,8 +174,8 @@ \item $|\hat{m}| = 8k$, i.e., $\hat{m}$ is a $k$-byte string; \item $0^8$ is the string of 8 zero-bits; \item $T = 00000001$ is an 8-bit \emph{type} code; - \item $1^z$ is a padding string of one-bits (\PKCS1 requires $z \ge 64$); - and + \item $1^z$ is a padding string of one-bits (with $z$ chosen so that + $\hat{m}$ has the right length; \PKCS1 requires $z \ge 64$); and \item $I_H$ is an identifier for the chosen hash function $H$. \end{itemize} This bit string is then converted into an integer, using a big-endian @@ -183,9 +183,9 @@ \end{slide} \begin{slide} - \head{Fixing RSA, 2: \PKCS1 padding (cont.)} + \head{\PKCS1 signature padding (cont.)} - Diagramatically, \PKCS1 signature looks like this: + Diagrammatically, \PKCS1 signature looks like this: \begin{tabular}[C]{r|c|c|c|c|c|} \hlx{c{2-6}v} \hex{00} & \hex{01} & \hex{FF} \hex{FF} \ldots \hex{FF} & @@ -201,10 +201,10 @@ In \cite{Brier:2001:CRS}, Brier, Clavier, Coron and Naccache analyse general affine padding schemes, of which the \PKCS1 scheme is an example, - and show that if the `message' -- the hash -- is more than a third the size - of the modulus. In particular, existential forgery is possible in - polynomial time, and selective forgery in subexponential time (though much - faster than factoring the modulus). + and show that the schemes can be broken if the `message' -- the hash -- is + more than a third the size of the modulus. In particular, existential + forgery is possible in polynomial time, and selective forgery in + subexponential time (though much faster than factoring the modulus). \end{slide} \xcalways\subsection{Full-domain hashing}\x @@ -314,7 +314,7 @@ \[ \Pr[F] = \Pr[F \land N] + \Pr[F \land \lnot N] \quad \text{so} \quad \Pr[F \land \lnot N] = \Pr[F] - \Pr[F \land N]. \]% - From the above discussion, we ahave + From the above discussion, we have \[ \Pr[V \land N] = \Pr[F \land N] \quad \text{and} \quad \Pr[V \land \lnot N] \ge \frac{1}{q_H} \Pr[F \land \lnot N]. \]% @@ -370,15 +370,15 @@ $\Xid{S}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)}(K, m)$: \+ \\ $r \getsr \{0, 1\}^k$; \\ $h \gets H(m \cat r)$; \\ - $h' \gets (r \cat 0^{8n-2k}) \xor H'(x)$; \\ + $h' \gets (r \cat 0^{8n-2k}) \xor H'(h)$; \\ $y \gets 0^8 \cat h \cat h'$; \\ \RETURN $T_K(y)$; \next $\Xid{V}{PSS}^{\mathcal{T}, H(\cdot), H'(\cdot)} (P, m, \sigma)$: \+ \\ $y \gets f_P(\sigma)$; \\ - \PARSE $y$ \AS $z \cat k\colon h \cat 8n - k\colon h'$; \\ - \PARSE $h' \xor H'(h)$ \AS $k\colon r \cat z$; \\ + \PARSE $y$ \AS $z, k\colon h, 8n - k\colon h'$; \\ + \PARSE $h' \xor H'(h)$ \AS $k\colon r, z$; \\ \IF $z = 0 \land z' = 0 \land h = H(m \cat r)$ \THEN \RETURN $1$; \\ \ELSE \RETURN $0$; @@ -495,8 +495,8 @@ $(m, \sigma) \gets A^{\id{sign}(\cdot), H(\cdot), H'(\cdot)}(P)$; \\ \IF $m \in \Xid{m}{list}$ \THEN \ABORT; \\ $y' \gets f_P(\sigma)$; \\ - \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\ - \PARSE $g \xor H'(h)$ \AS $k\colon r \cat z'$; \\ + \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ + \PARSE $g \xor H'(h)$ \AS $k\colon r, z'$; \\ $x \gets m \cat r$; \\ \IF $z \ne 0 \lor z' \ne 0$ \THEN \ABORT; \\ \IF $h \ne H(x)$ \THEN \ABORT; \\ @@ -511,8 +511,8 @@ $\sigma' \getsr \ran f_P$; \\ $y' \gets f_P(\sigma')$; \- \\ \UNTIL $y' < 2^{8n}$; \\ - \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\ - \PARSE $g$ \AS $k\colon r' \cat g'$; \\ + \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ + \PARSE $g$ \AS $k\colon r', g'$; \\ $h' \gets (r \xor r') \cat g'$; \\ \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\ $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\ @@ -524,10 +524,10 @@ \IF $x \in \dom \Xid{H}{map}$ \THEN \RETURN $\Xid{H}{map}(x)$; \\ \REPEAT \\ \quad\=\+\kill $(s, y') \gets \id{sr-choose}(P, y)$; \\ - \PARSE $x$ \AS $m \cat k\colon r$; \- \\ + \PARSE $x$ \AS $m, k\colon r$; \- \\ \UNTIL $y' < 2^{8n}$; \\ - \PARSE $y'$ \AS $z \cat k\colon h \cat 8n - k\colon g$; \\ - \PARSE $g$ \AS $k\colon r' \cat g'$; \\ + \PARSE $y'$ \AS $z, k\colon h, 8n - k\colon g$; \\ + \PARSE $g$ \AS $k\colon r', g'$; \\ $h' \gets (r \xor r') \cat g'$; \\ \IF $h \in \dom \Xid{H'}{map}$ \THEN \ABORT; \\ $\Xid{H}{map} \gets \Xid{H}{map} \cup \{x \mapsto h\}$; \\ @@ -563,7 +563,7 @@ Most of the \ABORT statements in the main inverter routine detect incorrect signatures. The final one, asserting $x \notin \Xid{I}{map}$, can't happen - unless the signaure is a duplicate of one we already gave. + unless the signature is a duplicate of one we already gave. The \ABORT{}s in $H$ and \id{sign} detect conditions in which the adversary has successfully distinguished its simulated environment from