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 **E**ncrypted
**K**ey **E**xchange.

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 two partners, A and B, each calculate a long nonce, a and b respectively, which is at least twice as long as the key they need, and communicate the nonces to each other.
- At this point, both partners can calculate a hash of the public key, the two nonces, and the shared secret. This value, H(M,e,a,b,p) will be called s (since M is taken, and it is used for maSking).
- Let B be the partner that generated the public-private key pair, and who knows d. Then, A will choose k, a random value that is the source of the session key, and send v=(k^e)*s mod M to B.
- B will then calculate (v/s)^d mod M, thus obtaining k.
- B proves knowledge of k by sending H(k,1) to A.
- If H(k,1) as recieved by A is valid, A proves knowledge of k by sending H(k,2) to B.
- If H(k,2) as received by B is valid, communications can begin using H(k,3) as the session key.

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:

- B posts, as his public key, M, e, b, and H(M,e,b,p) in some public place.
- A, who knows p, can verify the authenticity of M and e by recalculating H(M,e,b,p). A then calculates the random value: k, which serves as the source of the key, and a, a nonce. A then calculates s=H(M,e,a,b,p), and H(k,T) where T is a timestamp, as well as H(k), the message session key.
- Then A sends to B the following items: H(k,T), a, v=(k^e)*s mod M, from which B can obtain k, and a message encrypted with H(k) which includes a copy of T.

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:

- B posts, as his public key, M, e, b, and H(M,e,b,p) in some public place.
- A, who knows p, can verify the authenticity of M and e by recalculating H(M,e,b,p). A then calculates the random value: k, which serves as the source of the key, and a, a nonce. A then calculates s1=H(M,e,b,p), s2=H(M,e,a,b,p), and s3=H(M,e,a,b,T,p) where T is a timestamp, as well as H(k), the message session key.
- Then A sends to B the following items:
- v1=(a^e)*s1 mod M, from which B can obtain a,
- v2=(T^e)*s2 mod M, from which B can obtain T,
- v3=(k^e)*s3 mod M, from which B can obtain k, and a message encrypted with H(k).

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:

- The merchant card transmits the merchant's ID to the customer in the clear.
- The customer card transmits the customer's ID in the clear, and encrypts using both secret customer keys in turn and sends a message consisting of the customer's ID, the merchant's ID, and random padding.
- The merchant card decrypts and verifies the message recieved from the customer. It then uses the encrypted message from the customer, as encrypted with only one of the customer's secret keys instead of with both, (the intermediate result in the original encryption is used) to produce a session key. The merchant card then encrypts using first the session key, and then the other one of the customer's secret keys, a message consisting of the merchant's ID, the customer's ID, and random padding.
- The customer's card also generates the session key, and uses that as well as the appropriate one of its own secret keys to decrypt and verify the message recieved from the merchant. The merchant's message, encrypted with only the session key, is used to produce a second session key. The second session key is used to encrypt the transaction, which consists of the IDs of both parties, the amount and type of the transaction, and the two secret hash functions of that information. One secret hash function is for the use of the bank, and the other is for the use of the clearing center. (Since the customer cards can carry out those hashes, presumably the merchant cards can also safely be allowed to do so, so that they can be verified as well.)

[Next] [Up] [Previous] [Index]