some rsa keys only produce 255 bytes when encrypting spaces

Bug #1040261 reported by Roman Tetelman
8
This bug affects 1 person
Affects Status Importance Assigned to Milestone
Python-Crypto
New
Undecided
Unassigned

Bug Description

i was writing some tests to help get rid of stray strip()s where they shouldn't be, and ran into this:

 def testSpaces(self):
  keys = [RSA.generate(2048),
   #roughly one in 20 randomly generated keys seem to always return 255 bytes instead of
   #256 when encrypting strings consisting only of the space character
   #this is one of them cherry picked to make the issue reproducible
   RSA.importKey("""-----BEGIN RSA PRIVATE KEY-----
MIIEpQIBAAKCAQEAtqFtstUW6zXYMiZnnwDLzRuxCbHGS0J5g0/KlhIbfb1JsssN
b8j8K/9AFjvAdnXaF1GyHlrlEUfNqf1n1GK5hulYluHHdh371v8kq6YYYz5QBDdd
A3iZjW+MN8j+G3BpRSV+o0e9vKLoubz3TKx7WZDtcnR+Oc+35PaiLC2EDGIGLmrk
HcKmOED3I+rzcdd6FEcBQx4IRVwXAj2MTfP4yd8w4hT0kEPD7HSm6UKI+jmjgb/y
LhPqGIsM8oSQ9/zGhCX2C6G8sTydEHiYj5lmWYN5LCWIcjcQnHFXA/KkmDe8cIz+
0XcicTi/PRcrRQHlX2h4MXuGvQQfc5wuKDT1KQIDAQABAoIBAQCNM3ZLI/GaXYEQ
FR1clBL+PAC/DBHSMk0ct15cdReIOgd3EwMKgIxnv+vexMfjTu8VxHZAfepJWAis
+12BmerzYgq6bUn4CuqhqZbCl6KXaKAZAm0Jt/6QmcQBhYbh1CGv8nNc7qTF6fah
VHanc1vTPfg329WUAQOfJQjxuyczInA4OuwKGBxT+BLaxQ70iB+Y99oBm91JP54/
Xru5PHS718bxgzWY7R0M9XOFseMMMli5LUtUfIziVPgi/KI1vmA68F1+mfpkS6hW
hYethCFWSlFf6IuOP/mFabHJbFKRV1E030u+z9RLj3LYQ/0I5NesksKCZOg6XfUm
jc3n+TW5AoGBANFBknYUzGQNiCOCaTLupVb51dmwnB/irgtnBRpJTGblk0tppD1t
g7tCnAbC9eIgxwolgRWs8ClnOv9e0VK0B8/+HZZVl7Tn8F0ILf08VFL7kx717G8l
sB46SaYBdKoZ+LEGLdP09kZv79mUcVx872XNfv1s445qbGc8Orc4ZbMLAoGBAN9t
Qk3wCxJhv+VPRqv7ZQsem56JVUgFFiU8mJhgGavRlIY1OUaj+/6hFT2akN/PAKer
vQPDDXR9SO1LAPjLYDFv1HRKDdMhP36zQHXxbY96x3X1OHcGcartQkfbCw8WiIMq
BeulfGhkK24XrtMXfCOXPCZg7MEqUJXtyLs0XRkbAoGAYiknYlr5UkoCvd2UKb9H
Mli6V4cAhfiY+mJWQ3F09KPnB65DzEkOTY6+kHFuVKhZlknnltpsQo/ZXigFe41W
SNyE1pvKMaPH3mxS3oMpb0/yQMjOI4mDZ3qiR8xRBOZwAeLLJq23xW0HD4MR9nfo
+VF/q7Qjvw/vUDIxvPcoxecCgYEAwv9qtPbh0uM5RftQpN0+LNxD2bPmmHrH/yvJ
yoNlJE5AIHnnST3puyv/i8qQ0qSp36zFxLjBz39g3KlvabSmeb8uX2gadMA52Gy9
v7I8etMfrlWdOFSJdDKqfGgyWLLD5iYREL9Xuwxh0y4cSOPgVnex6ZUCTPyPZKsp
XCmxby0CgYEAm1Nu2wtwMSTw3eDkDl3oWSHnFss3hcU40pJpkfRDROIKQBykBEuB
X8xkZ2VdQ+O++8cML8rPxMr4AFIHQuyERL1+5GNbqiXt9nGASe8+SplhwqhjLJOk
9kJ6RPcK6eMQ/3XFJ+BSaCsr1e6ojbPRMXGOzuJm3GyOjkzCF5IC9V0=
-----END RSA PRIVATE KEY-----"""),
   ]
  for key in keys:
   clear = ' ' * 10

   ciphertext = key.encrypt(clear, os.urandom)
   self.assertEqual(clear, key.decrypt(ciphertext))
   self.assertEqual(len(ciphertext[0]), 256, "%d != %d\nkey:\n%s" % (len(ciphertext[0]), 256, key.exportKey()))

Revision history for this message
Roman Tetelman (kevlarman) wrote :

turns out it happens with any string, when converting from a python long to bytes any leading null bytes end up missing.
(encrypting any given string with 256 newly generated keys will reliably produce at least one that demonstrates this issue)

Revision history for this message
Darsey Litzenberger (dlitz) wrote :

Why do you expect it to do anything different? The Crypto.PublicKey.RSA module is just the RSA primitive, so it returns the bare result of m**e (mod n). If you pass it a string, it runs long_to_bytes on the result before returning it.

Many values return even fewer bytes:

    >>> k = RSA.generate(2048, e=5)
    >>> k.encrypt("\x00", "")
    ('\x00',)
    >>> k.encrypt("\x01", "")
    ('\x01',)
    >>> k.encrypt("\x02", "")
    (' ',)
    >>> k.encrypt("\x02", "")
    (' ',)
    >>> k.encrypt("\x03", "")
    ('\xf3',)
    >>> k.encrypt("\x04", "")
    ('\x04\x00',)
    >>> k.encrypt("\xff", "")
    ('\xfb\t\xf6\x04\xff',)

and it works with longs, too:

    >>> k.encrypt(2L, '')
    (32L,)
    >>> k.encrypt(255L, '')
    (1078203909375L,)

You really shouldn't be using the RSA module directly. That's called "Textbook RSA", and is insecure. You at least want to be using PKCS#1 padding, which is provided in the Crypto.Cipher.PKCS1_OAEP module. That will at least give you IND-CCA2 security, however, your messages will still be length-limited to less than the size of the modulus. What you really want to do is to use a higher-level encryption standard like OpenPGP or Keyczar (http://www.keyczar.org/), rather than trying to invent your own cryptographic message format.

Revision history for this message
Roman Tetelman (kevlarman) wrote :

because openssl rsa produces the leading zero(s) with the same key. as far as padding, in my application there are much faster ways to verify a plaintext than running rsa on it (and the plaintext is a sufficiently long string from /dev/urandom to be unguessable anyway)

Revision history for this message
Darsey Litzenberger (dlitz) wrote :

Hm. Ok, I agree in principle; I wonder if this will break for some users, but probably not.

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.