39

Sometimes we need to prove that a file was not created in advance - a good example is warrant canaries. The person releasing them may have been forced to sign the file with a future timestamp. For example, AutoCanary uses recent news headlines which is a very secure method, assuming the adversary can't predict future (or obviously manipulate the source of these headlines).

Question: What are other secure ways to prove that a file was not created in advance?

Samuel Shifterovich
  • 876
  • 9
  • 18
  • 3
    How about use https://en.wikipedia.org/wiki/Trusted_timestamping – rkosegi Dec 17 '16 at 13:48
  • 4
    I misunderstood what you said, and I think your title is misleading. The solution you've accepted doesn't imply the file wasn't created in advance at all. It simply implies the file has been made accessible after some time T. Now, of course you can include something extra in the file from the "future", but at that point you're cheating -- the real contents were already there; you just added something extra. There's no way to prove the other contents weren't there. – user541686 Dec 18 '16 at 00:40
  • 1
    I don't really understand your warrant canary example. The whole premise of warrant canaries is that you can't be compelled to write/sign them; but if you can, then there's no difference between being compelled to write/sign them *with* a future date vs. being compelled to write/sign them *at* that future date . . . is there? What am I missing? – ruakh Dec 18 '16 at 06:26
  • @ruakh Exactly, and by using for example news headlines, you cannot be forced to write&sign the canaries in advance. – Samuel Shifterovich Dec 18 '16 at 10:36
  • 1
    @Mehrdad This should be used in conjunction with signing. – Samuel Shifterovich Dec 18 '16 at 10:38
  • 2
    If an adversary can (a) force someone to sign the file with a future timestamp and (b) force that someone to release that file in the future, then all the suggested ways are vulnerable to the same adversary forcibly obtaining the signing keys, signing the 'canary' themselves whenever needed according to the suggested ritual (e.g. recent headlines) and releasing the signed file. On the other hand, if you are able to revoke compromised keys, then the same revocation will also make the pre-signed files useless, since they carry the future timestamp but are signed with an old key. – Peteris Dec 18 '16 at 14:17
  • @rkosegi: trusted timestamping only works if you can trust the timestamping authority. Something like a blockchain timestamping would've worked even in the absence of a trustworthy authority. – Lie Ryan Dec 18 '16 at 14:18
  • cf. [Proof of Existence](https://poex.io/) – Geremia Apr 20 '18 at 20:33

2 Answers2

39

If all parties can trust a common randomness beacon (like the NIST Randomness Beacon), this can be achieved by including a recent block from the beacon into the file along with its timestamp. The recipients then, in addition to verifying the signature, must also verify that the beacon data is authentic and as recent as they require.

Other public random values might also do the trick, for example, the winning numbers of a well-publicized lottery. But care needs to be exercised however that the items chosen have sufficient entropy. For example, if you just pick the closing value of the Dow Jones Industrial Average, that's been a 6- or 7-digit value for decades, so an attacker could just force you to precompute signatures for all likely future values of the index. The closing values of a list of stocks that all participants agree on beforehand might do the trick, though I'd want to do some calculations first to convince myself that the list has sufficient entropy.

Luis Casillas
  • 10,181
  • 2
  • 27
  • 42
  • 7
    This requires you to trust a **centralized** source. Bitcoin blockchain could be a very good solution, couldn't it? – Samuel Shifterovich Dec 16 '16 at 23:15
  • 9
    @SamuelShifterovich: Probably, modulo certain assumptions. In particular: 1) the blockchain will continue to grow indefinitely (rather than stopping once mining is no longer profitable), 2) no single entity will ever control >50% of the computing power in the Bitcoin network (because otherwise they can manipulate the blockchain in possibly undesirable ways), 3) there isn't some fundamental cryptographic weakness in the Bitcoin protocol. – Kevin Dec 17 '16 at 07:11
  • @SamuelShifterovich having e.g. a newspaper headline instead might presume that other centralized instances don't cooperate. Depending on your level of paranoia, I'd rather trust NIST or not. – Marcus Müller Dec 17 '16 at 15:32
  • 4
    For instance, Autocanary links as an example to https://riseup.net/en/canary, which, at the moment when I am writing, uses the link to the news headline `https://theintercept.com/2016/08/15/fact-check-911-happened/` as proof that it was created after 2016/08/15. It doesn't look very secure to me; "fact check 9/11 happened" is a very generic title that could have appeared basically at any moment after 2001. – Federico Poloni Dec 17 '16 at 19:57
  • 1
    @FedericoPoloni Indeed. Some kind of breaking news *that is more of an event, not a headline* is very efficient compared to something that is more of a website-specific article, like that The Intercept one. – Samuel Shifterovich Dec 17 '16 at 22:46
  • 1
    @Kevin Though some manipulation of the Bitcoin blockchain could happen, it does not mean much if you just want to prove freshness. Regardless of how large a fraction of the processing power an adversary controls, any hashes precomputed by the adversary cannot cover later transactions. So anybody who is creating transactions would know whether their transactions are included in the chain in a timely fashion, which would prove freshness of the hash at the head of the chain. – kasperd Dec 18 '16 at 12:09
1

I don't see how the headline matches the post, so please allow me to go with the post and in accordance with the comments:

One simple way to register the existence of a document or file is to use the blockchain.

http://www.cryptograffiti.info/ - allows you to post anything, like a hash of the file along with a news headline, and it will be there forever, date and time stamped. You can leave a simple love note or whatever you like, and it is permanent.

Here is an interesting article on how the Canadians used the blockchain to do a proof of existence of a new law, on the blockchain.

https://www.reddit.com/r/Bitcoin/comments/3aei7c/heres_what_the_canadian_senate_just_put_in_the/

SDsolar
  • 977
  • 1
  • 6
  • 25