5

Consider the following scenario:

  1. I prepare a document with a "Lorem ipsum bla bla" content (Document_A) and get a trusted timestamp for this document (Timestamp_of_document_A).
  2. After some years, I decide to produce a specific patented product where the patent is taken after Timestamp_of_document_A.
  3. Patent holder eventually sues me.
  4. I create a fake document as if I have the patented content before the original patent has been issued.
  5. As a proof of time of my fake document, I provide court the Timestamp_of_document_A.

Content of my fake document is as follows:

In order to prepare that product, do that, do this.

Here is a photo of the macro shot of my table that I prepared the product:

[Here is some random pixel image]

As you can see, with enough computing power, one can equalize the fake document's hash to Timestamp_of_document_A by changing the random pixel image's pixels. So the court should accept the fake document as valid because it has the trusted timestamp.

How can this issue be resolved?

Improve this question
1

2 Answers 2

Reset to default
53

You claim that you can make the hashes match with enough computing power. The problem is that given a modern hash algorithm, neither you nor anybody else has this computing power. That's the whole point of cryptographic hash algorithms.

The attack you're describing is a preimage attack: For a given hash, you're trying to find an input which results in the same hash. All modern hash algorithms are designed to make such attacks impractical. For example, in the case of SHA-256, the NIST assumes a preimage resistance of 256 bits. In other words, you would have to perform 2^256 operations to carry out this attack. This is absolutely hopeless. Even just finding two arbitrary (but different) messages which have the same SHA-256 hash (so a collision attack) would require 2^128 operations.

So unless there's a mathematical and/or technological breakthrough, the attack doesn't work.

However, some now-obsolete hash algorithms like MD5 are vulnerable to collision attacks, including chosen-prefix collisions which allow the attacker to find collisions for meaningful messages, not just gibberish data: They can set two arbitrary prefixes P and P' and then find suffixes S and S', so that MD5(P + S) and MD5(P' + S') are identical. In principle, this could be used for a different attack against a time stamping authority (TSA): The attacker has a document with the hash D, and they want to get a signed timestamp token for a past date T. If the token has the format document hash + timestamp + additional data, and if the hash algorithm h used by the TSA is vulnerable to chosen-prefix collision, then the attacker could construct two tokens M = D + T + S and M' = D + T' + S' with h(M) = h(M'). T' is some time in the future (chosen by the attacker), and S and S' are the attacker-constructed suffixes. At time T', the attacker obtains the signature for the token hash(D) + T' + S' from the TSA and then uses it as a signature for the different token hash(D) + T + S. This makes it seem like document D already existed at the past date T. The attack has several major limitations, though.

  • The attacker has to know about the (chosen-prefix) collision vulnerability of the hash algorithm before the TSA phases out this algorithm
  • Since the TSA doesn't have a record of actually having issued the backdated token, the attack becomes obvious if the TSA database and not just the signature is checked.
  • For the attack to work, the attacker must be able to cram all necessarily data (including the suffix from the collision attack) into the specific token format used by the TSA.
  • The attacker may need to hide the suffix, so that it won't stand out as suspicious unexplained data if the token is inspected by an expert witness.
Improve this answer
11
  • 4
    The final mention of "unexplained data" detracts from an otherwise perfect answer. There's no reason or precedent for why an expert witnesses would have an issue with a classic digitized photo whose high level content fits the document logically enough, other than the possibility of a pre-image attack. Documents, images, and unexplained pixels appear before courts all the time. Commented Jul 22, 2024 at 10:58
  • 9
    @JimmyJames: It’s true that MD5 is vulnerable to collision attacks, but preimage attacks are still impractical (the preimage resistance is “only” 123.4 bits rather than the expected 128 bits according to this paper; however, that doesn’t matter in practice). So even if the Time Stamping Authority had used MD5 several years ago, the OP still wouldn’t be able to find a different input with the same hash today. Commented Jul 22, 2024 at 19:34
  • 1
    @JimmyJames: What an attacker could do is try to attack the hash over the entire timestamp token. This would require them to know about a collision vulnerability before the TSA phases out the vulnerable hash algorithm. When the attacker becomes aware of a patent submission, they could then try to find two timestamp tokens with the same hash where one token contains the hash of a fake patent document and a timestamp in the past, one has a timestamp t which lies in the future. At t, the attacker gets a signature for the second token which matches the signature of the first (forged) token. Commented Jul 22, 2024 at 19:37
  • 3
    @JimmyJames: Sure, I just wanted to stress that the MD5 vulnerabilities you’ve referenced aren’t relevant for the current scenario. Even a 30-year old algorithm with plenty of vulnerabilities like MD5 cannot be used for this specific attack. So in that regard, the attack is still hypothetical. “Modern algorithm” was meant as a very broad term, not in the sense that algorithms immediately turn out to be vulnerable to forgery attacks once they become obsolete. Commented Jul 22, 2024 at 20:06
  • 2
    @Ja1024 I get it. I hope you didn't see my comment as a critique. I just want to highlight the importance of keeping up to date with security which, for most (even technical) people, means finding a security expert (presumably, such as yourself) who they can trust to help them with that. Commented Jul 22, 2024 at 20:13
7

There are Thermodynamic Limitations to cracking these hashes.

And these limits are not just "X number of years with enough computers". If you took the sun, extracted all its energy, and have magical computers that can convert that energy to generating a hash, you wouldn't be able to crack a single 256-bit key.

Improve this answer
7
  • 12
    This answer could be improved by mentioning that it relies on the assumption that there's no significantly better way to reverse a hash than what is currently known. Commented Jul 22, 2024 at 16:15
  • 4
    Thermodymaics doesn't prevent you from cracking the key; it only limits the number of attempts you can make. Commented Jul 23, 2024 at 13:50
  • @JiK You mean XKCD hacking with a wrench?. Sure, but if they don't understand the initial premise of the cryptography, then they're not going to comprehend what's going on with the vulnerability. The nature of secure hash is that you're not going to "randomly guess it" within a reasonable timeframe. If they don't grasp this, then they're not going to meaningfully grasp vulnerabilities. Commented Jul 23, 2024 at 16:01
  • 7
    @Nelson, I took that to mean better-than-brute-force mathematical attacks -- means to rule out some of the search space. Such things do happen. Commented Jul 23, 2024 at 18:29
  • 1
    @Nelson "if they don't understand the initial premise of the cryptography" The premise is that there is no better algorithm to reverse such hashes than brute force. We have not proven that, we just assume so because we have tried a lot and nobody has figured out a way. The thermodynamics argument in this answer relies on that unproven assumption too. Commented Jul 25, 2024 at 12:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.