7
$\begingroup$

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.
$\endgroup$
  • 1
    $\begingroup$ Is there a reason you do home-brewn CTR+CBC-MAC over proper CCM (or even EAX)? $\endgroup$ – SEJPM Mar 29 '16 at 19:24
  • $\begingroup$ I'm not surprised that you were able to get something based on SPECK into a smaller footprint than xsalsa20/poly1305, but I'm surprised by it being a factor of 3. Have you looked at the compiled output of AVRNaCl to see if there's anything that can be stripped out? $\endgroup$ – Daniel Franke Mar 29 '16 at 19:55
  • $\begingroup$ Well, I think both CCM and EAX would have larger code sizes and perhaps RAM usage. I haven't tried implementing them, but I have checked out Brian Gladman's code for these modes (ccm.c and eax.c), and it doesn't look very small. $\endgroup$ – Roman Mar 29 '16 at 20:19
  • $\begingroup$ As far as AVRNaCl is concerned, they have multiple versions. I have tried the version which is supposed to be the smallest. It uses lots of assembly code, so I haven't tried optimizing it. $\endgroup$ – Roman Mar 29 '16 at 20:20
  • $\begingroup$ nit-pick: most formal specifications output $(N||A||C||\tau))$ and return either $\perp$ or $P$ upon input of $(N||A||C||\tau)$. $\endgroup$ – SEJPM Mar 31 '16 at 13:37
5
$\begingroup$

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

Here are the arguments:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.