Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

This is mostly a terminology question, but I suppose that it is best asked and answered here. After browsing the Internet I have come across a fair number of completely different definitions of the term "key stretching" and would like to know if there is any consensus in the research literature about how the term is to be used, or, perhaps, that it should be avoided exactly because there is no consensus.

Some of the meanings:

  1. Key stretching is the method of applying a KDF or PRF to some input, as to produce output of arbitrary length. Some uses RFC 5931, gnu.org. The same feature is called key expansion in e.g. RFC 5869.
  2. Stretching the entropy of the input by increasing the complexity of the derivation process. Found this on Wikipedia and in this paper by the reputable authors Bruce Schneier, David Wagner et.al. However, it seems these authors intended this feature should be used in particular when there is a need for the first feature (key expansion).
  3. Increase the length of the input, e.g. by concatenating it with a public salt, before applying the KDF to it. Both this feature and the second is allegedly sometimes called Key Strengthening.

Are there any better terms that are more likely to be understood correctly without having to repeat the definition each time they are used? Key Expansion for the first, Key Hardening for the second, and Salting for the third?

On the other hand, the term key expansion seems to also often be used to describe the feature of cipher algorithm key schedules, when the input key is expanded into the round keys. It would be better to have a term that distinguishes between the output of a KDF and the intermediary output of a key schedule.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

In my practice (Smart Cards, often using DES and increasingly AES)

  • Key Expansion is often used to designate production of subkeys in a block cipher. This process is often a mere bit extraction, as part of the algorithm's Key Schedule.
  • Key Diversification is, almost exclusively, the process of producing a device key from its serial number (or other identifier) and a master key. This transformation must be such that compromise of the key of some devices does not compromise the master key, or the key of other devices.
  • Key Derivation is a general term for producing a key from another key. It is often used for Key Diversification, or the process of expanding one key to several keys of different function (e.g. a confidentiality key for CBC encryption, and an integrity key for CBC-MAC), or the process of obtaining a session key from a long-term key. The term Key Derivation tends to imply that the derived key does not leak from the original key (as illustrated in Key Diversification).

Further, I would understand Key Strengthening or Key Hardening (exclusively), or Key Stretching (less specifically) as a purposely compute-intensive transformation of a key, effectively increasing its resistance to brute force search by a parameterizable factor, e.g. in PBKDF2 or Scrypt. Key Stretching is attested in this meaning, as stated in the question. But I have also seen Key Stretching used for the process of obtaining several keys from a single one, without intend to slowdown a brute force search.

And I would understand Key Salting as the ages-old process of adding (public or mildly secret) salt to a key (of low-entropy such as a password), so that at least identical keys do not degenerate into identical cryptograms, without indication of the deliberate introduction of a compute-intensive transformation as in Key Strengthening.

I am not an authority, English is my second language, and I have somewhat changed my mind on the usual meaning of Key Stretching.

share|improve this answer
1  
The purpose of Schneier et.al. article, if you read the abstract, was to discuss how to convert legacy cryptosystems with low entropy keys, into cryptosystems with, say, 112 bit keys or 128 bit keys. When you do that, it is obviously sound not only to use a KDF that allows you to derive longer keys, but also to somehow make sure that the changes are matched by an increased hardness to search the key space. However, to my recollection the usefulness of the paper was discussed at length, because you can't really iterate yourself to 128 bit security if you start with 40 bit keys. –  Henrick Hellström Mar 11 '12 at 7:36
1  
...so, didn't the first meaning of key stretching (to describe the feature of a KDF to derive keys of arbitrary length) emerge from those discussions, in favor of the key strengthening feature, that can't always be made to match the required key expansion anyway? –  Henrick Hellström Mar 11 '12 at 8:33
    
@HenrickHellström: I second that. –  fgrieu Mar 11 '12 at 10:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.