**Abstract:** To formalize participants in cryptographic protocols, it is common to use probabilistic
Turing machines. We point out subtleties in common definitions of probabilistic
Turing machines, which imply that the common cryptographic operation of uniform
random sampling in a finite set {1,...,s}⊆Z is in general not possible within
this model. From a technical point of view, this invalidates in particular a standard
proof of the perfect zero knowledge property of the popular graph isomorphism
proof system. The observed limitation appears to be relevant for other cryptographic
protocol analyses as well, and we suggest one possible tweak of the definition
of a probabilistic Turing machine.