Using dynamic keys

Question

It is intuitively clear that, the less materials a cryptanalyst has available to work on, the lower would be his chance of success. This implies that the security of encryption of a message could be enhanced, if more than one keys are employed to process a given message (in comparison to the common practice of using one single key). Now from a user-given key one could dynamically derive (at regular intervals or not, using the same encryption algorithm or not) e.g. in counter mode of a block cipher a number of keys and use these to perform the actual encryption of a given message. Of course this key derivation operation involves certain processing cost but seems to be under circumstances nonetheless able to be a viable practical option of obtaining some additional security, isn't it?

Answer 1

As a general rule, I advise against designing security through the use of voodoo ritual. Unfortunately, frequent key renewal has all the hallmarks of a procedure meant to appease fearsome deities, as opposed to, say, science.

Let's see from where this idea comes from. We have to go back about one century, when cryptography was a military tool and was based upon a complex network of shared keys and passwords (this was before the invention of asymmetric cryptography). Since a secret which is shared is no longer "very secret", it was assumed that, in a standing army, the enemy could occasionally learn some keys; also, algorithms of that time were quite weak and could indeed be broken by hand (no computers at that time). Practical breakage was made easier by the quantity of data encrypted with a single key.

Thus began the practice of changing keys often: as a "cleansing operation" to kick out an assumed number of partially successful attackers, and to dance around the inherent weaknesses of the algorithms which were known at that time.

But times have changed. This was a century ago. Since then, a number of technologies have substantially modified the field, in particular a nifty kind of device called the computer. Modern cryptographic algorithms do not become weaker with the quantity of encrypted data (or, rather, the point where they become weaker is when the quantity of encrypted data is billions of billions of times the total size of all data which has ever existed on Earth). Also, encryption keys are no longer manipulated "by hand"; for instance, in a SSL connection, the key which is used to encrypt data is generated by the client implementation and used by both client and server, i.e. software on both sides. The keys which are potentially subject to theft or long-term attacks are the asymmetric keys (RSA and its ilk), not the actual symmetric data encryption keys.

Therefore, the conditions which made key renewal a good idea have disappeared. Nowadays, key renewal is applied to give a feeling of safety to people who think about cryptography as if we were still a horse-powered army. And, in practice, it s quite the opposite: for the sake of that feeling, extra complexity is added (this key renewal and stretching won't happen by itself) leading to new possibilities for vulnerabilities. Complexity is the bane of security.

Thus, key renewal like the kind you advocate tends to decrease overall security, not to increase it. Intuitive notions notwithstanding. The whole point of computers is to handle data in amounts which far exceed what the human brain can grasp, even intuitively.

Answer 2

There are some cases where key derivation is used to improve security.

A form of key derivation is key diversification which prevents an attacker that obtains a derived key to access information about the original secret or the other derived keys.

Key derivation is also used in systems that only support weak keys or keys without cryptographic properties.

Sometimes new and different keys have to be generated all the time because encrypting a lot of data exposes the original key. An example is wireless encryption protocols where key renewal is a feature of the protocol.

Answer 3

TL;DR in bold:

Basically what you have proposed is the basic premise behind "seeding" a pseudo-random number generator; the object is to turn a finite, known input into an infinite, unpredictable output. As long as the unpredictability holds, a cipher keyed from this output will behave like a one-time pad (OTPs are provably uncrackable if the pad's values are truly random and the sequence of a single pad is never used twice). A deterministic algorithm that could do this in practice would be the last word in symmetric cryptography.

The problem is that, in information theory terms, any pseudo-random bitstream has the same entropy as that of the original seed value. As a result, there is no algorithm that could do what is described in the previous paragraph. Every PRNG will, eventually, repeat the exact same stream of random bits, and long before that, a pattern will emerge that will allow the next bit of output, given knowledge of all previous bits, to be predicted with 100% accuracy. That's because a PRNG is a pseudo-random number generator; it produces numbers that, up to some limit, are indistinguishable from random, based on some mathematical formula such as the modular congruence used by Blum Blum Shub.

In addition, it gets even simpler; knowledge of the seed would allow someone to exactly reproduce the bitstream being observed. As used in cryptography, that would be the point; to plug in the same key as a seed to this PRNG and have it feed you the same stream used to encrypt, so you can decrypt. However, as there are a finite number of seed values for most PRNGs, and a PRNG, given the same seed, produces the same bitstream, there are only as many possible bitstreams as there are seed values. The same holds for other "random oracles", such as hash functions; because the hash of a specified message using a specified algorithm is deterministic, if you know the input you can produce the hash trivially, which is half of the point (the other half being that knowing the output shouldn't help you compute the input that produced it).

In the case of PINs, passwords, or other relatively low-entropy data, this makes a brute force of an algorithm only as difficult as the number of possible inputs for the specific system, not the number of possible outputs of the algorithm given any input. For instance, take a 4-digit PIN. There are 10,000 possible 4-decimal-digit values, from 0000 to 9999. There are no other possibilities without increasing the number of digits or increasing the number of values for each digit (moving to hexadecimal numbers, for instance). Therefore, finding the correct pin requires, worst-case, trying all 10,000 possibilities.

Hashing one of these 4-digit PINs with SHA-512 will produce a 512-bit number, which theoretically has 2^512 possibilities; however, because each hash value was produced from one of only 10,000 possible PINs, there are only 10,000 possible hash values to consider. The hash thus only "translates" these 10,000 initial values into a larger number space; the fact that there are only 10,000 hash values, and the range of possible inputs to try, are not secrets.

If you then hashed the hashes, and appended the second hash onto the first, you would have hash values 1024 bits long, and theoretically could have any of 2^1024 values; however, because the second hash was produced deterministically from the first, which could only have 2^512 values, the second hash can only have one possible value for each of the 2^512 possibilities for the first, and because our first hash was in fact produced by an input with only 10,000 possibilities, there are still only 10,000 possible 1024-bit hashes that can be produced in this way. You could continue this as many times as you like, producing a bitstream as long as you want, and there will still only be 10,000 possible bitstreams of any arbitrary length produced from 10,000 possible 4-digit PINs.

The value of key stretching, therefore, is in the required time and work; key derivation functions designed to increase password security provide their primary value by making the operation to derive one key from one password a minor inconvenience for a user who knows the correct password, but making repeating that operation the required number of times to find the correct password by brute force unfeasible. Again, the key-stretching process and the required computational time is still dependent on the input entropy; passwords, while relatively low-entropy for their length, still have a lot of possibilities if you know nothing about how the password is constructed (sometimes even if you do), so the processing time can be secure even at relatively short time delays, say one second (a password with 30 bits of entropy would take about 2000 years to brute-force at one try per second). A 4-digit pin can't be "stretched" enough to make brute-forcing it unfeasible in this way, because the desired time required for an attacker to try them all (say 3 years, the life of the average ATM/debit card, assuming you changed your PIN with every new card) would make the time required to generate one PIN-based key unfeasible (2 minutes, 37 seconds, much longer than you'd want to wait at an ATM).

AJ Henderson is correct that your proposed scheme is not unlike the well-known Counter (CTR) mode of a block cipher, where a nonce generated by a reproducible series is combined with each block of plaintext before passing it through the keyed cipher, thus further differentiating the various ciphertexts even if (as is rather common) the blocks have the same or very similar data.

However, Counter mode is called that because the system is just as secure when using a sequential series of number bitmasks (0x000...01, 0x000...02, 0x000...03, etc) for the nonces as when using a pseudo-random series; back to the previous point, because you have to know how to generate the same sequence of nonces that was used to encrypt in order to decrypt, that sequence is not a "secret" like the key is, no matter how apparently random it looks, and thus does not add any additional information entropy to the process. Thus, Counter mode typically uses a system of nonce generation that is exactly that; a counter.

The advantage of the nonces in Counter mode is that they make each block of ciphertext different, even if the blocks of plaintext were identical, thus preventing someone who knew the ciphertext from seeing two identical blocks and knowing that they were produced by the same plaintext. If two CTR-produced ciphertext blocks are identical, it's more or less a coincidence; the attacker would have to be able to separate the effect the nonce had on the plaintext from the effect that the cipher did, and if that is possible, it is a weakness of the cipher, not the Counter mode of operation. That holds, as previously stated, regardless of the exact sequence of nonces or the algorithm that produces them.

Answer 4

It sounds like you are described a CTR (counter) mode of operation of a cipher. This is an established mode of making a parallelizable encryption and decryption because the block key is derived from a counter off the initial key and IV. And yes, large amounts of information can leak if you are not using a random initialization vector (the starting state for XORs) and having each block apply the key differently (or effectively a "different" key). It is still derived, so it doesn't provide additional entropy though, it just helps prevent reduction of entropy through analysis.

Further, you could increase the key length (not by a pattern, but actually picking a longer random key) (effectively making "multiple" different unrelated keys) which would increase entropy, but would still be easier to analyze if there wasn't some kind of chaining in it's application to a much longer stream.