Všechny t?i útoky jsou útoky na vzor zprávy. Jsou založeny na principu "setkání uprost?ed" a používají stejnou techniku. V prvních dvou útocích autor doporu?uje zvýšit délku vnit?ního stavu, která by zásadn? zesložitila pravd?podobnost shody uprost?ed. U FFT ?íká, že je n?co shnilého ve struktu?e.
Preimage Attack on Hashing with Polynomials proposed at ICISC'06
Donghoon Chang
Abstract. In this paper, we suggest a preimage attack on Hashing with Polynomials proposed at ICISC'06 cite{Shpilrain06}. The algorithm has $n$-bit hash output and $n$-bit intermediate state. (for example, $n=163$). The algorithm is very simple and light so that it can be implement in low memory environment. Our attack is based on the meet-in-the-middle attack. We can find a preimage with the time complexity $2^{n-t}+2^{t}$ and the memory $2^{t}$. We recommend that hash functions such as Hashing with Polynomials should have the intermediate state size at least two times bigger than the output size.
Preimage Attacks on CellHash and SubHash
Donghoon Chang
Abstract. CellHash cite{DaGoVa91} and SubHash cite{DaGoVa92} were suggested by J. Daemen, R. Govaerts and J. Vandewalle in 1991 and 1992. SubHash is an improved version from CellHash. They have 257-bit internal state and 256-bit hash output. In this paper, we show a preimage attack on CellHash (SubHash) with the complexity $2^{129+t}$ and the memory $513*2^{128-t}$ bits for any $t$ (with the complexity about $2^{241}$ and the memory $513*2^{17}$ bits). Even though we modify them in a famous way, we show that we can find a preimage on the modified CellHash (the modified SubHash) with the complexity $2^{194}$ and the memory $513*2^{64}$ bits (with the complexity about $2^{241}$ and the memory size $513*2^{17}$ bits). So we recommend that a simple invertible structure-repeated hash functions such as CellHash and SubHash have the size of internal state two times longer at least than the output size of hash function. For example, Parallel FFT-Hashing cite{ScVa93} and RadioGat'{u}n cite{BeDaAsPe06} are such a case.
Preimage Attack on Parallel FFT-Hashing
Donghoon Chang
Abstract. Parallel FFT-Hashing was suggested by C. P. Schnorr and S. Vaudenay in 1993 cite{ScVa93}. That is a simple and light hash algorithm. Its basic component is a multi-permutation. We show a preimage attack on Parallel FFT-Hashing with complexity $2^{113}$ which is less than the complexity $2^{128}$. This shows that the structure of Parallel FFT-Hashing has some weaknesses.
