Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the Encode-then-Encrypt-and-MAC paradigm

ABSTRACT

The secure shell (SSH) protocol is one of the most popular cryptographic protocols on the Internet. Unfortunately, the current SSH authenticated encryption mechanism is insecure. In this paper, we propose several fixes to the SSH protocol and, using techniques from modern cryptography, we prove that our modified versions of SSH meet strong new chosen-ciphertext privacy and integrity requirements. Furthermore, our proposed fixes will require relatively little modification to the SSH protocol and to SSH implementations. We believe that our new notions of privacy and integrity for encryption schemes with stateful decryption algorithms will be of independent interest.

REFERENCES

• 1: Jee Hea An , Yevgeniy Dodis , Tal Rabin, On the Security of Joint Signature and Encryption, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.83-107, May 02, 2002
• 2: Mihir Bellare , Anand Desai , Eron Jokipii , Phillip Rogaway, A Concrete Security Treatment of Symmetric Encryption, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.394, October 19-22, 1997
• 3: Mihir Bellare , Joe Kilian , Phillip Rogaway, The Security of Cipher Block Chaining, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.341-358, August 21-25, 1994
• 4: Mihir Bellare , Tadayoshi Kohno , Chanathip Namprempre, Authenticated encryption in SSH: provably fixing the SSH binary packet protocol, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586112]
• 5: Bellare, M., Kohno, T., and Namprempre, C. 2004. SSH Transport Layer Encryption Modes. Available at http://www.ietf.org/html.charters/secsh-charter.html.
• 6: Mihir Bellare , Chanathip Namprempre, Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.531-545, December 03-07, 2000
• 7: Mihir Bellare , Phillip Rogaway, Encode-Then-Encipher Encryption: How to Exploit Nonces or Redundancy in Plaintexts for Efficient Cryptography, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.317-330, December 03-07, 2000
• 8: Bellare, M., Rogaway, P., and Wagner, D. 2004. The EAX mode of operation. In Fast Software Encryption---FSE 2004, W. Meier and B. Roy, eds. Lecture Notes in Computer Science. Springer-Verlag, Berlin, Germany.
• 9: Bellovin, S. 1996. Problem areas for the IP security protocols. In Proceedings of the 6th USENIX Security Symposium. San Jose, California. 1--16.
• 10: Bellovin, S. and Blaze, M. 2001. Cryptographic modes of operation for the Internet. In Second NIST Workshop on Modes of Operation.
• 11: John Black , Phillip Rogaway, CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.197-215, August 20-24, 2000
• 12: Ran Canetti , Hugo Krawczyk, Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.453-474, May 06-10, 2001
• 13: Canvel, B., Hiltgen, A., Vaudenay, S., and Vuagnoux, M. 2003. Password interception in a SSL/TLS channel. In Advances in Cryptology---CRYPTO 2003, D. Boneh, ed. Lecture Notes in Computer Science. Springer-Verlag, Berlin Germany.
• 14: Dai, W. 2002. An Attack Against SSH2 Protocol. Available from [e-mail].
• 15: Des. 1980. DES Modes of Operation. National Institute of Standards and Technology, NIST FIPS PUB 81, U.S. Department of Commerce.
• 16: Diffie, W. and Hellman, M. E. 1979. Privacy and authentication: An introduction to cryptography. Proceedings of the IEEE 67, 3 (Mar.), 397--427.
• 17: Dodis, Y. and An, J. H. 2003. Concealment and its applications to authenticated encryption. In Advances in Cryptology---EUROCRYPT 2003, E. Biham, ed. Lecture Notes in Computer Science, vol. 2656. Springer-Verlag, Berlin Germany, 312--329.
• 18: Virgil D. Gligor , Pompiliu Donescu, Fast Encryption and Authentication: XCBC Encryption and XECB Authentication Modes, Revised Papers from the 8th International Workshop on Fast Software Encryption, p.92-108, April 02-04, 2001
• 19: Oded Goldreich , Shafi Goldwasser , Silvio Micali, On the cryptographic applications of random functions, Proceedings of CRYPTO 84 on Advances in cryptology, p.276-288, August 1985, Santa Barbara, California, United States
• 20: Goldwasser, S. and Micali, S. 1984. Probabilistic encryption. Journal of Computer and System Science 28, 270--299.
• 21: Chris Hall , Ian Goldberg , Bruce Schneider, Reaction Attacks against several Public-Key Cryptosystems, Proceedings of the Second International Conference on Information and Communication Security, p.2-12, November 09-11, 1999
• 22: Charanjit S. Jutla, Encryption Modes with Almost Free Message Integrity, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.529-544, May 06-10, 2001
• 23: Jonathan Katz , Moti Yung, Unforgeable Encryption and Chosen Ciphertext Secure Modes of Operation, Proceedings of the 7th International Workshop on Fast Software Encryption, p.284-299, April 10-12, 2000
• 24: Kohno, T., Viega, J., and Whiting, D. 2004. CWC: A high-performance conventional authenticated encryption mode. In Fast Software Encryption---FSE 2004, W. Meier and B. Roy, Eds. Lecture Notes in Computer Science. Springer-Verlag, Berlin Germany.
• 25: Hugo Krawczyk, The Order of Encryption and Authentication for Protecting Communications (or: How Secure Is SSL?), Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.310-331, August 19-23, 2001
• 26: Krawczyk, H., Bellare, M., and Canetti, R. 1997. HMAC: Keyed-hashing for message authentication. IETF Internet Request for Comments 2104.
• 27: Lipmaa, H., Rogaway, P., and Wagner, D. 2000. CTR-mode encryption. In First NIST Workshop on Modes of Operation.
• 28: Chanathip Namprempre, Secure Channels Based on Authenticated Encryption Schemes: A Simple Characterization, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.515-532, December 01-05, 2002
• 29: Rogaway, P. 1995. Problems with Proposed IP Cryptography. Available at http://www.cs.ucdavis.edu/ rogaway/papers/draft-rogaway-ipsec-comments-00.txt.
• 30: Phillip Rogaway, Authenticated-encryption with associated-data, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586125]
• 31: Phillip Rogaway , Mihir Bellare , John Black , Ted Krovetz, OCB: a block-cipher mode of operation for efficient authenticated encryption, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502011]
• 32: Song, D. X., Wagner, D., and Tian, X. 2001. Timing analysis of keystrokes and timing attacks on SSH. In Proceedings of the 10th USENIX Security Symposium, Washington, DC. 337--352.
• 33: Serge Vaudenay, Security Flaws Induced by CBC Padding - Applications to SSL, IPSEC, WTLS ..., Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.534-546, May 02, 2002
• 34: Whiting, D., Ferguson, N., and Housley, R. 2002. Counter with CBC-MAC (CCM). Submission to NIST. Available at http://csrc.nist.gov/CryptoToolkit/modes/proposedmodes/.
• 35: Ylonen, T., Kivinen, T., Saarinen, M., Rinne, T., and Lehtinen, S. 2002. SSH Transport Layer Protocol, Draft 12. Available at http://www.ietf.org/html.charters/secsh-charter.html.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Security, Theory

Keywords:
Authenticated encryption, secure shell, security proofs, stateful decryption