Hamsi

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 12 aprilie 2012; verificările necesită 10 modificări .

Hamsi este o funcție hash criptografică bazată pe algoritmii Grindahl [1] și Serpent [2] . Această funcție hash nu este brevetată și este în domeniul public . Există două varietăți de algoritm : Hamsi-256 și Hamsi-512. Algoritmul se bazează pe funcția de expansiune și transformarea ciclică . Transformarea ciclică funcționează cu patru rânduri ale matricei de stare . Numărul de coloane din această matrice este 4 pentru Hamsi-256, 8 pentru Hamsi-512. Elementele matricei sunt cuvinte de 32 de biți .

Istorie

Hamsi a fost unul dintre participanții la competiția deschisă SHA-3 [4] a Institutului Național de Standarde și Tehnologie [ 4] pentru a dezvolta noi funcții hash criptografice care convertesc mesajele de lungime variabilă în șiruri de text comprimate de lungime fixă care pot fi utilizate pentru electronice . semnături digitale , autentificare a mesajelor și alte aplicații. La primul tur al concursului au participat 51 de candidați. 14 dintre ei (inclusiv Hamsi) au avansat în turul doi [5] . Hamsi nu s-a numărat însă printre cei 5 candidați din ultimul tur anunțați pe 10 decembrie 2010 [6] .

Descriere

Structura generală

Hamsi folosește transformări precum concatenare ( English Concatenation ), permutare ( English Permutation ) și rotunjire ( English Truncation ), care sunt, de asemenea, utilizate în alți algoritmi de hashing , cum ar fi Snefru [7] și Grindahl . Algoritmul folosește, de asemenea, funcțiile de expansiune a mesajului și de valoare Chaining la fiecare iterație . Pentru permutările neliniare ( ing. Permisiuni neliniare ) se folosesc transformări liniare și o cutie S din cifrul bloc Serpent . Structura generală a lui Hamsi poate fi reprezentată ca:

unu	extinderea mesajului	E : {0, 1} → {0, 1} ${\displaystyle ^{m))$ $^{n}$
2	Concatenare	C : {0, 1} x {0, 1} → {0, 1} $^{n}$ $^{n}$ ${\displaystyle ^{s))$
3	Permutări neliniare	P,P : {0, 1} → {0, 1} $_{f)$ ${\displaystyle ^{s))$ ${\displaystyle ^{s))$
patru	Trunchiere	T : {0, 1} → {0, 1} ${\displaystyle ^{s))$ $^{n}$

Denumiri:

F $_{n}$	Câmp final de n elemente
<<<	Rotiți la stânga
$\oplus$	SAU exclusiv ( XOR )
<<	Deplasare biți la stânga
[n, m, d]	Cod de lungime n, dimensiune m și distanță minimă d

Valorile m, n și s pentru diferite variante Hamsi sunt prezentate în următorul tabel:

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

Fie (M 1 ||M 2 ||M 3 || . . . . ||M ||) este deja un mesaj finalizat, atunci soiurile de Hamsi pot fi descrise după cum urmează: $_{\ell )$

Hamsi-256:

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

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

Hamsi-512:

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

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

Valori inițiale

Valoarea inițială pentru algoritm este valoarea inițială a valorii de legare h $_{0}$ . Se obține folosind codificarea UTF-8 a următorului mesaj: „Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgia”. Valorile inițiale pentru diferitele variante ale algoritmului sunt prezentate în următorul tabel:

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

Completarea mesajului

Hamsi operează pe blocuri de mesaje de 32 și 64 de biți pentru algoritmii Hamsi-256 și, respectiv, Hamsi-512 . Dacă lungimea blocului este mai mică decât este necesar, atunci apare mesajul de umplere . Adăugarea este după cum urmează. La mesajul din dreapta se adaugă un bit cu valoarea „1” și apoi se adaugă biții cu valoarea „0” până când lungimea mesajului este de 32 sau 64. Exemplu:

Există un mesaj pe 24 de biți

1010 0110 1110 1111 1111 0000

După completarea la 32 de biți , va arăta așa

1010 0110 1110 1111 1111 0000	1000 0000

Extensia mesajului

Hamsi folosește coduri liniare [8] pentru a extinde mesajele. Pentru Hamsi-256, extinderea unui mesaj de 32 de biți într-un mesaj de 256 de biți se face folosind codul [128, 16, 70] peste câmpul F [9] . Pentru Hamsi-512, extinderea unui mesaj de 64 de biți într-un mesaj de 512 de biți se face folosind codul [256, 32, 131] peste câmpul F. $_{4)$ $_{4)$

Concatenare

Cuvintele mesajului extins (m ,m , . . . ,m ) li se atribuie o valoare de legătură (c , c , . . . . , c ). Valorile i și j sunt 7 pentru Hamsi-256 și 15 pentru Hamsi-512. Apoi, pe mesajul primit va fi efectuată o permutare neliniară P. Metoda concatenării determină ordinea biților la intrarea P. $_{0}$ $_{unu}$ $_{i)$ $_{0}$ $_{unu}$ $_{j)$

La Hamsi-256

C: {0, 1} x{0, 1} → {0, 1} $^{256}$ $^{256}$ $^{512}$ , mai multe detalii

C(m , m1 , ...,m7 , c0 , c1 ,...,c7 ) = ( m0 , m1 , c0 , c1 , c2 , c3 , m2 , m 3 ,m 4 , m 5 , c 4 , c 5 , c 6 , c 7 ,m 6 ,m 7 ) $_{0}$

Ordinea cuvintelor este cel mai ușor de reținut folosind următorul tabel, al cărui rezultat poate fi obținut prin citirea rând cu rând:

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

La Hamsi-512

C: {0, 1} × {0, 1} → {0, 1} $^{512}$ $^{512}$ $^{1024}$ , mai multe detalii

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 )

Permutarea neliniară P

Permutarea neliniară constă din trei etape

Biții de intrare , constantele și contorul sunt XOR
Urmează apoi aplicarea S-box-urilor pe 4 biți
Și în sfârșit, mai multe aplicații ale transformării liniare L

Toate acestea se repetă de câte ori este dat numărul de cicluri. Intrarea primește de fiecare dată un mesaj (s 0 , s 1 , s 2 , . . . , s j ), unde j este 15 pentru Hamsi-256 și 31 pentru Hamsi-512.

1) Adăugarea constantelor și a contorului

În această etapă, mesajul de intrare, constantele și contorul sunt XOR . Contorul determină numărul ciclului executat. Pentru primul ciclu, c este 0, pentru al doilea, c = 1 și așa mai departe. Constantele utilizate sunt prezentate în următorul tabel:

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

La Hamsi-256

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

La Hamsi-512

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

2) Etapa de înlocuire

În această etapă, are loc înlocuirea cutiilor S pe 4 biți preluate din algoritmul Serpent . Hamsi este foarte bine proiectat pentru calculul paralel . Toate cele 128 de cutii S identice (256 pentru Hamsi-512) pot fi calculate în același timp, ceea ce accelerează algoritmul. S-box folosit în Hamsi:

X	0	unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece
s x]	opt	6	7	9	3	C	A	F	D	unu	E	patru	0	B	5	2

3) Etapa de conversie

Etapa de transformare se bazează pe mai multe aplicații ale transformării liniare L: {0, 1} → {0, 1} $^{128}$ $^{128}$ . L operează pe cuvinte de 32 de biți. În general, transformarea poate fi scrisă ca (s i , s j , s k , s l ) := L(s i , s j , s k , s l ) .

O descriere mai detaliată a transformării 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

Rotunjire

Rotunjirea T : {0, 1} 512 → {0, 1} 256 în Hamsi-256 este definită după cum urmează:

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 )

În Hamsi-512 rotunjirea T : {0, 1} 1024 → {0, 1} 512 este definit după cum urmează:

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 )

Rotunjirea se realizează după ciclul final al permutării neliniare.

Permutație neliniară P f

Permutările neliniare P și P f diferă numai în constante. De asemenea, P f este aplicat doar ultimului bloc de mesaj ca transformare finală.

Constante pentru P f :

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

Numărul de cicluri

Numărul de cicluri pentru diferite variante de Hamsi este prezentat în tabel:

	Hamsi-256	Hamsi-512
cicluri P	3	6
P f cicluri	6	12

În a doua rundă a competiției SHA-3 , a apărut o nouă modificare a algoritmului numită Hamsi-256/8. Diferența sa față de Hamsi-256 este că numărul de cicluri Pf este acum 8.

Note

↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl - o familie de funcții hash (nedefinite) // Lecture Notes in Computer Science. - 2007. - T. 4593 . - S. 39-57 . - doi : 10.1007/978-3-540-74619-5_3 . Arhivat din original pe 15 septembrie 2012.
↑ Serpent: O propunere pentru standardul avansat de criptare Arhivat la 13 ianuarie 2013 la Wayback Machine .
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Consultat la 28 noiembrie 2009. Arhivat din original pe 9 iulie 2011. (nedefinit)
↑ Institutul Național de Standarde și Tehnologie . Consultat la 28 noiembrie 2009. Arhivat din original la 17 iunie 2015. (nedefinit)
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Consultat la 28 noiembrie 2009. Arhivat din original la 10 aprilie 2012. (nedefinit)
↑ Raport de stare privind a doua rundă a SHA-3 . Consultat la 15 iunie 2015. Arhivat din original la 14 martie 2011. (nedefinit)
↑ Merkle RC O funcție de hash unidirecțională rapidă a software-ului. Journal of Cryptology, 3(1):43-58, 1990
↑ JH van Lint. Introducere în teoria codificării
↑ Limite pe distanța minimă a codurilor liniare. http://codetables.de.BKLC/ (link indisponibil)

Literatură

Ozgül Kücük. Funcția Hash Hamsi (PDF) (31 octombrie 2008). Consultat la 11 decembrie 2008. Arhivat din original la 11 aprilie 2012. (nedefinit)
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