Creating shared secrets out of thin air

ABSTRACT

Current security systems typically rely on the adversary's computational limitations (e.g., the fact that it cannot invert a hash function or perform large-integer factorization). Wireless networks offer the opportunity for a different, complementary kind of security, which relies not on the adversary's computational limitations, but on its limited network presence (i.e., that the adversary cannot be located at many different points in the network at the same time). We take a first step toward designing and building a wireless security system that leverages this opportunity: We consider the problem where a group of n nodes, connected to the same broadcast wireless network, want to agree on a shared secret (e.g., an encryption key), in the presence of an adversary Eve who tries to listen in and steal the secret. We propose a secret-agreement protocol, where the n nodes of the group keep exchanging bits until they have all agreed on a bit sequence that Eve cannot reconstruct (with very high probability). We provide experimental evidence---to the best of our knowledge, the first one---that a group of wireless nodes can generate thousands of new shared secret bits per second, with their secrecy being independent of the adversary's computational capabilities.

References

1. R. L. Rivest, A. Shamir, and L. Adleman, "A Method for Obtaining Digital Signatures and Public-key Cryptosystems," Communications of the ACM, vol. 21(2), pp. 120--126, 1978.
2. A. D. Wyner, "The Wire-tap Channel," Bell System Tech. J., vol. 54, pp. 1355--1387, 1975.
3. U. M. Maurer, "Secret Key Agreement by Public Discussion from Common Information," IEEE Trans. Info. Theory, vol. 39, 1993.
4. S. Xiao, W. Gong, and D. Towsley, "Secure Wireless Communication with Dynamic Secrets," in Proceedings of the IEEE INFOCOM Conference, 2010.
5. A. Mink, X. Tang, L. Ma, T. Nakassis, B. Hershman, J. C. Bienfang, D. Su, R. Boisvert, C. W. Clark, and C. J. Williams, "High Speed Quantum Key Distribution System Supports One-time Pad Encryption of Real-time Video," in Proceedings of SPIE, vol. 6244, 2006.
6. "The On-demand Video Consumer", Survey, 2012, http://www.youtube.com/yt/advertise/research.html.
7. L. Lai, H. El Gamal, and H. V. Poor, "The Wiretap Channel with Feedback: Encryption over the Channel," IEEE Trans. Info. Theory, vol. 54(11), pp. 5059--5067, 2008.
8. S. Gollakota and D. Katabi, "Physical Layer Wireless Security Made Fast and Channel Independent," in Proceedings of the IEEE INFOCOM Conference, 2011.
9. M. J. Siavoshani, U. Pulleti, E. Atsan, I. Safaka, C. Fragouli, K. Argyraki, and S. Diggavi. "Exchanging Secrets Without Using Cryptography," Technical Report, 2011, http://arxiv.org/abs/1105.4991.
10. F. J. Macwilliams and N. J. A. Sloane, "The Theory of Error Correcting Codes," North-Holland, 2006.
11. B. Azimi-Sadjadi, A. Kiayias, A. Mercado, and B. Yener, "Robust Key Generation from Signal Envelopes in Wireless Networks," in Proceedings of the ACM Conference on Computer and Communications Security (CCS), 2007.
12. C. Ye, S. Mathur, A. Reznik, Y. Shah, W. Trappe, and N. Mandayam, "Information-theoretically Secret Key Generation for Fading Wireless Channels," IEEE Trans. Information Forensics and Security, vol. 5(2), pp. 240--254, 2010.
13. J. Croft, N. Patwari, and S. Kasera, "Robust Uncorrelated Bit Extraction Methodologies for Wireless Sensors," in Proceedings of the IPSN Conference, 2010.
14. S. Jana, S. N. Premnath, M. Clark, S. Kasera, N. Patwari, and S. Krishnamurthy, "On the Effectiveness of Secret Key Extraction from Wireless Signal Strength in Real Environments," in Proceedings of the ACM MOBICOM Conference, 2009.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks