[PDF](+73👁️) Télécharger Crypto 101 pdf

Crypto 101

lvh


1



2


Copyright 2013-2016, Laurens Van Houtven

This book is made possible by your donations. If you enjoyed it, please
consider making a donation, so it can be made even better and reach
even more people.

This work is available under the Creative Commons Attribution-NonCommercial
4.0 International (CC BY-NC 4.0) license. You can find the full text of
the license at https://creativecommons.Org/licenses/by-nc/4.0/.



The following is a human-readable summary of (and not a substitute
for) the license. You can:

• Share: copy and redistribute the material in any medium or
format

• Adapt: remix, transform, and build upon the material

The licensor cannot revoke these freedoms as long as you follow
the license terms:

• Attribution: you must give appropriate credit, provide a link to
the license, and indicate if changes were made. You may do so
in any reasonable manner, but not in any way that suggests the
licensor endorses you or your use.

• Noncommercial: you may not use the material for commercial
purposes.

• No additional restrictions: you may not apply legal terms or
technological measures that legally restrict others from doing
anything the license permits.



3


You do not have to comply with the license for elements of the
material in the public domain or where your use is permitted by an
applicable exception or limitation.

No warranties are given. The license may not give you all of the
permissions necessary for your intended use. For example, other rights
such as publicity, privacy, or moral rights may limit how you use the
material.



Pomidorkowi


4



Contents

Contents 5

I Foreword 10

1 About this book 11

2 Advanced sections 13

3 Development 14

4 Acknowledgments 15

II Building blocks 17

5 Exclusive or 18

5.1 Description 18

5.2 A few properties of XOR 19

5.3 Bitwise XOR 20

5.4 One-time pads 21

5.5 Attacks on ’’one-time pads” 23

5.6 Remaining problems 29


5


CONTENTS


6


6 Block ciphers 30

6.1 Description 30

6.2 AES 36

6.3 DES and 3DES 41

6.4 Remaining problems 43

7 Stream ciphers 45

7.1 Description 45

7.2 A naive attempt with block ciphers 45

7.3 Block cipher modes of operation 53

7.4 CBC mode 53

7.5 Attacks on CBC mode with predictable IVs 55

7.6 Attacks on CBC mode with the key as the IV ... . 57

7.7 CBC bit flipping attacks 59

7.8 Padding 62

7.9 CBC padding attacks 63

7.10 Native stream ciphers 71

7.11 RC4 73

7.12 Salsa20 83

7.13 Native stream ciphers versus modes of operation ... 85

7.14 CTR mode 86

7.15 Stream cipher bit flipping attacks 87

7.16 Authenticating modes of operation 88

7.17 Remaining problems 88

8 Key exchange 90

8.1 Description 90

8.2 Abstract Diffie-Hellman 91

8.3 Diffie-Hellman with discrete logarithms 95

8.4 Diffie-Hellman with elliptic curves 96

8.5 Remaining problems 98

9 Public-key encryption 100

9.1 Description 100


CONTENTS


7


9.2 Why not use public- key encryption for everything? . 101

9.3 RSA . 102

9.4 Elliptic curve cryptography 108

9.5 Remaining problem: unauthenticated encryption . . 108

10 Hash functions 110

10.1 Description 110

10.2 MD5 112

10.3 SHA-1 112

10.4 SHA-2 112

10.5 Keccak and SHA-3 113

10.6 BLAKE and BLAKE2 113

10.7 Password storage 113

10.8 Length extension attacks 118

10.9 Hash trees 120

10. 10 Remaining issues 120

11 Message authentication codes 121

11.1 Description 121

11.2 Combining MAC and message 124

11.3 A naive attempt with hash functions 126

11.4 HMAC 130

11.5 One-time MACs 132

11.6 Carter-Wegman MAC 136

11.7 Authenticated encryption modes 137

11.8 OCB mode 139

11.9 GCM mode 142

12 Signature algorithms 143

12.1 Description 143

12.2 RSA-based signatures 144

12.3 DSA 144

12.4 ECDSA 150

12.5 Repudiable authenticators 150


CONTENTS


13 Key derivation functions 152

13.1 Description 152

13.2 Password strength 154

13.3 PBKDF2 154

13.4 bcrypt 154

13.5 scrypt 154

13.6 HKDF 154

14 Random number generators 159

14.1 Introduction 159

14.2 True random number generators 160

14.3 Cryptographically secure pseudorandom generators . 163

14.4 Yarrow 164

14.5 Blum Blum Shub 164

14.6 Dual_EC_DRBG 165

14.7 Mersenne Twister 173

III Complete cryptosystems 181

15 SSL and TLS 182

15.1 Description 182

15.2 Handshakes 183

15.3 Certificate authorities 184

15.4 Self-signed certificates 185

15.5 Client certificates 185

15.6 Perfect forward secrecy 186

15.7 Attacks 187

15.8 HSTS 191

15.9 Certificate pinning 193

15. 10 Secure configurations 193

16 OpenPGP and GPG 195

16.1 Description 195


CONTENTS


9


16.2 The web of trust 196

17 Off-The-Record Messaging (OTR) 199

17.1 Description 199

17.2 Key exchange 201

17.3 Data exchange 205

IV Appendices 206

A Modular arithmetic 207

A.l Addition and subtraction 208

A.2 Prime numbers 210

A. 3 Multiplication 212

A.4 Division and modular inverses 212

A. 5 Exponentiation 214

A.6 Exponentiation by squaring 215

A. 7 Montgomery ladder exponentiation 217

A. 8 Discrete logarithm 223

A. 9 Multiplicative order 225

B Elliptic curves 226

B. l The elliptic curve discrete log problem 228

C Side-channel attacks 230

C. l Timing attacks 230

C.2 Power measurement attacks 230

Bibliography 231

Glossary 237

Acronyms 244


Part I

Foreword


10




About this book


Lots of people working in cryptography have no deep
concern with real application issues. They are trying to
discover things clever enough to write papers about.

Whitfield Diffie

This book is intended as an introduction to cryptography for pro-
grammers of any skill level. It’s a continuation of a talk of the same
name, which was given by the author at PyCon 2013.

The structure of this book is very similar: it starts with very simple
primitives, and gradually introduces new ones, demonstrating why
they’re necessary. Eventually, all of this is put together into complete,
practical cryptosystems, such as TLS, GPG and OTR.

The goal of this book is not to make anyone a cryptographer or a
security researcher. The goal of this book is to understand how complete


11



CHAPTER 1. ABOUT THIS BOOK


12


cryptosystems work from a bird’s eye view, and how to apply them in
real software.

The exercises accompanying this book focus on teaching cryptogra-
phy by breaking inferior systems. That way, you won’t just ’’know” that
some particular thing is broken; you’ll know exactly how it’s broken,
and that you, yourself, armed with little more than some spare time and
your favorite programming language, can break them. By seeing how
these ostensibly secure systems are actually completely broken, you will
understand why all these primitives and constructions are necessary for
complete cryptosystems. Hopefully, these exercises will also leave you
with healthy distrust of DIY cryptography in all its forms.

For a long time, cryptography has been deemed the exclusive realm
of experts. From the many internal leaks we’ve seen over the years of
the internals of both large and small corporations alike, it has become
obvious that that approach is doing more harm than good. We can no
longer afford to keep the two worlds strictly separate. We must join
them into one world where all programmers are educated in the basic
underpinnings of information security, so that they can work together
with information security professionals to produce more secure software
systems for everyone. That does not make people such as penetration
testers and security researchers obsolete or less valuable; quite the
opposite, in fact. By sensitizing all programmers to security concerns,
the need for professional security audits will become more apparent,
not less.

This book hopes to be a bridge: to teach everyday programmers
from any field or specialization to understand just enough cryptography
to do their jobs, or maybe just satisfy their appetite.



2


Advanced sections


This book is intended as a practical guide to cryptography for program-
mers. Some sections go into more depth than they need to in order
to achieve that goal. They’re in the book anyway, just in case you’re
curious; but I generally recommend skipping these sections. They’11 be
marked like this:



This is an optional, in-depth section. It almost cer-
tainly won’t help you write better software, so feel free
to skip it. It is only here to satisfy your inner geek’s
curiosity.


13




3


Development


The entire Crypto 101 project is publicly developed on GitHub under
the cryptolOl organization, including this book.

This is an early pre-release of this book. All of your questions, com-
ments and bug reports are highly appreciated. If you don’t understand
something after reading it, or a sentence is particularly clumsily worded,
that’s a hug and I would very much like to fix it! Of course, if I never
hear about your issue, it’s very hard for me to address. . .

The copy of this book that you are reading right now is based on
the git commit with hash 3f89ec3, also known as 0.4.0-22-g3f89ec3.


14




Acknowledgments


This book would not have been possible without the support and con-
tributions of many people, even before the first public release. Some
people reviewed the text, some people provided technical review, and
some people helped with the original talk. In no particular order:

• My wife, Ewa

• Brian Warner

• Oskar Zabik

• Ian Cordasco

• Zooko Wilcox-O’Hearn

• Nathan Nguyen (@nathanhere)


15



CHAPTER 4. ACKNOWLEDGMENTS


16


Following the public release, many more people contributed changes.
I’d like to thank the following people in particular (again, in no partic-
ular order):

• coh2, for work on illustrations

• TinnedTuna, for review work on the XOR section (and others)

• dfc, for work on typography and alternative formats

• jvasile, for work on typefaces and automated builds

• hmmueller, for many, many notes and suggestions

.. as well as the huge number of people that contributed spelling,
grammar and content improvements. Thank you!



Part II

Building blocks


17



5


Exclusive or


5.1 Description

Exclusive or, often called ”XOR”, is a Boolean 1 binary 2 operator that
is true when either the first input or the second input, but not both, are
true.

Another way to think of XOR is as something called a ’’programmable
inverter”: one input bit decides whether to invert the other input bit,
or to just pass it through unchanged. ’’Inverting” bits is colloquially
called ’’flipping” bits, a term we’ll use often throughout the book.

In mathematics and cryptography papers, exclusive or is generally
represented by a cross in a circle: ©. We’ll use the same notation in
this book:

1 Uses only ’’true” and ’’false” as input and output values.

2 Takes two parameters.


18



CHAPTER 5. EXCLUSIVE OR


19


ki



The inputs and output here are named as if we ’re using XOR as an
encryption operation. On the left, we have the plaintext bit Pi. The i
is just an index, since we’ll usually deal with more than one such bit.
On top, we have the key bit ki, that decides whether or not to invert
Pi. On the right, we have the ciphertext bit, c % , which is the result of
the XOR operation.

5.2 A few properties of XOR

Since we’ll be dealing with XOR extensively during this book, we’ll
take a closer look at some of its properties. If you’re already familiar
with how XOR works, feel free to skip this section.

We saw that the output XOR is 1 when one input or the other (but
not both) is 1:


0 © 0=0 100=1

001=1 101=0


There’s a few useful arithmetic tricks we can derive from that.



CHAPTER 5. EXCLUSIVE OR


20


1. You can apply XOR in any order: a © b = b © a, no matter what
values a and b are. 3

2. Any bit XOR itself is 0: a © a = 0. If a is 0, then it’s 0 ® 0 = 0;
if a is 1, then it’s 1 © 1 = 0.

3. Any bit XOR 0 is that bit again: a ® 0 = a. If a is 0, then it’s
0 © 0 = 0; if a is 1, then it’s 1 © 0 = 1.

These rules also imply a ffi b © a = b:


a©6©a = a©a©6 (first rule)

= 0 ffi 6 (second rule)

= b (third rule)

We’ll use this property often when using XOR for encryption; you
can think of that first XOR with a as encrypting, and the second one
as decrypting.

5.3 Bitwise XOR

XOR, as we’ve just defined it, operates only on single bits or Boolean
values. Since we usually deal with values comprised of many bits, most
programming languages provide a ’’bitwise XOR” operator: an operator
that performs XOR on the respective bits in a value.

Python, for example, provides the ~ (caret) operator that performs
bitwise XOR on integers. It does this by first expressing those two


3 This property is known as commutativity; we say that XOR is commutative.


CHAPTER 5. EXCLUSIVE OR


21


integers in binary 4 , and then performing XOR on their respective bits.
Hence the name, bitwise XOR.


73 © 87 = 061001001 0 061010111

10 0 10 0

— (212) (212) (212) (212) (212) (2Th

— XL7 VJ7 VJ7 XL7 U7 XL7

10 10 11

= 001111

= 060011110
= 30


5.4 One-time pads

XOR may seem like an awfully simple, even trivial operator. Even so,
there’s an encryption scheme, called a one-time pad, which consists of
just that single operator. It’s called a one-time pad because it involves
a sequence (the ’’pad”) of random bits, and the security of the scheme
depends on only using that pad once. The sequence is called a pad
because it was originally recorded on a physical, paper pad.

This scheme is unique not only in its simplicity, but also because
it has the strongest possible security guarantee. If the bits are truly
random (and therefore unpredictable by an attacker), and the pad is

4 Usually, numbers are already stored in binary internally, so this doesn’t actually
take any work. When you see a number prefixed with ”0b”, the remaining digits are a
binary representation.


1 (left)

0

1 (right)

0


CHAPTER 5. EXCLUSIVE OR


22


only used once, the attacker learns nothing about the plaintext when
they see a ciphertext. 5

Suppose we can translate our plaintext into a sequence of bits. We
also have the pad of random bits, shared between the sender and the
(one or more) recipients. We can compute the ciphertext by taking the
bitwise XOR of the two sequences of bits.



If an attacker sees the ciphertext, we can prove that they will learn
zero information about the plaintext without the key. This property
is called perfect security. The proof can be understood intuitively by
thinking of XOR as a programmable inverter, and then looking at a
particular bit intercepted by Eve, the eavesdropper.

Let’s say Eve sees that a particular ciphertext bit q is 1. She has no
idea if the matching plaintext bit pi was 0 or 1, because she has no idea
if the key bit ki was 0 or 1. Since all of the key bits are truly random,
both options are exactly equally probable.

5 The attacker does learn that the message exists, and, in this simple scheme, the
length of the message. While this typically isn’t too important, there are situations
where this might matter, and there are secure cryptosystems to both hide the existence
and the length of a message.


CHAPTER 5. EXCLUSIVE OR


23


Alice 7 7 Bob

hi ki



Eve

5.5 Attacks on ’’one-time pads”

The one-time pad security guarantee only holds if it is used correctly
First of all, the one-time pad has to consist of truly random data.
Secondly, the one-time pad can only be used once (hence the name).
Unfortunately, most commercial products that claim to be ’’one-time
pads” are snake oil 6 , and don’t satisfy at least one of those two properties.

Not using truly random data

The first issue is that they use various deterministic constructs to pro-
duce the one-time pad, instead of using truly random data. That isn’t
necessarily insecure: in fact, the most obvious example, a synchronous
stream cipher, is something we’ll see later in the book. However, it
does invalidate the ’’unbreakable” security property of one-time pads.
The end user would be better served by a more honest cryptosystem,
instead of one that lies about its security properties.

6 ”Snake oil” is a term for all sorts of dubious products that claim extraordinary
benefits and features, but don’t really realize any of them.


CHAPTER 5. EXCLUSIVE OR


24


Reusing the ’’one-time” pad

The other issue is with key reuse, which is much more serious. Suppose
an attacker gets two ciphertexts with the same ’’one-time” pad. The
attacker can then XOR the two ciphertexts, which is also the XOR of
the plaintexts:


Cl © C2 = ( Pi © k) © (p2 © k)
= pi © k © p2 © k

= Pi®P2®k®k

= Pi © P2 © 0
= Pi © P2


(definition)
(reorder terms)
(a © b = b © a)
(x © x = 0)

(x © 0 = x)


At first sight, that may not seem like an issue. To extract either p\
or p 2 , you’d need to cancel out the XOR operation, which means you
need to know the other plaintext. The problem is that even the result of
the XOR operation on two plaintexts contains quite a bit information
about the plaintexts themselves. We’ll illustrate this visually with some
images from a broken ’’one-time” pad process, starting with figure 5.1
on page 25.


Crib -dragging

A classical approach to breaking multi-time pad systems involves ’’crib-
dragging”, a process that uses small sequences that are expected to occur
with high probability. Those sequences are called ’’cribs”. The name crib-
dragging originated from the fact that these small ’’cribs” are dragged
from left to right across each ciphertext, and from top to bottom across


CHAPTER 5. EXCLUSIVE OR


25



(a) First plaintext. (b) Second plaintext.



(c) First ciphertext. (d) Second ciphertext.



(e) Reused key. (f) XOR of ciphertexts.


Figure 5.1: Two plaintexts, the re-used key, their respective ciphertexts,
and the XOR of the ciphertexts. Information about the plaintexts
clearly leaks through when we XOR the ciphertexts.




CHAPTER 5. EXCLUSIVE OR


26


the ciphertexts, in the hope of finding a match somewhere. Those
matches form the sites of the start, or ’’crib”, if you will, of further
decryption.

The idea is fairly simple. Suppose we have several encrypted mes-
sages Ci encrypted with the same ’’one-time” pad K. 7 If we could
correctly guess the plaintext for one of the messages, let’s say Cj, we’d
know K :


Cj © Pj


( Pj © K) © Pj
K © Pj © Pj

K © 0
I<


Since K is the shared secret, we can now use it to decrypt all of the
other messages, just as if we were the recipient:


Pi = Ci® K for all i

Since we usually can’t guess an entire message, this doesn’t actually
work. However, we might be able to guess parts of a message.

If we guess a few plaintext bits pi correctly for any of the messages,
that would reveal the key bits at that position for all of the messages,
since k = c, ® p r . Hence, all of the plaintext bits at that position
are revealed: using that value for k, we can compute the plaintext bits
Pi = Ci® k for all the other messages.

7 We use capital letters when referring to an entire message, as opposed to just bits
of a message.


CHAPTER 5. EXCLUSIVE OR


27


Guessing parts of the plaintext is a lot easier than guessing the
entire plaintext. Suppose we know that the plaintext is in English.
There are some sequences that we know will occur very commonly, for
example (the u symbol denotes a space):

• u the u and variants such as . u The u

• u of u and variants

• u to u and variants

• u and u (no variants; only occurs in the middle of a sentence)

• u a u and variants

If we know more about the plaintext, we can make even better
guesses. For example, if it’s HTTP serving HTML, we would expect
to see things like Content-Type, <a>, and so on.

That only tells us which plaintext sequences are likely, giving us
likely guesses. How do we tell if any of those guesses are correct? If
our guess is correct, we know all the other plaintexts at that position as
well, using the technique described earlier. We could simply look at
those plaintexts and decide if they look correct.

In practice, this process needs to be automated because there are so
many possible guesses. Fortunately that’s quite easy to do. For example,
a very simple but effective method is to count how often different
symbols occur in the guessed plaintexts: if the messages contain English
text, we’d expect to see a lot of letters e, t, a, o, i, n. If we’re seeing
binary nonsense instead, we know that the guess was probably incorrect,
or perhaps that message is actually binary data.



CHAPTER 5. EXCLUSIVE OR


28


These small, highly probable sequences are called ’’cribs” because
they’re the start of a larger decryption process. Suppose your crib, u the u ,
was successful and found the five-letter sequence t u thr in another
message. You can then use a dictionary to find common words starting
with thr, such as through. If that guess were correct, it would reveal
four more bytes in all of the ciphertexts, which can be used to reveal
even more. Similarly, you can use the dictionary to find words ending
in t.

This becomes even more effective for some plaintexts that we know
more about. If some HTTP data has the plaintext ent-Len in it, then
we can expand that to Content-Length : u , revealing many more bytes.

While this technique works as soon as two messages are encrypted
with the same key, it’s clear that this becomes even easier with more
ciphertexts using the same key, since all of the steps become more
effective:

• We get more cribbing positions.

• More plaintext bytes are revealed with each successful crib and
guess, leading to more guessing options elsewhere.

• More ciphertexts are available for any given position, making
guess validation easier and sometimes more accurate.

These are just simple ideas for breaking multi-time pads. While
they’re already quite effective, people have invented even more effective
methods by applying advanced, statistical models based on natural
language analysis. This only demonstrates further just how broken
multi-time pads are. [33]


CHAPTER 5. EXCLUSIVE OR


29


5.6 Remaining problems

Real one-time pads, implemented properly, have an extremely strong
security guarantee. It would appear, then, that cryptography is over:
encryption is a solved problem, and we can all go home. Obviously,
that’s not the case.

One-time pads are rarely used, because they are horribly impractical:
the key is at least as large as all information you’d like to transmit, put
together. Plus, you’d have to exchange those keys securely, ahead of
time, with all people you’d like to communicate with. We’d like to
communicate securely with everyone on the Internet, and that’s a very
large number of people. Furthermore, since the keys have to consist of
truly random data for its security property to hold, key generation is
fairly difficult and time-consuming without specialized hardware.

One-time pads pose a trade-off. It’s an algorithm with a solid
information-theoretic security guarantee, which you can not get from
any other system. On the other hand, it also has extremely impractical
key exchange requirements. However, as we’ll see throughout this
book, secure symmetric encryption algorithms aren’t the pain point of
modern cryptosystems. Cryptographers have designed plenty of those,
while practical key management remains one of the toughest challenges
facing modern cryptography. One-time pads may solve a problem, but
it’s the wrong problem.

While they may have their uses, they’re obviously not a panacea. We
need something with manageable key sizes while maintaining secrecy.
We need ways to negotiate keys over the Internet with people we’ve
never met before.



6


Block ci P h ers


Few false ideas have more firmly gripped the minds
of so many intelligent men than the one that, if they just
tried, they could invent a cipher that no one could break.

David Kahn


6.1 Description

A block cipher is an algorithm that allows us to encrypt blocks of a
fixed length. It provides an encryption function E that turns plaintext
blocks P into ciphertext blocks C, using a secret key k:

C = E(k, P) (6.1)


30



CHAPTER 6. BLOCK CIPHERS


31


The plaintext and ciphertext blocks are sequences of bytes. They are
always the same size as one another, and that size is fixed by the block
cipher: it’s called the block cipher’s block size. The set of all possible
keys is called the keyspace.

Once we’ve encrypted plaintext blocks into ciphertext blocks, they
later have to be decrypted again to recover the original plaintext block.
This is done using a decryption function D, which takes the ciphertext
block C and the key k (the same one used to encrypt the block) as
inputs, and produces the original plaintext block P.


P = D(k, C)


Or, in blocks:


( 6 . 2 )


k


k



P


Block ciphers are an example of a symmetric-key encryption scheme,
also known as a secret-key encryption scheme. This means that the
same secret key is used for both encryption and decryption. We will
contrast this with public-key encryption algorithms, which have a
distinct key for encryption and decryption, later in the book.

A block cipher is a keyed permutation. It’s & permutation, because
the block cipher maps every possible block to some other block. It’s
also a keyed permutation, because the key determines exactly which
blocks map to which.


CHAPTER 6. BLOCK CIPHERS


32


We’ll illustrate this by looking at a block cipher with an impractical,
tiny 4-bit block size, so 2 4 = 16 possible blocks. Since each of those
blocks maps to a hexadecimal digit, we’ll represent the blocks by that
digit. Figure 6.1 illustrates the blocks that the cipher operates on.



Figure 6.1: All of the 16 nodes operated on by the block cipher. Each
node is designated by a hexadecimal digit.

Once we select a secret key, the block cipher will use that to de-
termine what the encryption of any given block is. We will illustrate
that relationship with an arrow: the block at the start of the arrow,
encrypted using E under key k, is mapped to the block at the end of


CHAPTER 6. BLOCK CIPHERS


33


the arrow.



Figure 6.2: An encryption permutation produced by the block cipher
under a particular key k.

In figure 6.2, you’ll notice that the permutation isn’t just one big
cycle: there’s a large cycle of 7 elements, and several smaller cycles of
4, 3 and 2 elements each. It’s also perfectly possible that an element
encrypts to itself. This is to be expected when selecting random permu-
tations, which is approximately what a block cipher is doing; it doesn’t
demonstrate a bug in the block cipher.

When you’re decrypting instead of encrypting, the block cipher
just computes the inverse permutation. In figure 6.3, you can see that








CHAPTER 6. BLOCK CIPHERS


34


we get the same illustration, except that all the arrows are going in the
other direction.





Figure 6.3: The decryption permutation produced by the block cipher
under the same key k: the inverse of the encryption permutation, that
is: all the arrows have been reversed.

The only way to know which block maps to which other block, is
to know the key. A different key will lead to a completely different set
of arrows, as you can see in figure 6.4.

In this illustration, you’ll notice that there’s even two permutations
of length 1: an element that maps to itself. This is again something to
be expected when selecting random permutations.











CHAPTER 6. BLOCK CIPHERS


35



Figure 6.4: An encryption permutation produced by the block cipher
under some other key


Knowing a bunch of (input, output) pairs for a given key shouldn’t
give you any information about any other (input, output) pairs under
that key 1 . As long as we’re talking about a hypothetical perfect block
cipher, there’s no easier way to decrypt a block other than to ’’brute-
force” the key: i.e. just try every single one of them until you find the
right one.

lr The attentive reader may have noticed that this breaks in the extremes: if you
know all but one of the pairs, then you know the last one by exclusion.










CHAPTER 6. BLOCK CIPHERS


36


Our toy illustration block cipher only has 4 bit blocks, or 2 4 =
16 possibilities. Real, modern block ciphers have much larger block
sizes, such as 128 bits, or 2 128 (slightly more than 10 38 5 ) possible
blocks. Mathematics tells us that there are n\ (pronounced ”n factorial”)
different permutations of an n element set. It’s defined as the product
of all of the numbers from 1 up to and including n:

n\ = 1 • 2 ■ 3 ■ . . . ■ (n — 1) ■ n

Factorials grow incredibly quickly. For example, 5! = 120, 10! =
3628800, and the rate continues to increase. The number of permuta-
tions of the set of blocks of a cipher with a 128 bit block size is (2 128 )!.
Just 2 128 is large already (it takes 39 digits to write it down), so (2 128 )!
is a mind-bogglingly huge number, impossible to comprehend. Com-
mon key sizes are only in the range of 128 to 256 bits, so there are only
between 2 128 and 2 256 permutations a cipher can perform. That’s just a
tiny fraction of all possible permutations of the blocks, but that’s okay:
that tiny fraction is still nowhere near small enough for an attacker to
just try them all.

Of course, a block cipher should be as easy to compute as possible,
as long as it doesn’t sacrifice any of the above properties.

6.2 AES

The most common block cipher in current use is Advanced Encryption
Standard (AES).

Contrary to its predecessor DES (which we’ll look at in more detail
in the next chapter), AES was selected through a public, peer-reviewed


CHAPTER 6. BLOCK CIPHERS


37


competition following an open call for proposals. This competition
involved several rounds where all of the contestants were presented,
subject to extensive cryptanalysis, and voted upon. The AES process
was well-received among cryptographers, and similar processes are
generally considered to be the preferred way to select cryptographic
standards.

Prior to being chosen as the Advanced Encryption Standard, the
algorithm was known as Rijndael, a name derived from the two last
names of the Belgian cryptographers that designed it: Vincent Rijmen
and Joan Daemen. The Rijndael algorithm defined a family of block
ciphers, with block sizes and key sizes that could be any multiple of
32 bits between 128 bits and 256 bits. [16] When Rijndael became
AES through the Federal Information Processing Standards (FIPS)
standardization process, the parameters were restricted to a block size
of 128 bits and keys sizes of 128, 192 and 256 bits. [1]

There are no practical attacks known against AES. While there
have been some developments in the last few years, most of them
involve related- key attacks [10], some of them only on reduced-round
versions of AES [9] .

A related key attack involves making some predictions about how
AES will behave with two different keys with some specific mathemat-
ical relation. Those predictions provide some information about what
identical (input, output) pairs will look like under those related keys.
Most of these attacks attempt to recover the key, or at least parts of it.

While a theoretically ideal block cipher wouldn’t be vulnerable to
a related key attack, these attacks aren’t considered practical concerns.
Because cryptographic keys are cryptographically random, the odds


CHAPTER 6. BLOCK CIPHERS


38


of selecting two such related keys is nonexistent. Such attacks are
interesting from an academic perspective: they can help provide insight
in the workings of the cipher, guiding cryptographers in designing
future ciphers and attacks against current ciphers.

A closer look at Rijndael



This is an optional, in-depth section. It almost cer-
tainly won’t help you write better software, so feel free
to skip it. It is only here to satisfy your inner geek’s
curiosity.


AES consists of several independent steps. At a high level, AES is a
substitution-permutation network.

Key schedule

AES requires separate keys for each round in the next steps. The key
schedule is the process which AES uses to derive 128-bit keys for each
round from one master key.

First, the key is separated into 4 byte columns. The key is rotated
and then each byte is run through an S-box (substitution box) that
maps it to something else. Each column is then XORed with a round
constant. The last step is to xor the result with the previous round key.

The other columns are then XORed with the previous round key
to produce the remaining columns.



CHAPTER 6. BLOCK CIPHERS


39


SubBytes


SubBytes is the S-box (substitution box) in AES. It is 8 x 8 bits in size.

It works by taking the multiplicative inverse over the Galois field,
and then applying an affine transformation so that there are no values
x so that x © S(x) = 0 or x © S(x) = 0xf f. To rephrase: there are no
values of x that the substitution box maps to x itself, or x with all bits
flipped. This makes the cipher resistant to differential attacks, unlike
the earlier DES algorithm, whose fifth S-box caused serious security
problems. 2



ShiftRows

After having applied the SubBytes step to the 16 bytes of the block,
AES shifts the rows in the 4x4 array:

2 In its defense, differential attacks were not publicly known back when DES was
designed.


CHAPTER 6. BLOCK CIPHERS


40


a 0,0

a 0,l

a 0,2

“ 0,3

0-1,0

Ol t l

0 1,2

Ol,3

02,0

02,1

02,2

a 2,3

a 3,0

03,1

a 3,2

“ 3,3


f>o,o

^ 0,1

bo, 2

bo, 3

bi,i

bi,2

bi,3

bi,o

& 2,2

^2,3

^ 2,0

b2,i

63,3

f>3,0

^3,1

b3,2


MixColumns

MixColumns multiplies each column of the state with a fixed polyno-
mial.

ShiftRows and MixColumns represent the diffusion properties of
AES.



AddRoundKey

As the name implies, the AddRoundKey step adds the bytes from the
round key produced by the key schedule to the state of the cipher.


CHAPTER 6. BLOCK CIPHERS


41



6.3 DES and 3DES

The Data Encryption Standard (DES) is one of the oldest block ciphers
that saw widespread use. It was published as an official FIPS standard
in 1977. It is no longer considered secure, mainly due to its tiny key
size of 56 bits. (The DES algorithm actually takes a 64 bit key input,
but the remaining 8 bits are only used for parity checking, and are
discarded immediately.) It shouldn’t be used in new systems. On
modern hardware, DES can be brute forced in less than a day. [21]

In an effort to extend the life of the DES algorithm, in a way that
allowed much of the spent hardware development effort to be reused,
people came up with 3DES: a scheme where input is first encrypted,


CHAPTER 6. BLOCK CIPHERS


42


then decrypted, then encrypted again:

c = EoEs(kl, DoEs(k‘2- EoEs(ki-P))) (6.3)

This scheme provides two improvements:

• By applying the algorithm three times, the cipher becomes harder
to attack directly through cryptanalysis.

• By having the option of using many more total key bits, spread
over the three keys, the set of all possible keys becomes much
larger, making brute-forcing impractical.

The three keys could all be chosen independently (yielding 168 key
bits), or k 3 = k\ (yielding 112 key bits), or k\ = k^ = k 3 , which,
of course, is just plain old DES (with 56 key bits). In the last keying
option, the middle decryption reverses the first encryption, so you
really only get the effect of the last encryption. This is intended as a
backwards compatibility mode for existing DES systems. If 3DES had
been defined as E(k \ , E(k, 2 , E(ks,p))), it would have been impossible
to use 3DES implementations for systems that required compatibility
with DES. This is particularly important for hardware implementations,
where it is not always possible to provide a secondary, regular ’’single
DES” interface next to the primary 3DES interface.

Some attacks on 3DES are known, reducing their effective security.
While breaking 3DES with the first keying option is currently imprac-
tical, 3DES is a poor choice for any modern cryptosystem. The security
margin is already small, and continues to shrink as cryptographic attacks
improve and processing power grows.


CHAPTER 6. BLOCK CIPHERS


43


Far better alternatives, such as AES, are available. Not only are they
more secure than 3DES, they are also generally much, much faster. On
the same hardware and in the same mode of operation (we’ll explain
what that means in the next chapter), AES-128 only takes 12.6 cycles
per byte, while 3DES takes up to 134.5 cycles per byte. [1 7 ] Despite
being worse from a security point of view, it is literally an order of
magnitude slower.

While more iterations of DES might increase the security margin,
they aren’t used in practice. First of all, the process has never been
standardized beyond three iterations. Also, the performance only be-
comes worse as you add more iterations. Finally, increasing the key
bits has diminishing security returns, only increasing the security level
of the resulting algorithm by a smaller amount as the number of key
bits increases. While 3DES with keying option 1 has a key length of
168 bits, the effective security level is estimated at only 112 bits.

Even though 3DES is significantly worse in terms of performance
and slightly worse in terms of security, 3DES is still the workhorse
of the financial industry. With a plethora of standards already in
existence and new ones continuing to be created, in such an extremely
technologically conservative industry where Fortran and Cobol still
reign supreme on massive mainframes, it will probably continue to be
used for many years to come, unless there are some large cryptanalytic
breakthroughs that threaten the security of 3DES.


6.4 Remaining problems

Even with block ciphers, there are still some unsolved problems.


CHAPTER 6. BLOCK CIPHERS


44


For example, we can only send messages of a very limited length:
the block length of the block cipher. Obviously, we’d like to be able to
send much larger messages, or, ideally, streams of indeterminate size.
We’ll address this problem with a stream cipher.

Although we have reduced the key size drastically (from the total
size all data ever sent under a one-time pad scheme versus a few bytes
for most block ciphers), we still need to address the issue of agreeing
on those few key bytes, potentially over an insecure channel. We’ll
address this problem in a later chapter with a key exchange protocol.



Stream ciphers


7.1 Description

A stream cipher is a symmetric-key encryption algorithm that encrypts
a stream of bits. Ideally, that stream could be as long as we’d like;
real-world stream ciphers have limits, but they are normally sufficiently
large that they don’t pose a practical problem.

7.2 A naive attempt with block ciphers

Let’s try to build a stream cipher using the tools we already have. Since
we already have block ciphers, we could simply divide an incoming


45



CHAPTER 7. STREAM CIPHERS


46


stream into different blocks, and encrypt each block:


abcdefgh ijklmno pqrstuvw



This scheme is called ECB mode (Electronic Code Book Mode),
and it is one of the many ways that block ciphers can be used to construct
stream ciphers. Unfortunately, while being very common in home-
grown cryptosystems, it poses very serious security flaws. For example,
in ECB mode, identical input blocks will always map to identical output
blocks:


abcdefgh abcdefgh abcdefgh



APOHGMMW APOHGMMW APOHGMMW


( 7 . 2 )


At first, this might not seem like a particularly serious problem.
Assuming the block cipher is secure, it doesn’t look like an attacker
would be able to decrypt anything. By dividing the ciphertext stream
up into blocks, an attacker would only be able to see that a ciphertext
block, and therefore a plaintext block, was repeated.

We’ll now illustrate the many flaws of ECB mode with two attacks.
First, we’ll exploit the fact that repeating plaintext blocks result in
repeating ciphertext blocks, by visually inspecting an encrypted image.
Then, we’ll demonstrate that attackers can often decrypt messages
encrypted in ECB mode by communicating with the person performing
the encryption.


CHAPTER 7. STREAM CIPHERS


47


Visual inspection of an encrypted stream

To demonstrate that this is, in fact, a serious problem, we’ll use a
simulated block cipher of various block sizes and apply it to an image 1 .
We’ll then visually inspect the different outputs.

Because identical blocks of pixels in the plaintext will map to iden-
tical blocks of pixels in the ciphertext, the global structure of the image
is largely preserved.

As you can see, the situation appears to get slightly better with
larger block sizes, but the fundamental problem still remains: the
macrostructure of the image remains visible in all but the most extreme
block sizes. Furthermore, all but the smallest of these block size
Lire la suite

• Taille
  15.51 MB
• Nombre de pages
  15