2
$\begingroup$

I am wondering if the following is a useful misuse-resistant authenticated encryption scheme:

Parameters (shared by many users):

  • Choose a hash function $H$, such as Blake2 or Keccak. SHA2 could also be used.
  • Choose a stream cipher $E$, such as ChaCha20 and AES in CTR mode.

Inputs

  • Up to a large amount of associated data $A$.
  • Up to $2^{64}$ bytes of plaintext $m$.
  • Secret key $K$, which must have at least $k$ bits of entropy but can be much longer.

Outputs

  • Ciphertext $C$, of the same length as the plaintext.
  • An auth tag $t$, of 256 or 512 bits depending on the choice of $H$.

Decryption takes $A$, $C$, $t$, and $K$ as inputs and returns either $m$ or the symbol $\text{FAIL}$ if the message was forged.

All lengths are 64 bit, little-endian encoded.

Encryption algorithm:

  1. Calculate the auth tag $t$ as $H(len(K)||K||len(A)||A||len(P)||P)$.
  2. Calculate the shared secret $S$ as $H(len(K)||K||t)$.
  3. Use $S$ as the key for stream cipher encryption. Any extra bits can be use for the nonce. Bits beyond that are discarded.

Decryption algorithm:

  1. Calculate shared secret (same as step 2 of encryption).
  2. Perform stream cipher decryption (same as encryption step, since encryption = decryption for a stream cipher).
  3. Recompute auth tag $t'$ from plaintext, AAD and key (same as encryption step 1).
  4. The message is rejected unless $t=t'$.

Claim

  • 256-bit confidentiality.
  • 256-bit integrity when used with a 256-bit hash.
  • 512-bit integrity when used with a 512-bit hash and $K$ has at least 512 bits of entropy.
  • IND-CCA2 security provided that the AAD is never repeated with the same key.
  • If the AAD repeats the only leak is whether a message repeated.

I would definitely like to know if this cryptosystem lives up to my claims. I doubt it, since I am not a cryptographer -- but I would be glad if I was proven wrong.

$\endgroup$
  • $\begingroup$ if you are not using the AAD it is not nonce misuse resistant. Also you used the same symbol for AAD and the tag, tag should be lowercase t $\endgroup$ – Richie Frame Feb 21 '16 at 6:57
  • $\begingroup$ The encryption key is derived from the auth tag, which is derived from the ciphertext C. Where does C come from? $\endgroup$ – Tim McLean Feb 21 '16 at 7:54
  • $\begingroup$ @TimMcLean typo, fixed $\endgroup$ – Demi Feb 21 '16 at 8:19
  • $\begingroup$ What endianness are your $len$s? ​ ​ $\endgroup$ – user991 Feb 21 '16 at 9:02
  • $\begingroup$ Little-endian byte order $\endgroup$ – Demi Feb 21 '16 at 9:07
2
$\begingroup$

256-bit confidentiality

Let's assume that we're using AES256-CTR and a 256-bit hash. A new 256-bit key $S$ is derived for each message. Since AES256 requires a 256-bit key, there are no extra bits in $S$ available for use in the nonce, suggesting that a constant nonce is used. I believe this is vulnerable to a multi-target attack.

The first block of ciphertext $C_0 = \text{AES256}(S, 0^{128}) \oplus P_0$, where $P_0$ is the first block of plaintext. Suppose that this block is predictable to the attacker (think of SMTP for example: it's not unusual for the first 16 bytes to be predictable) or attacker-controlled. The attacker can compute $K_0 = C_0 \oplus P_0 = \text{AES256}(S, 0^{128})$ to get the direct output of the block cipher.

Suppose that the attacker can observe (and maybe encourage the sending of) lots of encrypted messages. The attacker can compute $\text{AES256}(x, 0^{128})$ for many values of $x$, and check to see if any of those values match any of the $K_0$s the attacker observed. With $2^{20}$ messages (and therefore $2^{20}$ $K_0$s), the attacker should find an $x$ that works after about $2^{256-20} = 2^{236}$ tries, allowing the attacker to decrypt a single message. I believe this violates the claim of 256-bit confidentiality.

A similar attack can be applied to ChaCha20 when it is used with a constant nonce. In the case of a 512-bit hash, this seems to leave enough bits of $S$ for a complete nonce, which should mitigate this attack.

The message is rejected unless $t=t'$.

This is an implementation issue, but this is vulnerable to timing attacks unless a constant-time comparison is used.

$\endgroup$
  • $\begingroup$ Does this work for a 512-bit hash or for ChaCha20? $\endgroup$ – Demi Feb 21 '16 at 18:41
  • $\begingroup$ @Demetri see edit. $\endgroup$ – Tim McLean Feb 21 '16 at 21:50
2
$\begingroup$

Your scheme can't make due with much less than the family $\: m \mapsto H(\hspace{.03 in}\operatorname{len}(K\hspace{.02 in})||\hspace{.02 in}K\hspace{.02 in}||\hspace{.02 in}m)$
serving as a PRF when no message is a prefix of any other message.
(Such pseudorandomness does not follow from full
[collision-resistance and second-preimage resistance and onewayness].)

$\endgroup$
  • 1
    $\begingroup$ This doesn't work because the length fields are fixed-length. $\endgroup$ – Demi Feb 21 '16 at 20:12
  • 1
    $\begingroup$ @ everyone else : ​ Note that my original answer did work when I posted it. ​ ​ ​ ​ $\endgroup$ – user991 Feb 22 '16 at 1:45

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.