I was wondering if there exists (or if it could be created) a cryptographic system in which a message is encrypted and sent from A to B, and some nodes in the middle could intercept and decrypt the message (having been given a key for that) but in such a way that when B receives the message, he knows who has read it before it got to him.

In other words, I'm looking for a read (and even write, if possible) access log for the message. All cryptographic techniques (authentication, certificates, PKI, ...) and metadata are allowed.

  • What would happen if the intercepted message was stored for awhile and decrypted after it had arrived at B? – Blrfl Apr 12 '12 at 16:47
  • Maybe there can be a mechanism to prevent that ? What if, as mentioned in my comment to logicalscope's post, the function used to decrypt the message would not work after the message has been sent ? Maybe this idea is not that far from the already existing ideas regarding PFS or defense against replay attacks ? – bob Apr 13 '12 at 12:54
  • I've posted an answer that answers your question. – Blrfl Apr 13 '12 at 17:16

No system currently exists that does what you need. The reason is that detection of reading implies writing data somewhere. All parties would need to adhere to this principle -- be it through goodwill or because they all use the same cryptographic program/protocol.

Think of this as read-receipts in Microsoft Outlook. You can try to send an email from Outlook to a gmail account requesting a read receipt, but it will be completely ignored by the gmail receipient.1 However, depending on policies employed on the Exchange server/Outlook client, sending a read receipt request may or may not be guaranteed. So the challenge that you require is to get everyone on the same platform.

Of course, Quantum Cryptography does have the effect you are looking for. The effect here is that there is an unintentional information "write" operation occurring when you perform the read. This characteristic is merely a physical way to capture read receipts without allowing someone to opt-out.

1The email header does, however, show the systems the email traversed before arriving at its destination. This is part of the protocol adherence though it doesn't actually need to be there. That is, one hop in the network could opt to completely ignore this part of the protocol without any failure in later hops.

| improve this answer | |
  • Thank you, your explanation is pretty clear. What I had in mind was a mysterious mathematical function or cryptographic scheme that had to be applied by a user (and him only, because only him would have the correct keys for that), in order to decrypt it, but that would have the side effect of changing the information (or the meta data) in such a way that it could be traced back to the user. The user would have to be regular (not admin) and unable to copy the information in order to apply the function once, and return the message unmodified. Is that not possible ? – bob Apr 13 '12 at 9:24
  • Alternatively, I also thought of another scheme: for every read, the user has to ask permission to a authoritative person (such as the sender or receiver, perhaps), which would then be able to grant access and to give him keys so that he can decrypt the message. The authority would then have a log of read (and possibly another one for write) accesses. The user who asks the read permission would have to be authenticated so that only he can read it. The drawback in that scheme is that it's not very efficient, it requires a lot of back and forth, but maybe we could do it just once per flow. – bob Apr 13 '12 at 9:29
  • Regarding my first solution, let me develop my thoughts a little (it's not easy with 600 chars only): maybe a message M would have to be applied to f1() to pass it on, and f2() to decrypt part of it and pass it on, where f1() is made in such a way that it modifies f2(), making it unusable, so that both functions can't be used for the same message (either pass it on without reading, or read it and pass it on). – bob Apr 13 '12 at 9:37

What you're asking is really not possible.

Remember that a message is data, not a physical object and that interception doesn't always mean stopping its transit if it's in the air or on a wire. In many cases, data can be copied perfectly without any loss of transit time or leaving any traces that an interception ever happened.

The problem you're trying to solve is altering a copy of the message that neither you nor the recipient controls. In real-life terms, this isn't any different than Chuck overhearing a conversation between Alice and Bob, neither of whom know he's listening.

Making what you want happen would require three things:

  • Knowledge that Chuck overheard the conversation. So far the only systems that allow this for data are quantum, and as you and others have pointed out, that's not a practical alternative.

  • Knowledge of where Chuck and his noggin (containing what he intercepted) are at any given moment. Without knowing that Chuck intercepted the message, you're not even going to know whether it's him or one of the other six billion people on the planet you're looking for.

  • The ability to alter Chuck's knowledge of what he overheard. You could, I suppose, pay him to keep his mouth shut, but he still overheard what he overheard and changing that would be difficult. Someone else could pay him more to reveal what he knows. In more down-to-earth terms, if Chuck intercepts your message, writes what he intercepted to a removable storage and stashes it someplace safe, the fact that you've changed your copy of the message doesn't make Chuck's copy change at the same time. This is the fundamental reason what you're trying to do won't work.

Barring disclosure of your keys or someone finding a flaw in the algorithm, pick an algorithm and key length that makes your message unusable for long enough that by the time it is broken (and it will be broken eventually), it's no longer of any value. That's encryption's real purpose.

| improve this answer | |

If Bob sends a (encrypted) package of information to Alice over the Internet, it is not possible to know whether any of the intermediate nodes in the middle (or a wiretap between nodes) retained a copy of that (encrypted) package of information. It's usually not even possible to know which nodes that package traveled through on the Internet on the way from Bob to Alice.

There are a few techniques that can give you part of what you requested; perhaps one of them (or some combination) will be adequate for your application.

standard encryption

Modern cryptosystems generally give each person his own unique private key that no one else knows. (Actually, each person gets several private keys, but let's not get into that right now).

If Alice creates some plaintext and doesn't send it to anyone, except she encrypts the package of data with a modern cryptosystem and sends the encrypted package to Bob over the Internet, you can be confident that the only person who can decode that package into plaintext is the only person who has the the decryption key -- Bob.

he knows who has read it before it got to him. -- in this case, Alice and Bob can know that no one has read the plaintext before Bob got the encrypted package.

multi-key encryption

OpenPGP and similar systems encrypt a package of data in such a way that the encrypted package can be decoded by any one of many different people. When Alice created an OpenPGP package, she chooses who she wants to read that data, and the key IDs of those people are stored in that package (along with some other information that helps those people, and only those people, read that data).

he knows who has read it before it got to him. If Alice creates some plaintext and doesn't send it to anyone, except inside this one OpenPGP package, and her cryptosystem is working properly (*), then everyone can be sure that the only people who can decode that package into plaintext are the people whose key IDs are in that file.

(*) A properly-working cryptosystem, among other things, creates a new unguessable key while building the OpenPGP package, and then destroys all copies of that key except the encrypted versions inside that OpenPGP package.

(Alas, there's nothing preventing Bob or those other people, once they have decoded that particular package into plaintext, from forwarding the decoded plaintext to other people). (Also, there's no way of telling if those people actually did receive the message, unless they somehow tell you they got the message). (See Is it safe to store a single symmetric key encrypted with several different RSA public keys? for more details).

digital watermarking

information ... could be traced back to the user.

There are several digital watermarking techniques. You send each person "almost the same" or very similar data, but you make some subtle differences between the package you send to one person and the package you send to someone else. Later, if the data is leaked and posted on some website, you can analyze those subtle differences in the version posted to that website and figure out which of those people was the one that leaked this version of the data.

quantum key distribution

The quantum key distribution system allows Bob to send a key to Alice and guarantee that no one could have possibly eavesdropped and copied the key.

he knows who has read it before it got to him. -- in this case, Bob knows that no one (other than Alice) has read it before it got to him.

onion routing

With onion routing, you can package a message up in such a way that:

  • the outer 1st-level package you send out can only be decoded by one person.
  • That 1st person, if he ever decodes that 1st-level package, will discover inside a 2nd-level package that he can't decrypt, plus the address of a 2nd person to send it to, who is the only person who can decrypt it.
  • That 2nd person, if he ever decodes the 2nd-level package, will find inside a 3rd-level package that he can't decrypt, plus the address of a 3rd person to send it to, who is the only person who can decrypt it.

If that 3rd-level person ever tells you something that he could only know if he had read the plaintext inside that 3rd-level package, then you can be sure that every person along the chain has successfully decoded and passed along the package.

(This chain can be extended to many more steps).

digital signatures

Using your private key, you can attach a digital signature to a message in a way that anyone can confirm that it came from you.

Someone who receives that message can attach his own digital signature to the package consisting of { the original message, your signature }.

Someone who receives that signed message can in turn attach his own digital signature to the entire package.

The final package, consisting of the original message and a series of signatures, can be used to prove that the original message went through all those people who signed in that particular order.

he knows who has read it before it got to him. -- In this case, everyone who sees any version of this package can know that the other people whose signatures are in the package have read it before it got to him. (But with this system alone, it's not possible to tell if anyone else may have read it without signing it).

(Alternatively, signatures can be attached in a different way that also prove that the original message went through all those people, but it's not possible to show exactly what order they signed it).

(This chain can be extended to many more steps).

| improve this answer | |

Yes, this is what the trust models in asymmetric encryption work to prevent, also look up quantum cryptography. It's not all that simple, we usually can't say who, just whether it has been and maybe where in a network.

| improve this answer | |
  • This is an interesting answer, however I don't think quantum cryptography is available at usage level just yet, and I'm not looking for solutions involving science fiction, I would like a solution that I could deploy. As for the 'asymmetric encryption' you talked about, I don't want middle nodes to be unable to access the data, I just want to be able to know if they did. Maybe that's just not possible, in today's world ? – bob Apr 12 '12 at 13:43
  • 1
    Ultimately you can't track a read without either forcing it by encrypting where to send it on to as one could just send on a copy as it was received. Now if you onion route encrypt the route chain one knows they must have decrypted that part, you then include the message at each encryption level, the problem is one can only say yes or no to it being modified in some way so unless you enforce some modification it's not really possible. Now quantum cryptography will get any intercept, but again it doesn't tell much more than that. – ewanm89 Apr 12 '12 at 13:59

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.