Advanced Search
Article Contents
Article Contents

Another look at security definitions

Abstract Related Papers Cited by
  • We take a critical look at security models that are often used to give "provable security" guarantees. We pay particular attention to digital signatures, symmetric-key encryption, and leakage resilience. We find that there has been a surprising amount of uncertainty about what the "right" definitions might be. Even when definitions have an appealing logical elegance and nicely reflect certain notions of security, they fail to take into account many types of attacks and do not provide a comprehensive model of adversarial behavior.
    Mathematics Subject Classification: Primary: 94A60, 11T71.


    \begin{equation} \\ \end{equation}
  • [1]

    M. Albrecht, P. Farshim, K. Paterson and G. Watson, On cipher-dependent related-key attacks in the ideal-cipher model, in "Fast Software Encryption - FSE 2011,'' Springer-Verlag, (2011), 128-145.


    M. Albrecht, K. Paterson and G. Watson, Plaintext recovery attacks against SSH, in "IEEE Symposium on Security and Privacy,'' IEEE Computer Society, (2009), 16-26.


    J. Alwen, Y. Dodis, M. Naor, G. Segev, S. Walfish and D. Wichs, Public-key encryption in the bounded-retrieval model, in "Advances in Cryptology - Eurocrypt 2010,'' Springer-Verlag, (2010), 113-134.doi: 10.1007/978-3-642-13190-5_6.


    J. Alwen, Y. Dodis and D. Wichs, Leakage-resilient public-key cryptography in the bounded-retrieval model, in "Advances in Cryptology - Crypto 2009,'' Springer-Verlag, (2009), 36-54.doi: 10.1007/978-3-642-03356-8_3.


    R. Anderson, "Security Engineering,'' 2nd edition, Wiley, 2008.


    M. Bellare and D. Cash, Pseudorandom functions and permutations provably secure against related-key attacks, in "Advances in Cryptology - Crypto 2010,'' Springer-Verlag, (2010), 666-684.


    M. Bellare and S. DuanPartial signatures and their applications, available online at http://eprint.iacr.org/2009/336.pdf


    M. Bellare, O. Goldreich and A. MityaginThe power of verification queries in message authentication and authenticated encryption, available online at http://eprint.iacr.org/2004/309.pdf


    M. Bellare, D. Hofheinz and E. KiltzSubtleties in the definition of IND-CCA: When and how should challenge-decryption be disallowed?, available online at http://eprint.iacr.org/2009/418.pdf


    M. Bellare and T. Kohno, A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PFRs, and applications, in "Advances in Cryptology - Eurocrypt 2003,'' Springer-Verlag, (2003), 491-506.doi: 10.1007/3-540-39200-9_31.


    M. Bellare, T. Kohno and C. Namprempre, Breaking and provably repairing the SSH authenticated encryption scheme: A case study of the encode-then-encrypt-and-MAC paradigm, in "ACM Transactions on Information and System Security,'' 1 (2004), 206-241.doi: 10.1145/996943.996945.


    M. Bellare and P. Rogaway, Entity authentication and key distribution, in "Advances in Cryptology - Crypto '93,'' Springer-Verlag, (1994), 232-249; available online at http://cseweb.ucsd.edu/~mihir/papers/eakd.pdf


    D. J. Bernstein, H.-C. Chen, C.-M. Cheng, T. Lange, R. Niederhagen, P. Schwabe and B.-Y. Yang, ECC2K-130 on NVIDIA GPUs, in "Progress in Cryptology - Indocrypt 2010,'' Springer-Verlag, (2010), 328-346.doi: 10.1007/978-3-642-17401-8_23.


    I. Biehl, B. Meyer and V. Müller, Differential fault attacks on elliptic curve cryptosystems, in "Advances in Cryptology - Crypto 2000,'' Springer-Verlag, (2000), 131-146.doi: 10.1007/3-540-44598-6_8.


    A. Biryukov, O. Dunkelman, N. Keller, D. Khovratovich and A. Shamir, Key recovery attacks of practical complexity on AES variants with up to 10 rounds, in "Advances in Cryptology - Eurocrypt 2010,'' Springer-Verlag, (2010), 299-319.doi: 10.1007/978-3-642-13190-5_15.


    S. Blake-Wilson and A. Menezes, Unknown key-share attacks on the station-to-station (STS) protocol, in "Public Key Cryptography - PKC 1999,'' Springer-Verlag, (1999), 156-170.


    J. Blömer, M. Otto and J.-P. Seifert, Sign change fault attacks on elliptic curve cryptosystems, in "Fault Diagnosis and Tolerance in Cryptography (FDTC),'' Springer-Verlag, (2006), 36-52.doi: 10.1007/11889700_4.


    J.-M. Bohli, S. Röhrich and R. Steinwandt, Key substitution attacks revisited: Taking into account malicious signers, Intern. J. Information Security, 5 (2006), 30-36.doi: 10.1007/s10207-005-0071-2.


    A. Boldyreva, M. Fischlin, A. Palacio and B. Warinschi, A closer look at PKI: Security and efficiency, in "Public Key Cryptography - PKC 2007,'' Springer-Verlag, (2007), 458-475.doi: 10.1007/978-3-540-71677-8_30.


    R. Canetti, Universally composable signature, certification, and authentication, available online at http://eprint.iacr.org/2003/239; a shorter version appeared in "Computer Security Foundations Workshop (CSFW-17 2004),'' IEEE Computer Society, (2004), 219-235.


    J. le Carré, "The Looking Glass War,'' Coward-McCann, New York, 1965.


    D. Cash, Y. Z. Ding, Y. Dodis, W. Lee, R. J. Lipton and S. Walfish, Intrusion-resilient key exchange in the bounded retrieval model, in "Fourth Theory of Cryptography Conference - TCC 2007,'' Springer-Verlag, (2007), 479-498.


    S. Chatterjee, A. Menezes and P. Sarkar, Another look at tightness, in "Selected Areas in Cryptography - SAC 2011,'' Springer-Verlag, (2012), 293-319.


    J. Clayton, "Charles Dickens in Cyberspace: The Afterlife of the Nineteenth Century in Postmodern Culture,'' Oxford Univ. Press, 2003.


    R. Cooke, "The Mathematics of Sonya Kovalevskaya,'' Springer-Verlag, 1984.doi: 10.1007/978-1-4612-5274-0.


    J. Coron, Resistance against differential power analysis for elliptic curve cryptosystems, in "Cryptographic Hardware and Embedded Systems (CHES),'' Springer-Verlag, (1999), 292-302.doi: 10.1007/3-540-48059-5_25.


    R. Cramer and V. Shoup, Signature schemes based on the strong RSA assumption, ACM Trans. Inform. Sys. Secur., 3 (2000), 161-185.doi: 10.1145/357830.357847.


    G. Di Crescenzo, R. J. Lipton and S. Walfish, Perfectly secure password protocols in the bounded retrieval model, in "Third Theory of Cryptography Conference - TCC 2006,'' Springer-Verlag, (2006), 225-244.


    J. P. Degabriele, K. G. Paterson and G. J. Watson, Provable security in the real world, IEEE Secur. Privacy, 9 (2011), 18-26.


    R. L. Dennis, Security in the computer environment, SDC-SP 2440/00/01, AD 640648 (August 18, 1966).


    W. Diffie, P. van Oorschot and M. Wiener, Authentication and authenticated key exchanges, Des. Codes Crypt., 2 (1992), 107-125.doi: 10.1007/BF00124891.


    Y. Dodis, P. Lee and D. Yum, Optimistic fair exchange in a multi-user setting, J. Universal Comp. Sci., 14 (2008), 318-346.


    A. Domínguez-Oviedo, "On Fault-Based Attacks and Countermeasures for Elliptic Curve Cryptosystems,'' Ph.D. thesis, University of Waterloo, 2008.


    C. Donnelly and P. Embrechts, The devil is in the tails, ASTIN Bulletin, 40 (2010), 1-33.doi: 10.2143/AST.40.1.2049222.


    O. Dunkelman, N. Keller and A. Shamir, A practical-time related-key attack on the KASUMI cryptosystem used in GSM and 3G telephony, in "Advances in Cryptology - Crypto 2010,'' Springer-Verlag, (2010), 393-410.doi: 10.1007/978-3-642-14623-7_21.


    S. Dziembowski, Intrusion-resilience via the bounded-storage model, in "Third Theory of Cryptography Conference - TCC 2006,'' Springer-Verlag, (2006), 207-224.


    S. Dziembowski and K. Pietrzak, Leakage-resilient cryptography, in "Proc. 49th Annual IEEE Symposium on the Foundations of Computer Science,'' (2008), 293-302.


    W. van Eck, Electromagnetic radiation from video display units: An eavesdropping risk?, Comput. Soc., 4 (1985), 269-286.


    J. Fan, X. Guo, E. De Mulder, P. Schaumont, B. Preneel and I. Verbauwhede, State-of-the-art of secure ECC implementations: A survey of known side-channel attacks and countermeasures, in "2010 IEEE International Symposium on Hardware-Oriented Security and Trust (HOST),'' IEEE, (2010), 76-87.doi: 10.1109/HST.2010.5513110.


    P. Fouque, R. Lercier, D. Réal and F. Valette, Fault attack on elliptic curve Montgomery ladder implementation, in "Fault Diagnosis and Tolerance in Cryptography (FDTC),'' IEEE, (2008), 92-98.


    R. Gennaro, S. Halevi and T. Rabin, Secure hash-and-sign signatures without the random oracle, in "Advances in Cryptology - Eurocrypt '99,'' Springer-Verlag, (1999), 123-139.


    C. Gentry, Practical identity-based encryption without random oracles, in "Advances in Cryptology - Eurocrypt 2006,'' Springer-Verlag, (2006), 445-464.doi: 10.1007/11761679_27.


    S. Goldwasser, S. Micali and R. Rivest, A “paradoxical” solution to the signature problem, in "Proc. 25th Annual IEEE Symposium on the Foundations of Computer Science,'' (1984), 441-448.


    S. Jones, The formula that felled Wall St., in "Financial Times,'' 24 April 2009, available online at http://www.ft.com/cms/s/2/912d85e8-2d75-11de-9eba-00144feabdc0.html


    M. Joye, J. J. Quisquater, S. M. Yen and M. Yung, Observability analysis - Detecting when improved cryptosystems fail, in "Topics in Cryptology - CT-RSA 2002,'' Springer-Verlag, (2002), 17-29.doi: 10.1007/3-540-45760-7_2.


    M. Joye and S. M. Yen, Checking before output may not be enough against fault-based cryptanalysis, IEEE Trans. Comp., 49 (2000), 967-970.doi: 10.1109/12.869328.


    M. Joye and S. M. Yen, The Montgomery powering ladder, in "Cryptographic Hardware and Embedded Systems (CHES),'' Springer-Verlag, (2002), 291-302.


    B. Kaliski, Contribution to ANSI X9F1 and IEEE P1363 working groups, 17 June 1998.


    J. KatzSignature schemes with bounded leakage resilience, available online at http://eprint.iacr.org/2009/220.pdf


    J. Katz and Y. Lindell, "Introduction to Modern Cryptography,'' Chapman and Hall/CRC, 2008.


    J. Katz and V. Vaikuntanathan, Signature schemes with bounded leakage resilience, in "Advances in Cryptology - Asiacrypt 2009,'' Springer-Verlag, (2009), 703-720.doi: 10.1007/978-3-642-10366-7_41.


    T. Kleinjung, et al., Factorization of a 768-bit RSA modulus, in "Advances in Cryptology - Crypto 2010,'' Springer-Verlag, (2010), 333-350.doi: 10.1007/978-3-642-14623-7_18.


    A. H. Koblitz, "A Convergence of Lives: Sofia Kovalevskaia - Scientist, Writer, Revolutionary,'' Birkhaüser, 1983.doi: 10.1007/978-1-4684-9438-9.


    A. H. Koblitz, N. Koblitz and A. Menezes, Elliptic curve cryptography: The serpentine course of a paradigm shift, J. Number Theory, 131 (2011), 781-814.doi: 10.1016/j.jnt.2009.01.006.


    N. Koblitz, The uneasy relationship between mathematics and cryptography, Notices Amer. Math. Soc., 54 (2007), 972-979.


    N. Koblitz and A. Menezes, Another look at “provable security”, J. Cryptology, 20 (2007), 3-37.doi: 10.1007/s00145-005-0432-z.


    N. Koblitz and A. Menezes, Another look at “provable security” II, in "Progress in Cryptology - Indocrypt 2006,'' Springer-Verlag, (2006), 148-175.doi: 10.1007/11941378_12.


    P. Kocher, Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, in "Advances in Cryptology - Crypto '96,'' Springer-Verlag, (1996), 104-113.


    P. Kocher, Differential power analysis, in "Advances in Cryptology - Crypto '99,'' Springer-Verlag, (1999), 388-397; a brief version was presented at the Rump Session of Crypto '98.


    H. Krawczyk, HMQV: A high-performance secure Diffie-Hellman protocol, in "Advances in Cryptology - Crypto 2005,'' Springer-Verlag, (2005), 546-566.doi: 10.1007/11535218_33.


    M. G. Kuhn, Compromising emanations: Eavesdropping risks of computer displays, Technical Report 577, University of Cambridge Computer Laboratory, 2003, available online at http://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-577.pdf


    A. K. Lenstra, J. Hughes, M. Augier, J. Bos, T. Kleinjung and C. WachterRon was wrong, Whit is right, available online at http://eprint.iacr.org/2012/064.pdf


    M. Luby and C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions, SIAM J. Comput., 17 (1988), 373-386.doi: 10.1137/0217022.


    L. Lydersen, C. Wiechers, C. Wittmann, D. Elser, J. Skaar and V. Makarov, Hacking commercial quantum cryptography systems by tailored bright illumination, Nature Photonics, 4 (2010), 686-689.doi: 10.1038/nphoton.2010.214.


    J. Manger, A chosen ciphertext attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as standardized in PKCS #1 v2.0, in "Advances in Cryptology - Crypto 2001,'' Springer-Verlag, (2001), 230-238.doi: 10.1007/3-540-44647-8_14.


    J. Markoff, Researchers find a flaw in a widely used online encryption method, The New York Times, 15 February 2012, p. B4.


    K. McCurley, Language modeling and encryption on packet switched networks, in "Advances in Cryptology - Eurocrypt 2006,'' Springer-Verlag, (2006), 359-372.doi: 10.1007/11761679_22.


    A. Menezes, Another look at HMQV, J. Math. Crypt., 1 (2007), 47-64.


    A. Menezes, P. van Oorschot and S. Vanstone, "Handbook of Applied Cryptography,'' CRC Press, 1996.doi: 10.1201/9781439821916.


    A. Menezes and N. Smart, Security of signature schemes in a multi-user setting, Des. Codes Crypt., 33 (2004), 261-274.doi: 10.1023/B:DESI.0000036250.18062.3f.


    Z. MeraliHackers blind quantum cryptographers, Nature News, available online at http://www.nature.com/news/2010/100829/full/news.2010.436.html


    S. Micali and L. Reyzin, Physically observable cryptography, in "First Theory of Cryptography Conference - TCC 2004,'' Springer-Verlag, (2004), 278-296.


    P. Montgomery and R. Silverman, An FFT extension to the $P-1$ factoring algorithm, Math. Comput., 54 (1990), 839-854.


    M. Myers, C. Adams, D. Solo and D. Kapa, Internet X.509 certificate request message format, IETF RFC 2511, 1999, available online at http://www.rfc-editor.org/rfc/rfc2511.txt


    National Institute of Standards and Technology, Digital Signature Standard, FIPS Publication 186, 1994.


    National Security Agency, Tempest: A signal problem, approved for release 27 September 2007, available online at http://www.nsa.gov/public_info/_files/cryptologic_spectrum/tempest.pdf


    P. Nguyen and I. Shparlinski, The insecurity of the digital signature algorithm with partially known nonces, Des. Codes Crypt., 30 (2003), 201-217.doi: 10.1023/A:1025436905711.


    T. Okamoto, Provably secure and practical identification schemes and corresponding signature schemes, in "Advances in Cryptology - Crypto '92,'' Springer-Verlag, (1993), 31-53.doi: 10.1007/3-540-48071-4_3.


    K. Paterson, T. Ristenpart and T. Shrimpton, Tag size does matter: Attacks and proofs for the TLS record protocol, in "Advances in Cryptology - Asiacrypt 2011,'' Springer-Verlag, (2011), 371-389.doi: 10.1007/978-3-642-25385-0_20.


    K. Paterson and G. Watson, Plaintext-dependent decryption: A formal security treatment of SSH-CTR, in "Advances in Cryptology - Eurocrypt 2010,'' Springer-Verlag, (2010), 345-369.doi: 10.1007/978-3-642-13190-5_18.


    S. Pohlig and M. Hellman, An improved algorithm for computing logarithms over $GF(p)$ and its cryptographic significance, IEEE Trans. Inform. Theory, 24 (1978), 106-110.doi: 10.1109/TIT.1978.1055817.


    J. M. Pollard, Theorems on factorization and primality testing, Proc. Cambridge Philos. Soc., 76 (1974), 521-528.


    M. O. Rabin, Digitalized signatures and public-key functions as intractable as factorization, MIT/LCS/TR-212, MIT Laboratory for Computer Science, 1979.


    R. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Commun. ACM, 21 (1978), 120-126.doi: 10.1145/359340.359342.


    P. Rogaway, Practice-oriented provable security and the social construction of cryptography, Unpublished essay based on an invited talk at Eurocrypt 2009, May 6, 2009, available online at http://www.cs.ucdavis.edu/~rogaway/papers/cc.pdf


    P. Rogaway, M. Bellare and J. Black, OCB: A block-cipher mode of operation for efficient authenticated encryption, ACM Trans. Inform. Sys. Secur., 6 (2003), 365-403.doi: 10.1145/937527.937529.


    P. Rogaway and T. Shrimpton, A provable-security treatment of the key-wrap problem, in "Advances in Cryptology - Eurocrypt 2006,'' Springer-Verlag, (2006), 373-390.doi: 10.1007/11761679_23.


    RSA LaboratoriesPKCS #1 v2.1: RSA Cryptography Standard, available online at ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-1/pkcs-1v2-1.pdf


    RSA LaboratoriesPKCS #10 v1.7: Certification Request Syntax Standard, available online at ftp://ftp.rsasecurity.com/pub/pkcs/pkcs-10/pkcs-10v1_7.pdf


    D. Russell and G. T. Gangemi Sr., Computer security basics, in "TEMPEST,'' O'Reilly & Associates, 1991.


    F. Salmon, Recipe for disaster: the formula that killed Wall Street, Wired Magazine, 23 February 2009.


    V. Shoup, Why chosen ciphertext security matters, IBM Research Report RZ 3076 (#93122), 23 November 1998.


    F.-X. Standaert, How leaky is an extractor?, in "Progress in Cryptology - Latincrypt 2010,'' Springer-Verlag, (2010), 294-304.doi: 10.1007/978-3-642-14712-8_18.


    F.-X. Standaert, T. Malkin and M. Yung, A unified framework for the analysis of side-channel key recovery attacks, in "Advances in Cryptology - Eurocrypt 2009,'' Springer-Verlag, (2009), 443-461.doi: 10.1007/978-3-642-01001-9_26.


    N. Stephenson, "Cryptonomicon,'' Perennial, New York, 1999.


    C.-H. Tan, Key substitution attacks on some provably secure signature schemes, IEICE Trans. Fundam., E87-A (2004), 226-227.


    M. Turan, et al., Status report on the second round of the SHA-3 cryptographic hash algorithm competition, NIST Interagency Report 7764, 2011.


    S. Vaudenay, Provable security in block ciphers by decorrelation, in "15th Annual Symposium on Theoretical Aspects of Computer Science - STACS '98,'' Springer-Verlag, (1998), 249-275.


    D. Wagner, The boomerang attack, in "Fast Software Encryption - FSE '99,'' Springer-Verlag, (1999), 156-170.doi: 10.1007/3-540-48519-8_12.


    M. Whitehouse, Slices of risk, The Wall Street Journal, 12 September 2005.


    P. Wright, "Spycatcher - The Candid Autobiography of a Senior Intelligence Officer,'' William Heinemann, Australia, 1987.


    G. Yang, D. S. Wong, X. Deng and H. Wang, Anonymous signature schemes, in "Public Key Cryptography - PKC 2006,'' Springer-Verlag, (2006), 347-363.doi: 10.1007/11745853_23.


    T. Ylonen and C. Lonvick, The Secure Shell (SSH) Authentication Protocol, IETF RFC 4252, 2006, available online at http://www.rfc-editor.org/rfc/rfc4252.txt

  • 加载中

Article Metrics

HTML views() PDF downloads(381) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint