SipHash - SipHash - Wikipedia

SipHash je přidat – otočit – xor (ARX) založená rodina pseudonáhodné funkce vytvořil Jean-Philippe Aumasson a Daniel J. Bernstein v roce 2012,[1]:165[2] v reakci na příval „zatopení hashem“ útoky odmítnutí služby na konci roku 2011.[3]

Ačkoli je určen pro použití jako hashovací funkce ve smyslu počítačové vědy se SipHash zásadně liší od kryptografické hashovací funkce jako SHA v tom, že je vhodný pouze jako a ověřovací kód zprávy: a klíčováno hash funkce jako HMAC. To znamená, že SHA je navržen tak, aby pro útočníka bylo obtížné najít dvě zprávy X a Y takový, že SHA (X) = SHA (Y), i když kdokoli může vypočítat SHA (X). SipHash to místo toho zaručuje, když to viděl Xi a SipHash (Xi, k), útočník, který nezná klíč k nelze najít (žádné informace o) k nebo SipHash (Y, k) pro jakoukoli zprávu Y ∉ {Xi} které ještě neviděli.

Přehled

SipHash počítá 64-bit ověřovací kód zprávy ze zprávy s proměnnou délkou a 128bitového tajného klíče. Byl navržen tak, aby byl efektivní i pro krátké vstupy, s výkonem srovnatelným s ne kryptografickými hashovacími funkcemi, jako např CityHash,[4]:496[2]lze jej tedy použít k zabránění útokům typu odmítnutí služby hash tabulky („zatopení hashem“),[5] nebo k ověření síťové pakety. Později byla přidána varianta, která produkuje 128bitový výsledek.[6]

Neklíčená hashovací funkce, jako je SHA, je odolná proti kolizi, pouze pokud je použit celý výstup. Pokud se používá ke generování a malý výstup, například index do hash tabulky praktické velikosti, pak žádný algoritmus nemůže zabránit kolizím; útočník musí provést pouze tolik pokusů, kolik je možných výstupů.

Předpokládejme například, že síťový server je navržen tak, aby dokázal zpracovat až milion požadavků najednou. Sleduje příchozí požadavky v hašovací tabulce se dvěma miliony záznamů, pomocí hašovací funkce mapuje identifikační informace z každého požadavku na jeden ze dvou milionů možných záznamů v tabulce. Útočník, který zná hashovací funkci, ji musí pouze krmit libovolnými vstupy; jeden ze dvou milionů bude mít konkrétní hashovou hodnotu. Pokud nyní útočník pošle několik stovek žádostí, všechny vybrané k získání stejný hash value to the server, that will produce a large number of hash collisions, slowing (or probably stopping) the server with an effect similar to a zaplavení paketů mnoha milionů žádostí.[7]

Pomocí klíče neznámého útočníkovi zabrání klíčovaná hash funkce jako SipHash tomuto druhu útoku. I když je možné přidat klíč k nezačleněné hašovací funkci (HMAC je populární technika), SipHash je mnohem efektivnější.

Funkce v rodině SipHash jsou specifikovány jako SipHash-C-d, kde C je počet kol na blok zpráv a d je počet finalizačních kol. Doporučené parametry jsou SipHash-2-4 pro nejlepší výkon a SipHash-4-8 pro konzervativní zabezpečení.

The referenční implementace byl propuštěn jako software pro veřejné domény pod CC0.[6]

Používání

SipHash se používá v hash tabulka implementace různého softwaru:[8]

Implementace

Viz také

Reference

  1. ^ Dobraunig, Christoph; Mendel, Florian; Schläffer, Martin (29. listopadu 2014). Diferenciální kryptoanalýza SipHash. Mezinárodní workshop o vybraných oblastech v kryptografii. Přednášky z informatiky. 8781. str. 165–182. doi:10.1007/978-3-319-13051-4_10. ISBN  978-3-319-13050-7. Citováno 28. února 2018.
  2. ^ A b Jean-Philippe Aumasson & Daniel J. Bernstein (2012-09-18). „SipHash: rychlý PRF s krátkým vstupem“.
  3. ^ Lennon, Mike (2011-12-28). „Zranitelnost tabulky hash umožňuje útoky DDoS v širokém měřítku“. SecurityWeek.
  4. ^ Takže vyhrál; Narayanan, Ashok; Oran, David; Stapp, Mark (2013). Pojmenovaná datová síť na routeru: předávání rychlostí 20 Gb / s a ​​dále. Sborník konferencí ACM SIGCOMM 2013 o SIGCOMM. str. 495. doi:10.1145/2486001.2491699. ISBN  9781450320566. S2CID  1457918. Citováno 28. února 2018. Nedávno navržený nástroj SipHash [1] nabízí dobrou rovnováhu, protože poskytuje odolnost proti kolizím a srovnatelný výkon jako hash bez kryptoměny
  5. ^ Aumasson, Jean-Philippe; Bernstein, Daniel J.; Boßlet, Martin (08.11.2012). Hash-flooding DoS reloaded: útoky a obrana (PDF). Fórum zabezpečení aplikací - Západní Švýcarsko 2012.
  6. ^ A b „SipHash: rychlý PRF s krátkým vstupem“. 2016-08-01. Citováno 2017-01-21. Duševní vlastnictví: Nejsme si vědomi žádných patentů nebo patentových přihlášek týkajících se SipHash a neplánujeme žádat o žádné. Referenční kód SipHash je vydán pod licencí CC0, licencí podobnou veřejné doméně.
  7. ^ Crosby, Scott A .; Wallach, Dan S. (06.06.2003). Denial of Service via Algorithmic Complexity Attacks. Usenix Security Symposium. Washington DC.
  8. ^ Jean-Philippe Aumasson; Daniel J. Bernstein (01.08.2016). „SipHash: rychlý PRF s krátkým vstupem, uživatelé“. Citováno 2017-01-21.
  9. ^ „Zabezpečení Perl - útoky na algoritmickou složitost“. 2016-05-16. Citováno 2017-01-21.
  10. ^ Christian Heimes (2013-09-27). „PEP 456 - bezpečný a vyměnitelný hash algoritmus“. Citováno 2017-01-21.
  11. ^ „Implementujte SipHash, použijte jako naši hashovací funkci s 64bitovými hashvals“. 2018-07-16. Citováno 2018-07-16.
  12. ^ Graydon Hoare (2012-07-24). "Přidat core :: hash obsahující implementaci SipHash-2-4. Re: # 1616 a # 859". Citováno 2017-01-21.
  13. ^ Lennart Poettering (2013-12-22). „shared: switch our hash table implementation over to SipHash“. Citováno 2017-01-21.
  14. ^ "Kompaktní blokové relé". GitHub. Citováno 2018-09-27.
  15. ^ bslh_siphashalgorithm.h

externí odkazy