Many cryptographic applications of hash functions are analyzed in the random oracle model. Unfortunately, most concrete hash functions, including the SHA family, use the iterative (strengthened) Merkle-Damgård transform applied to a corresponding compression function. Moreover, it is well known that the resulting "structured" hash function cannot be generically used as a random oracle, even if the compression function is assumed to be ideal. This leaves a large disconnect between theory and practice: although no attack is known for many concrete applications utilizing existing (Merkle-Damgård based) hash functions, there is no security guarantee either, even by idealizing the compression function. Motivated by this question, we initiate a rigorous and modular study of developing new notions of (still idealized) hash functions which would be (a) natural and elegant; (b) sufficient for arguing security of important applications; and (c) provably met by the (strengthened) Merkle- Damgård transform, appli to a "strong enough" compression function. In particular, we develop two such notions satisfying (a)-(c): a preimage aware function ensures that the attacker cannot produce a "useful" output of the function without already "knowing" the corresponding preimage, and a public-use random oracle, which is a random oracle that reveals to attackers messages queried by honest parties.