Hamsi

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é 12. dubna 2012; kontroly vyžadují 10 úprav .

Hamsi je kryptografická hašovací funkce založená na algoritmech Grindahl [1] a Serpent [2] . Tato hašovací funkce není patentována a je ve veřejné doméně . Existují dvě varianty algoritmu : Hamsi-256 a Hamsi-512. Algoritmus je založen na expanzní funkci a cyklické transformaci . Cyklická transformace pracuje se čtyřmi řádky stavové matice . Počet sloupců této matice je 4 pro Hamsi-256, 8 pro Hamsi-512. Prvky matice jsou 32bitová slova .

Historie

Hamsi byl jedním z účastníků otevřené soutěže SHA-3 [4] Národního institutu pro standardy a technologie [ 4] s cílem vyvinout nové kryptografické hašovací funkce , které převádějí zprávy s proměnnou délkou na komprimované textové řetězce pevné délky, které lze použít pro elektronické digitální podpisy , ověřování zpráv a další aplikace. Prvního kola výběrového řízení se zúčastnilo 51 uchazečů. 14 z nich (včetně Hamsiho) postoupilo do druhého kola [5] . Hamsi však nebyl mezi 5 kandidáty z posledního kola oznámených 10. prosince 2010 [6] .

Popis

Obecná struktura

Hamsi používá takové transformace jako zřetězení ( anglicky Concatenation ), permutace ( anglicky Permutation ) a zaokrouhlování ( anglicky Truncation ), které se také používají v jiných hashovacích algoritmech , jako je Snefru [7] a Grindahl . Algoritmus také používá při každé iteraci funkce rozšíření zpráv a řetězení hodnot . Pro nelineární permutace ( angl. Non-linear Permitations ) se používají lineární transformace a jeden S-box z blokové šifry Serpent . Obecná struktura Hamsi může být reprezentována jako:

jeden	rozšíření zpráv	E: {0, 1} → {0, 1} $^{m}$ $^{n}$
2	Zřetězení	C : {0, 1} x {0, 1} → {0, 1} $^{n}$ $^{n}$ ${\displaystyle ^{s))$
3	Nelineární permutace	P,P : {0, 1} → {0, 1} ${\displaystyle _{f))$ ${\displaystyle ^{s))$ ${\displaystyle ^{s))$
čtyři	Zkrácení	T : {0, 1} → {0, 1} ${\displaystyle ^{s))$ $^{n}$

Označení:

F $_{n}$	Koncové těleso n prvků
<<<	Otočit doleva
$\oplus$	Exkluzivní OR ( XOR )
<<	Bitový posun doleva
[n, m, d]	Kód délky n, rozměru m a minimální vzdálenosti d

Hodnoty m, n a s pro různé varianty Hamsi jsou uvedeny v následující tabulce:

	m	n	s
Hamsi-256	32	256	512
Hamsi-512	64	512	1024

Nechť (M 1 ||M 2 ||M 3 || . . . ||M ||) je již dokončená zpráva, pak lze odrůdy Hamsi popsat takto: ${\displaystyle _{\ell ))$

Hamsi-256:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 256 , 0 < < ${\displaystyle _{i))$ ${\displaystyle _{i))$ ${\displaystyle _{i))$ ${\displaystyle _{i))$ $_{0}$ $i$ $i$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\displaystyle _{f))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$

Hamsi-512:

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1, h = v 512 , 0 < < ${\displaystyle _{i))$ ${\displaystyle _{i))$ ${\displaystyle _{i))$ ${\displaystyle _{i))$ $_{0}$ $i$ $i$ $\ell$

h = (T ◦ P ◦ C(E(M ), h −1)) ⊕ h −1 ${\displaystyle _{f))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$ ${\displaystyle _{\ell ))$

Počáteční hodnoty

Počáteční hodnotou pro algoritmus je počáteční hodnota vazebné hodnoty h $_{0}$ . Získává se pomocí kódování UTF-8 následující zprávy: "Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgium." Počáteční hodnoty pro různé varianty algoritmu jsou uvedeny v následující tabulce:

i

v 256

0x76657273, 0x69746569, 0x74204c65, 0x7576656e

0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69

i

v 512

0x73746565, 0x6c706172, 0x6b204172, 0x656e6265

0x72672031, 0x302c2062, 0x75732032, 0x3434362c

0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48

0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d

Dokončení zprávy

Hamsi pracuje na blocích zpráv o 32 a 64 bitech pro algoritmy Hamsi-256 a Hamsi-512 . Pokud je délka bloku menší, než je nutné, dojde k vyplnění zprávy . Přídavek je následující. Ke zprávě napravo se přidá jeden bit s hodnotou '1' a poté se přidají bity s hodnotou '0', dokud není délka zprávy 32 nebo 64. Příklad:

Existuje 24bitová zpráva

1010 0110 1110 1111 1111 0000

Po vyplnění na 32- bit to bude vypadat takto

1010 0110 1110 1111 1111 0000	1 000 0000

Rozšíření o zprávu

Hamsi používá k rozšíření zpráv lineární kódy [8] . U Hamsi-256 se rozšíření 32bitové zprávy na 256bitovou zprávu provádí pomocí kódu [128, 16, 70] přes pole F [9] . U Hamsi-512 se rozšíření 64bitové zprávy na 512bitovou zprávu provádí pomocí kódu [256, 32, 131] přes pole F . ${\displaystyle _{4))$ ${\displaystyle _{4))$

Zřetězení

Slovům rozšířené zprávy (m , m , . . . , m ) je přiřazena spojovací hodnota (c , c , . . . , c ). Hodnoty i a j jsou 7 pro Hamsi-256 a 15 pro Hamsi-512. Poté se na přijaté zprávě provede nelineární permutace P. Metoda zřetězení určuje pořadí bitů na vstupu P. $_{0}$ $_{jeden}$ ${\displaystyle _{i))$ $_{0}$ $_{jeden}$ ${\displaystyle _{j))$

Na Hamsi-256

C: {0, 1} x{0, 1} → {0, 1} $^{256}$ $^{256}$ $^{512}$ , další podrobnosti

C(m ,m 1 ,...,m 7 , c 0 , c 1 ,..., c 7 ) = (m 0 ,m 1 , c 0 , c 1 , c 2 , c 3 ,m 2 , m 3 , m 4 , m 5 , c 4 , c 5 , c 6 , c 7 , m 6 , m 7 ) $_{0}$

Slovosled si nejsnáze zapamatujete pomocí následující tabulky, jejíž výsledek lze získat čtením řádek po řádku:

m0 _	m 1	c 0	c 1
c 2	c 3	m2 _	m 3
m4 _	m 5	c 4	od 5
od 6	od 7	m6 _	m 7

Na Hamsi-512

C: {0, 1} × {0, 1} → {0, 1} $^{512}$ $^{512}$ $^{1024}$ , další podrobnosti

C(m 0 , m 1 , . . . , m 14 , m 15 , c 0 , c 1 , .. . , c 14 , c 15 ) = (m 0 , m 1 , c 0 , c 1 , m 2 ,m 3 , c 2 , c 3 , c 4 , c 5 , m 4 , m 5 , c 6 , c 7 , m 6 , m 7 , m 8 , m 9 , c 8 , c 9 , m 10 , m 11 , s 10 , s 11 , s 12 , s 13 , m 12 , m 13 , s 14 , s 15 , m 14 , m 15 )

Nelineární permutace P

Nelineární permutace se skládá ze tří stupňů

Vstupní bity , konstanty a čítač jsou XORed
Poté následuje aplikace 4bitových S-boxů
A nakonec několik aplikací lineární transformace L

To vše se opakuje tolikrát, kolikrát je udán počet cyklů. Vstup pokaždé obdrží zprávu (s 0 , s 1 , s 2 ,..., s j ), kde j je 15 pro Hamsi-256 a 31 pro Hamsi-512.

1) Přidání konstant a čítače

V této fázi jsou vstupní zprávy, konstanty a čítač XORed . Čítač určuje počet provedených cyklů. Pro první cyklus je c 0, pro druhý c = 1 a tak dále. Použité konstanty jsou uvedeny v následující tabulce:

α0 = 0xff00f0f0	α 1 = 0xccccaaaa	α 2 = 0xf0f0cccc	a 3 = 0xff00aaaa
α 4 = 0xccccaaaa	α 5 = 0xf0f0ff00	α 6 = 0xaaaacccc	α 7 = 0xf0f0ff00
α8 = 0xf0f0cccc	α9 = 0xaaaaff00	α10 = 0xccccff00	α 11 = 0xaaaaf0f0
α 12 = 0xaaaaf0f0	α13 = 0xff00cccc	α 14 = 0xccccf0f0	a 15 = 0xff00aaaa
α 16 = 0xccccaaaa	a 17 = 0xff00f0f0	a 18 = 0xff00aaaa	α 19 = 0xf0f0cccc
α20 = 0xf0f0ff00	α 21 = 0xccccaaaa	α22 = 0xf0f0ff00	α 23 = 0xaaaacccc
α24 = 0xaaaaff00	α 25 = 0xf0f0cccc	a 26 = 0xaaaaf0f0	a27 = 0xccccff00
a 28 = 0xff00cccc	α 29 = 0xaaaaf0f0	a 30 = 0xff00aaaa	a 31 = 0xccccf0f0

Na Hamsi-256

(s 0 , s 1 ,..., s 15 ) := (s 0 ⊕ α 0 , s 1 ⊕ α 1 ⊕ c, s 2 , . . . , s 15 ⊕ α 15 )

Na Hamsi-512

(s 0 , s 1 , ..., s 31 ) := (s 0 ⊕ α 0 , s 1 ⊕ α 1 ⊕ c, s 2 , ..., s 31 ⊕ α 31 )

2) Fáze substituce

V této fázi probíhá substituce 4bitových S-boxů převzatých z algoritmu Serpent . Hamsi je velmi dobře navržen pro paralelní výpočty . Všech 128 identických S-boxů (256 pro Hamsi-512) lze vypočítat současně, což urychluje algoritmus. S-box používaný v Hamsi:

X	0	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct
s[x]	osm	6	7	9	3	C	A	F	D	jeden	E	čtyři	0	B	5	2

3) Fáze konverze

Transformační krok je založen na několika aplikacích lineární transformace L: {0, 1} → {0, 1} $^{128}$ $^{128}$ . L pracuje na 32bitových slovech. Obecně lze transformaci zapsat jako (s i , s j , s k , s l ) := L(s i , s j , s k , s l ) .

Podrobnější popis transformace L(a, b, c, d) :

a := a <<< 13

c := c <<< 3

b := b ⊕ a ⊕ c

d := d ⊕ c ⊕ (a << 3)

b := b <<< 1

d := d <<< 7

a := a ⊕ b ⊕ d

c := c ⊕ d ⊕ (b << 7)

a := a <<< 5

c := c <<< 22

Zaokrouhlení

Zaokrouhlení T : {0, 1} 512 → {0, 1} 256 v Hamsi-256 je definováno takto:

T (s 0 , s 1 , s 2 , ... , s 14 , s 15 ) = ( s 0 , s 1 , s 2 , s 3 , s 8 , s 9 , s 10 , s 11 )

V Hamsi-512 zaokrouhlení T : {0, 1} 1024 → {0, 1} 512 je definováno takto:

T (s 0 , s 1 , s 2 , ... , s 30 , s 31 ) = ( s 0 , s 1 , s 2 , s 3 , s 4 , s 5 , s 6 , s 7 , s 16 , s 17 , s 18 , s 19 , s 20 , s 21 , s 22 , s 23 )

Zaokrouhlení se provádí po závěrečném cyklu nelineární permutace.

Nelineární permutace P f

Nelineární permutace P a P f se liší pouze v konstantách. Také Pf je aplikováno pouze na poslední blok zpráv jako konečná transformace.

Konstanty pro Pf :

a 0 = 0xcaf9639c	α1 = 0x0ff0f9c0	α2 = 0x639c0ff0	α 3 = 0xcaf9f9c0
α4 = 0x0ff0f9c0	α 5 = 0x639ccaf9	α6 = 0xf9c00ff0	α 7 = 0x639ccaf9
α8 = 0x639c0ff0	α9 = 0xf9c0caf9	α10 = 0x0ff0caf9	a 11 = 0xf9c0639c
a 12 = 0xf9c0639c	α13 = 0xcaf90ff0	α14 = 0x0ff0639c	α 15 = 0xcaf9f9c0
a 16 = 0x0ff0f9c0	a 17 = 0xcaf9639c	α 18 = 0xcaf9f9c0	α19 = 0x639c0ff0
α20 = 0x639ccaf9	a 21 = 0x0ff0f9c0	α22 = 0x639ccaf9	a 23 = 0xf9c00ff0
α 24 = 0xf9c0caf9	α25 = 0x639c0ff0	a 26 = 0xf9c0639c	α 27 = 0x0ff0caf9
α 28 = 0xcaf90ff0	a 29 = 0xf9c0639c	α 30 = 0xcaf9f9c0	a31 = 0x0ff0639c

Počet cyklů

Počet cyklů pro různé varianty Hamsi je uveden v tabulce:

	Hamsi-256	Hamsi-512
P cykly	3	6
P f cyklů	6	12

Ve druhém kole soutěže SHA-3 se objevila nová modifikace algoritmu nazvaná Hamsi-256/8. Jeho rozdíl od Hamsi-256 je v tom, že počet Pf cyklů je nyní 8.

Poznámky

↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl - rodina hašovacích funkcí (neurčitá) // Poznámky k přednáškám z informatiky. - 2007. - T. 4593 . - S. 39-57 . - doi : 10.1007/978-3-540-74619-5_3 . Archivováno z originálu 15. září 2012.
↑ Had: Návrh pokročilého šifrovacího standardu Archivováno 13. ledna 2013 na Wayback Machine .
↑ NIST.gov – Divize počítačové bezpečnosti – Centrum počítačových zdrojů . Získáno 28. listopadu 2009. Archivováno z originálu 9. července 2011. (neurčitý)
↑ Národní institut pro standardy a technologie . Získáno 28. listopadu 2009. Archivováno z originálu 17. června 2015. (neurčitý)
↑ NIST.gov – Divize počítačové bezpečnosti – Centrum počítačových zdrojů . Získáno 28. listopadu 2009. Archivováno z originálu 10. dubna 2012. (neurčitý)
↑ Zpráva o stavu druhého kola SHA-3 . Získáno 15. června 2015. Archivováno z originálu 14. března 2011. (neurčitý)
↑ Merkle RC Rychlá softwarová jednosměrná hashovací funkce. Journal of Cryptology, 3(1):43-58, 1990
↑ JH van Lint. Úvod do teorie kódování
↑ Ohraničuje minimální vzdálenost lineárních kódů. http://codetables.de.BKLC/ (nedostupný odkaz)

Literatura

Ozgül Kücük. Hashovací funkce Hamsi (PDF) (31. října 2008). Získáno 11. prosince 2008. Archivováno z originálu 11. dubna 2012. (neurčitý)
https://web.archive.org/web/20100825061836/http://homes.esat.kuleuven.be/~okucuk/hamsi/index.html
http://www.cosic.esat.kuleuven.be/publications/article-1203.pdf