IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Kryptografie

Aktivity
Avatar
Anna
Člen
Avatar
Anna:17.2.2019 14:35

Ahoj, mým cílem je najít dvě vstupní hodnoty pro které z této hashovací funkce vyleze stejný hash.

Zkusil jsem: Snažím se na to přijít, ale nevidím to v tom

Chci docílit: dvě vstupní hodnoty, pro které je stejný hash.

 
Odpovědět
17.2.2019 14:35
Avatar
Matúš Olejník
Člen
Avatar
Odpovídá na Anna
Matúš Olejník:17.2.2019 14:52

z této hashovací funkce

Chcelo by to aj poslať tú funkciu :D

Nahoru Odpovědět
17.2.2019 14:52
/* I am not sure why this works but it fixes the problem */
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Anna
Martin Dráb:17.2.2019 14:56

Pokud se jedná o opravdu kvalitní hashovací funkci (ve svém příspěvku nezmiňuješ její název či algoritmus), v zásadě nezbývá nic jiného než prostě zkoušet náhodné vstupy, dokud se hash dvou z nich neshoduje.

Díky tzv. narozeninovému paradoxu to není tak beznadějný úkol, pokud je hash krátký. Pokud má například 64 bitů, stačí zahashovat 232 rozdílných vstupů a máš cca 50 % pravděpodobnost, že dva z nich dávají stejný hash (obecně pro hash délky n bitů toho dosáhneš zahashováním 2^(n/2) rozdílných vstupů).

Pokud se jedná o hashovací funkci známou svými slabinami (např. MD5), nebo je uměle vytvořená, můžeš zkoumat, jak podobné hashe jsou generovány podobnými vstupy. Případně pohledat články popisující ty slabiny (o MD5 toho je spousta a určitě někde bude i nějaký ukázkový kód... či sada vstupů, co generuje stejný hash).

Akceptované řešení
+20 Zkušeností
+2,50 Kč
Řešení problému
Nahoru Odpovědět
17.2.2019 14:56
2 + 2 = 5 for extremely large values of 2
Avatar
Anna
Člen
Avatar
Anna:17.2.2019 15:00

Přikládám (omlouvám se)
Ohledně délky hashe (je maximálně 8 bitový)

Editováno 17.2.2019 15:01
 
Nahoru Odpovědět
17.2.2019 15:00
Avatar
Anna
Člen
Avatar
Odpovídá na Matúš Olejník
Anna:17.2.2019 15:22

dodáno

 
Nahoru Odpovědět
17.2.2019 15:22
Avatar
Anna
Člen
Avatar
Anna:17.2.2019 15:23

Například jsem zahashovala text a jeho hash je 02365E1E061E62BA. A nemohu přijít na další možný vstup se stejným hashem...

 
Nahoru Odpovědět
17.2.2019 15:23
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Anna
Martin Dráb:17.2.2019 15:29

Jestli se dívám správně, tak klíčová by mohla být část kódu ve funkci update, která počítá položky a z d. POložka d[2] se zdá být zmíněna pouze jednou a je násobena osmi. To znamená, že nám stačí dát dva vstupy takové, že jejich třetí bajt dostane po vynásobení osmi vždy stejnou hodnotu. Myslím, že třeba něco takového by mohlo fungovat:

  • 00 00 00 00 00 00 00,
  • 00 00 20 00 00 00 00.

Ale možná jsem někde něco přehlédl.

Nahoru Odpovědět
17.2.2019 15:29
2 + 2 = 5 for extremely large values of 2
Avatar
Anna
Člen
Avatar
Anna:17.2.2019 16:02

A ještě doplňující otázka; je možné přijít na hodnotu hashe, pro který tato funkce nemá žádný vstup?

 
Nahoru Odpovědět
17.2.2019 16:02
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:18.2.2019 13:16

Nechce se mi lustit, co ten kod presne dela.

Je treba zkouset vsechny kombinace znaku a vytvaret hash. Nebo pouzit slovnik.

Pro urychleni bych si to zjednodusil na prvni vystupni hodnotu a pokud se shoduje, pak bych spustil cely hash.
Jakoze asi vystupem plne_funkce je h0-h7, tak cely algoritmus zjednodusit, aby zustalo jen h0. A az bude zjednodusena_fun­kce(vstup)==h0, tak spustis plna_funkce(vstup)==­cely_hash.
Podle toho kodu by se to mohlo zrychlit tak 16x.

 
Nahoru Odpovědět
18.2.2019 13:16
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Peter Mlich
Martin Dráb:18.2.2019 14:36

Nechce se mi lustit, co ten kod presne dela.

Přesně tak. Zjistit výstupy, které ta funkce nevyplivne podle mě vyžaduje analýzu toho, jak funguje, což mi nepřijde jako záležitost na pár minut.

Je treba zkouset vsechny kombinace znaku a vytvaret hash. Nebo pouzit slovnik.

To si myslím, že není cesta. Ten hash má 8 bajtů a ta zpráva může být libovolně dlouhá (skládá se s 8bajtových bloků, mezi kterými se přenáší interní stav v h0...h7). Kdyby otázka například zněla, které hashe to nevygeneruje pro zprávy dlouhé nejvýše jeden blok (15 bajtů), nebylo by to tak složité.

Nahoru Odpovědět
18.2.2019 14:36
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 10 zpráv z 10.