20

Is it possible to construct a message that passively degrades over time without requiring an external factor to destroy it?

Things that are similar, but not what I mean:

  • A hard drive that degrades over time may become harder to read, but if you successfully copy the data from it to a more robust media, that data persists. Put another way, this is the media that degrades, not the message.
  • An executable that, when run, destroys all or part of itself. But if you can keep it from executing, it can't destroy itself. Here, it is not a passive trait that causes the message to destruct, nor is it unpreventable.

Instead, I mean to describe a message that goes from a readable to an unreadable state over a configurable period of time without any external intervention. For example, if I could encrypt a message using an unreproducible characteristic of a radioactive isotope, once that isotope had decayed past a point, it might not be possible to decrypt the original message. But that sounds like crazy science fiction. Are there any real scenarios where such a thing is possible?

Notes on "external"

I got a bit overexcited about this idea and abused the word "external". It doesn't matter if there are external factors involved; what I really just mean is

Is it possible to create a real system where a message can be created with a TTL and no human power can prevent that message from becoming unreadable after the TTL?

The "isotope" concept is an example where the message itself still exists, but our ability to read it decays. I don't want to get into semantics discussions about "external", but what I really mean is that the decay is "unpreventable" (without magic or even more advanced sci-fi).

Edit: I added italicized notes to the bulleted list.

kojiro
  • 579
  • 4
  • 11
  • isn't that example of using an isotope considered an external factor? – makerofthings7 Mar 06 '15 at 17:34
  • @makerofthings7-C.Lamont maybe, but the difference is that the isotope would be necessary to decrypt the message, and its age is inexorable, so the message would "naturally" be unreadable past the deadline. – kojiro Mar 06 '15 at 17:38
  • Perhaps you need to define what an "external factor" is. I actually like the idea of a key being tied to an isotope, and I don't agree that an isotope is an external factor in this case (it's a coincidental factor), but I think there are some interesting ideas here if you define your constraints a little more. – schroeder Mar 06 '15 at 17:44
  • @schroeder OK, maybe I abused "external". Edited. – kojiro Mar 06 '15 at 17:56
  • 10
    In what sense would the message exist if it's not possible to "successfully copy the" message "to a more robust media"? (Are you looking for something resembling [PUF](https://en.wikipedia.org/wiki/Physical_unclonable_function)s?) What is "TTL"? –  Mar 06 '15 at 19:08
  • 4
    TTL = time to live, I think... – woliveirajr Mar 06 '15 at 19:15
  • @RickyDemer in rereading my question I think it may not have been clear that the bulleted items were examples that did _not_ suit what I am interested in. The degraded drive is an example of the media degrading, not the message itself. I would be interested in a message that degrades no matter how many copies you make. PUFs look interesting, and related. – kojiro Mar 06 '15 at 19:18
  • 8
    In what sense would there _be_ a message if it can't be copied to standard media? –  Mar 06 '15 at 19:25
  • @RickyDemer it _can_ be copied. But all copies degrade at the same rate. – kojiro Mar 06 '15 at 19:26
  • Can it be copied _to standard media_? –  Mar 06 '15 at 19:26
  • @RickyDemer yes. – kojiro Mar 06 '15 at 19:29
  • 2
    So, Eldritch data that will make any hard drive holding it decay faster? –  Mar 06 '15 at 19:36
  • 4
    I can't tell what you are asking. Are you looking for a physical way of encoding data, so that if no one copies it for a long time, then after the long time passes, then the data will no longer be readable from that medium? Or are you looking for a way to ensure that even if someone does make a copy of the data onto their own media of their own choice, then the copy will also degrade? Achieving the latter seems pretty clearly impossible; are you willing to accept an answer that achieves the latter? Your requirements are not clearly specified. – D.W. Mar 06 '15 at 21:13
  • 9
    @kojiro "it can be copied. But all copies degrade at the same rate" So you're saying that if the message is "Hello World", and I read the message and memorize it (thus copying it to my brain), I should forget the message and be unable to remember it after the message expires? Sorry, that's not cryptography; that's magic. – Ajedi32 Mar 06 '15 at 21:29
  • @D.W. Well, my question title does start with "is it possible…", so I'm willing to accept a reasoned argument that it is _not_ possible. But to be fair, the discrepancy on most commenter's minds seems to be the question of what a "message" is. If an encrypted chunk of data could have been decrypted into a message, but cannot be decrypted anymore, is it still a message? Several of the answers I've already gotten have tried to cover this scenario, so I can't have been _that_ opaque. I was just trying _not_ to make an unnecessary constraint in a field I'm not an expert in. – kojiro Mar 06 '15 at 22:00
  • @Ajedi32 Hello... wait, what was the rest of the message? – Michael Mar 08 '15 at 06:19
  • [This message will self-destruct in 30 seconds.](https://www.youtube.com/watch?v=Y2BcEIRIw3o) – Mason Wheeler Mar 08 '15 at 12:27
  • 1
    @kojiro all the methods that handle "an encrypted chunk of data could have been decrypted into a message" still mean that if someone decrypts or reads the message while they could, then they can copy it and preserve it forever. – Peteris Mar 08 '15 at 14:56
  • Yes, I asked this question 2 years ago: http://crypto.stackexchange.com/questions/10012/is-there-a-cryptographic-function-or-system-in-which-it-becomes-harder-to-break – Chloe Mar 09 '15 at 05:08
  • 1
    @Chloe ah perfect! The answers and comments there are helpful, because I had suspected that only quantum phenomena would apply. (Particularly given what commenters here keep reminding me of – that once the message is "known" the game is up.) If only we could tell if a third observer had collapsed our wave function, we could invalidate trust in the message. – kojiro Mar 09 '15 at 12:21

9 Answers9

14

Let's dispense with the "if it can be copied" part first. I can start with a camera and work my way down from there. I can also enlist a sufficient number of monks, nevermind digital media.

Pretty much everything can be copied if you have enough time and enough monks

You're on a track with radioactive decay. If you can arrange a sufficiently large key that is represented by a number of decaying radioisotopes and arrange that key with a error correcting code, then you would have a predictable loss of the key within a certain time window that's a function of losing N bits of data at a rate determined by the half-life of the radioactive media combined with the M bits of losable key.

This still leaves the idea that a partially decayed key provides a better place to start than a fully decayed key, but then we're back to math about the number of attempts to fix the errored key and that's a mathematical combination as well. Once the key is decayed such that half the bits are likely wrong after the error correctable size then your data would be guarded just as well as if an attacker had nothing.

Doing the time-related math for your selected radioactive material and EC code is an exercise for the reader.

Jeff Ferland
  • 38,090
  • 9
  • 93
  • 171
  • 3
    I would surmise using blind monks for oral transmission could provide the upper bound to the survivability of the message! – munchkin Mar 06 '15 at 19:38
  • 2
    If you want to make this into an all-or-nothing switch, use some secret sharing algorithm. Once the number of good numbers goes below the threshold, the remaining ones don't tell you anything. – Christopher Creutzig Mar 07 '15 at 21:00
  • 1
    If someone has the key before it decays they can simply copy it to a medium that does not decay. – JamesRyan Mar 09 '15 at 10:55
  • 2
    And that's why the very first sentence says "give up on protecting against copying." As soon as somebody has access all the pieces they can all be copied. – Jeff Ferland Mar 13 '15 at 18:40
12

If time is the constraint, then use time as the solution.

One Time Passwords can use time-synchronization as a factor. You could design a system whereby a OTP algorithm is required, but use the time-sync portion not only to verify the OTP, but also as a check to see if the time threshold has been exceeded.

schroeder
  • 123,438
  • 55
  • 284
  • 319
  • 2
    Crypto isn't my field, so with my limited imagining of it I always think you should be able to spoof a timestamp. Can't I just set my computer's date back, disable ntp, and decrypt the message? – kojiro Mar 06 '15 at 17:55
  • but a OTP has to sync with a 3rd party's clock - that's the difference. If you use Google Authenticator, and try to change your system clock (or if your clock is 5 minutes off) - the OTP fails. So, if you used Google's OTP process, you can be sure of the time. – schroeder Mar 06 '15 at 18:01
  • 3
    But isn't it true that if you use totp and offline everything, arrange it such that the environment ( system clock, totp token, etc ) is correct for that particular time period, you would be able to circumvent this method? – munchkin Mar 06 '15 at 19:55
  • "and offline everything"? yes - if you had control of all parts of the OTP, you could, but if you depended on the 3rd party to remain outside of the attacker's control, you have a level of assurance – schroeder Mar 06 '15 at 20:01
  • 2
    Of the many answers here this is the most reasonable and realistic – KDEx Mar 07 '15 at 00:22
  • 9
    I don't see how the OTP property figures in here. The fundamental idea rather seems to be to require a third party for decryption and that party to refuse after some time, yes? – Christopher Creutzig Mar 07 '15 at 20:58
  • @ChristopherCreutzig the 3rd party is only used for the OTP synchronization. The resulting valid key is used as part of the decryption. Like a 2FA rolled into the decryption key. – schroeder Mar 07 '15 at 21:23
  • 10
    But what system is responsible for checking the time and how is it passive? What keeps me from telling a computer it's 1900 or 2100? – Jeff Ferland Mar 08 '15 at 03:09
  • Technically, OTP does not need a 3rd party. OTP means that you have a high-entropy (“truly random”) key as long as your message and use it only once. (That's the “OT” in “OTP”, whatever $anyone may market under the name this year.) I'm not sure what “synchronization” means in this context: As soon as you use any part of the key multiple times, the security goes out the window anyway. Sure, you can have some time-dependent starting point in a sufficiently long key, and you can require a third party to find it. That's still a form of “use-before x.x.x key escrow.” – Christopher Creutzig Mar 09 '15 at 14:29
8

If I understood what you want correctly, in special the hard drive example, then no.

Because if someone was able to read the message during some time, it means that he was able to save it form the computer to a flash disk, print it, extract it from the computer memory, copy it using pen-and-paper, photograph, audio/video record it, memorize it, speak it aloud etc. So even if the media is degraded, the message was saved again in some other media, even if the media is the brain of the person who read / listened to the message.

But if your scenario doesn't include that, and you mean that the message was stored in some computer that was totally secured, and that you want to be able to retrieve the information just during some specific time, and not before/after that, then yes: you can encrypt it using the strongest encryption you have, and then have some third party provide you the key just at the specific time. Since no-one would have access to the computer, the key would be able to decrypt the message only during that time. Before, brute-force would fail. After, the key wouldn't be provided. And instead the problem being your computer, it would go to the 3rd party providing the key.

woliveirajr
  • 4,462
  • 2
  • 17
  • 26
  • 1
    heh - an expired key escrow agreement – schroeder Mar 06 '15 at 19:14
  • Sorry, I think it may not have been clear that the "hard drive" example was an example of the media degrading, not the message. IOW the hard drive was an "external factor" that you can easily overcome by copying the file. What I mean is that even if you copy the message, all the copies degrade at the same rate. – kojiro Mar 06 '15 at 19:21
  • 4
    @kojiro The message is something, the media is another. The message is "Hello world", once you read it, I just can avoid that you spread it if I prevent you talking to anyone else. Except in a very restrict environment, where anyone who has access to the message dies or is isolated from the humanity, any time someone has access to the message, you lost control over it. – woliveirajr Mar 06 '15 at 19:27
5

Here are some ideas for you:

It sounds like you want to rely on physics and nature to act as the time constant t to degrade the original message m into m' where m' = f(t,m)

  1. Isotopes, cosmic radiation, the predictable orbit of the Earth, could all act as t.

  2. Use t to generate an OTP (or more secure equivalent) or XOR the output

  3. Figure out the math to do #2 above.

  4. Profit!!!

Alternatively

Things might be easier if we replace #1 with a computation bounded by physics, where computing the discrete logarithm reveals part of, but not all of the message. The longer you wait, the bigger the number is, and the harder it is to factor.

The inspiration I have for the previous paragraph is the Bitcoin Blockchain, and I'm re-imagining the solved "target" as having the previous block as a factor of the next block.

  Block #1 =  11  (this prime decrypts the first word of the file)
  Block #2 =  #1 * new prime
  Block #3 =  #2 * new prime
  Block #4 =  #3 * new prime
  ...

To prevent cheaters from rolling back the time (to get an easier number to factor) old blocks would be discarded on this prime chain.

How would you implement this? You would need a system that doesn't keep a full history of these primes. In bitcoin lingo, have a well known publishing sending address. This address inserts data into the chain, where the data is a NOP-opcode delimited list of puzzles (one prime per sentence). The client would then list all the prime numbers and work hard to decrypt each sentence until it gets too hard to solve.

Would love to see or hear more about anyone who wants to explore this idea further.

makerofthings7
  • 50,090
  • 54
  • 250
  • 536
  • If you're wondering what brought this idea up… I was reading [Laptop Security while Crossing Borders](https://www.schneier.com/blog/archives/2009/07/laptop_security.html) and wondered if it was possible to create a key that would only be valid in a limited window, like a timed safe. (In Schneier's article's case this would be useful because you wouldn't need to put your key in human escrow.) – kojiro Mar 06 '15 at 19:52
  • This seems like an example implementation of a more general concept - the message is encrypted, the "reader" doesn't have the key but can obtain it from an external oracle; when the key is not obtainable anymore (the oracle can not or will not give the key, depending on implementation) then the message is, in essence, destroyed. Of course, that doesn't prevent a reader from reading and copying the message, but nothing can do that. – Peteris Mar 08 '15 at 14:52
4

This isn't my forte but if;

1) you don't want copying the message to stop the degradation 2) you want the message to be readable (understandable?) up to a predefined time - presumably with some given accuracy on that time 3) you have no limitations in the minimum length of time required

Then a simple solution is write it in a colloquial dialect, then wait for that language to either evolve to the point of obfustication whereby the variations in colloquialisations render the message unclear or the language simply dies out. To calculate the time this takes you could look at past languages, or even specifically choose phrases that are on the decline (google actually tracks this kind of stuff, when I'm off my mobile I'll produce a few links). The predicted time will be just a estimation, but then that all comes down to error bars.

FraserOfSmeg
  • 163
  • 5
2

Ridiculously enough the opposite is true. It is possible to construct a passively more readable message. Consider the use of cryptography in messages. Moore's Law virtually guarantees everything will be readable at some point.

And so to go the other way, you need to have a strongly encrypted message whose keys somehow expire. At which point you're now faced with date attacks. The other way would be to somehow incorporate somekind of heartbeat mechanism.

It is all rather difficult to do. And so logically, the holistic method is to require the recipient to be in a secure area where it is impossible to digitally copy the message and delete all related activity after the time.

munchkin
  • 393
  • 1
  • 5
  • Sufficiently strong ciphers cannot be read through brute-force before the heat death of the universe, even if you turned the entire universe into a cipher-breaking computer. The threshold for this is surprisingly low, probably somewhere between 192 bits and 256 bits for a symmetric key. – Mark Mar 07 '15 at 06:36
  • Precisely my point, you choose a key size that is low enough that in 2-5 years, the messages are readable. – munchkin Mar 07 '15 at 13:16
  • On the contrary... if we allow for enough time for the message to decay, actually all messages currently meet OPs constraint. Proton decay of 10^32 years and black hole evaporation by 10^100 years will ensure all messages eventually self-destruct. – Michael Mar 08 '15 at 06:23
  • As they say in economics, in the long run we're all dead. Or in this case the mastication of messages in memoriam by a massive black hole. – munchkin Mar 09 '15 at 01:42
2

You could use some "hardened" systems such as those that exist on cell phone cards, credit cards, etc. that run a small computer and can physically destroy themselves after some condition is met (i.e. 3 invalid attempts at a pin) - these could be enhanced relatively easily to where they contain a small timer/battery (and last for years), and designed to be tamper-proof such that they destroy themselves rather than displaying the information.

The problem comes in when you want to read the data - how do you make sure that there are no copies made? you can't show it, as that would mean it can be copied via photographs, you can't play it, as then recording devices could be used, but perhaps you can send it digitally - obviously it would need to be encrypted, and you would need to verify that the receiver is not compromised in any way or it could be modified to re-transmit the message. Unfortunately I don't see any good ways around this issue, because ultimately if you have so much trust in the receiver, you may as well just give them the message at the start and be done with it. What usefulness this is I don't know, unless the information quickly becomes obsolete as soon as it's used (i.e. the launch code for a particular nuclear missile - once it's launched, it doesn't matter who has the code, since it's useless).

user2813274
  • 2,051
  • 2
  • 13
  • 18
1

Inherently, if the encrypted message can be decrypted once, it can be stored in decrypted form, and there is no way to do anything further.

HOWEVER

There is a way to make it HARDER to decrypt as time goes by.

If the time it was encrypted was made part of the key, and assuming it was not leaked in any way (e.g. file timestamps), then someone decrypting the message would have to try different times. If the receiver has no way of knowing the actual time it was sent, then they would have to try all times from now back to when it was encrypted. This means that, as time passes, there are more timestamps to try.

You could use the accuracy of the timestamp (days, seconds, microseconds) to make it more or less difficult. The difficulty would increase linearly, i.e. if twice as much time has passed, it will be twice as difficult to decode; I don't think there's much to be done about that.

Note that this approach is prone to a lot of key leakage - if you know when the message was encrypted, even approximately, then the timestamp searchspace can be hugely reduced. Also, if the receiver knows what time of day the message is likely to be generated in, that would also reduce the searchspace - "business hours" covers only 1/3 of the 24 hour clock, so if an attacker knows or suspect it was written in business hours, the searchspace is reduced by 2/3.

Also, as mentioned before, most files have timestamps - this would give the answer immediately. If there is some other information (e.g. which order the messages were encrypted in, as in a conversation) then this would greatly weaken the system.

AMADANON Inc.
  • 1,481
  • 9
  • 9
0

No. Just no.

You said:

Sorry, I think it may not have been clear that the "hard drive" example was an example of the media degrading, not the message. IOW the hard drive was an "external factor" that you can easily overcome by copying the file. What I mean is that even if you copy the message, all the copies degrade at the same rate

And this is impossible. Some other answers pointed this out already, but not prominently enough in my opinion.

As soon as you read a message for the first time, you can copy and preserve it forever.

You can build systems which only release the plain text message during certain time frames, but once it's out, it's out. And even such systems still need to be active some way, like a storage medium with a time bomb strapped to it or a NAS unit with an UPS which starts overwriting its data at some point until power runs out, or the accepted answer where a trusted third party confirms the time.

Nobody
  • 686
  • 4
  • 10