Como o Android DM-Verity Protection valida blocos com hash tree -- boot campo com os campo com dm-verity camp android Relacionado O problema

How does android dm-verity protection validate blocks with hash tree


3
vote

problema

português

Eu estou aprendendo sobre a proteção do Android DM-Verity e tento entender como o Android DM-verity usa a árvore de hash para validação de "bloco único".

https://source.android.com/security/veriedBoot/dm-verity diz:

.

Em vez disso, a dm-verity verifica os blocos individualmente e somente quando cada um é acessado. Quando ler em memória, o bloco é hash em paralelo. O hash é então verificado a árvore. E desde que ler o bloco é uma operação tão cara, a latência introduzida por esta verificação no nível do bloco é comparativamente nominal.

Depois que o bloco é lido e hash, é verificado a árvore. mas como posso verificar hash root, quando eu não li todos os blocos? Eu posso verificar exatamente essa parte da árvore que li, e isso significa que eu não tenho que ir até raízes cerquilha.

Eu não entendo porque usamos uma árvore de hash. stackoverflow thread diz que a principal razão para usar hash árvores é quando o hash é calculado para cada Bloco e do que para todo o arquivo novamente, não entendo porque é usado aqui.

Então, como é realmente implementado? Minha suposição é que quando o bloco é carregado para a memória Android apenas verifica a ramificação específica e o restante dos valores são retirados da hash árvore pré-computada. Mas do que não vejo o motivo para usar a árvore. Eu apenas armazenaria valores de hash de blocos e depois de ler o bloco e hashing comparar apenas o hash.

editar: vamos assumir essa implementação:

    .
  1. dividiu todo o dispositivo de bloco para os blocos de tamanho 4K.
  2. hash cada determinado bloco e hashes de concatenato (criar camada 0 de dm-verity)
  3. armazenar os hashes (camada 0) no final do dispositivo de bloco Agora, quando eu quero verificar o bloco 4K carregado na memória, encontro a posição do bloco e comparamos o hash de bloco carregado com o hash armazenado.

Na situação como Usando uma árvore faz sentido, porque você só tem raiz de merkle disponível, mas no Android, temos toda a árvore, então por que apenas não usar a camada 0 (implementação acima) e jogar fora o resto.

E ao escrever, acho que cheguei a uma resposta. Android armazena toda a árvore de hash no final. Mas a árvore não é assinada, apenas a tabela de veridade de DM (metadados) que contém o hash raiz. Então, na minha implementação, teria que assinar toda a camada 0. E isso provavelmente desperdiçando recursos, então é melhor usar a árvore.

english

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.

        

Lista de respostas

3
 
vote
vote
Melhor resposta
 

"Mas como posso verificar o hash root, quando não li todos os blocos?"

.

"Em essência, as folhas da árvore são páginas contendo valores de hash; cada nível superior na árvore contém hashes dos blocos abaixo dela." referência

Exemplo:

.

"Um caminho de merkle é usado para provar a inclusão de um elemento de dados. Um nó pode provar que uma transação K está incluída no bloco, produzindo um caminho de merkle que é apenas quatro hashes de 32 bytes (total de 128 bytes). O caminho consiste nos quatro hashes (mostrados com um fundo sombreado em um caminho de merkle usado para provar inclusão de um elemento de dados) HL, Hij, Hmnop e Habcdefgh. Com esses quatro hashes fornecidos como um caminho de autenticação, qualquer nó pode provar que HK (com um fundo preto na parte inferior do diagrama) é incluído na raiz de merkle, computando quatro hashes de casal adicional HKL, hijkl, hijklmnop e a raiz da árvore de merkle. "  merkle tree referência

"Eu apenas armazenaria os valores de hash de blocos e depois de ler o bloco e o hashing comparar apenas o hash."

Você tem que lembrar que os telefones celulares têm uma quantidade limitada de recursos. Sua maneira de fazer isso você tem que ler o bloco inteiro e comparar para verificar a validade antes. Com a árvore, você só precisa ler uma parte dela para verificar a validade.

.

"No entanto, tentar verificar um dispositivo de bloco inteiro pode assumir um período prolongado e consumir grande parte da energia de um dispositivo. Os dispositivos levariam longos períodos para inicializar e, em seguida, serem significativamente drenados antes de usar." referência

Para ajudar com sua pesquisa, acho que seria importante conhecer a teoria da árvore de hash. É chamado de ABCDEFGHIJKLMNABCDEFGHIJKLMN0 primeiro patenteado pelo Merkle Ralph

 

"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

 
 
     
     

Perguntas relacionadas

1  Se eu gerar minha própria chave personalizada e assinar uma ROM personalizada, poderei ter acesso root depois de bloquear o bootloader?  ( If i generate my own custom key and sign a custom rom then will i be able to ha ) 
Então, o que eu quero fazer é inicializar em minha própria ROM personalizada com um bootloader bloqueado. Eu tenho um oneplus 6t por isso é possível, mas poss...

1  Como verificar se eu desativei com sucesso a veracidade do DM?  ( How to check if i have successfully disabled dm verity ) 
Meu telefone tem a veracidade do DM ativada por padrão. Eu li sobre maneiras de desativá-lo. Depois disso, há alguma maneira com a qual posso verificar se a v...

2  Como habilitar adequadamente a veracidade de DM e FEC para / Sistema no Motorola X4 com Lineagos 17.1?  ( How to properly enable dm verity and fec for system on motorola x4 with lineage ) 
Eu construí LineageOS 17,1 para Motorola X4 / payton com desbloqueado bootloader com revertidos cometer 81cc203c06596878d2beb62ab6e07f36e278018e . A questão ...

3  Como a Update_Engine valide uma imagem de atualização diferencial com a veracidade de DM ativada?  ( How does update engine validate a differential update image with dm verity enabl ) 
Eu estou trabalhando com o Android 8, a inicialização verificada ao Android com verificação de DM e atualizações de A / B diferenciais baseadas em bloco. Para...

4  Como desativar a veracidade do DM no Android com "User" Build Type ROM?  ( How to disable dm verity on android with user build type rom ) 
Eu tenho um dispositivo Android Plus 6T que possui uma ROM de Tipo de Construção ABCDEFGHIJKLMNABCDEFGHIJKLMN0 . Este dispositivo está enraizado com a MAGISK...

1  Como lidar com DM-Verity em uma borda Samsung S7 ao instalar uma recuperação personalizada como o TWRP  ( How to deal with dm verity on a samsung s7 edge when installing a custom recover ) 
Eu estou apenas começando a explorar como personalizar meu Samsung S7 Edge e estou interessado em mover um aplicativo para a partição do sistema. Atualmente e...

3  Como o Android DM-Verity Protection valida blocos com hash tree  ( How does android dm verity protection validate blocks with hash tree ) 
Eu estou aprendendo sobre a proteção do Android DM-Verity e tento entender como o Android DM-verity usa a árvore de hash para validação de "bloco único". h...

1  Alterando /system/build.props em Totalmente Enraizado e DM-Verity removido dispositivo  ( Changing system build prop issues on fully rooted and dm verity removed device ) 
Então, eu tenho um MT6739 Dveice com Android 8.1, não é um / b sem costura, e não é agudo. Eu usei um método experimentado e testado para remover a veracida...

0  XTouch S40 Stock ROM Download  ( Xtouch s40 stock rom download ) 
Eu tenho um Xtreme S40 em execução no Android 9. Eu piscou a recuperação com uma imagem personalizada do Twrp e está preso em um loop de inicialização e exibe...

2  Instalar magisk no TWRP, com "Manter DM-Verity / AVB 2.0" opção?  ( Install magisk in twrp with keep dm verity avb 2 0 option ) 
Eu quero piscar o ZIP MAGISK enquanto mantém o DM-Verity e o AVB 2.0. O ZIP MAGISK detecta meu ABCDEFGHIJKLMBCDefGHIJKLMN1 Partição e mantém a criptografi...




© 2022 pergunte.org All Rights Reserved. Casa de perguntas e respostas todos os direitos reservados


Licensed under cc by-sa 3.0 with attribution required.