Panama (hashovací funkce)

Panama [1] je kryptografické primitivum, které lze použít buď jako kryptografickou hashovací funkci, nebo jako proudovou šifru. Byl vyvinut v roce 1998 Joan Dymen a Craig Klep pro zlepšení efektivity softwaru pro 32bitové architektury. Je to jeden z předchůdců Keccakova hashovacího algoritmu , který se stal vítězem soutěže kryptografických primitiv od amerického Národního institutu pro standardy a technologie [2] . Hodně se spoléhá na streamovací hash modul StepRightUp. [3]

Funkce

Podle vývojářů měla „Panama“ v době vývoje vysokou úroveň zabezpečení, ale toho bylo dosaženo za cenu obrovské výpočetní zátěže. Proto, jak se ukázalo, „Panama“ jako hashovací funkce se ukázala být pro hašování zpráv méně vhodná než její rivalové. Pokud mluvíme o „Panamě“ jako o proudové šifře, pak se dlouhá inicializační procedura ukázala jako charakteristický rys jejího použití. Proto je při jeho použití v úlohách vyžadujících vysoké rychlosti nutné zajistit všechny podmínky, které budou směřovat ke snížení počtu desynchronizací. [čtyři]

Předpokládalo se, že „Panama“ bude používána při šifrování nebo dešifrování videa pro přístup k některým aplikacím, zejména k „placené televizi“. [5] Logika vývojářů byla taková, že set-top boxy a digitální televize budou používat vysokorychlostní procesory a Panama nebude tyto procesory při dešifrování příliš zatěžovat.

Struktura

„Panama“ je založena na konečném automatu, který se skládá ze dvou velkých bloků: 544 stavových bitů a 8192-bitové vyrovnávací paměti, pracující na principu zpětnovazebního posuvného registru . Zpětná vazba zajišťuje, že vstupní bity procházejí několika iteracemi po vstupu, což zase zajišťuje bitovou difúzi. Musím říci, že podobný buffer je použit ve funkci SHA komprese. [6] Pracovní objekt Panama je 32bitové slovo a stav se skládá ze 17 takových slov, přičemž vyrovnávací paměť má 32 buněk, z nichž každá obsahuje 8 takových slov. [7]

Operace

Panama může aktualizovat vyrovnávací paměť a stavy iterací. A pro iterační funkci jsou implementovány tři režimy: "Reset", "Push" a "Pull". V režimu "Push" stroj přijímá nějaký vstup, ale nic nevydává. V režimu "Pull" se naopak výstupní data tvoří, ale nic se nebere jako vstupní. "Prázdná iterace Pull" také znamená, že výstup z této iterace je zahozen. V režimu "Reset" se stav a vyrovnávací paměť vynulují. [osm]

Změna stavu je charakterizována vysokou difuzí a distribuovanou nelinearitou. [9] To znamená, že k dosažení dobrého rozptylu stačí malý počet iterací. To se provádí pomocí 4 bloků, z nichž každý řeší svůj vlastní úkol.

První řeší problém nelinearity.
Druhý poskytuje bitovou disperzi.
Třetí vytváří bitovou difúzi.
Čtvrtý představuje vyrovnávací paměť a vstupní data. [deset]

Pokud považujeme „Panamu“ za hashovací funkci, pak algoritmus pro její fungování je následující. Zpočátku hašovací funkce přijímá všechny bloky zpráv. Poté se provede několik dalších "Push" iterací, což umožňuje, aby byly poslední přijaté bloky zpráv rozptýleny uvnitř vyrovnávací paměti a stavu. Poté se provede poslední iterace „Pull“, která vám umožní získat výsledek hash. Schéma šifrování streamování je inicializováno následovně: nejprve projdou dvě iterace "Push", aby se získal klíč a parametr diverzifikace. Poté dojde k řadě iterací "Pull", aby se klíč a parametr rozptýlily uvnitř vyrovnávací paměti a stavů. Tím je inicializace dokončena a Panama je připravena vytvořit bity výstupní sekvence provedením iterací „Pull“. [3]

Jak to funguje

Stav můžete označit jako a 17 slov definujících stavy lze označit jako . Vyrovnávací paměť je označena jako , -th její buňky - as a jedno ze slov ležících uvnitř této buňky - as . Zpočátku jsou stav i vyrovnávací paměť naplněny pouze nulami. V režimu "Push" přijímá "Panama" 8bitové slovo jako vstup, v režimu "Pull" se vytváří 8bitové slovo jako výstup. [7] $A$ $a0...a16$ $B$ $j$ ${\displaystyle b^{j))$ ${\displaystyle b_{i}^{j))$

Pokud označíme funkci, která aktualizuje vyrovnávací paměť, jako , pak, pokud to přijmeme , můžeme získat následující pravidla pro aktualizaci vyrovnávací paměti: $\lambda$ $d=\lambda (b)$

{\displaystyle d^{j}=b^{j-1))

v ,

j\notin {0...25}

d^{0}=b^{31}\oplus q

{\displaystyle d_{i}^{25}=b_{i}^{24}\oplus b_{i+2mod8}^{31))

pro

0<i<8

kde v režimu "Push" je vstupní blok a v režimu "Pull" je součástí stavu , tj. 8 jeho komponent, definovaných jako $q$ $p$ $A$

q_{i}=a_{i+1}

pro

0<i<8

Stav se aktualizuje podle následujícího pravidla , které je superpozicí 4 různých transformací: $\rho$

\rho ={\sigma }+\theta +\pi +\gamma

kde je inverzní lineární transformace, je opět inverzní lineární transformace, je kombinací rotace bitů slova a míchání pozice slova a transformace je bitové přidání vyrovnávací paměti a vstupního slova. $\theta$ $\gamma$ $\pi$ $\sigma$

V tomto případě určí součet operací, kde se jako první provede ta vpravo. $+$

Nyní můžeme zvážit každou z těchto operací. je definován takto: $\theta$

{\displaystyle c=\theta (a)\Šipka doleva c_{i}=a_{i}\oplus a_{i+1}\oplus a_{i+4))

pro ,

i\in {0...17}

kde všechny indexy jsou brány modulo . Všimněte si, že vratnost této transformace vyplývá ze skutečnosti, že je coprime s . $17$ ${\displaystyle 1\oplus x\oplus x^{4))$ $1\oplus x^{17}$

$\gamma$ lze definovat jako:

c=\gamma (a)\Leftrightarrow c_{i}=a_{i}\oplus (a_{i+1}NEBO\neg a_{i+2})

pro ,

i\in {0...17}

kde všechny indexy jsou brány modulo . $17$

Pokud se pro převod určí, že existuje posun v pozicích od nejméně významného bitu k nejvýznamnějšímu, pak: $\pi$ $t_k$ $k$

c=\pi (a)\Leftrightarrow c_{i}=t_{k}(a_{j})

a , a $j=7i{}{\pmod {17}}$ $k=i(i+1)/2{\pmod {32))$

Pokud pro transformaci bude provedena, že , pak $\sigma$ $c=\sigma (a)$

{\displaystyle c_{0}=a_{0}\oplus 00000001_{hex))

{\displaystyle c_{i+1}=a_{i+1}\oplus l_{i))

pro ,

0\leqslant i<8

c_{i+9}=a_{i+9}\oplus b_{i}^{16}

pro

0\leqslant i<8

V režimu "Push" je vstupní zpráva a v režimu "Pull" - . $l$ $p$ ${\displaystyle l=b^{4))$

Výstupní slovo v režimu "Pull" je definováno následovně: $z$

z_{i}=a_{i+9}

0\leqslant i<8

. [jedenáct]

"Panama" jako hashovací funkce

"Panama" jako hashovací funkce mapuje výsledek hash 256 bitů na zprávu libovolné délky. [11] V tomto případě hašování probíhá ve 2 fázích $M$

$M$ se přidáním jedniček převede na řetězec s délkou, která je násobkem 256. $M'$
Odpovídající řetězec je načten do "Panamy". $M'$

Lze jej označit jako sekvenci vstupních bloků . Poté se v nulovém okamžiku vygeneruje režim Reset a během cyklů se načtou vstupní bloky. Poté se provede 32 prázdných iterací "Pull". A pak při 33. iteraci "Pull" se vrátí výsledek hash . $M'$ $PROTI$ $p$ $PROTI$ $h$

Hlavním úkolem vývoje panamské hašovací funkce bylo najít „hermetickou“ hašovací funkci [11] , tedy funkci, pro kterou (pokud se hašovací výsledek skládá z bitů): $n$

pro problém hledání kolize je očekávaná složitost $2^{{n{/2}}$
pro problém výpočtu obrazu je očekávaná složitost $2^{n}$
pro úlohu výpočtu druhého obrázku je očekávaná složitost rovna $2^{n}$

Kromě toho není možné detekovat systematické korelace mezi jakoukoli lineární kombinací vstupních bitů a jakoukoli lineární kombinací výsledných bitů hash. [jedenáct]

Hledání kolizí

Tato hashovací funkce byla dvakrát úspěšně napadena. Již v roce 2001 se ukázalo, že tato hashovací funkce není kryptograficky bezpečná, protože byly nalezeny kolize operací. Joan Dymen navíc ukázal, že je možné najít kolize již pro operace a pro splnění parametrů spolehlivosti je nutné, aby kolize byly lokalizovány alespoň pro operace. [12] $2^{82}$ $2^6$ $2^{128}$

Poznámky

↑ Rychlé hašování a šifrování streamu s Panamou od Joan Daemen, Craig Clapp
↑ NIST vybírá vítěze soutěže Secure Hash Algorithm (SHA-3) . Datum přístupu: 5. listopadu 2016. Archivováno z originálu 5. října 2012. (neurčitý)
↑ 1 2 J. Daemen, "Strategie návrhu šifrovacích a hashovacích funkcí založené na lineární a diferenciální kryptoanalýze"
↑ Rychlé hašování a šifrování streamu s Panamou“ Joan Daemen, Craig Clapp
↑ Archivovaná kopie (odkaz není dostupný) . Získáno 16. prosince 2016. Archivováno z originálu 15. srpna 2011. (neurčitý)
↑ SHA1 verze 1.0 . Získáno 16. prosince 2016. Archivováno z originálu 14. května 2017. (neurčitý)
↑ 12 Panama . _ Získáno 4. listopadu 2016. Archivováno z originálu 26. prosince 2016. (neurčitý)
↑ Kryptografická funkce Panama | Dr Dobb's (nedostupný odkaz) . Datum přístupu: 4. listopadu 2016. Archivováno z originálu 23. února 2016. (neurčitý)
↑ * „Rychlé hašování a šifrování streamu s Panamou“ od Joan Daemen, Craig Clapp
↑ PANAMA kód | Blog o šifrování . Získáno 5. listopadu 2016. Archivováno z originálu 5. listopadu 2016. (neurčitý)
↑ 1 2 3 4 „Rychlé hašování a šifrování streamu s Panamou“ Joan Daemen, Craig Clapp
↑ Produkce kolize pro Panamu, okamžitě . Získáno 13. listopadu 2016. Archivováno z originálu 10. října 2019. (neurčitý)

Literatura

"Rychlé hašování a šifrování streamu s Panamou" Joan Daemen, Craig Clapp
A. Bosselaers, R. Govaerts, J. Vandewalle, "Fast Hashing on the Pentium"
J. Daemen, "Strategie návrhu šifrovacích a hashovacích funkcí založené na lineární a diferenciální kryptoanalýze"
CSK Clapp „Optimalizace rychlé streamovací šifry pro VLIW, SIMD a superskalární procesory“
Asoskov A. V., Ivanov M. A., Mirsky A. A., Ruzin A. V., Slanin A. V., Tyutvin A. N. "Streamové šifry".

Odkazy

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA