We now summarize each of the algorithms we have mentioned. Don't treat these summaries as complete analyses, however. You can't necessarily extrapolate from characteristics of individual algorithms (positive or negative) to whole systems without considering the other parts. Security is complicated that way.
The Rivest-Shamir-Adleman (RSA) public-key algorithm is the most widely used asymmetric cipher. It derives its security from the difficulty of factoring large integers
that are the product of two large primes of roughly equal size. Factoring is widely believed to be intractable (i.e., infeasible, admitting no efficient, polynomial-time solution), although this isn't proven. RSA can be used for both encryption and signatures.
Until September 2000, RSA was claimed to be patented in the U.S. states by Public Key Partners, Inc., a company in which RSA Security, Inc. is a partner. (The algorithm is now in the public domain.) While the patent was in force, PKP claimed that it controlled the use of the RSA algorithm in the U.S., and that the use of unauthorized implementations was illegal. Until the mid-1990s, RSA Security provided a freely available reference implementation, RSAref, with a license allowing educational and broad commercial use (as long as the software itself was not sold for profit). Since RSA is now in the public domain, RSAref has disappeared.
The SSH-1 protocol specified use of RSA explicitly. SSH-2 can use multiple public-key algorithms, but originally defined only DSA. [3.8.1.2] The SECSH working group added the RSA algorithm to SSH-2 shortly after the patent expired.
The Digital Signature Algorithm (DSA) was developed by the U.S. National Security Agency (NSA), and promulgated by the U.S. National Institute of Standards and Technology (NIST) as part of the Digital Signature Standard (DSS). The DSS was issued as a Federal Information Processing Standard, FIPS-186, in May 1994. It is a public-key algorithm, based on the Schnorr and ElGamal methods, and relies on the difficulty of computing discrete logarithms in a finite field. It is designed as a signature-only scheme that can't be used for encryption, although a fully general implementation may easily perform both RSA and ElGamal encryption.
DSA has also been surrounded by a swirl of controversy since its inception. The NIST first claimed that it had designed DSA, then eventually revealed that the NSA had done so. Many question the motives and ethics of the NSA, with ample historical reason to do so.[27] Researcher Gus Simmons discovered a subliminal channel in DSA that allows an implementor to leak information—for instance, secret key bits—with every signature.[28] Since the algorithm was to be made available as a closed hardware implementation in smart cards as part of the government's Capstone program, many people considered this property highly suspicious. Finally, the NIST intended DSA to be available royalty-free to all users. To that end it was patented by David Kravitz (patent #5,231,668), then an employee of the NSA, who assigned the patent to the U.S. government. There have been claims, however, that DSA infringes existing cryptographic patents, including the Schnorr patent. To our knowledge, this issue has yet to be settled in court.
The SSH-2 protocol uses DSA as its required (and currently, only defined) public-key algorithm for host identification.
The Diffie-Hellman key agreement algorithm was the first public-key system published in the open literature, invented by Whitfield Diffie, Martin Hellman, and Ralph Merkle in 1976. It was patented by them in 1977 (issued in 1980, patent #4,200,770); that patent has now expired, and the algorithm is in the public domain. Like DSA, it is based on the discrete logarithm problem, and it allows two parties to derive a shared secret key securely over an open channel. That is, the parties engage in an exchange of messages, at the end of which they share a secret key. It isn't feasible for an eavesdropper to determine the shared secret merely from observing the exchanged messages.
SSH-2 uses the Diffie-Hellman algorithm as its required (and currently, its only defined) key-exchange method.
The International Data Encryption Algorithm (IDEA) was designed in 1990 by Xuejia Lai and James Massey,[29] and went through several revisions, improvements, and renamings before reaching its current form. Although relatively new, it is considered secure; the well-known cryptographer Bruce Schneier in 1996 pronounced it "the best and most secure block algorithm available to the public at this time."
IDEA is patented in Europe and the U.S. by the Swiss company Ascom-Tech AG.[30] The name "IDEA" is a trademark of Ascom-Tech. The attitude of Ascom-Tech toward this patent and the use of IDEA in the U.S. has changed over time, especially with regard to its inclusion in PGP. It is free for noncommercial use. Government or commercial use may require a royalty, where "commercial use" includes use of the algorithm internal to a commercial organization, not just directly selling an implementation or offering its use for profit. Here are two sites for more information:
In 1997, the NIST began a program to develop a replacement for the existing government-standard symmetric encryption algorithm, DES, which was beginning to show its age. The process involved soliciting designs from the worldwide cryptographic community, and pitting them against one another in a design contest of sorts. After a five-year process, the winner was finally selected. The algorithm designed by Joan Daemen and Vincent Rijmen and originally known as Rijndael became the Advanced Encryption Standard, codified in FIPS-197. AES is a symmetric block cipher with key sizes of either 128, 192, or 256 bits. You can find more information at the following site:
| http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf |
The Data Encryption Standard (DES) is the old workhorse of symmetric encryption algorithms, now finally put out to pasture, replaced by AES. Designed by researchers at IBM in the early 1970s under the name Lucifer, the U.S. government adopted DES as a standard on November 23, 1976 (FIPS-46). It was patented by IBM, but IBM granted free worldwide rights to its use. It has been used extensively in the public and private sectors ever since. DES has stood up well to cryptanalysis over the years and is increasingly viewed as outdated only because its 56-bit key size is too small relative to modern computing power. A number of well-publicized designs for special-purpose "DES-cracking" machines have been put forward, and their putative prices are falling more and more into the realm of plausibility for governments and large companies. It seems sure that at least the NSA has such devices.
Triple-DES, or 3DES, is a variant of DES intended to increase its security by increasing the key length. It has been proven that the DES function can increase its security by encrypting multiple times with independent keys.[31] 3DES encrypts the plaintext with three iterations of the DES algorithm, using three separate keys. The effective key length of 3DES is 112 bits, a vast improvement over the 56-bit key of plain DES.
Ron Rivest designed the RC4 cipher in 1987 for RSA Data Security, Inc. (RSADSI); the name is variously claimed to stand for "Rivest Cipher" or "Ron's Code." It was an unpatented trade secret of RSADSI, used in quite a number of commercial products by RSADSI licensees. In 1994, though, source code claiming to implement RC4 appeared anonymously on the Internet. Experimentation quickly confirmed that the posted code was indeed compatible with RC4, and the cat was out of the bag. Since it had never been patented, RC4 effectively entered the public domain. This doesn't mean that RSADSI won't sue someone who tries to use it in a commercial product, so it is less expensive to settle and license than to fight. We aren't aware of any test cases of this issue. Since the name "RC4" is trademarked by RSADSI, the name "ARCFOUR" has been coined to refer to the publicly revealed version of the algorithm.
ARCFOUR is very fast but less studied than many other algorithms. It uses a variable-size key; SSH-1 employs independent 128-bit keys for each direction of the SSH session. The use of independent keys for each direction is an exception in SSH-1, and crucial: ARCFOUR is essentially a pad using the output of a pseudo-random number generator. As such, it is important never to reuse a key because to do so makes cryptanalysis trivially easy. If this caveat is observed, ARCFOUR is considered secure by many, despite the dearth of public cryptanalytic results.
Blowfish was designed by Bruce Schneier in 1993, as a step toward replacing the aging DES. It is much faster than DES and IDEA, though not as fast as ARCFOUR, and is unpatented and free for all uses. It is intended specifically for implementation on large, modern, general-purpose microprocessors and for situations with relatively few key changes. It isn't particularly suited to low-end environments such as smart cards. It employs a variable-size key of 32 to 448 bits; SSH-2 uses 128-bit keys. Blowfish has received a fair amount of cryptanalytic scrutiny and has proved impervious to attack so far. Information is available from Counterpane, Schneier's security consulting company, at:
| http://www.schneier.com/blowfish.html |
Twofish is another design by Bruce Schneier, together with J. Kelsey, D. Whiting, D. Wagner, C. Hall, and N. Ferguson. It was submitted in 1998 to the NIST as a candidate for the Advanced Encryption Standard, to replace DES as the U.S. government's symmetric data encryption standard. It was one of the five finalists in the AES selection process, out of 15 initial submissions, but eventually lost to Rijndael. Like Blowfish, it is unpatented and free for all uses, and Counterpane has provided uncopyrighted reference implementations, also freely usable.
Twofish admits keys of lengths 128, 192, or 256 bits; SSH-2 specifies 256-bit keys. Twofish is designed to be more flexible than Blowfish, allowing good implementation in a larger variety of computing environments (e.g., slower processors, small memory, in-hardware). It is very fast, its design is conservative, and it is likely to be quite strong. You can read more about Twofish at:
| http://www.schneier.com/twofish.html |
You can read more about the NIST AES program at:
| http://www.nist.gov/aes/ |
CAST was designed in the early 1990s by Carlisle Adams and Stafford Tavares. Tavares is on the faculty of Queen's University at Kingston in Canada, while Adams is an employee of Entrust Technologies of Texas. CAST is patented, and the rights are held by Entrust, which has made two versions of the algorithm available on a worldwide royalty-free basis for all uses. These versions are CAST-128 and CAST-256, described in RFC-2144 and RFC-2612, respectively. SSH-2 uses CAST-128, which is named for its 128-bit key length.
The 32-bit Cyclic Redundancy Check (CRC-32), defined in ISO 3309,[32] is a noncryptographic hash function for detecting accidental changes to data. The SSH-1 protocol uses CRC-32 (with the polynomial 0xEDB88320) for integrity checking, and this weakness admits the "insertion attack" discussed elsewhere. [3.5] The SSH-2 protocol employs cryptographically strong hash functions for integrity checking, obviating this attack.
MD5 ("Message Digest algorithm number 5") is a cryptographically strong, 128-bit hash algorithm designed by Ron Rivest in 1991, one of a series he designed for RSADSI (MD2 through MD5). MD5 is unpatented, placed in the public domain by RSADSI, and documented in RFC-1321. It has been a standard hash algorithm for several years, used in many cryptographic products and standards. A successful collision attack against the MD5 compression function by den Boer and Bosselaers in 1993 caused some concern, and though the attack hasn't resulted in any practical weaknesses, there is an expectation that it will, and people are beginning to avoid MD5 in favor of newer algorithms. RSADSI recommends moving away from MD5 in favor of SHA-1 or RIPEMD-160 for future applications demanding collision-resistance.[33]
SHA-1 (Secure Hash Algorithm) was designed by the NSA and the NIST for use with the U.S. government Digital Signature Standard. Like MD5, it was designed as an improvement on MD4, but takes a different approach. It produces 160-bit hashes. There are no known attacks against SHA-1, and, if secure, it is stronger than MD5 simply for its longer hash value. It has replaced MD5 in some applications; for example, SSH-2 uses SHA-1 as its required MAC hash function, as opposed to MD5 in SSH-1.[34]
Yet another 160-bit MD4 variant, RIPEMD-160, was developed by Hans Dobbertin, Antoon Bosselaers, and Bart Preneel as part of the European Community RIPE project. RIPE stands for RACE Integrity Primitives Evaluation;[35] RACE, in turn, was the program for Research and Development in Advanced Communications Technologies in Europe, an EC-sponsored program which ran from June 1987 to December 1995. RIPE was part of the RACE effort, devoted to studying and developing data integrity techniques. Hence, RIPEMD-160 should be read as "the RIPE Message Digest (160 bits)." In particular, it has nothing to do with RIPEM, an old Privacy-Enhanced Mail (PEM) implementation by Mark Riordan.
RIPEMD-160 isn't defined in the SSH protocol, but it is used
for an implementation-specific MAC algorithm in OpenSSH, under the
name
hmac-ripemd160@openssh.com . RIPEMD-160 is
unpatented and free for all uses. You can read more about it
at:
| http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html |
zlib is currently the only compression algorithm defined for SSH. In the SSH protocol documents, the term "zlib" refers to the "deflate" lossless compression algorithm as first implemented in the popular gzip compression utility, and later documented in RFC-1951. It is available as a software library called ZLIB at:
| http://www.zlib.net/ |
[27] See James Bamford's book, The Puzzle Palace (Penguin), for an investigative history of the NSA.
[28] G. J. Simmons, "The Subliminal Channels in the U.S. Digital Signature Algorithm (DSA)." Proceedings of the Third Symposium on: State and Progress of Research in Cryptography, Rome: Fondazione Ugo Bordoni, 1993, pp. 35-54.
[29] X. Lai and J. Massey, "A Proposal for a New Block Encryption Standard," Advances in Cryptology—EUROCRYPT '92 Proceedings, Springer-Verlag, 1992, pp. 389-404.
[30] U.S. patent #5,214,703, 25 May 1993; international patent PCT/CH91/00117, 28 November 1991; European patent EP 0 482 154 B1.
[31] Because it doesn't form a group over its keys. See W. Campbell and M. J. Wiener, "DES Is Not a Group," Advances in Cryptology—CRYPTO '92 Proceedings, Springer-Verlag, pp. 512-520.
[32] International Organization for Standardization, ISO Information Processing Systems—Data Communication High-Level Data Link Control Procedure—Frame Structure, ISO 3309, October 1984, 3rd Edition.
[33] RSA Laboratories Bulletin #4, 12 November 1996, ftp://ftp.rsasecurity.com/pub/pdfs/bulletn4.pdf.
[34] As this book went to press, the NIST announced plans to phase out SHA-1 by the year 2010, in favor of stronger algorithms like SHA-256 and SHA-512.
[35] Not to be confused with another "RIPE," Réseaux IP Européens ("European IP Networks"), a technical and coordinating association of entities operating wide area IP networks in Europe and elsewhere (http://www.ripe.net).