Shabal - Shabal

Shabal je kryptografická hashovací funkce předložený francouzským výzkumným projektem Saphir Mezinárodní soutěž NIST o hash funkce.

Saphir partneři

Výzkumní partneři společnosti Saphir (s výjimkou LIENS) zahájili koncepci Shabala a později se k nim přidali partneři výzkumného projektu Saphir2, kteří aktivně přispěli k finálnímu designu Shabala. Saphir (Zabezpečení a analýza hashových primitiv) je projekt ANH financovaný z hash funkcí. Společnost Saphir začala v březnu 2006 po dobu tří let a spojila pět partnerů: Cryptolog International, DCSSI, France Telecom (vedoucí), Gemalto a LIENS. Partneři Saphir2 pocházejí z průmyslu i akademické obce; k projektu se kromě partnerů společnosti Saphir přidali 4 noví partneři: EADS SN, INRIA, Sagem Sécurité a UVSQ.[1]

Dějiny

Shabal byl přihlášením do soutěže o hashovací funkci NIST, kde přešel do druhého kola, ale do posledního kola se nepřihlásil. Shabal nebyl vybrán jako finalista hlavně kvůli bezpečnostním obavám. Přestože nebyla ohrožena bezpečnost celého hashovacího algoritmu, objevení náhodných vlastností s nízkou časovou složitostí vyvolalo u kryptografů NIST obavy z možnosti silnějších útoků v budoucnosti.[2]

Název algoritmu byl zvolen jako pocta Sébastien Chabal.[1]

Popis

Shabal používá provozní režim, který lze považovat za variantu hash konstrukce Merkle – Damgård se širokým potrubím. Vnitřní stav Shabala se skládá ze tří částí, označovaných jako A, B a C. Klíčovaná permutace Shabalových aktualizací A a B pomocí nelineárních posuvných registrů zpětné vazby, které spolu interagují. Hlavní smyčka permutace využívá modulární násobení třemi a pěti, modulární sčítání, XOR, doplňování a operace AND.

Provozní režim funkce Shabal

Režim řetězení Shabala funguje následovně: (A, B) ← PM, C

(A, B, C) ← (A, C - M, B),

(A ⊕ W, B + M),

kde M je blok zpráv a W je počítadlo. Po zpracování všech bloků zpráv se použijí tři kola finalizace, ve kterých jsou blok zpráv a hodnoty čítače pevné. Pro Shabala jsou definovány dva laditelné parametry (p, r), kde p je počet smyček provedených v rámci klíčové permutace a r je velikost A. Výchozí hodnota (p, r) je (3, 12). Navíc by p a r měly vyhovovat 16p ≡ 0 mod r. Stejná interní funkce se používá pro všechny výstupní velikosti Shabala.[2]

Výstupní velikosti Shabala

Výstupní velikosti Shabala založené na délce souhrnu jsou:

  • Shabal-192
  • Shabal-224
  • Shabal-256
  • Shabal-384
  • Shabal-512[1]

Výstupy Šabala

Příklad shabalových hashů:

  • Shabal-192: CB6E700F CE4DCF97 D2BBBF00 0C5364FB B40C8732 0D733948
  • Shabal-224: 14A6DD99 E8D207F9 F7187681 326F6930 8BCAAE00 25F4855F 3120BA43
  • Shabal-256: C0088FDA 9ABA672A 79D0BD56 07AE488E 095E2114 06855B3B 1877A349 A2543F99
  • Shabal-384: 3312DE9D DA850D91 03785C3A C611B112 5D1BCAFC 033755D2 3B8EE05E 15251E4E 636A724F F0A8E584 4AABEAAF 122FC0C4
  • Shabal-512: C6168015 0A3F1FC8 688DD952 8E9E2FED 23EF9578 BCE2A7CB A5D80961 E6C9E632 9701A5A6 F037B89F 20C6C44E DC7931E7 2BB5AB82 B3ADCD32 9CE25056 22[1]

Bezpečnostní

  • Pro permutaci Shabala byly navrženy různé rozlišovací prvky. Pomocí testerů krychle byla s časovou složitostí popsána statistická nenáhodnost Shabalovy klíčové permutace300.[3]
  • Rotační rozlišovač klíčované permutace Shabala pomocí 2171 hovory byly prezentovány. Rozlišovač je založen na pozorování, že většina operací v P zachovává rotační vztahy mezi vstupy. Útok však nelze rozšířit na hashovací algoritmus kvůli nesymetrickému IV, přidání počítadla bloků a existenci finalizačních kol.[4][5]
  • Byl představen další rozlišovač na základě pozorování, že násobení třemi zachovává rozdíl v nejvýznamnějším bitu s pravděpodobností jeden. Pomocí tohoto pozorování autoři představili metodu k nalezení semi-ekvivalentních klíčů pro klíčovanou permutaci. V rámci modelu souvisejícího klíče autoři také představili metodu, která odlišuje P od náhodné permutace pomocí jediného dotazu. Metodu lze zobecnit na libovolný parametr zabezpečení. Autoři také představili metodu k nalezení pseudo-kolizí a pseudosekundových preimages pro variantu Shabala, ve které je počet iterací při finalizaci 24 N (N ≥ 2), místo 36. Tento útok však nefunguje původní Shabal, protože není možné zrušit rozdíly, když je počet iterací 36.[6]
  • U klíčované permutace P byly ukázány některé vlastnosti, které nelze snadno ověřit. Autoři navrhli jednoduchou metodu pro nalezení pevných bodů v P. Vstupy do permutace byly vybrány tak, aby nebyly ovlivněny smyčkami v permutaci. Metoda je nezávislá na počtu slov v A a počtu kol; metoda tedy funguje pro jakoukoli volbu laditelných parametrů zabezpečení. Autoři také ukázali způsob, jak konstruovat mnoho velkých kolizí, kde jediný rozdíl je v klíčovém vstupu.[2]
  • U některých zkreslených výstupních bitů byl pomocí diferenciální analýzy s 2 prezentován rozlišovací znak23 složitost dat.[7]
  • Nízký (45bitový) pseudo-kolizní útok na kompresní funkci Shabal s časovou složitostí 284 byl představen. Preimage útok s 2497 čas a 2400 složitost paměti pro Shabal 512 pomocí parametrů zabezpečení (2, 12).[8]
  • Žádný z rozlišovacích prvků přímo neohrožuje nárokovanou bezpečnost hashovacího algoritmu. Návrháři navíc upravili bezpečnostní důkaz lhostejnosti svého režimu zřetězení tak, aby vyžadoval slabší předpoklady než ideální šifry.[2]

Implementace

Reference

  1. ^ A b C d Bresson, Emmanuel; Clavier, Christophe; Fuhr, Thomas; Icart, Thomas; Misarsky, Jean-Francois; Naya-Plasencia, Maria; Reinhard, Jean-Rene; Thuillet, Celine; Videau, Marion (2008-10-28). „Shabal, příspěvek do soutěže NIST v kryptografickém hašovacím algoritmu“ (PDF): 2–3, 20, 22, 32–35. Citovat deník vyžaduje | deník = (Pomoc)
  2. ^ A b C d Interagency Report NIST 7764 (únor 2011). „Zpráva o stavu druhého kola soutěže SHA-3 v kryptografickém hašovacím algoritmu“ (PDF): 20–21. Citovat deník vyžaduje | deník = (Pomoc)
  3. ^ Aumasson, Jean-Philippe. „O pseudonáhodnosti Shabalovy klíčové permutace“ (PDF). Citováno 14. listopadu 2018. Citovat deník vyžaduje | deník = (Pomoc)
  4. ^ Van Assche, Gilles (24. března 2010). „Rotační rozlišovač Shabalovy permutace a jejího dopadu na bezpečnostní důkazy“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
  5. ^ Aerts, Nieke (srpen 2011). „Kryptoanalýza hašovacích funkcí, zejména uchazeči SHA-3, Shabal a Blake“ (PDF): 56–57. Citovat deník vyžaduje | deník = (Pomoc)
  6. ^ Aumasson, Jean-Philippe; Mashatan, Atefeh; Meier, Willi. „Více o Shabalově permutaci“ (PDF). Citováno 14. listopadu 2018. Citovat deník vyžaduje | deník = (Pomoc)
  7. ^ Novotney, Peter (20. července 2010). „Rozlišovač Shabalovy permutační funkce“ (PDF). Citovat deník vyžaduje | deník = (Pomoc)
  8. ^ Isobe, Takanori; Shirai, Taizo. „Útok Pseudo Collision s nízkou hmotností na Shabala a útok Preimage na Reduced Shabal-512“ (PDF). Citováno 14. listopadu 2018. Citovat deník vyžaduje | deník = (Pomoc)