Using XOR to derive a data key for ECIES

Question

I have been thinking about a rather simple enhancement for (EC)IES / RSA-KEM. The scheme would allow you to encrypt data while the calculation of the session / data key can be performed afterwards or in parallel. It would also allow you to encrypt for multiple recipients.

Anyway, the scheme would simply be:

1. Generate a (random) symmetric key: $K_d$;
2. Encrypt data with key $K_d$ using a symmetric cipher, resulting in $C$;
3. Generate an ephemeral key pair with public key $\widetilde{P}$;
4. For each recipient enumerated by $i$:
   1. Calculate a session key $K_i$ by performing key agreement with a static public key of the receiver (followed by a KDF);
   2. Perform $A_i = K_i \oplus K_d$;
   3. The messages consist of a quad $(i, A_i, \widetilde{P}, C)$ where the $i$ is just used to indicate the recipient.

To decrypt you would simply perform the key agreement again, followed by $K_d = K_i \oplus A_i$. For RSA-KEM the ephemeral key pair derivation is not required, and $\widetilde{P}$ is replaced by the result of the RSA-KEM operation with the public key of the receiver.

This seems to be a specific version of a simple Multi-Recipient Symmetric Encryption Scheme using Secret Sharing combined with (EC)IES or RSA-KEM. Obviously you'd have to store the $A_i$ values with the ciphertext, so that is a disadvantage compared with the normal ECIES approach.

Are there any particular problems with above approach? Are there more secure / flexible / efficient schemes to do the same?

Answer 1

As written, it makes an additional security assumption on the symmetric cipher; that the attacker can't flip bits in the key (and modify the ciphertext) to gain some advantage. That is likely true for most ciphers we would use in practice, but is nevertheless an additional assumption.

This is not difficult to fix; we don't select a random symmetric key $K_d$, instead, we generate a random value $J$, and set $K_d = \text{Hash}(J)$. Then, in step 4.2, we then instead set $A_i = K_i \oplus J$.

Answer 2

The remark of Conrado showed me that I could look at the XOR as a simple key wrapping operation, which is basically just another encryption. In that case it is clear that the scheme is secure for confidentiality; it just adds another layer of encryption.

Of course, encryption by itself doesn't offer integrity / authenticity. ECIES cannot offer authenticity by itself as any adversary can encrypt with the public key. However, as poncho pointed out, the problems would be exacerbated by using the XOR, as any bit in the encryption key can now be flipped by an attacker. That could e.g. enable related key attacks on the cipher.

For this reason it is probably a good idea to either hash the output of the key so that bit flips will 50% of the output bits on average (poncho's solution). Another way would be to use e.g. AES-SIV instead of XOR to make sure that all the bits of the encrypted key are related. The wrapped key would then be the $A_i$ value.

Finally, if the output of the scheme is all authenticated using a signature then the problem of the bit flipping are also removed. However, that does assume a encrypt-then-sign scheme, which has it's own drawbacks (mainly that the signature can be removed or replaced by another signature).