Steven M. Bellovin. Vernam, Mauborgne, and Friedman: The one-time pad and the index of coincidence. Technical Report CUCS-014-14, Department of Computer Science, Columbia University, May 2014. [ bib | http ]
The conventional narrative for the invention of the AT&T one-time pad was related by David Kahn. Based on the evidence available in the AT&T patent files and from interviews and correspondence, he concluded that Gilbert Vernam came up with the need for randomness, while Joseph Mauborgne realized the need for a non-repeating key. Examination of other documents suggests a different narrative. It is most likely that Vernam came up with the need for non-repetition; Mauborgne, though, apparently contributed materially to the invention of the two-tape variant. Furthermore, there is reason to suspect that he suggested the need for randomness to Vernam. However, neither Mauborgne, Herbert Yardley, nor anyone at AT&T really understood the security advantages of the true one-time tape. Col. Parker Hitt may have; William Friedman definitely did. Finally, we show that Friedman's attacks on the two-tape variant likely led to his invention of the index of coincidence, arguably the single most important publication in the history of cryptanalysis.
Steven M. Bellovin. The economics of cyberwar. Technical Report CUCS-010-14, Department of Computer Science, Columbia University, April 2014. Presented at the Institute for New Economic Thinking's Human After All. [ bib | http ]
Cyberwar is very much in the news these days. It is tempting to try to understand the economics of such an activity, if only qualitatively. What effort is required? What can such attacks accomplish? What does this say, if anything, about the likelihood of cyberwar?
Steven M. Bellovin. Mysterious checks from Mauborgne to Fabyan. Technical Report CUCS-012-14, Department of Computer Science, Columbia University, April 2014. A later version will appear in Cryptologia. [ bib | http ]
It has long been known that George Fabyan's Riverbank Laboratories provided the U.S. military with cryptanalytic and training services during World War I. The relationship has always be seen as voluntary. Newly discovered evidence suggests that Fabyan was in fact paid, at least in part, for his services.
Steven M. Bellovin. Frank Miller: Inventor of the one-time pad. Technical Report CUCS-009-11, Department of Computer Science, Columbia University, March 2011. A revised version appeared in Cryptologia 35(3), July 2011. [ bib | http ]
The invention of the one-time pad is generally credited to Gilbert S. Vernam and Joseph O. Mauborgne. We show that it was invented about 35 years earlier by a Sacramento banker named Frank Miller. We provide a tentative identification of which Frank Miller it was, and speculate on whether or not Mauborgne might have known of Miller's work, especially via his colleague Parker Hitt.
Michelle Madejski, Maritza Johnson, and Steven M. Bellovin. The failure of online social network privacy settings. Technical Report CUCS-010-11, Department of Computer Science, Columbia University, February 2011. [ bib | http ]
Increasingly, people are sharing sensitive personal information via online social networks (OSN). While such networks do permit users to control what they share with whom, access control policies are notoriously difficult to configure correctly; this raises the question of whether OSN users' privacy settings match their sharing intentions. We present the results of an empirical evaluation that measures privacy attitudes and intentions and compares these against the privacy settings on Facebook. Our results indicate a serious mismatch: every one of the 65 participants in our study confirmed that at least one of the identified violations was in fact a sharing violation. In other words, OSN users' privacy settings are incorrect. Furthermore, a majority of users cannot or will not fix such errors. We conclude that the current approach to privacy settings is fundamentally flawed and cannot be fixed; a fundamentally different approach is needed. We present recommendations to ameliorate the current problems, as well as provide suggestions for future research.
Mariana Raykova, Hang Zhao, and Steven M. Bellovin. Privacy enhanced access control for outsourced data sharing. Technical Report CUCS-039-11, Department of Computer Science, Columbia University, 2011. [ bib | http ]
Traditional access control models often assume that the entity enforcing access control policies is also the owner of data and resources. This assumption no longer holds when data is outsourced to a third-party storage provider, such as the cloud. Existing access control solutions mainly focus on preserving confidentiality of stored data from unauthorized access and the storage provider. However, in this setting, access control policies as well as users' access patterns also become privacy sensitive information that should be protected from the cloud. We propose a two-level access control scheme that combines coarse-grained access control enforced at the cloud, which allows to get acceptable communication overhead and at the same time limits the information that the cloud learns from his partial view of the access rules and the access patterns, and fine-grained cryptographic access control enforced at the user's side, which provides the desired expressiveness of the access control policies. Our solution handles both read and write access control.
Vasilis Pappas, Mariana Raykova, Binh Vo, Steven M. Bellovin, and Tal Malkin. Trade-offs in private search. Technical Report CUCS-022-10, Department of Computer Science, Columbia University, September 2010. [ bib | http ]
Encrypted search-performing queries on protected data - is a well researched problem. However, existing solutions have inherent inefficiency that raises questions of practicality. Here, we step back from the goal of achieving maximal privacy guarantees in an encrypted search scenario to consider efficiency as a priority. We propose a privacy framework for search that allows tuning and optimization of the trade-offs between privacy and efficiency. As an instantiation of the privacy framework we introduce a tunable search system based on the SADS scheme and provide detailed measurements demonstrating the trade-offs of the constructed system. We also analyze other existing encrypted search schemes with respect to this framework. We further propose a protocol that addresses the challenge of document content retrieval in a search setting with relaxed privacy requirements.
Shreyas Srivatsan, Maritza Johnson, and Steven M. Bellovin. Simple-VPN: Simple IPsec configuration. Technical Report CUCS-020-10, Department of Computer Science, Columbia University, July 2010. [ bib | http ]
The IPsec protocol promised easy, ubiquitous encryption. That has never happened. For the most part, IPsec usage is confined to VPNs for road warriors, largely due to needless configuration complexity and incompatible implementations. We have designed a simple VPN configuration language that hides the unwanted complexities. Virtually no options are necessary or possible. The administrator specifies the absolute minimum of information: the authorized hosts, their operating systems, and a little about the network topology; everything else, including certificate generation, is automatic. Our implementation includes a multitarget compiler, which generates implementation-specific configuration files for three different platforms; others are easy to add.
Elli Androulaki, Binh Vo, and Steven M. Bellovin. A real-world identity management system with master secret revocation. Technical Report CUCS-008-10, Department of Computer Science, Columbia University, April 2010. [ bib | http ]
Cybersecurity mechanisms have become increasingly important as online and offline worlds converge. Strong authentication and accountability are key tools for dealing with online attacks, and we would like to realize them through a token-based, centralized identity management system. In this report, we present aprivacy-preserving group of protocols comprising a unique per user digital identity card, with which its owner is able to authenticate himself, prove possession of attributes, register himself to multiple online organizations (anonymously or not) and provide proof of membership. Unlike existing credential-based identity management systems, this card is revocable, i.e., its legal owner may invalidate it if physically lost, and still recover its content and registrations into a new credential. This card will protect an honest individual's anonymity when applicable as well as ensure his activity is known only to appropriate users.
Elli Androulaki, Binh Vo, and Steven M. Bellovin. Privacy-preserving, taxable bank accounts. Technical Report CUCS-005-10, Department of Computer Science, Columbia University, April 2010. [ bib | http ]
Current banking systems do not aim to protect user privacy. Purchases made from a single bank account can be linked to each other by many parties. This could be addressed in a straight-forward way by generating unlinkable credentials from a single master credential using Camenisch and Lysyanskaya's algorithm; however, if bank accounts are taxable, some report must be made to the tax authority about each account. Using unlinkable credentials, digital cash, and zero knowledge proofs of kmowledge, we present a solution that prevents anyone, even the tax authority, from knowing which accounts belong to which users, or from being able to link any account to another or to purchases or deposits.
Elli Androulaki and Steven M. Bellovin. A secure and privacy-preserving targeted ad-system. Technical Report CUCS-044-09, Department of Computer Science, Columbia University, October 2009. A revised version will appear at the 1st Workshop on Real-Life Cryptographic Protocols and Standardization. [ bib | http ]
Hang Zhao and Steven M. Bellovin. Source prefix filtering in ROFL. Technical Report CUCS-033-09, Department of Computer Science, Columbia University, July 2009. [ bib | http ]
Yuu-Heng Cheng, Scott Alexander, Alex Poylisher, and Mariana Raykova Steven M. Bellovin. The Zodiac policy subsystem: a policy-based management system for a high-security MANET. Technical Report CUCS-023-09, Department of Computer Science, Columbia University, May 2009. [ bib | http ]
Elli Androulaki and Steven M. Bellovin. An anonymous credit card system. Technical Report CUCS-010-09, Department of Computer Science, Columbia University, February 2009. [ bib | http ]
Olaf Maennel, Randy Bush, Luca Cittadini, and Steven M. Bellovin. A better approach than carrier-grade-NAT. Technical Report CUCS-041-08, Department of Computer Science, Columbia University, September 2008. [ bib | http ]
Kyle Dent and Steven M. Bellovin. Newspeak: A secure approach for designing web applications. Technical Report CUCS-008-08, Department of Computer Science, Columbia University, February 2008. [ bib | http ]
Steven M. Bellovin and William R. Cheswick. Privacy-enhanced searches using encrypted Bloom filters. Technical Report CUCS-034-07, Department of Computer Science, Columbia University, September 2007. [ bib | http ]
Elli Androulaki, Mariana Raykova, Angelos Stavrou, and Steven M. Bellovin. Opentor: Anonymity as a commodity service. Technical Report CUCS-031-07, Department of Computer Science, Columbia University, September 2007. [ bib | http ]
Elli Androulaki, Seung Geol Choi, Steven M. Bellovin, and Tal Malkin. Reputation systems for anonymous networks. Technical Report CUCS-029-07, Department of Computer Science, Columbia University, September 2007. [ bib | http ]
Hang Zhao and Steven M. Bellovin. Policy algebras for hybrid firewalls. Technical Report CUCS-017-07, Department of Computer Science, Columbia University, March 2007. Also presented at the Annual Conference of the ITA, 2007. [ bib | http ]