Misuse-resistant authenticated encryption based on SHA-3/Blake2b and AES-CTR/ChaCha20

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.

• 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 – Richie Frame Feb 21 '16 at 6:57
• The encryption key is derived from the auth tag, which is derived from the ciphertext C. Where does C come from? – Tim McLean Feb 21 '16 at 7:54
• @TimMcLean typo, fixed – Demi Feb 21 '16 at 8:19
• What endianness are your $len$s? ​ ​ – user991 Feb 21 '16 at 9:02
• Little-endian byte order – Demi Feb 21 '16 at 9:07

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.

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

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].)

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