  With the rise of AI-enabled Real-Time Deepfakes (RTDFs), the integrity of
online video interactions has become a growing concern. RTDFs have now made it
feasible to replace an imposter's face with their victim in live video
interactions. Such advancement in deepfakes also coaxes detection to rise to
the same standard. However, existing deepfake detection techniques are
asynchronous and hence ill-suited for RTDFs. To bridge this gap, we propose a
challenge-response approach that establishes authenticity in live settings. We
focus on talking-head style video interaction and present a taxonomy of
challenges that specifically target inherent limitations of RTDF generation
pipelines. We evaluate representative examples from the taxonomy by collecting
a unique dataset comprising eight challenges, which consistently and visibly
degrades the quality of state-of-the-art deepfake generators. These results are
corroborated both by humans and a new automated scoring function, leading to
88.6% and 80.1% AUC, respectively. The findings underscore the promising
potential of challenge-response systems for explainable and scalable real-time
deepfake detection in practical scenarios. We provide access to data and code
at \url{https://github.com/mittalgovind/GOTCHA-Deepfakes}.
