Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Let's say we have a timestamping scheme of the following characteristics,

  • The hashes of the documents we are trying to timestamp are XOR'ed with "events" whose time of occurrence are very publicly known (i.e. the hash of the latest block on the blockchain),

$$M_{i}=(H_{D_{i}} \oplus B_{t_{i}})$$

Where,

$M_{i} =$ the hash of the document "mixed" with a known public event,

$H_{D_{i}} =$ hash of document to timestamp,

$B_{t_{i}} =$ hash of the latest block on the blockchain (a very known public event) at the time of timestamping ,

  • The concatenation of $M_{i}$ and the previous timestamp gets hashed together forming a new node on a hashed linked list,

$$H_{i} = Hash(M_{i} ||H_{i-1})$$

Where,

$H_{i} =$ the timestamp of the document.

  • Each $H_{i}$ is then published in "real time" into an independent (no relation to the timestamper) public third party platform so that anybody can potentially monitor any modification to the list. An example of this type of platform could be Twitter where each tweet is the concatenation of the current and previous timestamp,

$$T_{i} = H_{i} || H_{i-1}$$

Where,

$T_{i} =$ Public reference of the timestamping (i.e. a tweet).

That being said,

  1. What are your thoughts of the following assertions?

    • Future-dating a document (even in collusion with the timestamping service) would be not feasibly because of the unpredictable nature of the public event (i.e. it is not feasibly to know what the hash of the next block in the blockchain is going to be unless someone mines it).

    • Backdating a document, even in collusion with the timestamping service, would not be feasibly because of the nature of the hashed linked list.

  2. Does anybody know if a scheme like this is already described and/or implemented somewhere?
  3. What are your thoughts about the weaknesses of a scheme like this?
share|improve this question
add comment

1 Answer 1

Your diagram is not very clear, but XOR is not a good combiner function to use for timestamping, as it may allow backdating in some circumstances. For instance, see the "time travel" attacks in Section 3.3 of the following paper (e.g., pp.179-180): Cryptanalytic Attacks on Pseudorandom Number Generators. Depending upon how many inputs you have to the XOR function and the specific details of your scheme (which are not sufficiently clear from your question), generalized birthday attacks may also be possible and might allow backdating.

Instead, you should use hashing. There are standard constructions for hash-chaining: I suggest you use them. In particular, if the sequence of documents/data to be hashed is $D_1,D_2,D_3,\dots$, we form a hash chain by the formula

$$H_i = \text{Hash}(H_{i-1} \,||\, \text{Hash}(D_i)).$$

Then we can publish the $H_i$'s as well as each $\text{Hash}(D_i)$. See a standard reference on hash chaining and timestamping for more details.


Update (after the question was edited):

No, this is definitely not a good idea, because $x \oplus y$ does not uniquely determine $x$ and $y$.

For instance, someone could register $H_{D_i}$ (which gets mixed with $B_{t_i}$), then later claim that they actually registered $H'_{D_i}$ (and it was mixed with $B'_{t_i}$), as long as $H_{D_i} \oplus B_{t_i} = H'_{D_i} \oplus B'_{t_i}$. How would you detect it? There's not a fantastic way to do it.

It would be much better to compute $M_i$ as

$$M_i = \text{Hash}(\text{Hash}(D_i), t_i, B_{t_i}).$$

Now $D_i$ and $B_{t_i}$ are uniquely determined, given $M_i$; the collision-resistance of the hash function prevents backdating or lying about how $M_i$ was formed. This is such a simple fix, and it is so obviously better, that there's not much point analyzing in great detail the exact degree of vulnerability of xor; it's clear that using a hash is better than using a xor, so there's absolutely no reason to use a xor in this context.

So, bottom line: use a hash function, not xor.

share|improve this answer
    
Now that I learned how to insert formulas I made a major refactoring of my question to make it clearer. –  jliendo Apr 26 at 17:16
1  
@jliendo, I've edited my answer accordingly. The bottom line remains the same. –  D.W. Apr 26 at 19:37
    
Wonderful and truly helpful explanation D.W. –  jliendo Apr 26 at 20:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.