Merkle-fa

Egy bináris hash-fa

A kriptográfiában és a számítástechnikában a hash-fa vagy Merkle-fa egy olyan fa, amelyben minden "levél" (csomópont) egy adatblokk kriptográfiai hash-kódjával van ellátva, és minden olyan csomópont, amely nem levél (ág, belső csomópont vagy inode) a gyermekcsomópontjai címkéinek kriptográfiai hash-kódjával van ellátva. A hash-fa lehetővé teszi egy nagy adatszerkezet tartalmának hatékony és biztonságos ellenőrzését. A hash-fa a hash-lista és a hash-lánc általánosítása.

Annak bizonyítása, hogy egy levélcsomópont egy adott bináris hash-fa része, a fa levélcsomópontjai számának logaritmusával arányos számú hash kiszámítását igényli.[1] Ezzel szemben egy hash-listában ez a szám arányos a levélcsomópontok számával. A Merkle-fa ezért hatékony példája a kriptográfiai elkötelezettségi rendszernek, amelyben a fa gyökere egy elkötelezettségnek tekinthető, a levélcsomópontok pedig felfedhetők és bizonyíthatóan az eredeti elkötelezettség részét képezik.

A hash-fa fogalmát Ralph Merkle-ről nevezték el, aki 1979-ben szabadalmaztatta.[2][3]

Felhasználási esetek

[szerkesztés]

A kivonatfák bármilyen, számítógépen tárolt, kezelt és számítógépek között továbbított adat ellenőrzésére használhatók. Segítségükkel biztosítható, hogy a peer-to-peer hálózatban a többi egyenrangú féltől kapott adatblokkok sértetlenül és változatlanul érkezzenek, sőt, azt is ellenőrizni lehet, hogy a többi egyenrangú fél nem hazudik-e és nem küld-e hamis blokkokat.

A kivonatfákat a következőkben használják

  • hash-alapú kriptográfia;
  • Interplanetáris fájlrendszer (IPFS);
  • Btrfs és ZFS fájlrendszerek[4] (az adatromlás ellensúlyozására[5]);
  • Dat protokoll;
  • Apache Wave protokoll;[6]
  • Git és Mercurial elosztott revízióvezérlő rendszerek;
  • a Tahoe-LAFS biztonsági mentési rendszer;
  • Zeronet;
  • a Bitcoin és Ethereum peer-to-peer hálózatok;[7]
  • a Certificate Transparency keretrendszer;
  • a Nix csomagkezelő és leszármazottai, mint például a GNU Guix;
  • számos NoSQL rendszer, például az Apache Cassandra, a Riak és a Dynamo.[8]

Javaslatok születtek a hash-fák használatára a megbízható számítástechnikai rendszerekben.

A Merkle-fák Satoshi Nakamoto által készített kezdeti bitcoin-implementációja túlzott mértékben alkalmazza a hash-funkció tömörítési lépését, amit a Fast Merkle Trees alkalmazásával enyhítenek.[9]

Áttekintés

[szerkesztés]

A hash-fa egy hash-ekből álló fa, amelynek levelei (azaz a levélcsomópontok, néha "levelek" is) például egy fájl vagy fájlcsoport adatblokkjainak hash-jei. A fában feljebb lévő csomópontok a megfelelő gyermekeik hash-jai. Például a 0. hash a 0-0. és a 0-1. hash hash-ok összekapcsolásának eredménye. Vagyis hash 0 = hash( hash 0-0 + hash 0-1 ), ahol a "+" az összekapcsolást jelenti.

A legtöbb hash-fa implementáció bináris (minden csomópont alatt két gyermekcsomópont), de ugyanúgy használhatnak sokkal több gyermekcsomópontot is minden csomópont alatt.

A hash-eléshez általában egy kriptográfiai hash-függvényt, például SHA-2-t használnak. Ha a hash-fának csak a nem szándékos sérülések ellen kell védelmet nyújtania, használhatók nem biztonságos ellenőrző összegek, például CRC-k.

A hash-fa tetején van egy top hash (vagy gyökérhash vagy master hash). Mielőtt egy fájlt letöltünk egy P2P-hálózaton, a legtöbb esetben a legfelső hash-t egy megbízható forrásból szerezzük be, például egy barátunktól vagy egy olyan webhelyről, amelyről ismert, hogy jó ajánlásokat ad a letölthető fájlokra vonatkozóan. Ha a legfelső hash rendelkezésre áll, a hash-fa bármely nem megbízható forrásból, például a P2P-hálózat bármelyik társától megkapható. Ezután a kapott hash-fát a program ellenőrzi a megbízható top hash-hez képest, és ha a hash-fa sérült vagy hamis, akkor egy másik forrásból származó másik hash-fával próbálkozik, amíg a program nem talál olyan hash-fát, amely megfelel a top hash-nek.[10]

A fő különbség a hash-listához képest az, hogy a hash-fának egyszerre csak egy ága tölthető le, és az egyes ágak sértetlensége azonnal ellenőrizhető, még akkor is, ha a teljes fa még nem áll rendelkezésre. Például az L2 adatblokk sértetlensége azonnal ellenőrizhető, ha a fa már tartalmazza a 0-0 és az 1 hash-t. Ehhez az adatblokk hash-elését kell elvégezni, és az eredményt iteratívan kombinálni a 0-0, majd az 1 hash-sel, végül pedig az eredményt a legfelső hash-sel kell összehasonlítani. Hasonlóképpen, az L3 adatblokk sértetlensége ellenőrizhető, ha a fa már tartalmaz 1-1 és 0 hash-t. Ez előnyös lehet, mivel hatékony a fájlok nagyon kis adatblokkokra való felosztása, így sérülés esetén csak kis blokkokat kell újra letölteni. Ha a hashelt fájl nagy, egy ilyen hash-lista vagy hash-lánc meglehetősen nagy lesz. De ha ez egy fa, akkor egy kis ágat gyorsan le lehet tölteni, ellenőrizni lehet az ág sértetlenségét, és utána kezdődhet az adatblokkok letöltése.

Második preimage támadás

[szerkesztés]

A Merkle-hash-gyökere nem jelzi a fa mélységét, ami lehetővé teszi a második preimage támadást, amelynek során a támadó az eredetitől eltérő dokumentumot hoz létre, amelynek ugyanaz a Merkle-hash-gyökere van. A fenti példa esetében a támadó létrehozhat egy új dokumentumot, amely két adatblokkot tartalmaz, ahol az első hash 0-0 + hash 0-1, a második pedig hash 1-0 + hash 1-1.[11][12]

Egy egyszerű javítás a Certificate Transparency című könyvben található: a levélcsomópontok hash-jének kiszámításakor a hash-adatokhoz egy 0x00 bájtot, míg a belső csomópontok hash-jének kiszámításakor 0x01 bájtot kell előretenni. A hash-fa méretének korlátozása néhány formális biztonsági bizonyítás előfeltétele, és segít néhány bizonyítás szigorításában. Egyes implementációk a hash-fa mélységét a hash-fa mélységének előtagjaival korlátozzák a hash-ok előtt, így bármely kivont hash-lánc csak akkor tekinthető érvényesnek, ha az előtag minden lépésnél csökken, és a levél elérésekor még mindig pozitív.

Tiger hash-fa

[szerkesztés]

A Tiger hash-fa a hash-fa egy széles körben használt formája. Bináris hash-fát használ (minden csomópont alatt két gyermekcsomópont), általában 1024 bájtos adatblokkmérettel rendelkezik, és a Tiger hash-t használja.[13]

Tiger hash-fákat használnak a Gnutella,[14] Gnutella2 és Direct Connect P2P fájlmegosztó protokollokban,[15] valamint olyan fájlmegosztó alkalmazásokban, mint a Phex,[16] BearShare, LimeWire, Shareaza, DC++[17] és gtk-gnutella.[18]

Források

[szerkesztés]

Jegyzetek

[szerkesztés]
  1. ↑ Wayback Machine. web.archive.org. [2014. december 22-i dátummal az eredetiből archiválva]. (Hozzáférés: 2024. március 1.)
  2. ↑ Espacenet - Bibliographic data. worldwide.espacenet.com. (Hozzáférés: 2024. március 1.)
  3. ↑ Merkle, Ralph C. (1988. november 4.). „A Digital Signature Based on a Conventional Encryption Function” (angol nyelven). Advances in Cryptology — CRYPTO ’87, Berlin, Heidelberg, 369–378. o, Kiadó: Springer. DOI:10.1007/3-540-48184-2_32. 
  4. ↑ ZFS End-to-End Data Integrity (Jeff Bonwick's Blog). web.archive.org, 2012. április 3. [2012. április 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2024. március 1.)
  5. ↑ Liu, Likai: Bitrot Resistance on a Single Drive (angol nyelven). (Hozzáférés: 2024. március 1.)
  6. ↑ General Verifiable Federation - Google Wave Federation Protocol. web.archive.org, 2018. április 8. [2018. április 8-i dátummal az eredetiből archiválva]. (Hozzáférés: 2024. március 1.)
  7. ↑ Koblitz, Neal (2016. január 1.). „Cryptocash, cryptocurrencies, and cryptocontracts” (angol nyelven). Designs, Codes and Cryptography 78 (1), 87–102. o. DOI:10.1007/s10623-015-0148-5. ISSN 1573-7586. 
  8. ↑ The Architecture of Open Source Applications (Volume 1)The NoSQL Ecosystem. aosabook.org. (Hozzáférés: 2024. március 1.)
  9. ↑ bips/bip-0098.mediawiki at master · bitcoin/bips (angol nyelven). GitHub. (Hozzáférés: 2024. március 1.)
  10. ↑ Laurie, Ben, Emilia (2013. június 1.). „Certificate Transparency”. 
  11. ↑ Andreeva, Elena, Pierre-Alain (2008. november 4.). „Second Preimage Attacks on Dithered Hash Functions” (angol nyelven). Advances in Cryptology – EUROCRYPT 2008, Berlin, Heidelberg, 270–288. o, Kiadó: Springer. DOI:10.1007/978-3-540-78967-3_16. 
  12. ↑ Andreeva, Elena, Orr (2009. november 4.). „Herding, Second Preimage and Trojan Message Attacks beyond Merkle-Damgård” (angol nyelven). Selected Areas in Cryptography, Berlin, Heidelberg, 393–414. o, Kiadó: Springer. DOI:10.1007/978-3-642-05445-7_25. 
  13. ↑ Tree Hash EXchange format (THEX). web.archive.org, 2009. augusztus 3. [2009. augusztus 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2024. március 1.)
  14. ↑ Gtk-Gnutella: tigertree.c File Reference. gtk-gnutella.sourceforge.io. (Hozzáférés: 2024. március 1.)
  15. ↑ Attack Signature Detail Page (angol nyelven). www.broadcom.com. (Hozzáférés: 2024. március 1.)
  16. ↑ Phex - Phex 3.0.0 released. www.phex.org. (Hozzáférés: 2024. március 1.)
  17. ↑ DC++ your files, your way, no limits. dcplusplus.sourceforge.io. (Hozzáférés: 2024. március 1.)
  18. ↑ gtk-gnutella - The Graphical Unix Gnutella Client. gtk-gnutella.sourceforge.io. (Hozzáférés: 2024. március 1.)