1

We use a linked hash list for data integrity.

Content is hashed (HMAC-SHA256) and stored in a block that itself is hashed and referenced in the next block:

Simplified example:

...
{
   id: "block1",
   cId: "A",
   cHash: "hashOfA",
   pId: "block0",
   pHash: "hashOfBlock0",
   t: time
},
{
   id: block2,
   cId: "B",
   cHash: "hashOfB",
   pId: "block1",
   pHash: "hashOfBlock1",
   t: time
},
...

This enables us to detect changes in the content. The only problem we have is, that we cannot detect a whole replacement of the latest block that was added to the list. As this block has no following block that confirms it.

How can we confirm that the last block is not altered/replaced?

We thought about a top hash of the complete hash list securely stored somewhere else and is updated every time a new block is created. But how could we confirm the top hash is not altered? What would be a secure storage for this hash? Public? Are there some other solutions?

3
  • 1
    It sounds like you are trying to reinvent a Blockchain . See en.wikipedia.org/wiki/Blockchain Commented Dec 14, 2020 at 23:12
  • it's no reinventing it's a blockchain, but without the decentralized storage and proof of work - just a simple linked hash list - as we use it only for data integrity within our system.
    – codeteq
    Commented Dec 15, 2020 at 9:22
  • 1
    *'it's a blockchain, but without the ... proof of work' *. This is exactly why blockchains have a proof of work. The proof of work solves the problem that you are trying to solve. Blocks cannot be added or replaced without the proof of work. That makes it very difficult for an attacker to replace a block with his own - doing so would require a massive amount of computing power.
    – mti2935
    Commented Dec 15, 2020 at 18:50

1 Answer 1

1

You need to save a MAC (also named "tag" sometimes) of the last entry at a safe place. What safe means here depends on your threat model, but it should at least resit to the following attack:

Be warned that if the attacker can read this MAC at any point in time and has write access to it, it can restore the chain to a previous version by overwriting the MAC. For this the attacker does not need to know the secret authentication key used to compute the MAC.

To prevent a rollback of your chain, you must ensure that the MAC cannot be rolled back without noticing. This might be done for example by using a web service to store it and keep its history.

It was suggested to you to insert this MAC in the first node of the chain. If this MAC were part of the hashed data of the first node, this would introduce an unsolvable cycle of hashes. Thus, the MAC of the last node must be saved outside the structure of the hashed chain.

As a side note, this MAC can be based on a hash function like HMAC-SHA256, or it can be a fast (and still secure) MAC like SipHash. Other secure algorithms exist, but just ensure that the produced tag is at least 128 bits long and that the secret key is generated by a CSPRNG and of at least 128 bits.

10
  • so this is more or less a similiar approach like the top hash of the hashlist ?
    – codeteq
    Commented Dec 14, 2020 at 15:41
  • @codeteq Yes. If your threat model allows it, you can store this MAC in the first node, as suggested in the answer of kelalaka.
    – A. Hersean
    Commented Dec 14, 2020 at 16:28
  • To prevent a rollback you must ensure that the MAC cannot be rolled back without noticing. This might be done for example by using a web service to store it and keep its history.
    – A. Hersean
    Commented Dec 14, 2020 at 16:30
  • 1
    @kelalaka I will refrain for suggesting the use of a blockchain, which almost always introduce more issues than it solves. It is indeed possible the use cryptographic signatures instead of MACs, but it is far less efficient.
    – A. Hersean
    Commented Dec 15, 2020 at 18:04
  • 1
    Even the OP's problem (that does not use blockchain but an authenticated linked list) might be better solved just by proper authentication and access control. Which, in the end, it still needs to do to protect the MAC of the last node of the linked list.
    – A. Hersean
    Commented Dec 16, 2020 at 9:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .