3

I am learning about android dm-verity protection and I try to understand how does the android dm-verity uses the hash tree for validation of "single block".

https://source.android.com/security/verifiedboot/dm-verity says:

Instead, dm-verity verifies blocks individually and only when each one is accessed. When read into memory, the block is hashed in parallel. The hash is then verified up the tree. And since reading the block is such an expensive operation, the latency introduced by this block-level verification is comparatively nominal.

After the block is read and hashed, it is verified up the tree. But how can I verify root hash, when I have not read all the blocks?? I can verify just that part of the tree I have read, and that means I do not have to go up to root hash.

I do not understand why we use a hash tree. StackOverflow thread says that main reason for using hash trees is when the hash is computed for every block and than for the whole file again, i don't get why it is used here.

So how it is actually implemented?? My assumption is that when the block is loaded to memory android just checks the particular branch and rest of values are taken from the pre-computed hash tree. But than I don't see the reason for using the tree. I would just store block hash values and after reading the block and hashing compare just the hash.

Edit: Let's assume this implementation:

  1. split the whole block device to the blocks of 4K size.
  2. hash each particular block and concatenate hashes(create layer 0 of dm-verity)
  3. store the hashes (layer 0) at the end of block device Now, when I want to verify 4K block loaded to the memory, I find the block position and compare the hash of loaded block with the stored hash.

In the situation as this using a tree makes sense, because you only have Merkle root available, but in Android, we have the whole tree, so why just not use the layer 0 (implementation above) and throw away the rest.

And while writing, I think I came up with an answer. Android stores the whole hash tree at the end. But the tree is not signed, only the dm-verity table(metadata) that contains the root hash. So, In my implementation, I would have to sign the whole layer 0. And that is probably wasting resources, so it's better to use the tree.

2

"But how can I verify root hash, when I have not read all the blocks??"

"In essence, the leaves of the tree are pages containing hash values; each higher level in the tree contains hashes of the blocks below it." Reference

Example:

"A merkle path is used to prove inclusion of a data element. A node can prove that a transaction K is included in the block by producing a merkle path that is only four 32-byte hashes long (128 bytes total). The path consists of the four hashes (shown with a shaded background in A merkle path used to prove inclusion of a data element) HL, HIJ, HMNOP, and HABCDEFGH. With those four hashes provided as an authentication path, any node can prove that HK (with a black background at the bottom of the diagram) is included in the merkle root by computing four additional pair-wise hashes HKL, HIJKL, HIJKLMNOP, and the merkle tree root ."merkle tree Reference

"I would just store block hash values and after reading the block and hashing compare just the hash."

You have to remember that cell phones have a limited amount of resources. Your way of doing it you have to read the whole block and compare to verify the validity before. With the tree you only need to read a part of it to verify validity.

"However, attempting to verify an entire block device can take an extended period and consume much of a device's power. Devices would take long periods to boot and then be significantly drained prior to use." Reference

To help with your research I think it would be important to know the hash tree theory. It is called the Merkle tree first patented by Ralph Merkle

  • From what I understand besides 1. Binary search tree never meets collision, which means binary search tree can guarantee insertion, retrieve and deletion are implemented in O(log(n)), which is hugely fast than linear time. Besides, space needed by tree is exactly same as size of input data. 2. You do not need to know size of input in advance. 3. all elements in tree are sorted that in-order traverse takes O(n) time. Which is key in things like phone contacts which are in alphabetical order. – Bo Lawson Dec 8 '18 at 14:30
  • 1
    Thank you. I haven't heard about Merkle path, and now it's clear to me how the blocks are validated. However, I still was not sure why they use the tree, so I will edit my question, to clarify what I did not get. – zvaratom Dec 8 '18 at 14:32
  • 1
    The main reason is security. Keep in mind that android is supposed to be read-only to the user. Modification to any block is equivalent to breaking the cryptographic hash. dm-verity verifies blocks individually and only when each one is accessed. When read into memory, the block is hashed in parallel. The hash is then verified up the tree. And since reading the block is such an expensive operation, the latency introduced by this block-level verification is comparatively nominal. – Bo Lawson Dec 8 '18 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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