# Is this an acceptable authenticated encryption?

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?
-
Although I always appreciate a good protocol-building exercise, especially with so many details, is there some reason that SSL/TLS is not applicable here? It appears to be perfect for your needs. –  Reid Jul 21 '13 at 11:47
@Reid With SSL/TLS you have a handshake to allow server and client to select from a range of ciphers. How would that help me decide on an encryption primitive? I deliberately excluded protocol considerations from this question. –  Nuoji Jul 21 '13 at 12:08
Your question screams "protocol" to me, so I'm not sure what you are wanting beyond general help with that. The encryption primitive is AES-CTR in this case; the rest is part of the protocol. Regardless, yes, one of the parts of the SSL handshake is ciphersuite selection. Fortunately, there is extensive literature on the web on which ciphersuites are secure, but essentially you'd want something like ECDHE_RSA_AES_128_GCM_SHA384 or ECDHE_RSA_AES_128_CBC_SHA384. –  Reid Jul 21 '13 at 12:23
For lower (better supported) TLS versions TLS_DHE_RSA_WITH_AES_128_CBC_SHA256 is probably appropriate... –  Maarten Bodewes - owlstead Jul 21 '13 at 13:06
@Nuoji: SSL is battle-hardened. If you configure it to use a strong ciphersuite, it will be much better than virtually any approach you can build on your own (it's got more than a decade of effort behind it). The setup is easy, relative to creating your own secure protocol, and if you use a mode like AES-GCM on processors with the AES-NI instruction, its performance will be screaming fast. AtE is not generally recommended, but TLS 1.2 supports AES-GCM, which fixes that problem. Further, AES-GCM is supported by OpenSSL, which works pretty much everywhere. There are really lots of benefits. –  Reid Jul 21 '13 at 21:30

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.

-
The importance of a good, fast RNG should of course never be overlooked either, but that's getting a bit out of scope. –  Maarten Bodewes - owlstead Jul 21 '13 at 13:36
(1) What nonce? There are two nonces, but they are used to derive IV/key/sign key. Modifying either nonce would break all signing. –  Nuoji Jul 21 '13 at 17:51
(3) Are there any security issues with CMAC? –  Nuoji Jul 21 '13 at 18:00
I know that there are many, many subtle problems when creating the overall protocol, but even so, establishing a solid, efficient, AE primitive is an important step in the overall performance of encryption. –  Nuoji Jul 21 '13 at 18:05
OK, there is probably a good reason why there is a close button, and I think I found one. –  Maarten Bodewes - owlstead Jul 21 '13 at 20:02