Constructing a Pseudo Random Function (PRF) from a pseudorandom permutation is a fundamental problem in cryptology. Such a construction, implemented by truncating the last m bits of permutations of \(\{0, 1\}^{n}\) was suggested by Hall et al. (1998). They conjectured that the distinguishing advantage of an adversary with q quesires, \(\mathbf{Adv}_{n, m} (q)\), is small if \(q = o (2^{(m+n)/2})\), established an upper bound on \(\mathbf{Adv}_{n, m} (q)\) that confirms the conjecture for \(m < n/7\), and also declared a general lower bound \(\mathbf{Adv}_{n,m}(q)=\varOmega (q^2/2^{n+m})\). The conjecture was essentially confirmed by Bellare and Impagliazzo in 1999. Nevertheless, the problem of estimating \(\mathbf{Adv}_{n, m} (q)\) remained open. Combining the trivial bound 1, the birthday bound, and a result by Stam (1978) leads to the following upper bound: $$\mathbf{Adv}_{n,m}(q) \le O\left( \min \left\{ \frac{q^2}{2^n},\,\frac{q}{2^{\frac{n+m}{2}}},\,1\right\} \right) $$ This upper bound shows that the number of times that a truncated permutation can be used as a PRF can exceed the birthday bound by at least a factor of \(2^{m/2}\). In this paper we show that this upper bound is tight for every \(m 1\). This, in turn, verifies that the converse to the conjecture of Hall et al. is also correct, i.e., that \(\mathbf{Adv}_{n, m} (q)\) is negligible only for \(q = o (2^{(m+n)/2})\).