Why is the Fiat-Shamir heuristic deemed secure in the ROM? In their paper On the (In)security of the Fiat-Shamir Paradigm, Goldwasser and Tauman show that the Fiat-Shamir heuristic does not work with any hash function. From the paper:


  The most important question however remained open: are the digital signatures produced by the Fiat-Shamir methodology secure? In this paper, we answer this question negatively. 


However, they do state that it is secure in the random oracle model:


  [Pointcheval and Stern] proved that for every 3-round public-coin identification protocol, which is zero-knowledge with respect to an honest verifier, the signature scheme, obtained by applying the Fiat-Shamir transformation, is secure in the Random Oracle Model.


I'm confused because it seems to me that they then (in my opinion) go on to show that the Fiat-Shamir heuristic is never secure, not even in the random oracle model.

From the paper:


  Intuitively, the idea is to take any secure 3-
  round public-coin identification scheme (which is not necessarily zero-knowledge) and extend
  its verdict function so that the verifier also accepts views which convince him that the prover
  knows the verifier’s next message. Since the verifier chooses the next message at random,
  there is no way that the prover can guess the verifier’s next message during a real interaction,
  except with negligible probability, and therefore the scheme remains secure. However, when
  the identification scheme is converted into a signature scheme, by applying the Fiat-Shamir paradigm, the “verifier’s next message” is computed by a public function which is chosen at
  random from some function ensemble and is known in advance to everyone. A forger, who
  will now know in advance the “verifier’s next message” on any input, will be able to generate
  an accepting view for the verifier. This makes the signature scheme insecure regardless of
  which function ensemble is used to compute the “verifier’s next message” in the identification
  scheme.


Doesn't this also work in the random oracle model? It seems to me that this is attacking the very concept of replacing new randomness by anything (except pseudorandomness), be it hash obtained by evaluating a hash function, or actual randomness chosen by the random oracle (but available in advance, so not new randomness).

Instead of evaluating the hash function on the arguments relevant for the randomness substitute, the prover can ask the random oracle for the hash. Sure, this will be true randomness, but the verifier will get the same randomness from the random oracle in the next step, so the prover still knows in advance what "random" value the verifier will choose.
The paper by Goldwasser and Tauman is another paper in the series of the failure of the random oracle model; its novelty is applying this principle to the Fiat-Shamir paradigm and interactive protocols. However, an easier place to start is the seminal paper of Canetti, Goldreich and Halevi, called The Random Oracle Methodology, Revisited. This paper shows that there exist signature and encryption schemes that are secure in the random oracle model, but fail for every concrete instantiation, for any hash function. They prove this by carefully constructing a scheme that will fail for any hash function instantiation. Their proof does not work in the random-oracle model (as with Goldwasser and Tauman) since the description of the hash function does not exist when it's a random oracle (it's certainly not polynomial size). 

It's important to understand what this actually proves. The theorem proven shows that it is impossible to generically replace the random oracle with a hash function. That is, there does not exist any hash function that can be used to replace the random oracle in every construction, in order to get a proof in the standard model. Furthermore, there exist constructions that cannot be proven secure in the standard model at all, for any hash function. Thus, the random oracle model is not "sound" in the sense that it cannot always be a stepping stone to a standard-model proof.

What this does not say is that there are no random-oracle constructions that can be proven secure in the standard model. Since my previous double-negative sentence will surely be confusing, I'll explain. There may exist schemes that are proven secure in the random oracle and can be instantiated with a concrete hash function. These proofs do not state that this is impossible. Thus, it is theoretically possible that a hash function can be found to instantiate RSA-OAEP to be secure in the standard model, and it is theoretically possible that a hash function can be found to instantiate Fiat-Shamir on Schnorr's protocol specifically so that the result is a secure signature scheme in the standard model (I may be wrong, but I don't think that this has been proven to be impossible). To be honest, it is very unlikely that this is the case (at least in my opinion), but this hasn't been ruled out.