2
$\begingroup$

Consider the following block cipher mode of operation: \begin{align} tag_0 &= mac\:key\\ plaintext_0' &= plaintext_0 \oplus iv\\ E(tag_0 | plaintext_0') = C_0 &= tag_1 | ciphertext_0\\ E(tag_1 | plaintext_1) = C_1 &= tag_2 | ciphertext_1\\ ...\\ E(tag_N | plaintext_N) = C_N &= tag_{N+1} | ciphertext_N\\ cryptogram &= tag_{N+1} | ciphertext_0, ciphertext_1, ... ciphertext_N, iv\\ D(tag_N + 1 | ciphertext_N) &= P_N = tag_N | plaintext_N\\ D(tag_N | ciphertext_{N-1}) &= P_{N-1} = tag_{N-1} | plaintext_{N-1}\\ ...\\ D(tag_1 | ciphertext_0) &= P_N = tag_0 | (plaintext_0 \oplus iv)\\ \end{align} $tag_0$ is then validated against the mac key.

An explicit description, which demonstrates using a 128 bit block cipher (i.e AES) and 64 bit tag:

  • the the first block of a message that is encrypted consists of a mac key, denoted as $tag_0$, concatenated with the first 64 bits of plaintext
  • $plaintext_0$ is xor'd with an IV
  • the block $(tag_0 | plaintext_0)$ is encrypted
  • the first 64 bits of $ciphertext_0$ are used as $tag_1$ for encrypting $plaintext_1$,
  • this is repeated for the entire message
  • The cryptogram consists of the final tag prepended to the ciphertext, and the iv
  • Decryption is the same process with the messages in reverse order, and the tag validated against the mac key at the end.

Does the described mode of operation provide integrity and authentication of the plaintext?

Assuming so:

  • Does it have a name already/is there any established research?
  • What is the minimum acceptable value for the tag size? My guess is 64 bits. Too much larger would seem to preclude usefulness with ciphers that have a block size of <= 128 bits.
  • With a 128 bit block cipher, performance is 2 two block cipher operations per 128 bit block of plaintext, which could be better
  • The number of block cipher operations would appear to become more efficient with a larger blocksize + longer messages?
    • The ratio of required block cipher operations per block of plaintext appears to be given by: \begin{align}blocksize / (blocksize - tag\:size)\\ \end{align}

Edit

Astute commentators have pointed out the construction is similar to the way a sponge provides authentication. This is certainly not a coincidence! I have been studying the sponge construct for a while. The tag in the mode of operation described here fulfills a conceptually similar role as the capacity of a sponge function does.

$\endgroup$
  • $\begingroup$ This reminds me of the sponge construction. See also NORX, which uses the "monkeyDuplex" construction. There are some important distinctions from your construction, however (in particular, how the permutation is keyed). $\endgroup$ – Tim McLean Apr 12 '16 at 5:46
  • $\begingroup$ @TimMcLean Thank you, I am familiar with the sponge construction and NORX. This question is basically the inverse of another question I had; That one was about using a block cipher inside a sponge, whereas this one is basically like incorporating the state from a sponge inside a block cipher. $\endgroup$ – Ella Rose Apr 12 '16 at 6:25
  • $\begingroup$ If you have a look at NORX, you should also check Keyak which has the same construction and use the same idea of tags. $\endgroup$ – Biv Apr 12 '16 at 7:16
4
$\begingroup$

No, this mode as listed does not provide integrity of the decrypted plaintext.

An active attacker can flip arbitrary bits from the first 64 bits of the decrypted plaintext freely without causing a decryption failure. He can do this by modifying the $iv$; the decrypted $tag_0$ will authenticate (because the $iv$ is not used to compute that), and then the decryption process will apply the modified $iv$ to the decrypted $plaintext_0$

$\endgroup$
  • $\begingroup$ I see! re: "as listed" : What if the IV covered the first input block (tag _0 | plaintext_0) instead? I actually wasn't sure what exactly to do with the IV, so it's not surprising I didn't get that part right. Thank you for your insight, your answers are always helpful! $\endgroup$ – Ella Rose Apr 13 '16 at 2:59

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.