UMAC

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. června 2021; ověření vyžaduje 1 úpravu .

UMAC ( anglicky  message authentication code based on universal hashing, universal MAC , message authentication code based on universal hashing) je jedním z typů autentizačního kódu zprávy ( MAC ).

Historie

Tento algoritmus byl vybrán společností NESSIE v roce 2003 a na jeho vývoji se podíleli tito lidé: Intel Corp. (USA), University of Nevada (USA), IBM Research Laboratory (USA), Technion ( Izrael ) a University of California Davis (USA). Jeho autory byli John Black, Shai Halevi a Hugo Krawczyk, Ted Krovetz a Phillip Rogaway .

Popis

Rychlá „univerzální“ funkce se používá k hašování příchozí zprávy M do krátkého řetězce. Tento řetězec je pak XORed s pseudonáhodnou hodnotou, což má za následek značku UMAC:

kde K1 a K2 jsou tajné náhodné klíče, které mají příjemce a odesílatel.

To ukazuje, že bezpečnost UMAC závisí na tom, jak odesílatel a příjemce náhodně zvolí tajnou hashovací funkci a pseudonáhodnou sekvenci . V tomto případě hodnota Nonce změní každý takt. Kvůli použití Nonce musí přijímač a vysílač vědět, kdy byla zpráva odeslána a jak byla vygenerována hodnota Nonce. Místo toho můžete použít jakoukoli jinou neopakující se hodnotu jako Nonce, například pořadové číslo zprávy. Toto číslo přitom nemusí být tajné, hlavní je, aby se neopakovalo.

UMAC je navržen tak, aby používal 32bitové, 64bitové, 92bitové a 128bitové značky v závislosti na požadované úrovni zabezpečení. UMAC se obvykle používá ve spojení se šifrovacím algoritmem AES .

Funkce generování klíčů a pseudonáhodná sekvence

Vytváření pseudonáhodných bajtů je nezbytné pro fungování UHASH a při generování značek

Výběr blokové šifry

UMAC pro svou práci používá blokovou šifru , jejíž výběr je určen následujícími konstantami:

To využívá funkci

Příklad: pokud je AES použit s 16bajtovým klíčem, pak BLOCLEN bude 16 (protože AES pracuje s 16bajtovými bloky).

KDF - Funkce generování klíčů

Tato funkce generuje sekvenci pseudonáhodných bajtů používaných pro klíčové hašovací funkce.

Vchod:

Výstup:

PDF: funkce generování pseudonáhodných čísel

Tato funkce vezme klíč a daný čas a vrátí pseudonáhodné číslo, které se má použít v generovací značce. Pomocí této funkce lze získat čísla o délce 4, 8, 12 nebo 16 bajtů.

Vchod:

Výstup:

Generování značek UMAC

Tagy UMAC jsou generovány pomocí funkce UHASH pomocí hodnoty Nonce a dříve získaného řetězce (viz Popis). Jejich délka může být 4, 8, 12 nebo 16 bajtů.

Vchod:

Výstup:

Algoritmus výpočtu značky:

HashedMassage = UHASH(K, M, TagLen) Pad = PDF(K, nonce, TagLen) Tag = Pad xor HashedMassage

UMAC-32 UMAC-64 UMAC-96 UMAC-128

Tato označení obsahují ve svém názvu určitou hodnotu délky značky:

Univerzální hashovací funkce (UHASH)

UHASH ( anglicky  Universal hashing ) je univerzální hašovací funkce, jádro algoritmu UMAC. UHASH - funkce funguje ve třech fázích. Nejprve se na vstupní zprávu aplikuje L1-HASH, pak se na tento výsledek aplikuje L2-HASH a nakonec se na výsledek aplikuje L3-HASH. Pokud délka vstupní zprávy není větší než 1024 bitů, pak se L2-HASH nepoužívá. Protože funkce L3-Hash vrací pouze slovo o délce 4 bajtů, pokud je požadováno získat hash o délce větší než 4 bajty, provede se několik iterací tohoto tříúrovňového schématu.

Obecná funkce

Nechť je hašovací funkce vybrána ze třídy hašovacích funkcí H, které mapují zprávy na D, množinu možných vzorů zpráv. Tato třída se nazývá univerzální, pokud pro jakékoli samostatné dvojice zpráv existuje na množině funkcí H/D, funkce, která je mapuje na prvek D. Význam této funkce je, že pokud chce třetí strana nahradit jednu zprávu jiný, ale zároveň se domnívá, že hashovací funkce byla zvolena naprosto náhodně, pak se pravděpodobnost nezjištění substituce přijímající stranou blíží 1/D.

L1-Hash - první krok

L1-Hash rozděluje zprávy na bloky po 1024 bajtech a na každý blok aplikuje hashovací algoritmus nazvaný NH. Výstup algoritmu NH je 128krát menší než vstup.

L2-Hash - Fáze 2

L2-Hash pracuje s výstupem L1-Hash, používá polynomiální algoritmus POLY. Druhá fáze hashování se používá pouze v případě, že délka vstupní zprávy je větší než 16 megabajtů. Použití algoritmu POLY je vyžadováno, aby se zabránilo útokům načasování. Výstupem z algoritmu POLY je 16bajtové číslo.

L3-HASH - třetí fáze

Tato fáze je nutná k získání 4bajtové hodnoty z výstupních 16 bajtů algoritmu L2-Hash.

Bezpečnostní problémy

Odolnost vůči kryptoanalýze

Síla UMAC závisí na jeho hlavních funkcích: funkci odvození klíče (KDF) a funkci generování pseudonáhodné sekvence (PDF). Proto jsou obě funkce implementovány pomocí blokového šifrování, obvykle Advanced Encryption Standard (AES). UMAC však umožňuje použití jiných blokových šifer. Hlavní výhodou algoritmu UMAC a funkce UHASH je, že jejich síla závisí pouze na matematických vlastnostech daného algoritmu a funkce. Proto kryptoanalýza neovlivňuje zabezpečení funkce UHASH.

Délka pseudonáhodných čísel a možnost substituce

Algoritmus MAC se používá k autentizaci zpráv mezi dvěma stranami, které znají sdílený tajný klíč K. Autentizační značky se pro zprávu vypočítávají pomocí klíče K a v případě UMAC je klíčem čas. Hacknutí algoritmu MAC znamená, že útočník je schopen generovat zprávy sám, aniž by znal klíč. Wegman-Carterova teorie a analýza UMAC ukazují, že pokud je použit algoritmus UMAC s náhodnými klíči a počáteční hodnotou Nonce, pak pravděpodobnost, že útočník zprávu prolomí, je: , , , , pokud výstupní značky délky 32, 64, 96 , 128 se používají, resp. Pokud útočník provede N pokusů, pak se pravděpodobnost hacknutí zvyšuje úměrně počtu pokusů, tedy Nkrát. S dodatečným použitím algoritmu AES se výrazně snižuje pravděpodobnost hackingu.

Bezpečnost používání Nonce

UMAC používá aktuální čas v rozsahu 1 až BLOCKLEN bajtů. V tomto případě musí mít všechny hodnoty Nonce během relace stejnou délku. Pro nejlepší zabezpečení by se při použití stejného klíče relace neměla opakovat žádná hodnota Nonce.

Pokud je použit duplexní přenosový kanál, mohou být pro každý směr použity různé klíče. Při použití klávesy v obou směrech je velmi důležité, aby se neopakovala hodnota Nonce, to lze provést pomocí sudých kláves v jednom směru a lichých kláves ve druhém směru. V tomto případě není třeba aktuální hodnotu Noce tajit.

Hodnotu Nonce lze vytvořit a předat následujícími způsoby:

  1. Aktuální hodnota Noce je 8bajtové číslo bez znaménka, které se na začátku relace vynuluje a po každém odeslaném tagu se zvýší o jedničku. V tomto případě je tento čítač přenášen spolu se zprávou. Pokud je během relace odesláno více než 2 ^ 64 zpráv, dojde k přerušení .
  2. Aktuální hodnota Nonce je BLOCKLEN-bajtové číslo bez znaménka, které je na začátku relace nastaveno na nulu a po každém odeslaném tagu se zvyšuje o jedničku. V tomto případě se počítadlo výslovně nepřenáší mezi odesílatelem a příjemcem a každý z nich si aktuální hodnotu počítá sám.
  3. Aktuální hodnota Noce je pseudonáhodná hodnota BLOCKLEN bajtů. Pak je ale důležitá synchronizace pseudonáhodných sekvencí u odesílatele a příjemce.

Opakované útoky

Replay útoky jsou akce útočníka zaměřené na opakování zprávy, náhodného čísla a ověření značky. V UMAC tento útok selže, protože každá hodnota Nonce je použita právě jednou.

Kontrola předpony značky.

Povaha UMAC umožňuje implementovat kontrolu prefixu tagu, například přijímač může zkontrolovat pouze 32bitový prefix z 64bitového tagu. To se používá pro optimalizaci, pokud je výpočetní zatížení kontroly vysoké. V tomto případě má přijímač možnost odmítnout celou značku, pokud je 32bitová předpona nesprávná. Tento algoritmus snižuje zabezpečení relace.

Literatura