Kryptoanalýza kvázigrupovej hašovacej funkcie

01. September, 2010, Autor článku: Slaminková Ivana, Informačné technológie, Študentské práce
Ročník 3, číslo 9 Pridať príspevok

Táto práca je zameraná na kryptoanalýzu hašovacej funkcie založenej na kvázigrupách, ktorá bola prezentovaná v [2], [3]. Článok nadväzuje na prácu [6], ktorá sa zaoberá analýzou použítia kvázigrupy modulárneho odčítania. Skúmanou oblasťou je použitie kvázigrupy izotonej s kvázigrupou modulárneho odčítania. V práci sa zaoberáme konštrukciou hašovacej funkcie a prezentujeme samotný útok.

1. Úvod

Hašovacie funkcie sú v informatike veľmi dobre známe a v modernej kryptografii zohrávajú dôležitú rolu. Ide o funkcie, ktoré transformujú vstupný raťazerc ľubovoľnej dĺžky na výstupný reťazec fixnej dĺžky, ktorému hovoríme digitálny odtlačok.

Definícia 1 [5] Nech $\{0, \, 1\}^*$ je konečná množina slov nad abecedou $\{0, \, 1\}$ . Jednocestná hašovacia funkcia (angl. “One-Way Hash Function OWHF”) je funkcia $h \, : \, \{0, \, 1\}^* \rightarrow \{0, \, 1\}^m$ , ktorá spĺňa nasledujúce podmienky:

Argument $x$ môže byť ľubovoľnej dĺžky a výsledný odtlačok $h(x)$ má fixnú dĺžku $m$ bitov.
Dnes je $latex m \geq 160, \ldots, 256.

Hašovacia funkcia je jednocestá, t.j. pre daný digitálny odtlačok $y$ je “tažké” (v reálnom čase výpočtovo nerealizovateľné) nájsť takú správu $x$ , že $h(x)=y$ (n8jdenie vzoru; angl. “preimage resistance”) a k danej správe $x$ je “ťažké” nájsť takú správu $x'$ , že $x' \neq x$ a $h(x') = h(x)$ (nájdenie druhého vzoru; angl. “second preimage resistance”).

Podľa počtu vstupov, delíme hašovacie funkcie na nekľúčové a kľúčové. Hašovacie funkcie, ktorých vstupom je správa, ktorej odtlačok chceme získať, nazývame nekľúčové alebo MDCs (Manipulation Detection Codes). Ak je vstupom správa a tajný kľúč, ide o kľúčové hašovacie funkcie, ktorým taktiež hovoríme MACs (Message Autentication Codes).

Bezpečná hašovacia funkcia vytvára jedinečný vzťah medzi vstupom a digitálnym odtlačkom. Je však zrejmé, že z viacerých rôznych vstupov môžeme dostať ten istý digitálny odtlačok, nakoľko ide o zobrazenie z väčšej množiny do menšej. Práve preto musí byť zaručené, aby boli tieto vstupy ťažko identifikovateľné, teda aby bolo zložité nájsť kolíziu.

Definícia 2 [5] Hašovacia funkcia odlná voči kolíziám (angl. “Collision Resistant Hsh Function CRHF”) ej taká hašovacia funkcia $h \, : \, \{0, \, 1\}^* \rightarrow \{0, \, 1\}^m$ , pre ktorú je “ťažké” nájsť také dve rôzne správy $x, \, x'$ že $h(x) = h(x')$ (angl. “collision resistance”).

V kryptografii sa v posledných rokoch objavilo niekoľko kryptosystémov založených na kvázigrupách, aj keď takéto riešenie nie je príliš bežné. Ako je však ukázané v [4], práve použitie kvázigrúp v dizajne S-boxov, môže predstavovať nové riešenia v návrhu blokových šifier.

Kvázigrupy môžeme použiť aj pri návrhu hašovacích funkcií, ako vidíme v [2], [3].

Definícia 3 [1] Štruktúra $(Q,*), \, Q = q_1, q_2, \ldots, q_n$ , $\parallel Q \parallel = n$ sa nazýva konečná kvázigurpa rádu $n$ ak platí, že pre ktorékoľvek dva dané prvky $a, b \in Q$ , rovnosť $a * b = b$ a $y * a = b$ má práve jedno riešenie. Potom Caleyho tabuľka konečnej kvázigrupy rádu $n$ je latinský štvorec, t.j. pole $n \times n$ s vlastnosťou, že každý riadok a každý stĺpec obsahuje permutáciu prvkov z množiny $Q$ .

Definícia 4 [1] Nech ( $Q, ^. \,$ ) a ( $H, *$ ) sú dve konecné kvázigrupy. Usporiadaná trojica ( $\theta, \varphi, \psi$ ) bijektívnych zobrazení $\theta, \varphi, \psi$ množiny $G$ na množinu $H$ sa nazýva izotópia ( $G, ^. \,$ ) na ( $H, *$ ), ak $\theta (x) * \varphi (y) = \psi (x \, ^. \, y )$ , pre všetky $x, y \in G$ . Kvázigrupy ( $G, ^. \,$ ) a ( $H,*$ ) potom nazývame izotopné.

2. Konštrukcia

Konštrukcia [2], [3] Nech ( $Q, \odot$ ) je konecná kvázigrupa. Nech správa, ktorej odtlacok chceme získat, je postupnost prvkov ( $m_1, m_2, \ldots , m_k$ ) z kvázigrupy $Q$ . Nech $Q ^*$ je množina všetkých konecných slov nad $Q$ . Hašovacia funkcia $H_a \, : \, Q \times Q^* \rightarrow W, \, a \in Q$ je daná vztahom:

$H_a (m_1, m_2, \ldots, m_k) = (( \ldots ( a \odot m_1) \odot m_2 ) \odot \ldots ) \odot m_{k-1} \odot m_k$ , kde $m_i \in Q, 1 \leq i \leq k$ .

Príklad 1 Nech $Q = \{ 0,1,2,3, \}$ a nech operácia $\odot$ na $Q$ je definovaná tabulkou 1. Nech $a = 1$ a nech správa, ktorej odtlacok chceme vypocítat, je $(1,0,3,1)$ . Potom je odtlacok vypocítaný nasledovne:

$H_1 (1,0,3,1) = ((( 1 \odot 1) \odot 0) \odot 3) \odot 1 = 2$ .

Tabulka 1: Caleyho tabulka operácie $\odot$ definovanej na $Q$ .

$\odot$	0	1	2	3
0	0	2	1	3
1	2	3	0	1
2	1	0	3	2
3	3	1	2	0

Takéto hašovanie nám so sebou prináša obrovské požiadavky na pamät. K získaniu odtlacku správy, by sme museli uložit tabulku o velkosti $n^2$ prvkov, pričom za dnes bezpečnú dlžku odtlačku sa považuje 160 – 256 bitov. Túto pamätovú nárocnost rieši špeciálna kvázigrupa, kvázigrupa modulárneho odcítania. Operácia $\otimes$ definovaná na $Q$ je daná predpisom:

Tabulka 2: Tabulka kvázigrupy modulárneho odcítania pre $n = 4$ .

$\otimes$	0	1	2	3
0	0	3	2	1
1	1	0	3	2
2	2	1	0	3
3	3	2	1	0

Tým, že použijeme jednoducho vypocítatelnú operáciu $\otimes$ , môžeme používat kvázigrupy s velkým poctom prvkov. V [6] sa podarilo ukázat, že hašovacia funkcia založená na kvázigrupe modulárneho odcítania nie je spolahlivým riešením. Kvôli zvýšeniu bezpecnosti sa preto do návrhu hašovacej funkcie zavádzajú izotopné kvázigrupy.

Definícia 5 Nech ( $Q, \otimes$ ), $\parallel Q \parallel =n$ , je kvázigrupa modulárneho odcítania. Nech $\theta, \varphi$ a $\psi ^{-1}$ sú známe permutácie. Nech ( $Q, ^. \,$ ) izotopná s kvázigrupou ( $Q, \otimes$ ). Kvázigrupová operácia v ( $Q, ^. \,$ ) môže byt zapísaná ako:

$a \, ^. \, b = \psi ^{-1} (\theta(a) + (n - \varphi (b)) mod \, n ), \quad n = \parallel Q \parallel$ .

Generovanie permutácií sa realizuje tak, že sa postupnost $n$ prvkov rozdelí na niekolko castí a tie sa rotujú v rôznych smeroch. V [2] a [3] sú prezentované metódy $P1(), \, P2(), \, P3()$ , ktoré generujú požadované permutácie $\theta, \varphi$ a $\psi ^{-1}$ .

Metóda $P1()$ realizuje výpocet permutácie $\theta$ , co znamená $\theta(x) = P1(x)$ . Podobným spôsobom sú realizované aj dalšie dve permutácie $P2()$ a $P3()$ . Metódy sú uvedené v jazyku C++.

Metóda na výpocet permutácie $\theta$

ZZ Quasigroup::P1(ZZ x) {


ZZ Dim2 = m_Dim / 2;

if(x < Dim2*2)
{
if (x & 1)
(x & 1)
{
x = 2*((x/2 + 1) % Dim2) + 1;
}
else
{
x = 2*((x/2 + Dim2 - 1) % Dim2);
}
}
return x;

}

Metóda na výpocet permutácie $\varphi$

ZZ Quasigroup::P2(ZZ x) {


ZZ Dim3 = m_Dim / 3;

bool Shift = m_Dim % 2 >= 1;

if (x < Dim3*3)
{
switch (x % 3)
{
case 0:
x = 3 * ((x/3 + Dim3/3) % Dim3);
break;
case 1:
x = (3 * (Dim3 - x/3)) + 1;
break;
case 2:
x = (3 * ((x/3 + Dim3 - 1)% Dim3))+ 2;
break;
}
}

else

{
if (x % 3 == 2)

{

if (x == (Dim3 * 3 + 1))

{

x = (Dim3 * 3) + 2;

}

else

{

x = (Dim3 * 3) + 1;

}

}

} if (Shift) { x = (x + Dim3) % Dim3; } return x; }

Metóda na výpocet permutácie $\psi ^{-1}$

ZZ QuasiGroup::P3(ZZ x) { ZZ Dim2 = m_Dim / 2; x = (x + Dim2 - 1) % m_Dim; return x; }

2.1 Príklad hašovania

Príklad 2 Nech ( $Q, \otimes$ ), $\parallel Q \parallel = 4$ , je kvázigrupa modulárneho odcítania s Caleyho tabulkou danou v tabulke 1. Nech $\theta = [1,3,2,0]$ , $\varphi = [3,0,1,2]$ a $\psi ^{-1} = [3,2,0,1]$ . Caleyho tabulka kvázigrupy ( $Q, \, \cdot$ ) izotopnej s kvázigrupou ( $Q, \otimes$ ) je zobrazená v tabulke 3.

Tabulka 3: Caleyho tabulka kvázigrupy ( $Q, \, \cdot$ ) .

$\cdot$	0	1	2	3
0	0	2	3	1
1	3	1	0	2
2	1	0	2	3
3	2	3	1	0

Nech $a = 1$ a nech správa, ktorej odtlacok chceme získat je $(1,0,3,1)$ . Potom je odtlačok vypočítaný nasledovne:

$H_1 (1,0,3,1) = ((( 1 \cdot 1) \cdot 0) \cdot 1 =$ $2$

$1 \cdot 1 = \psi ^{-1} (\theta (1) + (4 - \varphi (1)) mod \, 4) =$
$\psi ^{-1} (3 + (4-0) mod \, 4) = \psi ^{-1} (3) =$ $1$

$1 \cdot 0 = \psi ^{-1} (\theta (1) + (4 - \varphi (0)) mod \, 4 ) =$
$\psi ^{-1} (3+(4-3) mod \, 4) = \psi ^{-1} (0) =$ $3$

$3 \cdot 3 = \psi ^{-1} (\theta (3) + (4 - \varphi (3)) mod \, 4) =$
$\psi ^{-1} (0 + (4-2) mod \, 4) = \psi ^{-1} (2) =$ $0$

$0 \cdot 1 = \psi ^{-1} (\theta (0) + (4 - \varphi(1)) mod \, 4) =$
$\psi^{-1} (1 + (4 - 0) mod \, 4) = \psi ^{-1} (1) =$ $2$

3. Útok na hašovaciu funkciu

Vlastnosť, ktorú musí nevyhnutne spĺňať každá hašovacia funkcia, je odolnosť voči kolízii. Náš útok preto zameriame na overenie tejto vlastnosti. Pokúsime sa nájst dve správy s identickým odtlačkom.

Nech $a \in Q, \, a$ je známym parametrom hašovacej funkcie a majme správu $(m_1, m_2, \ldots, m_k)$ , $\, m \in Q$ , $\leq i \leq k$ . Označme digitálny odtlačok ako $H_a (m_1,m_2, \ldots, m_k) = (\ldots (( a \cdot m_1) \cdot m_2) \cdot \ldots) \cdot m_k = d$ [6].

Falošnú správu môžeme vytvoriť pridaním predpony alebo prípony k pôvodnej správe alebo môžeme vytvoriť äplne novú správu, nezávislú na pôvodnej.

3.1 Pridanie predpony / prípony

Pridaním predpony môže falošná správa vyzerať ako $(p_1, p_2, \ldots, p_l, m_1, m_2, \ldots, m_k ),$ $p_1 \in Q$ , $1 \leq i \leq l$ [6]. Na základe toho musí platiť, že $(\ldots (( a \cdot p_1) \cdot p_2 ) \cdot \ldots ) \cdot p_l = a$ . Falošnú správu môžeme taktiež vytvoriť pridaním prípony a môže vyzerať ako $(m_1, m_2, \ldots, m_k, s_1, s_2, \ldots, s_t)$ , $s_i \in Q$ , $1 \leq i \leq t$ [6]. Na základe toho musí platiť, že $(\ldots (( d \cdot s_1) \cdot s_2) \cdot \ldots ) \cdot s_t = d$ . Môžeme si všimnúť, že všetky prvky predpony, resp. prípony môžeme zvoliť ľubovoľne, s výnimkou jedného (na ľubovoľnom mieste), ktorý je potrebné určiť. Nech $a' = ( \ldots (( a \cdot p_1) \cdot p_2 ) \cdot \ldots )$ a nech $d' = (\ldots (( d \cdot s_1) \cdot s_2 ) \cdot \ldots ).$ Potom potrebujeme nájsť také $p_l$ a $s_t$ , aby platilo $a' \cdot p_l = a, \, d' \cdot s_t = d$ .

3.2 Vytvorenie úplne novej správy

Vytvorme novú správu $(x_1, x_2, \ldots, x_ {\upsilon}),$ $x_i \in Q,$ $1 \leq i \leq \upsilon .$ Prvky $(x_1, x_2, \ldots, x_{\upsilon -1}.$ Našou úlohou je teda nájsť také $x_{\upsilon},$ aby $d' \cdot x_{\upsilon} = d$ ,

$d = ( \psi ^{-1} (\theta (d') + (n - \varphi (x_{\upsilon})) mod \, n )$ ,
$\psi (d) = \theta (d') + (n - \varphi (x_{\upsilon})) mod \, n$ ,
$\varphi (x_{\upsilon}) = \theta (d') + (n - \psi (d)) mod \, n$ ,
$x_{\upsilon} = \varphi ^{-1} (\theta (d') + (n - \psi (d)) mod \, n$

Rovnako vieme chýbajúci prvok odvodiť aj pri pridaní predpony, resp. prípony k pôvodnej správe z podkapitoly 3.1.

$p_l = \varphi ^{-1} (\theta (a') + (n - \psi (a)) mod \, n )$ .
$s_t = \varphi ^{-1} (\theta (d') + (n - \psi (d)) mod \, n )$ .

Ako vidíme, zložitosť nájdenia správneho prvku spočíva v nájdení inverzných permutácií $\varphi ^{-1}$ a $\psi$ , či už vytvoríme úplne novú správu alebo doplníme pôvodnú správu o predponu alebo príponu. Permutáciu $\theta$ invertovať nepotrebujeme. Pre obidva tieto typy vytvorenia novej správy je potom zložitosť útoku rovnaká. Tiež vidíme, že ani známy parameter $a$ takto zvoleného návrhuhašovacej funkcie, nijako neovplyvní zložitosť hľadania kolízie, či už ho poznáme alebo nie.

3.3 Hladanie inverzných permutácií

Je známe, že invertovanie permutácií je vo všeobecnosti náročný problém. Keď sa však podrobnejšie pozrieme na metódy generovania permutícií z kapitoly 2, prichádzame na zaujímavý fakt. Metóda na generovanie permutácie $\varphi$ je navrhnutá tak, že permutáciu nikdy nevygeneruje. Pre ukážku uvádzame niekoľko príkladov v tabuľke 4.

Tabulka 4: Tabulka generovania prvkov $\varphi$ .

$\parallel Q \parallel$	Generované prvky $\varphi$
4	[0, 4, 2, 3]
7	[2, 2, 0, 5, 6, 4, 1]
8	[0, 7, 5, 3, 4, 2, 6, 7]
14	[3, 13, 11, 6, 10, 2, 9, 7, 5, 0, 4, 8, 12, 13]

Z hľadiska definície 4, to predstavuje podstatný problém, keďže podľa nej majú byť $\theta, \varphi$ a $\psi ^{-1}$ jednoznačne permutácie. Nakoľko ale jedna z nich nie je, neplatia ďalšie vlastnosti, ktoré sú základom návrhu tejto hašovacej funkcie.

Príklad 3 Nech $\parallel Q \parallel = 4$ a nech $\theta, \varphi$ a $\psi ^{-1}$ sú vygenerované metódami uvedenými v kapitole 2. Potom je $\theta = [2,3,0,1]$ , $\varphi = [0,4,2,3]$ a $\psi ^{-1} = [1,2,3,0]$ . Tabuľka operácie $\cdot$ na množine $Q$ je zobrazená v tabuľke 5.

Tabulka 5: Tabuľka operácie $\cdot$ na množine $Q$ ..

$\cdot$	0	1	2	3
0	3	3	1	0
1	0	0	2	1
2	1	1	3	2
3	2	2	0	3

Podľa definície 3 musí pre konečnú kvázigrupu platiť, že pre ktorékoľvek dava prvky $a, b \in Q$ , mus9 ma5 rovnosť $a \cdot x = b$ a $y \cdot a = b$ práve jedno riešenie. Zvoľme teda $a = 0$ a $b = 3$ . Po dosadení dostávame

$0 \cdot x = 3$
$y \cdot 0 = 3$ .

Z tabuľky 5 je potom

$x = 0$ alebo $x = 1$ a $y = 0$

Vidíme, že $x$ má dve možné riešenia tejto rovnosti , čím nie je splnená podmienka v definícii 3. Taktiež neplatí, že príslušná tabuľka je latinský štvorec.

Dôsledok 1 $(Q, \cdot)$ nie je konečná kvázigrupa a Caleyho tabuľka ku $(Q, \cdot)$ nie je latinský štvorec.

Čo sa týka teoretického hľadiska, vidíme, že celá konštrukcia návrhu, je na základe takéhoto generovania permutácie $\varphi$ úplne narušená. Hašovať sa ale aj napriek tomuto faktu dá, čo si ukážeme na nasledujúcom príklade.

Príklad 4 Nech $\parallel Q \parallel = 4$ a nech $\theta = [2,3,0,1],$ $\varphi = [0,4,2,3]$ a $\psi ^{-1} = [1,2,3,0]$ sú vygenerované metódami uvedenými v kapitole 2. Tabuľka operácie $\cdot$ na množine $Q$ je zobrazená v tabuľke 5. Nech správa, ktorej odtlačok chceme vypočítať je $(2,1,1,3)$ a nech $a = 0$ . Odtlačok správy vypočítame pomocou tabuľky 5 nasledovne:

$H_0 (2,1,1,3) = ((( 0 \cdot 2) \cdot 1) \cdot 1) \cdot 3 = 3.$

Keďže vieme hašovať, môžeme sa aj v tomto prípade pokúsiť vytvoriť falošnú správu s rovnakým odtlačkom. Už v predchádzajúcich príkladoch sme prišli na to, že zložitosť útoku as odvíja od zložitosťi invertovania permutácie $\psi$ a od zložitosti invertovania $\varphi ^{-1}$ , ktorá však, už ako viem, nie je permutáciou.

Vytvorme teda novú správu, ktorej odtlačok sa bude zhodovať s vyššie vypočítaným $d = 3$ . Nech nová správa je $(0,2,3,x_{\upsilon})$ . Označme $d' = (( 0 \cdot 0) \cdot 2 ) \cdot 3 = 0$ . Platí, že $d' \cdot x_{\upsilon} = d$ , teda $0 \cdot x_{\upsilon} = 3$ .

Vieme, že $x_{\upsilon}$ môžeme vypočítať nasledovne:

$x_{\upsilon} \varphi ^{-1} (\theta (d') + (n - \psi (d)) mod \, n ).$

Po dosadení dostávame

$x_{\upsilon} = \varphi ^{-1} (\theta (0) + (4 - \psi (3)) mod \, 4).$

K určeniu $x_{\upsilon}$ potrebujeme poznať $\varphi ^{-1}$ a $\psi$ . Pozrime sa preto na možnosti invertovania funkcií, ktoré sme uviedli v časti 2.

Metóda na invertovanie permutácie $\psi ^{-1}$

Už na prvý pohľad vidíme, že permutácia $\psi ^{-1}$ sa generuje zložito. Veľmi jednoducho vieme nájsť inverzný algoritmus k pôvodnému. Metóda je uvedená v jazyku C++.

ZZ Quasigroup::invP3(ZZ x) { ZZ Dim2 = m_Dim / 2; x = (x + 1 - Dim2) % m_Dim; return x; }

Metóda na invertovanie permutácie $\varphi$

Algoritmus na generovanie prvkov $\varphi$ už vyzerá o čosi zložitejšie a problém, ktorý tu vzniká, je hlavne ten, že nejde o permutáciu. Problém sa redukuje na invertovanie postupností s párnym počtom prvkov, teda $\parallel Q \parallel = 2k$ , $k \in N$ . Dôvodom je to, že počet prvkov postupnosti (permutácie, vo všeobecnom prípade) vypočítame z dĺžky odtlačku, a to $\parallel Q \parallel = 2^d$ , kde $d$ je dĺžka odtlačku. Nikdy sa teda nestane, aby permutácia mala nepýrny počet prvkov.

Z tabuľky 4 vidíme, že jednoznačne určiť pôvodný prvok k inverznému, môže predstavovať problém, ak by sa prvky opakovali kdekoľvek v danej postupnosti a opakovalo by sa ich rôzne veľa. Algoritmus bol však navrhnutý tak, že nám vygeneruje 3 typy postupností, čo vidíme v nasledujúcej tabuľke 6.

Tabulka 6: Tabulka typov postupností $\varphi$

$\parallel Q \parallel$	Špecifický znak
4, 10, 16, 22, …	1 sa zobrazuje na $n$
6, 12, 18, 24, …	1 sa zobrazuje na $n + 1$
8, 14, 20, 26, …	1 a $n -1$ sa zobrazuje na $n - 1$

Príklady jednotlivých typov môžeme nájsť v tabuľke 4. Ostatné prvky postupnosti $\varphi$ , okrem vyššie spomenutých prvkov 1 a $n - 1$ , sa generujú s jednoznačným určením inverzného prvku. Pri prvom a druhom type postupnosti ho však vieme určiť jednoznačne tiež, je ním 1. Pri treťom type vznikajú dve možnosti chýbajúcich prvkov, no otestovanie dvoch možností, nepredstavuje žiadny problém. Metóda je uvedená v jazyku C++.

ZZ* Quasigroup::invP2(ZZ x) { ZZ * arr = new ZZ[2]; arr[0] = x; arr[1] = to_ZZ(-1); ZZ Dim3 = m_Dim / 3; if(m_Dim % 2 == 0) { if(x < Dim3 * 3) { switch(x % 3) { case 0: arr[0]=3*((x/3 - Dim3/3)% Dim3); break; case 1: arr[0]=3*(Dim3 - (x-1)/3) + 1; break; case 2: arr[0]=3*(((x-2)/3 + 1 - Dim3)% Dim3)+ 2; break; } } else { if(x == m_Dim || x == m_Dim + 1) { arr[0] = 1; return arr; } } if(x == (Dim3 * 3) + 1) { arr[0] = 1; arr[1] = (Dim3 * 3) + 1; } } return arr; }

Metóda na invertovanie permutácie $\theta$

Pre úplnosť uvádzame aj inverznú funkciu k permutácii $\theta$ , o ktorej sme si však povedali, že ju k vytvoreniu falošnej správy invertovať nepotrebujeme. Metóda je uvedená v jazyku C++.

ZZ Quasigroup::invP1(ZZ x) { if (m_Dim % 2 == 0) { if(x % 2 == 0) { x = 2 * ((x / 2 + 1 - Dim2) % Dim2); } else { x = 2 * (((x - 1) / 2 - 1) % Dim2) + 1; } } else { if(x == m_Dim) { x = m_Dim; } else { if(x % 2 == 0) { x = 2 * ((x / 2 + 1 - Dim2) % Dim2); } else { x = 2 * (((x - 1) / 2 - 1) % Dim2) + 1; } } } return x; }

Ak už poznáme algoritmy na generovanie inverzných prvkov, môžeme dokončiť vytvorenie falošnej správy. Potrebujeme vypočítať

$x_{\upsilon} = \varphi ^{-1} (\theta (0) + (4 - \psi (3)) mod \, 4),$

Vyššie uvedenými metódami vypočítame inverzné prvky a po dosadení dostávame

$x_{\upsilon} = \varphi ^{-1} (2+(4-2) mod \, 4),$
$x_{\upsilon} = \varphi ^{-1} (0)$

a teda

$x_{\upsilon} = 0.$

Opäť sa nám podarilo nájsť správu, ktorej odtlačok je zhodný s odtlačkom pôvodnej správy.

$H_0 (2,1,1,3) = ((( 0 \cdot 2) \cdot 1 ) \cdot 1 ) \cdot 3 =$ $3$ ,
$H_0 (0,2,3,0) = ((( 0 \cdot 0) \cdot 2) \cdot 3) \cdot 0 =$ $3$ .

Dôsledok 2 Hašovacia funkcia $H_a$ nie je odolná voči nájdeniu kolízie, voči nájdeniu druhého vzoru ani voči nájdeniu prvého vzoru.

4. Záver

V práci sme predstavili návrh hašovacej funkcie založenej na kvázigrupách, podla [2], [3]. Ide o použitie kvázigrupy izotopnej s kvázigrupou modulárneho odčítania. Už pri študovaní samotnej konštrukcie, sme prišli na podstatný problém v generovaní permutácií, nakoľko jedna z uvedených metód permutáciu negeneruje
(časť 3.3). Z teoretického hľadiska to problém je, ale hašovat sa aj napriek tomuto faktu dá, čo sme ukázali na príklade 4.

Útok sme založili na nájdení kolízie a zistili sme, že jeho zložitosť, závisí od zložitosti nájdenia permutácie $\psi$ inverznej k $\psi ^{-1}$ a od zlo6itosti n8jdenia postupnosti $\varphi ^{-1}$ inverznej k $\varphi$ .

Z podkapitoly 3.1 a 3.2 môžeme vidieť, že útok je rovnako zložitý, ak falošnú správu vytvoríme modifikovaním pôvodnej správy, teda pridáme predponu, príponu, resp. obidva, alebo vytvoríme úplne novú správu nezávislú na pôvodnej. Taktiež vidíme, že známy parameter $a$ nijako nevplýva na bezpečnosť hašovacej funkcie a zložitosť útoku je rovnaká, či ho poznáme alebo nie.

Nakoľko sa daná permutácia a postupnosť negenerujú príliš zložito, podarilo sa nájsť inverzné metódy na ich generovanie (časť 3.3). Následne sa podarilo vytvoriť falošnú správu, ktorej odtlačok bol zhodný s odtlačkom pôvodnej správy.

5. Literatúra

DÉNES, J., KEEDWELL, A. D., "Latin Squares and their Applications", Academic Press, New York, 1974
DVORSKÝ, J., OCHODKOVÁ, E., SNÁŠEL, V., "Hashovací funkce založená na kvázigrupách", Mikulášska kryptobesídka, Praha, 2001, pp. 27-36
DVORSKÝ, J., OCHODKOVÁ, E., SNÁŠEL, V., "Hash functions based on large quasigroups", Proc. of Velikonocní kryptologie, Brno, 2002, pp. 1-8
GROŠEK, O., SATKO, L., NEMOGA, K., Ïdeal difference tables from an algebraic point of view", Cryptology and Information Security, Proceedings of VI RECSI, Teneriffe, Spain, 2000, pp. 453-454
PREENEL, B., "The state of hash functions", Cryptology and Information Security, Proceedings of VI RECSI, Teneriffe, Spain, 2000, pp. 3-27
VOJVODA, M., "Cryptoanalysis Of One Hash Function Based On Quasigroup", Tatra Mt. Math.Publ. 29, 2004, pp. 173-181

Spoluautorom tohto článku je Ing. Milan Vojvoda, PhD, Katedra aplikovanej informatiky a výpočtovej techniky, Fakulta elektrotechniky a informatiky STU Bratislava

O časopise

Meta

RSS

Kryptoanalýza kvázigrupovej hašovacej funkcie

Napísať príspevok

Rubriky

Burza práce

Štúdijné materiály

Archív