Secure authentication and key agreement via abstract multi-agent interaction
Ahmed, Ibrahim Hassan
Authentication and key agreement are the foundation for secure communication over the Internet. Authenticated Key Exchange (AKE) protocols provide methods for communicating parties to authenticate each other, and establish a shared session key by which they can encrypt messages in the session. Within the category of AKE protocols, symmetric AKE protocols rely on pre-shared master keys for both services. These master keys can be transformed after each session in a key-evolving scheme to provide the property of forward secrecy, whereby the compromise of master keys does not allow for the compromise of past session keys. This thesis contributes a symmetric AKE protocol named AMI (Authentication via Multi-Agent Interaction). The AMI protocol is a novel formulation of authentication and key agreement as a multi-agent system, where communicating parties are treated as autonomous agents whose behavior within the protocol is governed by private agent models used as the master keys. Parties interact repeatedly using their behavioral models for authentication and for agreeing upon a unique session key per communication session. These models are evolved after each session to provide forward secrecy. The security of the multi-agent interaction process rests upon the difficulty of modeling an agent's decisions from limited observations about its behavior, a long-standing problem in AI research known as opponent modeling. We conjecture that it is difficult to efficiently solve even by a quantum computer, since the problem is fundamentally one of missing information rather than computational hardness. We show empirically that the AMI protocol achieves high accuracy in correctly identifying legitimate agents while rejecting different adversarial strategies from the security literature. We demonstrate the protocol's resistance to adversarial agents which utilize random, replay, and maximum-likelihood estimation (MLE) strategies to bypass the authentication test. The random strategy chooses actions randomly without attempting to mimic a legitimate agent. The replay strategy replays actions previously observed by a legitimate client. The MLE strategy estimates a legitimate agent model using previously observed interactions, as an attempt to solve the opponent modeling problem. This thesis also introduces a reinforcement learning approach for efficient multi-agent interaction and authentication. This method trains an authenticating server agent's decision model to take effective probing actions which decrease the number of interactions in a single session required to successfully reject adversarial agents. We empirically evaluate the number of interactions required for a trained server agent to reject an adversarial agent, and show that using the optimized server leads to a much more sample-efficient interaction process than a server agent selecting actions by a uniform-random behavioral policy. Towards further research on and adoption of the AMI protocol for authenticated key-exchange, this thesis also contributes an open-source application written in Python, PyAMI. PyAMI consists of a multi-agent system where agents run on separate virtual machines, and communicate over low-level network sockets using TCP. The application supports extending the basic client-server setting to a larger multi-agent system for group authentication and key agreement, providing two such architectures for different deployment scenarios.