Establishing encryption key using shared secret

Question

I need to establish some security on a network of 8 bit microcontrollers. very limited RAM, CPU and packet sizes.

I have zeroed in on a shared secret based scheme. Setting up shared secret is out of scope. Encryption is AES128.

To securely create and share an encryption key between two nodes, A and B, I cooked up this:

A creates an encryption key Ks = H(Ns, R0)    
A sends R0 to  B    
B calculates key K's = H(Ns, R0)

K's and Ks will be same if and only if B has Ns

Where H = Hash(R0|Ns|R0), or Hash(R0|Ns|H(Ns)) or maybe HMAC (still undecided)
R0 = random number
Ns = Shared network secret.

Ns is 16 byte. R0 is 4 byte. Both come directly from a RNG.

Primary Objectives are: Tamper proofing, Forward secrecy.

Not concerned about resistance to Side channel or replay attacks for now.

R0 (and hence Ks) will be updated periodically, perhaps every 100-10K independent packet transfers.

Is the scheme ok? Do the Ns or R0 need to be increased in size? Most importantly, will this scheme be able to keep Ns safe, and for how long?

=============== Edit:

Reg Forward secrecy:

I wanted to ensure that as long as network secret is safe, if a future session key (Ks) is compromised, past session keys and data should not also be compromised. Also, a renegotiation of session key should re-establish security.

That may not be exact definition of forward secrecy, but that's what I meant. I don't have sessions but I will expire keys periodically and after time or some count of packets is crossed etc, and call that a session.

===============

Reg H()

Based on answers, I have added AES(k=Ns, d=R0) to list of functions for H(). Will decide based on time/clock requirements.

===============

For now, based on the answers, I infer that all current options for H() will create good enough keys that will protect both encrypted data and Network Secret Ns.

If you are reading this text and feel that any of them might not be safe, please leave a comment or answer. Thanks.

Answer 1

You don't need a hash function for this. Given that you're already using AES-128, and that your master key $N_s$ is 128 bits long, a perfectly good method for deriving the session keys $K_s$ would be to encrypt the random number $R_0$ (padded to a full AES block) using AES-128 (in ECB mode, i.e. using the raw block cipher) with $N_s$ as the key.

Even if the attacker can choose the random numbers $R_0$, and could obtain all the corresponding session keys, recovering $N_s$ would still require a practical chosen-plaintext key recovery attack on AES. No such attack is currently known, and if one was found, AES would be considered totally broken.

---

However, it's also worth noting that this key derivation scheme (either as above, or as proposed in your question) does not provide forward secrecy; an attacker who has captured a past session, including $R_0$, can easily decrypt it if they later somehow learn $N_s$.

It is, however, possible to achieve something similar to forward secrecy using key renewal. That is, instead of deriving temporary session keys from a fixed master key, you regularly derive a new master key from the old one, and then erase the old key. This erasure will protect old messages from decryption even if the new key is compromised; it will not, however, protect future messages from compromise of an old key in any way.

One way to do this would be to compute the new master key $K_n$ from the old key $K_{n-1}$ as $$K_n = \text{AES}_{K_{n-1}}(A),$$ and the corresponding session key as $$S_n = \text{AES}_{K_n}(B),$$ where $A$ and $B$ are any two distinct constant cipher blocks (e.g. all zeros and all ones). You would then use $S_n$ to encrypt your messages using an authenticated encryption mode.

Maintaining key synchronization between the two communicating sides can be a bit tricky. One method would be to store the key renewal counter $n$ explicitly, and to transmit it in plain with each message. Upon receiving a message tagged with a new counter value $n' > n$ (and $n' < n+2^b$ for some reasonable constant $b$, to prevent denial-of-service attacks), you'd compute $K_{n'}$ and $S_{n'}$ and try to use them to decrypt and authenticate the message; if the authentication succeeds, you increment your own counter to $n'$ and start using $K_{n'}$ and $S_{n'}$ as the new keys; otherwise, you assume the message was bogus and ignore it.

Note that it's enough to use a $b$-bit counter and let it wrap around. For most applications, $b$ can be fairly small; say, $b = 8$, or even $b = 1$. It's also possible to implement key synchronization without transmitting a counter at all, but this gets slightly more complicated. (Basically, whenever you receive a message you can't authenticate with $S_n$, you need to retry authentication with $S_{n+1}$.)

Answer 2

So, they both have a 16 byte shared secret, and you want to create a shared 16 byte (=128 bit) AES key...am I missing something here? Why not just use the secret as the key!

Just plug it into CBC or CTR or GCM or something, and you'll be good.

If you'll be running this for a large number of messages, then the scheme you described using HMAC would be perfectly acceptable. As far as I can tell, it can't be broken without attacking HMAC or AES.

This is of course assuming that the network secret is known only to Alice and Bob, which depends on how the micro-controllers set up the shared secret key with the network.

Answer 3

First, Don't roll your own crypto.

Second, you don't need to negotiate session keys for each transmission. As long as the network-secret is safe, all the connections using this secret are always safe.

However, you mentioned forward secrecy. You can't get this with pre-shared keys. If the keys gets screwed every connection (now and in the future) can be broken, assuming the handshake is recorded.

Concerning your concerns in regard of Ns, that it may be extracted or otherwise be compromised from the protocol, you are quite safe, as the hash-functions make reverse-looking-up Ns impossible. However in about 50 years (or maybe a bit less) it will be possible for many organizations to brute-force 128-bit keys. So, if your device will be deployed for more than ~40 years, make sure to upgrade to something stronger (and make sure the Ns can't be reverse engineered from the device!)

Using HMAC as your choice for H is optimal, as you want to use the "authentication tag" of R0, using your shared-key as your session key. R0 should be chosen larger, as of now it has no real value, as a 32-bit value isn't all that unpredictable, I suggest going for something in the 12-16 byte range (96-128 bit).

For me, the key-setup phase is looking good enough, although I'd never trust any protocol whiches security hasn't been proven. You can leave it as it is or you can add a response from B with a R1 and use the XOR of the two, which is only useful in case you think one device may be compromised and it would help any attacker to somehow "predict" a certain key. Updating every 10-100k messsages looks fine (assuming the device will exchange this amount of data in a foreseeable amount of time, like a week or less)

As it goes for "don't roll your own crypto", using TLS-PSK is an option, you may want to use AEAD schemes (i.e. GCM) like TLS_PSK_WITH_AES_256_GCM_SHA384. As your shared key you can either plug-in your Ns or your derived session key, they'll likely be equivalentely secure.