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 Engineering could 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
$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

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\Leftrightarrowr^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.