Randy: A Secure One-Time Pad Cryptosystem for Communication in Extreme Adversarial Settings

Abstract

Most modern encryption schemes provide security contingent on one or more conjected but unproven computational hardness assumptions, implying that future algorithmic and technological advances might render existing ciphertexts insecure. The security guarantees of the venerable one-time pad (OTP) encryption scheme, by contrast, are information-theoretic and wholly unconditioned on unproven assumptions. Yet, despite the allure of ``unconditional'' security, sampling and managing the required randomness is so fraught that practitioners rarely employ OTP encryption in the wild---even in scenarios where long-term secrecy is paramount. Randy is an architecture and protocol suite that provides passphrase-authenticated and OTP-encrypted sockets suitable for communicating securely in ultrahigh-stakes adversarial environments where the adversary is assumed to be computationally unbounded. The Randy architecture centers around a shared randomness pool stored on a securely deletable storage device. This thesis aims to enhance the security and reliability of Randy's model through a comprehensive analysis. The existing model is thoroughly examined to identify weaknesses and vulnerabilities, which serve as the foundation for further improvements. To address these identified weaknesses, a secure and reliable synchronization scheme is proposed to ensure the security of the cryptosystem. Additionally, we introduce various techniques to manage and reduce randomness exhaustion in Randy. These techniques aim to improve the availability of the system by preserving the padding materials. Finally, we implement our design as a Linux kernel module that allows existing applications to seamlessly use Randy to provide unconditionally secure mutual authentication, message integrity, and secrecy for all messages. This implementation showcases the practicality of the model and highlights its security and functionality features. We analyze the security of our design and present empirical measurements from a prototype implementation thereof.