On the insecurity of a server-aided RSA protocol

Phong Q. Nguyen, Igor E. Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

17 Citations (Scopus)

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 RSAS 1. 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2001
Subtitle of host publication7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Australia, December 9–13, 2001 Proceedings
EditorsColin Boyd
Place of PublicationBerlin; New York
PublisherSpringer, Springer Nature
Pages21-35
Number of pages15
ISBN (Electronic)9783540456827
ISBN (Print)3540429875, 9783540429876
DOIs
Publication statusPublished - Dec 2001
Event7th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT - 2001 - Gold Coast, Australia
Duration: 9 Dec 200113 Dec 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2248
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other7th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT - 2001
CountryAustralia
CityGold Coast
Period9/12/0113/12/01

Keywords

  • Cryptanalysis
  • Lattices
  • RSA signature
  • Server-aided protocol

Fingerprint Dive into the research topics of 'On the insecurity of a server-aided RSA protocol'. Together they form a unique fingerprint.

Cite this