How is the key in a private key encryption protocol exchanged?

Question

Windows NT used a point-to-point protocol where a client can communicate "securely" with a server by using a stream cipher to encrypt an array of messages with some key $k$. The server also encrypts its response with the same key $k$. But how is it aware of this key?

More general: if Alice and Bob use some encryption/decryption algorithm that operates on the same private key $k$, what is a secure way of exchanging this key? (without using a different key ofcourse)

This is something that I've always asked myself whilest studying private key cryptography.

Answer 1

Most private key algorithms rely on infeasibility of certain computations like factorisation of a number into its prime factors given the current computing infrastructure.

At the same time, most of them are also computationally intensive when used for encryption and decryption and therefore the entire message stream is not encrypted using the private keys. Rather, the message is encrypted using some other (less intensive) algorithm and the key used for that encryption is encrypted using the Private Key.

Of course, as you point out, secure exchange of keys remains an issue which can be to a certain extent be addressed by:

• Diffie-Hellman Key Exchange: Uses modular arthimetic to securely exchange keys.
• Single/Multiple Key Distribution Center (KDC): Uses trusted third party based ticketing system.
• Kerberos Authentication Protocol: A relatively complex protocol based on KDC.

Answer 2

Whenever Alice and Bob wants to agree on a same private key, the most popular method is to use Diffie-Hellman. It works as follows:

1. Two public values are first chosen lets say $n=13$ and $g=17$. (These are usually very large prime numbers and known to everyone using that protocol).

2. Alice chooses a Private Value $a = 3$ and Bob chooses a Private Value $b = 7$. These are private to themselves.

3. Alice computes: $A = g^a\mod n$ and Bob computes: $B = g^b\mod n$, in this case $A = 12$ and $B = 4$ and they exchange each others values (may be through chat), i.e. everybody knows the values of $A$ and $B$.

4. Alice computes: $K = B^a \mod n$ and Bob computes: $K = A^b\mod n$, in this case $K = 12$.

Now Alice and Bob have both agreed upon the value $K$ as their key. Note that since the value $n$ and $g$ and very large prime numbers it is almost impossible for a eavesdropper to factorize them and compute the key himself.

A problem in private key cryptography is man-in-the-middle attack and that is one of the main reasons to choose public key cryptography over private key cryptography.

Answer 3

First, a point of terminology: what you describe is symmetric encryption, and a key that's shared between participants is usually known as a secret key; “private key” usually means the part of a key in public-key cryptography that only one participant knows.

There are two ways of disseminating a secret key: it can be transported in some physically secure fashion, or it can be transported using some other form of encryption, commonly public-key cryptography.

There are ways to exchange a secret key that do not require a secret communication channel. The most popular is the Diffie-Hellman key exchange protocol. The principle of Diffie-Hellman is that each participant generates its own key pair, and there is a mathematical operation that constructs a large number from one public key and one private key. This mathematical operation has a very interesting property: the large number can be constructed from Alice's private key and Bob's public key, or from Bob's private key and Alice's public key; you get the same number either way. So Alice and Bob exchange their public keys, and both parties know the large number, which can then be used as a secret key. An eavesdropper can find out both public key, but it is impossible¹ to find the large number from the public keys alone.

The Diffie-Hellman key exchange allows two parties to exchange a secret, no matter who is listening. However, it does not authenticate Alice to Bob or vice versa. Therefore it is amenable to a man-in-the-middle attack: Mallory performs the key exchange with Alice (who believes she's talking to Bob) and separately with Bob (who believe he's talking to Alice), and thus gets to decide or at least know the secret.

When the attacker can intercept and inject messages, more cryptography is needed for the participants to authenticate each other. (A passive attacker effectively means that the underlying transport protocol provides authentication.) The easy way is for each participant to already know each other's public key. If Alice knows Bob's public key:

• Alice can authenticate Bob by sending him a challenge: a random value (a nonce) encrypted with Bob's public key. If Bob can decrypt that value and send it back, Alice knows she is really talking to Bob.
• Bob can authenticate with Alice by sending her a message signed with his public key. Alice verifies the signature to check she is really talking to Bob.

There are many variants that use one of these methods (or yet another variant) in one direction and either the same or a different method in the other direction, or that authenticate in one direction only. For example, SSL/TLS (the cryptography layer for many -s protocols such as HTTPS, SMTPS, IMAPS, etc.) can use several different cipher combinations, and usually authenticates the server to the client but can optionally authenticate the client as well. Diffie-Hellman is slow and cumbersome for this application; the most widely algorithm with public key distribution is RSA.

Of course, Alice and Bob might not know each other's public key beforehand. So they instead rely on a trust chain: Bob sends Alice his public key, alongside a signed statement from a third party that affirms that this key is really Bob's public key. This signed statement is called a certificate and the third partie is a certificate authority. The third party may be known to Bob, or its identity may be confirmed by a fourth party, and so on. Eventually this chain of trust (… vouches for Dominique vouches for Charlie who vouches for Bob) must reach some party Ron that Bob already trusts, meaning that Bob has Ron's public key and trusts Ron to only sign valid certificates.

There are protocols that do not rely on public-key cryptography. In particular, the Kerberos protocol is used in both unix-based and Windows-based networks to establish connections between a client and a server. Kerberos uses a central authentication server called a key distribution center (KDC). The KDC must have the user's password stored in a database, and the client normally prompts the user for the password. To avoid exposing the password, the protocol does not use the password directly, but a cryptographic hash or more generally a key derivation function applied to the password.

With this shared secret, the client and the KDC establish a secure channel and the KDC sends the client a “ticket”. The ticket contains a session key (i.e. a newly generated secret key), as well as a copy of the key that is encrypted with another symmetric key shared between the KDC and the server that the client wants to contact. The client then forwards this encrypted copy to the server. The server decrypts this message to get the session key, and generates a nonce that it encrypts with the session key and sends back to the client. The client then initiates a secure channel with the server, encrypted with the session key, and starts by showing that it could decrypt the nonce: this authenticates the client to the server. A Kerberos session establishment is a variant of the Needham-Schroeder protocol.

¹ _{In the sense that cryptographers have tried very hard, but the best way they've found to do it requires an unachievable amount of computing power.}

Answer 4

A possible way is to first use Public-Key Cryptography to exchange a private key. However, when it's not possible, there are some specific key exchange protocols, probably the most well-known is the Diffie-Hellman protocol.

Answer 5

There is always the trivial solution: the users meet and exchange keys. This is not very practical for many cases, but possible.

In addition to the Diffie-Hellman (DH) key-exchange protocol, there are also quantum key distribution protocols. One of the most known QKD protocols is the Bennett-Brassard protocol, BB84.

The advantage of BB84 over DH, is that DH is secure only if discrete logarithm cannot be done efficiently (see discrete logarithm assumption, and also the related DDH Assumption). However, BB84 is information-theoretically secure. That is, even if $P=NP$, BB84 would still be secure (but DH would not).

On the flip side, MITM attack is a problem for BB84 as well, and one must assume the users use authenticated channel to overcome this problem (but this usually requires them to preshare an authentication key, and we're back in square one).