#### Termes les plus recherchés

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

#### Crypto 101 is an introductory course on cryptography, freely available for programmers of all ages and skill levels.Télécharger gratuit 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

- 15.51 MB
- 15

##### Vous recherchez le terme ""

151

58