# Cryptography Engineering

These are my notes on the book Cryptography Engineering by

Niels Ferguson, Bruce Schneier, Tadayoshi Kohno

Paperback: 384 pages

Publisher: John Wiley & Sons; March 2010

ISBN: 978-0470474242

“The world is full of bad security systems designed by people who have read

Applied Cryptography.”Cryptography Engineeringcould have the same effect.

## 1. The Context of Cryptography

Every system can be attacked. There is no such thing as perfect security. The whole point of a security system is to provide access to some people and not the others. *In the end, you will always have to trust some people in some way*, and these pople may still be able to attack your system.

When someone claims that they’ve secured a system against a generic attack, you know to be sceptical.

The best way to have confidence in building something secure is to keep it simple. Complexity is a measure of how many thing interact at any one point. To make a large, simple system you have to provide a very clear and simple interface between different parts of the system. Programmers call this modularization.

## 2. Introduction to Cryptography

**Kerchoffs’ Principle** The security of the encryption scheme must depend only on the secrecy of the key, and not on the secrecy of the algorithm.

With enough effort, any practical cryptographic system can be attacked successfully. The real question is how much work it takes to break a system.

## 3. Block Ciphers

**Ideal Block Cipher** For each key value, we want the block cipher to be a random permutation, and the different permutations for the different key values should be chosen independently.

A block cipher with a block size of $k$ bits specifies a permutation on $k$-bit output. The maximum key size (in bits) in this case is

For a security level of $n$ bits, every cryptographic value should be at least $2n$ bits long.

**Exercise 3.1** How much space would be required to store a table for an entire idealized block cipher that operates on $k$-bit blocks and that has $n$-bit keys?

**Exercise 3.2** DES. 64-bit block size; 16 rounds. 56-bit keys. How does 3DES work as a function of DES?

**Exercise 3.3** AES. 128-bit block size. Key length, rounds: (128, 10), (192, 12), (256, 14).

**Exercise 3.8** Using an existing cryptography library, decrypt the following ciphertext (in hex)

with the following 256-bit key (also in hex)

using AES.

Solution

```
$ echo "539B333B39706D149028CFE1D9D4A407" | xxd -r -p | openssl enc -aes256 -d -K "8000000000000000000000000000000000000000000000000000000000000001" -iv 0 -nopad | xxd
```

**Exercise 3.9** Using an existing cryptography library, encrypt the following plaintext (in hex)

with the following 256-bit key (also in hex)

using AES.

Solution

```
$ echo "296C93FDF499AAEB4194BABC2E63561D" | xxd -r -p | openssl enc -aes256 -e -K "8000000000000000000000000000000000000000000000000000000000000001" -iv 0 -nopad | xxd
```

**Exercise 3.10** Write a program that experimentally demonstrates the complementation property of DES.

Solution in Groovy

## 4. Block Cipher Modes

The encryption modes in this chapter are only designed to provide confidentiality against eavesdroppers; they do not stop the attacker from changing the data.

Any padding scheme is acceptable, as long as it is reversible.

In practice all padding rules add a minimum of one byte to the length of the plaintext.

An erroneous padding should be treated in the same manner as an authentication failure.

All block cipher modes leak some information.

The best you can do at this point is use CTR or CBC and limit the amount of data you process with any one key. We suggest limiting CBC encryption to $2^{32}$ blocks or so, and CTR encryption to $2^{60}$ blocks.

**Exercise 4.3** Suppose you, as an attacker, observe a 32-byte ciphertext $C$ and a 32-byte ciphertext $C’$. Suppose you know these ciphertexts were generated using CTR mode with the same nonce. The nonce is implicit, so it is not included in the ciphertext. You also know the plaintext $P$ corresponding to $C$. Then you can derive the plaintext $P’$ corresponding to $C’$

Verification in Groovy

**Exercise 4.4** Decrypt the ciphertext (in hex)

that was generated with 256-bit AES key (also in hex)

using CBC mode with a random IV. The IV is included at the beginning of the ciphertext.

Solution

```
$ echo "7C3D26F77377635A5E43E9B5CC5D05926E26FFC5220DC7D405F1708670E6E017" | xxd -r -p | openssl enc -aes-256-cbc -d -K "8000000000000000000000000000000000000000000000000000000000000001" -iv 87F348FF79B811AF3857D6718E5F0F91 -nopad | xxd
```

**Exercise 4.5** Encrypt the plaintext

using AES in ECB mode and the key

Answer

Solution

```
$ echo "626C6F636B2063697068657273202020686173682066756E6374696F6E732078626C6F636B2063697068657273202020" | xxd -r -p | openssl enc -aes-256-ecb -e -K "8000000000000000000000000000000000000000000000000000000000000001" -nopad | xxd
```

Do not ever use ECB for anything.

## 5. Hash Functions

The collision-resistance requirement merely states that, although collisions exist, they cannot be found.

Some might argue that all $n$-bit hash functions provide only $n/2$ bits of security.

**Exercise 5.1** Two blocks

and

produce an MD5 collision

```
$ echo "d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f8955ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5bd8823e3156348f5bae6dacd436c919c6dd53e2b487da03fd02396306d248cda0e99f33420f577ee8ce54b67080a80d1ec69821bcb6a8839396f9652b6ff72a70" | xxd -r | openssl dgst -md5
d41d8cd98f00b204e9800998ecf8427e
$ echo "d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f8955ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5bd8823e3156348f5bae6dacd436c919c6dd53e23487da03fd02396306d248cda0e99f33420f577ee8ce54b67080280d1ec69821bcb6a8839396f965ab6ff72a70" | xxd -r | openssl dgst -md5
d41d8cd98f00b204e9800998ecf8427e
```

**Exercise 5.2** Compute the SHA-512 hash value of the following message in hex:

Solution

```
$ echo "48656C6C6F2C20776F726C642E202020" | xxd -r | shasum -ba 512
cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e
```

**Exercise 5.3** Consider SHA-512-n, a hash function that first runs SHA-512 and then outputs only the first $n$ bits of the result. Write a program that uses a birthday attack to find and output a collision on SHA-512-n, where $n$ is a multiple of 8 between 8 and 48. Your program may use an existing cryptography library. Time how long your program takes when $n$ is 8, 16, 24, 32, 40, and 48, averaged over five runs for each $n$. How long would you expect your program to take for SHA-512-256? ($1.5\cdot 10^{26}$ years) For SHA-512-384? ($2.7\cdot 10^{45}$ years) For SHA-512 itself? ($5.0\cdot 10^{64}$ years)

Solution in Groovy.

Function | Colliding strings (in hex) | Hash (in hex) | Time |
---|---|---|---|

SHA-512-8 | `36` / `3130` |
`3C` |
68ms |

SHA-512-16 | `313035` / `333732` |
`03D2` |
62ms |

SHA-512-24 | `383938` / `36333138` |
`121165` |
157ms |

SHA-512-32 | `3134313833` / `3933363536` |
`2D83D66F` |
551ms |

SHA-512-40 | `343131323130` / `32343433363431` |
`5232228D80` |
15sec |

SHA-512-48 | `37383538363039` / `3132393635383233` |
`1A0922E4701D` |
233sec |

**Exercise 5.4** Let SHA-512-n be as in the previous exercise. Write a program that finds a message $M$ (a pre-image) that hashes to the following values.

Function | Hash (in hex) | Pre-image (in hex) | Time |
---|---|---|---|

SHA-512-8 | `A9` |
`323030` |
22ms |

SHA-512-16 | `3D4B` |
`3931313939` |
633ms |

SHA-512-24 | `3A7F27` |
`3130343632323237` |
2min |

SHA-512-32 | `C3C0357C` |
`32383732323933353533` |
3hr |

Solution in Groovy

How long would you expect a similar program to take for SHA-512-256? ($8.6\cdot 10^{63}$ years) For SHA-512-384? ($2.9\cdot 10^{102}$ years) For SHA-512 itself? ($9.9\cdot 10^{140}$ years)

**Section 5.2.1** Simple but insecure hash function.

Let $K$ be a 256-bit key set to all zeros. To hash the message $m$, first pad it in some way and break it into 128-bit blocks $m_1,…,m_k$. Set $H_0$ to a 128-bit block of all zeros. And now compute $H_i = AES_K(H_{i-1} \oplus m_i)$. Let $H_k$ be the result of the hash function.

Here’s a non-generic attack. Pick a message $m$ such that after padding it splits into two blocks $m_1$ and $m_2$. Let $H_1$ and $H_2$ denote the values computed as part of the hash function’s internal processing; $H_2$ is also the output of the hash function. Now let $m’_1 = m_2 \oplus H_1$ and let $m’_2 = H_2 \oplus m_2 \oplus H_1$, and let $m’$ be the message that splits into $m’_1$ and $m’_2$ after padding.

**Exercise 5.5** Show that both $m$ and $m’$ hash to $H_2$

## 6. Message Authentication Codes

One should never use the same key for both encryption and authentication.

**The Horton Principle** Authenticate what is meant, not what is said.

Whenever you do authentication, always think carefully about what other information shuold be included in the authentication.

**Exercise 6.2** Suppose $c$ is one block long, $a$ and $b$ are strings that are a multiple of the block length, and $M(a \parallel c) = M(b \parallel c)$. Here $M$ is CBC-MAC. Then $M(a \parallel d) = M(b \parallel d)$ for any block $d$.

**Exercise 6.3** Suppose $a$ and $b$ are both one block long, and suppose the sender MACs $a$, $b$, and $a \parallel b$ with CBC-MAC. An attacker who intercepts the MAC tags for these messages can now forge the MAC for the message $m = b \parallel (M(b) \oplus M(a) \oplus b)$, which the sender never sent. The forged tag for this message is equal to $M(a \parallel b)$, the tag for $a \parallel b$.

**Exercise 6.4** Suppose message $a$ is one block long. Suppose that an attacker has received the MAC $t$ for $a$ using CBC-MAC under some random key unknown to the attacker. Explain how to forge the MAC for a two-block message of your choice.

Answer

with the same MAC $t$

Example

```
$ echo 4d414373206172652076657279207573 | xxd -r -p | openssl enc -aes-256-cbc -e -K 8000000000000000000000000000000000000000000000000000000000000001 -nopad -iv 0 | xxd -p
e8e9a4ce5d20c4adf552b2c6382e124e
$ echo 4d414373206172652076657279207573a5a8e7bd7d41b6c8d524d7b4410e673d | xxd -r -p | openssl enc -aes-256-cbc -e -K 8000000000000000000000000000000000000000000000000000000000000001 -nopad -iv 0 | xxd -p -c 32 | cut -c 33-64
e8e9a4ce5d20c4adf552b2c6382e124e
```

**Exercise 6.5** Using an existing cryptography library, compute the MAC of the message

using CBC-MAC with AES and the 256-bit key

Answer

Solution

```
$ echo 4d4143732061726520766572792075736566756c20696e2063727970746f677261706879212020202020202020202020 | xxd -r -p | openssl enc -aes-256-cbc -e -K 8000000000000000000000000000000000000000000000000000000000000001 -nopad -iv 0 | xxd -p -c 48 | cut -c 65-96
```

**Exercise 6.6** Using an existing cryptography library, compute the MAC of the message

using HMAC with SHA-256 and the key

Answer

Solution

```
$ echo 4d4143732061726520766572792075736566756c20696e2063727970746f67726170687921 | xxd -r -p | openssl dgst -sha256 -mac HMAC -macopt hexkey:0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b0b
```

We can verify the answer using the definition of HMAC

```
$ echo 3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D3D36363636363636363636363636363636363636363636363636363636363636364d4143732061726520766572792075736566756c20696e2063727970746f67726170687921 | xxd -r -p | shasum -ba 256
7df010140cf808457a1dd8b0cb4a4a35a8708b77c8a27da4cab9fcb3f839e6f1
$ echo 57575757575757575757575757575757575757575757575757575757575757575C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C5C7df010140cf808457a1dd8b0cb4a4a35a8708b77c8a27da4cab9fcb3f839e6f1 | xxd -r -p | shasum -ba 256
be48c659ee041edc12af8d47960776189902e011b1c6a54056a5b10d9618fa4a
```

**Exercise 6.7** Using an existing cryptography library, compute the MAC of the message

using GMAC with AES and the 256-bit key

and the nonce

Answer for 128-bit tag

Solution in Groovy

## 7. The Secure Channel

**TODO:** Implement secure channel between Alice and Bob in Erlang.

**Exercise 7.1** In our design of a secure channel, we said that the message numbers must not repeat. What bad things can happen if the message numbers do repeat?

The same bad things can happen as in Exercise 4.3. Repeating message numbers means reusing the same key stream. Suppose an attacker observes two ciphertexts encoded for the same message number

Since the key streams for both ciphertexts where the same, the attacker can now compute the difference between them

Suppose the attacker knows the first message and its authentication tag

Now she can compute the second message and its authentication tag

**Exercise 7.3** Modify the algorithms for the secure channel in this chapter to use the dedicated, single-key mode for providing both encryption and authentication. You can use GCM as a black box.

## 8. Implementation Issues

**Standard implementation techniques are entirely inadequate to create secure code.**

Unless you are willing to put real effort into developing a secure implementation, there is little point in bothering with cryptography.

Many systems contain so-called optimizations that are useless, counterproductive, or insignificant because they do not optimize those parts of the system that form the bottleneck. We have become quite conservative about optimizations. Usually we don’t bother with them.

There are some programmers who implement assertion checking in development, but switch it off when they ship the product. This is not the security perspective.

Ideally, one programmer implements the module and a second programmer implements the tests. Both work from the functional specification. Any misunderstanding between the two is a clear indication that the specification have to be clarified.

The test code is about as big as the operational code, and we have not found a way fo significantly improving that.

Writing high-quality code takes about as long as writing low-quality code, if you count the time from start to finished product, rather than from start to first buggy version.

## 9. Generating Randomness

The more you know about a value, the smaller its entropy is.

Estimates of the amount of entropy per character in English text vary a bit, but are in the neighborhood of 1.5–2 bits per letter.

Generate 16 random bytes

```
dd if=/dev/urandom bs=16 count=1 2> /dev/null | xxd -p
```

Generate random base64 URL safe encoded string

```
dd if=/dev/urandom bs=32 count=1 2> /dev/null | base64 | tr "/+=" "_- "
```

**Exercise 9.1** Investigate the random number generators built into three of your favourite programming languages. Would you use these random number generators for cryptographic purposes?

JVM — yes; ERTS — yes; Racket — yes.

**Exercise 9.2** Using an existing cryptography library, write a short program that generates a 256-bit AES ket using a cryptographic PRNG.

where `bin`

module is defined here

**Exercise 9.5** Using a cryptographic PRNG that outputs a stream of bits, implement a random number generator that outputs random integers in the set $0, 1, …, n-1$ for any $n$ between $1$ and $2^{32}$.

**Exercise 9.6** Implement a naive approach for generating random numbers in the set 0,1,…,191. For this naive approach, generate a random 8-bit value, interpret that value as an integer, and reduce that value modulo 192. Experimentally generate a large number of random numbers in the set 0,1,…,191 and report on the distribution of results.

As expected, small numbers appear as twice as often as large numbers in the set

## 10. Primes

**Exercise 10.1** Implement Eratosthenes Sieve. What is the worst-case performance? $O(2^n)$. Generate a graph of the timings for $n=2,4,8,16,…,2^{20}$.

Solution in Erlang.

2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048 | 4096 | 8192 | 16384 | 32768 | 65536 | 131072 | 262144 | 524288 | 1048576 |

2 | 2 | 2 | 3 | 5 | 11 | 20 | 73 | 91 | 172 | 335 | 777 | 1729 | 3933 | 9073 | 25632 | 41719 | 108630 | 287291 | 679175 |

Here is the graph in logariphmic scale for $k=1,…,20$.

**Exercise 10.2** Compute 13635 + 16060 + 8190 + 21363 (mod 29101) in two ways and verify the equivalence: by reducing modulo 29101 after each addition and by computing the entire sum first and then reducing modulo 29101.

**Exercise 10.3** Compute the result of 12358 * 1854 * 14303 (mod 29101) in two ways and verify the equivalence: by reducing modulo 29101 after each multiplication and by computing the entire product first and then reducing modulo 29101.

**Exercise 10.4** Is {1,3,4} a subgroup of the multiplicative group of integers modulo 7? No, but {1,2,4} and {1,6} are.

**Exercise 10.5** GCD(91261, 117035) = 263.

**Exercise 10.6** 74$^{-1}$ (mod 167) = 79.

**Exercise 10.7** Generate few primes within the range $l=2^{255}$ and $u=2^{256}-1$.

```
97930216791462598045972883206226108036297956314017330320914377792388523022969
81584374835399266544251931666118226996961716105131490897360674548913013941917
67817200436541682412601222897087873297429605953843518229574841130195287660929
```

Solution in Erlang

Long prime

```
44129837063770165553832059107682306619738412373949690544924694569657334347697318
89282384595223880473291549477607931396621136675427472767457004072458644693312251
85702178678741261775298175549211893240790465679089929528914498139387782873637685
80666645668381134591441541906590131473893822013775159412354495643526549278176367
16420639243316759189536141159464748559796000728199658803151427159954563483308188
14969131978928808655813172004950285866534577393792532435966009786326519840221560
87609143247862022593121169632248770931444531492919464625476888424016012399968184
999766493587299104952314827482039660243903052554035019917
```

**Exercise 10.9** Compute 27$^{35}$ (mod 569).

Performed 15 multiplications.

## 11. Diffie-Hellman

**Fermat’s Little Theorem** If $p$ is a prime number, then $\forall a \in [1,2,…,p-1] \quad a^{p-1} = 1 \; (\mod p)$.

**Theorem 11.3** $p=2q + 1$, $p$ is a prime number, then $r$ is a square modulo $p$ $\Leftrightarrow$ $r^q = 1 \; (\mod p)$.

*Necessity*: $r = s^2 \Rightarrow r^q = s^{2q} = s^{p-1} = 1 \; (\mod p)$ by FLT.

*Sufficiency*: Suppose $\nexists s \in [1,…,p-1]$ such that $r = s^2$. Then $\nexists s \in [1,…,p-1]$ such that $r^q = s^{2q} = s^{p-1} = 1 \; (\mod p)$, which contradicts FLT.

## 12. RSA

Generate RSA private key using OpenSSL

```
openssl genrsa -out private.pem 2048
openssl asn1parse -i -in private.pem
```

The key consists of the follwing components

Extract RSA public key from the private key

```
openssl rsa -in private.pem -pubout
```

Convert RSA public key between PKIX and PKCS#1 formats

```
openssl rsa -pubin -in public.pem -RSAPublicKey_out
openssl rsa -RSAPublicKey_in -in pkcs1-public.pem -pubout
```

RSA implementation in Erlang.

**Exercise 12.1** Let p = 89, q = 107, n = pq, a = 3, and b = 5. Find x in $\mathbb{Z}_n$ such that a = x (mod p) and b = x (mod q). Anser: 8458.

**Exercise 12.2** Let p = 89, q = 107, n = pq, x = 1796, and y = 8931. Compute x + y (mod n) directly. Compute x + y (mod n) using CRT representations. Answer: 1204.

**Exercise 12.3** Let p = 89, q = 107, n = pq, x = 1796, and y = 8931. Compute xy (mod n) directly. Compute xy (mod n) using CRT representations. Answer: 3344.

**Exercise 12.4** Let p = 83, q = 101, n = pq, and e = 3. Is (n,e) a valid RSA public key? If so, compute the corresponding private RSA key d.

**Exercise 12.5** Let p = 79, q = 89, n = pq, and e = 3. Is (n,e) a valid RSA public key? No, because t and e are not relatively prime, d does not exist.

**Exercise 12.8** Let p = 71, q = 89, n = pq, and e = 3. First find d: 1027. Then compute the signature on $m_1 = 5416, m_2 = 2397$, and $m_3 = m_1 m_2 (\mod n)$ using the basic RSA operation: 923, 2592, 5086. Show that the third signature is equivalent to the product of the first two signatures.

What does *equivalent* mean here? $\sigma_1 \sigma_2 (\mod n) = 3834$ is obviously not the same as $\sigma_3$.

OpenSSL failed to show it

```
$ echo '1528' | xxd -r -p | openssl dgst -sha256 -sign my.pem -hex
Error Signing Data
140736496063496:error:04075070:rsa routines:RSA_sign:digest too big for rsa key:rsa_sign.c:122:
```

## 13. Introduction to Cryptographic Protocols

The question “Do you trust him?” is incomplete. It should be “Do you trust him with X?”

We talk about trust when we design protocols. Always keep in mind that business people think and talk in terms of risks. You’ll have to convert between the two perspectives if you want to be able to talk to them.

The function of cryptographic protocols is to minimize the amount of trust required.

## 14. Key Negotiation

Every time a party sends an authentication, the authentication data consist of *all* the data exchanged so far: *all* the previous messages, and *all* the data fields that precede the authentication in the authenticator’s message.

Be very careful with protocol complexity. There are no good modularization notations for protocols, so everything ends up being mixed together.

## 20. PKI

**Create**

Create a new key and a self-signed certificate

```
openssl req -x509 -newkey rsa:2048 -sha256 -keyout key.pem -out certificate.pem -days 730 -subj "/C=CA/ST=Ontario/L=Toronto/O=NDPAR INC./OU=IT/CN=www.ndpar.org"
```

**Inspect**

Print first certificate in the file

```
openssl x509 -in certificate.pem -noout -text
```

Print specific fields of the certificate

```
openssl x509 -in certificate.pem -noout -issuer -startdate -enddate
openssl x509 -in certificate.pem -noout -pubkey
```

Print all certificates in the file using `openssl`

or `keytool`

```
openssl crl2pkcs7 -nocrl -certfile certificates.pem | openssl pkcs7 -print_certs -text -noout
keytool -printcert -v -file certificates.pem
```

Example: Origins of root certificates on macOS 10.12.6

```
openssl crl2pkcs7 -nocrl -certfile certificates.pem | openssl pkcs7 -print_certs -text -noout | grep 'Issuer:' | grep -oP '(?<=C=)[a-zA-Z]{2}' | tr [a-z] [A-Z] | sort | uniq -c
```

2 BE, 6 BM (Bermuda), 1 CA, 12 CH, 3 CN, 1 CZ, 6 DE, 1 DK, 1 EE, 4 ES, 4 EU, 3 FI, 4 FR, 5 GB, 1 GR, 1 HK, 2 HU, 1 IE, 6 IL, 1 IT, 4 JP, 1 KR, 3 NL, 2 NO, 4 PL, 1 RO, 2 SE, 2 SK, 1 TR, 4 TW, 63 US, 1 VE (Venezuela)

## 22. Standards and Patents

The political structure of the committee puts very little emphasis on creating a good technical standard. The most important thing is to reach consensus. The standard is finished when everybody is equally *unhappy* with the result.

Many standards are internally inconsistent, or even contradict themselves.

For reasons of simplicity and consistency, which are crucial to the overall security, a security system must be designed by a small group of experts.