Útok nalezením vzoru

Útok nalezením vzoru (také útok nalezením předlohy, anglicky preimage attack) je kryptoanalytický útok na kryptografickou hašovací funkci, který najde k spočítanému haši některou ze zpráv, které jsou mu vzorem. U kryptografických hašovacích funkcí se rozlišují dva druhy odolnosti proti hledání vzoru:

• odolnost vůči nalezení vzoru (anglicky preimage resistance) – pro kryptografickou hašovací funkci $h$ a její libovolný výstup $y$ neexistuje prakticky realizovatelný algoritmus, který by uměl najít nějaké neznámé $x$ splňující $h(x)=y$
• odolnost vůči nalezení druhého vzoru (anglicky second-preimage resistance) – pro kryptografickou hašovací funkci $h$ a její libovolný vstup $x$ neexistuje prakticky realizovatelný algoritmus, který by uměl najít nějaké neznámé $x'$ splňující $h(x)=h(x')$

Srovnání s obecným hledáním kolizí

Odolnost vůči útoku nalezením druhého vzoru je silnější než vůči útoku nalezením kolize, neboť pokud útočník umí najít druhý vzor, umí tím najít i kolizi. U útoku nalezením kolize je totiž požadováno nalezení libovolných dvou kolizních vzorů, zatímco útok nalezením druhého vzoru požaduje schopnost najít druhý vzor k jednomu již zadanému.

U dříve široce používaných kryptografických hašovacích funkcí MD5 a SHA-1, u kterých už byly objeveny prakticky realizovatelné útoky nalezením kolize (MD5 v roce 2005, SHA-1 v roce 2017), se k roku 2018 nepodařilo najít prakticky realizovatelné útoky nalezením vzoru.

Reference

V tomto článku byl použit překlad textu z článku Preimage attack na anglické Wikipedii.