# Establishing encryption key using shared secret

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.

• Please tell me you use something standardized for the transport layer (TLSv1.2, TLS-PSK, TLS_PSK_WITH_AES_128_GCM_SHA256) – SEJPM Jun 25 '15 at 20:21
• Standardized things were not written for I2C/SPI buses connected to 8 bit microcontrollers.. so No.. I am not planning to use libraries... I know its against common wisdon to write crypto libs, but I think what the hell.. cant lose knowledge by doing it.. right? – GPS Jun 27 '15 at 13:20

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}$.)

• AES for generating session keys is good idea.. I hand't thought of that. Choice between my H() and AES() will now just be based on number of clock cycles taken by each. Thanks for this suggestion. Also, periodic master key renewal is what I had in mind. I was hoping to transmit encrypted new master key in a master-key-update message. I will consider your key renewal message too..If a session or master key is somehow leaked, I believe all past data still is secure. I am still working on future data, which I don't think would be possible from within this protocol. – GPS Jun 27 '15 at 13:50
• The main advantage of using AES for key derivation is that you're using it for encryption anyway, so it doesn't cost you any extra code to include it. Of course, if you need a hash for something else too, then it indeed becomes just a matter of speed and convenience. That said, AES is likely to win the speed contest too. – Ilmari Karonen Jun 28 '15 at 9:49
• Yes sir. I need hash for some authentication messaging, so its there anyway. I do think AES will win for key-gen that's why its an awesome idea. Though, I've not yet zeroed in on a specific hash.. – GPS Jun 28 '15 at 9:56
• You might not actually need a hash for authentication either, if you e.g. replace HMAC with CMAC. If you're using public key signatures, though, those probably do require a hash (among other machinery). – Ilmari Karonen Jun 29 '15 at 19:57

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.

• This does not provide forward secrecy. – Stephen Touset Jun 25 '15 at 20:36
• @StephenTouset, PSK never gives you forward secrecy, if your long-term keys are screwed you'll always have lost secrecy of all messages (some logic applies to RSA key exchange). Or was that an addition to the answer? – SEJPM Jun 25 '15 at 20:41
• Sure it can. Use the PSK to simply authenticate a DH session whose keys are discarded after use. – Stephen Touset Jun 25 '15 at 20:48
• Thanks for comments guys. I understand the issue with Forward secrecy now. I misused the term.. I will shortly edit the question to reflect what I actually had in mind. @StephenTouset I would love to do DH session, in fact that was where I started, but I have very limited packet size that can be transmitted at once. Once I add authentication payload to key-negotiation, and other network parameters I have a budget for no more than 10-12 bytes (each way) for establishing key. DH will not establish secure enough keys in only that many bytes of exchange. – GPS Jun 27 '15 at 13:33

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.

• Thanks. There is a tight limitation on number of bytes I have available for key-setup.. but I should be able to get maybe 4-6 more for this. As far as response from other node goes, I will cover that under node authentication. I want to keep that entirely independent of key setup, or based on key setup, but not based on network secret, to protect Ns. I will discuss auth in another question. – GPS Jun 27 '15 at 14:03