Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
crypto.SE is clearly the better choice –  CodesInChaos Apr 21 '12 at 8:46
add comment

1 Answer

up vote 3 down vote accepted

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)))
share|improve this answer
    
But doesn't this require the whole message to be known before Bob can authenticate Alice, though? Or can the signature and the message be concatenated the other way? If so, it does look considerably simpler (although the same amount of data is still sent since public key encryption/signing requires padding anyway). It essentially removes the nonce from the protocol. –  Thomas Apr 21 '12 at 13:01
    
@Thomas: Yes, in this scheme the signature can only be checked after the message did arrive and is decrypted. But this is normally not a problem for use cases like email ... and in your protocol, Bob still needs to verify the integrity of the whole message after decrypting it. –  Paŭlo Ebermann Apr 21 '12 at 13:07
    
But what if an attacker decides to send me a large message (not necessarily email), I am forced to accept receiving the totality of it until I can deny it. This would constitute a basis for a denial of service attack, wouldn't it? –  Thomas Apr 21 '12 at 13:15
    
If an attacker captures a valid message and changes part #3 to be really large, you have the same problem. But yes, you are right that one could implement some counter-measures here, like encrypting the signature of a nonce first, then the actual message (authenticated with a MAC) (and immediately, the protocol gets a bit closer to your one, and less simple). –  Paŭlo Ebermann Apr 21 '12 at 13:24
    
True. A solution would be to put the message length next to the message hash. But the attacker could still mess with it and randomly change it to something probably much larger, so it could have its own hash too (which solves the problem). But I agree, it does get more complicated quickly. Though I want the protocol to be as robust as possible though, as I won't only use it for email (that's what I had in mind initially) so it makes sense to plan it properly. –  Thomas Apr 21 '12 at 13:29
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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