Book Review - Applied Cryptography

Categories: Security

Introduction

This article contains some notes I made while reading the book Applied Cryptography, 20th Anniversary Edition by Bruce Schneier and which did not fit into the security book review article.

These are really just notes-to-myself; no promises that they are also useful to anyone else.

  • Title: Applied Cryptography, 20th Anniversary Edition
  • Author: Schneier, Bruce
  • Publisher: Wiley
  • Published: 1995 (2nd Edition), 2015 (Anniversary Edition)

Summary

This “Anniversary Edition” is a re-print of the second edition of this book from 1995, with a new introduction and a new foreword from the author but otherwise unchanged.

Despite the age of the content, the book does an excellent job of covering all the significant concepts in encryption, digital signatures, authentication, hashing, and other related topics. It thoroughly deserves the label “a classic” - and for its content as well as the political impact it made at its first publication. This book played an important part in moving cryptography from a secret-services topic to an academic one, for which I think we all should be grateful.

The author’s own foreword recommends “Cryptography Engineering, Schneier/Ferguson/Kohno, 2010” as a more up-to-date source of information; this book is sadly not currently available on safaribooksonline. However the original still holds up well. The only single topic I could see that was missing is blockchain; otherwise symmetric and asymmetric encryption, public key cryptography, PGP, etc are all covered.

The writing style is wonderfully readable, with complex concepts explained in plain language (as far as possible). Some of the content (particularly in chapters 10-20) is too detailed for the needs of most readers, but it is still worthwhile to skim the text and pick out the higher-level concepts.

I think every reader of this book will end up improving their knowledge of cryptology, whether almost-beginner or expert.

The book references this article on Why Cryptosystems Fail which is an excellent summary of the real-world causes of it security problems. Sadly, the partially optimistic ending to the article (things must get better) has not come true - the article is from around 1993, but in my experience the same problems are still occurring in the current decade. It appears that applying good security practices are just not part of human nature or commercial interests.

Chapter By Chapter

  • Chapters 1-9 are excellent overviews of various principles and possibilities.
  • Chapter 10 is somewhat weak and shows its age.
  • Chapter 11 (mathematical background) is still somewhat readable, but not necessary for users of encryption.
  • Chaptes 12-14 (on block ciphers) are beautifully written, and worth at least skimming; there is a mix of very detailed and more general info.
  • Chapter 15 can be useful (combining ciphers)
  • Chapter 16-17 (on stream ciphers) is also interesting
  • Chapter 18 on hah functions is very useful.
  • Chapter 19 (on public key systems) explains why different keys are needed for encryption and signatures.
  • Part4 (the real world, particularly ch 24/25) are very useful.

The coverage of IVs and ECB/CBC/CFB/OFB modes with respect to error extension (or not) is very important when choosing an encryption mode.

The list of possible protocols in Chapter 3 is fascinating - I was not aware how many tricky things can be supported (see threshold schemes and secret-sharing schemes with prevention for example). The description of subliminal messages in digital signatures is also cool.

Designated confirmer signatures are also cool: you get a document, and a block of data that claims to be a signature from me over the document with confirmer being notary.acme.com. You cannot verify this signature with just my public key - you must ask acme.com if the signature is valid. The answer you get from acme is trustworthy - they cannot fake a “yes, valid” or “no, invalid” (although they can of course refuse to answer at all). In addition, if you forward that answer to anyone, you cannot prove that the forwarded info really came from acme, ie the person you are forwarding the answer to cannot be sure that you are not lying about having verified the signature; that third party must ask acme.com independently to verify the signature if they really need to be sure.

Best Bits

Interesting facts:

  • Never use your private key to decrypt a value sent by an untrusted party and send them the decrypted value. An attacker can choose a value which, when decrypted, will reveal your private key. One particular example is: if somebody sends you a document to sign, never decrypt the document, sign it, and return (decrypted doc, signature). The decrypted-doc value reveals your key if the input doc is carefully chosen. Of course such a carefully-chosen input doc would look like garbage, but an automated signing system might not notice that. Computing a hash over the input document, signing and returning that does not cause problems - only returning data “decrypted” with your private key. This is in fact not normally a problem, as big blocks of data are not normally encrypted with a public key; instead the main data is encrypted with a symmetric key and then the symmetric key is encrypted with the public key. In this case, returning the document content is no problem - just returning the decrypted symmetric key (which is not something that you would normally do).
  • Apparently, it is also dangerous to encrypt attacker-provided values at all with your private key. However when signing a document, you only encrypt the hash with your key. The attacker cannot easily choose a document that hashes to a particular value - and the values that are dangerous are usually longer than a standard hash value, so encrypting and exporting the hash of an attacker-provided doc is acceptable.

Interesting details about public key cryptography:

  • Some public-key algorithms can be used only for encryption (aka PKE), some only for signatures, and some for both (RSA and ElGamel work for both)
  • DSA (digital signature algorithm) is a US-based standard that works only for signatures; it is somewhat related to elGamel.
  • ElGamel is secure, but ciphertext output is about twice the size of the plaintext input; RSA does not have that problem.
  • As RSA patents have expired, RSA is currently recommended for both encryption and for signatures.
  • OpenPGP supports all three options (plus some others)
  • Elliptical curve-based variants of RSA are becoming more popular.

If Alice is sending messages to Bob, encrypted with Bob’s public key, and the number of possible messages is small (eg just a timestamp or some enumerated-value) then eve can simply encrypt the same values with Bob’s key and compare; this is equivalent to block-cipher encryption without an IV or hashing passwords without salt. And the solution is to do something equivalent to an IV or salt: Alice should append a random header or footer to each message (which will be ignored) before encrypting so that the same message encrypts to a different value each time. Given modern systems, and decent funding, eve can precompute large numbers of possible values; in particular if Alice sends Bob an encrypted symmetrical encryption key (hybrid encryption) then either the key should be long (much larger than 56 bits) or random (discarded) padding should be added to the encrypted data (effectively salting the value).

Interesting details about encryption modes (from Chapter 9):

  • If simplicity and speed are your main concerns, ECB is the easiest and fastest mode to use a block cipher. It is also the weakest. Besides being vulnerable to replay attacks, an algorithm in ECB mode is the easiest to cryptanalyze. I don’t recommend ECB for message encryption.
  • For encrypting random data, such as other keys, ECB is a good mode to use. Since the data is short and random, none of the shortcomings of ECB matter for this application.
  • For normal plaintext, use CBC, CFB, or OFB. Which mode you choose depends on your specific requirements. Table 9.1 gives a summary of the security and efficiency of the various modes.
  • CBC is generally best for encrypting files. The increase in security is significant; and while there are sometimes bit errors in stored data, there are almost never synchronization errors. If your application is software-based, CBC is almost always the best choice.

Quotes

The book contains some classic quotes:

This one is spookily prescient:

Key escrow has considerable disadvantages. The user has to trust the escrow agents’ security procedures, as well as the integrity of the people involved. He has to trust the escrow agents not to change their policies, the government not to change its laws, and those with lawful authority to get his keys to do so lawfully and responsibly. Imagine a major terrorist attack in New York; what sorts of limits on the police would be thrown aside in the aftermath?

This one was sadly just too optimistic:

Computerized voting will never be used for general elections unless there is a protocol that both maintains individual privacy and prevents cheating.

Very good advice:

If companies do not feel that their interests are served by making their algorithms public, it is best to assume they’re right and avoid the algorithm.

And some are just amusing (IT humour):

Alice and Bob were in trouble until they received a letter from an obscure graduate student in cryptography. The information in the letter was too theoretical to be of any earthly use to anyone, but the envelope the letter came in was extremely handy.

Alice is the chief financial officer at Secrets, Ltd.—“We don’t tell you our motto.”

Further Reading

  • Ross Anderson: Why Cryptosystems Fail – an excellent summary of the real-world causes of it security problems. Sadly, the partially optimistic ending to the article has not come true - the article is from around 1993, but in my experience the same problems are still occurring in the current decade. It appears that applying good security practices are just not part of human nature or commercial interests.

  • TSMC fails to apply patches - TSMC fails to apply Windows security patches, loses US$250 million due to factory shutdown.