Symmetric-key algorithm

From Wikipedia, the free encyclopedia

Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related cryptographic keys for both decryption and encryption.

The encryption key is trivially related to the decryption key, in that they may be identical or there is a simple transform to go between the two keys. The keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link.

Other terms for symmetric-key encryption are single-key, one-key and private-key encryption. Use of the latter term can sometimes conflict with the term private key in public key cryptography.

Contents

[edit] Types of symmetric-key algorithms

Symmetric-key algorithms can be divided into stream ciphers and block ciphers. Stream ciphers encrypt the bits of the message one at a time, and block ciphers take a number of bits and encrypt them as a single unit. Blocks of 64 bits have been commonly used; the Advanced Encryption Standard algorithm approved by NIST in December 2001 uses 128-bit blocks.

Symmetric-key algorithms are not always used alone. In modern cryptosystem designs, both asymmetric (public key) and symmetric algorithms are used to take advantage of the virtues of both. Such systems include SSL, PGP and GPG, etc. Asymmetric key algorithms make key distribution for faster symmetric key algorithms.

Some examples of popular and well-respected symmetric algorithms include Twofish, Serpent, AES (aka Rijndael), Blowfish, CAST5, RC4, TDES, and IDEA.

[edit] Speed

Symmetric-key algorithms are generally much less computationally intensive than asymmetric key algorithms. In practice, this means that a quality asymmetric key algorithm is hundreds or thousands of times slower than a quality symmetric key algorithm.

[edit] Limitations

The disadvantage of symmetric-key algorithms is the requirement of a shared secret key, with one copy at each end. Since keys are subject to potential discovery by a cryptographic adversary, they need to be changed often and kept secure during distribution and in service. The consequent requirement to choose, distribute and store keys without error and without loss, known as key management, is difficult to reliably achieve.

In order to ensure secure communications between everyone in a population of n people a total of n(n − 1)/2 keys are needed.[1] Very often these days, the much slower asymmetric algorithms are used to distribute symmetric-keys at the start of a session, then the higher speed symmetric-key algorithms take over (see Transport Layer Security). The same problems of reliable key distribution still exists at the asymmetric level, but they are somewhat more tractable. However, the symmetric key is nearly always generated in real-time.

The symmetric-key algorithms can't be used for authentication or non-repudiation purposes.

[edit] Reversibility

Encryption functions must, by definition, be reversible since you need to be able to both encrypt and (provided you have the right key) decrypt messages.

Various methods have been used historically to manage this. There have been book ciphers, in which the shared key is related to some content in a book, auto-key ciphers in which the key is partially derived from the plaintext, grill ciphers (supposedly first invented by the Italian mathematician Gerolamo Cardano), etc. In modern times, after computers became available, most symmetric ciphers have been based on repeated 'rounds'. Usually a rather simple scheme for each round is used repeatedly as in the following generic example. This general method is usually ascribed to Horst Feistel. For a more indepth description of this method (with diagrams) see Feistel cipher.

The bits to be encoded are split into two parts P1 and P2. P1 is unchanged, P2 is added (or exclusive-or'd) to a one-way hashed function f (varied by a key or 'salt') of P1. The two results are then swapped over. This is called 'a round'.

i.e. where p1, p2, key are bit vectors; ',' is a concatenation operator and f is a function p1, p2 \mapsto p2^{\prime}, p1 such that:

p2^{\prime} = p2 + \mathrm{f}(p1, key)

Since the output of the round still has access to the value P1, and the addition is a reversible operation, then this operation may be undone, for any one-way function f.

Whilst a single round is insecure, p1 having been unchanged, repeating the operation more than once, often with different functions and 'round keys', greatly improves the strength.

To decrypt multiple rounds, each round is undone in reverse order hence, for decryption, the keys are applied in reverse order.

After several rounds (typically between 8 and 64) of processing, the output becomes so scrambled that, in the case of well designed ciphers, nothing faster than brute force key search is feasible. With a long enough key, a brute force attack can be made infeasible.

[edit] Attacks on symmetric ciphers

Symmetric ciphers have historically been susceptible to known-plaintext attacks, chosen plaintext attacks, differential cryptanalysis and linear cryptanalysis. Careful construction of the functions for each round can greatly reduce the chances of a successful attack.

When used with asymmetric ciphers for key transfer, pseudorandom key generators are nearly always used to generate the symmetric cipher session keys. However, lack of randomness in those generators or in their initialization vectors is disastrous and has led to cryptanalytic breaks in the past. Very careful implementation and deployment, with initialization based on high quality sources of entropy, is essential lest security be lost.

[edit] Notes

  1. ^ Beutelspacher, Albrecht (1994). “The Future Has Already Started or Public Key Cryptography”, Cryptology, translation from German by J. Chris Fisher, 102. ISBN 0-88385-504-6.


Stream ciphers
v  d  e
Algorithms: A5/1 | A5/2 | FISH | Grain | HC-256 | ISAAC | MUGI | Panama | Phelix | Pike | Py | Rabbit | RC4 | Salsa20 | Scream | SEAL | SOBER | SOBER-128 | SOSEMANUK | Trivium | VEST | WAKE
Theory: Shift register | LFSR | NLFSR | Shrinking generator   Standardization: eSTREAM
Block ciphers
v  d  e
Algorithms: 3-Way | AES | Akelarre | Anubis | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 | Cobra | CMEA | Crab | CS-Cipher | DEAL | DES | DES-X | DFC | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | ICE | IDEA | IDEA NXT | Iraqi | KASUMI | KHAZAD | Khufu and Khafre | Libelle | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | XTEA
Design: Feistel network | Key schedule | Product cipher | S-box | SPN   Attacks: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL
Standardization: AES process | CRYPTREC | NESSIE   Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key
Cryptography
v  d  e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers