In the previous section, we have examined the Kerberos system, which provides cryptographic protection to networked computers.
It had one important limitation: if a user chooses a poor password, that is, not one so poor that it could be guessed in a few tries at a computer terminal for attempts to directly log on to the actual system, but merely one poor enough that an attacker trying thousands of passwords from a list on a computer of his own could find the password on that list, that user's security can be compromised.
Note that the IBM system examined in the section before it did not have this weakness; it, however, depended on tamper-proof hardware being present on the user terminals. With this proviso, it is possible to do anything public-key methods can achieve, and more. Kerberos, however, did not even use any public-key techniques.
This technique, a dictionary attack, had also been used against password files on classic Unix systems: two countermeasures were employed to block this attack there: one was salt, a random value which is hashed with the user's password (this prevents the attacker from precomputing a dictionary of hashed common passwords, but a dictionary attack remains possible, just somewhat slower, as the dictionary must be hashed for each user under attack) and another was a shadow password file (in Unix, unlike in most other timesharing operating systems, the file with user IDs and the hashes of their passwords was actually readable by all normal users of the computer), which meant that the attacker could not read the file with the hashes of user passwords.
How can Kerberos be modified so that it is immune to the dictionary attack?
Kerberos is vulnerable to a dictionary attack because there are components of some messages that are encrypted with the user's permanent secret key (the one derived from the user's current password) that can, in combination with components of other messages, be seen to be correctly deciphered if a correct guess at the user's password is applied to them.
Specifically, the second message, from the Kerberos server to the user, contains a copy of the session key for the dialogue between the user and the ticket-granting server. This session key is then used by the user to encipher an authenticator which is sent to the ticket-granting server in the third message. That authenticator contains the current time and the user's name, and since these two values are public information, a correct value for the session key, which a correct guess at the password would yield, can be seen to be correct when these two values emerge.
If the Kerberos server had a public key, and the first message from the user to the Kerberos server were enciphered in that key, and included a random value which would be combined with the user's permanent secret key to encrypt the first session key, an eavesdropper would not have the information available to mount a dictionary attack.
An attacker who impersonated the user would recieve a copy of the first session key, encrypted by means of a known function of the user's permanent secret key. But since the first session key is only a sequence of random bits, the encrypted first session key would be of no use for a dictionary attack.
If the first message included an authenticator for the user's permanent secret key (the user's name and the current time enciphered with it), that would further guarantee the user was genuine, and encrypted it would not be available for a dictionary attack.
If, however, the user only sent the authenticator, encrypted with the server's public key, and no random padding was used in the public-key encrypted block, then a brute-force search would still be possible, by noting the time, and creating an authenticator, and then encrypting it with the server's public key, for every password tried.
Several related techniques have been developed for making use of a small shared secret such as a password for achieving a high security of communications between two parties. These techniques have been developed recently, and some of them are protected by patents.
The simplest of these techniques to understand, and the one that most obviously provides privacy amplification, is EKE, or Encrypted Key Exchange.
Instead of the parties having permanent public keys, they generate a new public/private key pair for each session, but each party sends its "public" key to the other party encrypted, using the small shared secret as the key.
In order for this to work, brute-force search on the small shared secret must be impossible, hence the portion of the public key that is encrypted with it must have the form of a string of random bits. Hence, this technique cannot be used by enciphering the modulus for RSA.
Privacy amplification is obtained, because to read a message, if the encryption techniques used are effective, one has to do a brute-force search on the conventional encryption key, and then solve for the private key from a public key for each value tried in the search.
Another technique, SPEKE, is based on the Diffie-Hellman method of key establishment.
In Diffie-Hellman, a common modulus, P, and a common base, A, are agreed upon by both parties. Each party generates a secret number, x for the first party, and y for the second. The first party communicates A^x (modulo P) to the second party, and the second party communicates A^y (modulo P) to the first. Both parties can compute A^(xy) (modulo P), since that is both (A^x)^y and (A^y)^x, but an eavesdropper, knowing only A^x and A^y, cannot.
In SPEKE, the common base, A, is derived from the shared secret. Also, x and y are equal to twice random integers produced by each party.
Another technique is SNAKE. In this case, the modulus P is a function of the shared secret. However, instead of just one modulus, a function is provided to create different moduli based on other inputs in addition to the shared secret.
Thus, both users create a family of secret random numbers; the first one creates x1, x2, x3 and so on, the second y1, y2, y3. Each user also creates a family of public random numbers, the first a1, a2, a3... and the second b1, b2, b3 and so on.
P1 is a function of a1 and the shared secret; P2 is a function of a2 and the shared secret, and so on. (The function is also varied each time, so that if a1=a2, it is not the case that P1=P2.)
The first user calculates and discloses b1^x1 mod P1, b2^x2 mod P2, b3^x3 mod P3 and so on; the second user calculates and discloses b1^y2 mod P1, b2^y2 mod P2, b3^y3 mod P3 and so on. So, as in Diffie-Hellman, both users can calculate b1^(x1*y1) mod P1 and so on.
Finally, in SNAKE, the agreed-upon secret key depends on these secret values, but is a hash of all the public information exchanged followed by the secret values obtained by the Diffie-Hellman method.
Another of these techniques is SRP, which is also a variant of Diffie-Hellman. In this technique, in addition to both participants generating a random number, one x and the other y, a third number, z, is involved. It is a hash of the user's password, and the host only requires a copy of A^z for the protocol. (In the detailed description of the protocol, x is a hash of the user's password and a salt supplied by the host, rather than a number randomly chosen at the user's computer.)
The user generates A^x, and passes it to the host. The host generates A^y, but sends A^y+A^z to the user.
Both the user and the host know what z is, so subtracting off A^z is not a problem for the user, but it would be for the eavesdropper.
Thus, the user knows x, A^y, and z, and the host knows A^x, y, and A^z. The Diffie-Hellman method is now modified so that what the user and host both know is A^(xy+yz), which the user calculates as (A^y)^(x+z) and the host calculates as (A^x*A^z)^y. The user in this method is proving twice to the host that it knows z. A hash of this calculated quantity is used as the session key.
Another method recently devised for achieving the same goals as EKE, using a small shared secret to materially increase the security of key exchange by public key encryption, does so without encrypting any public keys, and uses RSA (or similar systems) instead of Diffie-Hellman as its base. This method is OKE, for Open Key Exchange, and is described in a paper on the web site of Stefan Lucks.
In this protocol, both partners share a small common secret, p.
Either partner to a proposed communication can subsequently generate a set of RSA keys, M, e, and d, and disclose M and e publicly, thus communicating them to the other partner.
The generic OKE protocol, as naïvely applied to RSA, proceeds as follows:
The intent of this protocol is to use the common secret p as a tool for authenticating the public key (M,e) under conditions where the common secret p can be retained, but the public key, or even a sufficiently long hash of it to provide authentication, could not. Thus, since p is not dependent on the public key itself, this can be thought of as a form of authentication in advance.
Unfortunately, this basic version of the protocol has one weakness: an adversary impersonating B can post an invalid RSA key such that the operation x^e mod M is not invertible. An attack exists by doing so which allows information useful in a dictionary attack on p to be obtained. A modification, called protected OKE, is proposed, where a is replaced by two values, a0 and a1, and instead of sending them, one sends the result of encrypting them using B's RSA key as many times as there are bits in the desired session key, in the following manner: a2=(a0^e)*a1 mod M, a3=(a1^e)*a2 mod M, and so on. If the RSA operation is not invertible, then having aK and a(K-1) will not enable one to unambiguously obtain a0 and a1, which are then both used in calculating the hash which is used as s.
At one point, I tried to convert OKE to a protocol that could operate passively, so that B could simply post his public key, and then A could send an encrypted message to B at any time without any interaction, as follows:
In the RSA encryption, of course, k is actually randomly padded in the normal fashion.
Introducing a timestamp gives some protection back against replay attacks in a passive one-way protocol, and further protection can be obtained if B checks for repeated use of values of a, but this does lose some of the properties of the original OKE protocol.
I even tried to elaborate it as follows:
In the RSA encryptions, of course, a, T, and k are actually randomly padded in the normal fashion.
However, these protocols do not work as given, because M, e, b, and H(M,e,b,p) can be used to mount a dictionary attack on p. If we omit H(M,e,b,p) from the public key posted for B, we could send messages using an M and e that are not authenticated, and simply rely upon the recipient being unable to read the message sent without knowing p. But that, again, would inevitably fall to a dictionary attack on p, since someone impersonating B and using a false M and e would simply try every possible p to read the message. Thus, interactivity is an essential part of OKE, and it cannot be converted to a passive protocol; another basic idea, such as EKE, has to be added to provide protection against dictionary attacks on the shared secret when interactivity is absent.
One interesting thing that can be done using only a hash function, is bit-commitment or coin-flipping.
Given a one-way hash function, two people can proceed as follows: each one generates a random number, and then transmits the hash of that random number to the other person.
After both have done this, they can then transmit the original random numbers to each other, and both can be sure that neither party altered his random number based on finding out what the other person's random number was. Hence, the XOR of those two random numbers can be treated as if it was a genuine random number by the two parties (but not necessarily by anyone else) for basically the same game-theoretic reasons that make playing randomly the best strategy for scissors-paper-stone.
An interesting example of a smart-card protocol, UEPS, is described in Bruce Schneier's Applied Cryptography.
It involves tamper-proof cards and machines into which the cards are inserted; both customers and merchants have cards, but of two different types.
A customer card contains the customer's ID and two secret keys which are functions of the customer's ID, and it is able to carry out two secret hash functions. A merchant card is able to carry out the secret algorithm to produce a customer's two secret keys from the customer's ID. Both cards can derive a 56-bit DES key from an encrypted message.
A transaction proceeds as follows: