Limits when decrypting private keys

An encrypted private key (PKCS#8 in DER or PEM format, or OpenSSH) states how expensive the derivation of its decryption key from the passphrase is: the iteration count of PBKDF2, the cost parameters of scrypt, or the number of rounds of bcrypt (for OpenSSH keys). A malicious key can therefore require an extremely expensive derivation, and tie up the CPU for hours, or all the memory, before the passphrase is even checked.

For this reason, the functions that decrypt such keys reject the ones above two limits:

  • max_iteration_count, for the time;

  • max_memory, for the memory (in bytes).

Both are keyword arguments of:

The limits do not apply when encrypting a key (for instance, with export_key()): the caller chooses the parameters then.

A similar limit, max_cost, protects Crypto.Protocol.KDF.bcrypt_check(), when it verifies a password against a bcrypt hash that states its own cost (see bcrypt password hashes).

Default limits

By default (max_iteration_count=None and max_memory=None), the limits depend on the key derivation function, so that the derivation takes at most about one minute on a recent x86-64 laptop, with a single thread:

Key derivation

Default max_iteration_count

PBKDF2 (with any hash), and PBKDF1 (legacy PBES1 algorithms)

50,000,000 iterations

scrypt

N·r·p/8 up to 225 (33,554,432)

bcrypt_pbkdf (OpenSSH private keys)

16,384 rounds

Key derivation

Default max_memory

scrypt

256 MiB, for all threads together

PBKDF1, PBKDF2, bcrypt_pbkdf

(they need very little memory)

These limits are far above the recommended minimum costs for passwords: for instance, OWASP recommends at least 600,000 iterations for PBKDF2-HMAC-SHA256, and N = 217 with r = 8 and p = 1 for scrypt (128 MiB, and a cost N·r·p/8 of 217).

With PBKDF2, the time of one iteration depends on the hash, and on the length of its digest. When the digest is shorter than the key (for instance, the 28 bytes of SHA-512/224 or SHA3-224, for a 32-byte AES-256 key), PBKDF2 has to compute two blocks of output, each one with the full iteration count: then, each iteration costs twice as much. These are the slowest cases, and the ones for which the default limit takes about one minute.

The scrypt cost

The total work of scrypt (its CPU time) is proportional to N·r·p: for this reason, max_iteration_count limits N·r·p/8 (rounded up) and not N alone. For the usual r = 8 and p = 1, it is just N.

scrypt also does some work in proportion to r·p only, whatever N is (two PBKDF2 steps over 128·r·p bytes): about as much as with N = 128. To account for it, N counts as 1024 in the cost when it is smaller. This changes nothing for real keys, whose N is larger.

The p flows of scrypt are independent, and they can run on several threads (see below). With t threads, each one computes at most ⌈p/t⌉ flows, so the elapsed time is proportional to N·r·⌈p/t⌉: that is the best case, when t CPU cores are free. The limit is on the total work instead, which does not depend on the number of threads, nor on how busy the CPU is.

For instance, the default max_iteration_count accepts N = 220 with r = 8 and p = 32, or N = 214 with r = 8 and p = 2048 (both at the limit); it rejects N = 226 with r = 8 and p = 1. The memory is limited separately (see below): by default, the first example is rejected anyway, because each thread would need 1 GiB. The second example takes about 47 seconds on one thread, and at least 6 seconds on 8 threads (16 MiB for each one).

Memory and threads

Only scrypt needs a significant amount of memory:

  • 128·(N+2)·r bytes for each thread, so a little more than 128·N·r bytes;

  • 256·r·p bytes for all the flows together (their input and their output).

With p larger than 1, scrypt can run on up to p threads, as requested with the threads parameter (see Crypto.Protocol.KDF.scrypt()).

max_memory limits the total of all threads together, not each thread. If the requested threads do not fit, fewer are used, down to one; if a single thread does not fit, the key is rejected.

For instance, with the default limit of 256 MiB:

  • N = 216 and r = 8 (a little more than 64 MiB for each thread): at most 3 threads are used, even with threads=4;

  • N = 217 and r = 8 (a little more than 128 MiB for each thread): only 1 thread is used;

  • N = 218 and r = 8 (a little more than 256 MiB for one thread): the key is rejected.

Keys created by OpenSSL (at most 32 MiB) and by this library with the default parameters (16 MiB) are well within the default limit.

OpenSSH keys and bcrypt

An encrypted OpenSSH private key (-----BEGIN OPENSSH PRIVATE KEY-----) derives its key and IV with bcrypt_pbkdf: at every round, it computes two bcrypt hashes with cost 6 (about 3 ms in total on a recent x86-64 laptop, as the two run interleaved on a single core). The key states the number of rounds (up to 232-1), and max_iteration_count limits it. The default limit of 16,384 rounds takes about one minute, and it is far above what OpenSSH uses (16 rounds by default, with ssh-keygen -a to change it).

A key with less than one round is rejected, before any key derivation. bcrypt needs very little memory (about 8 KiB), so max_memory does not apply.

bcrypt password hashes

Crypto.Protocol.KDF.bcrypt_check() verifies a password against a bcrypt hash, which states its own cost, from 4 to 31. The time doubles at every step: cost 12 takes about 0.2 seconds on a recent x86-64 laptop, but cost 31 about one day. A hash from an untrusted source (for instance, user accounts imported from elsewhere) could therefore tie up the CPU.

For this reason, bcrypt_check() rejects a hash whose cost is above max_cost, before any hashing, with Crypto.KdfIterationLimitError (a ValueError):

  • by default (max_cost=None), the limit is 20, about one minute;

  • an explicit max_cost is the highest cost allowed;

  • with max_cost=0, no limit applies.

The usual costs for passwords (10 to 14) are well within the default limit.

Explicit limits

An explicit max_iteration_count is the maximum number of iterations for PBKDF1 and PBKDF2, whatever the hash, the maximum N·r·p/8 for scrypt, and the maximum number of rounds for bcrypt_pbkdf (OpenSSH keys). An explicit max_memory is the maximum number of bytes, for all threads together.

Warning

The unit of max_iteration_count depends on the key derivation, and so does the time of one unit: about 0.1 to 1 microseconds for PBKDF2, but 3 milliseconds for bcrypt_pbkdf. A value chosen for PBKDF2 (for instance, 10,000,000) would allow an OpenSSH key with as many rounds, that is, about 9 hours. When the type of the key is not known in advance, keep the default (None).

With max_iteration_count=0 or max_memory=0, the corresponding limit does not apply. Only use 0 with keys that come from a trusted source.

Both parameters must be integers (or None), and not negative: otherwise, TypeError or ValueError is raised, even if the key turns out not to be encrypted.

Invalid parameters

Keys with parameters that make no sense are rejected with a ValueError, before any key derivation: an iteration count of PBKDF1 or PBKDF2 lower than 1, or scrypt parameters other than a power of 2 (and at least 2) for N, and positive values for r and p (RFC 7914).

The private key inside an RSA PKCS#8 key must be an RSAPrivateKey (PKCS#1, RFC 8017): another container (for instance, another encrypted PKCS#8 key) is rejected.

Errors

When a key is above a limit, the functions raise:

Both are subclasses of Crypto.KdfLimitError, which is a ValueError. Their message says which value is too high, and which limit applies.

For instance, to accept a trusted key that needs more memory than the default:

>>> from Crypto import KdfMemoryLimitError
>>> from Crypto.PublicKey import ECC
>>>
>>> try:
>>>     key = ECC.import_key(encrypted_key, passphrase)
>>> except KdfMemoryLimitError:
>>>     key = ECC.import_key(encrypted_key, passphrase, max_memory=2**30)

What is not covered