Security Analysis of Two RSA-Based Fair Document Exchange Protocols

In 2005, A. Nenadic N. Zhang and Q. Shi proposed a new cryptographic primitive, called Verifiable and Recoverable Encryption of Signature VRES. Based on RSA-based VRES, they presented two variant protocols RSA-CEMD1 and RSA-CEMD2 for certified e-mail delivery with RSA receipts. They claimed that the protocols provided strong fairness to ensure that the recipient receives the e-mail if and only if the sender receives the receipt. Later, N. Zhang, Q. Shi, M. Merabti, and R. Askwith presented a practical and efficient fair document exchange protocol based on a verifiable and recoverable encryption of keys that is somewhat similar to the VRES. In this paper, we find that the VRES scheme is universal forgeable. Anyone can generate the false VRES for any message without the knowledge of any private key of the sender, the recipient and the TTP. It follows that the two variant protocols RSA-CEMD1, RSA-CEMD2 are all insecure. Meanwhile, we show that the document exchange protocol is not fair since the verifiable and recoverable encryption of keys is not recoverable.