How to exchange authentication keys

Question

I am trying to create a secure Bluetooth Low Energy connection. The peripheral server (the main device other people would connect to) would need to service many clients (users) and due to hardware limitations, I would not be able to let the hardware manage security (essentially, it has a limit of 4 keys, i.e., 4 users).

I have researched and have decided on the following general scheme.

1. Use AES128 for encryption. The key is held in the server and client, assuming that is done securely.
   • To do this, the device can generate a random "password" and make it visually appear to the user, which has to enter it on his client device (smartphone). The smartphone, which has generated the AES key would use the password to encrypt the key and send it to the device for storage.
2. Use SHA-256 with a cryptographic key to authenticate messages. I know that this should be done after the encryption.
3. Upon connection, generate an authentication key and send it to the other one.
   • I thought about this (not using a static authentication key), so that an attacker cannot record the messages of a session and replay that later. I guess this must be a well-known problem.
   • Question 1: How can the key be reliably sent from one to the other?
   • Question 2: Who should be the one generating this authentication key? The server device? Or the smartphone?
4. To know which encryption key to use, the userid could be sent in plaintext.
   • Question 3: Is it possible not to send userid in plaintext and still be able to understand which key to use for the communication? Does it matter?
5. On each message passing, derive a new authentication key from the previous one.
   • I thought about this, so that if an attacker hijacks a session, previously sent cyphered messages in this session would look invalid.
   • Question 4: What algorithm could be used to derive a new key from the old one, ensuring that the result is also a "good" key (high entropy and such)?
6. Use an IV to make sure the same message (a command to the server device) encrypts to different messages every time.
   • Question 5: Should this also change on every command similar to the authentication key?

Regarding Question 1, during the authentication key exchange, HMAC doesn't seem to be possible, so I was thinking of sending the generated key only encrypted. The other end of the communication can recover the authentication key by decrypting the message. Question 6: could an attacker be able to recover the key by pretending to be on the key-receiving end of the communication? How about if it is pretending to be on the key-sending end?

Regarding Question 2, I am inclined towards having the smartphone generate a key, as it probably has better access to cryptographic libraries (as opposed to the device, which runs on a microcontroller).

Regarding Question 3, I cannot see a problem with an attacker knowing which userid the communication is established with. A system with multiple users with visible ids is, I think, as secure as a system with a single user. Then again, I'm not a security expert.

Regarding Question 4 and 5, I am guessing a pseudo-random number generator seeded with the authentication key/IV should do.

Answer 1

First, some notes on your choices of primitives:

• AES-256: You don't need to use AES-256 unless the data you want to protect needs to remain confidential for more than 30 years
• SHA-256 for authentication. Don't use plain SHA-256. Either use HMAC-SHA-256 using an encrypt-then-authenticate approach or (even better!) use AES-GCM or AES-EAX as your mode of choice as the two provide authenticated encryption (AE) and the likelihood of errors is much less.

Now to answer your questions:

1. If you store a key on both devices long-term-wise I think your questio means "How to securely transmit / negotiate a session key for authentication and encryption?". Well you could use ECDH to let both devices negotiate a key, but I assume this isn't possible in your case. In this case you simply generate a key at random, encrypt it using the long-term key and send it to the device, preferably using an AE mode, as you only have to manage one key then.
2. Who should generate a key? The one with access to the better randomness sources, usually this is the more powerful platform having more user interaction. (in your case the smartphone I think)
3. The answer on this depends on your situation. If the user-id is just some random number and if you're not too concerned with privacy of your users, you can send it in plain. If the user-id actually holds information (like a name) you could the connecting device send a nonce $N$ along with $Tag=H(N||ID||N)$. Then the device could try out all (4!) IDs and look for the match. This wouldn't expose the user-ids at any point in time in plain. If the user-id is low entropy and you want to protect it very hard, usage of a password hashing scheme (PHS, as function $H$ instead of SHA-256) may be an option to put more work effort to find the ID.
4. What you describe here is similar to the famous OTR protocol. To perform the operation you need you'd simply use a key-based key derivation function (KBKDF/KDF) like HKDF. But be aware, as soon as the devices get out of sync (i.e. a message is lost), you'd need to renegotiate a new session. And note: using this approach doesn't provide forward-authenticity. Meaning if an old key get's stolen, all subsequent keys of the communication can be derived. In my eyes it's sufficient to use AES-GCM for the whole session and don't change with every message, as this means unneccessary performance overhead. You could simply renegotiate the connection every now and then to get a similar property.
5. Yes. Usually IVs are meant to be message-specific. This would result in you sending a new IV with every message. To avoid replay attacks you may also want to consider using message numbers.
6. If you do the setup as described at the beginning (using the password copied from the device to the phone) and you do already use authentication at this point, you're safe, assumed that the transmitted password wasn't intercepted, because an attacker can't fake the authentication tag. (excluding faking of the sender) He can't get the key on the receiving end, because this would mean he can decrypt the key, encrypted using the password which is impossible for any good password (random, 20 chars, lowercase, uppercase(, numbers))

I hope this answers your questions.