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.

If you are reading this text and feel that any of them might not be safe, please leave a comment or answer. Thanks.
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' &gt; n$ (and $n' &lt; 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}$.)