Geek tričko zdarma Geek tričko zdarma
Tričko zdarma! Stačí před dobitím bodů použít kód TRIKO15. Více informací zde

Diskuze: Kryptografie

Aktivity (2)
Avatar
Marie
Člen
Avatar
Marie :17. února 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. února 14:35
Avatar
Odpovídá na Marie
Matúš Olejník:17. února 14:52

z této hashovací funkce

Chcelo by to aj poslať tú funkciu :D

Nahoru Odpovědět 17. února 14:52
/* I am not sure why this works but it fixes the problem */
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Marie
Martin Dráb:17. února 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í
+1 bodů
Řešení problému
Nahoru Odpovědět 17. února 14:56
2 + 2 = 5 for extremely large values of 2
Avatar
Marie
Člen
Avatar
Marie :17. února 15:00

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

Editováno 17. února 15:01
 
Nahoru Odpovědět 17. února 15:00
Avatar
Marie
Člen
Avatar
 
Nahoru Odpovědět 17. února 15:22
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!
Avatar
Marie
Člen
Avatar
Marie :17. února 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. února 15:23
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Marie
Martin Dráb:17. února 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. února 15:29
2 + 2 = 5 for extremely large values of 2
Avatar
Marie
Člen
Avatar
Marie :17. února 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. února 16:02
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:18. února 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. února 13:16
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Peter Mlich
Martin Dráb:18. února 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. února 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.