Crypto Mini-FAQ

From: Roger Schlafly (rogerschlafly_at_mindspring.com)
Date: 11/28/04


Date: Sun, 28 Nov 2004 15:22:40 GMT


                        Crypto Mini-FAQ

Q: Where is the FAQ for cryptology?

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

Q: What is the best book on crypto?

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.

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.

For producing secure software,see Writing Secure Code, by Michael
Howard and David C. LeBlanc. Bill Gates recommends the book.

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

Q: What popular methods can be recommended?

For secure hashing, use SHA-1. (MD5 has been broken.) For a block
cipher, use AES 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: I want something simple, free, fast, and painless. What do I use?

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.

Q: How can I generate random numbers?

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/

Q: Should I test for weak keys?

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.

Q: How do I convert a password into a key?

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/

Q: Can I get my system evaluated by posting it?

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/

Q: What does it mean for a system to be secure, or to be broken?

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.

Q: Where can I get free software?

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

Q: How can I encrypt a file on my hard drive?

A good PGP clone on unix 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.

Q: What crypto standards are there?

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

Q: Has the govt put secret backdoors in any of these algorithms?

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

Q: How do I put these algorithms together in a system?

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.

Q: How do I combine encryption and authentication?

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.

Q: How large should my keys be?

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.pdf

Some countries may have laws restricting keysizes.

Q: What methods are provably secure?

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.

Q: Are the newer public key methods better than RSA?

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.

Q: Will quantum computers make all this crypto obsolete?

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.

Q: Is it legal for me to use strong crypto in my product?

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/

Q: Do I have to pay license fees to use an algorithm?

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.

Q: I've lost my password. How do I decrypt my file?

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

Q: What is identity-based encryption?

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.

Q: Can I hide my message in a picture?

Yes, using steganography.

Q: How can I hack [this product] to break the protection?

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

Q: Where can I goto crypto grad school?

See:
http://avirubin.com/courses.html

Q: Where can I get more information?

Besides the FAQs, sites, and books listed above, try this link
collection:
http://www.tcs.hut.fi/~helger/crypto/

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



Relevant Pages

  • Re: AdaCrypt Test Runs
    ... In all likelihood, AdaCrypt ... interested in crypto but know very well that it's rather pointless to ... and use a block cipher in CBC mode. ... program to encrypt that plaintext three times and each time it came ...
    (sci.crypt)
  • Crypto Mini-FAQ
    ... This crypto mini-faq is an attempt to have something that is more ... For producing secure software,see Writing Secure Code, by Michael ... RC4 is a very popular stream cipher for those reasons. ... How can I encrypt a file on my hard drive? ...
    (sci.crypt)
  • Crypto Mini-FAQ
    ... This crypto mini-faq is an attempt to have something that is more ... For producing secure software,see Writing Secure Code, by Michael ... RC4 is a very popular stream cipher for those reasons. ... How can I encrypt a file on my hard drive? ...
    (sci.crypt)
  • Crypto Mini-FAQ
    ... This crypto mini-faq is an attempt to have something that is more ... For producing secure software,see Writing Secure Code, by Michael ... RC4 is a very popular stream cipher for those reasons. ... How can I encrypt a file on my hard drive? ...
    (sci.crypt)
  • Crypto Mini-FAQ
    ... This crypto mini-faq is an attempt to have something that is more ... For producing secure software,see Writing Secure Code, by Michael ... RC4 is a very popular stream cipher for those reasons. ... How can I encrypt a file on my hard drive? ...
    (sci.crypt)