Hamsi

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. april 2012; checks kræver 10 redigeringer .

Hamsi er en kryptografisk hashfunktion baseret på Grindahl [1] og Serpent [2] algoritmerne . Denne hash-funktion er ikke patenteret og er i det offentlige domæne . Der er to varianter af algoritmen : Hamsi-256 og Hamsi-512. Algoritmen er baseret på ekspansionsfunktionen og cyklisk transformation . Cyklisk transformation fungerer med fire rækker af tilstandsmatrixen . Antallet af kolonner i denne matrix er 4 for Hamsi-256, 8 for Hamsi-512. Elementerne i matrixen er 32- bit ord .

Historie

Hamsi var en af deltagerne i National Institute of Standards and Technologys [4] SHA-3 åbne konkurrence [ 4] om at udvikle nye kryptografiske hashfunktioner, der konverterer beskeder med variabel længde til komprimerede tekststrenge med fast længde, der kan bruges til elektroniske digitale signaturer , meddelelsesgodkendelse og andre applikationer. 51 kandidater deltog i første runde af konkurrencen. 14 af dem (inklusive Hamsi) gik videre til anden runde [5] . Hamsi var dog ikke blandt de 5 kandidater til sidste runde, der blev annonceret den 10. december 2010 [6] .

Beskrivelse

Generel struktur

Hamsi bruger sådanne transformationer som sammenkædning ( engelsk sammenkædning ), permutation ( engelsk permutation ) og afrunding ( engelsk trunkering ), som også bruges i andre hashing - algoritmer , såsom Snefru [7] og Grindahl . Algoritmen bruger også meddelelsesudvidelses- og kædeværdifunktionerne ved hver iteration . _ Til ikke-lineære permutationer ( eng. Non-linear Permitations ) bruges lineære transformationer og en S-boks fra Serpent - blokcifre . Hamsi's generelle struktur kan repræsenteres som:

en	beskedudvidelse	E : {0, 1} → {0, 1} ${\displaystyle ^{m))$ $^{n}$
2	Sammenkædning	C : {0, 1} x {0, 1} → {0, 1} $^{n}$ $^{n}$ ${\displaystyle ^{s))$
3	Ikke-lineære permutationer	P,P : {0, 1} → {0, 1} ${\displaystyle _{f))$ ${\displaystyle ^{s))$ ${\displaystyle ^{s))$
fire	Trunkering	T : {0, 1} → {0, 1} ${\displaystyle ^{s))$ $^{n}$

Betegnelser:

F $_{n}$	Endeligt felt af n elementer
<<<	Drej til venstre
$\plus$	Eksklusiv ELLER ( XOR )
<<	Bitskift til venstre
[n, m, d]	Kode for længde n, dimension m og minimumsafstand d

m-, n- og s-værdierne for forskellige Hamsi-varianter er vist i følgende tabel:

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

Lad (M 1 ||M 2 ||M 3 || . . . ||M ||) er allerede en afsluttet besked, så kan sorterne af Hamsi beskrives som følger: ${\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}$ $jeg$ $jeg$ $\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}$ $jeg$ $jeg$ $\ell$

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

Indledende værdier

Startværdien for algoritmen er startværdien af bindingsværdien h $_{0}$ . Den opnås ved hjælp af UTF-8- kodningen af følgende meddelelse: "Ozgul Kucuk, Katholieke Universiteit Leuven, Departement Elektrotechniek, Computer Security and Industrial Cryptography, Kasteelpark Arenberg 10, bus 2446, B-3001 Leuven-Heverlee, Belgien." Startværdierne for de forskellige varianter af algoritmen er præsenteret i følgende tabel:

jeg

v 256

0x76657273, 0x69746569, 0x74204c65, 0x7576656e

0x2c204b61, 0x74686f6c, 0x69656b65, 0x20556e69

jeg

v 512

0x73746565, 0x6c706172, 0x6b204172, 0x656e6265

0x72672031, 0x302c2062, 0x75732032, 0x3434362c

0x20422d33, 0x30303120, 0x4c657576, 0x656e2d48

0x65766572, 0x6c65652c, 0x2042656c, 0x6769756d

Færdiggørelse af meddelelsen

Hamsi opererer på beskedblokke på 32 og 64 bit for henholdsvis Hamsi-256 og Hamsi-512 algoritmerne . Hvis bloklængden er mindre end nødvendigt, opstår beskedudfyldning . Tilføjelsen er som følger. En bit med værdien '1' tilføjes til meddelelsen til højre , og derefter tilføjes bits med værdien '0', indtil meddelelseslængden er 32 eller 64. Eksempel:

Der er en 24 bit besked

1010 0110 1110 1111 1111 0000

Efter polstring til 32- bit vil det se sådan ud

1010 0110 1110 1111 1111 0000	1000 0000

Beskedudvidelse

Hamsi bruger lineære koder [8] til at udvide beskeder. For Hamsi-256 udføres udvidelsen af en 32- bit besked til en 256 - bit besked ved at bruge koden [128, 16, 70] over F [9] feltet . For Hamsi-512 sker udvidelsen af en 64- bit besked til en 512 - bit besked ved at bruge koden [256, 32, 131] over F-feltet . ${\displaystyle _{4))$ ${\displaystyle _{4))$

Sammenkædning

Ordene i den udvidede meddelelse (m ,m , . . . . , m ) tildeles en forbindelsesværdi (c , c , . . . , c ). i- og j-værdierne er 7 for Hamsi-256 og 15 for Hamsi-512. Derefter udføres en ikke-lineær permutation P på den modtagne meddelelse. Sammenkædningsmetoden bestemmer rækkefølgen af bits ved input P. $_{0}$ $_{en}$ ${\displaystyle _{i))$ $_{0}$ $_{en}$ ${\displaystyle _{j))$

Hos Hamsi-256

C: {0, 1} x{0, 1} → {0, 1} $^{256}$ $^{256}$ $^{512}$ , flere detaljer

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}$

Ordrækkefølgen er nemmest at huske ved at bruge følgende tabel, hvis resultat kan opnås ved at læse linje for linje:

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

Hos Hamsi-512

C: {0, 1} × {0, 1} → {0, 1} $^{512}$ $^{512}$ $^{1024}$ , flere detaljer

C( m 0 , m 1 , . . . , m 14 , m 15 , c 0 , c 1 , . . . ,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 )

Ikke-lineær permutation P

Ikke-lineær permutation består af tre trin

Indgangsbittene , konstanterne og tælleren er XORed
Derefter følger anvendelsen af 4-bit S-bokse
Og endelig flere anvendelser af den lineære transformation L

Alt dette gentages lige så mange gange, som antallet af cyklusser er angivet. Inputtet modtager hver gang en besked (s 0 , s 1 , s 2 , . . . , s j ), hvor j er 15 for Hamsi-256 og 31 for Hamsi-512.

1) Tilføjelse af konstanter og tæller

På dette trin er inputmeddelelsen, konstanterne og tælleren XORed . Tælleren bestemmer nummeret på den udførte cyklus. For den første cyklus er c 0, for den anden er c = 1, og så videre. De anvendte konstanter er vist i følgende 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

Hos Hamsi-256

( s 0 , s 1 , ... _ _ _ _ _ _ _ _ _ _ _ _ _

Hos Hamsi-512

( s 0 , s 1 , ... _ _ _ _ _ _ _ _ _ _ _ _ _

2) Udskiftningstrin

På dette stadium finder substitutionen af 4-bit S-bokse taget fra Serpent -algoritmen sted . Hamsi er meget godt designet til parallel computing . Alle 128 identiske S-bokse (256 for Hamsi-512) kan beregnes på samme tid, hvilket fremskynder algoritmen. S-boks brugt i Hamsi:

x	0	en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten
s[x]	otte	6	7	9	3	C	EN	F	D	en	E	fire	0	B	5	2

3) Konverteringstrin

Transformationstrinnet er baseret på flere anvendelser af den lineære transformation L: {0, 1} → {0, 1} $^{128}$ $^{128}$ . L opererer på 32-bit ord. Generelt kan transformationen skrives som (s i , s j , s k , s l ) := L(s i , s j , s k , s l ) .

En mere detaljeret beskrivelse af transformationen 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

Afrunding

Afrunding T : {0, 1} 512 → {0, 1} 256 i Hamsi-256 er defineret som følger:

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 )

I Hamsi-512 afrunding T : {0, 1} 1024 → {0, 1} 512 er defineret som følger:

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 )

Afrunding udføres efter den sidste cyklus af den ikke-lineære permutation.

Ikke-lineær permutation P f

Ikke-lineære permutationer P og Pf adskiller sig kun i konstanter. Desuden anvendes Pf kun på den sidste meddelelsesblok som en endelig transformation.

Konstanter for P f :

a 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

Antal cyklusser

Antallet af cyklusser for forskellige varianter af Hamsi er angivet i tabellen:

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

I anden runde af SHA-3- konkurrencen dukkede en ny modifikation af algoritmen kaldet Hamsi-256/8 op. Dens forskel fra Hamsi-256 er, at antallet af Pf - cyklusser nu er 8.

Noter

↑ L. R. Knudsen, C. Rechberger, S. S. Thomsen. Grindahl - en familie af hashfunktioner (ubestemt) // Lecture Notes in Computer Science. - 2007. - T. 4593 . - S. 39-57 . - doi : 10.1007/978-3-540-74619-5_3 . Arkiveret fra originalen den 15. september 2012.
↑ Serpent: Et forslag til den avancerede krypteringsstandard Arkiveret 13. januar 2013 på Wayback Machine .
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Hentet 28. november 2009. Arkiveret fra originalen 9. juli 2011. (ubestemt)
↑ National Institute of Standards and Technology . Hentet 28. november 2009. Arkiveret fra originalen 17. juni 2015. (ubestemt)
↑ NIST.gov - Computer Security Division - Computer Security Resource Center . Hentet 28. november 2009. Arkiveret fra originalen 10. april 2012. (ubestemt)
↑ Statusrapport om anden runde af SHA-3 . Hentet 15. juni 2015. Arkiveret fra originalen 14. marts 2011. (ubestemt)
↑ Merkle RC En hurtig software-envejs-hash-funktion. Journal of Cryptology, 3(1):43-58, 1990
↑ JH van Lint. Introduktion til kodningsteori
↑ Grænser for minimumsafstanden for lineære koder. http://codetables.de.BKLC/ (utilgængeligt link)

Litteratur

Ozgül Kücük. Hash-funktionen Hamsi (PDF) (31. oktober 2008). Hentet 11. december 2008. Arkiveret fra originalen 11. april 2012. (ubestemt)
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