Post Thu May 03, 2012 7:06 pm

The Block Cipher Companion

A few weeks ago I picked up a new book called The Block Cipher Companion by Lars Knudsen and Matthew J.B. Robshaw.  I don't know if we have any other crypto nerds lurking on this forum, but I decided to post this review just in case.

You can find the book on Amazon here:
http://www.amazon.com/dp/3642173411/ref=rdr_ext_tmb

The book is aimed at practioners and aspiring researchers in block cipher cryptography.  It is very well-written and accessible (for a cryptography book).  I've been interested in cryptography since Applied Crypto came out when I was in high school so I was very excited to finally see a dedicated book on block ciphers.

In addition to being of interest to cryptgraphers, I think the book is also useful for security engineers.  If you want to know more about how block ciphers work and how they should be used in practice, but don't want to actually design and break block ciphers, read chapters 1-5 and chapter 9. 

The book is not meant to be a first book in cryptography.  If you are just starting out, read Understanding Cryptography by Christof Paar & Jan Pelzl or Cryptography and Network Security by William Stallings.  I haven't read Stallings' book, but it is popular as a textbook and appears to cover the background material you'll need.  I love Paar & Pelzl's book.  In particular, it does a great job of explaining the math behind AES.

The book is awesome.  I've read some cryptanalysis papers, but I've never been able to devote as much time to cryptography as I'd like so much information organized into one volume.  I'm considering doing cryptography research in grad school and I think this book will be very useful if I do.  One of the biggest strengths of the book is that it has tons of references.  There are 769 references which is tremendous for a book that's only about 220 pages.  Each chapter has a further reading section that organizes the references by topic.  For someone considering research, having a good road map for the research literature is extremely valuable.  The book is also very well written which makes it much easier to understand.  It's hard to explain cryptography in an accessible manner, but the authors of this book do a great job.

My chief complaint is that Chapter 8, Advanced Attacks, moves too fast and really doesn't go into enough detail about some of the attacks for you to understand them without reading the associated papers.  I also think chapter nine could stand to include more detail, but it's still accessible and shouldn't confuse anyone.  Overall, I rate the book 9/10.  If they expanded chapter 8 and perhaps chapter 9, I'd rate it 10/10.

The first few chapters cover the design of DES and AES while also mentioning the attacks against them.  These chapters don't actually explain the attacks--the later chapters do that--so they are worth revisiting after you've read the rest of the book.  The fourth and fifth chapers are probably the most important for a security engineer.  They cover implementation details and some ways that block ciphers can be attacked in practice (including rainbow tables which are used in password cracking).  Chapters six through eight describe how block cipher algorithms are attacked and designed.  Chapter nine describes several other block cipher designs that are intersting for one reason or another.

Below, I give a chapter by chapter review of the book.

1. Introduction

The introduction is very basic and introdues some terms and the notion of a block cipher.  It doesn't say anything that someone familiar with basic crypto shouldn't already know.

2. DES

This chapter describes DES and explains the history and design criteria behind it.  It also describes several variants on DES and their security properties.  There's nothing groundbreaking here.  This chapter would fit well in any introductory crypto textbook and should (mostly) be a refresher for readers seeking out this book.

3. AES

The first part of this chapter describes AES and, like the previous chapter, could easily fit into an introductory textbook.  The AES chapter in Paar and Pelzl's Understanding Cryptography does a better job of explaining the background behind AES and readers unfamiliar with the math or who are encountering AES (or crypto in general) for the first time should read that book first.  Having already read previous descriptions of AES, I felt like my understanding of the algorithm improved somewhat after reading the description in this book.

The second part of this chapter explains the various attacks that have been tried on AES and describes the current state of affairs.  Since these attacks have not been explained yet, this section is probably worth skimming a second time after reading the rest of the book.

4. Using Block Ciphers

This chapter explains how block ciphers are used in practice and covers several operational topics including modes of operation, padding, message authentication codes, and hashing with block ciphers.  The chapter also describes some of the attacks that are possible with various modes of operation.  While some of this material is covered in introductory textbooks, the treatment here is better and has more depth.  At least some of it will be new to most readers.  This chapter should be read (and re-read) by anyone who plans to implement block cipher cryptography in practice.

5. Brute-force attacks

While the focus of this book is block ciphers, this chapter is useful to anyone wanting to understand how modern password crackers work.  While I bought the book to learn more about block ciphers and cryptanalysis, this chapter made me sad that the book's focus is so narrow.  The topics in this chapter would have gone great with a discussion so salts, password/key-stretching, and GPU (or similar) cracking efforts.

This chapter does a better job of covering brute-force attacks than any book I've seen.  It explains Martin Hellman's time-memory trade-off as well as the Rainbow Tables attack that came after it.  It also explains attacks on multiple encryption and does so with more depth than I've seen in introductory books.  If you're curious about how Rainbow Tables work and haven't read Oecshlin's paper, this chapter will fill you in.  I recommend reading both so I linked the paper after my review.  You're welcome. 

6. Differential Cryptanalysis: The Idea

The first chapters of this book should be useful to both aspiring cryptographers and security people who need to implement or work with cryptography.  This chapter is the first of three that are focused solely on cryptographers.  Many introductory textbooks now cover basic differential and linear cryptanalysis but the treatment is pretty superficial.  That's not the case here.  The authors invent a series of toy ciphers that they break using increasingly advanced differential attacks.  The later versions of the toy cipher have more rounds and permute the input bits which complicates the attack.  This chapter is the most accessible coverage of differential cryptanalysis that I've seen.  It's even better than Howard Heys' tutorial and that was pretty damn good. 

This chapter introduces the concepts and terminology, but it also explains implementation details.  It may be tough reading for someone encountering the material for the first time, but it's worth it.  If you really get stuck, try reading the Heys tutorial.  They are both clear and (relatively) easy to follow, but it may help to hear a concept explained slightly differently if you're having trouble.  By the time you finish this chapter, you're ready to start looking at the advanced variations of the attack that are used in various cryptanalysis papers.

7. Linear Cryptanalysis: The Idea

This chapter is similar in structure to the previous one and explains linear cryptanalysis, the other of the two major cryptanaytic attacks that spurred codebreaking research in the 90s.  Again, the authors use a series of toy ciphers and proceed to evolve their attack along with the cipher showing how to implement the attack on a cipher with several rounds that also permutes the input bits in each round. 

8. Advanced Topics

I have a love-hate relationship with this chapter.  It's by far the most difficult to read in the book.  The authors revisit differential and linear cryptanalysis and explain some formal notions that are useful for cryptanalysis research.  They also describe advanced variants on linear and differential cryptanalysis as well as other advanced attacks that are unrelated.  The end of the chapter also explains the current state of block cipher design and how the attacks of the past years have affected it.

This chapter covers a lot of material in relatively little space.  It helped me to understand several attacks that I was unfamiliar with.  It includes copious references.  If you have any inclination toward conducting block cipher research or cryptanalysis, this chapter is worth reading (several times). 

My chief complaint is that it tries to cover too much too fast.  While this is the longest chapter in the book, it really should be longer and perhaps split into two.  I understand that the authors had to make a trade-off.  There is a huge body of literature in block cipher design and cryptanalysis.  The authors obviously did not want to write a 1,000 page tome that covered every detail of each attack and variation.  But, some parts of this chapter are just plain hard to understand without more detail.

Rather than reading the chapter straight through, I recommend pairing each section with one or more of the referenced papers.  This will give you the depth you really need to understand the attacks.  Of course, if a section doesn't interest you or provides the amount of detail you want, just keep reading.  But if something doesn't make sense after reviewing it for a bit or if the details aren't there, put the book down and spend the time reading the papers behind the idea.
For a cryptography grad student, this chapter is the most important one in the book and can serve as a guide to the literature on cryptanalysis.  They'll have to read all of the papers anyway so they may not mind that the chapter is a little lean.

9.  A Short Survey and Six Prominent Ciphers

Most introductory textbooks only cover DES and AES with, at best, a passing mention of some other block ciphers.  This chapter really helps to round out the book by giving some details on six other block ciphers.  While AES is the standard, there are many other block ciphers in existence and they are important.  Some of them are no longer used but introduced important design concepts.  FEAL attempted to provide a better alternative to DES and instead became a crash-test dummy for new attacks (it's vulnerable to everything).  PRESENT uses design ideas similar to AES but is intended for embedded or other constrained conditions where even AES proves too resource heavy. 

The chapter is an easy read and was relaxing in comparison to the previous chapter.  Again, however, I think the chapter is too short.  The chapter doesn't fully detail the designs of the six ciphers and it should.  Since the book is inteded as a companion for practitioners and researchers, including the full details of these designs would make the volume a more dependable resource. 

Further reading:

Understanding Cryptography by Christof Paar and Jan Pelzl is my favorite introduction to cryptography.  If you haven't read another crypto book, start here.

Bruce Schneier's Applied Cryptography is a little dated, but it covers a huge number of block cipher algorithms.  The book came out five years before AES, but it includes a lot of cool ciphers.  If you're really interested in block ciphers, it's still a book well worth having.

Cryptography Engineering (previously Practical Cryptography) by Niels Ferguson and Bruce Schneier is entirely about implementing cryptography.  The authors both came to the conclusion that most of the real-world problems are not due to bad cipher designs but to poor implementation and other security problems.  This is their contribution to solving the problem.

Network Security: Private Communication in a Public World is a great introduction to network security protocols.  It covers design principles and real-world protocols including IPSec, SSL, Kerberos, and others.

Making a Faster Cryptanalytic Time-Memory Trade-Off
http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf

A Tutorial on Linear and Differential Cryptanalysis
http://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
BS in IT, CISSP, MS in IS Management (in progress)