Thursday, July 11, 2013

SaltStack: RSA e = d = 1

An instance of textbook RSA has three parameters: e, d, and n, where e = d-1 (mod phi(n)). Encryption of a message m is me, and decryption of a ciphertext c is cd = (me)d = med = m1 = m.

When you set e = 1, encrypting a message does not change it, since raising any number to the power of 1 does not change it. SaltStack was using 1 as their RSA public key (e), so encryption was doing nothing:

 @@ -47,7 +47,7 @@ def gen_keys(keydir, keyname, keysize, user=None):  
    priv = '{0}.pem'.format(base)  
    pub = '{0}.pub'.format(base)  
 -  gen = RSA.gen_key(keysize, 1, callback=lambda x, y, z: None)  
 +  gen = RSA.gen_key(keysize, 65537, callback=lambda x, y, z: None)  
    cumask = os.umask(191)  
    gen.save_key(priv, None)  

What really amazes me is that the library they're using, M2Crypto, lets you do this without any kind of error or warning.

Lessons Learned:
  • Have a professional cryptographer review your parameter choices.
  • Write unit tests to check that messages can't be decrypted with a different key (edit: This might not catch the problem, see the comments).
  • Before using a cryptography library, it's a necessary to understand something about what it's doing behind the scenes.


  1. Actually, the message can't be decrypted with a different key. That's not the nature of the problem -- the error comes before decryption; decryption itself works fine. The problem is that you don't need to decrypt in the first place. The right test to run is that the message differs from the ciphertext. If testing for the specific key of 1, you can run this as a unit test, but when writing cryptographic libraries, you really need to test a lot of keys to get some kind of certainty that this can't come up. Randomized or bounded-exhaustive testing seems a better tool for the job.

    1. Testing that the ciphertext is not the same as the plaintext wouldn't catch it, because the library should be applying padding, which makes it different.

      You could encrypt the same plaintext twice with "different" keys, then check that both ciphertexts are different. But even that wouldn't work, because the padding probably incorporates randomness.

      Decrypting with a "different" key is the only way, that I can think of, to reliably test for this using only the library's public API and not make assumptions about what it's doing with padding. Even though a different private key would have a different 'n', it would decrypt properly since decryption with d=1 is the identity operation for all n. Even then, the padding might incorporate 'n'...

      It's probably best to straight up check that the public key isn't 1.

      There are other poor choices for the public key, that would pass all of the above tests, so I think in this case it's best to go with a standard, like 65537, and test that the public key always has that value.