Is this an acceptable authenticated encryption?

Question

After much deliberation, I've decided to use a normal Encrypt-then-MAC scheme instead of an authenticated encryption mode such as GCM as authenticated encryption primitive. This is due to the lack of good, clean and reliable implementation across all the platforms I intend to support.

Background

This is for a multiplayer [strategy] game over TCP/IP. In particular, a player will log in and play every day (or every other day) for about 1-2 months (the typical playing time).

The reason why we use encryption at all, is to:

• prevent sabotage (replay another player's login + actions to make him waste his daily turns, modify actions in flight)
• prevent eavesdropping (stealing login credentials, monitoring actions, stealing in-app purchases)

Proposed Authenticated Encryption Primitive

1. At a new connection derive the IV, encryption key and signing key using HMAC-SHA512, using a secret (lifetime - max 24 hours, randomly generated) and public client + server nonces and two salts (one for each direction). We simply split the resulting 64 bytes to form 16 byte IV, 16 byte key and 32 byte signing key.
2. We set up two AES-CTR ciphers (one in each direction) using the IVs and the encryption keys derived in step 1.

3. For each packet to encrypt, we perform the following steps:

   1. Encrypt the packet with the next [plaintext number of] bytes of AES-CTR.
   2. Calculate HMAC-SHA256(signing key, 4 byte message number || 4 byte message length || ciphertext)
   3. Increase message number by 1.
   4. Send ciphertext || first 8 bytes of HMAC

On decryption, checking HMAC is made so that successful matching the HMAC and failing to match the HMAC should execute equally fast.

Example code:

int hmacFail = 0;
int hmacSuccess = 0;
while (hmacPtr < hmacEnd) {
    if (*(hmacPtr++) != *(hmacOurPtr++)) {
        hmacFail++;
    } else {
        hmacSuccess++;
    }
}
if (hmacFail > 0) -> Raise HMAC invalid error

On failed packet authentication, the connection is dropped. On the consequent reconnect a new server and client nonce will be used, so IV and keys will not be reused. Typically a connection lives for about 5 minutes, but may stretch into 1-2 hours.

Messages are typically small (less than 100 bytes) and infrequent (usually no more than a few messages a second)

Questions

1. Is something missing from the MAC?
2. I'm fairly confident that reducing the HMAC to 8 bytes should be ok, as the behaviour of dropping a connection (and thus forcing a new signing key). It might be quite ok to reduce it further.
3. As far as I can tell from some initial benchmarking, the dominating cost is in calculating the hash. What are my options if I want to reduce this cost while using readily available hash primitives? Going to SHA1 or even MD5 would make it faster (in my particular test, SHA1 was around 50% faster, MD5 100% faster). Any tips and tricks given the circumstances?
4. Anything else I've forgotten to take into account?

Answer 1

This is basically a description of a protocol, I'll just go over the cryptography related points that you've raised.

1. At least the nonce is missing from the calculation. Just to be sure I would include the entire counter value used in the CTR encryption.
2. 64 bit of MAC output should be OK, both NIST SP 800-107 Revision 1 and NIST SP 800-38B define 64 bit of hash output as acceptable. See NIST SP 800-107 table 2. If less bits are used additional security proof would be required.
3. It is possible to go for an AES based MAC instead (AES-CMAC). AES is likely to be faster - especially if encryption is currently not the dominating cost; this depends on the deployed hardware and runtime environment of course.
4. That's hard to tell without taking the complete protocol into account. Most of the time the symmetric algorithms are not the hard part of the protocol - authentication and key management are much harder parts to get right. This is why choosing TLS should be preferred.

There are two side channel attacks that are often forgotten when creating an online protocol.

1. Timing attacks are particularly dangerous, especially during the authentication/session key derivation phase.
2. Ciphertext length based attacks are particularly dangerous on the application level, including the authentication phase (e.g. of username/password).

Please take both into account when designing any secure transport protocol.