Security of a simple AEAD construction

Question

Introduction

I want securely communicate with a small 8-bit device which has a very limited program program memory (Arduino Uno - 32K).

My goal is to minimize code size and RAM usage. There are multiple alternatives I could use, but I have reasons to believe that all of them would have larger code size and/or RAM usage. See the end of this post for details.

I came up with a very simple Authenticated Encryption with Associated Data (AEAD) construction that uses the Speck block cipher. Any block cipher with a 128-bit block size could be used, but Speck is super small in software.

Speck is used both for authentication (CBC-MAC) and encryption (CTR mode). In both cases, I'm using a 128-bit block size and a 128-bit key size.

High-level overview

Like proper AEAD modes, this construction offers two operations:

• authenticated encryption
• authenticated decryption

I'm going for an interface similar to what NaCl does, except I include additional authentication-only data, and I use two separate keys. The authenticated encryption operation thus takes five inputs:

• authentication key $K_A$
• encryption key $K_E$
• nonce $N$
• plaintext $P$
• associated data $A$

Output is ciphertext $C$, which contains everything needed to reconstruct $N$, $P$ and $A$. If you know the keys, that is.

Interface for authenticated decryption simply takes this ciphertext $C$ and returns true if MAC verification and all other integrity checks succeed; otherwise, it returns false. It also returns $N$, $P$ and $A$.

Authenticated encryption

Since I'm going for extreme simplicity and small code size, I made this construction quite inflexible and limited:

• nonce $N$ must be exactly $7$ bytes
• additional data $A$ must be exactly $8$ bytes
• plaintext $P$ must be a multiple of $16$ bytes

Byte $0$ of the output $C$ is the number of blocks in $P$ ($\frac{length}{16}$). The purpose of this is to make the set of all messages prefix-free for use in CBC-MAC. It also limits the maximum message size to $256 \times 16 = 4$ kilobytes.

Bytes $1-7$ of $C$ are the nonce $N$.

Bytes $8-15$ of $C$ are the additional authenticated data $A$.

Next comes $P$ encrypted in CTR mode with the $K_E$. Counter blocks are constructed as follows:

• $7$ bytes nonce $N$
• $8$ bytes zeroes
• $1$ byte counter

Lastly, CBC-MAC is calculated by encrypting all previous $C$ data in CBC mode with the authentication key $K_A$ and a zero IV (check out point no. 2). The last block of this encryption is appended to $C$.

I believe this scheme could be described as Encrypt-then-MAC.

I am intentionally refraining from using all bytes of the counter block to limit the number of blocks encrypted by a single key. The user will be advised to not use the upper $4$ bits of the nonce to limit encryption to $2^{60}$ blocks, which is the maximum recommended for CTR mode by Ferguson and Schneier in Cryptography Engineering.

Questions

1. Assuming the nonce $N$ is unique for each message, does this construction meet the standard notions of confidentiality and authenticity?

2. Is it accurate to call this an AEAD construction, or would another name be more preferable?

Alternatives

I could use AVRNaCl, but their procedure for verifying and decrypting a ciphertext (crypto_secretbox_open) compiles to about 6K, whereas the crypto described in this question is less than 2.5K, and could probably be optimized down to 2K.

I could also use CCM or EAX with something like AES or Speck, but I believe this would also have a larger compiled code, and here's my argument:

1. According to JP Norair, EAX needs less code than CCM.
2. There's a really nice set of libraries for the Arduino called ArduinoLibs, and it contains a cryptographic library which includes Speck and EAX. I tried compiling EAX with SpeckTiny, and the code size was more than 4K.
3. If EAX has smaller code size than CCM, then it won't be less than the 4K for EAX. Unless, of course, the EAX code is optimized, but I'm not an expert in AVR assembly, and I'm still not sure it would come close to the size of the construction described in this post.
4. Even just intuitively, the construction described in this post is simple. It's a few lines of simple code. The only challenge with implementation that I found is to make a constant-time MAC verification. Both CCM and EAX are more complex than this.

Answer 1

Yes, this is secure.
(one of the few cases where I'm pretty confident about this).

Here are the arguments:

• Combining a secure (e.g. SUF-CMA) MAC with a secure (e.g. CPA-secure) encryption method in encrypt-then-authenticate is generally proven secure. This was shown in "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm" by M. Bellare and C. Namprempre (PDF). Also worth a read is the answer by Yehuda Lindell on the linked question, which emphasizes the fact that you should use established modes (like CCM or EAX) if possible, as they already come with a full proof of security.
• Your're using CBC-MAC with a prepended message length which was shown to be a secure MAC by Rackoff and Gorbunov in "On the Security of Cipher Block Chaining Message Authentication Code" (PDF), assuming the underlying block cipher is a PRF (from which it is indistinguishable up to $2^{n/2}$ blocks with $n$ being the block size in bits)
• The cipher being used is CTR-mode with speck which is a provably (CPA) secure stream cipher if the block cipher can be modeled as a PRF which it can up to $2^{n/2}$ blocks without any problems, furthermore you successfully deployed counter measures against nonce re-use in the underlying mode and thereby should be fine.