[pycrypto] Bug in Crypto.PublicKey.RSA?

[Bill Broadley]

Dwayne C. Litzenberger wrote:
>> >>> keysize=368
>> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>> [ finishes in close to zero time ]
>> >>> keysize=369
>> >>> privkeyA = RSA.generate(keysize, rpool.get_bytes)
>> Hangs forever.... well at least 10's of minutes.
> 
> I filed a bug report:
> 
>     https://bugs.launchpad.net/pycrypto/+bug/268101

Ah, do you think that is an ubuntu bug?  Or a pycrypto?  I.e. can I fix it by 
installing pycrypto myself.  I had thought I had just misunderstood.

>>> I should also add that you should not be encrypting user data 
>>> directly using RSA.  You _need_ padding like PKCS#1 if you want any 
>>> security.
>>
>> Hmm, I was not aware of padding issues.  What is the attack?  How much 
>> is the ideal padding?  Is the attack related to guessing the plain 
>> text based on the file size?  Is the padding supposed to be random 
>> extra bytes?  Filled to some boundary like the next 16 bytes?  More?  
>> Does compressing the plain text help?
> 
> If you're asking "how much" padding, then you misunderstand what is 
> meant by RSA "padding".  It is NOT just a simple matter of appending 
> zeros to a message.  Quoting Wikipedia:
> 
>     "In public key cryptography, padding is the process of preparing a 
>     message for encryption or signing with a primitive such as RSA. A 
>     popular example is OAEP. This is called "padding" because 
> originally,     random material was simply appended to the message to 
> make it long     enough for the primitive, but this is not a secure form 
> of padding and     is no longer used. A modern padding scheme aims to 
> ensure that the     attacker cannot manipulate the plaintext to exploit 
> the mathematical     structure of the primitive..."
> 
> If you want to implement your own RSA encryption, then look at PKCS#1 
> (currently at version 2.1):
> 
>     http://www.rsa.com/rsalabs/node.asp?id=2125

That's was a bit of a hard read, I found some similar relevant material at:
      http://en.wikipedia.org/wiki/Optimal_Asymmetric_Encryption_Padding

Which looks relevant and useful.  Some additional at the bottom of the page:
# ^ M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt 
with RSA.

Thanks for bringing the padding issue to my attention.

> Dan Boneh's article, "Twenty Years of Attacks on the RSA Cryptosystem", 
> is a good start:
> 
>     http://www.cs.bgu.ac.il/~beimel/Courses/crypto/Boneh.pdf

Added to my reading list thanks.

> If "only the one encrypting should ever be able to decrypt the files", 
> then why not use symmetric encryption?  It's much faster, and probably 
> stronger in the long run (since most people don't use 8192-bit RSA keys).

Mostly for the added protection of not having your private key on the system.
I might even backup systems that aren't even under my control.  Scenarios like 
"Hey, user departmental user X, to back up your machine install this program, 
and use this public key."

I also find the public key appealing for reputation, a global ID, etc.

Oh, as to performance my symmetric vs public key encryption tests didn't find 
much difference:
$ dd if=/dev/urandom of=/tmp/100MB bs=10240 count=10240
$ time (echo a-test-password-of-non-trivial-length | gpg -o /dev/null 
--symmetric --passphrase-fd 0  /tmp/100MB)
real	0m8.563s
user	0m8.513s
sys	0m0.052s
$ ls -alh /tmp/100MB
-rw-r--r-- 1 bill bill 100M 2008-09-09 19:43 /tmp/100MB

Using a 2kbit RSA key:
$ gpg --list-keys
/home/bill/.gnupg/pubring.gpg
-----------------------------
pub   1024D/07DDAB8A 2008-09-08
uid                  Python benchmark <py at bench>
sub   2048g/37E185E1 2008-09-08
$ time (echo | gpg -o /dev/null -e -r benchmark --passphrase-fd 0 /tmp/100MB )
Reading passphrase from file descriptor 0

real	0m9.555s
user	0m9.513s
sys	0m0.048s

So I'm not too concerned about 8.5 seconds 11.5MB/sec vs 10.5MB/sec.

Am I missing something?

> If you must use public-key crypto, use GPG.  Avoid X.509:
> 
>     http://www.cs.auckland.ac.nz/~pgut001/pubs/x509guide.txt
> 
> Also, avoid PKCS#12:
> 
>     http://www.cs.auckland.ac.nz/~pgut001/pubs/pfx.html

Wow, more land mines than I expected, thanks.

> Don't forget to apply an authentication scheme to the data if there's 
> any possibility that the data might be manipulated.

Indeed.

>> #2 Securely communications between peers (of encrypted files).  Possibly
>>    with out of band communication of public keys (I.e. manual peer
>>    introduction by the admin).
> 
> This is too vague for me to recommend anything, but it sounds like GPG 
> might work here.
> 
> And don't forget about random number generation.  All your crypto relies 
> upon it, but people screw up the implementations all the time.  Don't be 
> one of those people!

Indeed.  If I generate the keys myself (as opposed to asking gpg) I'd use 
/dev/random under linux (which from what I can tell is a pretty good 
implementation).