3
$\begingroup$

I have the following requirements:

  • 64 bits (8 bytes) of data ($D$) that requires confidentiality and integrity;
  • the data itself is a nonce, never need to authenticate/encrypt the same value twice (e.g. a counter);
  • I can only use AES cipher (128-bits key);
  • I can have a maximum of 128 bits as output (one block).

Given two different AES-128 keys ($K_\mathrm A$ for Authentication, $K_\mathrm E$ for Encryption), I'm using the following MAC-then-Encrypt scheme:

  • compute $\mathit{MAC} = \operatorname{CMAC}(K_\mathrm A, D, 8)$ (see RFC 4493)
  • truncate the MAC to get the tag: $T = \operatorname{MSB}_{64}(\mathit{MAC})$ (see NIST 800-38B)
  • get the plaintext $P = D\mathop\Vert T$ (16 bytes)
  • get the ciphertext $C = \operatorname{AES}(K_\mathrm E, P)$ by using AES/ECB/NoPadding mode

I generally know that MAC-then-Encrypt schemes can be secure, but I'm not able to demonstrate it for this scheme. Could you elaborate on that? Is there any improvement I can do?

I know that a good alternative would be AES-GCM (or CCM). Is there any way to fit into a single block of ciphertext by using AES-GCM on 8 bytes of data?

$\endgroup$
3
$\begingroup$

The lack of a generic security reduction for MAC-then-encrypt is basically only for pathological cases where an encryption scheme admits modifications to the ciphertext that don't affect the plaintext, like AES-CTR with an extra bit of key stream appended to the message on encryption and ignored on decryption.

So is your AES-CMAC-then-AES scheme or an AES-GCM variant secure?

AES-CMAC-then-AES. What you described is a deterministic nonceless authenticated encryption scheme. As such, it can't conceal repeated messages, but otherwise it provides confidentiality and authentication, as long as you reject invalid MAC tags before even thinking about the data. Finding a way to reject replayed messages is your responsibility.

AES-GCM. AES-GCM is a deterministic nonce-based authenticated encryption scheme. That is, AES-GCM is a different kind of cryptosystem from AES-CMAC-then-AES. If you can provide a 96-bit nonce for each message, e.g. a message sequence number, then it provides about the same security.*

AES-GCM is also quirky about nonce sizes: With a nonce size other than 96 bits, AES-GCM's security diminishes, because of the low but nonnegligible probability of collision in the internal 96-bit nonce derivation. And, of course, with a repeated nonce, AES-GCM's security vanishes.

But for the scenario you described, both more complex than you need!

(CAVEAT LECTOR: This is not a peer-reviewed academic journal of cryptographic designs. This is a pseudonymous stranger on the internet blathering crypto at you.)

You could use $C = \operatorname{AES}_k(D \mathbin\Vert 0^{64})$, and reject decryption if the message does not end with 64 zero bits.

For uniform random permutation $\pi\colon \{0,1\}^{128} \to \{0,1\}^{128}$, the adversary's chance of guessing a ciphertext $C'$ for which $\pi(C')$ has 64 trailing zero bits in one try is $2^{-64}$, which is the best you could hope for with an 8-byte authenticator anyway.

Obviously, $\operatorname{AES}_k^{-1}$ for uniform random $k \in \{0,1\}^{128}$ or $k \in \{0,1\}^{256}$ is not exactly a uniform random choice of permutation, but the attacker's advantage knowing $\pi = \operatorname{AES}_k^{-1}$ for some key $k$ is negligible: even in their worst case when $D$ is uniform, they have a far better chance of guessing $D$ or forging $C'$ than of guessing $k$.


* The short messages are critical here because the attacker's forgery probability is about $2^{-\tau}$ for CMAC but $\ell \cdot 2^{-\tau}$ for GCM, for $\tau$-bit tags and up to $128\ell$-bit messages, when the tag size $\tau$ is much smaller than the cipher block size 128.

Specifically, let $n$ be the block size in bits; $\tau$, the tag size in bits; $\ell$, the maximum message length in $n$-bit blocks; $q$, the number of oracle queries; and $f$, the number of forgery attempts. Assume a uniform random permutation; $\operatorname{AES}_k$ is a good enough approximation. For CMAC, the attacker's forgery probability is bounded by $$O(q \ell^2) 2^{-n} + 1 - \operatorname{Binom}(0; f, 2^{-\tau}) = O(q \ell^2) 2^{-n} + 1 - (1 - 2^{-\tau})^f,$$ which, for $f \lll 2^\tau$, is approximately $O(q \ell^2) 2^{-n} + f 2^{-\tau}$. For GCM, the attacker's forgery probability is bounded by $$1 - \operatorname{Binom}(0; f, \ell 2^{-\tau}) = 1 - (1 - \ell 2^{-\tau})^f \approx f \ell 2^{-\tau}.$$

If $\tau$ is, say, 32, and you authenticate messages of up to 64 KB, CMAC limits the forger's success to about one in four billion, while GCM limits the forger's success to about one in four thousand.

$\endgroup$
  • $\begingroup$ Your answer is exactly what I was looking for. Yes, my application already rejects $D$ if it is old/replayed, so I need a nonceless scheme. I understand your point, I will consider your proposal of replacing the truncated MAC with a simpler string of 64 zeros (or maybe any other fixed string). Answer accepted, thank you. $\endgroup$ – gentooise Sep 11 '17 at 9:37
  • $\begingroup$ TL;DR version: MAC then encrypt should be pad, MAC (including padding), then encrypt $\endgroup$ – Joshua Feb 21 at 0:02

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.