Not understanding deterministic authenticated encryption (DAE) security definition
As I wrote in a comment, the reason your proposed attack does not work is that the random oracle also returns the same result when queried with the same input.
The ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say &quot;uniform random function&quot; rather than &quot;random-bits oracle&quot;. For example, see Definition 1 in this paper.