RIPEMD-128

RIPEMD-128
Kehittäjät	Hans Dobberthin , Anton Boselaers ja Bart Prenel
Luotu	1996
Standardit	ISO/IEC 10118-3:2004
Hash-koko	128 bittinen
Kierrosten lukumäärä	neljä
Tyyppi	hash-toiminto

RIPEMD-128 ( RACE Integrity Primitives Evaluation Message Digest ) on Hans DobbertininEnglanti Anton Boselaersin ja Bart Prenelin vuonna 1996 kehittämä kryptografinen hash - funktio .

Historia

RIPEMD on joukko hash-funktioita , jotka kuuluvat MD-SHA-perheeseen. Ensimmäinen näistä oli RIPEMD-0, jota RACE Integrity Primitives Evaluation (RIPE) -konsortio suositteli vuonna 1992 MD4 - algoritmin parannetuksi versioksi [1] . Dobbertinin suorittama krypta- analyysi osoitti, että tämä algoritmi ei ole turvallinen , minkä myöhemmin vahvistivat löydetyt haavoittuvuudet [ 2] RIPEMD-128 (yhdessä 160-bittisen version RIPEMD-160 kanssa ) esiteltiin korvaamaan alkuperäisen RIPEMD:n, joka myös oli 128-bittinen. Myös muita algoritmin versioita on kehitetty pidemmällä hash-pituudella: RIPEMD-256 ja RIPEMD-320 (256-bittinen ja 320-bittinen).

Toinen syy siirtymiseen algoritmeihin, jotka tuottavat tuloksen suurella bittimäärällä, oli laskentatekniikan nopea kehitys ( Mooren lain mukaan ). Tuolloin saatavilla olevat algoritmit tulivat vuosi vuodelta entistä haavoittuvaisempia raa'an voiman törmäyshyökkäyksille . RIPEMD-128 on kuitenkin löytänyt tiensä joihinkin pankkisovelluksiin [3] . Se standardisoitiin vuonna 2004 ( ISO/IEC 10118-3:2004 arkistoitu 2. helmikuuta 2017 Wayback Machinessa ).

Algoritmi

Satunnaisen syöttöviestin perusteella hash-funktio luo 128-bittisen hash-arvon, sanoman tiivisteen . Algoritmi perustuu MD4 -hajautusalgoritmiin . MD4-hajautus koostuu 48 operaatiosta, jotka sisältävät epälineaaristen Boolen funktioiden soveltamisen ja jotka on ryhmitelty 3 kierrokseen , joissa on 16 operaatiota. RIPEMD-128-algoritmissa kierrosten lukumäärä on nostettu 4:ään. Lisäksi käytetään muita Boolen funktioita ja vakioarvoja [3] . Algoritmissa suoritetaan kaksi riviä (virtaa) rinnakkain, jotka on ehdollisesti jaettu Vasemmalle ja Oikealle.

Algoritmi koostuu useista päävaiheista:

1. Puuttuvien bittien lisääminen

Algoritmi toimii 512-bittisillä tietolohkoilla, syöttöviesti pienennetään alustavasti vaadittuun kokoon. Ensin, riippumatta viestin alkuperäisestä pituudesta, siihen lisätään yksi bitti, joka on yhtä suuri kuin 1. Sitten siihen lisätään bittejä, jotka ovat yhtä suuria kuin 0, kunnes tuloksena olevan sekvenssin pituudeksi tulee 448 bittiä modulo 512. Laajennuksen seurauksena ylöspäin 512 bittiä pitkäksi, muokattu viesti on tasan 64 bittiä lyhyt. Tässä vaiheessa siihen voidaan lisätä 1 - 512 bittiä.

2. Viestin pituuden lisääminen

Seuraavassa vaiheessa alkuperäisen viestin pituus (ennen ensimmäisen vaiheen soveltamista) 64-bittisenä esityksenä lisätään 448-bittiseen vastaanotettuun viestiin. Jos alkuperäinen viestin pituus ylittää 264 bittiä, käytetään vain vähiten merkitseviä 64 bittiä sen bitin pituudesta. Lisäksi alkuperäisen viestin pituus lisätään kahden 32-bittisen sanan muodossa: ensin lisätään alemmat 32 bittiä, sitten korkeammat. Tämän vaiheen jälkeen muokatun viestin pituudeksi tulee 512 bittiä. Se voidaan esittää myös 16 32-bittisenä sanana.

3. Funktioiden ja vakioiden määrittely

a. Sanajärjestys viestissä

Jokaisella kierroksella käytetään erilaisia permutaatiofunktioiden yhdistelmiä määrittämään viestin 32-bittisten sanojen järjestys .

Määritellään permutaatiofunktio : $\rho$

$i$	0	yksi	2	3	neljä	5	6	7	kahdeksan	9	kymmenen	yksitoista	12	13	neljätoista	viisitoista
${\näyttötyyli \rho (i)}$	7	neljätoista	13	yksi	kymmenen	6	viisitoista	3	12	0	9	5	2	neljätoista	yksitoista	kahdeksan

Ja myös permutaatiofunktio : $\pi$

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

Jokaisella kierroksella järjestys määräytyy seuraavasti:

Linja	Erä 1	Kierros 2	Kierros 3	Kierros 4
Vasen	$i$	$\rho$	$\rho ^{2}$	$\rho ^{3}$
Oikein	$\pi$	$\pi \rho$	$\pi \rho ^{2}$	$\pi \rho ^{3}$

b. Boolen funktiot

Jokaisella kierroksella kullekin riville käytetään tiettyjä Boolen funktioita.

Määritellään epälineaariset bittikohtaiset Boolen funktiot:

$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\tai \neg y)\oplus z$

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

Jokaisella kierroksella linjasta riippuen sovelletaan seuraavaa:

Linja	Erä 1	Kierros 2	Kierros 3	Kierros 4
Vasen	$f_1$	$f_{2}$	$f_3$	${\displaystyle f_{4))$
Oikein	${\displaystyle f_{4))$	$f_3$	$f_{2}$	$f_1$

sisään. Vaihteet

Seuraavat muutokset ( ) koskevat molempia rivejä : $X$

Pyöristää	x0_ _	x1_ _	x2_ _	x3_ _	x4 _	x5_ _	x6 _	X7_ _	x8_ _	x9_ _	X 10	X 11	X 12	X 13	X 14	X 15
yksi	yksitoista	neljätoista	viisitoista	12	5	kahdeksan	7	9	yksitoista	13	neljätoista	viisitoista	6	7	9	kahdeksan
2	12	13	yksitoista	viisitoista	6	9	9	7	12	viisitoista	yksitoista	13	7	kahdeksan	7	7
3	13	viisitoista	neljätoista	yksitoista	7	7	6	kahdeksan	13	neljätoista	13	12	5	5	6	9
neljä	neljätoista	yksitoista	12	neljätoista	kahdeksan	6	5	5	viisitoista	12	viisitoista	neljätoista	9	9	kahdeksan	6

Vakiot

Seuraavien reaalilukujen kokonaislukuosia käytetään algoritmissa käytettyinä vakioina ( ): $K$

Linja	Erä 1	Kierros 2	Kierros 3	Kierros 4
Vasen	$0$	$2^{30}{\sqrt {2}}$	$2^{30}{\sqrt {3}}$	$2^{30}{\sqrt {5}}$
Oikein	$2^{30}{\sqrt[{3}]{2}}$	$2^{30}{\sqrt[{3}]{3))$	$2^{30}{\sqrt[{3}]{5}}$	$0$

4. Suoritetaan hajautus

Kun olet asettanut kaikki alkufunktiot ja vakiot ja saattanut viestin vaadittuun kokoon, voit jatkaa algoritmin suorittamiseen. Algoritmi suoritetaan kahta rinnakkaista polkua (viivaa) pitkin. Viestien käsittely tapahtuu 16 sanan sanoilla 32 bitissä.

Jokaisessa vaiheessa kullekin riville suoritetaan seuraava toimenpide:

${\näyttötyyli A:=(A+f(B,C,D)+X+K)^{<<s))$

jossa tarkoittaa syklistä paikkojen muutosta . ${\näyttötyyli ^{<<s))$ $s$

Työn nopeus

Vertailutaulukossa on esitetty MD-tyyppisten toimintojen suoritusnopeudet. Testiohjelmat kirjoitettiin assembly-kielellä ja C :llä käyttäen optimointeja testikoneelle: [4]

Algoritmi	Mbps - asm	Mbps - C	Suhteellinen suorituskyky
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

Myöhemmin tehty riippumaton tutkimus osoitti melko samanlaisia tuloksia. Mittauksessa käytettiin C++- kirjastoa Crypto++ : [5]

Algoritmi	Mbps	Jaksot per tavu	Suhteellinen suorituskyky
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

Turvallisuus

Salaustekniikassa on kahta päätyyppiä hyökkäyksiä kryptografisiin hajautustoimintoihin: esikuvahyökkäys - yritys löytää viesti, jolla on tietty hash-arvo, ja törmäyshyökkäys - kahden eri syöttölohkon etsiminen kryptografisesta hash-funktiosta, jotka tuottavat samat hash-funktion arvot eli tiivistetörmäysfunktiot .

RIPEMD-128-algoritmin, kuten muidenkin RIPEMD -perheen algoritmien , mukaan lukien alkuperäinen ensimmäinen, katsotaan kestävän esikuvahyökkäystä. RIPEMD-128 :lla ensimmäisen esikuvan löytämisen laskennallinen monimutkaisuus on 2 128 , mikä vastaa sen bittipituuden maksimiarvoa - haku vaatii kattavan haun : [6]

Algoritmi	Esikuvan löytämisen vaikeus	Paras hyökkäys (kierrokset)
RIPEMD (alkuperäinen)	2128 _	35/48
RIPEMD-128	2128 _	35/64
RIPEMD-160	2160 _	31/80

RIPEMD-128:n lyhennetylle versiolle on olemassa algoritmeja ensimmäisen esikuvan löytämiseksi, jotka vaativat vähemmän monimutkaisuutta: [7]

Pyöreät	Löytämisen vaikeus	Lähde
33	2 124,5 _	artikla [6]
35	2121 _	artikla [6]
36	2 126,5 _	artikla [8]

Alkuperäinen RIPEMD ei ollut törmäysturvallinen. Törmäys tuli tunnetuksi vuonna 2004 [2] , vuonna 2005 julkaistiin vastaava artikkeli algoritmin kryptausanalyysistä [9] . Koska mikä tahansa kryptografinen hash-funktio on määritelmän mukaan alttiina syntymäpäivähyökkäykselle , arvausvaikeus ei saa ylittää 2 N/2 N-bittisessä hash-funktiossa. 128-bittinen RIPEMD voidaan kuitenkin "rikkoa" 2 18 :ssa , mikä on paljon vähemmän kuin sen vastaava arvo 2 64 .

Täydellinen RIPEMD-128 voisi teoriassa olla "rikki". Törmäyshyökkäyksen monimutkaisuus on noin 2 61,57 (tarvittavaa 2 64 pistettä vastaan ). Vaikka lyhennetty versio on alttiina onnistuneemmille hyökkäyksille:

Kohde	Pyöreät	Löytämisen vaikeus	Lähde
Pakkaustoiminto	48	2 40	artikla [7]
Pakkaustoiminto	60	2 57,57	Artikkeli [1]
Pakkaustoiminto	63	2 59,91	Artikkeli [1]
Pakkaustoiminto	Täysi (64)	2 61,57	Artikkeli [1]
hash-toiminto	38	2 14	artikla [7]

Toiminnon 128-bittinen lähtö, joka ei näyttänyt olevan riittävän suojattu lyhyellä aikavälillä [3] , toimi vain syynä vaihtaa RIPEMD-160 :een . Hänestä tunnetaan vain törmäyshyökkäykset lyhennettyä versiota vastaan (48 laukausta 80:stä, 251 kertaa) [10] .

Esimerkkejä

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

Esimerkkejä lumivyöryvaikutuksesta :

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

Linkit

RIPEMD-perheen hash-funktiosivu Arkistoitu 14. joulukuuta 2005 Wayback Machinessa (kuvaus, lähteet)
Pääkehittäjäartikkeli arkistoitu 18. lokakuuta 2016 Wayback Machinessa

Muistiinpanot

↑ 1 2 3 4 Franck Landelle, Thomas Peyrin. Täyden RIPEMD-128:n kryptoanalyysi . — Matemaattisten tieteiden osasto, Fysikaalisten ja matemaattisten tieteiden korkeakoulu, Nanyang Technological University, Singapore, 2013.
↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Hash-funktioiden MD4, MD5, HAVAL-128 ja RIPEMD törmäykset . — Osasto Tietojenkäsittelytieteen ja -tekniikan tutkinto, Shanghai Jiaotong University, Shanghai, Kiina, 2004.
↑ 1 2 3 Hans Dobbertin, Antoon Bosselaers, Bart Preneel. RIPEMD-160: RIPEMD:n vahvistettu versio . – 1996.
↑ Bart Preneel, Hans Dobbertin, Antoon Bosselaers. Kryptografinen hajautusfunktio RIPEMD-160 . – 1997.
↑ Wei Dai. Suosittujen salausalgoritmien nopeusvertailu . Haettu 22. tammikuuta 2017. Arkistoitu alkuperäisestä 2. heinäkuuta 2017. (määrätön)
↑ 1 2 3 Chiaki Ohtahara, Yu Sasaki, Takeshi Shimoyama. Esikuvahyökkäykset RIPEMD-128:lle ja RIPEMD-160:lle . – 2011.
↑ 1 2 3 Florian Mendel, Tomislav Nad, Martin Schlaffer. Vähennetyn kaksoisvirran hajautusfunktion RIPEMD-128 törmäyshyökkäykset . – 2012.
↑ Lei Wang, Yu Sasaki, Wataru Komatsubara, Kazuo Ohta, Kazuo Sakiyama. (Toinen) Esikuvahyökkäykset askelvähennettyyn RIPEMD/RIPEMD-128:aan uudella paikallisen törmäyksen lähestymistavalla . – 2011.
↑ Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu. Hash-funktioiden MD4 ja RIPEMD salausanalyysi . — 2005. Arkistoitu 3. maaliskuuta 2019.
↑ Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen. RIPEMD-160:n törmäyskestävyydestä . – 2006.

Hash-funktiot
yleinen tarkoitus	Adler-32 CRC Fletcherin tarkistussumma FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash summa
Kryptografinen	Stribog GOST R 34.11-94 Vyö BLAKE BMW CubeHash KAIKU edonkey2k FSB Fuuga 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 Iho Snefru Tiikeri Whirlpool
Avainten luontitoiminnot	bcrypt PBKDF2 scrypt Argon 2 Lyra 2
Tarkista numero ( vertailu )	Tarkista summa Verhouffin algoritmi Kuun algoritmi Damm-algoritmi Viivakoodi pankkitilit pankkikortit ISIN SNILS OKPO TINA OKATO ISBN OGRN ja OGRNIP VIN
Hashes	Sekkinumeroiden vertailu Todennusprotokollat Viivakoodin vertailu Kryptografia Magneettilinkki Merklen allekirjoitus ed2k UURNA