This is a LinuxChix course page. This and the other courses pages are yet to be ported to the new LinuxChix website. Please feel free to browse the course in the meantime.

We appreciate your patience.

LinuxChix(tm)

A Field Guide to Algorithms

In the 1970's, an algorithm was developed called the Data Encryption Standard, or DES. It was a block cipher (meaning that it encrypted blocks of the plaintext message at a time) with a block size of 64 bits. It uses a 56 bit key to do the encrypting. At the time, this was sufficient. However, it's now perfectly computationally possible to crack a DES key. In a 1998 challenge, the Electronic Frontier Foundation built a machine that cracked DES in three days.

There is a book out that specifies exactly how that worked. However, it's illegal in the US to export those details in electronic form. (Grrrr.)

So DES isn't something that you really want to trust for uber-secure data any more (or perhaps even marginally secure data -- depends on your paranoia level). Generally, you need your data to be safer for longer than it would take to force the DES key. So unless you're encrypting something that only needs to remain unknown for a few days, you want to pick something cryptographically stronger.

DES, however, spawned. A newer implementation of DES-like principles, 3DES, is still generally considered to be secure. In 3DES, the DES algorithm is used three times with three different keys on the plaintext. This is substantially more secure, but also kinda slow as block ciphers go since you have

Plaintext ----> Text-1 ----> Text-2 ----> Ciphertext
for every block. Three separate transformations on the block before it's encrypted -- you take a performance hit.

The U.S.'s National Institute for Science and Technology (NIST) started a challenge to look for the next-generation cryptographic standard to replace DES, called Advanced Encryption Standard (AES). They narrowed the field from fifteen candidates to five, all block ciphers with block sizes of 128 bits and keys of either 128, 192, or 256 bits. The algorithms that were chosen are a good indication of what you're going to see in crypto over the next several years.

AES

Ultimately, NIST chose the Rijndael algorithm (mentioned earlier in this discussion) as the winner. Cited reasons were performance on a wide variety of platforms without compromising security.

Other neato algorithms that were contenders:

Serpent
Slower, but performance was less of a concern to the inventors than making it as ironclad as they could.
Twofish
Based on the Blowfish algorithm (which is used in some ssh implementations) -- fast and good on a variety of platforms. And open source, yay.
Mars
IBM's submission for AES -- very efficient on 32-bit processors, but less so on things like smart cards which may not have the same instruction set available to them.
RC6
RSA Labs's submission for the same. One of the newer algorithms out there, so there were questions about how well it's been vetted by the security/crypto community.

All of the above are what's known as symmetric or shared-key algorithms. The same plaintext and the same key will get you the same ciphertext every time. In order to prevent this predictability, some crypto implementations will XOR (perform a bitwise exclusive or operation) each block of plaintext with the previous one, and then encrypt and send that. Since the previous block is unlikely to be the same in most messages, you're likely to get different plaintexts that will then produce different ciphertexts, even when still using the same key.

Other things you'll see out there:

IDEA
A patented algorithm also sometimes used in ssh (if I recall correctly it's in Ylonen's ssh but not in OpenSSH because of the patent issues). Very secure, no known attacks that can break it. (The best out there today can get through 4.5 of its 8.5 cycles, so that's nowhere close.)
ElGamal & DSS
Public-key like RSA is (rather than symmetric), but based on discrete logarithms rather than prime factorization. There are attacks on this sort of mathematics (google for Pollard's Rho if you want to see all the math for discrete log/elliptical curve cryptosystem cracking), and there's a project being worked on through distributed.net -- like SETI@home for crypto geeks. [grin] Still, it's been around for a while and is decently secure, if you don't use teeny keys.

Also, you may encounter hashing algorithms. There are two fairly common ones that are often considered good -- MD5 and SHA1.

Copyright (c) 2002 by Raven Alder. This material may be distributed only subject to the terms and conditions set forth in the Open Publication License, v1.0 or later (the latest version is presently available at http://www.opencontent.org/openpub/).

© LinuxChix 2000-2006 unless otherwise specified Hosting provided by Intel and OSU Open Source Lab.