Difference between revisions of "GenericAttacksHash"

From The ECRYPT Hash Function Website
 
(11 intermediate revisions by 2 users not shown)
Line 2: Line 2:
  
 
The resistance of a hash function to collision and (second) preimage
 
The resistance of a hash function to collision and (second) preimage
−
attacks depends in the first place on the length $n$ of the hash
+
attacks depends in the first place on the length n of the hash
 
value. Regardless of how a hash function is designed, an adversary
 
value. Regardless of how a hash function is designed, an adversary
 
will always be able to find preimages or second preimages after
 
will always be able to find preimages or second preimages after
−
trying out about $2^n$ different messages. In case an adversary is
+
trying out about 2<sup>n</sup> different messages. In case an adversary is
−
given $2^k$ distinct target hashes, preimages can be found after
+
given 2<sup>k</sup> distinct target hashes, preimages can be found after
−
trying about $2^{n-k}$ different
+
trying about 2<sup>n-k</sup> different
−
messages~\cite[Chapter 2, pages 12-13]{Merkle79SecrecyAuthenticationAnd} %, chapter 2, pages 12-13}.
+
messages. This is first described in the thesis of Merkle, pages 12-13.
 +
<bibtex>
 +
@phdthesis{phdMerkle79,
 +
  author    = {Ralf C. Merkle},
 +
  title    = {Secrecy, authentication, and public key systems},
 +
  year      = {1979},
 +
}
 +
</bibtex>
  
 
= Collision attacks =  
 
= Collision attacks =  
−
As independently observed by Merkle~\cite{conf/crypto/Merkle89} and
+
As independently observed by Merkle and
−
Yuval~\cite{journal/cryptologia/Yuval79} in 1979, finding collisions
+
Yuval in 1979, finding collisions
−
requires a much smaller number of trials: about $2^{n/2}$, as
+
requires a much smaller number of trials: about 2<sup>n/2</sup>, as
−
described subsequently in Sect.~\ref{sec:birth}. As a result, hash
+
described subsequently. As a result, hash
 
functions producing less than 160 bits of output are currently
 
functions producing less than 160 bits of output are currently
 
considered inherently insecure. Moreover, if the internal structure
 
considered inherently insecure. Moreover, if the internal structure
Line 20: Line 27:
 
found more efficiently than what could be expected based on its hash
 
found more efficiently than what could be expected based on its hash
 
length, then the function is considered to be broken.
 
length, then the function is considered to be broken.
−
 
+
<bibtex>
 +
@inproceedings{cryptoMerkle89,
 +
  author    = {Ralph C. Merkle},
 +
  title    = {A Certified Digital Signature},
 +
  booktitle = {CRYPTO},
 +
  year      = {1989},
 +
  pages    = {218-238},
 +
  url        = {http://link.springer.de/link/service/series/0558/bibs/0435/04350218.htm},
 +
  editor    = {Gilles Brassard},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {435},
 +
  isbn      = {3-540-97317-6},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@article{cryptologiaYuval79,
 +
  author    = {Gideon Yuval},
 +
  title    = {How to Swindle Rabin},
 +
  journal  = {Cryptologia},
 +
  volume    = {3},
 +
  year      = {1979},
 +
  pages    = {187-189},
 +
}
 +
</bibtex>
 
=== The birthday attack ===
 
=== The birthday attack ===
 
The birthday attack (also called''square-root'' attack) is a generic attack which considers a
 
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
 
hash function as black box. Therefore, a birthday attack is
−
successful for every hash function. For any message $m$ we can
+
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
+
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
+
2<sup>-n</sup> of the pairs (m,m*) satisfies h(m) = h(m*), one can
−
expect to find a colliding message pair after trying about $2^n$
+
expect to find a colliding message pair after trying about 2<sup>n</sup>,
−
arbitrary message pairs, \cf~\eqref{eqn:collision}. Nevertheless, it
+
arbitrary message pairs. Nevertheless, it
−
follows from the birthday paradox that one can check $2^n$ pairs
+
follows from the birthday paradox that one can check 2<sup>n</sup> pairs
−
with only $2^{n/2}$ evaluations of $h$. A birthday attack works as
+
with only 2<sup>n/2</sup> evaluations of h. A birthday attack works as
 
follows:
 
follows:
−
\begin{enumerate}
+
* Pick any message m and compute h(m).
−
  \item Pick any message $m$ and compute $h(m)$.
+
* Update list L. Check if h(m) is in the list L.
−
  \item 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.
−
    \begin{itemize}
+
**    else save the pair (h(m),m) in the list L and go back to step 1.
−
        \item if $(h(m),m)$ is already in $L$, a colliding message pair has been found.
 
−
        \item else save the pair $(h(m),m)$ in the list $L$ and go back to step 1.
 
−
    \end{itemize}
 
−
\end{enumerate}
 
 
From the birthday paradox we know that we can expect to find a
 
From the birthday paradox we know that we can expect to find a
−
matching entry, after performing about $2^{n/2}$ hash evaluations.
+
matching entry, after performing about 2<sup>n/2</sup> hash evaluations.
 
Note that in a birthday attack an attacker has full control over the
 
Note that in a birthday attack an attacker has full control over the
−
messages. Hence, as pointed out by Yuval~\cite{}, this method
+
messages. Hence, as pointed out by Yuval, this method
 
enables an attacker to construct meaningful collisions.
 
enables an attacker to construct meaningful collisions.
  
−
=== Parallel collision search ===
 
  
 +
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.
 
<bibtex>
 
<bibtex>
 
@article{jocOorschotW99,
 
@article{jocOorschotW99,
 
   author    = {Paul C. van Oorschot and Michael J. Wiener},
 
   author    = {Paul C. van Oorschot and Michael J. Wiener},
−
   title    = {{Parallel Collision Search with Cryptanalytic Applications}},
+
   title    = {Parallel Collision Search with Cryptanalytic Applications},
 
   journal  = {J. Cryptology},
 
   journal  = {J. Cryptology},
 
   volume    = {12},
 
   volume    = {12},
Line 58: Line 93:
 
   pages    = {1-28},
 
   pages    = {1-28},
 
   url        = {http://link.springer.de/link/service/journals/00145/bibs/12n1p1.html},
 
   url        = {http://link.springer.de/link/service/journals/00145/bibs/12n1p1.html},
−
   abstract  = {A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in $GF(2^{155})$ thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.},
+
   abstract  = {A simple new technique of parallelizing methods for solving search problems which seek collisions in pseudorandom walks is presented. This technique can be adapted to a wide range of cryptanalytic problems which can be reduced to finding collisions. General constructions are given showing how to adapt the technique to finding discrete logarithms in cyclic groups, finding meaningful collisions in hash functions, and performing meet-in-the-middle attacks such as a known-plaintext attack on double encryption. The new technique greatly extends the reach of practical attacks, providing the most cost-effective means known to date for defeating: the small subgroup used in certain schemes based on discrete logarithms such as Schnorr, DSA, and elliptic curve cryptosystems; hash functions such as MD5, RIPEMD, SHA-1, MDC-2, and MDC-4; and double encryption and three-key triple encryption. The practical significance of the technique is illustrated by giving the design for three $10 million custom machines which could be built with current technology: one finds elliptic curve logarithms in GF2<sup>155</sup>) thereby defeating a proposed elliptic curve cryptosystem in expected time 32 days, the second finds MD5 collisions in expected time 21 days, and the last recovers a double-DES key from two known plaintexts in expected time 4 years, which is four orders of magnitude faster than the conventional meet-in-the-middle attack on double-DES. Based on this attack, double-DES offers only 17 more bits of security than single-DES.},
 
}
 
}
 
</bibtex>
 
</bibtex>
−
 
 
<bibtex>
 
<bibtex>
 
@article{jocWiener04,
 
@article{jocWiener04,
Line 74: Line 108:
 
   abstract  = {An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanksrsquo method for computing discrete logarithms in cyclic groups of prime order n, which requires $n^{1/2}+o(1)$ processor steps, but, when all factors are taken into account, has full cost n2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.},
 
   abstract  = {An open question about the asymptotic cost of connecting many processors to a large memory using three dimensions for wiring is answered, and this result is used to find the full cost of several cryptanalytic attacks. In many cases this full cost is higher than the accepted complexity of a given algorithm based on the number of processor steps. The full costs of several cryptanalytic attacks are determined, including Shanksrsquo method for computing discrete logarithms in cyclic groups of prime order n, which requires $n^{1/2}+o(1)$ processor steps, but, when all factors are taken into account, has full cost n2/3+o(1). Other attacks analyzed are factoring with the number field sieve, generic attacks on block ciphers, attacks on double and triple encryption, and finding hash collisions. In many cases parallel collision search gives a significant asymptotic advantage over well-known generic attacks.},
 
}
 
}
−
</bibtex>  
+
</bibtex>
  
 
= Attacks in the quantum setting =
 
= Attacks in the quantum setting =
Line 84: Line 118:
  
 
One of the celebrated results in quantum algorithms is
 
One of the celebrated results in quantum algorithms is
−
Grover's~\cite{Grover1996AFastQuantum} from 1996.
+
Grover's from 1996: The search for a particular element in an unordered database of size
−
%(building up on pioneering work of Deutsch, etc..~\cite{}):
+
r takes at most O(r<sup>1/2</sup>), an actual algorithm is provided. Matching lower bounds exist for this problem as
−
The search for a particular element in an unordered database of size
+
well (see Boyer et al. and Zalka). This
−
$r$ takes at most $O(r^{1/2})$, an actual algorithm is provided that
 
−
uses xxx memory. Matching lower bounds exist for this problem as
 
−
well~\cite{boyer98tight,zalka99GroversQuantumSearching}. This
 
 
algorithm is of wide interest as it does not rely on a particular
 
algorithm is of wide interest as it does not rely on a particular
 
structure of the elements in the search space.
 
structure of the elements in the search space.
Line 96: Line 127:
 
There, the search for a preimage or a second preimage is at most as
 
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
 
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}$
+
these types of generic attacks is lowered from 2<sup>n</sup> to 2<sup>n/2</sup>
 
in the quantum setting.
 
in the quantum setting.
  
Line 102: Line 133:
 
that many collisions exist and the problem is to find a single one
 
that many collisions exist and the problem is to find a single one
 
indeed leads to (both asymptotically and for commonly used finite
 
indeed leads to (both asymptotically and for commonly used finite
−
dimensions\todo{better wording than finite dim. needed!}) faster
+
dimensions) faster
 
algorithms. An actual quantum algorithm for the collision problem is
 
algorithms. An actual quantum algorithm for the collision problem is
 
due to Brassard, H{\o}yer, and
 
due to Brassard, H{\o}yer, and
−
Tapp~\cite{DBLP:conf/latin/BrassardHT98} from 1997. This combination
+
Tapp from 1997. This combination
−
of Grover's algorithm with the birthday effect yields a runtime of
+
of Grover's algorithm with the birthday effect yields a runtime of 2<sup>n/3</sup> for a hash function with n bit output size. The
−
$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
−
algorithm requires $\Theta(n^{1/3}$log $n)$ classical bits of
 
 
memory. To the best of the author's knowledge, no time/memory
 
memory. To the best of the author's knowledge, no time/memory
 
tradeoffs are known. Is this the best one can do? Nontrivial lower
 
tradeoffs are known. Is this the best one can do? Nontrivial lower
 
bounds for the collision problem were an open problem for some time.
 
bounds for the collision problem were an open problem for some time.
−
Only in 2001, Aaronson~\cite{DBLP:conf/stoc/Aaronson02} proved a
+
Only in 2001, Aaronson proved a
−
query complexity of $\Omega(n^{1/5})$. Subsequent work of Shi
+
query complexity of <math>\Omega(n^{1/5})</math>. Subsequent work of Shi
−
improved this bound to $\Omega(n^{1/4})$ and finally to
+
improved this bound to <math>\Omega(n^{1/4})</math> and finally to
−
$\Omega(n^{1/3})$(\cite{DBLP:conf/focs/Shi02,DBLP:journals/jacm/AaronsonS04}).
+
<math>\Omega(n^{1/3})</math>. As this constitutes a tight bound, indeed one can not do better than
−
As this constitutes a tight bound, indeed one can not do better than
+
Brassard et al. That is, given our current axiomatic assumptions
−
Brassard~\etal. That is, given our current axiomatic assumptions
 
 
about the nature of quantum mechanics.
 
about the nature of quantum mechanics.
  
Line 129: Line 158:
 
of the story, dedicated quantum cryptanalytic techniques have not
 
of the story, dedicated quantum cryptanalytic techniques have not
 
been considered yet. Fast quantum algorithms to compute median and
 
been considered yet. Fast quantum algorithms to compute median and
−
mean values~\cite{DBLP:conf/stoc/Grover98}, and other basic building
+
mean values by Grover, and other basic building
 
blocks seem to be an interesting starting point.
 
blocks seem to be an interesting starting point.
 +
 +
<bibtex>
 +
@inproceedings{Grover1996AFastQuantum,
 +
  author    = {Lov K. Grover},
 +
  title    = {A Fast Quantum Mechanical Algorithm for Database Search},
 +
  booktitle = {Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC), Philadelphia, Pennsylvania, USA, May 22-24, 1996},
 +
  publisher = {ACM},
 +
  year      = {1996},
 +
  pages    = {212--219},
 +
  abstract  = {Anunsorted database contains N records, of which just
 +
one satisfies a particular property. The problem is to
 +
identify that one record. Any classical algorithm, deterministic
 +
or probabilistic, will clearly take O (N) steps
 +
since on the average it will have to examine a large fraction
 +
of the N records. Quantum mechanical systems can
 +
do several operations simultaneously due to their wave
 +
like properties. This paper gives an O ( JN) step quantum
 +
mechanical algorithm for identifying that record. It
 +
is within a constant factor},
 +
  url        = {http://doi.acm.org/10.1145/237814.237866},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@article{boyer96tight,
 +
    author = {Michel Boyer and Gilles Brassard and Peter H{\o}yer and Alain Tapp},
 +
    title = {Tight bounds on quantum searching},
 +
    number = "PP-1996-11", month = "30,", year = "1996", url = "citeseer.ist.psu.edu/article/boyer98tight.html" } @article{boyer98tight, author    = {Michel Boyer and Gilles Brassard and Peter H{\o}yer and Alain Tapp},
 +
  title    = {Tight bounds on quantum searching},
 +
  journal  = {Fortschritte der Physik},
 +
abstract  = {We provide a tight analysis of Grover’s recent algorithm for quantum database searching. We give
 +
a simple closed-form formula for the probability of success after any given number of iterations of
 +
the algorithm. This allows us to determine the number of iterations necessary to achieve almost
 +
certainty of finding the answer. Furthermore, we analyse the behaviour of the algorithm when the
 +
element to be found appears more than once in the table and we provide a new algorithm to find such
 +
an element even when the number of solutions is not known ahead of time. Using techniques from
 +
Shor’s quantum factoring algorithm in addition to Grover’s approach, we introduce a new technique
 +
for approximate quantum counting, which allows to estimate the number of solutions. Finally we
 +
provide a lower bound on the efficiency of any possible quantum database searching algorithm and
 +
we show that Grover’s algorithm nearly comes within a factor 2 of being optimal in terms of the
 +
number of probes required in the table.}, 
 +
  volume    = {46},
 +
  year      = {1998},
 +
  pages    = {493-505},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@article{praZalka99,
 +
  author    = {Christof Zalka},
 +
  title    = {Grover’s quantum searching algorithm is optimal},
 +
  journal  = {Physical Review A},
 +
  volume    = {60},
 +
  number    = {4},
 +
  year      = {1999},
 +
  url      = {link.aps.org/doi/10.1103/PhysRevA.60.2746},
 +
  abstract  = {I show that for any number of oracle lookups up to about p/4 sqrt[N], Grover’s quantum searching algorithm gives the maximal possible probability of finding the desired element. I explain why this is also true for quantum algorithms which use measurements during the computation. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers.},
 +
  pages    = {2746-–2751},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{latinBrassardHT98,
 +
  author    = {Gilles Brassard and Peter H{\o}yer and Alain Tapp},
 +
  title    = {Quantum Cryptanalysis of Hash and Claw-Free Functions},
 +
  booktitle = {LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings},
 +
  editor    = {Claudio L. Lucchesi and Arnaldo V. Moura},
 +
  year      = {1998},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  volume    = {1380},
 +
  pages    = {163--169},
 +
  url        = {http://link.springer.de/link/service/series/0558/bibs/1380/13800163.htm},
 +
  editor    = {Claudio L. Lucchesi and Arnaldo V. Moura},
 +
  publisher = {Springer},
 +
  series    = {LNCS},
 +
  abstract  = {We give a quantum algorithm that finds collisions in arbitrary r-to-one functions after only  expected evaluations of the function, where N is the cardinality of the domain. Assuming the function is given by a black box, this is more efficient than the best possible classical algorithm, even allowing probabilism. We also give a similar algorithm for finding claws in pairs of functions. Further, we exhibit a space-time tradeoff for our technique. Our approach uses Grover's quantum searching algorithm in a novel way.},
 +
  volume    = {1380},
 +
  isbn      = {3-540-64275-7},
 +
  isbn      = {3-540-64275-7},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{stocAaronson02,
 +
  author    = {Scott Aaronson},
 +
  title    = {Quantum lower bound for the collision problem},
 +
  booktitle = {Proceedings on 34th Annual ACM Symposium on Theory of Computing (STOC), May 19-21, 2002, Montr{\'e}al, Qu{\'e}bec, Canada},
 +
  publisher = {ACM},
 +
  year      = {2002},
 +
  pages    = {635-642},
 +
  abstract  = {The collision problem is to decide whether a function X :
 +
{1, . . . , n} ? {1, . . . , n} is one-to-one or two-to-one, given
 +
that one of these is the case. We show a lower bound of
 +
O�n1/5� on the number of queries needed by a quantum
 +
computer to solve this problem with bounded error probability.
 +
The best known upper bound is O�n1/3�, but
 +
obtaining any lower bound better than O(1) was an open
 +
problem since 1997. Our proof uses the polynomial method
 +
augmented by some new ideas. We also give a lower bound
 +
of O�n1/7�for the problem of deciding whether two sets are
 +
equal or disjoint on a constant fraction of elements. Finally
 +
we give implications}, 
 +
  url        = {http://doi.acm.org/10.1145/509907.509999},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{focsShi02,
 +
  author    = {Yaoyun Shi},
 +
  title    = {Quantum Lower Bounds for the Collision and the Element Distinctness Problems},
 +
  booktitle = {43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings},
 +
  publisher = {IEEE Computer Society},
 +
  year      = {2002},
 +
  isbn      = {0-7695-1822-2},
 +
  pages    = {513-519},
 +
  abstract  = {Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i) = f(j) under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r -to-one function must evaluate the function \Omega (({n \mathord{\left/ {\vphantom {n r}} \right. \kern-\nulldelimiterspace} r}){1 \mathord{\left/ {\vphantom {1 {3)}}} \right. \kern-\nulldelimiterspace} {3)}} times, where n is the size of the domain and {r \mathord{\left/ {\vphantom {r n}} \right. \kern-\nulldelimiterspace} n}. This lower bound matches, up to a constant factor, the upper bound of Brassard, Høyer, and Tapp [ACM SIGACT News, 28:14-19, 1997], which uses the quantum algorithm of Grover [Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212-219, 1996] in a novel way. The previously best quantum lower bound is \Omega (({n \mathord{\left/ {\vphantom {n {r)^{{1 \mathord{\left/ {\vphantom {1 5}} \right. \kern-\nulldelimiterspace} 5}} }}} \right. \kern-\nulldelimiterspace} {r)^{{1 \mathord{\left/ {\vphantom {1 5}} \right. \kern-\nulldelimiterspace} 5}} }}) evaluations, due to Aaronson [Proceedings of the Thirty-Fourth Annual ACM Symposium on the Theory of Computing, pages 635-642, 2002]. Our result implies a quantum lower bound of \Omega (n^{{2 \mathord{\left/ {\vphantom {2 3}} \right. \kern-\nulldelimiterspace} 3}}) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is \Omega (\sqrt n ) queries in the black-box model; and \Omega (\sqrt n \log n) comparisons in the comparisons-only model, due to Høyer, Neerbek, and Shi [Lecture Notes in Computer Science, Vol. 2076, pp. 346-357, 2001].},
 +
  url        = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181975},
 +
  publisher = {IEEE Computer Society},
 +
  isbn      = {0-7695-1822-2},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@article{jacmAaronsonS04,
 +
  author    = {Scott Aaronson and Yaoyun Shi},
 +
  title    = {Quantum lower bounds for the collision and the element distinctness problems},
 +
  journal  = {J. ACM},
 +
  volume    = {51},
 +
  number    = {4},
 +
  year      = {2004},
 +
  pages    = {595-605},
 +
  abstract  = {Given a function f as an oracle, the collision problem is to find two distinct indexes
 +
i and j such that f (i ) D f ( j ), under the promise that such indexes exist. Since the security of
 +
many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower
 +
bounds provide evidence for the existence of cryptographic primitives that are immune to quantum
 +
cryptanalysis. We prove that any quantum algorithm for finding a collision in an r-to-one function
 +
must evaluate the function Ä((n=r )1=3) times, where n is the size of the domain and r jn. This matches
 +
an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously
 +
known. Our result also implies a quantum lower bound of Ä(n2=3) queries for the element distinctness
 +
problem, which is to determine whether n integers are all distinct. The best previous lower bound was
 +
Ä(pn) queries.},
 +
  url        = {http://doi.acm.org/10.1145/1008731.1008735},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{stocGrover98,
 +
  author    = {Lov K. Grover},
 +
  title    = {A Framework for Fast Quantum Mechanical Algorithms},
 +
  booktitle = {Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC), Dallas, Texas, USA, May 23-26, 1998},
 +
  publisher = {ACM},
 +
  year      = {1998},
 +
  pages    = {53--62},
 +
  abstract  = {A framework is presented for the design and analysis
 +
of quantum mechanical algorithms, the 0( fi) step
 +
quantum search algorithm is an immediate consequence
 +
of this framework. It leads to several other search-type
 +
applications - an example is presented where the Walsh-
 +
Hadamard (W-H) transform of the quantum search algorithm
 +
is replaced by another transform tailored to the
 +
parameters of the problem. Also, it leads to quantum
 +
mechanical algorithms for problems not immediately
 +
connected with search - two such algorithms are presented
 +
for calculating the mean and median of statistical
 +
distributions. In order to classically estimate either the
 +
mean or median of a given distribution to a precision E ,
 +
needs a(~-~) steps. The best known quantum mechanical
 +
algorithm for estimating the median takes O(E-‘)
 +
steps, and that for estimating the mean takes O(E -1.5 )
 +
steps. This paper presents O(E-l) step algorithms for
 +
both problems (all bounds are upto polylogarithmic factors).
 +
Both algorithms are considerably simpler than
 +
known algorithms.},
 +
  url        = {http://doi.acm.org/10.1145/276698.276712},
 +
}
 +
</bibtex>
 +
<bibtex>
 +
@inproceedings{stocGrover00,
 +
  author    = {Lov K. Grover},
 +
  title    = {Rapid sampling though quantum computing},
 +
  booktitle = {Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC), May 21-23, 2000, Portland, OR, USA},
 +
  publisher = {ACM},
 +
  year      = {2000},
 +
  pages    = {618-626},
 +
  abstract  = {This paper extends the quantum search class of
 +
algorithms to the multiple solution case. It is shown that,
 +
like the basic search algorithm, these too can be represented
 +
as a rotation in an appropriately defined two
 +
dimensional vector space. This yields new applications -
 +
an algorithm is presented that can create an arbitrarily
 +
specified quantum superposition on a space of size N in
 +
o(4r-N) steps. By making a measurement on this superposition,
 +
it is possible to obtain a sample according to an
 +
arbitrarily specified classical probability distribution in
 +
O(,f-N) steps. A classical algorithm would need f2(N)
 +
steps.},
 +
  url        = {http://doi.acm.org/10.1145/335305.335389},
 +
}
 +
</bibtex>

Latest revision as of 13:33, 25 March 2008

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 2n different messages. In case an adversary is given 2k distinct target hashes, preimages can be found after trying about 2n-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 2n/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 calledsquare-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 2n, arbitrary message pairs. Nevertheless, it follows from the birthday paradox that one can check 2n pairs with only 2n/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 2n/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(r1/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 2n to 2n/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 2n/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
Retrieved from "https://ehash.iaik.tugraz.at/index.php?title=GenericAttacksHash&oldid=1974"