Selecting Cryptographic Key Sizes
Objective
The objective of this problem is to choose appropriate key sizes for symmetric and public key algorithms to satisfy protection goals.
Scenario
According to the DoJ Declassification website, classified documents are considered for automatic declassification 25 years after their creation. We take this to imply that a security system must be able to protect classified information for at least 25 years after its creation date. In addition, when a system is designed, it is expected that it will be in use for some period of time, we'll say for 10 years. As a designer, this means we must be choosing cryptographic parameters to be secure for 35 years: a document that is created in the system on its last day in service must still be secure for 25 years from its creation date.
It is your responsibility to choose the cryptograhpic parameters for the file encryption portion of the system. Each file is to be encrypted using a symmetric key algorithm, using a different, randomly-generated key K for each file. A public key algorithm will be used to encrypt K using the public key of the file owner. The encrypted key, which we denote by K', will be stored along with the encrypted file. The preferred cryptographic algorithms are AES and RSA, although you may propose alternative algorithms if you have a strong case to do so.
To determine the key sizes, you need to have an idea of what an adversary can expect to do over the next 35 years. Since you are protecting classified information, you can assume that adversaries exist and are well-funded. You will need to estimate what a well-funded adversary could achieve today and then extrapolate to estimate what they could achieve in the future.
Procedure
You need to produce a symmetric key size and a RSA modulus size, both in bits, such that the system will be secure for 35 years. If you choose to use a different procedure, please explain your rationale.
-
Determine current capability for symmetric key assuming a
brute-force attack
- Establish baseline timing information, e.g. AES decryptions per second, on a modern CPU. OpenSSL can produce this sort of timing information for you.
- Research current supercomputer capability and scale your timing information to estimate current maximum decryptions per second on a supercomputer.
- Consider further scaling the decryption rate by a constant factor to allow for the fact that your adversary is likely a well-funded nation-state.
-
Estimate future symmetric decryption rates and set key size
- Use Moore's Law to estimate decryption rates in 35 years.
- Determine the key size necessary to ensure that, 35 years from now, an adversary could not decrypt a single file by brute-force attack using their computing resources for a full month.
-
Estimate RSA parameter sizes that provide security equivalent
to your symmetric key size.
- Read about the factorization of a 768-bit RSA modulus completed in 2010. Estimate the modulus size that could be factored today by a well-funded adversary using one year of compute resources. Justify your estimate.
- Use Moore's Law to predict how much more work an adversary could do in 35 years (you've probably done this already when determining the symmetric key size). Express this as a multiplicative constant, i.e. “in 35 years, and adversary could do C times as much computation as today.”
- The complexity of GNFS is expressed in L-notation. L-notation cannot be used to directly estimate the cost of factoring a number of a given size, but it can be used to estimate the relative difficulty of factoring two numbers of different sizes. Use the ratio of two L-expressions to determine the size of an integer n such that factoring n with the GNFS is C times harder than what can be factored today. Note: the argument n to the L-expression is the actual integer n, not its size in bits; the size in bits is proportional to log n.
Additional Questions
- Is Moore's Law appropriate for estimating computational capabilities in the distant future? Is there a better alternative?
- How would the design change if you believed a Quantum Computer with 50,000 qubits would be developed in the next 35 years?
- How could you extend this system so that the owner of a file can grant access to other users?