Cryptanalysis
The goal of cryptanalysis is to find some weakness or insecurity in a cryptographic scheme, thus permitting its subversion. It is an essential part of communications intelligence. Cryptanalysis might be undertaken by a malicious attacker, attempting to subvert a system, or by the system's designer (or others) attempting to evaluate whether a system has vulnerabilities. In modern practice, however, quality cryptographic algorithms and protocols have usually been carefully examined and many have been proved that establish practical security of the system (at least, under clear -- and hopefully reasonable -- assumptions).
It is a commonly held misconception that every encryption method can be broken. In connection with his WWII work at Bell Labs, Claude Shannon proved that the one-time pad cipher is unbreakable, provided the key material is truly random, never reused, kept secret from all possible attackers, and of equal or greater length than the message[1]. That is, an enemy who intercepts an encrypted message has provably no better chance of guessing the contents than an enemy who only knows the length of the message.
Even two-time use of the keys can lead to compromise, as shown by the VENONA project that allowed cryptanalysis of Soviet espionage traffic, in which a one-time pad was used more than once. [2]
Any cipher except a one-time pad can be broken with enough computational effort (by brute force attack if nothing else), but the amount of effort needed to break a cipher may be exponentially dependent on the key size, as compared to the effort needed to use the cipher. In such cases, effective security can still be achieved if some conditions (e.g., key size) are such that the effort ('work factor' in Shannon's terms) is beyond the ability of any adversary.
General types of cryptanalytic attacks
There are a wide variety of cryptanalytic attacks, and they can be classified in any of several ways. One distinction turns on what an attacker knows and can do. In a ciphertext-only attack, the cryptanalyst has access only to the ciphertext (modern cryptosystems are usually effectively immune to ciphertext-only attacks). In a known-plaintext attack, the cryptanalyst has access to a ciphertext and its corresponding plaintext (or to many such pairs). In a chosen-plaintext attack, the cryptanalyst may choose a plaintext and learn its corresponding ciphertext (perhaps many times); an example is the gardening used by the British during WWII. Finally, in a chosen-ciphertext attack, the cryptanalyst may choose ciphertexts and learn their corresponding plaintexts[3]. Also important, often overwhelmingly so, are mistakes (generally in the design or use of one of the protocols involved; see ULTRA for some historical examples of this).
Cryptanalysis of symmetric-key techniques typically involves looking for attacks against the block ciphers or stream ciphers that are more efficient than any attack that could be against a perfect cipher. For example, a simple brute force attack against DES requires one known plaintext and 255 decryptions, trying approximately half of the possible keys, before chances are better than even the key will have been found. But this may not be enough assurance; a linear cryptanalysis attack against DES requires 243 known plaintexts and approximately 243 DES operations[4]. This is a considerable improvement on brute force attacks.
Public-key algorithms are based on the computational difficulty of various problems. The most famous of these is integer factorization (the RSA cryptosystem is based on a problem related to factoring), but the discrete logarithm problem is also important. Much public-key cryptanalysis concerns numerical algorithms for solving these computational problems, or some of them, efficiently. For instance, the best algorithms for solving the elliptic curve-based version of discrete logarithm are much more time-consuming than the best known algorithms for factoring, at least for problems of equivalent size. Thus, other things being equal, to achieve an equivalent strength of attack resistance, factoring-based encryption techniques must use larger keys than elliptic curve techniques. For this reason, public-key cryptosystems based on elliptic curves have become popular since their invention in the mid-1990s.
While pure cryptanalysis uses weaknesses in the algorithms themselves, other attacks on cryptosystems are based on actual use of the algorithms in real devices, known as side-channel attacks. If a cryptanalyst has access to, say, the amount of time the device took to encrypt a number of plaintexts or report an error in a password or PIN character, he may be able to use a timing attack to break a cipher that is otherwise resistant to analysis. An attacker might also study the pattern and length of messages to derive valuable information; this is known as traffic analysis[5], and can be quite useful to an alert adversary. And, of course, social engineering, and other attacks against personnel who work with cryptosystems or the messages they handle (e.g., bribery, extortion, blackmail, espionage, ...) may be most productive attacks of all.
Vulnerabilities of cryptographic primitives
Much of the theoretical work in cryptography concerns cryptographic primitives — algorithms with basic cryptographic properties — and their relationship to other cryptographic problems. For example, a one-way function is a function intended to be easy to compute but hard to invert. In a very general sense, for any cryptographic application to be secure (if based on such computational feasibility assumptions), one-way functions must exist. However, if one-way functions exist, this implies that P ≠ NP.[6]. Since the P versus NP problem is currently unsolved, we don't know if one-way functions exist. If they do, however, we can build other cryptographic tools from them. For instance, if one-way functions exist, then secure pseudorandom generators and secure pseudorandom functions exist[7].
Other cryptographic primitives include cipher algorithms themselves, one-way permutations, trapdoor permutations, etc.
Vulnerabilities of cryptographic protocols
In many cases, cryptographic techniques involve back and forth communication among two or more parties in space or across time (e.g., cryptographically protected backup data). The term cryptographic protocol captures this general idea. Cryptographic protocols have been developed for a wide range of problems, including relatively simple ones like interactive proofs[8], secret sharing[9][10], and zero-knowledge[11], and much more complex ones like electronic cash[12] and secure multiparty computation[13].
When the security of a cryptographic system fails, it is rare that the vulnerabilty leading to the breach will have been in a quality cryptographic primitive. Instead, weaknesses are often mistakes in the protocol design (often due to inadequate design procedures or less than thoroughly informed designers), in the implementation (e.g., a software bug), in a failure of the assumptions on which the design was based (e.g., proper training of those who will be using the system), or some other human error. Many cryptographic protocols have been designed and analyzed using ad hoc methods. Methods for formally analyzing the security of protocols, based on techniques from mathematical logic (see for example BAN logic), and more recently from concrete security principles, have been the subject of research for the past few decades[14][15][16]. Unfortunately, these tools are cumbersome and not widely used for complex designs.
References
- ↑ "Shannon": Claude Shannon and Warren Weaver, "The Mathematical Theory of Communication", University of Illinois Press, 1963, ISBN 0-252-72548-4
- ↑ National Security Agency, VENONA
- ↑ Menezes, AJ; PC van Oorschot & SA Vanstone (Fifth Edition, 2001), Handbook of Applied Cryptography, ISBN 0-8493-8523-7
- ↑ Pascal Junod, "On the Complexity of Matsui's Attack", SAC 2001.
- ↑ Dawn Song, David Wagner, and Xuqing Tian, "Timing Analysis of Keystrokes and Timing Attacks on SSH", In Tenth USENIX Security Symposium, 2001.
- ↑ Goldreich, Oded (2001), Foundations of Cryptography, Volume 1: Basic Tools, Cambridge University Press, ISBN 0-521-79172-3
- ↑ J. Håstad, R. Impagliazzo, L.A. Levin, and M. Luby, "A Pseudorandom Generator From Any One-Way Function", SIAM J. Computing, vol. 28 num. 4, pp 1364–1396, 1999.
- ↑ László Babai. "Trading group theory for randomness". Proceedings of the Seventeenth Annual Symposium on the Theory of Computing, ACM, 1985.
- ↑ G. Blakley. "Safeguarding cryptographic keys." In Proceedings of AFIPS 1979, volume 48, pp. 313-317, June 1979.
- ↑ A. Shamir. "How to share a secret." In Communications of the ACM, volume 22, pp. 612-613, ACM, 1979.
- ↑ S. Goldwasser, S. Micali, and C. Rackoff, "The Knowledge Complexity of Interactive Proof Systems", SIAM J. Computing, vol. 18, num. 1, pp. 186-208, 1989.
- ↑ S. Brands, "Untraceable Off-line Cash in Wallets with Observers", In Advances in Cryptology -- Proceedings of CRYPTO, Springer-Verlag, 1994.
- ↑ R. Canetti, "Universally composable security: a new paradigm for cryptographic protocols", In Proceedings of the 42nd annual Symposium on the Foundations of Computer Science (FOCS), pp. 136-154, IEEE, 2001.
- ↑ D. Dolev and A. Yao, "On the security of public key protocols", IEEE transactions on information theory, vol. 29 num. 2, pp. 198-208, IEEE, 1983.
- ↑ M. Abadi and P. Rogaway, "Reconciling two views of cryptography (the computational soundness of formal encryption)." In IFIP International Conference on Theoretical Computer Science (IFIP TCS 2000), Springer-Verlag, 2000.
- ↑ D. Song, "Athena, an automatic checker for security protocol analysis", In Proceedings of the 12th IEEE Computer Security Foundations Workshop (CSFW), IEEE, 1999.