# Generic Attacks

## Contents

# 1 Preimage attacks

The resistance of a hash function to collision and (second) preimage
attacks depends in the first place on the length n of the hash
value. Regardless of how a hash function is designed, an adversary
will always be able to find preimages or second preimages after
trying out about 2^{n} different messages. In case an adversary is
given 2^{k} distinct target hashes, preimages can be found after
trying about 2^{n-k} different
messages. This is first described in the thesis of Merkle, pages 12-13.

*Ralf C. Merkle* - **Secrecy, authentication, and public key systems**

- Ph.D. Thesis, ,1979
- Bibtex
**Author :**Ralf C. Merkle**Title :**Secrecy, authentication, and public key systems**In :**Ph.D. Thesis, -**Address :****Date :**1979

# 2 Collision attacks

As independently observed by Merkle and
Yuval in 1979, finding collisions
requires a much smaller number of trials: about 2^{n/2}, as
described subsequently. As a result, hash
functions producing less than 160 bits of output are currently
considered inherently insecure. Moreover, if the internal structure
of a particular hash function allows collisions or preimages to be
found more efficiently than what could be expected based on its hash
length, then the function is considered to be broken.

*Ralph C. Merkle* - **A Certified Digital Signature**

- CRYPTO 435:218-238,1989
- http://link.springer.de/link/service/series/0558/bibs/0435/04350218.htm

Bibtex**Author :**Ralph C. Merkle**Title :**A Certified Digital Signature**In :**CRYPTO -**Address :****Date :**1989

*Gideon Yuval* - **How to Swindle Rabin**

- Cryptologia 3:187-189,1979
- Bibtex
**Author :**Gideon Yuval**Title :**How to Swindle Rabin**In :**Cryptologia -**Address :****Date :**1979

### 2.1 The birthday attack

The birthday attack (also called*square-root* attack) is a generic attack which considers a
hash function as black box. Therefore, a birthday attack is
successful for every hash function. For any message m we can
compute the n-bit hash value y = h(m). Since at least a fraction
2^{-n} of the pairs (m,m*) satisfies h(m) = h(m*), one can
expect to find a colliding message pair after trying about 2^{n},
arbitrary message pairs. Nevertheless, it
follows from the birthday paradox that one can check 2^{n} pairs
with only 2^{n/2} evaluations of h. A birthday attack works as
follows:

- Pick any message m and compute h(m).
- Update list L. Check if h(m) is in the list L.
- if (h(m),m) is already in L, a colliding message pair has been found.
- else save the pair (h(m),m) in the list L and go back to step 1.

From the birthday paradox we know that we can expect to find a
matching entry, after performing about 2^{n/2} hash evaluations.
Note that in a birthday attack an attacker has full control over the
messages. Hence, as pointed out by Yuval, this method
enables an attacker to construct meaningful collisions.

The simple algorithm discussed above has memory requirements
<math>O(2^{n/2})</math>. Pollard's rho-method, based on distinguished points,
can be used to greatly reduce memory requirements at little extra
cost. Also, various cycle finding algorithms are of use for
collision search. In practice, generic collision search might not
run on a single processor, but rather in parallel on many
processors. Van Oorschot and
Wiener discuss a method to
achieve linear runtime gains.

*Paul C. van Oorschot, Michael J. Wiener* - **Parallel Collision Search with Cryptanalytic Applications**

- J. Cryptology 12(1):1-28,1999
- http://link.springer.de/link/service/journals/00145/bibs/12n1p1.html

Bibtex**Author :**Paul C. van Oorschot, Michael J. Wiener**Title :**Parallel Collision Search with Cryptanalytic Applications**In :**J. Cryptology -**Address :****Date :**1999

*Michael J. Wiener* - **The Full Cost of Cryptanalytic Attacks**

- J. Cryptology 17(2):105-124,2004
- http://dx.doi.org/10.1007/s00145-003-0213-5

Bibtex**Author :**Michael J. Wiener**Title :**The Full Cost of Cryptanalytic Attacks**In :**J. Cryptology -**Address :****Date :**2004

# 3 Attacks in the quantum setting

Results of quantum complexity theorists as well as newly invented algorithms suggest that even with the power of hypothetic quantum computers applied against commonly used hash functions, no exponential improvement over classical computers is possible. Here we briefly discuss hash function related aspects of this work.

One of the celebrated results in quantum algorithms is
Grover's from 1996: The search for a particular element in an unordered database of size
r takes at most O(r^{1/2}), an actual algorithm is provided. Matching lower bounds exist for this problem as
well (see Boyer et al. and Zalka). This
algorithm is of wide interest as it does not rely on a particular
structure of the elements in the search space.

This result has already direct implications on hash functions:
There, the search for a preimage or a second preimage is at most as
hard as a search in an unordered database, hence security against
these types of generic attacks is lowered from 2^{n} to 2^{n/2}
in the quantum setting.

How about collision attacks in the quantum setting? Here, the fact
that many collisions exist and the problem is to find a single one
indeed leads to (both asymptotically and for commonly used finite
dimensions) faster
algorithms. An actual quantum algorithm for the collision problem is
due to Brassard, H{\o}yer, and
Tapp from 1997. This combination
of Grover's algorithm with the birthday effect yields a runtime of 2^{n/3} for a hash function with n bit output size. The
algorithm requires <math>\Theta(n^{1/3}log n)</math> classical bits of
memory. To the best of the author's knowledge, no time/memory
tradeoffs are known. Is this the best one can do? Nontrivial lower
bounds for the collision problem were an open problem for some time.
Only in 2001, Aaronson proved a
query complexity of <math>\Omega(n^{1/5})</math>. Subsequent work of Shi
improved this bound to <math>\Omega(n^{1/4})</math> and finally to
<math>\Omega(n^{1/3})</math>. As this constitutes a tight bound, indeed one can not do better than
Brassard et al. That is, given our current axiomatic assumptions
about the nature of quantum mechanics.

The bottom line here is as follows. Ignoring practical problems with implementations of large, stable quantum computers, and still requiring a (what now became standard) 128-bit security level gives rise to the following minimal output sizes for hash functions. If only oneway-ness but not collision resistance is required then 256-bits would be enough, for collision resistance at least 384 bits are needed. Of course, these blackbox results might not be the end of the story, dedicated quantum cryptanalytic techniques have not been considered yet. Fast quantum algorithms to compute median and mean values by Grover, and other basic building blocks seem to be an interesting starting point.

*Lov K. Grover* - **A Fast Quantum Mechanical Algorithm for Database Search**

- Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC), Philadelphia, Pennsylvania, USA, May 22-24, 1996 pp. 212--219,1996
- http://doi.acm.org/10.1145/237814.237866

Bibtex**Author :**Lov K. Grover**Title :**A Fast Quantum Mechanical Algorithm for Database Search**In :**Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC), Philadelphia, Pennsylvania, USA, May 22-24, 1996 -**Address :****Date :**1996

*Michel Boyer, Gilles Brassard, Peter H\oyer, Alain Tapp* - **Tight bounds on quantum searching**

- Fortschritte der Physik 46(PP-1996-11):493-505, 30, 1998
- citeseer.ist.psu.edu/article/boyer98tight.html

Bibtex**Author :**Michel Boyer, Gilles Brassard, Peter H\oyer, Alain Tapp**Title :**Tight bounds on quantum searching**In :**Fortschritte der Physik -**Address :****Date :**30, 1998

*Christof Zalka* - **Grover’s quantum searching algorithm is optimal**

- Physical Review A 60(4):2746-–2751,1999
- link.aps.org/doi/10.1103/PhysRevA.60.2746

Bibtex**Author :**Christof Zalka**Title :**Grover’s quantum searching algorithm is optimal**In :**Physical Review A -**Address :****Date :**1999

*Gilles Brassard, Peter H\oyer, Alain Tapp* - **Quantum Cryptanalysis of Hash and Claw-Free Functions**

- LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings 1380:163--169,1998
- http://link.springer.de/link/service/series/0558/bibs/1380/13800163.htm

Bibtex**Author :**Gilles Brassard, Peter H\oyer, Alain Tapp**Title :**Quantum Cryptanalysis of Hash and Claw-Free Functions**In :**LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings -**Address :****Date :**1998

*Scott Aaronson* - **Quantum lower bound for the collision problem**

- Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), May 19-21, 2002, Montr{\'e}al, Qu{\'e}bec, Canada pp. 635-642,2002
- http://doi.acm.org/10.1145/509907.509999

Bibtex**Author :**Scott Aaronson**Title :**Quantum lower bound for the collision problem**In :**Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), May 19-21, 2002, Montr{\'e}al, Qu{\'e}bec, Canada -**Address :****Date :**2002

*Yaoyun Shi* - **Quantum Lower Bounds for the Collision and the Element Distinctness Problems**

- 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings pp. 513-519,2002
- http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181975

Bibtex**Author :**Yaoyun Shi**Title :**Quantum Lower Bounds for the Collision and the Element Distinctness Problems**In :**43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings -**Address :****Date :**2002

*Scott Aaronson, Yaoyun Shi* - **Quantum lower bounds for the collision and the element distinctness problems**

- J. ACM 51(4):595-605,2004
- http://doi.acm.org/10.1145/1008731.1008735

Bibtex**Author :**Scott Aaronson, Yaoyun Shi**Title :**Quantum lower bounds for the collision and the element distinctness problems**In :**J. ACM -**Address :****Date :**2004

*Lov K. Grover* - **A Framework for Fast Quantum Mechanical Algorithms**

- Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), Dallas, Texas, USA, May 23-26, 1998 pp. 53--62,1998
- http://doi.acm.org/10.1145/276698.276712

Bibtex**Author :**Lov K. Grover**Title :**A Framework for Fast Quantum Mechanical Algorithms**In :**Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), Dallas, Texas, USA, May 23-26, 1998 -**Address :****Date :**1998

*Lov K. Grover* - **Rapid sampling though quantum computing**

- Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), May 21-23, 2000, Portland, OR, USA pp. 618-626,2000
- http://doi.acm.org/10.1145/335305.335389

Bibtex**Author :**Lov K. Grover**Title :**Rapid sampling though quantum computing**In :**Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), May 21-23, 2000, Portland, OR, USA -**Address :****Date :**2000