ciphers in the SSH protocols and
their implementations. Required algorithms are in bold;, recommended
ones are italic; the others are optional. Parentheses indicate an
algorithm not defined in the protocol, but provided in some
implementation. The meanings of the entries are:
The free version of SSH2 supports only the required DSA for public
keys, while the commercial F-Secure SSH2 Server adds partial support
for RSA keys for user authentication. [
].
The F-Secure server starts if its host key is RSA and reports that it
successfully read the key. However, it still advertises its host key
type as DSA in its key-exchange messages and then supplies the RSA
key anyway, causing clients to fail when they try to read the
supplied key. Of course, this problem masks the question of whether
the client can handle an RSA host key even if it were properly
identified. OpenSSH/2 doesn't contain RSA support at all, but
now that the RSA patent has expired, the ssh-rsa key type will be
added to the SSH-2 protocol, and support should follow shortly.
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.
3.9.1. Public-Key Algorithms
3.9.1.1. Rivest-Shamir-Adleman (RSA)
The
Rivest-Shamir-Adleman
public-key algorithm (RSA) 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 United 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 USA, 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). They no longer support or
distribute this toolkit, though it is commonly available. Since RSA
is now in the public domain, there's no longer any reason to
use RSAref. It is no longer supported, some versions contain security
flaws, and there are better implementations out there; we discourage
its use.
The SSH-1 protocol specifies use of RSA explicitly. SSH-2 can use
multiple public-key algorithms, but it defines only DSA. [
Section 3.9.1.2, "Digital Signature Algorithm (DSA)"] The SECSH working group plans to add the RSA
algorithm to SSH-2 now that the patent has expired. In the meantime,
only the F-Secure SSH2 Server implements RSA keys in SSH2, using the
global key-format identifier "ssh-rsa". This isn't
yet part of the draft standard: to be technically correct it should
use a localized name, e.g.,
[email protected].
[
Section 3.5.1.1, "Algorithm choice and negotiation"] However, this is unlikely to cause a
real problem. The feature is useful for authentication to an SSH2
server with an existing SSH1 key, so you don't need to generate
a new (DSA) key.
3.9.1.2. Digital Signature Algorithm (DSA)
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.
[37] Researcher Gus Simmons discovered a
subliminal channel in DSA that allows an implementor to leak
information -- for instance, secret key bits -- with every
signature.
[38] 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, 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.
3.9.1.3. Diffie-Hellman key agreement
The
Diffie-Hellman key agreement algorithm
was the original public-key system, 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.
3.9.2. Secret-Key Algorithms
3.9.2.1. International Data Encryption Algorithm (IDEA)
The
International
Data Encryption Algorithm (IDEA) was designed in 1990 by Xuejia Lai
and James Massey,
[39] 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 United States by the Swiss company
Ascom-Tech AG.
[40] The name "IDEA" is a
trademark of Ascom-Tech. The attitude of Ascom-Tech towards this
patent and the use of IDEA in the United States 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:
http://www.ascom.ch/infosec/idea.html
http://www.it-sec.com/index_e.php
3.9.2.2. Data Encryption Standard (DES)
The
Data Encryption Standard (DES) is the
aging workhorse of symmetric encryption algorithms. 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 becoming 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. Because of these weaknesses, NIST
is currently in the process of selecting a successor to DES, called
the Advanced Encryption Standard (AES).
3.9.2.3. Triple-DES
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
doesn't form a group over its keys,
[41] which means that encrypting multiple times with
independent keys can increase security. 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.
3.9.2.4. ARCFOUR (RC4)
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-sized key; SSH-1 employs independent 128-bits 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.
3.9.2.5. Blowfish
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-sized 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.counterpane.com/blowfish.html
3.9.2.6. Twofish
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. Two years later, it is one of the five finalists
in the AES selection process, out of 15 initial submissions. 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.counterpane.com/twofish.html
You can read more about the NIST AES program at:
http://www.nist.gov/aes/
3.9.2.7. CAST
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.
3.9.2.8. Speed comparisons
We ran some simple experiments to
rank the bulk ciphers in order of speed. Since there is no single SSH
package that contains all of the ciphers, we present two experiments
to cover them all.
Table 3-7 and
Table 3-8 show the time required to
transfer a 5-MB file from a 300-MHz Linux box to a 100-MHz Sparc-20
over an otherwise unloaded 10-base-T Ethernet.
Table 3-7. Transferring with scp2 (F-Secure SSH2 2.0.13)
|
Cipher |
Transfer Time (seconds) |
Throughput (KB/second) |
|
RC4 |
22.5 |
227.4 |
|
Blowfish |
24.5 |
208.6 |
|
CAST-128 |
26.4 |
193.9 |
|
Twofish |
28.2 |
181.3 |
|
3DES |
51.8 |
98.8 |
Table 3-8. Same Test with scp1 (SSH-1.2.27)
|
Cipher |
Transfer Time (seconds) |
Throughput (KB/second) |
|
RC4 |
5 |
1024.0 |
|
Blowfish |
6 |
853.3 |
|
CAST-128 |
7 |
731.4 |
|
Twofish |
14 |
365.7 |
|
3DES |
15 |
341.3 |
This is necessarily a gross comparison, and we provide it only as a
rough guideline. Remember that these numbers reflect the performance
of particular implementations, not the algorithms themselves, tested
in a single configuration. Your mileage may vary. Objects in mirror
are closer than they appear.
Note that
scp1 is roughly four times faster than
scp2. This is due to a major implementation
difference:
scp1 uses the
scp1
-t server, whereas
scp2
uses the SFTP subsystem. [
Section 7.5.9, "For Internal Use Only"] Nonetheless,
the relative cipher speed comparisons do agree where they overlap.
We must emphasize that we included RC4 in the SSH1 test only for
completeness; due to security vulnerabilities, RC4 shouldn't
ordinarily be used with the SSH-1 protocol.
3.9.3. Hash Functions
3.9.3.1. CRC-32
The 32-bit
Cyclic Redundancy
Check (CRC-32), defined in ISO 3309,
[42] 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
later. [
Section 3.10.5, "The Insertion Attack"] The SSH-2 protocol employs
cryptographically strong hash functions for integrity checking,
obviating this attack.
3.9.3.2. MD5
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
themselves recommend moving away from MD5 in favor of SHA-1 or
RIPEMD-160 for future applications demanding
collision-resistance.
[43]
3.9.3.3. SHA-1
SHA-1 (Secure Hash Algorithm) was
designed by the NSA and 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 is starting to
replace MD5 in some applications; for example, SSH-2 uses SHA-1 as
its required MAC hash function, as opposed to MD5 in SSH-1.
3.9.3.4. RIPEMD-160
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;
[44]
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 (
http://www.analysys.com). 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 (
http://ripem.msu.edu/ ).
RIPEMD-160 isn't defined in the SSH protocol, but it is used
for an implementation-specific MAC algorithm in OpenSSH, under the
name
[email protected]. 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
