Now we turn our attention to $T^1$. It's clear that we can't simulate
$T^1$ very easily using an oracle for $F$, since we don't know $K$
(and indeed there might not be a key $K$). The intuitive reason why
- $T^1$ is insecure is that $F$ might have leak useful information if
- its input matches its key. This doesn't affect the strength of $F$ as
- a PRF because you have to know the key before you can exploit this
- leakage; but $T^1$ already knows the key, and this can be exploited to
- break the MAC.
+ $T^1$ is insecure is that $F$ might leak useful information if its input
+ matches its key. This doesn't affect the strength of $F$ as a PRF
+ because you have to know the key before you can exploit this leakage; but
+ $T^1$ already knows the key, and this can be exploited to break the MAC.
To show that this is insecure formally, let $F'$ be defined as
follows:
\next
Algorithm $\Xid{V}{XUH}^{H, F}_{K, K'}(m, \tau)$: \+ \\
$(s, \sigma) \gets \tau$; \\
- \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\
+ \IF $\sigma = H_K(m) \xor F_{K'}(s)$ \THEN \RETURN $1$; \\
\ELSE \RETURN $0$;
\end{program}
Note that verification is stateless.
\next
Algorithm $\Xid{V}{XUH$\$$}^{H, F}_{K, K'}(m, \tau)$: \+ \\
$(s, \sigma) \gets \tau$; \\
- \IF $\sigma = H_K(m) \xor F_{K'}(i)$ \THEN \RETURN $1$; \\
+ \IF $\sigma = H_K(m) \xor F_{K'}(s)$ \THEN \RETURN $1$; \\
\ELSE \RETURN $0$;
\end{program}
\begin{eqnarray*}[Ll]
\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
\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
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
$\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$;
$(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; \\
$\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\}$; \\
\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\}$; \\
~mdw / doc / ips / commitdiff