Followup-To: sci.crypt

Subject: Crypto Mini-FAQ

From: "Roger Schlafly"

Archive-name: crypto/faq

Last-modified: 2006/12/27

Posting-Frequency: Weekly

Copyright: Roger Schlafly

Several useful but out-of-date crypto FAQs are here: http://www.faqs.org/faqs/by-newsgroup/sci/sci.crypt.html

This crypto mini-faq is an attempt to have something that is more concise, up-to-date, and relevant to sci.crypt. It will be kept here: http://www.schlafly.net/crypto/faq.htm

For a pre-computer history of cryptology, see The Code Breakers, by David Kahn.

For an elementary exposition, see Cryptography Decrypted, by H. X. Mel and Doris M. Baker or The Code Book by Simon Singh.

For a general introduction to a lot of algorithms, with source code, see Applied Cryptography by Bruce Schneier. This book is partially superseded by Practical Cryptography, by Niels Ferguson and Bruce Schneier.

For a more mathematical reference work, and the best freely downloadable crypto book, see Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, and Scott Vanstone. http://www.cacr.math.uwaterloo.ca/hac/

For a good textbook, see Cryptography Theory and Practice, by Douglas Stinson. See also Modern Cryptography: Theory and Practice, by Wenbo Mao.

For a college course, see these U. of Washington class lectures. http://www.cs.washington.edu/education/courses/csep590/06wi/lectures/

For a textbook with emphasis on mathematical background, see A Course in Number Theory and Cryptography, (Graduate Texts in Math. No. 114, Springer-Verlag, New York, 1987, Second edition, 1994), by Neil Koblitz.

For a broader view of system security, see Security Engineering: A Guide to Building Dependable Distributed Systems, by Ross Anderson. It is now a free download. http://www.cl.cam.ac.uk/~rja14/book.html

For producing secure software, see Writing Secure Code, by Michael Howard and David C. LeBlanc. Bill Gates recommends the book. For better coverage of unix issues, see Building Secure Software, by Viega and McGraw.

For books on theoretical cryptography, see Introduction to Modern Cryptography, by Mihir Bellare and Phillip Rogaway, or The Foundations of Cryptography (2 volumes) by Oded Goldreich. Most of the content is freely available online. http://www.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

For a popular account of crypto politics, see Crypto, by Steven Levy.

For a web site that explains a lot of cryptography, see: http://home.ecn.ab.ca/~jsavard/crypto/intro.htm

For reviews of crypto books, see: http://www.youdzone.com/cryptobooks.html

For secure hashing, use SHA-1 or SHA-256. (MD5 has been broken.) For a block cipher, use AES-128 or Triple-DES (with AES preferred), in either CBC or CTR mode. For private-key authentication, use HMAC-SHA1. For public-key encryption and signatures, use DH/DSA or RSA.

Q. Has SHA-1 been broken?

There is a new Chinese paper that has announced an attack on SHA-1 that is more efficient than brute force. It is too early to say what the practical significance of the attack will be. NIST has recommended switching to SHA-256 by the year 2010 or so. Most uses of SHA-1 will probably be safe for a long time.

RC4 (aka ARC4) is a very popular stream cipher for those reasons. It is commonly used in SSL for secure web connections, and is reasonably secure if used correctly. You need to avoid reusing a key, waste the first few output bytes, and realize that there is no authentication. Some RC4-based systems have been broken, as constructing a secure system is a lot more complicated than choosing a cipher. You can find free RC4 software in a variety of languages here: http://www.xs4all.nl/~cg/ciphersaber/

Even if you use a relatively big and slow algorithm, it is unlikely to have a significant impact on your system. Processor speed and memory have gotten so cheap that just about any cipher is small and fast enough for just about any purpose. A bigger problem is that your system will probably have subtle flaws in it unless you consult with experts.

A common mistake is to just plug the time of day into a simple PRNG. Those random number generators are fine for doing numerical simulations, but not for cryptography. You need to use a hardware RNG, or use unpredictable data like mouse movements, or use suitable system calls such as to a /dev/random driver, or something similar. For more discussion, see: http://www.cs.berkeley.edu/~daw/rnd/

No. There are no weak keys that need to be avoided in DES, Triple-DES, or AES. It is sometimes worthwhile to check that a user-chosen password is not too easily guessable. If you don't trust your random number generator, it might be worth checking that it does not output all zeros or repeated values. But there is no statistical test that can determine that your RNG is satisfactory for cryptographic purposes.

You can just use the password directly, but it is usually better to run it thru a hash function or a key derivation function (KDF). A popular choice is PBKDF2 in PKCS#5. See: http://www.rsasecurity.com/rsalabs/pkcs/

Maybe. If you just post ciphertext and challenge anyone to break it, you will only get flamed. If your system is not well-explained, then no one will read it. If you just need some secure algorithm or protocol, then you are nearly always better off using some established method like SSL. If you think that you can advance the state of the art somehow, then give it a shot. A good cryptosystem should only depend on the secrecy of the keys, and not of the algorithms.

The sci.crypt sandbox is a place where new cipher designs can be posted: http://sandbox.emboss.co.nz/

A system is secure if it withstands a certain class of attacks, and
broken otherwise. The notion depends on assumptions about the abilities
of potential attackers, so those assumptions need to be carefully
defined for the concept to make any sense. For example, AES-128
might be considered secure if the attacker has less than a trillion
dollars, and broken if he has a computer that can search 2^{128} keys
in a reasonable amount of time.

Many systems are broken because attackers find ways around the unstated premises of the designers. It is a common fallacy to think that a system is secure just because a large keysize is used.

There are a number of good freeware libraries for software developers, such as Crypto++ and OpenSSL. Here are a couple of lists: http://www.homeport.org/~adam/crypto/index.html http://www.thefreecountry.com/sourcecode/encryption.shtml

Commercial products with US govt certification are listed here: http://csrc.nist.gov/cryptval/140-1/1401val.htm

A good PGP clone for end-user message encryption is GnuPG: http://www.gnupg.org/

For Windows systems, you can also use PGPi: http://www.pgpi.org/

GnuPG (and PGP) can encrypt files for yourself, encrypt files for others, and digitally sign documents with a public key.

When you encrypt a disk file, the plaintext may still remain even if you delete it or overwrite the file. To remove it from the disk itself, you need a secure file deletion utility.

TrueCrypt allows one to create a virtual encrypted disk. http://www.truecrypt.org/

US govt standards for DES, SHA, DSA, AES, and others are here: http://csrc.nist.gov/

IEEE-1363 and forthcoming amendments cover various public key algorithms, and have a lot of practical implementation information. http://grouper.ieee.org/groups/1363/

For network security protocols, see SSH, IPSEC, SSL (TLS), and S/MIME. These are widely available, and it is nearly always better to use one of these, than to reinvent the wheel. Some others are mentioned here: http://www.nue.et-inf.uni-siegen.de/~schmidt/tcsecurity/protocols.html

Some other important standards (such as X.9F and ISO/IEC) are briefly summarized here: http://www.cacr.math.uwaterloo.ca/hac/about/chap15.pdf http://crypto.cs.mcgill.ca/~stiglic/cryptoresources.html

No. Some US govt crypto policies have been controversial, but there is no evidence of secret backdoors or anything like that.

Typically you use a recipient public key to establish a cipher key, and then use the cipher key to encrypt the bulk of the message. The integrity of the message is assured by including a MAC of the message. The authenticity of the sender is assured by a digital signature and some certificates. You could look at something like SSL or S/MIME for an example, although these are not really good starting points for designing a new system.

If you do it right, your system will be able to withstand a chosen ciphertext attack. That means that if the sender encrypts either "buy" or "sell", then an attacker who intercepts the message cannot tell which it is, even if he tricks the receiver into decrypting various other related messages.

You can encrypt the plaintext and then authenticate the ciphertext with a MAC, or you can authenticate the plaintext and encrypt the combination, or you can encrypt and authenticate separately, or you can use a fancy new encryption mode that does both at the same time. Any of these can be secure if done properly. The safest bet is probably to encrypt and then authenticate, for reasons discussed here: http://www.cs.berkeley.edu/~daw/my-posts/use-etm http://citeseer.nj.nec.com/krawczyk01order.html

You can run into trouble if you use the same key for both encryption and authentication. If you have one key K and you want to do both, an effective method is to use SHA1(K,"encrypt") as the encryption key and SHA1(K,"MAC") as the MAC key. If you are extra paranoid, you can replace SHA1 with HMAC-SHA1.

A panel of experts recommended 90-bit cipher keys in 1996 as being sufficient for the next 20 years. ftp://ftp.research.att.com/dist/mab/keylength.txt

AES keys can be 128, 192, or 256 bits. AES-128 should be secure for the foreseeable future. Triple-DES uses 168 bit keys, but is perhaps less secure than AES-128.

For official recommendations on keysizes, see: http://csrc.nist.gov/CryptoToolkit/kms/guideline-1-Jan03.pdf

Some countries may have laws restricting keysizes.

The one-time pad (where the plaintext is XORed into random key stream) is provably secure in a certain academic sense. But it is not really very practical (because it needs long keys that can never be repeated) and not really very secure (because someone can intercept the message and alter it without the recipient noticing). Furthermore, the random key stream is usually simulated with a pseudo-random number generator, and all security properties are lost if that PRNG is weak.

Computational complexity theory is just not good enough to prove that DES or RSA encryption is secure. The academic literature has lots of theorems that prove that certain constructions have certain properties provided that factoring is hard, or under some similar assumption. Another class of arguments involves some idealized model like the random oracle model. These arguments are valuable for the insights that they offer to experts, but have virtually no significance to the casual crypto consumer.

Diffie-Hellman (DH) is actually older and simpler than RSA, and along with DSA it can be used for all the things that RSA is commonly used for. The differences are minor and technical. Elliptic curve cryptosystems (ECC) have the advantage of shorter public keys. The best attacks on ECC are exponential in the keysize, while the attacks on RSA and DH/DSA are sub-exponential, so ECC will become more attractive after a few more years of Moore's law. Other methods like NTRU have not yet gained credibility.

Not in our lifetimes. Quantum cryptography along a single fiber optic strand has been demonstrated, and claims to offer provable security in a certain narrow academic sense, like the one-time pad. But to be practical, it has to be combined with conventional cryptography, in which case the quantum operations do not add much.

Quantum computers threaten the future of RSA in about the same way that cold fusion threatens to solve the world's energy problems. It would require huge theoretical and practical breakthroughs. Even if that happens, people could just shift to AES-256 and other algorithms. In the meantime, Moore's Law is a bigger threat to RSA at the common keysizes.

Probably. Efforts to regulate strong crypto in the USA and other countries have subsided, and products ship all over the world with strong crypto now. For an international legal survey, see: http://rechten.kub.nl/koops/cryptolaw/

Some crypto products are protected by copyright, patent, trademark, and trade secret laws. But you can use SHA-1, AES, HMAC, RSA, DH, DSA, ECC, RC4, and all the essentials royalty-free. Some silly speed-up tricks are patented.

If the system is secure and does not have any key recovery feature, then there is nothing you can do besides trying to guess the password. If the system used the sort of crippled encryption that is common in many commercial products, then you might be able to use a decryption tool. This search finds many pages describing such tools: http://www.google.com/search?q=password+recovery

It is a variant of public-key cryptograpphy, in which a transformation from email addresses to key pairs is done by some central server. The catch is that the central server can reproduce anyone's private key. The advantage is that the user only has to get a private key when he needs to decrypt something. With conventional public-key crypto, the user has to get a key before anyone can send him messages.

Yes, using steganography.

Most product hacks are not particularly interesting to cryptologists, and are better described on hacker sites.

See: http://avirubin.com/courses.html http://www.cs.berkeley.edu/~dmolnar/gradschools.html

Besides the FAQs, sites, and books listed above, try this link collection: http://www.cs.ut.ee/~helger/crypto/

For the home pages of cryptographers, see: http://www.cryptolounge.org/wiki/Home_Pages_of_Cryptography_Related_People.

Disclaimer: This is just my opinion. Do not expect one book to make you an expert. Send comments and corrections to me at: rogerschlafly@mindspring.com