Subject: common modulus attack on RSA

From: [email-masked]
Date: Fri, 3 May 2002 09:58:51 -0500

From: John Dlugosz

In "Applied Cryptography", page 472, Schneier warns against ever encrypting
the same plaintext with two keys having the same n (but different e).

Different public keys may indeed have a common n, either by chance, because
of an implementation that reuses a small set of n, or a deliberate attack.

The session key is encrypted to multiple public keys.

Looking at section 5.1 of RFC2440, it appears that only the MPI of the
RSA-encrypted value of m is used.  I'm supposing that m is much smaller
than n, so the whole thing takes one "block" through RSA.

The other values put into m (the algorithm and the  checksum) are the same,
too, so m will be identical in every public-key encrypted session key
packet.

Perhaps the new draft should note that an implementation could warn about
multiple recipients with the same n.  Remember, this could be done by
other-than-chance, such as deliberatly introducing them as an attack.
Better yet, I'd be happier if another number, chosen by the encryptor, were
prepended to the session key, different for each recipient (e.g. a simple
counter).

Is the note that a new PKCS-1 padding be made doing exactly this?  If so,
does that add a unique value to the =end= (what I normally think of as
padding), or does it pre-pend anything, too?  If so, is it guaranteed that
the length of the final m is shorter than n?

--John

---

From: Derek Atkins <[email-masked]>
Date: 03 May 2002 11:19:25 -0400

You do realize that the liklihood of using the same 'N' is near zero.
If you and I choose the same N, that means that we can effectively
decrypt each others' messages.

Also, the 'm' being encrypted has random padding, and that random
padding should be unique per key.  In other words, 'm' _should_ be
different for each key anyways.

-derek

-- 
       Derek Atkins, SB '93 MIT EE, SM '95 MIT Media Laboratory
       Member, MIT Student Information Processing Board  (SIPB)
       URL: http://web.mit.edu/warlord/    PP-ASEL-IA     N1NWH
       [email-masked]                        PGP key available