correct usage of keys and nonce

Question

I've being studying up on AES, GCM, CBC, HMAC and a lot of other primitives and am somewhat ( a little bit, perhaps) familiar with them however I am still a bit weary on the use of the keys and nonce.

Background:
I have got multiple (embedded) devices (sometimes hundreds) all of which are connect to a server. These devices are to communicate with either AES-CBC HMAC or AES-GCM. when using HMAC I know first to encrypt then MAC. Further more these devices have a pre-installed key on them.

Here is what i think i know:
1. You can have 1 master key but AES and HMAC never use the master key directly
2. You should use a KDF like PBKDF2 to create a session
3. Every so often you should change the master key

Now say we start connecting a device to the server. Both the device and the server have the same master key but they must agree upon a session key. I cannot do this in any other way than to use Diffie hellman? simply sending over a salt for the PBKDF2 won't do since an attacker might alter it.

Then, when using CBC, we create a random number as IV, we encrypt the message, add the IV and then use the HMAC with the session key, append the result and send it over.

When using GCM we create a nonce, encrypt the text, append the nonce to the cipher text and send it over, we either keep sending the nonce over or we keep a counter on both sides either way we always +1 the nonce.

So my question:
is diffie hellman a must have? or is there an other way to do? keep in mind I am very restricted in processor power and memory so using a PKI with RSA is not an option.

is everything else i described correct?

1 final remark, It is often said it's better to use 2 separate keys (1 for encryption 1 for HMAC) this simply means using DH twice

Answer 1

1. Well PBKDF is for deriving keys from passwords, you don't need it if your master keys are already safe, just use something like HKDF. (faster)
2. ECDH and DH are certainly the most secure options you have for negotiating session keys. Of course, as you do have a pre-shared master secret you have some interesting new options.
3. Your usage of the HMAC sounds secure. By convention you might want to append the ciphertext to the IV (-> $IV||C$ instead of $C||IV$) as the IV is the $-1.$ block.
4. Your usage of the nonce sounds pretty secure. As long as you don't reuse nonces for the same key (which you don't do) you're safe.
5. Using seperate keys means to use keys which share no known relation (hashing doesn't count). So you could derive the $K_{MAC}=KDF(MS,"MAC")$ and the $K_{Enc}=KDF(MS,"ENCRYPTION")$, this would be perfectly safe and you wouldn't have to re-perform DH.

Now to solve your session key problem:
It is a non-standard symmetric key-agreement protocol:
Notation:
$r_A,r_B,n_A,n_B$ are all 64-byte random numbers.
$E_K(X)$ notates authenticated encryption of X using a key derived from the pre-shared master secret.

1. $A$ sends $B$ $n_A$. $n_A$ is a nonce, used to guarantee freshness of execution.
2. $B$ responds to $A$ with $E_K(n_A||n_B||r_B)$. $A$ verifies that $n_A$ is correct and saves $r_B$.
3. $A$ finally responds with $E_K(n_B||n_A||r_A)$. $B$ verifies that $n_A$ and $n_B$ are correct.

Now both parties share $r_A$ and $r_B$ and hence one can use these values to generate a session key (without forward secrecy), using a standard KDF.

Answer 2

PBKDF2 is an acronym for Password Based Key Derivation Function, #2. As you already have a key you need a Key Based Key Derivation Function or KBKDF instead. Currently the most up to date one is probably HKDF, which was - very quickly - also recognized by NIST. There are other KDF's such as KDF1 and KDF2 which are easier to construct (not many libraries contain KBKDF's by default).

---

You don't require Diffie-Hellman if you already have a shared secret, unless you also require Forward Secrecy.

What you can do is store device keys on the device, send over some device ID to the server that uses that to calculate the device keys from a master key. That way, if one device is compromised, you don't loose the master key (the device is fitted with the device key upon creation using the same algorithm).

Similarly you can use a key derivation from the device key using some unique session based information or large enough random to establish session keys. I would create 2 to 3 session keys:

1. for explicit authentication using a MAC (you don't want to use your secure channel for implicit authentication - trust me on this)
2. for encryption of the secure channel
3. for authentication of the secure channel (unless you use one key for encryption and authentication as in GCM)

It's best to use different session keys for client and server (e.g. by reordering the client ID and server ID) otherwise you may run into nonce reuse, replay attacks etc.

---

Note that the authentication data used for explicit authentication should contain as much data as possible, including one or more randoms, client ID, server ID and something to identify the session with.

---

So basically you don't require asymmetric primitives for such a scheme, although you may gain additional benefits from it. Forward secrecy is one, but you might also want to achieve anonymity to name just one other (I presume this is less important for your use case though).