71

Are there any cryptographic schemes/protocols that would allow me to encrypt a file, make it publicly available, but ensure that it can only be decrypted after specific date?

I assume it would be almost impossible without a trusted authority (notary). Or is there some way?

I was inspired by the idea of "secure triggers", which is a scheme to decrypt data after a specific event has happened. But this "trigger event" is only known to the author.

In contrast, I am interested in a cryptographic scheme that would enable decryption of data at (or after) a specific date which is publicly known.

  • 10
    Possible duplicate: crypto.stackexchange.com/questions/606/… – Mike Ounsworth May 12 '15 at 18:37
  • 5
    On the surface, it seems like the answer to your question is "time lock puzzles" which require someone to perform X amount of work in order to obtain the key. This could work for you if someone's willing to dedicate a server to solving the puzzle, and then release the key publicly, but it's def. not a good client-side solution. – Mike Ounsworth May 12 '15 at 18:42
  • 4
    You have to think about your question a little to see if it even makes sense. Who sets the date and time in the first place? If Congress decides that daylight savings is suddenly ending right now, and your file had just become decryptable 10 seconds ago, do you really expect it to become sealed again? If you cross a country border, is your file somehow supposed to react to that? Isn't it pretty obvious that being able to decrypt the file must necessarily require the cooperation of whoever is decreeing the current date/time? – Mehrdad May 14 '15 at 11:13
  • 3
    @Mehrdad Unix time. As long as we're not moving at relativistic speeds, unix time is unambiguous :) – Navin May 14 '15 at 21:47
  • 4
    Are you allowed to be "in the loop?" It is trivial to do this if you simply publish the decryption key at the date you are willing to allow decryption to occur. You effectively become the trusted party. Otherwise, it is information-theoretically impossible (meaning you are now talking hardware solutions, rather than theoretical cryptographic solutions). – Cort Ammon May 15 '15 at 5:36

16 Answers 16

71

Time is relative. Cryptography lives in the ethereal world of abstract computing machines: there are machines that can do operations. Bigger machines can do operations faster. There is no clock that you can enforce; physical time has no meaning. In other words, if an attacker wants to get your file earlier, he just has to buy a faster computer.

Now one can still make an effort. You may be interested in time-lock puzzles. The idea is to be able to make a problem instance that is easy to build but expensive to open, where the cost is configurable. The solution found by Rivest, Shamir and Wagner (to my knowledge, this is the only practical time-lock puzzle known so far) works like this:

  • Generate a random RSA modulus n = pq where p and q are big primes (and also p = 3 mod 4, and q = 3 mod 4).
  • Generate a random x modulo n.
  • For some integer w, define e = 2w, and compute y = xe mod n.
  • Hash y with some hash function, yielding a string K that you use as key to encrypt the file you want to time-lock.
  • Publish x, n, w and the encrypted file. Discard p, q, y and K.

The tricky point is that computing y, in all generality, has a cost which is proportional to w: it is a succession of w modular squarings. If w is in the billions or more range, then this is going to be expensive. However, when the p and q factors are known, then one can compute e modulo p-1 and q-1, which will be a lot shorter, and the computation of y can be performed within a few milliseconds.

Of course this does not guarantee a release at a specific date; rather, it guarantees a minimum effort to unlock the puzzle. Conversion between effort and date depends on how hard attackers try...

The time-lock puzzle expressed above has some nice characteristics, in particular being impervious to parallelism. If you try to break one such puzzle and you have two computers, you won't get faster than what you could do with a single computer.

In a somewhat similar context, this time-lock puzzle is used in the Makwa password hashing function, candidate to the ongoing PHC. In password hashing, you want a configurable opening effort (albeit within a much shorter time frame, usually less than a second).

  • 2
    However, my understanding is that parallelism-resistance is not relevant to password hashing. – user49075 May 13 '15 at 23:28
  • Well put and well answered. – Paul Draper May 14 '15 at 1:26
  • 4
    @RickyDemer: in fact, parallelism-resistance can be argued to be a bad thing for password hashing, because the attacker has all the parallelism he can wish for (he has many potential passwords to hash) while the defender gets password one at a time. If the defender has a parallel architecture (e.g. a GPU or even a PC with a few cores) then he may prefer a function that supports moderate parallelism. Heavy-duty authentication servers benefit from parallelism by virtue of running multiple password-based authentication simultaneously. – Tom Leek May 14 '15 at 11:56
  • 29
    Time is relative, but the speed of light is absolute. Put the decryption key sufficient distance away from the attackers. No powerful computer can overcome that. – emory May 14 '15 at 15:06
  • 1
    This is a case for genuine "key escrow", and it operates in a similar way to normal escrow... Encrypt a file with a symmetric key, give the key to an escrow firm along with the fee, destroy your copy, they release the key at X date. – Riking May 16 '15 at 21:23
55

If you do not want to involve a third party, you (the party encrypting the file) could simply release the key to decrypt the file on the target date.

I have seen this done for video game releases. Customers are allowed to download an encrypted copy of the game in advance. Then, when the release time comes, the game company simply releases the key. That way, people can start playing immediately when the game is released, without needing to wait for a download.

  • 9
    @AronFoster: Unless the encrypting party builds their own service, what you are describing still involves using a trusted third party. That party just happens to be Twitter. – Lily Finley May 12 '15 at 18:38
  • 14
    @AronFoster: I don't think Twitter qualifies as a "trusted authority" in this context. Either the key provided on their service works, or it doesn't. If for some reason they decide to lie about the key, then the message will "decrypt" to gibberish, and everyone knows what they did. (Well, that or the OP lied about providing a legitimate cyphertext.) If Twitter decides to not provide the key at all, than the author can publish via ANY other service. The channel here doesn't matter, since the requirement is not secrecy, but just distributing a key which works. – loneboat May 12 '15 at 19:18
  • 7
    @loneboat: The real trust at work here is the assurance that Twitter will not reveal (or attempt to use) the key before the specified time. – Lily Finley May 12 '15 at 19:30
  • 6
    But if you're worried that Twitter Inc. will single you out and violate their own rules just to decrypt your secret early, you'll have much bigger problems than the fact that you trusted Twitter to not reveal the key. Just like how Microsoft isn't going to reveal a backdoor in BitLocker just to charge you personally with buying drugs over the internet, if you get to the point where you're expecting a multi-billion dollar company to single you out then your conversations on digital security need to be at a much higher level than we're having here. – Aron Foster May 12 '15 at 19:51
  • 10
    @AronFoster: A trusted third party is still a trusted third party even when they have more to lose by breaking this trust than you do. – Lily Finley May 12 '15 at 20:02
48

Carefully place a spaceship broadcasting the decryption key in orbit around a black hole. The pull of gravity will delay the message until the appropriate time.

Or you could just do like normal people and place the key broadcasting spaceship an appropriate number of light years away from the intended audience.

  • 8
    I like this answer because it doesn't have the "time problems" of other answers. But I think it could be simplified - you need a mirror at some x/2 light years away, and then transmit the key to that mirror. Assuming no-one is able to sniff/disturb it, you'd have the appropriate delay of x years. – domen May 14 '15 at 12:38
  • 1
    @domen I am not an expert in these matters, but couldn't you use quantum theory to ensure that the transmission to the mirror is not intercepted. It would not matter if the transmission is intercepted on the return trip. – emory May 14 '15 at 14:17
  • 1
    @emory as far as I know, quantum theory allows you to detect whether the message is being intercepted, but not to prevent it. – David Z May 16 '15 at 9:54
  • 2
    @DavidZ But quantum theory also allows to turn any attempted eavesdropping to turn the message into gibberish (for bith the intended audience and the eavesdropper) – Hagen von Eitzen May 17 '15 at 10:22
  • 1
    @HagenvonEitzen ah, I suppose you're right - I was thinking of "intercepted" in the sense of "blocked". A malicious third party can prevent the intended recipient from receiving the message at all, but (probabilistically) cannot gain access to its contents without also cracking the associated classical communication channel. – David Z May 17 '15 at 11:04
17

Use secret sharing to split a private encryption key into N parts, parameterized to allow reconstruction of the key with K or more parts, where K <= N. Best done using CRM, as described on the following page:

http://en.wikipedia.org/wiki/Secret_sharing

Then send each part to independent services that agree to publish at a given date in the future.

Up to K-1 of the services can "defect" by publishing early without affecting the scheme.

Up to N-K of the services can fail to publish altogether, also without affecting the scheme.

  • 1
    Presumably you'd use different classes of key storage as well -- independent online; some sort of trusted official/legal representative; family; your will (depending on how that's stored). The problem is that you have 2 almost opposite failure modes, and if you get to say K-2 having released the key, is there anything you can do about it -- I suggest not. – Chris H May 14 '15 at 12:47
  • 1
    @ChrisH If it's a matter of preventing early publishing, you can also supply each service with a secure checksum of each -other- key part, and each service would support deletion of the key stored on it given at least K' early leaked keys. Then have a trusted friend periodically search for such early leaked keys, and if enough are found, invoke the deletion protocol on all remaining servers. The data would be lost forever, of course. – Atsby May 14 '15 at 21:24
  • that's the sort of thing I was thinking of. Of course you'd only need to wipe out N-K+1 keys if I understand the system properly. On the other hand if your trusted friend betrayed your trust they could prevent release using the deletion protocol. So you end up needing more watchers each of whom could only delete some keys, which I'm sure introduces its own weaknesses. – Chris H May 15 '15 at 9:02
  • 1
    @ChrisH The trusted friend cannot invoke the deletion protocol unless the keys have actually been leaked. So it is an enhancement that prevents release if some keys are leaked, but does not allow the friend to do anything if the keys aren't leaked. – Atsby May 15 '15 at 22:49
  • Don't use a deletion protocol, use a larger number for K and N. Solves the same problem. – Ben May 16 '15 at 7:37
6

I believe that in order to properly design your system, you need to define what "time" means in your context, and why you chose a specific time. Assuming that your message is to be decrypted on the 29th of August 1997 at 02:14 AM, what is difference between the moment before and the moment after the deadline? Why specifically this date? You may be able to utilize this event as a component in your scheme.

For instance, if you expect that Skynet will become self-aware at the date in question and you want the message to be decryped only after Skynet becomes self-aware, then the decryption key could be 'skynet_became_self_aware'. It is unlikely to be brute forced, especially as it contains a non-dictionary word. However, it becomes very likely that it will be tried after the event occurs, especially if there are automated systems trying to brute force it which will add the word 'skynet' to their dictionaries at the proper time.

This scheme is not perfect, as the chance of brute forcing the key still exists and even after the date there might not be suitable resources in use trying to crack it. However, this scheme has the additional benefit that if the event whose date you choose happens earlier or later than expected, then the message will not be decrypted too late / too early.

  • 4
    Your use of the future tense to describe a date in 1997 makes me wonder if you have a time machine, which would render time-locked encryption moot. – David Richerby May 13 '15 at 16:29
  • 4
    @DavidRicherby: It's not so much a time machine per se, but one of the effects of my relativistic wormhole is that I encounter the effect before the cause. Oh, and to answer your next question: Titan, a moon of Saturn. – dotancohen May 13 '15 at 16:42
  • 8
    So, what are you having for dinner tonight? – David Richerby May 13 '15 at 16:47
  • 2
    That's some appetite! :-) – Rory Alsop May 13 '15 at 20:27
  • 1
    @DavidRicherby even with a powerful time machine, certain points in the time-space continuum can still be time-locked. No timetravel in, no timetravel out. It's a wibbly wobbly timey wimey thing.... – AviD May 14 '15 at 12:45
6

If the only trusted party is yourself, and you can't guarantee being available when the message contents are to be made public, then what you can do instead is to build a device (physical or virtual) that will automatically make the key public at the required time, and then hide the device.

An easy way would be to buy a virtual server from Amazon or any of hundreds of other companies - perhaps several servers in foreign countries - under a different identity, not traceable to the identity of the person who published the message. Ideally, you would buy this server several years before releasing the message. These servers simply sit and wait, doing nothing (perhaps hosting an innocent-looking email or FTP server), until the specified date, and then publish the decryption key through multiple public channels so as to satisfy your definition of making the information "public."

Nobody would even know that these servers exist, so nobody is looking for them; and their purpose can be sufficiently obfuscated that nobody who stumbles across them by accident realizes what they're for. There are many millions of internet-connected servers - yours are simply lost amongst the noise.

This would be sufficient unless the message is considered by the public to be important enough that there would be a world-wide effort to locate the key, on a scale that would inspire governments to perform sophisticated traffic analysis every virtual and physical server that went online in the past decade, and then manually examine all files and code on each of the (millions of) suspicious ones, looking for hidden information.

In that case, you could hide the device even further. If you really want to do this James Bond style, put the message on a tape connected to a shortwave radio transmitter with a reserve battery in Antarctica (where it might get buried in snow), or a remote Brazil jungle (where it might get damaged by animals), or at the bottom of the ocean, with a chemically-inflated air bag to float it to the surface at the specified date and time (where it might corrode - maybe Lake Superior is safer?), or buried shallowly underground, with a periscope-like antenna.

Of course, the difficulty and cost of any of these options depends on how long you want to keep the device hidden. If it's a century, it's likely that Internet protocols will have changed, and anything more complex than analog short-wave radio might be infeasible. (And it may be that nobody is listening to shortwave anymore, either.) If it's only a few months, your device could simply be a prepaid smartphone connected to an external battery pack and dropped someplace moderately obscure. There are already lots of cell-based remote sensors on the market, that automatically make a phone call or a web connection when some criteria are met, so this would be almost undetectable - it would look to the cell phone company like just another one of these increasingly ubiquitous devices.

  • 3
    Device wakes up after a century - duplicate IPv6 address detected, interface disabled ... – Hagen von Eitzen May 17 '15 at 10:28
4

I'm not fully sure if this paper about time-lock encryption has been inspired by this discussion but it would be the most formal solution to the question "How to build time-lock encryption?", which is a reformulation of "How to protect data so that it can only be decrypted after a specific date?"

But now let's get into the details on how this works.

One basically constructs a reference clock using computation publically available (like Bitcoin computations). So, as far as I understand this this depends on the Bitcoin blockchain to reach a certain size (it grows every 10 minutes, relative precisely). As this happens "witness encryption" will enable everyone to decrypt the data (where the blockchain contains some witness, which only gets available as the chain gets a certain size). As it's impossible to break the witness encryption schemes and to be faster than the whole bitcoin network (performing more than 300PHashes/s as of now) it's unlikely for an attacker to be able to get the decrypted data (which may be a key) before the time-lock expires.

One may also note that this scheme doesn't suffer from high costs (space travel), it doesn't need trusted third parties (you don't need to trust the Bitcoin network) and the encrypting party doesn't need to be available at time of decryption and parties with high computational ressources have little chances of knowing the secret earlier.

One may also want to read this paper, following a similar approach and reducing security to the subset-problem, which is believed to be hard.

2

Encrypt the file with a very long key, split it up into parts, and give each part to a trusted person along with instructions not to surrender said part until the given date. You may add some redundancy by giving each part out to more people, in case one of them were to be hit by a bus.

Of course, a network of computers could do this just as humans can. In fact, Bitcoin's time based difficulty retargeting algorithm, though it serves a different purpose, relies on similar principles. I don't know that any program actually exists for this purpose, however.

2

A hypothetical approach is given in the paper cited in the question (which is very interesting BTW, despite the occasional clumsy grammar) which is to use a software containing an encrypted payload, triggering off of some outside value like a news story, and have people around the world run it until such time as the payload is executed. This fails to meet the "publicly known date/time" requirement but the premise is a good starting point. A distributed service, much like TOR/Bitcoin, could be run in a P2P fashion by many individuals around the world for the sole purpose of maintaining time-dependent key releases. This is known as Byzantine Fault Tolerance (aka the Byzantine Generals Problem, see http://en.wikipedia.org/wiki/Byzantine_fault_tolerance for a complete explanation) but in this case the "fault" to be guarded against would be the premature release of the information so it is not a direct application, but a tangential one that would require a new set of techniques.

Careful coding could be used to create a scheme where each user holds one tiny piece of the key, many users have redundant copies of individual pieces, and there is a strong means of preventing premature "harvesting" including malware evasion and multi-platform support (wherein keys are intentionally split evenly between users running the software on Windows, IOS, Android, OS X, Linux, etc.)

It would almost need to work like an inverse of the bitcoin blockchain, where instead of every user having a verifiable copy of what took place in the past, each user has a unique slice of what will be happening in the future, and only as the future turns to the present are each block released to the world for consumption. A technique of onion-ing a la TOR could be used in this case, whereby each piece of your secret key was sent to a set of users, they transfigured it and sent it on retaining only a translation key, and that kept going for N rounds upstream. Each layer could have its own randomized timer to later pass the material downstream, getting closer to the origin where the last timer would count down and trigger the release of the key parts to come together on a set of agreed upon peers and be emailed, or something.

The only missing piece would be how to avoid mass collusion, such as a bounty set up to entice enough users to give up their key material in return for a split of the pot, since it can not be assumed that many of them regard their escrowed information to have a > 0 value if left untouched. A way to fully obfuscate the material would be desirable, so that each user had one big blob of data without knowing which event slices were in their care. This is an interesting problem, indeed.

0

Ultimately, the second law of thermodynamics gets in your way. Look at your plaintext as a closed system; it can only ever increase in entropy.

Encrypting information increases its entropy, but having the key compensates for it. The total entropy of key+ciphertext is the same as the entropy of the plain text.

When you destroy the key, the overall entropy of the system increases. Which means, you can never go back (except with massive input of energy through brute-force computing power).

This means that you must keep the key; you cannot temporarily destroy it.

Of course you can hide the key, encrypt it again, keep it with a trusted third party, etc. But the key must always be somewhere.

0

Encrypt with a one-time XOR pad and have some kind of automation to send the cipher stream at the appointed hour. One time XOR pads are completely resistant to pattern attacks because there's no pattern.

For this to succeed you must

  • produce the key yourself and not share it with anyone
  • build tamper-proof timed delivery automation
  • conceal the true purpose of the timed delivery system by ensuring that it does a good job of performing an immensely boring but essential infrastructure purpose, so that no-one tries to investigate, unplug, modify or re-purpose it
  • destroy all copies of the XOR pad outside the tamper resistant timed delivery system

Note that to be truly tamper proof it has to respond to tampering by very thoroughly scrambling the XOR pad. Happily since XOR pads contain random data there is no way to tell whether it has self-destructed or not.

You could further conceal the XOR pad steganographically to stop the inquisitive from wondering why anyone would hide a lot of apparently random data.

I realise that there are elements of security by obscurity in this approach. That's unavoidable; if I knew of such a system and wanted to attack it I would start by depriving it of power and desoldering everything that looked like storage so I could examine the contents without allowing it to respond to tampering. Even then you could embed a UPS.

Informed attack depends on a priori knowledge of the system, starting with its existence. If only the sender even knows of its existence this can be robust. A common strategy is to avoid having any one party construct a fragment large enough to have coherent purpose.

0

It could be possible to build a blockchain based system that gives every block in the future additional payload that the miner of that block has to solve.

Every block could create a private key for a public key that's known in advance. You encrypt your message with a symmetric key and then encrypt that key with the known public keys of the next 10000 blocks that will be mined.

If the network gathers more computational power it can add additional numerical problems to blocks being mined to keep up the block generation time of on average 10 minutes.

If the network loses processing power it will however take longer time the file can be successfully encrypted.

  • So you suggest creating a new altcoin (in an already crowded market) just to timeshift a file release? Even if it catches on, if your file is valuable it will be decrypted earlier than you intended. Those mining the coin would start at the first block and work forwards, while anyone wanting the file would start at the last block and work backwards, only doing the work to crack the keys, not waiting 10 minutes between each one, and not necessarily publishing their results. When the two groups "met" the cracker(s) would have your file. – Hugh Allen May 18 '15 at 17:14
  • 1
    New altcoins need new features to differentiate themselves from existing coins. This feature alone might not justify a new coin but together with other features it might. Such a feature could be especially valuable if the blockchain get's used as a public store of information. I could imagine to preregister scientific trials on a blockchain. In that case scientists might want to have a time lag till the information get's public but at the same time the information is not valuable enough for an attacker. – Christian May 18 '15 at 23:16
0

Using not completely trusted sources, you could send the decryption key by snail mail to the trusted party. This does not trust the party completely since they cannot post early, but they could not post at all, so to minimize the risk, multiple trusted sources can be used.

To increase the time delay, you could use a online service to ask them to send the postcard from outside the country (but that would make it vulnerable to man in the middle attacks), for example http://mijnkaart.bpost.be/fotokaarten-maken for the dutch speakers, but I'm sure that similar services exist elsewhere.

0

This works to trigger at the time of an event that you cause.

Make an automation (see the answer of Peter Wone) that checks whether you have a wikipedia page in your name. and triggers if it does.

This is obviously very trigger sensitive & only works if you are unknown at the time of construction.

You could solve both problems by including the condition that certain information about the event is contained in the Wikipedia entry.

I am sure that using Google there are a couple of other interesting triggers to be found

0

Like others said, one cannot provide decryption by a specific date, but by a specific effort. As for a single purpose algorithm the effort is strongly related to the interest of the parties trying to unlock it earlier and thus quite unknown.

So the best solution may involve linking the puzzle to a much larger and inert interest. The most feasible that came to my mind these days is the Bitcoin block chain. As bitcoins are reality for some years, and their generation involves large amounts of hardware today, we have good chances to predict their generation rate on a reasonable long term (maybe weeks to months).

I wonder if this could be done. What would be needed is a linking between generated bitcoins and the needed key. We cannot rely on a single bitcoin to be generated, but have to use something like a small n of a formerly chosen large amount of m possible bitcoins will provide decryption. This is possible with 'secret sharing' (https://en.wikipedia.org/wiki/Secret_sharing). As bitcoin hashes depend on the transactions made before, it would be quite tricky to construct m puzzles that would solve by the bitcoins hash one day.

-1

The only way you can do this is to ensure that a) you control the code that performs the decryption, and b) that you are getting the date from an immutable source. For example, if you include as part of your decryption a call to an atomic clock web service (ideally a secure one that couldn't be spoofed). At that point, you just check the date and if it's less than your desired date, you don't bother decrypting.

  • 2
    The other answers here show that this is not the only way. If you keep the key until the date, as one of them suggests, you don't need to control the decryption code. – S.L. Barth May 13 '15 at 21:45
  • Spoofing a clock or other outside signal is either going to be easier than directly cracking the encryption, or it's simply going to shift the problem -- how do you prevent the "secure" clock from being broken into before a specific date? – Matthew Read May 14 '15 at 4:10
  • Unspoofable is going to be impossible, but you can come somewhat close by using multiple reliable time sources. Use several reliable NTP servers in different countries (they can be spoofed by IP address redirection) along with a GPS-based clock (which could be spoofed by somebody with the budget to build a GPS simulator infrastructure). – Kevin Keane May 17 '15 at 23:45

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.