[This approach is flawed. A different speculative approach using an RNG instead of the cipher as a source of entropy was posted as a separate question]
Assume $E$ is a block cipher, $C_0 = IV$ and $P_0 = 0$
Encryption:
- Add an additional block to the message and store the key in it, ie. $P_n = Key$.
- Encrypt all non-final plaintext blocks $P_k, 0 < k < n$ in the following way:
$C_k = P_k \oplus E(C_{k-1} \oplus P_{k-1})$ - Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus E(C_{n-1} \oplus P_{n-1}))$
Decryption:
- Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus E(C_{k-1} \oplus P_{k-1})$ - Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus E(C_{n-1} \oplus P_{n-1})$
Authentication
- Verify $P_n = Key$
Note the number of encryption operations is actually $n+1$, so the title is slightly inaccurate (mentioning that would have made it too long). Also, it may not be completely essential to store the key - A non-secret value might work, but I'm being cautious for now..
Please try be constructive, as even if this is flawed in its current state it might be possible to fix it without adding a significant amount of expensive operations.