Compared to GCM or XTS modes, how secure is H xor R1, E (R2, R1, Message) for confidentiality and integrity? Let R1 and R2 be (32 byte) random values, and let a H = Hash (R1, R2, Message) be of the same length as each R value.  Provided E (R2, R1, Message) is operating in some chaining mode, are there any known weaknesses of a scheme like this which aims to provide confidentiality and integrity?  The hash could also be an HMAC.

Basically, the following would be presented in succession:

(H xor R1), E (R2, R1, Message)


And verification would involve decrypting with the shared key to arrive at R1; xoring with the first part to arrive at a calculated H, and verifying that H agrees with the hash value that it should.  From that point onward only, further processing on the remainder of the message takes place.
I don't see any reason to expect this to provide integrity (INT-PTXT or INT-CTXT).  In fact, if $R1,R2$ were known to the attacker, I can show that in general it does not provide integrity: there exist some encryption algorithms that are IND-CPA secure but where your scheme does not provide integrity.  (e.g., any stream cipher.)  This sounds like a certificational weakness that makes me skeptical about this construction.

I can't see any reason why you would want to invent a homebrew scheme, that comes with no proof of security, and might have some problems that are known not to occur in existing authenticated encryption schemes... rather than using a well-analyzed authenticated encryption mode.

Basically: don't use this.  Use a standard authenticated encryption mode.  There's a reason they are standard; they have been analyzed in depth.



Here is the attack on integrity, assuming $E$ is a stream cipher.  Suppose we are given an encryption of message $M$, and $R1,R2$ are known.  The attack will change the ciphertext into a valid encryption of some other message $M'$ of the attacker's choice, as follows.

Compute $\Delta = \text{hash}(R1,R2,M) \oplus \text{hash}(R1,R2,M')$.  Xor $M \oplus M'$ into the part of the ciphertext that encrypts the message $M$.  Next, xor $\Delta$ into the part of the ciphertext that encrypts $R1$.  This is now a valid encryption of $M'$ (an encryption that'll be accepted by the recipient and that decrypts to $M'$), which breaks integrity.

Why does this attack work?  If you xor $\Delta$ into the $R1$ part of the ciphertext, this will cause the recipient to think the hash is $H \oplus \Delta$ instead of $H$.  That sounds like a bad property in itself, to me.

I realize this property doesn't actually break your scheme, because in your scheme, $R1,R2$ are presumably not known to the attacker.

Nonetheless, it "smells" to me like it is going to be hard to prove the security of your scheme, because of a circular dependency here.  The integrity of the message depends upon the integrity of $H$, which in turn seems to partly rely on the integrity of $R1$, but the integrity of $R1$ depends upon the integrity of $H$.  In addition, there is no "separation of concerns".  The integrity of the message depends upon the secrecy of $R1,R2$; and the secrecy of the scheme depends upon its integrity properties.  Standard proofs typically rely upon a separation of concerns, where integrity does not rely upon confidentiality.  These kinds of circular dependencies seem like like they are going to make it challenging to prove this scheme secure (if it is even secure).

Now maybe there is a way to prove your scheme secure.  But the onus is on you to show the proof of security.  Why would we use a scheme with no proof of security, when we have one that does come with a proof of security?