  Popular instant messaging applications such as WhatsApp and Signal provide
end-to-end encryption for billions of users. They rely on a centralized,
application-specific server to distribute public keys and relay encrypted
messages between the users. Therefore, they prevent passive attacks but are
vulnerable to some active attacks. A malicious or hacked server can distribute
fake keys to users to perform man-in-the-middle or impersonation attacks. While
typical secure messaging applications provide a manual method for users to
detect these attacks, this burdens users, and studies show it is ineffective in
practice. This paper presents KTACA, a completely automated approach for key
verification that is oblivious to users and easy to deploy. We motivate KTACA
by designing two approaches to automatic key verification. One approach uses
client auditing (KTCA) and the second uses anonymous key monitoring (AKM). Both
have relatively inferior security properties, leading to KTACA, which combines
these approaches to provide the best of both worlds. We provide a security
analysis of each defense, identifying which attacks they can automatically
detect. We implement the active attacks to demonstrate they are possible, and
we also create a prototype implementation of all the defenses to measure their
performance and confirm their feasibility. Finally, we discuss the strengths
and weaknesses of each defense, the overhead on clients and service providers,
and deployment considerations.
