Is this authenticated one-way communication protocol secure?

Question

I am looking to see if this one-way communication protocol is secure. Assume Alice wants to send Bob a message (and doesn't need Bob to reply in the same session/channel - think email). Bob knows Alice's public key $A_{public}$, and Alice knows Bob's public key $B_{public}$. Assume ideal cryptographic primitives for the hash function (ideal one-way function) and symmetric cipher (ideal random permutation) and that the bit sizes used are large enough to ensure computational security (say RSA-2048, a 256-bit symmetric key, 256-bit hash function output and 256-bit nonce)

---

Protocol

Field #1

Alice randomly generates:

• a key $K$ for an agreed upon symmetric cipher
• other material needed for the cipher (IV, etc..)
• a nonce $N$

Alice encrypts all of the above using $B_{public}$ (with random padding).

Field #2

Then she computes $\textrm{HMAC}(N, A_{public})~~$ (where $N$ is used as a key), signs it with her private key (with random padding)

Field #3

Finally, Alice calculates her message's hash. Then she encrypts it along with the message itself, using the symmetric key $K$.

She then sends to Bob, in this order:

• the first field (the one encrypted with Bob's public key)
• the second field (the one signed with her private key)
• the third field (the one encrypted with the symmetric key)

---

Proof that Bob can decrypt it

Bob can obviously decrypt Field #1. He can then iterate through his list of known public keys (assuming he doesn't have millions of them, it will be efficient enough), undo the signature, and verify Field #1 using the nonce $N$ against the HMAC. Bob can then know Alice did send both fields, and as he knows the symmetric key, he may decrypt the message and verify its integrity against the message hash.

Bonus: this also offers some protection against accidental corruption. If Field #1 in its encrypted form is corrupted while being transmitted, the nonce $N$ will be corrupted with overwhelming probability which will prevent Bob from authenticating Alice. If Field #2 in its signed form is corrupted, the HMAC will be garbled, with the same consequences as before. And if Field #3 is corrupted, the message hash will detect it.

Of course if either Field #1 or Field #2 are damaged, then Bob will not know that Alice sent the message and so cannot ask for a retransmission unless he asks all his contacts (which isn't very practical), but there are probably methods to fix that.

---

Expectations:

Define "attacker" as an entity which has no knowledge of Alice's private key or Bob's private key.

1. an attacker should not be able to impersonate Alice
2. an attacker should not be able to read nor modify the message
3. an attacker should not be able to deduce the sender (Alice) nor the recipient (Bob)

Analysis:

1. This is just a draft but my initial analysis of the protocol shows that it mostly relies on the nonce $N$ - if the HMAC signed by Alice can be verified, then it implies that Field #1 was indeed created by Alice and the rest follows. Note that if the nonce $N$ was not placed inside Field #1 but instead in Field #2 for instance, then an attacker could trivially forge Field #1 while leaving Field #2 intact, which would allow him to impersonate Alice. So the protocol depends on the link between Field #1 and Field #2.

2. This easily follows from 1, since the attacker cannot impersonate Alice then he cannot forge neither Field #1 nor Field #2 which implies that he cannot forge (nor read) Field #3 either, as the symmetric key is in Field #1. If a streamed mode of operation is used for the cipher, he could attempt to tamper with some message bits, but this would be detected by the message hash.

3. This is more interesting. Field #1, even as plaintext, only contains random data, so it is of no use to an attacker on its own. Field #2 could in theory be decrypted by an attacker by looking up some LDAP table and checking every public key he can get his hands on, however without knowledge of the nonce $N$ (which cannot be obtained by the attacker) the HMAC would reveal no information. So the attacker has no way of establishing which public key is in fact the right one, as they all result in random data from the attacker's point of view. And Field #3 is of course of no use without the symmetric key. So an attacker cannot deduce neither the sender nor the recipient using only the data sent over the channel. Note that again, if the nonce $N$ wasn't in Field #1 but in Field #2, then the attacker could fairly easily identify Alice (but not Bob).

Finally, since the whole protocol is almost completely randomized, replay/related-key attacks are not applicable, and the attacker will not be able to reuse any past communications to his advantage. In fact assuming different, independent messages are sent each time, the only quantity which is always sent to Bob is Alice's public key, and it is masked by the HMAC (with the random nonce). Of course the drawback of all this is that the random number generator better be good as it will almost certainly be the weakest link in the chain here (but isn't that always the case?).

---

Is this secure? Are the security expectations met with the given conditions? Does anybody see anything I might have overlooked here, or perhaps a way to simplify the protocol while maintaining its security by sending less stuff? For instance a way for Bob to easily figure out who is sending him the message without him having to iterate over his contact list, while leaking no information to the attacker (I don't see how this is possible, as the only way for Alice to prove her identity is to sign a verifiable quantity, and this quantity must only be verifiable by Bob to meet expectation 3)

As far as I can see this scheme is algorithmically secure and provides external anonymity for both parties, authenticity for both parties (Alice knows only Bob will be able to read the message, and Bob knows Alice sent it), and integrity. But I am aware cryptography is not a trivial matter which is why I'm submitting the protocol here to see if I missed any obvious weaknesses.

Thanks and all feedback is welcome. This is all theoretical by the way, but comments on software bugs that are likely to occur and their implications are welcome too (for instance, can a software bug permanently compromise Alice and/or Bob, or just the communication where the bug occurred?)

PS: I wasn't sure whether this should go in Security SE or Cryptography SE. I opted for Cryptography since it's more about algorithms than implementation but I apologize in advance if I was wrong.

Answer 1

I think you are right, the non-identifiability of Alice and Bob by an attacker is the problematic point. For this to work, you need some requirements on your public-key encryption and signature scheme(s):

• An encrypted message (i.e. your field 1) does not allow any clues on the public key used to encrypt it.
• A signature (i.e. your field 2) does not allow any clues on the public key to be used for verification, as long as the message itself is not known, but allows retrieving the signed message when the public key is known ("undoing the signature").

I'm not sure if these are valid for RSA. The second can only be valid for "sign-by-encrypting-with-private-key" schemes like RSA (e. will not be valid for DSA), and I'm not even sure if it is valid for RSA.

I think that these properties are normally not what public-key schemes are designed for.

(But I might be wrong here, if so I hope someone will correct me.)

In general, your split into the fields #1, #2 and #3 seems a bit complicated. Is there any reason that Alice doesn't use the usual scheme?

• Encrypt($B_{public}$, $K$)
• Encrypt($K$, message || signature($A_{private}$, hash(message)))