# Would this method allow fast authenticated encryption using only a single encryption and RNG operation per block? [closed]

The most promising of the 4 approaches described here (version 4) has been posted as a separate question. This post should be considered for archiving and historical purposes only.

Disclaimer: the algorithms I present here (and in other messages) are used as a hands-on way to learn about developing crypto algorithms, (and might also be of interest for other curious people), not for practical use (at least not after dozens of iterations and peer-review). I understand some people vote down not just because it seems unproved and speculative, and possibly flawed, but also perhaps because I'm not necessarily presenting it this way. This is just a manner of speech. Most of this *is* probably flawed, but that's the whole point here!

The most plausible approach so far is no. 4 so if you're interested jump right into it and try to see if you can find any flaws or attacks. The previous ones are only kept for historical reference (@J.D.'s answer was given for No. 1).

Version 1:

[This was modified from the original version to use a seed as $Key \oplus IV$ instead of just the key, $E(Key \oplus IV)$ and $H(Key \oplus IV)$ are other options]

Assume $E$ is a block cipher, $P_0 = IV$

(Consider both cases where the IV is in plaintext or encrypted)

Encryption:

1. Add an additional block to the message and store the key in it, ie. $P_n=Key$.
2. Seed a random number generator with $Key \oplus IV$.
3. Encrypt all non-final plaintext blocks $P_k, 0<k<n$ in the following way: $C_k=P_k \oplus E(P_{k−1} \oplus Random())$
4. Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus E(P_{n−1} \oplus Random()))$

Decryption:

1. Seed a random number generator with $Key \oplus IV$.
2. Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus E(P_{k−1} \oplus Random())$
3. Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus E(P_{n−1} \oplus Random())$

Authentication:

1. Verify $P_n=Key$

Note the number of encryption operations is actually $n+1$, so the title is slightly inaccurate. Also, it may not be completely essential to store the key in the final block - A non-secret value might work, but I'm being cautious for now..

I'm also not sure if a cryptographically secure RNG is needed here? what do you think? If not, (and of course assuming it may actually is correct and secure), it might execute very fast in practice.

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.

Version 2:

An alternative (which is probably what I had in mind when I wrote this but I didn't describe it precisely)

Assume $E$ is a block cipher, $P_0 = IV$

(Consider both cases where the IV is in plaintext or encrypted)

Encryption:

1. Add an additional block to the message and store the key in it, ie. $P_n=Key$.
2. Seed a random number generator with $Key \oplus IV$.
3. XOR with the output of the RNG (this could be done incrementally)
4. Encrypt all non-final (modified) plaintext blocks $P'_k, 0<k<n$ in the following way: $C_k=P'_k \oplus E(P'_{0} \oplus P'_{1} .. \oplus P'_{k−1})$
5. Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus E(P'_{0} \oplus P'_{1} \oplus .. \oplus P'_{n−1}))$

Decryption:

1. Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus E(P'_{0} \oplus P'_{1} \oplus .. \oplus P'_{k−1})$
2. Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus E(P'_{0} \oplus P'_{1} \oplus .. \oplus P'_{n−1})$
3. Seed a random number generator with $Key \oplus IV$.
4. XOR non-final blocks with the output of the RNG (could be done incrementally to a different copy)

Authentication:

1. Verify $P_n=Key$

Version 3: (an attempt to overcome flaws pointed out by @SOJPM)

Assume $E$ is a block cipher, $P_0 = IV$

(Consider both cases where the IV is in plaintext or encrypted)

Encryption:

1. Add an additional block to the message and store the key in it, ie. $P_n=Key$.
2. Seed a random number generator with $Key \oplus IV$.
3. XOR with the output of the RNG (this could be done incrementally)
4. Encrypt all non-final (modified) plaintext blocks $P'_k, 0<k<n$ in the following way: $C_k=P'_k \oplus (E(P'_{0}) \oplus E(P'_{0} \oplus P'_{1}) \oplus .. \oplus E(P'_{0} \oplus P'_{1} .. \oplus P'_{k−1}))$
5. Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus E(E(P'_{0}) \oplus E(P'_{0} \oplus P'_{1}) \oplus .. \oplus E(P'_{0} \oplus P'_{1} .. \oplus P'_{k−1})))$

Decryption:

1. Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus E(P'_{0}) \oplus E(P'_{0} \oplus P'_{1}) \oplus .. \oplus E(P'_{0} \oplus P'_{1} .. \oplus P'_{k−1})$
2. Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus (E(P'_{0}) \oplus E(P'_{0} \oplus P'_{1}) \oplus .. \oplus E(P'_{0} \oplus P'_{1} .. \oplus P'_{k−1}))$
3. Seed a random number generator with $Key \oplus IV$.
4. XOR non-final blocks with the output of the RNG (could be done incrementally to a different copy)

Authentication:

1. Verify $P_n=Key$

Version 4: (using nested encryption)

Assume $E$ is a block cipher, $P_0 = IV$

(Consider both cases where the IV is in plaintext or encrypted)

Encryption:

1. Add an additional block to the message and store the key in it, ie. $P_n=Key$.
2. Seed a random number generator with $Key \oplus IV$.
3. XOR with the output of the RNG (this could be done incrementally)
4. Encrypt all non-final (modified) plaintext blocks $P'_k, 0<k<n$ in the following way: $C_k = P'_k \oplus ..E(E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1}) \oplus P'_{0} \oplus P'_{1} \oplus P'_{2}))..$ (up to $P'_{k-1}$)
5. Encrypt the final plaintext block $P_n$ (containing the key) in the following way:
$C_n = E(P_n \oplus ..E(E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1}) \oplus P'_{0} \oplus P'_{1} \oplus P'_{2}))..)$ (up to $P'_{n-1}$)

Decryption:

1. Decrypt all non-final ciphertext blocks:
$P_k = C_k \oplus ..E(E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1}) \oplus P'_{0} \oplus P'_{1} \oplus P'_{2}))..$ (up to $P'_{k-1}$)
2. Decrypt the final ciphertext block:
$P_n = D(C_k) \oplus ..E(E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1}) \oplus P'_{0} \oplus P'_{1} \oplus P'_{2}))..$ (up to $P'_{n-1}$)
3. Seed a random number generator with $Key \oplus IV$.
4. XOR non-final blocks with the output of the RNG (could be done incrementally to a different copy)

Authentication:

1. Verify $P_n=Key$

Note: the nested encryptions are calculated incrementally. First $E(P'_{0})$ then $E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1})$ then $E(E(E(P'_{0}) \oplus P'_{0} \oplus P'_{1}) \oplus P'_{0} \oplus P'_{1} \oplus P'_{2}))$. It's an incremental process - only a single encryption operation is performed per block (the inner encryption results are saved)

Note: I'm not sure if it's needed to XOR with all the previous $P'$ or just the latest one in the nested encryption.

In this case (assuming it actually works ?!) it looks more reasonable to ask if a crypto RNG is needed? That's probably why I asked in the first place..

[sorry for the trial and error approach but I find this process extremely effective!].

• Seed a random number generator with the key. Is this equal to "Key a stream-cipher?" because usually RNGs should behave unpredictable. And please note that your scheme hasn't any speed advantage over standard two-pass schemes, as usually "one RNG call / one stream-cipher call" = "one or two blockcipher calls", because they're usually built from blockciphers. AND there may be security issues (but I didn't analyze because it's "too slow") May 24, 2015 at 20:20
• @SOJPM I'm not asking this purely because of practical advantages, so having better alternatives is not an issue. I'm just curious about the validity of this particular use of cryptographic constructs. You seem to imply that a cryptographically secure RNG is needed here (and if it does I guess modes like CCM are equivalent in performance but as I said that's not the point here). I'm interested in why exactly is that the case? What would be the flaws of the scheme with non-cryptographic one? (this might look like a silly question to you but I can assure you it isn't and is very interesting!) May 24, 2015 at 20:45
• @SOJPM I had a small unintentional mistake there (carried over from the previous, flawed version), I changed to $P_0 = IV$ - fixed it now. May 24, 2015 at 21:48
• @RickyDemer I updated version 2 to a more complete description (the previous one just described the changes from version 1). It is still speculative, and possibly just plain wrong, but I'm curious how this could evolve by the input of the community. The point here is to have fun and learn about cryptography. May 25, 2015 at 12:02
• v2 is broken as well. This is a simple "XOR-MAC". If you XOR some error in some plaintext and XOR the same error in a later or earlier plaintext you'll still receive the exact same authentication tag. May 25, 2015 at 12:06