Question on the CPA-security proof of the CTR-Mode
The problem is with your statement &quot;There is no overlap and A probability to win is $1/2$, because the PRF is secure.&quot; What does that mean? The only way to formalize that is to show that if adversary wins with probability greater than $1/2$ when there is no overlap, then you can break the PRF. That is essentially what the proof does. Note that it doesn't have to be by contradiction - it's also possible to show that when there is no overlap, then a reduction to distinguishing the PRF from random shows that the gap is negligible. That is the way the proof written in the book works.