Ensure that a file can only be decrypted after a specific date

Question

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.

Answer 1

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 = 2^w, and compute y = x^e 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).

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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.

Answer 11

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.

Answer 12

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.

Answer 13

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

Answer 14

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.

Answer 15

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.

Answer 16

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.