Shatter: Using Threshold Cryptography to Protect Single Users with Multiple Devices

ABSTRACT

The average computer user is no longer restricted to one device. They may have several devices and expect their applications to work on all of them. A challenge arises when these applications need the cryptographic private key of the devices' owner. Here the device owner typically has to manage keys manually with a "keychain" app, which leads to private keys being transferred insecurely between devices -- or even to other people. Even with intuitive synchronization mechanisms, theft and malware still pose a major risk to keys. Phones and watches are frequently removed or set down, and a single compromised device leads to the loss of the owner's private key, a catastrophic failure that can be quite difficult to recover from.

We introduce Shatter, an open-source framework that runs on desktops, Android, and Android Wear, and performs key distribution on a user's behalf. Shatter uses threshold cryptography to turn the security weakness of having multiple devices into a strength. Apps that delegate cryptographic operations to Shatter have their keys compromised only when a threshold number of devices are compromised by the same attacker. We demonstrate how our framework operates with two popular Android apps (protecting identity keys for a messaging app, and encryption keys for a note-taking app) in a backwards-compatible manner: only Shatter users need to move to a Shatter-aware version of the app. Shatter has minimal impact on app performance, with signatures and decryption being calculated in 0.5s and security proofs in 14s.

References

1. Overview of projects working on next-generation secure email. https://github.com/OpenTechFund/secure-email. Accessed Feb 2015.
2. Apple Inc. iOS security. https://www.apple.com/business/docs/iOS Security Guide.pdf, June 2015.
3. M. Bellare, D. Micciancio, and B. Warinschi. Foundations of group signatures: Formal definitions, simplified requirements, and a construction based on general assumptions. In Advances in Cryptology -- Eurocrypt 2003, pages 614--629. Springer, 2003.
4. B. Blakley, G. Blakley, A. H. Chan, and J. L. Massey. Threshold schemes with disenrollment. In Advances in Cryptology -- CRYPTO'92, pages 540--548. Springer, 1993.
5. G. R. Blakley. Safeguarding cryptographic keys. In the National Computer Conference, volume 48, pages 313--317, 1979.
6. N. Borisov, I. Goldberg, and E. Brewer. Off-the-record communication, or, why not to use PGP. In 2004 ACM Workshop on Privacy in the Electronic Society, pages 77--84. ACM, 2004.
7. P. Bright and D. Goodin. Encrypted e-mail: How much annoyance will you tolerate to keep the NSA away? Ars Technica, June 2013.
8. A. Chowdhry. Gmail's 'Undo send' option officially rolls out. Forbes, June 2015.
9. M. D. Corner and B. D. Noble. Zero-interaction authentication. In 8th Annual International Conference on Mobile Computing and Networking, pages 1--11. ACM, 2002.
10. I. Damgrdå and M. Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In Public Key Cryptography, pages 119--136. Springer, 2001.
11. Y. Desmedt, M. Burmester, R. Safavi-Naini, and H. Wang. Threshold things that think (T4): Security requirements to cope with theft of handheld/handless internet devices. In Symposium on Requirements Engineering for Information Security, 2001.
12. M. Farb, Y.-H. Lin, T. H.-J. Kim, J. McCune, and A. Perrig. Safeslinger: Easy-to-use and secure public-key exchange. In 19th Annual International Conference on Mobile Computing & Networking, pages 417--428. ACM, 2013.
13. R. Geambasu, J. P. John, S. D. Gribble, T. Kohno, and H. M. Levy. Keypad: An auditing le system for theft-prone devices. InSixth Conference on Computer Systems, EuroSys '11, pages 1--16, New York, NY, USA, 2011. ACM.
14. R. Gennaro, S. Goldfeder, and A. Narayanan. Threshold-optimal DSA/ECDSA signatures and an application to Bitcoin wallet security. In 14th International Conference on Applied Cryptography and Network Security. Springer, 2016.
15. D. L. Gil. Multiple devices and key synchronization. https://github.com/coruus/zero-one/blob/master/multidevice-keysync.markdown, 2014.
16. M. Green. The daunting challenge of secure e-mail. The New Yorker, November 2013.
17. B. Greenstein, D. McCoy, J. Pang, T. Kohno, S. Seshan, and D. Wetherall. Improving wireless privacy with an identifier-free link layer protocol. In Sixth International Conference on Mobile Systems, Applications, and Services, MobiSys '08, pages 40--53, New York, NY, USA, 2008. ACM.
18. G. Greenwald, E. MacAskill, and L. Poitras. Edward Snowden: The whistleblower behind the NSA surveillance revelations. The Guardian, 2013.
19. T. Hase. Secure PGP key sync -- a proposal. https://blog.whiteout.io/2014/07/07/secure-pgp-key-sync-a-proposal/, 2014.
20. A. Herzberg, S. Jarecki, H. Krawczyk, and M. Yung. Proactive secret sharing or: How to cope with perpetual leakage. In Advances in Cryptology -- CRYPT0'95, volume 963 of Lecture Notes in Computer Science, pages 339--352. Springer Berlin Heidelberg, 1995.
21. A. Kalamandeen, A. Scannell, E. de Lara, A. Sheth, and A. LaMarca. Ensemble: Cooperative proximity-based authentication. In 8th International Conference on Mobile Systems, Applications, and Services, pages 331--344. ACM, 2010.
22. F. M. A. Krause. Designing secure & usable Picosiblings. https://www.cl.cam.ac.uk/~fms27/papers/2014-Krause-picosiblings.pdf, 2014. Masters thesis.
23. M. Lentz, V. Erdélyi, P. Aditya, E. Shi, P. Druschel, and B. Bhattacharjee. SDDR: Light-weight, secure mobile encounters. In 23rd USENIX Security Symposium, pages 925--940, 2014.
24. Y.-H. Lin, A. Studer, H.-C. Hsiao, J. M. McCune, K.-H. Wang, M. Krohn, P.-L. Lin, A. Perrig, H.-M. Sun, and B.-Y. Yang. Spate: Small-group PKI-less authenticated trust establishment. In 7th International Conference on Mobile Systems, Applications, and Services, MobiSys '09, pages 1--14, New York, NY, USA, 2009. ACM.
25. M. S. Melara, A. Blankstein, J. Bonneau, E. W. Felten, and M. J. Freedman. CONIKS: Bringing key transparency to end users. In 24th USENIX Security Symposium, pages 383--398, Aug. 2015.
26. A. Oprea, D. Balfanz, G. Durfee, and D. Smetters. Securing a remote terminal application with a mobile trusted device. In 20th Annual Computer Security Applications Conference, pages 438--447, Dec 2004.
27. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Advances in Cryptology -- EUROCRYPT'99, pages 223--238. Springer, 1999.
28. R. Peeters. Security architecture for things that think. http://www.cosic.esat.kuleuven.be/publications/thesis-202.pdf, 2012. Ph.D. thesis.
29. R. Peeters, M. Kohlweiss, and B. Preneel. Threshold things that think: Authorisation for resharing. In J. Camenisch and D. Kesdogan, editors, iNetSec 2009 -- Open Research Problems in Network Security, volume 309 of IFIP Advances in Information and Communication Technology, pages 111--124. SpringerBerlin Heidelberg, 2009.
30. R. Peeters, S. Nikova, and B. Preneel. Practical RSA threshold decryption for things that think. In 3rd Benelux Workshop on Information and System Security, 2008.
31. R. Peeters, D. Singelée, and B. Preneel. Threshold-based location-aware access control. Mobile and Handheld Computing Solutions for Organizations and End-Users, pages 20--36, 2013.
32. S. Sheng, L. Broderick, C. Koranda, and J. Hyland. Why Johnny still can't encrypt: Evaluating theusability of email encryption software. In 2006 Symposium On Usable Privacy and Security - Poster Session, 2006.
33. V. Shoup. Practical threshold signatures. In 19th International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT'00, pages 207--220, Berlin, Heidelberg, 2000. Springer-Verlag.
34. K. Simoens, R. Peeters, and B. Preneel. Increased resilience in threshold cryptography: sharing a secret with devices that cannot store shares. In Pairing-Based Cryptography-Pairing 2010, pages 116--135. Springer, 2010.
35. S. Sinclair and S. Smith. PorKI: Making user PKI safe on machines of heterogeneous trustworthiness. In 21st Annual Computer Security Applications Conference, pages 10 pp.--430, Dec 2005.
36. D. Singelee, R. Peeters, and B. Preneel. Toward more secure and reliable access control. IEEE Pervasive Computing, (3):76--83, 2012.
37. F. Stajano. Pico: No more passwords! InSecurity Protocols XIX, volume 7114 of Lecture Notes in Computer Science, pages 49--81. Springer Berlin Heidelberg, 2011.
38. O. Stannard and F. Stajano. Am I in good company? A privacy-protecting protocol for cooperating ubiquitous computing devices. In Security Protocols XX, volume 7622 of Lecture Notes in Computer Science, pages 223--230. Springer Berlin Heidelberg, 2012.
39. Q. Staêrd-Fraser, G. Jenkinson, F. Stajano, M. Spencer, C. Warrington, and J. Payne. To have and have not: Variations on secret sharing to model user presence. In 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing: Adjunct Publication, pages 1313--1320. ACM, 2014.
40. A. Whitten and J. D. Tygar. Why Johnny can't encrypt: A usability evaluation of PGP 5.0. In 8th USENIX Security Symposium , SSYM'99, pages 14--14, Berkeley, CA, USA, 1999.

Index Terms

• Security and privacy

  • Cryptography

    • Key management

  • Human and societal aspects of security and privacy

    • Usability in security and privacy

  • Network security

    • Mobile and wireless security

    • Security protocols