20
$\begingroup$

Since most cryptographic hash functions are simple, compact constructions does this simplicity impose a limit on the complexity and the size of a function that can generate preimages? That is, given a cryptographic hash function, H of some length and complexity can we lower or upper bound the complexity/size of a function that finds preimages of H. If not, why not?

If the upper bound on the size of a function that efficiently finds a preimage of H is smaller than the output size of H and then this has implications for the strength of the hash function. How can we justify that such an efficient preimage finding function must be larger than the output size?

Improve this question
$\endgroup$
7
  • $\begingroup$ What means an efficient preimage finding function must be larger than the output size? Do you mean time-complexity here instead of size of function? $\endgroup$
    – Paŭlo Ebermann
    Jul 15, 2011 at 0:19
  • $\begingroup$ @Paulo Ebermann - I mean that if an efficient preimage finding function is smaller in number of bits than the output size of the hash function then one could guess the preimage finding function faster than one could guess the preimage thereby breaking the hash function. By efficient, I mean a that the preimage function finds the preimage in roughly the same time as the hash function generates an output (that is the preimage function is an inversion of the hash function and not just a program that guesses at preimages). $\endgroup$
    – Ethan Heilman
    Jul 15, 2011 at 12:36
  • $\begingroup$ I just don't understand the concept of size for a function, sorry. Size of (input) domain? Size of output? Time/space needed to execute an implementation? $\endgroup$
    – Paŭlo Ebermann
    Jul 15, 2011 at 12:40
  • $\begingroup$ @Paulo Ebermann - The minimum number of bits that is required to describe a function. For example machine code can be used to describe a particular mapping from one set of integers to another. Given a hash function H, that is encoded using language L, can you find another function P such that P inverts H in the same time/memory complexity as H and that P encoded in L is smaller than the output size of H (the encoded description of P is smaller than the output size of H). $\endgroup$
    – Ethan Heilman
    Jul 15, 2011 at 12:56
  • 1
    $\begingroup$ @Paulo Ebermann - Consider a less efficient function LP, that is essentially a mapping of all $2^n$ possible outputs to inputs. Such a function can find preimages in O(1) time, but requires 2^n space. Now compress this mapping into less than 2^n. Thus, for every hash function H there must exist an inverter function that finds preimages cheaper than brute force. All hash functions are "broken" the trick is discovering the function that breaks the hash function. If such a preimage finding function is too big, discovering it by brute force is hard. $\endgroup$
    – Ethan Heilman
    Jul 15, 2011 at 14:37

2 Answers 2

Reset to default
9
$\begingroup$

Cryptographic hash functions (like everything else a traditional computer does) can be described as a set of binary operations, XOR, register rotate, and binary addition being very common. These translate directly to a classic computer science problem known as "binary satisfiability" or SAT.

SAT problem has been proven NP-complete. To butcher the definition of this sublime mathematical concept, it means that there's no known algorithm which can solve the puzzle without the number of puzzle pieces ending up in an exponent somewhere describing the amount of work it will take. Crypto algorithms try to jack that exponent up into the tens of thousands or more.

There are, of course, any number of ways that any actual function might have weaknesses which cause it to not present such a worst-case problem for the attacker. But cryptographers have amassed a body of knowledge for assessing the security of algorithms beyond their outward number of bits. All but the most ancient crypto functions are out of reach of today's best SAT solvers.

But then P != NP hasn't really been proven now, has it? :-)

Improve this answer
$\endgroup$
3
  • $\begingroup$ +1 Interesting. Are there any research papers that you would recommend that use proof of resistance to 3SAT to argue the strength of various hash functions/ciphers? $\endgroup$
    – Ethan Heilman
    Aug 5, 2011 at 14:38
  • 1
    $\begingroup$ Sure, eprint.iacr.org/2006/254 and eprint.iacr.org/2010/285 for example. What's most interesting though is how the attitudes towards SAT seems to have changed in just 4 years. From (literally) "We expect SAT solvers to find new applications as a validation and testing tool of practicing cryptanalysts" to "We found preimages for some reduced versions and showed that full function is secure against the presented attack." $\endgroup$
    – Marsh Ray
    Aug 6, 2011 at 4:23
  • 7
    $\begingroup$ This only says if SAT is easy (i.e. P=NP), then all hash functions are broken, not the other way around (if SAT is hard, then hash functions are good). $\endgroup$
    – Paŭlo Ebermann
    Oct 12, 2011 at 22:27
13
$\begingroup$

The general justification is several years of cryptographic research in trying to "break" hash functions. As far as I know there is no "proof" that finding pre-images of a hash are hard. It is just assumed to be hard based on the history of effort trying to invert it. A hash function considered secure today may well turn out to be weak tomorrow.

This paper (ONE-WAY FUNCTIONS AND CIRCUIT COMPLEXITY) might be of help in understanding the relationship between circuit complexity and one-way functions.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I know that there are functions that are justifiably hard to invert given a under a particular a mathematical assumption (discrete log problem as done in the paper provided). Most cryptographic hash functions do not use such assumptions, yet in practice they appear to be hard to invert. What is the thinking on why this is? Is the conventional wisdom that some mysterious one way property is hiding in xor-rotations and GF s-boxes? $\endgroup$
    – Ethan Heilman
    Jul 12, 2011 at 20:19
  • 1
    $\begingroup$ The difference is more on the underlying primitives you call as "mathematical". A discrete log problem is as mathematical (IMO) as the "fuzzy" problems involved in hash functions. The reason (as you probably know) for using such fuzzy security is efficiency. It is much faster to use a SHA256 than to use a DL based hash. $\endgroup$
    – Jus12
    Jul 12, 2011 at 20:29
  • $\begingroup$ What are the philosophical underpinnings of 'fuzzy' or 'cowboy' cryptography that attempt to explain why it is hard to break. While there is probably no known hard-science theory that explains why SHA2 hasn't been broken yet, there may be explanations in philosophy or other softer fields. What are the stories cryptographers tell themselves about why SHA2 provides resistance to attempts to break it? $\endgroup$
    – Ethan Heilman
    Jul 13, 2011 at 17:50
  • 2
    $\begingroup$ @EthanHeilman I think confusion and diffusion is the best argument for symmetric crypto (i.e. hashes, block ciphers and stream ciphers). $\endgroup$
    – Paŭlo Ebermann
    Oct 12, 2011 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.