3
$\begingroup$

I have one sender, and a small number (~5) of recipients. The sender knows each recipient's public EC key. I want the sender to broadcast a single message in such a way that any one of the recipients can decrypt it. For reasons that aren't completely technical, I'd like the security properties of the encryption algorithm to be as similar as possible to those of Bitmessage, which uses ECIES, with AES and HMACSHA256 as the symmetric cipher and MAC. I'd like the encrypted message to be as small as possible.

After a brief search, I couldn't find any "standard" (well-studied, or used somewhere high-profile) extension of ECIES for this case. I can obviously:

  • Choose a random session symmetric encryption key and session MAC key.
  • Symmetrically encrypt and MAC the message.
  • Asymmetrically encrypt the session keys with ECIES, once per recipient.

Then I can broadcast a concatenation of the encrypted message and encrypted session keys, and any recipient can decrypt his copy of the session keys and decrypt the message. That adds a lot of overhead, though. So, using Wikipedia's variable names:

  1. When I do ECIES, can I omit the MAC $d$? An attacker doesn't gain anything by tampering with the session key, since that just causes the inner decryption or MAC check to fail. The answer is "no" here if we naively encrypt-then-MAC the inner message, more complicated otherwise as discussed below.
  2. Can I use the same ephemeral EC pair $R = rG$ for all recipients?
  3. Can I use the same IV for all invocations of the symmetric cipher (once per recipient in ECIES, plus once for the message itself)?
  4. If the total length of my session keys is the same as the length of my $KDF()$ output, then can I get rid of the symmetric cipher $E(k_E;m)$ used within ECIES entirely, and replace it with $k_E \oplus m$? That would obviously render question 3 irrelevant.

I think the answer is "yes to all", but some of these look potentially subtle. Thanks!

$\endgroup$
2
$\begingroup$

When I do ECIES, can I omit the MAC $d$? An attacker doesn't gain anything by tampering with the session key, since that just causes the inner decryption or MAC check to fail.

I wouldn't rely on that property. Please don't do this.

Can I use the same ephemeral EC pair $R=rG$ for all recipients?

Yes, you can do this. NaCl in principle does the same thing, but uses your own (static) private key for the key-agreement, while you make the $r$ temporarily your private key (for this message).

Can I use the same IV for all invocations of the symmetric cipher (once per recipient in ECIES, plus once for the message itself)?

Yes you can do this, guaranteed that you always have distinct keys. The DH-style key agreements will guarentee the different symmetric keys for each recipient. The encapsulated symmetric message key will also be distinct so it's safe to re-use IVs here. An alternative suggestion would be to re-use the IV, but add some small value (like 0 for the actual message, 1 for the first recipient in the list, etc.) Generally you shouldn't re-use IVs if you're not sure whether all keys are unique.

If the total length of my session keys is the same as the length of my $KDF()$ output, then can I get rid of the symmetric cipher $E(k_E;m)$ used within ECIES entirely, and replace it with $k_E\oplus m$?

I'm surprised you don't already do this. You can let your KDF generate a stream of key bytes (KDFs can output arbitrary length keys) and use them as stream cipher. This is an acknowledged variant of ECIES and is actually standardized and implemented for example in Crypto++ and BouncyCastle.

$\endgroup$
  • $\begingroup$ Thanks, appreciated. Can you sketch the attack that worries you if the "outer MAC" is omitted as in my question 1? And can we prevent that in a different way that adds O(1) bytes to the message for n recipients? $\endgroup$ – RhinoGuy Dec 4 '15 at 19:37
  • $\begingroup$ In particular, if the inner message encrypts-then-MACs, then I see how an attacker may cause the message to validly decrypt to garbage by flipping a bit in the session encryption key but not session MAC key. It seems like a single MAC that includes either the plaintext or the session encryption key prevents that, though. $\endgroup$ – RhinoGuy Dec 4 '15 at 19:49
  • $\begingroup$ @RhinoGuy, I don't have an attack at hand, but am worried because of this answer. I need to get clarity on how often an attacker has to try to get another key which will yield a valid tag. $\endgroup$ – SEJPM Dec 4 '15 at 20:05
  • $\begingroup$ What do you mean by "another key which will yield a valid tag"? If we encrypt-then-MAC the inner message, and an attacker tampers with the session encryption key independently of the session MAC key (trivial with XOR as in my q4, possible with AES-CBC if the session key length equals the AES block length and the MAC key comes first), then won't the inner MAC always pass? If so, then the answer to q1 is unequivocally "no" for encrypt-then-MAC. $\endgroup$ – RhinoGuy Dec 5 '15 at 0:35
  • $\begingroup$ @RhinoGuy, your comment isn't quite easy to understand, but I think you're right. It is trivial to manipulate the content of the message undetectly if MAC-then-Encrypt was used and one may be able to successfully manipulate the message if Encrypt-then-MAC is used, so my "no" to q1 looks like the most secure choice here. $\endgroup$ – SEJPM Dec 6 '15 at 14:09

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.