Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!newsfeed.stanford.edu!postnews.google.com!news4.google.com!out03b.usenetserver.com!news.usenetserver.com!in02.usenetserver.com!news.usenetserver.com!uns-out.usenetserver.com!news.usenetserver.com!pc03.usenetserver.com!STARBAND.NET-a23zrI7RMR4vk!not-for-mail
Newsgroups: sci.crypt,talk.politics.crypto
Followup-To: sci.crypt
Subject: Crypto Mini-FAQ
From: "Roger Schlafly"
Message-ID:
X-Complaints-To: abuse@usenetserver.com
Organization: UseNetServer.com
Date: Thu, 13 Dec 2007 06:02:22 +0000
Lines: 1
X-Trace: be1e84760caee319ae1a424094
Xref: senator-bedfellow.mit.edu sci.crypt:953905 talk.politics.crypto:49706
Archive-name: crypto/faq
Last-modified: 2007/11/27
Posting-Frequency: Weekly
Copyright: Roger Schlafly
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. See also Modern Cryptography: Theory and
Practice, by Wenbo Mao.
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
http://www.cl.cam.ac.uk/users/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://www.quadibloc.com/crypto/intro.htm
For reviews of crypto books, see:
http://www.youdzone.com/cryptobooks.html
For a college class in cryptography, see:
http://www.cs.washington.edu/education/courses/csep590/06wi/
Q: What popular methods can be recommended?
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.
Many secure systems today use SHA-1 for hashing, triple-DES (in
CBC mode) for a block cipher, DH/DSA or RSA for public-key
encryption and signatures, and HMAC-SHA1 for private-key authentication.
Systems that require very high security in the future are migrating
to NSA Suite B. For information classified SECRET, it uses SHA-256
for hashing, AES-128 for a block cipher, ECDH public-key encryption,
and ECDSA for signatures.
http://www.nsa.gov/ia/industry/Crypto_suite_b.cfm
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://ciphersaber.gurus.com/
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 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/
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.
You can also use AES in GCM mode.
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://www.keylength.com/en/4/
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.uvt.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, SHA-256, AES, HMAC, RSA,
DH, DSA, ECC, RC4, and all the essentials royalty-free. Some silly
speed-up tricks are patented.
Certicom has some patents on ECC, but has only successfully enforced
them on EC-MQV, which is an optional alternative to ECDH in NSA Suite B.
However MQV has some subtle security weaknesses, and hardly anyone
uses it.
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
http://www.cs.berkeley.edu/~dmolnar/gradschools.html
Q: Where can I get more information?
Besides the FAQs, sites, and books listed above, try this link
collection:
http://www.adastral.ucl.ac.uk/~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:
faq@darkbuzz.com