RIPEMD-128

RIPEMD-128
Vývojáři	Hans Dobberthin , Anton Boselaers a Bart Prenel
Vytvořeno	1996
Normy	ISO/IEC 10118-3:2004
Velikost hash	128 bit
Počet kol	čtyři
Typ	hashovací funkce

RIPEMD-128 ( RACE Integrity Primitives Evaluation Message Digest ) je kryptografická hašovací funkce vyvinutá Hansem Dobbertinemanglicky Antonem Boselaersem a Bartem Prenelem v roce 1996 .

Historie

RIPEMD je sada hashovacích funkcí patřících do rodiny MD-SHA. První z nich byl RIPEMD-0, doporučený v roce 1992 konsorciem RACE Integrity Primitives Evaluation (RIPE) jako vylepšená verze algoritmu MD4 [1] . Kryptoanalýza provedená Dobbertinem ukázala, že tento algoritmus není bezpečný z hlediska , což později potvrdily nalezené zranitelnosti [ 2] RIPEMD-128 (spolu se 160bitovou verzí, RIPEMD-160 ) byl představen jako náhrada za původní RIPEMD, který byl rovněž 128bitový. Další verze algoritmu byly také vyvinuty s delšími délkami hash: RIPEMD-256 a RIPEMD-320 (256-bit a 320-bit, v tomto pořadí).

Dalším důvodem pro přechod k algoritmům, které produkují výsledek s velkým počtem bitů, byl rychlý rozvoj výpočetní techniky (podle Moorova zákona ). Algoritmy dostupné v té době se staly každým rokem více a více zranitelnější vůči útokům kolizí hrubou silou . RIPEMD-128 si však našel cestu do některých bankovních aplikací [3] . Byl standardizován v roce 2004 ( ISO/IEC 10118-3:2004 Archived 2 February 2017 at Wayback Machine ).

Algoritmus

Vzhledem k libovolné vstupní zprávě vygeneruje hašovací funkce 128bitovou hašovací hodnotu, souhrn zprávy . Algoritmus je založen na hashovacím algoritmu MD4 . MD4 hash se skládá ze 48 operací obsahujících aplikaci nelineárních booleovských funkcí , seskupených do 3 kol po 16 operacích. V algoritmu RIPEMD-128 byl počet kol zvýšen na 4. Kromě toho se používají další booleovské funkce a konstantní hodnoty [3] . V algoritmu jsou paralelně prováděny dvě linie (toky), které jsou podmíněně rozděleny na levou a pravou.

Algoritmus se skládá z několika hlavních kroků:

1. Přidání chybějících bitů

Algoritmus pracuje s datovými bloky 512 bitů, vstupní zpráva je předběžně zmenšena na požadovanou velikost. Nejprve se k ní bez ohledu na počáteční délku zprávy přidá jeden bit rovný 1. Poté se k ní přidají bity rovné 0, dokud délka výsledné sekvence nebude 448 bitů modulo 512. V důsledku rozšíření se na 512 bitů, upravená zpráva je přesně 64 bitů krátká. V tomto kroku k němu lze přidat od 1 do 512 bitů.

2. Přidání délky zprávy

V dalším kroku se délka původní zprávy (před aplikací prvního kroku) v 64bitové reprezentaci přičte k 448bitové přijaté zprávě. Pokud původní délka zprávy přesáhne 264 bitů, použije se pouze nejméně významných 64 bitů její bitové délky. Navíc je délka původní zprávy přidána ve formě dvou 32bitových slov: nejprve se přidá nižších 32 bitů, poté vyšší. Po tomto kroku bude délka upravené zprávy 512 bitů. Může být také reprezentován jako 16 32bitových slov.

3. Definice funkcí a konstant

A. Slovosled ve zprávě

K určení pořadí 32bitových slov ve zprávě se v každém kole používají různé kombinace permutačních funkcí .

Pojďme definovat permutační funkci : $\rho$

$i$	0	jeden	2	3	čtyři	5	6	7	osm	9	deset	jedenáct	12	13	čtrnáct	patnáct
$\rho (i)$	7	čtrnáct	13	jeden	deset	6	patnáct	3	12	0	9	5	2	čtrnáct	jedenáct	osm

A také permutační funkce : $\pi$

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

V každém kole je pořadí určeno takto:

Čára	1. kolo	2. kolo	3. kolo	4. kolo
Vlevo, odjet	$i$	$\rho$	$\rho ^{2}$	$\rho ^{3}$
Že jo	$\pi$	$\pi \rho$	$\pi \rho ^{2}$	$\pi \rho ^{3}$

b. Booleovské funkce

V každém kole jsou na každý řádek aplikovány určité booleovské funkce.

Pojďme definovat nelineární bitové booleovské funkce:

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

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

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

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

V každém kole, v závislosti na řadě, platí následující:

Čára	1. kolo	2. kolo	3. kolo	4. kolo
Vlevo, odjet	$f_1$	$f_{2}$	$f_3$	${\displaystyle f_{4))$
Že jo	${\displaystyle f_{4))$	$f_3$	$f_{2}$	$f_1$

v. Směny

Následující posuny ( ) platí pro oba řádky : $X$

Kolo	x0 _	x1 _	x2 _	x3 _	x4 _	x5 _	x6 _	X7 _	x8 _	x9 _	X 10	X 11	X 12	X 13	X 14	X 15
jeden	jedenáct	čtrnáct	patnáct	12	5	osm	7	9	jedenáct	13	čtrnáct	patnáct	6	7	9	osm
2	12	13	jedenáct	patnáct	6	9	9	7	12	patnáct	jedenáct	13	7	osm	7	7
3	13	patnáct	čtrnáct	jedenáct	7	7	6	osm	13	čtrnáct	13	12	5	5	6	9
čtyři	čtrnáct	jedenáct	12	čtrnáct	osm	6	5	5	patnáct	12	patnáct	čtrnáct	9	9	osm	6

Konstanty

Celé části následujících reálných čísel se používají jako konstanty ( ) použité v algoritmu: $K$

Čára	1. kolo	2. kolo	3. kolo	4. kolo
Vlevo, odjet	$0$	$2^{30}{\sqrt {2}}$	$2^{30}{\sqrt {3}}$	$2^{30}{\sqrt {5}}$
Že jo	$2^{30}{\sqrt[{3}]{2}}$	$2^{30}{\sqrt[{3}]{3}}$	$2^{30}{\sqrt[{3}]{5}}$	$0$

4. Provádění hašování

Po nastavení všech počátečních funkcí a konstant, uvedení zprávy na požadovanou velikost, můžete přistoupit k provádění algoritmu. Algoritmus se provádí podél dvou paralelních cest (čar). Zpracování zprávy probíhá ve slovech o 16 slovech ve 32 bitech.

V každém kroku se pro každý z řádků provede následující operace:

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

kde označuje cyklický posun v pozicích. ${\displaystyle ^{<<s))$ $s$

Rychlost práce

Tabulka pro srovnání ukazuje rychlosti provádění funkcí podobných MD. Testovací programy byly napsány v assembleru a C s použitím optimalizací pro testovací stroj: [4]

Algoritmus	Mbps – asm	Mbps - C	Relativní výkon
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

Nezávislá studie provedená později ukázala poměrně podobné výsledky. Při měření byla použita C++ knihovna Crypto++ : [5]

Algoritmus	Mbps	Cykly na byte	Relativní výkon
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

Zabezpečení

V kryptografii existují dva hlavní typy útoků na kryptografické hashovací funkce: útok preimage – pokus najít zprávu s danou hash hodnotou, a kolizní útok – hledání dvou různých vstupních bloků kryptografické hashovací funkce, které produkují stejné hodnoty hashovací funkce, to jest hašovací kolize -funkce .

Algoritmus RIPEMD-128, stejně jako ostatní algoritmy z rodiny RIPEMD , včetně původního prvního, je považován za odolný vůči útoku preimage. Pro RIPEMD-128 je výpočetní složitost nalezení prvního předobrazu 2 128 , což se shoduje s maximální hodnotou pro jeho bitovou délku – hledání vyžaduje vyčerpávající hledání : [6]

Algoritmus	Obtížnost nalezení předobrazu	Nejlepší útok (kola)
RIPEMD (originál)	2128 _	35 ze 48
RIPEMD-128	2128 _	35 z 64
RIPEMD-160	2160 _	31 z 80

Pro zkrácenou verzi RIPEMD-128 existují algoritmy pro nalezení prvního předobrazu, které vyžadují menší složitost: [7]

kola	Obtížnost hledání	Zdroj
33	2 124,5 _	článek [6]
35	2121 _	článek [6]
36	2 126,5 _	článek [8]

Původní RIPEMD nebyl kolizní. Kolize vešla ve známost v roce 2004 [2] , v roce 2005 vyšel odpovídající článek o kryptoanalýze algoritmu [9] . Vzhledem k tomu, že jakákoli kryptografická hašovací funkce je z definice zranitelná vůči narozeninovému útoku , obtížnost uhodnutí nemůže překročit 2 N/2 pro N-bitovou hašovací funkci. 128bitový RIPEMD však může být „zlomen“ na 2 18 , což je mnohem méně než jeho odpovídající hodnota 2 64 .

Kompletní RIPEMD-128 by teoreticky mohl být "rozbitý". Kolizní útok má složitost asi 2 61,57 (proti nezbytným 2 64 ). Zatímco zkrácená verze podléhá úspěšnějším útokům:

cílová	kola	Obtížnost hledání	Zdroj
Kompresní funkce	48	2 40	článek [7]
Kompresní funkce	60	2 57,57	článek [1]
Kompresní funkce	63	2 59,91	článek [1]
Kompresní funkce	Úplné (64)	2 61,57	článek [1]
hashovací funkce	38	2 14	článek [7]

128bitový výstup funkce, který se krátkodobě nezdál být dostatečně chráněný [3] , posloužil právě jako důvod k přechodu na RIPEMD-160 . U ní jsou známy pouze kolizní útoky na zkrácenou verzi (48 z 80 ran, 251krát ) [10] .

Příklady

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

Příklady demonstrující lavinový efekt :

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

Odkazy

Stránka hašovací funkce rodiny RIPEMD Archivováno 14. prosince 2005 na Wayback Machine (popis, zdroje)
Hlavní článek pro vývojáře Archivováno 18. října 2016 na Wayback Machine

Poznámky

↑ 1 2 3 4 Franck Landelle, Thomas Peyrin. Kryptoanalýza úplného RIPEMD-128 . — Division of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapur, 2013.
↑ 1 2 Xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu. Kolize pro hashovací funkce MD4, MD5, HAVAL-128 a RIPEMD . — Odd. of Computer Science and Engineering, Shanghai Jiaotong University, Shanghai, China, 2004.
↑ 1 2 3 Hans Dobbertin, Antoon Bosselaers, Bart Preneel. RIPEMD-160: Posílená verze RIPEMD . — 1996.
↑ Bart Preneel, Hans Dobbertin, Antoon Bosselaers. Kryptografická hashovací funkce RIPEMD-160 . — 1997.
↑ Wei Dai. Porovnání rychlosti populárních krypto algoritmů . Získáno 22. ledna 2017. Archivováno z originálu 2. července 2017. (neurčitý)
↑ 1 2 3 Chiaki Ohtahara, Yu Sasaki, Takeshi Shimoyama. Útoky předobrazu na RIPEMD-128 a RIPEMD-160 s omezeným počtem kroků . — 2011.
↑ 1 2 3 Florian Mendel, Tomislav Nad, Martin Schlaffer. Kolizní útoky na redukované duální hashovací funkci RIPEMD-128 . — 2012.
↑ Lei Wang, Yu Sasaki, Wataru Komatsubara, Kazuo Ohta, Kazuo Sakiyama. (Druhé) Útoky předobrazem na stupňovitě redukovaném RIPEMD/RIPEMD-128 s novým přístupem k místním srážkám . — 2011.
↑ Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen, Xiuyuan Yu. Kryptoanalýza hashovacích funkcí MD4 a RIPEMD . — 2005. Archivováno 3. března 2019.
↑ Florian Mendel, Norbert Pramstaller, Christian Rechberger, Vincent Rijmen. O odolnosti RIPEMD-160 proti kolizi . — 2006.

Hashovací funkce
obecný účel	Adler-32 CRC Fletcherův kontrolní součet FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografický	Stribog GOST R 34.11-94 Pás BLAKE bmw CubeHash ECHO edonkey2k FSB Fuga 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 Kůže Snefru Tygr vířivá vana
Funkce generování klíčů	bcrypt PBKDF2 scrypt Argon2 Lyra2
Kontrolní číslo ( srovnání )	Kontrolní součet Verhouffův algoritmus Algoritmus Měsíce Sakra algoritmus čárový kód bankovní účty bankovních karet ISIN SNILS OKPO CÍN OKATO ISBN OGRN a OGRNIP VIN
Hashe	Porovnání kontrolních čísel Autentizační protokoly Porovnání čárových kódů Kryptografie Magnetický odkaz Merkle podpis ed2k URNA