6
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ What bothers me intuitively with this scheme is that the symmetric key may no longer be random as it would be when it was a direct output of a KDF given the afterwards combination with an unauthenticated value. But I can't translate that into a an attack right now nor come up with reasoning why it won't potentially be a problem. $\endgroup$ – SEJPM Jul 24 '20 at 10:07
  • $\begingroup$ On the other hand, ECIES or RSA-KEM based schemes are not authenticated anyway; if you want authenticated then it is possible to add a signature. I don't see anything that would make it less secure than unauthenticated ECIES - but I might be mistaken in that regard so please use this as attack vector! $\endgroup$ – Maarten Bodewes Jul 24 '20 at 10:09
  • $\begingroup$ I have the exact same question. In SEC1 this is called "XOR encryption scheme", but the spec requires also using a MAC. Could you avoid this MAC is if you use authenticated encryption with the key being encrypted anyway? $\endgroup$ – Conrado Jul 24 '20 at 12:08
  • $\begingroup$ I think my scheme is more XOR encryption (of a secret key, so key wrapping) combined with a symmetric cipher. As for the MAC, no indications are given why it is even needed in SEC1. Of course with ECB / CBC there are padding & plaintext oracle attacks to deal with. But remember: any attacker can encrypt any ciphertext with ECIES. So a MAC can certainly not be seen as a way to replace a signature. Once you have a signature, you certainly don't need a MAC anymore if you ask me. $\endgroup$ – Maarten Bodewes Jul 24 '20 at 12:56
  • $\begingroup$ Heh, if I just see it as key wrapping I can probably prove that it is secure. And in that case I might as well use AES-SIV. Before that I looked at it as some kind of derivation. Funny what you get by just talking about a solution. $\endgroup$ – Maarten Bodewes Jul 24 '20 at 12:59
3
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.