En criptografía e ciencias da computación, unha árbore de hash ou árbore de Merkle é unha árbore na que cada nó «folla» está etiquetado co hash criptográfico dun bloque de datos e cada nó que non é unha folla (denominado rama ou nó interno) está etiquetado co hash criptográfico das etiquetas dos seus nós fillos. Unha árbore de hash permite verificar de maneira eficiente e segura o contido dunha estrutura de datos de gran tamaño. Unha árbore de hash é unha xeneralización dunha lista hash e dunha cadea hash.
Nunha árbore de hash binaria equilibrada, verificar unha proba de inclusión dunha folla require un número de operacións hash proporcional ao logaritmo do número de follas, unha vez dispoñibles os hash do camiño de autenticación. Isto evita ter que transmitir a lista completa de hash, cuxo tamaño é proporcional ao número de follas. Unha raíz de Merkle permite vincular un conxunto de datos cun resumo, e os camiños de autenticación permiten verificar elementos individuais. Esta vinculación non implica por si soa a ocultación dos datos.
O concepto recibe o nome de Ralph Merkle, que presentou a solicitude da patente estadounidense o 5 de setembro de 1979; a patente 4.309.569 concedeuse o 5 de xaneiro de 1982. Solicitude presentada o 5 de setembro de 1979. Cesionario: The Board of Trustees of the Leland Stanford Junior University. Merkle tamén publicou construcións de sinaturas dixitais baseadas en árbores.
Usos As árbores de hash poden empregarse para verificar datos almacenados, procesados e transferidos nos computadores e entre eles. Se se coñece unha raíz auténtica, permiten comprobar que os bloques de datos recibidos doutros pares nunha rede entre pares non sufriron danos nin alteracións, mesmo se proceden dun par malicioso.
As árbores de hash utilízanse en: criptografía baseada en hash; InterPlanetary File System (IPFS), que emprega unha xeneralización en forma de grafo acíclico dirixido de Merkle; BitTorrent, na versión 2 do protocolo; o sistema de ficheiros ZFS (para combater a degradación de datos); o protocolo Dat; o deseño proposto para o protocolo de federación de Google Wave, antecesor de Apache Wave; os sistemas de control de versións distribuídos Git e Mercurial (aínda que, en sentido estrito, empregan grafos acíclicos dirixidos, non árbores); o sistema de copias de seguridade Tahoe-LAFS; ZeroNet, na identificación de ficheiros da extensión Bigfile; OpenZFS; as redes entre pares Bitcoin Copia dos autores do 1 de outubro de 2015, sección 3. e Ethereum; o sistema Certificate Transparency; a proposta de certificados de árbore de Merkle; o xestor de paquetes Nix e os seus derivados, como GNU Guix; varios sistemas NoSQL, como Apache Cassandra, Riak e Dynamo. En Dynamo, estas árbores permiten comparar réplicas e localizar diferenzas mediante un proceso de antientropía.
Tamén se empregan como compromisos en argumentos criptográficos eficientes. En sistemas de computación de confianza, propúxose usalas para verificar a integridade da memoria externa dun procesador protexido.
A vinculación coa raíz depende da resistencia a colisións, da codificación e da estrutura da árbore. Un resumo non garante por si só que os datos queden ocultos: cando son previsibles, pódense calcular candidatos e comparar os resultados.
Visión xeral As follas dunha árbore de hash conteñen os resumos dos bloques de datos de, por exemplo, un ficheiro ou un conxunto de ficheiros. Os nós internos conteñen o hash da concatenación dos valores dos seus fillos. Por exemplo, na imaxe anterior, o hash 0 é o resultado de aplicar a función hash á concatenación dos hash 0-0 e hash 0-1. É dicir, hash 0 = hash( hash 0-0 + hash 0-1 ), onde «+» indica concatenación, respectando a orde dos fillos.
A maioría das implementacións de árbores de hash son binarias (dous nós fillos baixo cada nó), pero tamén poden empregar moitos máis nós fillos baixo cada nó.
Normalmente emprégase unha función hash criptográfica, como SHA-2, para calcular os hash. Se a árbore de hash só necesita protexer contra danos involuntarios, poden empregarse sumas de comprobación non criptográficas, como as CRC.
Na parte superior dunha árbore de hash hai un hash superior (ou hash raíz ou hash mestre). Para autenticar os datos, o verificador debe dispoñer dunha raíz de confianza. A partir dela pode comprobar os bloques e os camiños de autenticación recibidos de fontes non fiables, como pares dunha rede P2P, e rexeitar os que non concorden coa raíz esperada. Copia arquivada o 3 de agosto de 2009.
Un camiño de autenticación contén os hash irmáns e a súa posición para reconstruír a raíz. Na figura, o bloque L2 pode comprobarse co hash 0-0 e o hash 1: calcúlase o hash de L2, combínase primeiro co hash 0-0 na orde indicada e despois co hash 1, e compárase coa raíz auténtica. Para L3 úsanse o hash 1-1 e o hash 0. Así pódese verificar un bloque sen descargar a árbore enteira.
Ataque de segunda preimaxe Se a construción non distingue os datos das follas dos hash dos nós internos nin vincula adecuadamente a estrutura da árbore, pode permitir un ataque de segunda preimaxe por confusión entre ambos os tipos de nó. No exemplo anterior, se eses tamaños de bloque son admisibles e se usa a mesma función sen prefixos distintos, un novo documento con dous bloques, hash 0-0 + hash 0-1 e hash 1-0 + hash 1-1, produce os antigos nós internos como follas e conserva a raíz. Non é unha vulnerabilidade inevitable de toda árbore de Merkle.
En Certificate Transparency defínese unha solución sinxela: ao calcular os hash dos nós folla, anteponse un byte 0x00 aos datos aos que se aplica o hash, mentres que se antepón 0x01 ao calcular os hash dos nós internos. Algunhas demostracións de seguridade de esquemas de selado de tempo enlazado establecen límites explícitos no número de elementos comprometidos e nos camiños admitidos; as cotas dalgunhas reducións dependen deses límites. Por exemplo, a implementación de KSI de Guardtime incorpora o nivel ao cálculo dos nós internos e comproba un nivel máximo; as follas teñen nivel cero.
Hash de árbore Tiger O hash de árbore Tiger é unha forma de árbore de hash. Emprega unha árbore de hash binaria (dous nós fillos baixo cada nó), adoita ter un tamaño de bloque de datos de 1024 bytes, recomendado polo formato THEX, e utiliza o hash Tiger.
O seu uso está documentado no protocolo Gnutella2 e en clientes como DC++ e gtk-gnutella. Phex incorporou soporte para subidas con estes hash na versión 3.0.0, publicada en 2007.
Notas
Véxase tamén Bibliografía Patente da árbore de Merkle 4,309,569: explica tanto a estrutura da árbore de hash como o seu uso para xestionar moitas sinaturas dun só uso. Tree Hash EXchange format (THEX): especificación das árbores Tiger, arquivada o 16 de marzo de 2008. Estuda, entre outros, ataques de segunda preimaxe contra funcións hash en árbore. Trata ataques a funcións hash iterativas con dithering, distintos da confusión entre follas e nós internos.
Outros artigos Árbore binaria Cadea de bloques Táboa de hash distribuída Táboa hash Trie hash Selado de tempo enlazado Árbore radix
Ligazóns externas Unha implementación en C dunha árbore de hash binaria SHA-256 con crecemento dinámico (árbore de Merkle) Implementación dunha árbore de Merkle en Java ThexCS: artigo e exemplos de Tiger Tree Hash (TTH) en C#, por Gil.Schmidt; copia arquivada o 30 de outubro de 2019. Implementacións de Tiger Tree Hash (TTH) en C e Java RHash, unha ferramenta de liña de comandos de código aberto que pode calcular TTH e ligazóns magnet con TTH.
Categoría:Criptografía Categoría:Programación