6
$\begingroup$

I was looking for more realistic alternatives to the ROM for describing hash functions in theoretical proofs. I came across the common reference string model (where hash functions can be modeled as having been picked from a family of functions). Are there any other?

EDIT -- To make my question less vague: It seemed to me that the ROM or CRS was not modeling what a hash function is in reality and so proofs of security in the ROM model were problematic (considering all real hash functions are deterministic, keyless, and WILL always have collisions that can be found -- facts ignored by ROM and CRS). So I was looking for alternatives.

David Cash pointed out the Rogaway paper that deals exactly with the problem I'd been having. His reply below summarizes how the paper deals with this issue -- i.e., by requiring the explicit knowledge of the collision finding algorithm by an adversary.

$\endgroup$
5
  • 5
    $\begingroup$ Perhaps you are looking for standard notions for security for hash functions, like collision resistance, target collision resistance, and so on. Googling should turn up many sources for these. If you are referring to the issue that real hash functions are not usually keyed, then this paper may be interesting to you: cs.ucdavis.edu/~rogaway/papers/ignorance.pdf. For cryptographic purposes one can also get by with universal hashes and variants in certain settings. $\endgroup$
    – David Cash
    Commented Feb 6, 2013 at 21:11
  • $\begingroup$ Actually now that I've read it, that paper is exactly what I was looking for! Thank you so much! $\endgroup$
    – RDN
    Commented Feb 7, 2013 at 17:04
  • 1
    $\begingroup$ @DavidCash: Could you make your comment an answer?? $\endgroup$
    – Jeffε
    Commented Feb 7, 2013 at 18:13
  • $\begingroup$ Sure. Though I'm still not sure how the question jives with the subsequent comments. $\endgroup$
    – David Cash
    Commented Feb 7, 2013 at 19:31
  • $\begingroup$ rmx-sha256 is a real hash function that is not [deterministic and keyless]. $\:$ ROM doesn't ignore that real hash functions "WILL always have collisions that can be found" since (fully) non-uniform adversaries can find collisions in the oracle. $\:$ (This is as opposed to partially non-uniform adversaries, whose advice is not allowed to depend on the oracle.) $\hspace{1.2 in}$ $\endgroup$
    – user6973
    Commented Feb 8, 2013 at 23:59

1 Answer 1

9
$\begingroup$

(I am interpreting this question in the following way due to the comments.) In implementations of cryptographic systems, hash functions like the SHA-256 are defined by a deterministic algorithm mapping arbitrary-length bit-strings to some fixed-length bit-strings. This situation is troublesome for formal analyses (reductions) of these systems because, when modeled in the straightforward way, there is no obvious way to "assume" some important security notions like collision-resistance for such functions. To be explicit, we might take a function $H:\{0,1\}^* \rightarrow \{0,1\}^{256}$ and say that

$H$ is collision-resistant if no probabilistic poly-time algorithm outputs distinct $x,y$ such that $H(x) = H(y)$.

Under this definition, no function $H$ is collision resistant: By the pigeon-hole principle such an $x,y$ exists, and there also exists a constant-time algorithm that outputs them. (We're leaving aside the additional problem that "probabilistic poly-time" is ill-defined here.) Most modifications of the definition, like asking for long $x,y$ or something, are unsatisfying. Let me mention also that some properties are (I believe) achievable, such as when the $x$ is chosen at random and the adversary has to find a $y$ that collides.

But if one models the hash as a keyed function that take an additional key input, then these security notions can be plausibly assumed to be achieved. Thus we often give security reductions where a keyed hash function is used and random hash key is chosen in the model. Though this is incongruous with reality, it seems fine.

To better address this disparity, Rogaway in suggested that we forget about the formal assumption per se and instead focusing on the existence of an explicit reduction to doing something with the hash function. This is exploiting the fact that we apparently don't "know" of an algorithm finding collisions in SHA-256, even though there is a "constant-time" algorithm for doing exactly that.

By the way, the random oracle model generally addresses a different issue: sometimes we don't have any way to reduce security to any reasonable property of our (keyed or keyless) hash function, so we instead analyze the system in a model where the evaluations of the hash are replaced by evaluations of a random oracle (which everyone can access). Incidentally, doing this also makes the hash appear to be keyless and thus superficially "closer to reality," but this is in fact not the case: Now the entire function has become the key, and indeed an exponentially long key.

$\endgroup$
2
  • $\begingroup$ "when the $x$ is chosen at random and the adversary has to find a $y$ that collides", $\hspace{1.3 in}$ the adversary is attacking second-preimage resistance. $\:$ $\endgroup$
    – user6973
    Commented Feb 9, 2013 at 0:02
  • $\begingroup$ @RickyDemer Yes that is the informal notion that corresponds to what I was talking about. $\endgroup$
    – David Cash
    Commented Feb 9, 2013 at 6:23

Your Answer

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

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