|
|
|
Cryptographic Algorithms
This page lists commonly used cryptographic algorithms and methods, and
tries to give references to implementations and textbooks. Where available,
comments are also made about the usefulness or other aspects of the
algorithms. The comments should be interpreted as the author's subjective
opinion and should not be considered authoritative in any way.
Public key algorithms use a different key for encryption and decryption,
and the decryption key cannot (practically) be derived from the encryption
key. Public key methods are important because they can be used to transmit
encryption keys or other data securely even when the parties have no
opportunity to agree on a secret key in private. All known methods are quite
slow, and they are usually only used to encrypt session keys (randomly
generated "normal" keys), that are then used to encrypt the bulk of the data
using a symmetric cipher (see below).
- RSA (Rivest-Shamir-Adelman) is the most commonly
used public key algorithm. Can be used both for encryption and for signing.
It is generally considered to be secure when sufficiently long keys are used
(512 bits is insecure, 768 bits is moderately secure, and 1024 bits is good).
The security of RSA relies on the difficulty of factoring large integers.
Dramatic advances in factoring large integers would make RSA vulnerable. RSA
is currently the most important public key algorithm. It is patented in the
United States (expires year 2000), and free elsewhere.
For information on the recommended key lengths for RSA, see for example the
book "Applied Cryptography" by Bruce Schneier. At
present, 512 bit keys are considered weak, 1024 bit keys are probably secure
enough for most purposes, and 2048 bit keys are likely to remain secure for
decades.
One should know that RSA is very vulnerable to chosen plaintext attacks. There is
also a new timing attack that can be
used to break many implementations of RSA. The RSA algorithm is believed to
be safe when used properly, but one must be very careful when using it to
avoid these attacks.
Many implementations of RSA are freely available. See e.g.
ftp.funet.fi:/pub/crypt/cryptography/asymmetric/rsa.
For more information, see e.g.
- Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
- Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to
Computer Security. Prentice-Hall, 1989.
- Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill,
1994.
- R. Rivest, A. Shamir, and L. M. Adleman: Cryptographic Communications
System and Method. US Patent 4,405,829, 1983.
- Hans Riesel: Prime Numbers and Computer Methods for Factorization.
Birkhauser, 1994.
- Sherry Mayo's
cryptography page contains a description of RSA.
- Diffie-Hellman is a commonly used
public-key algorithm for key exchange. It is generally considered to be
secure when sufficiently long keys and proper generators are used. The
security of Diffie-Hellman relies on the difficulty of the discrete logarithm
problem (which is believed to be computationally equivalent to factoring large
integers).
Diffie-Hellman is sensitive to the choice of the strong prime and the
generator. The size of
the secret exponent is also important for its security. Conservative advice is
to make the random exponent twice as long as the intended session key.
One should note the results presented in Brian A. LaMacchia and Andrew M.
Odlyzko, Computation of Discrete
Logarithms in Prime Fields, Designs, Codes and Cryptography 1 (1991),
47-62. Basically, they conclude that by doing precomputations, it is possible
to compute discrete logarithms relative to a particular prime efficiently.
The work needed for the precomputation is approximately equal or slightly
higher than the work needed for factoring a composite number of the same size.
In practice this means that if the same prime is used for a large number of
exchanges, it should be larger than 512 bits in size, preferably 1024
bits.
There is also a new timing attack
that can be used to break many implementations of Diffie-Hellman.
For further information, see e.g.
- Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1994.
- Jennifer Seberry and Josed Pieprzyk: Cryptography: An Introduction to
Computer Security. Prentice-Hall, 1989.
- Man Young Rhee: Cryptography and Secure Data Communications. McGraw-Hill,
1994.
- M. E. Hellman and R. C. Merkle: Public Key Cryptographic Apparatus and
Method. US Patent 4,218,582, 1980.
Elliptic curve public key cryptosystems is an
emerging field. They have been slow to execute, but have become feasible with
modern computers. They are considered to be fairly secure, but haven't yet
undergone the same scrutiny as for example RSA.
For further information, see e.g.
- Bruce Schneier: Applied Cryptography, 2nd edition. John Wiley & Sons,
1995.
- IEEE P1363 Draft Standard on Elliptic Curve
Cryptosystems and Related Methods.
- DSS (Digital Signature Standard). A
signature-only mechanism endorsed by the United States Government. Its design
has not been made public, and many people have found potential problems with
it (e.g., leaking hidden data the signature, and revealing your secret key if
you ever happen to sign two different messages using the same random number).
- ElGamal public key cryptosystem. Based on
the discrete logarithm problem. See e.g. Bruce Schneier: Applied
Cryptography, John Wiley and Sons, 1994.
- LUC is a public key encryption system. It uses
Lucas functions instead of exponentiation. It's inventor Peter Smith has since
then implemented four other algorithms with Lucas functions: LUCDIF, a key
negotiation method like Diffie-Hellman; LUCELG PK, equivalent to El Gamal
public-key encryption; LUCELG DS, equivalent to El Gamal digital signature;
and LUCDSA, equivalent to the US Digital Siganture Standard. LUC Encryption
Technology Ltd has obtained patents for cryptographic use of Lucas
functions in United States and New Zealand.
Source code can be found in
ftp.funet.fi:/pub/crypt/cryptography/asymmetric/luc
Secret key algorithms use a the same key for both encryption and decryption
(or the other is easily derivable from the other).
- DES is an algorithm developed in the 1970s. It
was made a standard by the US government, and has also been adopted by several
other governments worldwide. It is widely used, especially in the financial
industry.
DES is a block cipher with 64-bit block size. It uses 56-bit keys. This
makes it fairly easy to break with modern computers or special-purpose
hardware. DES is still strong enough to keep most random hackers and
individuals out, but it is easily breakable with special hardware by
government, criminal organizations, or major corporations. In large volumes,
the cost of beaking DES keys is on the order of tens of dollars. DES is
getting too weak, and should not be used in new designs.
A variant of DES, Triple-DES or 3DES is based on using DES three
times (normally in an encrypt-decrypt-encrypt sequence with three different,
unrelated keys). Many people consider Triple-DES to be much safer than plain
DES.
- Blowfish is an algorithm developed by Bruce
Schneier. It is a block cipher with 64-bit block size and variable length
keys (up to 448 bits). It has gained a fair amount of acceptance in a number
of applications. No attacks are known against it.
Blowfish is used in a number of popular software packages, including
Nautilus and PGPfone.
- IDEA (International Data Encryption Algorithm)
is an algorithm developed at ETH Zurich in Switzerland. It uses a 128 bit
key, and it is generally considered to be very secure. It is currently one of
the best public known algorithms. It is a fairly new algorithm, but it has
already been around for several years, and no practical attacks on it have
been published despite of numberous attempts to analyze it.
IDEA is patented in the United States and in most of the European
countries. The patent is held by Ascom-Tech. Non-commercial use of IDEA is
free. Commercial licenses can be obtained by contacting idea@ascom.ch.
- RC4 is a cipher designed by RSA Data Security,
Inc. It used to be a trade secret, until someone posted source code for an
algorithm in Usenet News, claiming it to be equivalent to RC4. There is very
strong evidence that the posted algorithm is indeed equivalent to RC4. The
algorithm is very fast. Its security is unknown, but breaking it does not
seem trivial either. Because of its speed, it may have uses in certain
applications. It can also accept keys of arbitrary length. RC4 is
essentially a pseudo random number generator, and the output of the generator
is xored with the data stream. For this reason, it is very important that the
same RC4 key never be used to encrypt two different data streams.
The United States government routinely approves RC4 with 40 bit keys for
export. Keys that are this small can be easily broken by governments,
criminals, and amateurs.
- SAFER is an algorithm developed by J. L.
Massey (one of the developers of IDEA). It is claimed to provide secure
encryption with fast software implementation even on 8-bit processors. Two
variants are available, one for 64 bit keys and the other for 128 bit keys.
An implementation is in
ftp.funet.fi:/pub/crypt/cryptography/symmetric/safer.
An analysis of SAFER-K64 was presented in Crypto'95 and is in the
proceedings.
- Ciphers based on a hash function. Any cryptographically strong
hash function (see below) can be turned into a cipher. There are several
possible arrangements; the general idea is that the hash function is used as a
random number generator, and the hash value is xored with the data to be
encrypted. When all bytes of the hash value have been used, a new hash value
is obtained by modifying the key (or whatever was hashed) somehow, and taking
a hash of that. The data to be hashed may include a key, the previous hash
value, a sequence number, previous plaintext, etc.
- Enigma was the cipher used by the Germans in
World War II. It is trivial to solve with modern computers. This cipher is
used by the unix crypt(1) program, which should thus not be used.
- Vigenere is a historical cipher mentioned
in many textbooks. It is easily solvable.
- Several other classical ciphers are described in
http://rschp2.anu.edu.au:8080/cipher.html. These ciphers should not be
used because they are not secure.
These and a number of other ciphers are available from
ftp.funet.fi:/pub/crypt/cryptography/symmetric .
Many commonly used ciphers (e.g., IDEA, DES, BLOWFISH) are block ciphers.
This means that they take a fixed-size block of data (usually 64 bits), an
transform it to another 64 bit block using a function selected by the key.
The cipher basically defines a one-to-one mapping from 64-bit integers to
another permutation of 64-bit integers.
If the same block is encrypted twice with the same key, the resulting
ciphertext blocks are the same (this method of encryption is called Electronic
Code Book mode, or ECB). This information could be useful for an
attacker.
In practical applications, it is desirable to make identical plaintext
blocks encrypt to different ciphertext blocks. Two methods are commonly used
for this:
- CFB mode: a ciphertext block is obtained by encrypting the previous
ciphertext block, and xoring the resulting value with the plaintext.
- CBC mode: a ciphertext block is obtained by first xoring the
plaintext block with the previous ciphertext block, and encrypting the
resulting value.
The previous ciphertext block is usually stored in an Initialization Vector
(IV). An initialization vector of zero is commonly used for the first block,
though other arrangements are also in use.
More information on cipher modes can be found e.g. in Bruce Schneier:
Applied Cryptography, John Wiley & Sons, 1994.
- MD5 (Message Digest Algorithm 5) is a secure
hash algorithm developed at RSA Data Security, Inc. It can be used to hash an
arbitrary length byte string into a 128 bit value. MD5 is in wide use, and is
considered reasonably secure.
However, some people have reported potential weaknesses in it, and "keyed
MD5" (typically used for authentication by having a shared secret, and
computing an authentication value by hashing first the secret (as a key), and
then the data to be hashed) has been reported to be broken. It is also
reported that one could build a special-purpose machine costing a few million
dollars to find a plaintext matching given hash value in a few weeks.
MD5 is available from
ftp.funet.fi:/pub/crypt/hash/mds/md5 .
MD5 is described e.g. in Bruce
Schneier: Applied Cryptography, John Wiley & Sons, 1994.
- MD2, MD4: These are older hash algorithms from RSA Data
Security. They have known flaws, and their use is not recommended.
Source code is available from
ftp.funet.fi:/pub/crypt/hash/mds.
- SHA (Secure Hash Algorithm) (also SHS,
Secure Hash Standard): This is a cryptographic hash algorithm published by the
United States Government. It produces an 160 bit hash value from an arbitrary
length string. Many people consider it quite good. It is a fairly new
algorithm.
SHA is available from
ftp.funet.fi:/pub/crypt/hash/sha, and is included in many cryptographic
libraries.
The official standard text can be found
here.
- Tiger is a new hash algorithm developed by Anderson and Biham. It
is available from ftp.funet.fi:/pub/crypt/hash/tiger.
- Most recent hash algorithm is RIPEMD-160, which is designed to
replace MD4 and MD5. It produces a digest of 20 bytes, reportedly runs at 40
Mb/s on a 90 MHz Pentium and has been placed in the public domain by its
designers. The RIPEMD-160 homepage is at http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html
Cryptographic systems need cryptographically strong random numbers that
cannot be guessed by an attacker. Random numbers are typically used to
generate session keys, and their quality is critical for the quality of the
resulting systems. The random number generator is easily overlooked, and
becomes the weakest point of the system.
Some machines may have special purpose hardware noise generators. Noise
from the leak current of a diode or transistor, least significant bits of
audio inputs, times between interrupts, etc. are all good sources of
randomness when processed with a suitable hash function. It is a good idea to
acquire true environmental noise whenever possible.
Disclaimer: Any opinions and evaluations presented here are speculative,
and the author cannot be held responsible for their correctness.
|
|
|
|