Using XOR to derive a data key for ECIES

Cryptography Asked by Maarten Bodewes on December 26, 2021

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?

2 Answers

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).

Answered by Maarten Bodewes on December 26, 2021

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$.

Answered by poncho on December 26, 2021

Add your own answers!

Related Questions

Using XOR to derive a data key for ECIES

2  Asked on December 26, 2021 by maarten-bodewes


Computing PGP ed25519 and curve25519 keygrips?

2  Asked on December 21, 2021 by skaht


Find Consecutive X-Coordinate algorithm

1  Asked on December 21, 2021 by kmart875


Why we can’t implement AES 512 key size?

3  Asked on December 17, 2021 by hamedb71


How can Cipher Block Chaining (CBC) in SSL be attacked?

3  Asked on December 14, 2021 by antonpug


Subset Sum Hashes

1  Asked on December 14, 2021 by lev-knoblock


LWR parameter estimation

0  Asked on December 4, 2021 by mev


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir