Samuel R. Buss ^{1}
Department of Mathematics
Univ. of Calif., San Diego

Peter N. Yianilos ^{2}
NEC Research Institute
Princeton, N.J.
June 1999
Our short secret key cryptosystems are based the use of slowed down key generation, as advocated by Quisquater, et al. We use a ``slow oneway'' function to convert a short secret key into an expanded key, which can be used in a conventional (long key) cryptosystem. Although the notion of slowdown in cryptographic systems is wellknown, our analysis suggests that it is far more useful than is generally recognized.
The first contribution of this paper is the analysis of the security of short key cryptosystems and the tradeoffs between key length, amount of slowdown, and security. An important aspect of our analysis is the identification of the advantages of extremely slow slowdown functions for key generation. The second contribution is the inclusion of an auxiliary, nonsecret key; which we argue is necessary to maintain security, and also allows a single short key to be used for multiple independently secure communication sessions, and to be used as a master key in key management protocols.
Keywords: Cryptography, short secret key, slow oneway functions, security, key management.
There are a wide variety of keybased cryptosystems which allow secret communication based on the use of keys which control encryption and decryption algorithms. In symmetric key systems, two parties share a common secret key and use common encryption and decryption methods. In public key cryptosystems, one party holds a secret key and the other party holds a public key (and often another set of secret/public keys are used dually in conjunction).^{3}
The length of the secret key is an important parameter of a cryptosystem which affects the security of the cryptosystem. In order to have good security in practical symmetric key systems the secret key is typically of length 90 bits or longer; in public key systems, the secret key may need to be 1000 bits or longer for good security. This paper discusses a method for using short secret keys, of length approximately 40 bits, which achieve security equivalent to the security of conventional (long key) cryptosystems. Our short key cryptosystems can be used as either symmetric cryptosystems or as public key cryptosystems.
Perhaps the main advantage of the short key cryptosystem lies in key management. It is wellknown that users have trouble remembering secret keys without writing them down; for 1000 bit keys, it moreorless necessary to store the key electronically since such a long key can not be reliably typed in repeatedly. However, the 40 bit key of our short key cryptosystem is much easier to remember: this means that many key management issues can be avoided by the simple expedient of the user memorizing his or her key. This means that the short key cryptosystems are more secure against attacks which electronically access the user's computers and against attacks involving physical access or theft.
It is generally believed that a secret key must be sufficiently large in order to prevent attacks which exhaustively search the key space. In addition, one must assume that an adversary carrying out an exhaustive key search attack may construct special purpose hardware to test putative keys. In addition, the adversary may be able to test many keys simultaneously in parallel, either with the use of parallel computers or by distributing the workload to many computers across networks. A typical assumption is that keys per second can be considered by a single processor and at this rate a 40 bit key may be found in roughly ten days. However, with the use of special purpose hardware it is possible to check far more than keys second: Blaze et al.[3] suggest that RC4 keys could be checked at the rate of keys per second with FPGA's and at the rate of keys per second with custom VLSI chips. For parallel attacks, using multiple machines, even the estimate of keys per second would be deemed too low. For instance, as this paper was being written in mid1998, it was reported that the EFF DES Cracker machine was capable of testing almost DES keys per second, using an array of 1500 custom VLSI chips. Thus it would seem necessary to use keys which are considerably longer than 40 bits to implement a secure system (see the discussion in [3]). This is unfortunate because short keys have the advantage that a person can easily remember them.
However, as is wellknown (see [9,10]) exhaustion attacks are proportionally slowed down by increasing the time needed to test a single key. Quisquater, Desmedt, and Davio [9] were the first to suggest that a key generation scheme might be purposefully slowed down to thwart exhaustive key search attacks. Following their idea, we investigate the advantages of short key cryptosystems based on the idea of slow key expansion. The slow key expansion inserts a long delay into the time needed to test a putative key; thereby rendering it impossible to check millions or even thousands of keys per second. We extend the work of Quisquater et al. in two ways. First, we identify the necessity of an auxiliary nonsecret key both to prevent tabledriven attacks and to allow a single short key to be used for multiple independently secure communication sessions. Second, we discuss the security of particular protocols based on short keys, and analyze the tradeoffs between key length, slowdown, and security; in particular we propose the use of extremely slow oneway functions. We also discuss the hardness properties that the slowdown function must satisfy. The result is secure cryptosystems with keys of length only 40 bits (the exact key length could be either shorter than or longer than 40 bits depending on the needs of the cryptosystem).
One of our motivations for this paper is that despite the straightforward nature of the slowdown technique used to create short key cryptosystems, its utility does not seem to be widely appreciated (see, for example, [3], which has an extensive discussion of exhaustive key search attacks, but does not mention slowdown methods).
A short key cryptosystem is built in tandem with a conventional symmetric key cryptosystem or a conventional public key cryptosystem. In our proposal, a secure cryptosystem is controlled by a short secret key, which can be expanded into an expanded key by use of a slow oneway function. A slow oneway function is a function which can be computed only with a certain delay and such that the inverse of the function cannot be feasibly computed. The expanded keys then play the role of the secret keys in the traditional symmetric key and public key systems. In addition, in order to substantially enhance security as well as to greatly increase the flexibility of the short key cryptosystem protocol, we augment the short secret key with an public auxiliary key. The auxiliary key is publicly known: it may be chosen at random or may contain identifying information. The expanded key will depend on both the private key and the auxiliary key and thus multiple expanded keys may be generated from a single secret key; this allows the same secret key to used for an extended time, even in multiple, independently secure, communication channels. In this way, a short secret key can be used as a master key in key management protocols of type proposed by [6,7].
The fact that the time required to test a potential secret key is important for the security of a cryptosystem is certainly wellknown: the best example is the use of a 35 second delay in the Unix login protocol when an incorrect userid/password combination is presented. Quisquater et al. [9] proposed a slowdown in key generation for DES. A number of other authors have suggested the use of purposely slowtocompute functions, similar in spirit to our slow functions but for other applications. These include [4] for designing uncheatable benchmarks, [5] for combating junk mail, [11] for ``timedrelease'' cryptography and [2,1] for partial key escrow. The package transform of [10] is another approach to slowing down exhaustive key search, but only applies when very long messages are being sent. Our use of an auxiliary key is similar to the `salt' used with Unix passwords, to prevent table based attacks; auxiliary keys have also been used for theoretical constructions such as the the amplification of weak oneway permutations into oneway permutations. In spite of the prior usages of slowdowns, the effectiveness of purposeful slowdowns for key generation has not been recognized; for instance, the paper [3] discusses the need for long keys for security, without ever considering the use of slowdown functions. The current work is novel firstly in that we propose the use of very slow functions, with runtime from a few seconds up to several hours or even longer, as a crucial ingredient in preserving the security of cryptosystem. Secondly, the level of security which can be achieved is surprisingly high (see the tables for section 3.3). Thirdly, with the auxiliary keys, this allows short secret keys to serve as master keys in a key management protocol.
Section 2 of this paper describes the mathematical framework for the short key cryptosystems and defines the relationships between the short secret key, the public auxiliary keys and the expanded keys. Section 3 proposes several scenarios for the use of short key cryptosystems, illustrating their use in secure communication protocols. This includes estimates on timing, on level of security, on the overhead of computing expanded keys, etc. In addition, it describes how a single secret key may be used securely as the basis for multiple expanded keys for public key cryptography. In section 4, we suggest candidates for slow oneway functions.
The fact that we focus on 40 bit secret keys is somewhat arbitrary. Indeed for certain applications, even shorter keys will be adequate but there is a tradeoff with the slowness of the slow oneway function. For other applications, where stronger security is required or less slowness can be tolerated, one may wish to use short keys which are slightly longer than 40 bits. Finally, the length 40 bits is commonly regarded as the length permitted by the U.S. government for export purposes; however, this is not a real reason to consider 40 bit keys, both because we expect future changes in cryptography laws and because under current law the 40 bit limit would not necessarily apply to short key cryptographic protocols.
A short key cryptosystem consists of
The slow oneway function requires some explanation. Recall that a oneway function is a function so that is easy to compute (in polynomial time, say), but such that is hard to invert; i.e., given a value of , it is hard to compute a value such that . We further define a function to be slow if there is a known best runtime function so that on inputs of length , can be computed in time , but cannot be computed in time substantially less than . Furthermore, we require that if distinct values are given, then any sequential machine which computes (even most of) the values of should require time approximately equal to ; in other words, computing multiple values of simultaneously is no easier than computing the values independently. A slow oneway function is a function which is both slow and oneway. Generally, if one has a slow function , and one can obtain a slow oneway function by composing with a oneway permutation.
In section 4 below, we shall and shall propose some candidates for slow oneway functions. For the moment, we just remark that the existence of slow oneway functions is not entirely obvious. In any event, until problems such as the P vs NP problem are solved, we will be unable to prove the existence of oneway functions. (It is at present the case that no conventional cryptographic system has been proved to be mathematically secure; our short key cryptosystems are no different in this regard.)
The basic protocol for short key cryptosystems is as follows. Two entities, Alice and Bob, wish to communicate securely. If the underlying conventional cryptosystem is a symmetric key system, then Alice and Bob share knowledge of . On the other hand, for a public key system then only one (Alice, say) knows the secret key . Alice, possibly jointly with Bob, chooses an auxiliary key, which we denote by . The auxiliary key may be publicly known, and thus no secure communication is needed for its choice. Both and are input to the slow oneway function yielding the value . This value is called the expanded key and must have sufficient length to be used as a key for the conventional cryptosystem , which is assumed to be secure against direct attacks on the conventional cryptosystem for that key length. Alice then uses the expanded key as the secret key for the system to communicate with Bob.
For a symmetric cryptosystem, Alice and Bob each have knowledge of the secret key , which must be exchanged securely only once. The auxiliary key can be computed publicly and even changed repeatedly. Since Bob knows both and , he uses to compute and then, with knowledge of , Alice and Bob communicate using as the secret key for the symmetric key system .
For a public key system, Alice merely uses to generate her private and public keys and for the system . As usual she keeps her private key secret and she sends her public key to Bob via a nonsecure channel, but it is unnecessary for her to publicize her auxiliary key . However, Alice does not need to save her long private key permanently, since she can always recreate it from and using .
To give a brief estimate of the security of the short key cryptosystem, assume that an attacker knows the auxiliary key and has intercepted Alice's communication to Bob and is attempting a brute force attack by trying every possible 40bit secret key. Further suppose that the computation of requires time 1 second on a single computer and that the attacker uses 10000 computers in parallel to compute for various values of . Since , it will take the attacker approximately to try all possible secret keys . This allows for a substantial level of security! If more security is needed, one can easily choose a slower slow oneway function . If less security is needed, one can use keys shorter than 40 bits.
An important role of the auxiliary key is to prevent a tablebased attack. That is, without the use of , the expanded key would depend only on and an attacker could build a table giving the expanded key corresponding to each value of . For 40 bit keys, this table would contain keys, which is certainly not too large to store with today's memory technologies. The computation effort to compute this table would be immense, but perhaps not prohibitive, since the payoff would be large, namely, the table would allow a wide variety of messages to be almost immediately decoded. However, with the use of the public key , this tablebased attack is completely thwarted since the public key should be at least as long as the secret key and thus the table would be impossibly large.
Another role of the auxiliary key is to allow a single short key to be used as a master key in key generation protocols, see section 3.2. We discuss in more detail various short key cryptosystems protocols and their security in the next section.
One of the primary reasons that short key cryptography is useful is that is greatly simplifies key management and key security. The primary reason for this is that, as will be seen from the protocols below, that the secret key may be merely memorized without any need to write it down or store it electronically. The auxiliary keys may be longer and need to stored in writing or electronically, but they are publicly known anyway, and there is no need to keep the auxiliary keys secret.
There are several traditional ways in which the short keys might be memorized. The most straightforward way would be to use alphanumeric characters to encode the key. For instance, if a key consists of a string of symbols from a 36 symbol alphabet (uppercase letters and digits), then an eight symbol string encodes a secret key of just over 41 bits, while a seven symbol string encodes a secret key of just over 36 bits.^{4}
A second possibility is to use a generalization of a method widely used by online internet service providers for user passwords. Namely, choose a set of approximately 10,322 wellknown, distinct English words. Choosing three of these words at random, e.g., ``bermaquatichappy'' or ``seismicshelflip'', encodes a secret key of 40 binary bits since . Of course, the words need to be chosen truly at random, unlike the two examples given here.^{5}Using three English words to encode a key has the effect of making the key much easier to remember since mnemonic methods are more readily usable for key memorization.
For slightly longer keys, one could use four English words instead of three English words: this would give a secret key of 53 bits.
We first consider short key cryptographic protocols in which the underlying conventional long key cryptosystem is a symmetric key system. In this case, Alice and Bob begin by picking a short key of length bits. Later, when they wish to carry out a private communication, they jointly choose an auxiliary key : this could be done by picking it at random, or by one them picking the auxiliary key unilaterally, or by having Alice and Bob each choose half the key at random if they fear the other has been subverted by an adversary. They then both compute , which takes time . The expanded key is used as the key for the cryptosystem for their communications. Once they are done with the round of communication, they may erase the key : if they later need to recover , they can do so by recomputing .
One feature of the above protocol is that it is possible to use multiple auxiliary keys , each one yields a key (presumably generally distinct) expanded key . Thus each communication session can use a distinct expanded key . If any of the keys are compromised or revealed, then the rest of the communication sessions remain securely private, because of the onewayness of .^{6}
As a speculative application, the ability to use distinct expanded keys for different communication sessions would allow an business or an embassy to have a secured, shielded system that is used once per day, say, to generate a new expanded key . The expanded keys would be used for a limited period of time and then erased.
Like any symmetric key cryptosystem, short key cryptosystems can also be used for user authentication. For this application, we envision a batterypowered, electromagnetically shielded, handheld device which computes the function . If a user, Alice, is remotely contacting Bob, then Bob may send a randomly chosen auxiliary key . Alice enters first and then her short secret key into the handheld device. After 10 seconds (for instance), the handheld device displays the value . Alice then returns that value to Bob: Bob also knows and separately computes , comparing it to Alice's response. If they match, then Alice is authenticated. For this application to benefit from the use of the short key, it needs to be designed so that the value of and all intermediate memory values used in the computation of are thoroughly erased after the computation. In this case, theft of the handheld device cannot compromise the secret key .
Now we consider the protocols for the situation where the underlying conventional, long key cryptosystem is a public key system. If Alice wants to generate a public/private key pair for communication with Bob, she generates an auxiliary key (chosen randomly, say) and then computes , which is her private key for use with the cryptosystem . From this she computes the public key which corresponds to and sends to Bob on an (insecure) channel.^{7} Note that Alice does not need to reveal her auxiliary key to Bob; on the other hand, if is revealed, then there is no loss of security. Once Alice and Bob complete a communication, Alice may erase her copies of ; if she needs to recover it later she can recompute it from and . This gives Alice the ability to recover old messages and to prove the content of old messages, without the security risk of keeping a long (1000 bits or more) private key in writing or electronically stored.
By varying the auxiliary key , Alice can use a single short key to generate a large number of private/public key pairs for the cryptosystem . In this way, Alice can have a large number of secure communications based on a single short secret key.
Since public key cryptosystems are quite flexible and allow many operations such as message signatures, message undeniability, message authentication, etc., all of the capabilities can be achieved with a short key cryptosystem.
In designing a short key cryptosystem to have adequate security, the two most important parameters which can be varied are (a) the secret key length and (b) slowness of the slow oneway function . These parameters should be chosen so as to keep the key length short, and so as to keep the slowness of being a serious impediment. In choosing the parameters, one should consider how large an attack may be mounted, how certain one is about the slowness of , and how often the slow function must be computed.
We let denote the length of the secret key, and we let be the time required to compute for keys of length (we assume here that the length of and the method of computing has been fixed). To measure the serious of the attack, we use a factor and an attack time . The factor is the ratio of the computational power available to the attacker to the computational power of the computer used for computing . The value includes the following factors:
Since there are potential secret keys, the system is
deemed to be safe from attackers provided
For true security, one probably should use a value of ; however the smaller value might be acceptable for low security applications. For security against a ``worldwide'' attack where , one probably should use short keys of length closer to 56.
One tradeoff in picking the slowdown time is that the time cannot be so long as to impede the implementation of the cryptographic protocol. If Alice and Bob's secure connection is to be longlived, then a quite long slowdown may be reasonable, providing additional security. An initial one time slowdown of hours, or even days or longer, might be acceptable; later, new expanded keys may be generated by running again with its execution overlapped with the communication session in progress so that no further delays are experienced.
Finally, it is stressed that the public auxiliary keys must be chosen to minimize the likelihood that two sessions will use the same one. Combining some random bits (say 40) with the encoded standard date and time is a natural approach.
A slow oneway function must enjoy the following hardness properties, which generalize the usual notion of onewayness:
Of course, the search problem for is inherently parallelizable; so an adversary who is able to use a large amount of hardware can speed up the exhaustive search for the value of . This is of course part of the reason for our use of the parameter in the previous section.
As we remarked before, any slow function can be converted into a slow oneway function merely by composing the slow function with a oneway function. Thus, practically speaking, it is sufficient to find good candidates for slow functions, since from this one can readily create a slow oneway function.
A natural choice for the slow function is to base in on iteration of the pseudorandom number generator . Letting be a strong pseudorandom number generator with a sufficiently large internal state that maps bit numbers to bit numbers, one can form an initial seed and then apply repeatedly to the seed until the desired slowdown is achieved. One or more subsequent values of is then read out and hashed to generate the expanded key . It is easy to generate an extended key of any length using this scheme so that it might be used to generate a 56bit DES key, or several for repeated DES, etc.
An important consideration when choosing a slow function is whether it is possible to build special, custom hardware that accelerates the computation of values of the function . In particular, if it is difficult to get a large speedup with custom hardware, then one does not need to use such a large value for . The pseudorandom generator approach above is attractive because processors in widespread use can evaluate functions like this very efficiently with the computation taking place entirely within cache memory. Moreover, it is inherently sequential, guarding against a parallel attack. For these reasons, it is unlikely that supercomputers or even special purpose hardware can provide a major improvement in the time needed to compute a single value of the function based on such a pseudorandom number generator.
One possible problem with above pseudorandom number generator method is that one must ensure that it is not possible to quickly compute multiple iterations of ; this is not a general design requirement for pseudorandom number generators, although doubtlessly most pseudorandom number generators have this property. To be more careful with this, one might combine the pseudorandom generator with a one parameter family of oneway permutations . (Candidates for include many of the standard symmetric key cryptographic functions, including DES, etc., where the parameter serves as the secret key for the cryptographic function. One should use DES for this only if a hardware implementation is available.) Then make the parameter a function of and and set as before, and set where denotes the fold iteration of . Choosing a value large enough so that the computation of requires run time , one can use (and possibly a few subsequent 's if more bits are needed) to form the expanded key .
Quisquater et al. [9] proposed iterated DES as a slowdown function for key generation. Several other authors have suggested functions with purposeful slowdowns, for other applications. For the application of uncheatable benchmarks, Cai et al.[4] propose iterated powering modulo a product of two large primes; as a second proposal, they suggest a oneway benchmark where one uses a oneway function and a hash function and the slow problem is the problem of finding a value so that for a given value . By controlling the size of the set from which is drawn they control the runtime of a procedure which finds from . Dwork and Naor [5] propose slow functions as means of reducing junk email. Their suggestions for slow functions include extracting square roots modulo a prime , with carefully chosen so that the expected time to find a square root can be controlled. Rivest, Shamir and Wagner [11] suggest timelock cryptography which depend on tailoring the computation runtime of a problem: they also suggest iterated powering modulo a product of two large primes as a slow function. It should be noted that iterated power modulo the product of two large primes (as suggested by [4,11]) is not so good for our application, unless one is able to completely discard all knowledge of the two large primes; this is because knowledge of the primes would open a trapdoor that would circumvent the the slowness of the slow oneway function.
We have shown that slow key expansion may be used to construct secure public key or symmetric cryptosystems in which very little secret knowledge is required. A 40bit secret, for example, may be remembered as eight alphanumeric symbols or only three entries drawn from a 10,322 word dictionary of common English words. Security is enhanced because secret keys this small can be remembered by the owners and may never be stored for any long period in the cryptosystem itself. When used with auxiliary nonsecret keys, short secret keys can be used as master keys in a key generation protocol and allow multiple independently secure communication sessions.
Acknowledgement We thank Mihir Bellare, Russell Impagliazzo and Francis Zane for helpful comments on a draft of this paper.
This document was generated using the LaTeX2HTML translator Version 2K.1beta (1.47)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html split 0 image_type gif nonext_page_in_navigation noprevious_page_in_navigation up_url ../main.html up_title 'Publication homepage' accent_images textrm numbered_footnotes sk.tex
The translation was initiated by Peter N. Yianilos on 20020625