Abstract
Human understanding of protocols is central to protocol security. The security of a protocol rests on its designers, its implementors, and, in some cases, its users correctly conceptualizing how it should work, understanding how it actually works, and predicting how others will think it works. Ensuring these conceptualizations are correct is difficult. A complementary field, however, provides some inspiration on how to proceed: the field of language-theoretic security (LangSec) promotes the adoption of a secure design-and-development methodology that emphasizes the existence of certain computability boundaries that must never be crossed during parser and protocol construction to ensure correctness of design and implementation. We propose supplementing this work on classical computability boundaries with exploration of human-computability boundaries. Classic computability research has focused on understanding what problems can be solved by machines or idealized human computers—that is, computational models that behave like humans carrying out rote computational tasks in principle but that are not subject to the natural limitations that humans face in practice. Humans are often subject to a variety of deficiencies, e.g., constrained working memories, short attention spans, misperceptions, and cognitive biases. We argue that such realities must be taken into consideration if we are to be serious about securing protocols. A corollary is that while the traditional computational models and hierarchies built using them (e.g., the Chomsky hierarchy) are useful for securing protocols and parsers, they alone are inadequate as they neglect the human-computability boundaries that define what humans can do in practice. In this position paper, we advocate for the discovery of human-computability boundaries, present challenges with precisely and accurately finding those boundaries, and outline future paths of inquiry.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
While the discussion in this paper focuses on protocols, the notion of human-computability boundaries is certainly applicable more broadly.
- 2.
We note that not everyone held this view. For example, Shagrir provides discussion on Gödel’s rejection of this assumption [19].
- 3.
As noted by Carl Ellison: “The term ‘ceremony’ was coined for this purpose by Jesse Walker of Intel Corporation.” [8].
References
Basin, D., Radomirovic, S., Schmid, L.: Modeling human errors in security protocols. In: 2016 IEEE 29th Computer Security Foundations Symposium (CSF), pp. 325–340. IEEE (2016)
Beautement, A., Sasse, M.A., Wonham, M.: The compliance budget: managing security behaviour in organisations. In: Proceedings of the 2008 New Security Paradigms Workshop, pp. 47–58. ACM (2009)
Bella, G., Coles-Kemp, L.: Layered analysis of security ceremonies. In: Gritzalis, D., Furnell, S., Theoharidou, M. (eds.) SEC 2012. IAICT, vol. 376, pp. 273–286. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30436-1_23
Blum, M., Vempala, S.: The complexity of human computation: a concrete model with an application to passwords. arXiv preprint arXiv:1707.01204 (2017)
Bratus, S.: LANGSEC: Language-theoretic security: "The View from the Tower of Babel". http://langsec.org. Accessed 2 Jan 2019
Bratus, S., Locasto, M., Patterson, M., Sassaman, L., Shubina, A.: Exploit programming: from buffer overflows to "weird machines" and theory of computation. Login USENIX Mag. 36(6), 13–21 (2011)
Copeland, B.J.: The Church-Turing Thesis. In: Zalta, E.N. (ed.) The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, Spring 2019 edn. (2019)
Ellison, C.: Ceremony design and analysis. Cryptology ePrint Archive, Report 2007/399 (2007). https://eprint.iacr.org/2007/399
Gilovich, T., Griffin, D., Kahneman, D.: Heuristics and Biases: The Psychology of Intuitive Judgment. Cambridge University Press, Cambridge (2002)
Herley, C.: So long, and no thanks for the externalities: the rational rejection of security advice by users. In: Proceedings of the 2009 workshop on New Security Paradigms Workshop, pp. 133–144. ACM (2009)
Johansen, C., Pedersen, T., Jøsang, A.: Towards behavioural computer science. In: Habib, S.M.M., Vassileva, J., Mauw, S., Mühlhäuser, M. (eds.) IFIPTM 2016. IAICT, vol. 473, pp. 154–163. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41354-9_12
Kahneman, D.: A perspective on judgment and choice: mapping bounded rationality. Am. Psycholog. 58(9), 697 (2003)
Kahneman, D., Thaler, R.H.: Anomalies: utility maximization and experienced utility. J. Econ. Perspect. 20(1), 221–234 (2006). https://doi.org/10.1257/089533006776526076
Law, E., Ahn, L.V.: Defining (Human) computation. Synth. Lect. Artif. Intell. Mach. Learn. 5(3), 1–121 (2011)
Meier, S., Schmidt, B., Cremers, C., Basin, D.: The TAMARIN prover for the symbolic analysis of security protocols. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 696–701. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-39799-8_48
Naked Security, Sophos: Anatomy of a “goto fail" - Apple’s SSL bug explained, plus an unofficial patch for OS X!, February 2014. https://nakedsecurity.sophos.com/2014/02/24/anatomy-of-a-goto-fail-apples-ssl-bug-explained-plus-an-unofficial-patch/. Accessed 3 Jan 2019
Patterson, M.: Parser combinators for binary formats, in C. https://github.com/UpstandingHackers/hammer. Accessed 4 Jan 2019
Quinn, A.J., Bederson, B.B.: Human computation: a survey and taxonomy of a growing field. In: Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1403–1412. ACM (2011)
Shagrir, O.: Gödel on turing on computability. In: Olszewski, A., Wole’nski, J., Janusz, R. (eds.) Church’s Thesis After Seventy Years, pp. 393–419. Ontos Verlag (2006)
Sloman, S.A.: Two systems of reasoning. In: Gilovich, T., Griffin, D., Kahneman, D. (eds.) Heuristics and Biases: The Psychology of Intuitive Judgment. Cambridge University Press, Cambridge (2002)
Smith, S.W.: Security and cognitive bias: exploring the role of the mind. IEEE Secur. Privacy 10(5), 75–78 (2012)
Turing, A.M.: On computable numbers, with an application to the entscheidungsproblem. Proc. London Math. Soc. 2(1), 230–265 (1937)
Von Ahn, L.: Human computation. In: Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, pp. 1–2. IEEE Computer Society (2008)
Wing, J.M.: Computational thinking. Commun. ACM 49(3), 33–35 (2006)
Acknowledgement
This material is based upon work supported by the United States Air Force and DARPA under Contract No. FA8750-16-C-0179 and Department of Energy under Award Number DE-OE0000780.
Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Air Force, DARPA, United States Government or any agency thereof.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Kothari, V. et al. (2020). Human-Computability Boundaries. In: Anderson, J., Stajano, F., Christianson, B., Matyáš, V. (eds) Security Protocols XXVII. Security Protocols 2019. Lecture Notes in Computer Science(), vol 12287. Springer, Cham. https://doi.org/10.1007/978-3-030-57043-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-030-57043-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57042-2
Online ISBN: 978-3-030-57043-9
eBook Packages: Computer ScienceComputer Science (R0)