author mdw Sun, 3 Feb 2002 14:16:46 +0000 (14:16 +0000) committer mdw Sun, 3 Feb 2002 14:16:46 +0000 (14:16 +0000)
 auth-mac.tex patch | blob | blame | history auth-sig.tex patch | blob | blame | history enc-pub.tex patch | blob | blame | history

index 60e0034..67489f0 100644 (file)
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] index 8faff1e..17f0bad 100644 (file) \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)$; \\
$(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\}$; \\
index 2da1c82..bf1dc89 100644 (file)
@@ -1521,7 +1521,7 @@ for OAEP+ which is presented in full later.
$w \gets T_K(y)$; \\
\PARSE $w$ \AS $s, k\colon t$; \\
$r \gets t \xor H(s)$; \\
-      \PARSE $s$ \AS $s' \cat k\colon c$; \\
+      \PARSE $s$ \AS $s', k\colon c$; \\
$x \gets s' \xor G(r)$; \\
\IF $c = H'(x \cat r)$ \THEN \RETURN $x$; \\
\ELSE \RETURN $\bot$;