Skip to main content
main-content

Über dieses Buch

In cryptography, ciphers is the technical term for encryption and decryption algorithms. They are an important sub-family that features high speed and easy implementation and are an essential part of wireless internet and mobile phones.

Unlike block ciphers, stream ciphers work on single bits or single words and need to maintain an internal state to change the cipher at each step. Typically stream ciphers can reach higher speeds than block ciphers but they can be more vulnerable to attack. Here, mathematics comes into play. Number theory, algebra and statistics are the key to a better understanding of stream ciphers and essential for an informed decision on their safety.

Since the theory is less developed, stream ciphers are often skipped in books on cryptography. This book fills this gap. It covers the mathematics of stream ciphers and its history, and also discusses many modern examples and their robustness against attacks.

Part I covers linear feedback shift registers, non-linear combinations of LFSRs, algebraic attacks and irregular clocked shift registers. Part II studies some special ciphers including the security of mobile phones, RC4 and related ciphers, the eStream project and the blum-blum-shub generator and related ciphers.

Stream Ciphers requires basic knowledge of algebra and linear algebra, combinatorics and probability theory and programming. Appendices in Part III help the reader with the more complicated subjects and provides the mathematical background needed. It covers, for example, complexity, number theory, finite fields, statistics, combinatorics. Stream Ciphers concludes with exercises and solutions and is directed towards advanced undergraduate and graduate students in mathematics and computer science.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction to Stream Ciphers

Abstract
In this chapter we follow the history of ciphers from its beginning to modern days. The historic few point helps us to understand the difference between the two big classes of ciphers (block ciphers and stream ciphers). We analyse attacks from the past to learn for the future.
Andreas Klein

Shift Register-Based Stream Ciphers

Frontmatter

Chapter 2. Linear Feedback Shift Registers

Abstract
Linear Feedback Shift Registers (LFSRs) have nice statistical properties and a well developed theory. They are also cheap and fast. This makes them attractive as basis for ciphers. In this chapter we will review the part of the theory we will need. A focus lies on the algorithmic parts.
Andreas Klein

Chapter 3. Non-linear Combinations of LFSRs

Abstract
As we have seen in the previous chapter a secure cipher need at least one nonlinear part. The natural way to proceed is to study nonlinear combinations of LFSRs. In this chapter we will meet for the first time the three big attack classes (correlation attacks, algebraic attacks, time-memory trade-off attacks). Which are central elements in the following chapters.
Andreas Klein

Chapter 4. Correlation Attacks

Abstract
Correlation attacks a quite old attack class and modern ciphers are usually designed to defend them. But in the past decade several improvements were made, forcing us to take higher security margins than in the past. We go through different types of correlation attacks and investigating tricks from computer science to statistics to squeeze out maximal performance.
Andreas Klein

Chapter 5. BDD-Based Attacks

Abstract
Binary Decision Diagrams (BDDs) are an efficient way to store and manipulate Boolean functions. BDD-based attacks are a new a quite successful variant of time-memory trade-off attacks. We will learn to handle BDDs and finally investigate a BDD-based attack against E 0 (Bluetooth) as a real world example.
Andreas Klein

Chapter 6. Algebraic Attacks

Abstract
As the name suggests algebraic attacks need a lot of algebra. So we take a crash course in solving systems of nonlinear equations. At the end of the chapter we will look on two real word examples to see how the theory pays off. We will see how algebraic attacks breaks the eStream candidate LILI-128 and we will revisit E 0 to see how algebraic attacks put pressure on it.
Andreas Klein

Chapter 7. Irregular Clocked Shift Registers

Abstract
In this chapter we will learn the concept of irregular clocking. There are some simple but still unbroken ciphers of this type. We investigate the possibility of correlation attacks which are currently the best know attacks against the shrinking generator. The chapter closes with a discussion of the dangers from side channel attacks.
Andreas Klein

Some Special Ciphers

Frontmatter

Chapter 8. The Security of Mobile Phones (GSM)

Abstract
Beginning with this chapter the focus switches from general principles to special ciphers. We start with the two variants of the A5 cipher of the GSM protocol (mobile phones). We will learn how to break these ciphers and by the way revisit many of the attacks from the previous chapters.
Andreas Klein

Chapter 9. RC4 and Related Ciphers

Abstract
RC4 is a widely used cipher designed for 8-bit processors. It is part of the wireless LAN standards WEP and WPA. The chapter starts with the analysis of these protocols and show how protocol failures helps the attacker. Then we analyse RC4 in detail with a special focus on the weak key scheduling. We will learn how to break RC4 if carelessly used and we will learn how to use it in a secure way. We will also have a look on some variations of RC4 and see how to transfer attacks against RC4 to its variants.
Andreas Klein

Chapter 10. The eStream Project

Abstract
The eStream project (2004–2008) was a research project of European cryptographers to identify a portfolio of interesting new stream ciphers. Representative for all ciphers from these project we describe three in detail. Two unbroken finalists: one optimised for hardware an one optimised for software implementation. The third example is an interesting, but unfortunately unsuccessful attempt to revive asynchronous stream ciphers. All three examples show state of the art stream cipher design.
Andreas Klein

Chapter 11. The Blum-Blum-Shub Generator and Related Ciphers

Abstract
This chapter covers stream ciphers with security proofs with a special focus on the Blum-Blum-Shub generator the most important cipher of that type. We will learn what security proofs are, what they can do for us and what they can’t do for us.
Andreas Klein

Mathematical Background

Frontmatter

Chapter 12. Computational Aspects

Abstract
Beginning with this chapter starts a collection of background materials. This chapter contains
  • bit tricks for efficient sideway addition (useful for correlation attacks),
  • tips for memory and cache efficient BDD implementation,
  • a summary of results form complexity theory (useful for ciphers with security proofs),
  • a collection of efficient matrix computation algorithms (for algebraic attacks).
Andreas Klein

Chapter 13. Number Theory

Abstract
Many ciphers with security proof including the Blum-Blum-Shub generator base on number theory problems. This chapter collect the parts of number theory necessary to understand the security proofs and the attacks.
Andreas Klein

Chapter 14. Finite Fields

Abstract
A short collection of properties of finite field designed as reminder of the algebra course.
Andreas Klein

Chapter 15. Statistics

Abstract
In cryptography we use statistics to decide whether a small bias is just a coincident or a real weakness which lead to an attack. Better statistics can speed up the attacks significantly. Not all the statistics we need is part of standard introduction courses. Therefore this chapter explains the more exotic statics we use.
Andreas Klein

Chapter 16. Combinatorics

Abstract
Enumerative Combinatorics is of course an important part of cryptography. We use it extensively when analysing RC4. Here are the proofs for some combinatorial results which we used.
Andreas Klein

Exercises with Solutions

Frontmatter

Chapter 17. Exercises

Abstract
To help for self studying this chapter provides a set of exercises. The exercises are sorted roughly according to the order of chapters. But sometimes they are chapter bridging.
Andreas Klein

Chapter 18. Solutions

Abstract
Solutions to the exercises from the previous chapter.
Andreas Klein

Programs

Frontmatter

Chapter 19. An Overview of the Programs

Abstract
I have written example programs for most of the algorithms described in the book. You can download the programs from the corresponding homepage and use them as basis for your own experiments. Here I describe what is necessary to get them running.
Andreas Klein

Chapter 20. Literate Programming

Abstract
Together with https://static-content.springer.com/image/chp%3A10.1007%2F978-1-4471-5079-4_20/310998_1_En_20_IEq1_HTML.gif Donald Knuth developed a new way to document programs: literate programming. This technique is less well known then its deserve. I used literate programming consequently for all my programs. Here I describe the system I use and make a bit advertisement for this fantastic programming style.
Andreas Klein

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise