[Courses] [security] A Field Guide to Algoriths (was: Crypto Scientists Crack Prime Problem)

[Raven Alder]

Heya --

Quoth Kai MacTane (Tue, Aug 13, 2002 at 02:44:42PM -0700):
> >This is why it's hard to trust closed source and proprietary crypto
> >algorithms.  You're at the mercy of the vendor; you have no way of
> >seeing for yourself whether it sucks or not.  In my opinion, the best
> >crypto setups are the ones where everyone knows the algorithm and
> >implementation details, and still can't break it.  If it's stood the
> >test of time for mathematicians and computer scientists worldwide for
> >years, odds are good that it's a stable crypto setup.
> 
> So, what are some crypto systems/standards/algorithms that fit this 
> criterion? I believe RSA is one -- the algorithm has been widely available 
> for educational purposes for something close to 20 years, and AFAIK, it's 
> been subjected to a *lot* of analysis, and still proves computationally 
> unfeasible to crack. Are there any others?

	Ah, you have paid the price of asking a good question -- you
wait a week for the answer.  "Wow, that's probably something a lot of
people are curious about.  I should write something kinda thorough.
Tomorrow."  [lather rinse repeat]

	Here's my quick tour of current crypto algorithms; I expect that
others will have more to add to the discussion.  

	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.

EFF's cracking of DES:	https://www.cosic.esat.kuleuven.ac.be/des/

	There is a book out, referenced in the above article, 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:    http://csrc.nist.gov/encryption/aes/
        http://www.ii.uib.no/~larsr/aes.html

	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. 

        Rijndael:       

http://www.esat.kuleuven.ac.be/~rijmen/rijndael/index.html

	Other neato algorithms that were contenders:

        Serpent:        http://www.cl.cam.ac.uk/~rja14/serpent.html

Slower, but performance was less of a concern to the inventors than
making it as ironclad as they could. 

        Twofish:        http://www.counterpane.com/twofish.html

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:		http://www.research.ibm.com/security/mars.html

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:

http://www.rsasecurity.com/rsalabs/rc6/index.html

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:	http://home.ecn.ab.ca/~jsavard/crypto/co0404.htm

	A patented algorithm also sometimes used in ssh (if I recall
correctly it's in Ylonen's ssh (ssh.com) 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:	http://www.x5.net/faqs/crypto/q29.html

	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 cryptosustem cracking),
and there's a project being worked on through distributed.net -- like
SETI at 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. 

	On to digital certificates and public key infrastructure...
soonish.  [grins, waves hands]  Discuss, discuss.

Cheers,
Raven 

"I'm not really a 'sports' kind of person.  More of a 'fight' 
 kind of person."
  -- Rogue, on baseball

"You're not getting paid for security here."