# 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!].

## closed as too broad by Maarten Bodewes♦, yyyyyyy, cpast, DrLecter, e-sushiMay 28 '15 at 23:05

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• 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") – SEJPM May 24 '15 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!) – Anon2000 May 24 '15 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. – Anon2000 May 24 '15 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. – Anon2000 May 25 '15 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. – SEJPM May 25 '15 at 12:06

## 1 Answer

Anon2000 - as currently constructed your mode is fatally flawed. Given two known messages encrypted with the same key (i.e. where the attacker knows the plaintexts) that are each at least two blocks in length (not counting the IV or final validation block), the attacker can trivially forge at least two other 'valid' messages (and many more than that if the 2 known messages are long or he knows more messages), regardless of whether the RNG is cryptographically secure or not. Rather than spell it out for you, I think you would learn more by trying to figure out for yourself why such forgeries are trivial. As a hint, consider what happens to a message that is (say) 4 blocks long when you flip a single bit in the plaintext of the second block.

Again, I can't recommend enough that you take some time to understand provable security, and more generally try to think like an attacker. Without that skill-set, any 'fixes' you might make in your mode design are like someone who doesn't know aerodynamics trying to design an airplane -- even if you constantly go back and forth to aeronautical engineers with proposed trial-and-error 'fixes', your plane still won't fly, you will have learned much less than had you sat down with an aerodynamics textbook, and you will eventually piss off the engineers.

• You'd be surprised that coming up with crypto schemes and having good cryptoanalysis skills are not necessarily interdependent concepts (and I do have analysis skills, but they're seem to be at a "fuzzy" state right now though). If you are an engineer, you're someone who could imagine taking away the human factor here (e.g. no one who gets "pissed of"). Imagine that instead of human feedback, there would be a machine, comparable to an automated test or a compiler, that could instantly tell if a scheme is secure or not. You'd be surprised how far one can go with that - yes - trial and error! – Anon2000 May 25 '15 at 5:59
• I work daily with automated testing, and the more I've used it and came to be depend on it I simply realized that human effort is simply not as ideal and efficient for verification (although I spend a lot of time "logically" understanding and analyzing what I do). This might appear strange to you, but I adapted a methodology where most verification is "outsourced" to external entities (i.e. machines) so i have no problem writing silly programs and try to test them. I simply don't hesitate that much! – Anon2000 May 25 '15 at 6:06
• I'm not saying comparing you (or other people who donate their time at this site) to a "machine", but in some way, if you were, that would be awesome! think about it! I would come up with 10 flawed schemes (based on even possibly flawed intuition), spending little time trying to perform analysis on them, respond to the faults and incrementally develop a better and better solution! As I've said you'd be surprised how just "fixing local problems" with rapid feedback can be a useful strategy! Even if you don't like this in its current form, take it as an experiment! – Anon2000 May 25 '15 at 6:09
• I'm not an ignorant person. I'm capable of coming with "somewhat plausible" algorithms (just like an agent in a context of say, an evolutionary algorithm would) and but in some cases not that good/focused/clear at verifying them. I don't see the big deal here, I never claimed I believe it works, or that it should work. It would just be that the effort and the mental state needed to verify it is not available for me right now. I didn't hesitate at asking because I thought it was a positive methodology in general. And it is! (again, a machine would be better but that's what I have right now.. :) – Anon2000 May 25 '15 at 6:23
• @Anon And here we see the problem with your approach. You cannot have an automated process to see if something is secure. The two possible ways to show security are a mathematical proof, or having your scheme peer-reviewed by many competent cryptographers over a substantial period of time. The fact that no one has found an issue with v4 of the malleability question yet doesn't mean it's secure; more likely, it means people have stopped bothering to look at it. – cpast May 25 '15 at 16:24