7

I have read up on Digital signature and it is stated that it provides non-repudation.

Assuming Alice signs the message using her private key and sends it to Bob, Bob can use Alice's public key to verify the signature hence Alice cannot deny sending the message. This only proves that Alice is the sender of the message.

How can Alice have proof that Bob has received the message sent from Alice?

10

In practice, unless Bob sends a signed receipt, you are out of luck.

The underlying cryptographic problem is called fair exchange. If you consider a network protocol such that Alice and Bob want to send each other some data elements (e.g. in your case an email from Alice to Bob, and a receipt from Bob to Alice; but it also works as a model for payments), then Alice and Bob will send messages. Let's call ma the element that is to be conveyed from Alice to Bob, and mb the element that should go from Bob to Alice. When the exchange protocol is played, at some point in the sequence of messages, Alice will obtain enough information to be able to rebuild mb. That point will be immediately after reception by Alice of some protocol message from Bob; before the message, Alice does not know enough to rebuild ma, and after she does. Similarly, Bob will also obtain enough information to rebuild mb right after having received some message from Alice.

The tricky point is that there is no such thing as simultaneity. You cannot ensure for two remote people (Alice and Bob) to send messages at the same time. Thus, Alice and Bob get all they need at necessarily distinct moments. Suppose that Alice gets her element first; then she may simply stop responding at that point. Bob will never get the element from Alice, while Alice got the one from Bob. The exchange is unfair.

To get some intuition about what I explain above: suppose a simple protocol by which Alice sends an email to Bob, then Bob sends a signed receipt. In that case, Bob could get the email and refuse to send the receipt; Alice would have no proof. To fix that, you may want to design the protocol such that Bob sends the receipt first, and then Alice sends the email. In that case, Alice could cheat by getting a receipt from Bob, then refusing to complete the protocol and send the email.

What I mean here is that the flaw is fundamental. There can be no two-party protocol, however complex and convoluted, that ensures a fair exchange. This is because of the lack of simultaneity.


Now impossibility results have never discouraged people from trying. There are mostly two methods to get a fair exchange protocol:

  1. Make it so that cheaters pay for it. For instance, Alice sends an encrypted email to Bob, with a symmetric key Ka. Bob sends an encrypted email to Alice, with a symmetric key Kb. Alice and Bob then send each other the keys, bit by bit, one at a time. Either may bail out of the protocol at any time, with a partial key knowledge, and try to complete decryption through exhaustive search of the missing key bits. A cheater will then have an advantage over the other, but only by one bit in the resulting brute force. There is some remaining unfairness, but only a small one.

    For such a protocol to work, some additional mathematics must be thrown at it, so that Alice and Bob may prove to each other that the "encrypted messages" they sent are the genuine things, and not some chunks of random junk. There are a lot of details to care about.

  2. Have a trusted third party. This is the model of existing postal services around the World. Alice gives the letter to the postal service; the postman then ensures that Bob will get the letter only after having signed the receipt. This works because both Alice and Bob trust the postman: Bob knows that the postman will give him the letter, and thus has no problem with signing the receipt before having the letter in his hands; Alice knows that the postman will not give the letter to Bob without receiving a receipt first, and the postman will send the receipt back to Alice.

Standard emails follow neither method right now. Some people are running Web-based services in which they play the role of the trusted third-party; I am not sure any of them has reached any level of significant commercial success. I am not aware of any deployed in the wild implementation of a cryptographic fair exchange protocol.

  • "unless Bob sends a signed receipt, you are out of luck." Receipts can be forged. – K. Alan Bates Nov 14 '14 at 20:16
  • In all of this I am assuming signed receipts, with a signature algorithm that cannot be forged (because both Alice and Bob know each other's public keys). – Tom Leek Nov 14 '14 at 20:37
  • Does the bitwise exchange even work in this scenario? There is only one sensible message Bob can send (i.e. "I have received your message"), so sending one bit is the same as sending all of them. – Fax May 21 at 10:14
10

TL;DR Anyone can send a message and say it is from Alice if it is not signed; there is no way for Alice to prove that she didn't send those unsigned messages. However, Alice can prove she sent a message by signing it with a private key. Similarly, anyone can say Bob read a message, and Bob can't prove he didn't. But Bob can prove he read a message by signing it with his private key.


A small side point, I'm going to make a distinction here between having received and read a message. I can send an email to your mail server, (and the network will confirm that it was sent), but if your server is ignoring all incoming data, even though the network says it was received by your firewall, it doesn't mean the mail server actually read the message or has access to it in any way.

In good cryptography, it's assumed everyone can receive the message, but only the indented recipient can read it. Even though Alice here isn't actually encrypting specifically for Bob, we will assume that the message is posted in some public way that it guarantees that Bob could receive it if he wanted to, but encrypted so only Bob can read it (even though you might not technically encrypt it, just require Bob to log into Gmail with his username and password, but the same principle).

In such a case, there is no way for Bob to prove he hasn't received the message; after all, Bob could download (receive) the email from Alice from the mail server to his computer, but not actually open (read) it. If the message was encrypted, he could save the message and his private key to a non-networked computer and decrypt and read it there, burning the computer after he is done. No one could know if he successfully successfully decrypted and read the message or not.

However, at any time, Bob can prove that he has read the message by signing the decrypted message Alice sent, and sending back the signature. The only way he could have access to and sign the decrypted version (which would include having read the non-encrypted email from his Gmail account) was if he had read it.


Addendum: Ideally, Bob would sign the message with his own private key, but this isn't strictly necessary. As long as the message "encrypted" (or sent securely) in some way that only Bob can read it, the only one that could possibly have access to and sign the "decrypted" message is Bob*. If the message is not encrypted or sent securely, anyone could sign Alice's message with any key, claiming to be Bob that signed it.

* Technically, there is a second person who could sign the decrypted message: since Alice wrote the email to Bob, she has access to the unencrypted message and could sign it, claiming to be Bob. If she just wants to know if Bob read her message, this would be silly of her to do. However, if Alice wants to prove to the authorities that it was Bob that read her email, Bob would need to sign the decrypted message with his private key (which Alice would not have access to).

  • Alice can prove she sent a message by signing it with a private key. She can say that she sent it and you can be sure it was her who said it (by verifying the sig), but she can still lie. – user10008 Nov 15 '14 at 10:37
  • @user10008 I don't follow. Could you elaborate? – IQAndreas Nov 16 '14 at 5:00
  • You said that she can prove to a third party not trusting her that she sent some message to bob, by signing it. However, as she possesses the private key, she can sign anything, and so "prove" she sent something to bob she didn't actually send. DKIM would be an example with which she can actually prove she sent a message, provided that people trust her mail provider. – user10008 Nov 16 '14 at 6:59
  • @user10008 Alice can prove to a third party that she was the one who sent Message #1367882 by signing it. Whether the recipient of that message was Bob, or if he even received it is irrelevant. – IQAndreas Nov 17 '14 at 19:29
3

If you want to require Bob to let Alice know whenever Bob has received a message, as far as I know there isn't any such system built into the most common cryptographic systems. You would need to go outside of cryptography for a bit and require a server which tracks every time a message is downloaded from it.

For instance, Alice could send a secret URL to Bob that tells him where he can find the message. When Bob opens that URL, the server on the other end tracks that Bob has accessed the URL, sends a receipt to Alice, and sends the data to Bob. If you want to be pedantic, there is always the possibility that Bob says the URL request didn't complete, and although he sent a request for a message, there was a network problem, and he never received and read the data.


This next part was supposed to be a comment, not part of the answer, but is too long for the comment field:

You could devise an elaborate cryptographic system where each time Bob accesses the URL he receives (1) a single character of the message and (2) a small bit of data he has to sign with his private key. He stores the character (appending it to the data he has already received), and then signs and sends back the bit of data to get the next character of the message.

Alice can therefore prove exactly which characters in the message Bob has received. Well, almost exactly. Keep in mind, Bob could always say "I received 499 characters, but not the 500th character, therefore I didn't get the entire message." assuming he refused to send back the proof of work for the last character he received.

Alice could also do this on a per-message basis rather than a per-character basis. In each message, Alice sends instructions on how to decrypt the text message (perhaps including a one-time pad). She can never prove that Bob has read the latest message she sent, but if she can prove that Bob has read a single message, she can prove that Bob read every message before that one.

  • I have added two different answers for a reason; the first answer is a Cryptography answer, while this is a Computer Sciences answer. As they are two completely different ideas, I wish for them to be up- and down-voted independently. – IQAndreas Nov 14 '14 at 9:39
  • That system can only prove that data has been accessed, not that Bob was the recipient. If the "secret URL" is accessible remotely, you can't even guarantee that the handshake that resulted in a secret URL going to Bob was the one that resulted in a request for you to serve data. Even with RSA encryption, secrecy of Bob's private key is essential. If that key is compromised, then all bets are off on all communications between Bob and Alice from the point the key was known. I know I'm nitpicking, but the words "prove" and "guarantee" were used. You can't. – K. Alan Bates Nov 14 '14 at 20:26
  • That system can only prove that data has been accessed, not that Bob was the recipient. > Assuming the URL is random enough so that the possibility of a third party guessing or randomly coming across the URL is near zero. You could also add a password prompt to the page, but I'd argue that is no more secure than a longer URL. – IQAndreas Nov 14 '14 at 20:36
  • 1
    All of these things increase the likelihood that requests for resources originate from Bob. If we're involving heuristic devices rather than mathematics, then yes, you can essentially "guarantee" that Bob was the originator of a request to a randomly generated resource with a sufficiently tight TTL. But mathematically speaking, you can't guarantee it. You could transmit Bob the secret URL and he could hand his private key and that secret URL to Charlie immediately after you send it. – K. Alan Bates Nov 14 '14 at 20:42
  • 1
    I don't think there's anything particularly wrong with your answer. I just wanted to interject that when the words "guarantee", "proof", and "non-repudiation" are involved with distributed systems, your best case scenario smashes face first into a brick asymptote that cannot be overcome. – K. Alan Bates Nov 14 '14 at 20:44
-1

There is only one way for Alice to truly prove that Bob has received her message:

Hand it to him


Even with asymmetric keying, you can only have reasonable assurances that the communication channel is secure and that the intended recipient is receiving your messages.

You can guarantee that Alice's private key was used to encrypt a message. You can guarantee that Bob's private key was used to sign receipt of a message. What you cannot prove is whether Alice or Bob were the bearers of those keys at the time of transmission.

My point is, there is no way to -mathematically- guarantee secure communication of distributed messages. Your best case scenario smashes face first into a brick asymptote that cannot be overcome, so words such as "proof" and "guarantee" should be avoided. Your best case scenario is "Ehh, that's close enough."

The only way for Alice to guarantee that Bob receives her message is to physically hand it to him, and that only holds true if Alice can physically identify Bob, unfailingly.

  • My point was that you have no guarantees of valid receipt or non-repudiation in distributed messaging. You can have reasonable assurances. You can know, unequivocally, that Alice's private key was used to encrypt a message, and you can know that Bob's private key was used to sign receipt of a message, but you cannot prove that either of those parties were the bearer of the keys at the time of communication. Reasonable assurance is your best likelihood without manual confirmation from the repudiating party that they did, in fact, receive the message in question. – K. Alan Bates Nov 14 '14 at 20:50
  • 1
    @TildalWave "this should have been a comment." I disagree. The only solution to the Byzantine Generals' Problem that can be guaranteed to work is to eliminate the valley. – K. Alan Bates Nov 14 '14 at 20:57

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.