Modeling hash functions as random oracles is a heuristic which gives some evidence that a cryptographic scheme is secure. We'll show examples of such arguments, but also show some counterintuitive results arrived at in this model. Namely, we'll show that a straighforward implementation of an RSA-based signature scheme is only loosely related (in its security) to the RSA problem, while a new scheme which essentially adds only one more bit to the signature does suddenly become as difficult as the underlying RSA problem. How can one bit change so much?