PyCrypto generates bad signatures

Question

I'm having major problems with PyCrypto, as the code below demonstrates. One issue is that the test case does not fail in a repeatable way, but has different causes on different platforms using different keys.

Note that the test case provides two sets of keys for Alice and Bob, the first generated by OpenSSL and the second generated by PyCrypto (uncomment the section 'Alternate keys').

The test case is a simple round trip:

1. Alice generates a symmetric key and encrypts the data
2. Alice encrypts the symmetric key with Bob's public key, then signs the encrypted key with her private key (hashes are not used in this simple test case).
3. Bob verifies the signature with Alice's public key and decrypts the symmetric key with his private key.
4. Bob decrypts the data with the symmetric key.

Here are the results of some some sample runs:

On Linux with OpenSSL keys

attempts: 1000
 success: 0
mismatch: 0
    fail: 1000
  Bad signature = 993
  Ciphertext too large = 7

On Linux with PyCrypto keys

attempts: 1000
 success: 673
mismatch: 0
    fail: 327
  AES key must be either 16, 24, or 32 bytes long = 3
  Ciphertext too large = 324

On Windows with OpenSSL keys

attempts: 1000
 success: 993
mismatch: 0
    fail: 7
  AES key must be either 16, 24, or 32 bytes long = 3
  Bad signature = 4

On Windows with PyCrypto keys

attempts: 1000
 success: 994
mismatch: 0
    fail: 6
  AES key must be either 16, 24, or 32 bytes long = 6

Here is the test case:

from Crypto import Random
from Crypto.PublicKey import RSA
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from base64 import b64encode, b64decode

rng = Random.new().read

# openssl genrsa -out alice.rsa 1024
alice_private_key = RSA.importKey('''
-----BEGIN RSA PRIVATE KEY-----
MIICXAIBAAKBgQDcWasedZQPkg+//IrJbn/ndn0msT999kejgO0w3mzWSS66Rk3o
Nab/pjWFFp9t6hBlFuERCyyqjwFbqrk0fPeLJBsKQ3TOxDTXdLd50nIPZFgbBmtP
khKTd7tydB6GacMsLqrwI7IlJZcD7ts2quBTNgQAonkr2FJaWyJtTbb95QIDAQAB
AoGAbnIffD/w+7D5ZgCeTAKv54OTjV5QdcGI/OI1gUYrhWjfHAz7JcYms4NK1i+V
r9EfcJv8Kb/RHphZVOoItM9if5Rvaf890r4T+MUUZbl4E7LwEWBuASe6RPyI8Dao
uTOomFlKDjT5VbcBx+WOD+upmrjAwcolyLVulQ5g9Z59pW0CQQDybUKrz4EVzKMx
rpAx0gIzkvNpe/4gxXBueyWqUTASiSwojyZFY6g25KVMuW16fSsRStptm6NpumxB
XVojid7nAkEA6K/7VZd2eMq0O/MP2LT1n6dzx7130Y1g9HWbjsLTRWevGYytcD0O
ldebQxgCbLftuvkcpRtbmIjOsbji4dRfUwJBAJiQolC1+irZ6iouDZkM7U2/wWg1
HC1LlAIzhfS1u2cu5Jdx30fz+7zwEAdE+t0HQL9VODmapTC4ncBVG5EaBykCQB0L
4s8DckmP3EHjjKXbqRG+AIj9kNh60pCRodKHZYIzeDszQW9SX+C6omoUtDDIIQgH
EtlVefCnm026K7BPJ3sCQAdhylJJ/ePSiY9QriPG/KTZR2aprF8eM1UrRebH2S0S
4hZZmqYH/T/akHVxPsyuqyzoZGbVj6kauRhWbBLmpWk=
-----END RSA PRIVATE KEY-----
'''.strip())

# openssl rsa -in alice.rsa -out alice.pub -pubout
alice_public_key = RSA.importKey('''
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDcWasedZQPkg+//IrJbn/ndn0m
sT999kejgO0w3mzWSS66Rk3oNab/pjWFFp9t6hBlFuERCyyqjwFbqrk0fPeLJBsK
Q3TOxDTXdLd50nIPZFgbBmtPkhKTd7tydB6GacMsLqrwI7IlJZcD7ts2quBTNgQA
onkr2FJaWyJtTbb95QIDAQAB
-----END PUBLIC KEY-----
'''.strip())

# openssl genrsa -out bob.rsa 1024
bob_private_key = RSA.importKey('''
-----BEGIN RSA PRIVATE KEY-----
MIICXwIBAAKBgQDddMPxMRIe34mNYbldimaZ1j4Zw/kqPHkOfbzBhp3XR254eSQO
Ne9DgaLQhw16n4o3FFP8aijlotw/LUfKosEldmiCFuZdTiMP/49a5CbQ/End+Z38
tHIzmGv7qjtkU7K8Eu/J5/y3wqBNAkfejC4j8MNxg8eBBGTq8okra8in8wIDAQAB
AoGBAKmueSAKME81iiipMyWoEPtYe9a0IOsq0Lq4vvMtmS1FTzDB6U12J/D6mGzc
vggxy+5uBfgGw3VINye1IyfxUrlbD0iycMY0dZUgm0QetOOnv8ip/cSKpAilvK+B
H4q9ES0L2M/XOZoFgSmg58HS9UJfcXz95un8WRxSvn26lH3BAkEA/VZoZmTJ5W5f
NwqxbWmOokRn+hBOl1hOvCDbRjuMKWNdQSFSmsQtjbGorNYfT4qrL4SxPbE3ogAe
Pw9zxHbWkwJBAN/IlQtCfncEZ/3wYCS2DxEbO5NPEBTUQgOGzauQ4/lzU5k73gXL
ZiHZYdwNUPY359k+E26AAEBG5A+riI1VZSECQQCYR7Jlqjv6H4g4a8MPQ54rR/dA
R0EWlExvpUhpRS4RStspZUBkK3w+agY8LlGP3Ijd/WMU9Eu+o1eLDFzIQa7lAkEA
kViwJV4M0bSU7oRfjbiJ1KyBZ04kvcKXFb9KejJjP7O+Cnqt28meDkIoo0oq2aC5
/4moCU8t2pGwstTQnitmwQJBAPSIOKujoLp23e4KCbB8ax9meY+2jaWTtf5FPpSV
tHs1WhlITxCowbjF+aWGsypitdT596cHFKAV0Om89vf6R0U=
-----END RSA PRIVATE KEY-----
'''.strip())

# openssl rsa -in bob.rsa -out bob.pub -pubout
bob_public_key = RSA.importKey('''
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDddMPxMRIe34mNYbldimaZ1j4Z
w/kqPHkOfbzBhp3XR254eSQONe9DgaLQhw16n4o3FFP8aijlotw/LUfKosEldmiC
FuZdTiMP/49a5CbQ/End+Z38tHIzmGv7qjtkU7K8Eu/J5/y3wqBNAkfejC4j8MNx
g8eBBGTq8okra8in8wIDAQAB
-----END PUBLIC KEY-----
'''.strip())

# Alternate keys (uncomment for PyCrypto keys)
#alice_private_key = RSA.generate(1024, rng)
#alice_public_key = alice_private_key.publickey()
#bob_private_key = RSA.generate(1024, rng)
#bob_public_key = bob_private_key.publickey()

def generate(data, signature_key, encryption_key):
    # Generate encrypted data
    symmetric_key = rng(16)
    symmetric_cipher = AES.new(symmetric_key)
    padded_data = data + (' ' * (16 - divmod(len(data), 16)[1]))
    encrypted_data = bytes(symmetric_cipher.encrypt(padded_data))

    # Encrypt the symmetric key
    encrypted_key = bytes(encryption_key.encrypt(symmetric_key, None)[0])

    # Sign the encrypted key
    signature = long_to_bytes(signature_key.sign(encrypted_key, None)[0])

    return encrypted_key, signature, encrypted_data

def validate(encrypted_key, signature, encrypted_data, verification_key, decryption_key):
    # Verify the signature
    if not verification_key.verify(encrypted_key, (bytes_to_long(signature),)):
        raise Exception("Bad signature")

    # Decrypt the key
    symmetric_key = decryption_key.decrypt((encrypted_key,))

    # Decrypt the data
    symmetric_cipher = AES.new(symmetric_key)
    return symmetric_cipher.decrypt(encrypted_data).strip()


def test():
    attempts = 1000
    success = 0
    mismatch = 0
    fail = 0
    causes = {}
    for _ in range(attempts):
        data = b64encode(Random.new().read(16))
        try:
            encrypted_key, signature, encrypted_data = \
                generate(data, alice_private_key, bob_public_key)
            result = validate(encrypted_key, signature, 
                encrypted_data, alice_public_key, bob_private_key)
            if result == data:
                success += 1
            else:
                mismatch += 1
        except Exception as e:
            fail += 1
            reason = str(e)
            if reason in causes:
                causes[reason] += 1
            else:
                causes[reason] = 1

    print("attempts: %d" % attempts)
    print(" success: %d" % success)
    print("mismatch: %d" % mismatch)
    print("    fail: %d" % fail)
    for cause, count in causes.items():
        print("  %s = %d" % (cause, count))


test()

Is there any reason why PyCrypto seems to be such a basket case?

Answer 1

First, I would consider the cases where the OpenSSL keys are used. The most important fact is that Bob's RSA modulus (bn) is slightly smaller than Alice's RSA modulus (an).

The error Ciphertext too big shows up at the "sender" (that is, within the generation function). The ciphertext you "sign" is guaranteed to be smaller than an (because encryption is computed modulo an) but it may sometimes (due to the plaintext being random) happen to be larger than bn. In that case, signature is not possible.

As far as I can tell, the check is performed and an exception is raised only if you have the GMP library installed, which is often the case on Linux systems. On Windows, it is difficult to install such library, and pycrypto relies on pure python code. The exception will be not be raised in that case (though it should, the two versions should behave in the same way), and you will silently get the wrong value as signature (Bad signature).

The error AES key must be either 16, 24, or 32 bytes long shows up when your random AES key starts with 0x00. Since the RSA primitive converts the byte string into an integer, the leading zero will lost in the process, and you will get back that error at the receiving end.

If you generate RSA keys on the fly, in 50% of the cases bn>an and you will see fewer errors.

I am not able to understand why 100% of the tests fail on Linux with OpenSSL keys, but I guess there is a similar reason to explain that.

In general (and this holds also for all other crypto libraries), the root cause of all problems is that you are using the raw RSA mechanisms. Beside considerations about limitations and correct way to use the API, you have a big security hole. Some form of secure padding must always be used, otherwise an attacker can easily break your scheme.

In PyCrypto, proper protocols are available via the PKCS#1 modules for both RSA signatures and RSA encryption. However, mind that signature must be done on the message hash (e.g. SHA1), and encryption on a payload which is considerably smaller than the RSA modulus.