How to generate successive stream-cipher keys?

Question

I've identified a weakness in a distributed simulation system I'm looking at, and I'm looking for some advice on how to fix it.

Clients initially negotiate an authentication token with a login server using Diffie-Hellman. They then connect to the each simulation node they require (seperate hosts) in turn, using the token as a key for data encryption.

The problem is that for a single client the same key (i.e. the token data) is being used for each node.

I'm thinking of hashing the token n+1 times each time it is used, to produce a new key each time. Unfortunately I don't have the option of re-negotiating an entirely new key for each node a client wants to access.

Does this sound OK, at least for a temporary fix?

Thanks for any advice.

Cheers!

Answer 1

I can see a number of problems with your suggestion to let the session key $sk_{n,c}$ for node $n$ and client $c$ be $sk_{n,c} = h^{n+1}(masterkey_c)$, where $masterkey_c$ is what you refer to as "token":

• You should use different keys for encryption and integrity, and different keys for the client -> node direction and the node -> client direction, making four keys total for each node and client combination.
• The keys are not independent. If an adversary is able to compromise a node $n$ and get the session keys of that node, then the sessions of each node $n+k$ with $k > 0$ will also be trivially compromised.
• There is no easy way to negotiate a new $sk_{n,c}$ if the connection between client $c$ and node $n$ is dropped. The client will have to negotiate a new $masterkey_c$.

I presume you have already figured out a way to securely distribute $masterkey_c$ from the login server to the nodes. The question is exactly which security features you need. I presume the communication between the client and the node is two-way, and that your application is such that you both need protection from replay attacks and the ability to easily renegotiate the session key of any client and node pair without having to renegotiate the master key for the client.

To begin with, you need a key derivation function $KDF(keymaterial,label,nonce)$. If the only cryptographic primitives you have are the stream cipher and the hash, you will firstly have to implement HMAC since it will be used for the protocol later. Secondly, you could then construct the KDF as follows:

$KDF(keymaterial,label,nonce) = HMAC(keymaterial,label|nonce)$

where $|$ denotes concatenation.

Thirdly, you need an unpredictable pseudo random bit generator. Since the client is performing a Diffie-Hellman handshake with the login server, it must have one already. If the nodes don't have access to the same functions the login server has, they could get a random $seed$ sent to them by the login server and use the following:

$DRBG(seed,ctr) = KDF(seed,"drbg",I2OS(ctr)), ctr = ctr + 1$

client/node master key

Server side, the login server performs the following calculation and sends the result to the corresponding node. The client might perform the calculation immediately before connecting to a node. The keymaterial $masterkey_c$ is the output from the Diffie-Hellman handshake:

$masterkey_{c,n} = KDF(masterkey_c,"mast",I2OS(n))$

client/node handshake

Input: $masterkey_{c,n}$

Output: message counter c->n $Ctr_{c,n}$ message counter n->c $Ctr_{n,c}$, session keys $ek_{c,n}$, $ek_{n,c}$, $ak_{c,n}$, $ak_{n,c}$.

Note: For simplicity, I assume you are using a stateful stream cipher, and that the encryption keys $ek_{c,n}$ and $ek_{n,c}$ can be regarded as stream cipher states that get updated by each call to the encryption function $E(keystate,text)$.

1. Both the client and the node set both message counters to $0$.
2. The client generates a random nonce $nonce_c$ and sends it to the node.
3. The node generates a random nonce $nonce_n$ and sends it to the client.
4. Both calculate $ek_{c,n} = KDF(masterkey_{c,n},"ekcn",h(nonce_c)|h(nonce_n))$, $ek_{n,c} = KDF(masterkey_{c,n},"eknc",h(nonce_c)|h(nonce_n))$, $ak_{c,n} = KDF(masterkey_{c,n},"akcn",h(nonce_c)|h(nonce_n))$, $ak_{n,c} = KDF(masterkey_{c,n},"aknc",h(nonce_c)|h(nonce_n))$.
5. The client calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|E(ek_{c,n},"verify")), Ctr_{c,n} = Ctr_{c,n} + 1$ and sends it to the node. The node disconnects if it fails.
6. The node calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|E(ek_{n,c},"verify")), Ctr_{n,c} = Ctr_{n,c} + 1$ and sends it to the node. The client disconnects if it fails.

There should probably be some safety mechanism in the handshake protocol that prevents the client and the node to repeat it indefinitely in case of failure. For instance, they could attempt to complete it three times, before they give up and the client either marks that specific node as unreachable, or returns to the login server to negotiate a new $masterkey_c$. The client should only do the latter if it fails to complete the handshake with several nodes.

Bulk data transfer

Input: $pt$

Output: $ct|mac$

Client to node:

• $ct = E(ek_{c,n},pt)$
• $mac = HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$
• $Ctr_{c,n} = Ctr_{c,n} + 1$

The client sends $ct|mac$ to the node, the node calculates $HMAC(ak_{c,n},I2OS(Ctr_{c,n})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{c,n}$ and decrypts $ct$ otherwise.

Node to client:

• $ct = E(ek_{n,c},pt)$
• $mac = HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$
• $Ctr_{n,c} = Ctr_{n,c} + 1$

The node sends $ct|mac$ to the client, the client calculates $HMAC(ak_{n,c},I2OS(Ctr_{n,c})|ct)$ and verifies that it matches $mac$, disconnects if it doesn't, and increments $Ctr_{n,c}$ and decrypts $ct$ otherwise.

Hope this helps

Answer 2

No, this isn't a good idea.

The reason is that if you ever re-use a key in a stream cipher, an attacker can XOR off known plaintext to get the key stream.

Yes, your fix is an improvement, but you were starting from completely insecure and you've pushed it up into mostly completely insecure.

The login token is probably easily hackable, if not guessable, and an attacker merely has to start with that and keep hashing to get a test key. The whole search space is likely less than 100. It's rarely going to be more than 1000, and thus someone who really wants to hack you is going to wait for mere milliseconds before getting the right key.

Do you not have an equivalent of /dev/random? or /dev/urandom? Or anything? If you start with something that's got some good key value to it, you're mostly okay.

Where are you getting your x (as in g^x) for your D-H, or is that not random either? Frankly, if you're stuck, it's much better to hash x than your token -- or hash both of them, or HMAC the token using X as your HMAC key. Wherever you're getting your X from, use that to get your key.