[ pycrypto-Bugs-1266515 ] RSA encryption without proper padding considered weak

Bugs item #1266515, was opened at 2005-08-22 13:07
Message generated for change (Tracker Item Submitted) made by Item Submitter
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=120937&aid=1266515&group_id=20937

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Submitted By: Nobody/Anonymous (nobody)
Assigned to: Nobody/Anonymous (nobody)
Summary: RSA encryption without proper padding considered weak

Initial Comment:
I've just read PKCS#1 v1.5 (which has become RFC 2313)
and PKCS#1 v2.1 (RFC 3447)

PKCS#1 v2.1 (RFC 3447)
    http://www.rsasecurity.com/rsalabs/node.asp?id=2125
   
ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf

v2.1 states that cryptographic primitives (such as the
simple m**e mod n of RSA) "are not intended to provide
apart from a scheme" (p.9). It then defines a slightly
more complex encryption "scheme" which encodes the
plaintext prior to the plain RSA encryption.

The encryption function of RSAobj keys is a simple
exponentiation modula n.

This is weak for several reasons:

* decryption == signing, and an attacker could use this
to retrieve a valid signature for an arbitrary document
even if the entity that holds the private key has
disabled signing.

* Given that the set of expected plain texts is small,
an opponent is able to precompute the corresponding
ciphertext.

* Even more serious, there seem to be attacks which
reveal the private key (or parts of it), but haven't
read about the mathematics at all. But the encoding
stuff in PKCS#1 can't be all useless!? 

IMHO all of the above would apply to signatures and
qNEW encryptions/signatures as well. ElGamal depends on
a private one-time value, but I don't know if this
implicates that the above weaknesses don't apply to
ElGamal.

RFC 2440 (OpenPGP) cites (p.17) PKCS#1 and uses the
"old" encoding format of v1.5 which is no longer
recommended by v2.1 but still secure if used like in
RFC 2440. However, an OpenPGP implementtion is required
to "make new PKCS-1
padding for each key" (recipient) when encryption for
several recipients.  RFC 3560 (RSAES-OAEP in CMS)
refers to known "adaptive chosen ciphertext attacks"
that apply to the PKCS#1 v1.5 padding algorithm and, so
far I'm sure, also to unpadded RSA.

If it turns out that the encryption provided by the
Python Cryptography Toolkit is weak, this would be a
serious issue.
In this case, I propose

    - to provide "EME-OAEP" encoding (as defined in PKCS#1)
    - to consider subclassing the
Crypto.PublicKey.pubkey.pubkey class, owerwriting the
encrypt/decrypt/sign/verify methods so that they
support EME-OAEP and recommending the new class.

bye,
    dpj

ps. I'd like to take the opportunity to thank amk and
all the other Python-Crypto people; I've learned a lot
about cryptogrophy and even more about python from your
sources.


----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=120937&aid=1266515&group_id=20937


-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf