RIPEMD-128

RIPEMD-128
Udviklere	Hans Dobberthin , Anton Boselaers og Bart Prenel
Oprettet	1996
Standarder	ISO/IEC 10118-3:2004
Hash størrelse	128 bit
Antal runder	fire
Type	hash funktion

RIPEMD-128 ( RACE Integrity Primitives Evaluation Message Digest ) er en kryptografisk hashfunktion udviklet af Hans Dobbertinengelsk Anton Boselaers og Bart Prenel i 1996 .

Historie

RIPEMD er et sæt hash-funktioner, der tilhører MD-SHA-familien. Den første af disse var RIPEMD-0, anbefalet i 1992 af RACE Integrity Primitives Evaluation (RIPE) konsortiet som en forbedret version af MD4-algoritmen [1] . Krypteringsanalyse udført af Dobbertin viste, at denne algoritme ikke er sikker i forhold til , hvilket senere blev bekræftet af de fundne sårbarheder [ 2] RIPEMD-128 (sammen med en 160-bit version, RIPEMD-160 ) blev introduceret som en erstatning for den originale RIPEMD, som også var 128-bit. Andre versioner af algoritmen er også blevet udviklet med længere hash-længder: RIPEMD-256 og RIPEMD-320 (henholdsvis 256-bit og 320-bit).

En anden grund til at gå over til algoritmer, der producerer et resultat med et stort antal bits, var den hurtige udvikling af computerteknologi (ifølge Moores lov ). De algoritmer, der var tilgængelige på det tidspunkt, blev mere og mere sårbare over for brute-force kollisionsangreb hvert år . Imidlertid har RIPEMD-128 fundet vej til nogle bankapplikationer [3] . Det blev standardiseret i 2004 ( ISO/IEC 10118-3:2004 Arkiveret 2. februar 2017 på Wayback Machine ).

Algoritme

Givet en vilkårlig inputmeddelelse genererer hash-funktionen en 128-bit hashværdi, beskedsammendraget . Algoritmen er baseret på MD4 hashing-algoritmen . MD4 hashing består af 48 operationer, der indeholder anvendelsen af ikke-lineære booleske funktioner , grupperet i 3 runder af 16 operationer. I RIPEMD-128-algoritmen er antallet af runder øget til 4. Derudover bruges andre boolske funktioner og konstantværdier [3] . I algoritmen udføres to linjer (flows) parallelt, som er betinget opdelt i Venstre og Højre.

Algoritmen består af flere hovedtrin:

1. Tilføjelse af manglende bits

Algoritmen fungerer med datablokke på 512 bit, inputmeddelelsen er foreløbigt reduceret til den nødvendige størrelse. Først, uanset meddelelsens begyndelseslængde, tilføjes en bit lig med 1. Derefter tilføjes bit lig med 0 til den, indtil længden af den resulterende sekvens bliver 448 bit modulo 512. Som et resultat af udvidelse, op til 512 bit lang, er den ændrede meddelelse nøjagtigt 64 bit kort. På dette trin kan der tilføjes fra 1 til 512 bits.

2. Tilføjelse af beskedlængde

Ved næste trin føjes længden af den oprindelige meddelelse (før anvendelse af det første trin) i 64-bit repræsentation til den 448-bit modtagne meddelelse. Hvis den oprindelige meddelelseslængde overstiger 264 bit, så bruges kun de mindst signifikante 64 bit af dens bitlængde. Desuden tilføjes længden af den originale meddelelse i form af to 32-bit ord: de nederste 32 bit tilføjes først, derefter de højere. Efter dette trin bliver længden af den ændrede meddelelse 512 bit. Det kan også repræsenteres som 16 32-bit ord.

3. Definition af funktioner og konstanter

en. Ordrækkefølge i beskeden

Forskellige kombinationer af permutationsfunktioner bruges i hver runde for at bestemme rækkefølgen af 32-bit ord i meddelelsen .

Lad os definere permutationsfunktionen : $\rho$

$jeg$	0	en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten
$\rho (i)$	7	fjorten	13	en	ti	6	femten	3	12	0	9	5	2	fjorten	elleve	otte

Og også permutationsfunktionen : $\pi$

$\pi (i)=9i+5(mod16)$

I hver runde bestemmes rækkefølgen som følger:

Linje	Runde 1	Runde 2	Runde 3	Runde 4
Venstre	$jeg$	$\rho$	$\rho ^{2}$	$\rho ^{3}$
Ret	$\pi$	$\pi \rho$	$\pi \rho ^{2}$	$\pi \rho ^{3}$

b. Booleske funktioner

I hver runde anvendes visse booleske funktioner for hver linje.

Lad os definere ikke-lineære bitvise booleske funktioner:

$f_{1}(x,y,z)=x\oplus y\oplus z$

$f_{2}(x,y,z)=(x\land y)\lor (\neg x\land z)$

$f_{3}(x,y,z)=(x\eller \neg y)\oplus z$

$f_{4}(x,y,z)=(x\land z)\lor (y\land \neg z)$

I hver runde, afhængig af linjen, gælder følgende:

Linje	Runde 1	Runde 2	Runde 3	Runde 4
Venstre	$f_1$	$f_{2}$	$f_3$	${\displaystyle f_{4))$
Ret	${\displaystyle f_{4))$	$f_3$	$f_{2}$	$f_1$

i. Skifter

Følgende skift ( ) gælder for begge linjer : $x$

Rund	x0 _	x1 _	x2 _	x3 _	x4 _	x5 _	x6 _	X7 _	x8 _	x9 _	X 10	X 11	X 12	X 13	X 14	X 15
en	elleve	fjorten	femten	12	5	otte	7	9	elleve	13	fjorten	femten	6	7	9	otte
2	12	13	elleve	femten	6	9	9	7	12	femten	elleve	13	7	otte	7	7
3	13	femten	fjorten	elleve	7	7	6	otte	13	fjorten	13	12	5	5	6	9
fire	fjorten	elleve	12	fjorten	otte	6	5	5	femten	12	femten	fjorten	9	9	otte	6

Konstanter

Heltalsdelene af følgende reelle tal bruges som konstanter ( ) brugt i algoritmen: $K$

Linje	Runde 1	Runde 2	Runde 3	Runde 4
Venstre	$0$	$2^{30}{\sqrt {2}}$	$2^{30}{\sqrt {3}}$	$2^{30}{\sqrt {5}}$
Ret	$2^{30}{\sqrt[{3}]{2))$	$2^{30}{\sqrt[{3}]{3))$	$2^{30}{\sqrt[{3}]{5))$	$0$

4. Udfører hashing

Efter at have indstillet alle de indledende funktioner og konstanter, bragt meddelelsen til den nødvendige størrelse, kan du fortsætte til udførelsen af algoritmen. Algoritmen udføres langs to parallelle stier (linjer). Beskedbehandling sker i ord på 16 ord i 32 bit.

Ved hvert trin, for hver af linjerne, udføres følgende operation:

${\displaystyle A:=(A+f(B,C,D)+X+K)^{<<s))$

hvor angiver et cyklisk skift i positioner. ${\displaystyle ^{<<s))$ $s$

Arbejdshastighed

Tabellen til sammenligning viser udførelseshastighederne for MD-lignende funktioner. Testprogrammerne blev skrevet i assemblersprog og C , ved hjælp af optimeringer til testmaskinen: [4]

Algoritme	Mbps - asm	Mbps - C	Relativ præstation
RIPEMD-128	77,6	35,6	1.00
RIPEMD-160	45,3	19.3	0,58
SHA-1	54,9	21.2	0,71
MD5	136,2	59,7	1,76
MD4	190,6	81,4	2,46

En uafhængig undersøgelse udført senere viste nogenlunde lignende resultater. C++- biblioteket Crypto++ blev brugt i målingen : [5]

Algoritme	Mbps	Cykler pr. byte	Relativ præstation
RIPEMD-128	153	11.4	1.00
RIPEMD-160	106	16.5	0,69
RIPEMD-256	158	11.1	1.03
RIPEMD-320	110	15.9	0,72
SHA-1	153	11.4	1.00
MD5	255	6.8	1,67

Sikkerhed

I kryptografi er der to hovedtyper af angreb på kryptografiske hashfunktioner: et preimage-angreb - et forsøg på at finde en besked med en given hashværdi og et kollisionsangreb - en søgning efter to forskellige inputblokke af en kryptografisk hashfunktion, der producerer de samme hashfunktionsværdier, det vil sige en hashkollision -funktioner .

RIPEMD-128-algoritmen, ligesom andre algoritmer i RIPEMD- familien , inklusive den originale første, anses for at være modstandsdygtig over for preimage-angrebet. For RIPEMD-128 er den beregningsmæssige kompleksitet ved at finde det første præbillede 2 128 , hvilket falder sammen med den maksimale værdi for dets bitlængde - søgningen kræver udtømmende søgning : [6]

Algoritme	Vanskeligheden ved at finde forbilledet	Bedste angreb (runder)
RIPEMD (original)	2128 _	35 ud af 48
RIPEMD-128	2128 _	35 ud af 64
RIPEMD-160	2160 _	31 ud af 80

For en forkortet version af RIPEMD-128 er der algoritmer til at finde det første preimage, der kræver mindre kompleksitet: [7]

runder	Svært ved at finde	Kilde
33	2.124,5 _	Artikel [6]
35	2121 _	Artikel [6]
36	2.126,5 _	Artikel [8]

Den originale RIPEMD var ikke kollisionssikker. Kollisionen blev kendt i 2004 [2] , i 2005 blev der publiceret en tilsvarende artikel om kryptoanalysen af algoritmen [9] . Da enhver kryptografisk hashfunktion per definition er sårbar over for et fødselsdagsangreb , kan sværhedsgraden ved at gætte ikke overstige 2 N/2 for en N-bit hashfunktion. En 128-bit RIPEMD kan dog blive "brudt" i 2 18 , hvilket er meget mindre end dens tilsvarende værdi på 2 64 .

En komplet RIPEMD-128 kunne teoretisk set være "brudt". Kollisionsangrebet har en kompleksitet på omkring 2 61,57 (mod de nødvendige 2 64 ). Mens den forkortede version er genstand for mere vellykkede angreb:

Mål	runder	Svært ved at finde	Kilde
Kompressionsfunktion	48	2 40	Artikel [7]
Kompressionsfunktion	60	2 57,57	Artikel [1]
Kompressionsfunktion	63	2 59,91	Artikel [1]
Kompressionsfunktion	Fuld (64)	2 61,57	Artikel [1]
hash funktion	38	2 14	Artikel [7]

Funktionens 128-bit output, som ikke syntes at være tilstrækkeligt beskyttet på kort sigt [3] , tjente blot som en grund til at skifte til RIPEMD-160 . For hende kendes kun kollisionsangreb på den forkortede version (48 ud af 80 runder, 251 gange) [10] .

Eksempler

RIPEMD128("") = "cdf26213a150dc3ecb610f18f6b38b46" RIPEMD128("a") = "86be7afa339d0fc7cfc785e72f578d33" RIPEMD128("abc") = "c14a12199c66e4ba84636b0f69144c77"

Eksempler, der demonstrerer lavineeffekten :

RIPEMD128("aaa10 0 ") = "5b250e8d7ee4fd67f35c3d193c6648c4" RIPEMD128("aaa10 1 ") = "e607de9b0ca4fe01be84f87b83d8b5a3"

Noter

↑ 1 2 3 4 Franck Landelle, Thomas Peyrin. Kryptoanalyse af fuld RIPEMD-128 . — Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, 2013.
↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Kollisioner for Hash-funktionerne MD4, MD5, HAVAL-128 og RIPEMD . — Afd. of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai, Kina, 2004.
↑ 1 2 3 Hans Dobbertin, Antoon Bosselaers, Bart Preneel. RIPEMD-160: En styrket version af RIPEMD . – 1996.
↑ Bart Preneel, Hans Dobbertin, Antoon Bosselaers. Den kryptografiske hash-funktion RIPEMD-160 . – 1997.
↑ Wei Dai. Hastighedssammenligning af populære kryptoalgoritmer . Hentet 22. januar 2017. Arkiveret fra originalen 2. juli 2017. (ubestemt)
↑ 1 2 3 Chiaki Ohtahara, Yu Sasaki, Takeshi Shimoyama. Preimage-angreb på Step-Reduced RIPEMD-128 og RIPEMD-160 . – 2011.
↑ 1 2 3 Florian Mendel, Tomislav Nad, Martin Schlaffer. Kollisionsangreb på den reducerede Dual-Stream Hash-funktion RIPEMD-128 . – 2012.
↑ Lei Wang, Yu Sasaki, Wataru Komatsubara, Kazuo Ohta, Kazuo Sakiyama. (Anden) Preimage-angreb på trinreduceret RIPEMD/RIPEMD-128 med en ny lokal kollisionstilgang . – 2011.
↑ Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu. Krypteringsanalyse af Hash-funktionerne MD4 og RIPEMD . — 2005. Arkiveret 3. marts 2019.
↑ Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen. Om kollisionsmodstanden af RIPEMD-160 . – 2006.

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE