Abstract:
At Crypto '88, Matsumoto, Kato and Imai proposed a protocol, known as RSA-S1,
in which a smart card computes an RSA signature, with the help of an untrusted
powerful server. There exist two kinds of attacks against such protocols:
passive attacks (where the server does not deviate from the protocol)
and active attacks (where the server may return false values).
Pfitzmann and Waidner presented at Eurocrypt '92
a passive meet-in-the-middle attack and a few active attacks on RSA-S1.
They discussed two simple countermeasures to thwart such attacks:
renewing the decomposition of the RSA private exponent,
and checking the signature (in which case a small public exponent must be
used). We present a new lattice-based provable passive attack on RSA-S1
which recovers the factorization
of the RSA modulus when a very small public exponent is used,
for many choices of the parameters.
The first countermeasure does not prevent this attack
because the attack is a one-round attack, that is,
only a single execution of the protocol is required.
Interestingly, Merkle and Werchner recently provided a security proof
of RSA-S1 against one-round passive attacks in some generic model,
even for parameters to which our attack provably applies.
Thus, our result throws doubt on the real significance
of security proofs in the generic model, at least for server-aided RSA
protocols.
We also present a simple analysis of a multi-round lattice-based
passive attack proposed last year by Merkle.