Encryption Algorithms - Basics

Encryption Algorithms
Version 1.0
1/28/2005


Here is some information that I put together during my studies for various certifications and general knowledge. Please feel free to use it for study purposes or make comments on it for improvements. If you post it on other message boards or redistribute it please keep my contact information intact.

-Kruptos
AKA. = Rob Kraus rkraus@unguarded.org

Although this tutorial is pretty comprehensive, I do not claim to be a Cryptology Guru. If you do find errors please let me know. I have broken this document down into different areas, Asymmetric Algorithms, Symmetric Algorithms, Hashes and other items that I could not fit into the other categories, but felt like mentioning.

What is Encryption anyway??

Encryption is a form of Cryptography. It has many roles and is the foundation of many security measures including but not limited to digital signatures, digital certificates, PKI and more. It scrambles plain text into unreadable ciphertext. During the encryption process a key is used to encrypt and decrypt the data, the strength of particular encryption is often determined my the length of the key, which is measured in bits. The more bits in the key, typically the harder it is to crack the key.


Symmetric Encryption Algorithms

Symmetric encryption is also called “secret key” or “single key” encryption, and uses just one key called a shared secret for both encrypting and decrypting. The problem with this is that the key must be shared between the sender and the recipient of the data, so a secure method of key exchange must be devised. Otherwise, if a third party intercepts the key during the exchange, they can easily decrypt the data. Symmetric keys have a computational efficiency advantage, (10-100 million bits/sec that rivals asymmetric keys).


Data Encryption Standard Algorithm
Developed by IBM and was the US government standard from 1976-2001. Adopted as a Federal Information Processing Standard (FIPS) in 1977. It is also the worlds most commonly used mechanism.

DES uses a single 64 bit circulating block cipher key. 56 bits of data and 8 bits of parity and operates on data in 64 bit chunks. The key is broken into 16 separate 48-bit subkeys, one for each round, which are called Feistel cycles.


Triple DES Algorithm
(3DES) is based on the DES algorithm. To improve security the encryption is performed 3 times using 3 different keys. The multiple encryptions result in a ciphertext that has an “effective” key size as large as the sum of the sizes of the three keys. (192 bits)

The keys can all be different numbers, all the same number or 2 can be the same. In common implementations the same key is used for the first and last stage of the processing which reduces the strength of the encryption. If all 3 64-bit keys have the same value, the algorithm is no stronger than DES. Uses 48 rounds in its computation.


Advanced Encryption Standard Algorithm
Developed by Dr. Joan Daemen and Dr. Vincent Rijmen. Instead of using Feistel cycles in each round like DES, it uses iterative rounds like IDEA (discussed in the next section). Data is operated on in 128-bit chunks which are grouped into four groups of 4 bytes each. This is a block cipher with variable lock and key length.
The number of rounds is also dependent on the size of the key, as seen below:
128-bit Key – 9 rounds
192-bit Key – 11 rounds
256-bit Key – 13 rounds


International Data Encryption Algorithm
Ascom Systems currently has the patent on this. The algorithm supports both Electronic Code Book (ECB) and Cipher Block Chaining (CBC) with eight initial vectors (CBC64).
A 128-bit key is used to enhance security. It is newer, faster and more secure than DES. It is faster due to the fact that each round consists of much simpler operations than the Feistel cycle in DES. Block cipher operates on 64 bit blocks of data. Used in PGP encryption software


SkipJack
SkipJack is intended only for use in electronic encryption devices (harware). SkipJack operates in a manner similar to DES, but uses an 80-bit key and 32 rounds, rather than 56-bit keys and 16 rounds (DES)

Blowfish
A block cipher that works on 64-bit blocks of data. The key length can be up to 448 bits and the data blocks go through 16 rounds of cryptographic functions.

RC5
A block cipher that has different parameters that you can choose from for the block size, key size and number of rounds to be used.
Block sizes: 32/64/128
Key size: up to 2048 bits.



HMAC
Hash Message Authentication Code (HMAC) secret key algorithm. Provides data integrity, and origin Authentication through a digital signature produced by a keyed hash function.


Asymmetric Encryption Algorithms

Asymmetric Encryption is also referred to as public key encryption, but actually relies on a key pair. It is comprised of two mathematically related keys, one is called the public key and the other is called the private key. They are also generated to be used together. The private key is never shared and is kept secret and only used by its owner. The public key is made available to whoever wants it. Asymmetric are usually much slower then symmetric, with a speed of a few thousand bits/sec.


Diffie-Hellman Algorithm
Created by Whitfield Diffie and Martin Hellman and published in 1976. The key exchange process is as follows:

The two parties agree on two numbers, one is a large prime number and the other is an integer smaller then the prime. This can be done in the open and does not affect security.

Each of the two parties separately generates another number which they keep secret. This number is the equivalent to a private key. A calculation is made involving the private key and the previous two public numbers. The result is sent to the other party and is effectively the public key.

The two parties exchange their public keys. They then privately perform a calculation involving their own private key and the other party’s public key. The resulting number is the session key. Each party will arrive at the same number.

The session key can be used as a secret key for another cipher, such as DES. No third party monitoring the exchange can arrive at the same session key without knowing one of the private keys.

This algorithm is still widely used, most notably in the IPSec protocol. IPSec uses the Diffie-Hellman algorithm in conjunction with RSA authentication to exchange a session key that is used for encrypting all traffic that crosses the IPSec tunnel.



RSA Algorithm
Created by Ron Rivist, Adi Shamir, and Leonard Adleman. RSA is significantly faster the Diffie-Hellman, which lead to a split in the asymmetric cryptography field that refers to Diffie-Hellman as similar algorithms as Public Key Distribution Systems (PKDS), and to RSA and similar algorithms as Public Key Encryption (PKE). PKDS systems are used as session key exchange mechanisms, while PKE systems are generally considered fast enough to encrypt reasonably small messages.

Programs you may encounter that use RSA are:
Pretty Good Privacy (PGP)
Secure Shell (SSH)


Digital Signature Algorithm
The algorithm uses private and public key pairs. Only the private key of the key pair is capable of creating a signature. The hash function used in the creation and verification process is defined in the Secure Hash Standard (SHS).

To create a signature, the message is processed by the SHS hashing algorithm, thereby creating a message digest. The private key and the digest are then used as inputs to the DSA, which generates the signature. For message and sender verification, the recipient uses the hash function to create a message digest, and then the sender’s public key is used to verify the signature. Allowed key sizes range from 512 to 1,024 bits. DSA is much slower than RSA for signature verification.


Hashing Algorithm Functions

Hashing is a technique in which an algorithm (also called a hash function) is applies to a portion of data to create a unique digital “fingerprint” that is a fixed size variable. If anyone changes the data by so much as one binary digit, the hash function will produce a different output (called a hash value) and the recipient will know that the data has been changed. The hash function cannot be reverse engineered, that is , you cannot use the hash value to discover the original data that was hashed. Thus, hashing algorithms are referred to as one-way hashes. A good hash function will not return the same result form two different inputs (collision), each result should be unique.

There are several different types of hashing, including division-remainder, digit rearrangement, folding, and radix transformation. These classifications refer to the mathematical process used to obtain the hash value.

Standard hashing algorithms include:
MD2
MD4
MD5
Secure Hash Algorithm (SHA)
Secure Hash Algorithm-1 (SHA-1)

Message Digest 2
Produces 128-bit values and is slower then MD4/MD5.


Message Digest 4
MD4 is a one-way hash function. A message digest is a small digital signature, generally intended for use with e-mail or other electronic communication. The MD4 hash function produces a hash 128 bits in size from a plain text message of any size.

MD4 was created by Ronald Rivest in 1990. MD4 has several vulnerabilities and has been since been replaced with MD5.

A message hashed with MD4 has bits added so that the total message length(in bits) plus an additional 64 bits is divisible by 512. MD4 then appends a 64-bit “snapshot” of the message length. Next, the message is encrypted in 512-bit blocks. Each block is manipulated three times in production of the final hash. Produces 128-bit hash values and is used for high speed computation in software implementation and is optimized for microprocessors.

Message Digest 5
MD5 was created by Rivest in 1991. MD5’s process is very similar to MD4, except that it finishes the process with four rounds rather then three. It is slower than MD4 but more secure. Produces 128-bit hash values and is more complex then MD4, processes text in 512-bit blocks.

SHA
Produces 160-bit hash values. This is then inputted into the DSA, which computes the signature for a message. The message digest is signed instead of the whole message.


SHA-1
SHA-1 is the replacement for SHA as described by SHS. SHA-s is similar to MDx functions, although it is slightly slower. The performance is slower due to the fact that SHA-1 uses a 160-bit message digest rather than a 128-bit one. The more bits in the digest makes the algorithm stronger and less likely to encounter collisions.


HAVAL
HAVAL is a one way variable length hash function and is the modification of MD5. It processes text in blocks of 1024 bits. Experiments have shown that HAVAL is faster then MD5.


Other good information – More development will be placed here in the future.

Kerberos

Kerberos is a method for authenticating a request for a service in a computer network. Developed in the Athena Project at the Massachusetts Institute of Technology (MIT).

The name is taken from Greek mythology; Kerberos was a 3-headed dog that guarded the gates of Hades.

Kerberos lets the user request an encrypted “ticket” from an Authentication process that can be used to access particular services on the network. More information can be found by referring to RFC 1510.

Internet Security Association and Key Management Protocol (ISAKMP)

ISAKMP is an Internet IPSEC Protocol. It negotiates, establishes, modifies, and deletes security associations. It also exchanges key generation and authentication of data. It is independent of the details of any specific key generation technique, key establishment protocol, encryption algorithm, or authentication mechanism.


Algorithm Subclasses

Block Cipher
Encrypt data in discrete chunks of a fixed size. Block ciphers are symmetric, which mean that they use the same key for encryption and decryption. The most common blocks will have a size of 64 bits, but may support blocks of any size. 128-bit block cipher is now surfacing more in the networking world.


Stream Cipher
Stream ciphers are symmetric that operate on plaintext bit-by-bit. The processing of plaintext uses an XOR operation. Stream cipher algorithms create a key stream that is combined with the plaintext to create a ciphertext.





XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

As mentioned above, much of this material I came across in my studies for Security+ and SSCP certifications. I do not claim to be a guru on this and this was intended to be study material and information to share amoung the security community. If you do find errors and please let me know and I will update. Please pay close attention to the version number at the beginning of this document.

Also, I would like to list some of the sources of my information as not to take credit from some of the original creators of some of the information contained in the document.

Syngress Books, Security+ Study Guide and DVD Training System, ISBN 1-931836-72-8, 2002

Syngress Books, SSCP Study Guide and DVD Training System, ISBN

SSCP Notes – 1.0, Vijayanand Banahatti, April 2004, Originally sourced from www.cccure.org

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX