Document robustness of Keybase timestamps under various threat models

[nealmcb]

Context: There are a variety of models, standards and services for secure / verifiable / trusted timestamp protocols such as

• RFC 3161 - Internet X.509 Public Key Infrastructure Time-Stamp Protocol (TSP)
• PGP Digital Timestamping Service
• OriginStamp
• Various blockchains
• Etc....

But Keybase also provides visible timestamps on chats, and timestamps other content in a variety of ways.

So how does Keybase stack up as a trusted timestamp service? I've searched the documentation that seemed relevant and see no discussion of this.

• What guarantees are there on the validity of timestamps? Are they generated based on clocks on on local devices, or checked for being in sequence with nearby chat messages, or ??
• Are there ways for users to subvert the timestamps of their own content, and pre- or post-date it? (E.g. deleting a public object such that Keybase or archived data can't be used to document its data and existence in the future, or modifying a timestamp?)
• At what granularity might someone be able to prove a given timestamp?
• How can timestamps on kbfs files, proofs, signatures and other content be conveniently uncovered by users, and related guarantees on validity, granularity etc be communicated?
• What denial of service attacks are there? Can I publish something in a way that a timestamp on it is guaranteed to be verifiable, even if the Keybase server goes away some day or tries to violate any of these guarantees?

Issue: Can you answer these sorts of questions in the Keybase documentation, or point to existing answers?

Reference use case: I've been looking for public, easy-to-verify timestamps for a long time, and posted this example use case focused on publication and auditing of election results in 2010:

• What good, standard digital signature / timestamp verification clients are widely or easily deployed? - Information Security Stack Exchange

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

This issue now has a funding of 20.0 DAI (20.0 USD @ $1.0/DAI) attached to it.

• If you would like to work on this issue you can 'start work' on the Gitcoin Issue Details page.
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $68,047.14 more funded OSS Work available on the Gitcoin Issue Explorer

[JosephDunivan]

Hi @nealmcb. These are some very interesting questions, but I noticed the link to Stack Exchange is a question posted from 9 years ago. Is this issue resolved? What exactly is the association with the bounty on GitCoin and the question from 9 years ago?

[maxtaco]

Hi, we have thought a bunch about this, but our documentation doesn't reflect that yet. I hope to work on this soon.

[nealmcb]

@JosephDunivan The question is still highly relevant. I'm really disappointed that even 9 years later, we don't have a good, easy, widely understood story on how to prove timestamps on documents. The accepted solution at Stack Exchange only relates to signing the content, not a timestamp. The GitCoin bounty was just my way of drawing attention to the topic and a way of seeing how GitCoin works.

Keybase looks great in various ways for validating who vouches for the content, and potentially good if not great for timestamps. So I'm looking forward to the documentation that maxtaco is working on.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work has been started.

These users each claimed they can complete the work by 1 month, 2 weeks from now.
Please review their action plans below:

1) adrianhacker-pdx has started work.

I have scoured the scholarly internet and found a couple research papers about timestamping that I believe will demonstrate a method for secure timestamping via the Bitcoin blockchain.

Learn more on the Gitcoin Issue Details page.

[gitcoinbot]

Issue Status: 1. Open 2. Started 3. Submitted 4. Done

---

Work for 20.0 DAI (20.0 USD @ $1.0/DAI) has been submitted by:

1. @adrianhacker-pdx

@nealmcb please take a look at the submitted work:

• PR by @adrianhacker-pdx

---

• Learn more on the Gitcoin Issue Details page
• Want to chip in? Add your own contribution here.
• Questions? Checkout Gitcoin Help or the Gitcoin Slack
• $90,544.98 more funded OSS Work available on the Gitcoin Issue Explorer

[nealmcb]

@adrianhacker-pdx thank you, but the gitcoin bounty is for work specific to Keybase. I already referenced Bitcoin-based approaches in the StackExchange question (e.g. OriginStamp, listed above), but they are either slow or costly.

[adrianhacker-pdx]

@nealmcb please look at the updated pull request which includes summary of keybase past security issues, keybase server security overview, and a link to the external auditor report of keybase

[adrianhacker-pdx]

@nealmcb I have noticed that in Keybase's documentation there are a lot of implied "at your own risk" statements. Also, they admittedly state that anything associated with Keybase is not protected from root or user associated processes. It's all included in the pull request. Finally, I included the part where resource-constrained systems were mentioned as not being the best for using Keybase as it is a resource hog. I don't think you're going to find anything with Keybase that is innovative or advantageous over proven technologies.

[nealmcb]

The PR notes this quote from https://keybase.io/docs/kbfs

At the time of this document, there are very few people using this system.

That isn't germane to this issue, but it is very out-of-date (from about 2016), and that's hard to see because it is also not timestamped ;) . Time to fix it....

[nealmcb]

@adrianhacker-pdx, again, the question for this issue and this bounty is how to leverage Keybase data for timestamps. The question is not whether Keybase is worthy or innovative, though I assure you that lots of folks with lots of credibility have demonstrated that it is.

Posting hashes of the Keybase merkle tree regularly to Bitcoin, as documented at Merkle Root In Bitcoin Blockchain, is one of many ways that timestamps could be verified with crude granularity (within about 6 hours it seems).

Update: I see that the focus is now on publishing lots more frequently to the Stellar blockchain, which should give much more granularity: Server Security - Merkle Root In Stellar Blockchain | Keybase Docs. Thanks!

Update 2: It looks like the documentation there is wrong about....the timestamp.

Since 20 Jan 2020, Keybase has been regularly pushing its Merkle Root into the Stellar blockchain

The Stellar tree shows creation of account GA72FQOMHYUCNEMZN7GY6OBWQTQEXYL43WPYCY2FE3T452USNQ7KSV6E on 2020-01-24T21:28:58 UTC, not Jan 20.

Given that, part of the answer to my question is how users can verify the timestamps, perhaps given a bit of new user-friendly code. But there may well be much better ways to leverage the data. Digging deep into Keybase code and proofs is needed to document the tradeoffs, given specific threat models. I'm glad to see that the Keybase folks, at least, are planning to do that.

Of course, if you find any issues with Keybase that actually relate to timestamps (rather than content, identity, etc), they would be relevant for this issue.

[nealmcb]

It's nice that Keybase is now providing evidence via Stellar, hourly it seems. So if someone can establish the reliability of Stellar timestamps, we should get at least an upper limit of around an hour for possible skew of public Keybase actions (though we would need more work to make it easier for folks to verify timestamps of individual actions.)

Beware that the design and implementation of Bitcoin in particular makes its timestamps vulnerable to some degree of manipulation, allowing timestamps up to two hours in the future, and sometimes resulting in blocks with out-of-order timestamps, as documented by culubas in Timejacking & Bitcoin.

For example, there are blocks with timestamps earlier than the previous block, like
617888 (2020-02-17 21:55:48), whose timestamp is before that of its parent
617887 (2020-02-17 21:55:56).