Available Digests

[xloem]

Hi,

I'm working xloem/openrealrecord, which uses blake2 digests from the sodium library for its trees and checkpoints. Your trees appear to use weaker hashes such as sha256, so if openrealrecord integrates these timestamps, the timestamps could become the weakest link in the digest trees and in some cases the gains of using a more modern algorithm will be lost.

I was wondering what the plans were for including modern hashing algorithms such as blake2 or sha-3 in the opentimestamps system?

[petertodd]

1. What makes you think blake2/sha3 are any stronger than SHA256? Even NIST doesn't claim that SHA3 is more secure than SHA256

2. The only secure attestations that OpenTimestamps supports are currently Bitcoin and arguably Litecoin, both of which are based on SHA256. Thus even if SHA256 was insecure, using another hash function elsewhere in the proof wouldn't help.

3. Timestamping places such low demands on hash functions that even SHA1 is secure when used for timestamping.

4. OpenTimestamps does support SHA3, in the form of the pre-NIST-standardization OpKECCAK256, however for full end-to-end SHA3 you'd need to timestamp with Ethereum. While that is supported, Ethereum isn't secure, nor is it stable, so I wouldn't recommend it without simultaneously timestamping via Bitcoin.

[petertodd]

Sorry, re-opening - hit the wrong button! And besides, this isn't my repo, so it's not my place to close this issue. :)

[xloem]

@petertodd,

1. See for example https://github.com/zcash/zcash/issues/706#issuecomment-187807410 which makes many points.

2. (EDIT: Bitcoin uses a double-sha256, but of course that may make collision attacks a little easier, not harder, as finding a collision in either hash could have the same effect). Blocks are globally broadcast and stored, making forging one a difficult task. There is a much smaller space for collisions because of the constraints on the content of accepted blocks.

3. I want to use timestamps to assert content as well as time. Is this a good use for opentimestamps?

4. I saw keccak mentioned in the source which I really appreciated, but the cli tool is coded to reject it as unsupported.

[petertodd]

1. Few if any of those points are relevant here.
2. Nope, the double-SHA256 doesn't help OTS, as the proof format has no concept of double-SHA256. It's also unclear that double-SHA256 has any relevance to attacks against timestamping.
3. No. Sounds like you want double-spend protection, not timestamping.
4. The CLI tool is the least of your problems in making use of keccak. We have an experimental ETH calendar, but it's very unreliable as ETH itself is unreliable.

[xloem]

1. I feel they are. For example, NIST has banned the use of SHA256 in all new designs. We should at least allow users to follow suit.

2. I think I possibly misconstrued the use of the double-sha256 ... but I feel that forging a block in the bitcoin blockchain is much harder than forging other things. Blocks are broadcast globally and have to fit all the bitcoin economy rules.

3. I think I may have failed to convey to you what I mean by asserting content. I want to produce a cryptographic hash of a file that can be used to verify the file is unchanged, and post that hash to a blockchain, to verify that specific file had that specific content (i.e. was definitely not any file with differing content) before the publication time of a block. This is what trusted timestamping means to me. I don't see how double spend protection could help with this?

4. I feel strong hashes are valuable in bitcoin itself. I trust the bitcoin blockchain (I do not trust the ethereum blockchain, they have few miners and haven't solved proof of stake), and I want to put hashes I trust into the bitcoin blockchain I trust. Like putting a hard-to-pick lock on your door even though your windows are breakable.

[petertodd]

1. Source?
2. Sure it is, but that doesn't help us in the particular type of SHA256 break you're talking about. Also remember that any scenario where this stuff matters will be far into the future, at a point where SHA256 has been broken.
3. Yes, that's not timestamping. The only thing timestamping does is prove data existed in the past; timestamping does not prove there "was definitely not any file with differing content".

[xloem]

Hey, the source for 1 was the link I posted above. I haven't independently verified it. I feel almost all of the other points it made are relevant here, too, I just picked one.

I hear you agreeing that forging blockchain blocks is really hard, even without regard to the strength of SHA256. This forging is required to make use of a collision with the SHA256 double-hash that verifies the content of the block. Hence it does help in this particular type of SHA256 break, which would be a hash collision that allows the timestamp tree to be changed but the block to still validate; the collision in question would be a forged bitcoin block.

Remember that even if an attacker can produce an SHA256 collision and offer a changed timestamp hash, this means a changed timestamp transaction id. This transaction id is used, forever in the future, in every transaction that makes use of the change left over from the timestamp transaction. That could potentially be a lot of SHA256 collisions; it could potentially mean convincing the victim of an entire fake blockchain and isolating them from the real blockchain. (or it could be just two collisions if you immediately move all the change to a different address after every timestamp ... which would be much less secure here)

You quoted me in 3, but to me the way you quoted me does not reflect what I was trying to say. Here's a way of rephrasing it: you can only prove data existed in the past if your hash has no collisions, because otherwise it could have been some other, colliding, data, that existed in the past.

For example, you could timestamp a photo of yourself in bed at 3 AM tomorrow morning to try to prove you were asleep then. Two years later, somebody mean could come along, and take a photo of you in an empty bank. If the hash you used was completely broken, they could find a way to adjust the lowest bits of the pixels in the image until it hashed to the same value as your original image did. If you lose your copy of the photo, they now have proof that you were in that empty bank at the time you took your 3 AM photo, and can make a case that you participated in a bank robbery.

The opentimestamps.org website says "A timestamp proves that some data existed prior to some point in time." But because of hash collisions, the mean person with the bank photo of you has proven his photo existed at a time that it did not exist.

It's valuable to use hashes that are more resistant to collision. I believe that verifying content as well as time is an integral part of trusted timestamping.

A trusted timestamp of a hash only has value for as long that hash is not broken. It's important to use hashes that are expected to last for a long time without breaking, such that the timestamps do as well.

[xloem]

(So, I took the time to look at https://petertodd.org/2017/sha1-and-opentimestamps-proofs more closely, and I kind of see where you're coming from. As long as hashes don't have preimage attacks, they do actually prove what they purport to, unless the original publication was crafted to collide. When I consider a hash breaking here, I consider the attacker having access to a preimage attack, although it's notable that if the attacker were the block miner or the calendar server they would only need a collision attack. To use the right words, I feel that newer hashes should be an option, because they are likely to last longer without a preimage attack being found.)

[petertodd]

The source isn't in that link, and anyway, that link doesn't go to a NIST website, it goes to the IAD website, which is a part of the NSA. From the URL it looks like that was part of their inexplicable quantum computing related advice, which given past history of the NSA, could easily be subterfuge.

Re: collisions, your example is simply not what OpenTimestamps attempts to prove, nor is the proof format able to support stronger guarantees. If you want stronger guarantees, you'll need to implement them yourself, and you'll need a very different proof format than what OTS uses.

Anyway, 256-bit hash functions such as SHA256 aren't vulnerable to quantum computers, which only reduce them to 128-bit hash functions. That's still perfectly secure for OpenTimestamps. You'd need a major cryptographic break - one so major as to be almost unprecedented in the entire history of cryptographic hash functions - for SHA256 to be insufficient for timestamping.

[xloem]

The source isn't in that link, and anyway, that link doesn't go to a NIST website, it goes to the IAD website, which is a part of the NSA. From the URL it looks like that was part of their inexplicable quantum computing related advice, which given past history of the NSA, could easily be subterfuge.

Hmm what link are you referring to? I meant https://github.com/zcash/zcash/issues/706#issuecomment-187807410 which I linked to in my comment https://github.com/opentimestamps/javascript-opentimestamps/issues/22#issuecomment-390436438 .

your example is simply not what OpenTimestamps attempts to prove, nor is the proof format able to support stronger guarantees

To repeat myself, the opentimestamps.org website says "A timestamp proves that some data existed prior to some point in time." I feel this is what I am trying to prove. Do you disagree?

You'd need a major cryptographic break - one so major as to be almost unprecedented in the entire history of cryptographic hash functions - for SHA256 to be insufficient for timestamping.

You seem to feel that almost any hash would be sufficient for timestamping, including ones that are vulnerable to collision attacks. But couldn't a calendar server take advantage of a collision attack to compromise a timestamp?

Say I submitted some PR's to add support for blake and sha-3; would there be any issue merging them in?

[petertodd]

I'm referring to the link in https://github.com/zcash/zcash/issues/706#issuecomment-187807410, specifically https://www.iad.gov/iad/customcf/openAttachment.cfm?FilePath=/iad/library/ia-guidance/ia-solutions-for-classified/algorithm-guidance/assets/public/upload/CNSA-Suite-and-Quantum-Computing-FAQ.pdf&WpKes=aF6woL7fQp3dJieGY3pmDtEBdP8vHA2987qb9n, which is both broken, and from the NSA, not NIST.

To repeat myself, the opentimestamps.org website says "A timestamp proves that some data existed prior to some point in time." I feel this is what I am trying to prove. Do you disagree?

Yes, you're line of argument above seems confused. Quite simply, while a handful of collision attacks are known, preimage attacks are nearly unheard of for modern hash functions. Meanwhile, all collision attacks require both bits of data to exist prior to computing the colliding hash digest, which means the timestamp proof is still valid.

For the purpose of timestamping it's quite likely that SHA256 will never be broken.

You seem to feel that almost any hash would be sufficient for timestamping, including ones that are vulnerable to collision attacks. But couldn't a calendar server take advantage of a collision attack to compromise a timestamp?

No. As I explained in https://petertodd.org/2017/sha1-and-opentimestamps-proofs, the existence of a collision does not invalidate a timestamp proof.

Say I submitted some PR's to add support for blake and sha-3; would there be any issue merging them in?

As I mentioned above, we already support the only relevant version of SHA3, the pre-NIST-standardization OpKECCAK256. That particular variant is slightly stronger than what NIST standardized anyway, and it's the only one that actually sees usage.

More hash functions are not welcome: every additional feature we add is yet more code that the entire ecosystem has to support. Quite frankly, I only accepted the OpKECCAK256 pull-req because it came from an important member of the OTS team who needed it for marketing reasons; I don't think OTS clients should use it, nor should OTS implementors feel like they absolutely have to implement it.

[xloem]

I'm referring to the link in zcash/zcash#706 (comment)

I see; sorry. I had not visited the secondary link. Personally, I feel SHA-256 is weaker than newer hashes, simply because public efforts have come closer to demonstrating a collision attack. In general, I expect private parties to have reached farther than public research has, so it's a concern to me.

you're line of argument above seems confused. As I explained in https://petertodd.org/2017/sha1-and-opentimestamps-proofs, the existence of a collision does not invalidate a timestamp proof.

I don't trust that preimage attacks will not be found. But still, your timestamped documents are aggregated by servers into trees of hashes before being posted to a blockchain. If one of those servers becomes compromised and is able to create a hash collision, it could intentionally submit a tree that it could later replace with a different tree. Isn't this correct?

In the extreme, one's own system could be compromised, and malware could submit a prepared collision for one's own document. This is a stretch, but it is physically possible, and could even be effective ransomware.

More hash functions are not welcome: every additional feature we add is yet more code that the entire ecosystem has to support.

I guess I'd like to apologize for spending a couple days basically arguing with you. I'm trying to put my mind at ease regarding the security of my own project, when I myself am not a security expert. So I have stress here -- it's important to me -- and it's hard for me to negotiate that. I approach opentimestamps.org with wariness because it does not appear to place security first to me (complexity, apparent lack of support for complete decentralization, encouraging inexperienced people to consider insecure constructs in environments they don't understand, assuming what has been published is similar to all that can be done). I've gotten in a disagreement with you before regarding the use of timestamps to verify logs ( https://github.com/guardianproject/haven/issues/22 ).

I believe that timestamps, despite being called timestamps, can help prevent recordings from being tampered with. I believe logs are tampered with, and would do so myself if I had to cover my tracks and was able to do it. I think we should work to be supportive of this use-case for trusted timestamps.

It's so incredible that you have created an open source project here to consolidate and standardize efforts around timestamping. I'm not certain the concerns I come up with are reasonable or valuable to others, but I hope that if they are that contributions would be welcome.

[petertodd]

If one of those servers becomes compromised and is able to create a hash collision, it could intentionally submit a tree that it could later replace with a different tree. Isn't this correct?

That's the point: even in that case, the timestamp proof is still valid because both trees would have to be created at the same time.

If you have doubts about OTS, I'm happy for you to use something else. But I'd strongly advise you to get the help of competent cryptographers first.

[xloem]

That's the point: even in that case, the timestamp proof is still valid because both trees would have to be created at the same time.

Exactly. If the server or your system is compromised, it could create two trees at the same time containing a hash collision. At first it publicizes only one of them. Later, after you have already verified the result and decided to trust it, it replaces it with the fake tree it prepared in advance, created at the same time as the correct tree. Do you see?

[petertodd]

I do see that; it is not an exploit. As you say, the "fake" tree would have been created at the same time as the "correct" tree. Thus, the timestamp proofs are still valid.

This is timestamping: there is no such thing as "replacing" one tree or another in the context of timestamping. Timestamping only proves that data exists prior to a point in time; timestamping does not prove the non-existence of data. By design OTS calendars are not a blockchain precisely to ensure that people don't mistakenly think they provide the guarantees that you seem to think they do.

I strongly recommend that you obtain the services of a qualified cryptographer; you seem to have serious misunderstandings about what OTS proves.

[xloem]

Well, I'm trying to convince you to support OTS proving the content of the data as well as the time, so that my purposes can be met by a standard =) This would require concern for hash collisions.

I can't imagine anybody can prove the non-existence of data. But I understand that OTS will not promise to prove that the content is unchanged. I think it could possibly be helpful to state this directly on the website somewhere.

Thanks for your time, Peter. This is the same reason I was arguing in the other issue I linked. If a timestamp were made with a strong hash and posted straight to the blockchain by a party the owner trusts, I feel it could offer very strong evidence against surreptitious tampering. Now I finally hear you, I'll post a comment to the Haven issue regarding this.

[petertodd]

I can't imagine anybody can prove the non-existence of data.

By restricting the definition of non-existence to a specific context, blockchains do exactly that.

But I understand that OTS will not promise to prove that the content is unchanged. I think it could possibly be helpful to state this directly on the website somewhere.

Note that the OTS website links to my blog post on this subject, which starts with examples of what exactly timestamps can and can't do: https://petertodd.org/2016/opentimestamps-announcement#what-can-and-cant-timestamps-prove

If a timestamp were made with a strong hash and posted straight to the blockchain by a party the owner trusts, I feel it could offer very strong evidence against surreptitious tampering.

Well, let's be clear: a timestamp does offer very strong evidence against surreptitious tampering if you can rule out surreptitious tampering in the past, prior to when the timestamp was made. In some use-cases this is possible; in other use-cases it is not.

[petertodd]

Anyway, I'm glad to help!

[xloem]

To clarify, these timestamps can mislead the user into believing their data has not been tampered with by publicizing a hash that verifies, but the data could be later replaced with differing data prepared at the same time, such that the hash still verifies. If the hash were resistant to collisions this would not be the case.

[RCasatta]

To clarify, these timestamps can mislead the user into believing their data has not been tampered with by publicizing a hash that verifies, but the data could be later replaced with differing data prepared at the same time, such that the hash still verifies. If the hash were resistant to collisions this would not be the case.

This is possible only if the receipt contains sha1 which is supported but not the default. As of today integrity of OpenTimestamps receipt is granted by using sha256 as default.

as Peter said if you are concerned with sha256 just use keccak256 which is already supported.

That said, I would be in favour of adding blake2 in the same way we support keccak256 always for marketing reasons. However, only if we have agreement between the libraries.

[xloem]

Thanks so much, RCasatta.

When posted this issue I had found https://github.com/opentimestamps/javascript-opentimestamps/blob/master/ots-cli.js#L68 and thought that keccak256 was not supported by this library. You guys seemed confident it is, so I looked through the rest of the code and see you are correct. It looks like when it was added in d13d5b4e1e661265a8af556dbaa79848da1ee040 ots-cli.js was not updated.