9781466570269 download pdf

This practical guide to modern encryption breaks down the fundamental mathematical concepts at the heart of cryptography. Table of contents : Content: Preface -- I. Now the most used texbook for introductory cryptography courses in both mathematics and computer science, the Third Edit.

Cryptography is a key technology in electronic key systems. It is used to keep data secret, digitally sign documents, ac. Home Introduction to Modern Cryptography [2 ed. Introduction to Modern Cryptography [2 ed. For example, P can be a text document, and F can be the modification of part of the text. The first FHE scheme was created in , and since then more efficient variants appeared, but it remains unclear whether FHE will ever be fast enough to be useful.

Searchable Encryption Searchable encryption enables searching over an encrypted database without leaking the searched terms by encrypting the search query itself. Like fully homomorphic encryption, searchable encryption could enhance the privacy of many cloud-based applications by hiding your searches from your cloud provider.

As of this writing, however, searchable encryption remains experimental within the research community. Tweakable Encryption Tweakable encryption TE is similar to basic encryption, except for an additional parameter called the tweak, which aims to simulate different versions of a cipher see Figure However, TE is not bound to a single application and is a lowerlevel type of encryption used to build other schemes, such as authentication encryption modes.

Figure Tweakable encryption In disk encryption, TE encrypts the content of storage devices such as hard drives or solid-state drives. To make encryption unpredictable, TE uses a tweak value that depends on the position of the data encrypted, which is usually a sector number or a block index.

How Things Can Go Wrong Encryption algorithms or implementations thereof can fail to protect confidentiality in many ways. Weak Cipher Our first example concerns ciphers that can be attacked using cryptanalysis techniques, as occurred with the 2G mobile communication standard. Telecommunication operators had to find workarounds to prevent the attack.

Furthermore, the attack is a time-memory trade-off TMTO , a type of method that first runs computations for days or weeks in order to build large look-up tables, which are subsequently used for the actual attack. Wrong Model The next example concerns an invalid attack model that overlooked some side channels. Many communication protocols that use encryption ensure that they use ciphers considered secure in the CPA or CCA model.

They simply need validity queries to tell whether a ciphertext is valid, and these queries are usually sent to the system responsible for decrypting ciphertexts. Padding oracle attacks are an example of such attacks, wherein an attacker learns whether a ciphertext conforms to the required format. Specifically, in the case of padding oracle attacks, a ciphertext is valid only if its plaintext has the proper padding, a sequence of bytes appended to the plaintext to simplify encryption.

Decryption fails if the padding is incorrect, and attackers can often detect decryption failures and attempt to exploit them. For example, the presence of the Java exception javax. BadPaddingException would indicate that an incorrect padding was observed. In , researchers found padding oracle attacks in several web application servers.

The validity queries consisted of sending a ciphertext to some system and observing whether it threw an error. Thanks to these queries, they could decrypt otherwise secure ciphertexts without knowing the key.

Further Reading We discuss encryption and its various forms in more detail throughout this book, especially how modern, secure ciphers work. There are also many more types of encryption than those presented in this chapter, including attribute-based encryption, broadcast encryption, functional encryption, identity-based encryption, message-locked encryption, and proxy re-encryption, to cite but a few.

Without randomness, cryptography would be impossible because all operations would become predictable, and therefore insecure. This chapter introduces you to the concept of randomness in the context of cryptography and its applications. We discuss pseudorandom number generators and how operating systems can produce reliable randomness, and we conclude with real examples showing how flawed randomness can impact security.

Random or Non-Random? What do random bits look like? The value looks more random than because it has the signs typical of a randomly generated value. That is, has no obvious pattern. When we see the string , our brain registers that it has about as many zeros three as it does ones five , just like 55 other 8-bit strings , , , and so on , but only one 8-bit string has eight zeros. This example illustrates two types of errors people often make when identifying randomness: Mistaking non-randomness for randomness Thinking that an object was randomly generated simply because it looks random.

Mistaking randomness for non-randomness Thinking that patterns appearing by chance are there for a reason other than chance. The distinction between random-looking and actually random is crucial. Indeed, in crypto, non-randomness is often synonymous with insecurity. Randomness as a Probability Distribution Any randomized process is characterized by a probability distribution, which gives all there is to know about the randomness of the process.

A probability distribution, or simply distribution, lists the outcomes of a randomized process where each outcome is assigned a probability.

A probability measures the likelihood of an event occurring. A probability distribution must include all possible outcomes, such that the sum of all probabilities is 1. A uniform distribution occurs when all probabilities in the distribution are equal, meaning that all outcomes are equally likely to occur. Entropy: A Measure of Uncertainty Entropy is the measure of uncertainty, or disorder in a system.

You might think of entropy as the amount of surprise found in the result of a randomized process: the higher the entropy, the less the certainty found in the result. We can compute the entropy of a probability distribution. Unlike the natural logarithm, the binary logarithm expresses the information in bits and yields integer values when probabilities are powers of two.

Entropy is maximized when the distribution is uniform because a uniform distribution maximizes uncertainty: no outcome is more likely than the others. By the same token, when the distribution is not uniform, entropy is lower. Consider the coin toss example. NOTE Entropy can also be viewed as a measure of information. In the case of the unfair coin toss, you know in advance that tails is more probable, so you can usually predict the outcome of the toss.

The result of the coin toss gives you the information needed to predict the result with certainty. The job of this component is to return random bits when requested to do so. How is this randomness generation done? A cryptographic algorithm to produce high-quality random bits from the source of entropy.

This is found in pseudorandom number generators PRNGs. Randomness comes from the environment, which is analog, chaotic, uncertain, and hence unpredictable. In cryptography, randomness usually comes from random number generators RNGs , which are software or hardware components that leverage entropy in the analog world to produce unpredictable bits in a digital system. For example, an RNG might directly sample bits from measurements of temperature, acoustic noise, air turbulence, or electrical static.

Such system- and human-generated activities can be a good source of entropy, but they can be fragile and manipulated by an attacker. These can provide real randomness, rather than just apparent randomness. Pseudorandom number generators PRNGs address the challenge we face in generating randomness by reliably producing many artificial random bits from a few true random bits.

For example, an RNG that translates mouse movements to random bits would stop working if you stop moving the mouse, whereas a PRNG always returns pseudorandom bits when requested to do so.

PRNGs rely on RNGs but behave differently: RNGs produce true random bits relatively slowly from analog sources, in a nondeterministic way, and with no guarantee of high entropy. In contrast, PRNGs produce random-looking bits quickly from digital sources, in a deterministic way, and with maximum entropy. Essentially, PRNGs transform a few unreliable random bits into a long stream of reliable pseudorandom bits suitable for crypto applications, as shown in Figure In order to generate pseudorandom bits, the PRNG runs a deterministic random bit generator DRBG algorithm that expands some bits from the entropy pool into a much longer sequence.

As its name suggests, a DRBG is deterministic, not randomized: given one input you will always get the same output. In the course of its work, the PRNG performs three operations, as follows: init Initializes the entropy pool and the internal state of the PRNG refresh R Updates the entropy pool using some data, R, usually sourced from an RNG next N Returns N pseudorandom bits and updates the entropy pool The init operation resets the PRNG to a fresh state, reinitializes the entropy pool to some default value, and initializes any variables or memory buffers used by the PRNG to carry out the refresh and next operations.

The refresh operation is often called reseeding, and its argument R is called a seed. When no RNG is available, seeds may be unique values hardcoded in a system. The refresh operation is typically called by the operating system, whereas next is typically called or requested by applications. The next operation runs the DRBG and modifies the entropy pool to ensure that the next call will yield different pseudorandom bits.

Specifically, PRNGs should guarantee backtracking resistance and prediction resistance. Backtracking resistance also called forward secrecy means that previously generated bits are impossible to recover, whereas prediction resistance backward secrecy means that future bits should be impossible to predict. To achieve prediction resistance, the PRNG should call refresh regularly with R values that are unknown to an attacker and that are difficult to guess, thus preventing an attacker from determining future values of the entropy pool, even if the whole pool is compromised.

A key, K, and a counter, C both 16 bytes. The system chooses the RNGs used to produce R values, and it should call refresh regularly. The N bits requested are then produced by encrypting C using K as a key. For one thing, you need to get all the details of the algorithm right—namely, how entropy pools are chosen, the type of cipher to be used in next, how to behave when no entropy is received, and so on.

Even if Fortuna is correctly implemented, security failures may occur for reasons other than the use of an incorrect algorithm. For example, Fortuna might not notice if the RNGs fail to produce enough random bits, and as a result Fortuna will produce lower-quality pseudorandom bits, or it may stop delivering pseudorandom bits altogether. Another risk inherent in Fortuna implementations lies in the possibility of exposing associated seed files to attackers.

However, if an identical seed file is used twice, then Fortuna will produce the same bit sequence twice. Finally, if two Fortuna instances are in the same state because they are sharing a seed file meaning they are sharing the same data in the entropy pools, including the same C and K , then the next operation will return the same bits in both instances.

Cryptographic vs. Non-crypto PRNGs are designed to produce uniform distributions for applications such as scientific simulations or video games. Defaulting to a non-crypto PRNG is a recipe for disaster because it often ends up being used in crypto applications, so be sure to use only crypto PRNGs in crypto applications. Notice in this equation that bits of S interact with each other only through XORs.

The converse is also true: bits from the initial state can be expressed as an XOR of output bits. Although linear combinations of those bits include at most variables, nonlinear combinations allow for up to variables. It would be impossible to solve, let alone write down the whole of these equations. Note that , a much smaller number, is the estimated information capacity of the observable universe. The key here is that linear transformations lead to short equations comparable in size to the number of variables , which are easy to solve, whereas nonlinear transformations give rise to equations of exponential size, which are practically unsolvable.

The game of cryptographers is thus to design PRNG algorithms that emulate such complex nonlinear transformations using only a small number of simple operations. NOTE Linearity is just one of many security criteria. Although necessary, nonlinearity alone does not make a PRNG cryptographically secure.

These tests take a sample of pseudorandom bits produced by a PRNG say, one megabyte worth , compute some statistics on the distribution of certain patterns in the bits, and compare the results with the typical results obtained for a perfect, uniform distribution.

For example, some tests count the number of 1 bits versus the number of 0 bits, or the distribution of 8-bit patterns. When you run statistical tests on randomly generated data, you will usually see a bunch of statistical indicators as a result.

These are typically pvalues, a common statistical indicator. Most of these PRNGs are software based, but some are pure hardware. When running the script, notice how user activity accelerates entropy recovery bytes read are printed to stdout encoded in base Guess when I started randomly moving the mouse and hitting the keyboard to gather entropy.

Spoiler: it does not. As is usually the case in Windows, the process is complicated. For instance, the final version of the TrueCrypt encryption software was found to call CryptAcquireContext in a way that could silently fail, leading to suboptimal randomness without notifying the user.

In hardware engineering terms, this entropy source is a dual differential jamb latch with feedback; essentially, a small hardware circuit that jumps between two states 0 or 1 depending on thermal noise fluctuations, at a frequency of MHz.

This kind of thing is usually pretty reliable. When invoked, RDRAND sets the carry flag to 1 if the data set in the destination register is a valid random value, and to 0 otherwise, which means you should be sure to check the CF flag if you write assembly code directly. Assuming that you can guess the value of seconds, microseconds has only possible values and thus an entropy of log , or about 20 bits.

PRNGs in different systems ended up producing identical random bits due to a same base entropy source for example, a hardcoded seed. At a high level, the presence of identical keys is due to key-generation schemes like the following, in pseudocode: prng.

The presence of shared primes in different keys is due to key-generation schemes where additional entropy is injected during the process, as shown here: prng. Alas, many systems overlook that detail, so I thought I should give you at least one such example.

The popular MediaWiki application runs on Wikipedia and many other wikis. It uses randomness to generate things like security tokens and temporary passwords, which of course should be unpredictable. Look for the function called to get a random bit, and be sure to read the comments. In , researchers showed how to exploit the predictability of Mersenne Twister to predict future tokens and temporary passwords, given a couple of security tokens. The chat program Cryptocat was designed to offer secure communication.

It used a function that attempted to create a uniformly distributed string of decimal digits—namely, numbers in the range 0 through 9. Cryptocat did the following to address that problem and obtain a uniform distribution: Cryptocat. Other SHA-2 Algorithms The SHA-2 family includes SHA, which is algorithmically identical to SHA except that its initial value is a different set of eight bit words, and its hash value length is bits, instead of bits, and is taken as the first bits of the final chaining value.

As a result, it uses bit chaining values eight 64bit words and ingests bit message blocks sixteen bit words , and it makes 80 rounds instead of The compression function is otherwise almost the same as that of SHA, though with different rotation distances to cope with the wider word size. Security-wise, all four SHA-2 versions have lived up to their promises so far: SHA guarantees bit preimage resistance, SHA guarantees about bit collision resistance, and so on.

As I write this, though, we have yet to see a successful attack on SHA Of these 64 submissions, 51 matched the requirements and entered the first round of the competition. During the first weeks of the competition, cryptanalysts mercilessly attacked the submissions. JH A tweaked sponge function construction wherein message blocks are injected before and after the permutation rather than just before.

The permutation also performs operations similar to a substitution— permutation block cipher as discussed in Chapter 4. JH was designed by a cryptographer from a university in Singapore. Keccak A sponge function whose permutation performs only bitwise operations. Keccak was designed by a team of four cryptographers working for a semiconductor company based in Belgium and Italy, and included one of the two designers of AES.

Skein was designed by a team of eight cryptographers from academia and industry, all but one of whom is based in the US, including the renowned Bruce Schneier. Another reason is that Keccak is more than just a hash. These two algorithms are extendable-output functions XOFs , or hash functions that can produce hashes of variable length, even very long ones.

The numbers and represent the security level of each algorithm. These ANDs are the only nonlinear operations in Keccak, and they bring with them cryptographic strength. These operations provide SHA-3 with a strong permutation algorithm free of any bias or exploitable structure.

SHA-3 is the product of more than a decade of research, and hundreds of skilled cryptanalysts have failed to break it. It should be faster than all previous hash standards, including MD5. It should be suited for use in modern applications, and able to hash large amounts of data either as a few large messages or many small ones, with or without a secret key.

It should be suited for use on modern CPUs supporting parallel computing on multicore systems as well as instruction-level parallelism within a single core. BLAKE2s, optimized for 8- to bit platforms, can produce digests ranging from 1 to 32 bytes.

Each function has a parallel variant that can leverage multiple CPU cores. The two halves of the state are XORed together after the block cipher. How Things Can Go Wrong Despite their apparent simplicity, hash functions can cause major security troubles when used at the wrong place or in the wrong way—for example, when weak checksum algorithms like CRCs are used instead of a crypto hash to check file integrity in applications transmitting data over a network.

However, this weakness pales in comparison to some others, which can cause total compromise in seemingly secure hash functions. Unfortunately, SHA-2 hash functions are vulnerable to the length-extension attack, even though the NSA designed the functions and NIST standardized them while both were well aware of the flaw.

This flaw could have been avoided simply by making the last compression function call different from all others for example, by taking a 1 bit as an extra parameter while the previous calls take a 0 bit. The client picks a random value, C, as a challenge. The server computes Hash M C as a response and sends the result to the client.

The client also computes Hash M C and checks that it matches the value received from the server. It then records H1 in memory and discards M, at which point it no longer stores M.

Now when the client sends a random value, C, the server computes Compress H1, C , after adding the padding to C to fill a complete block, and returns the result as Hash M C. To learn more about the theoretical security notions that underpin preimage resistance and collision resistance, as well as length-extension attacks, search for indifferentiability.

For more recent research on hash functions, see the archives of the SHA-3 competition, which include all the different algorithms and how they were broken. Last but not least, research these two real exploitations of weak hash functions: The nation-state malware Flame exploited an MD5 collision to make a counterfeit certificate and appear to be a legitimate piece of software.

The Xbox game console used a weak block cipher called TEA to build a hash function, which was exploited to hack the console and run arbitrary code on it. Keyed hashing forms the basis of two types of important cryptographic algorithms: message authentication codes MACs , which authenticate a message and protect its integrity, and pseudorandom functions PRFs , which produce random-looking hash-sized values. Some MACs and PRFs are based on hash functions, some are based on block ciphers, and still others are original designs.

Upon receiving the message and its authentication tag, Bill recomputes MAC K, M and checks that it is equal to the authentication tag received. Not all communication systems use MACs. Sometimes an authentication tag can add unacceptable overhead to each packet, typically in the range of 64 to bits. Thus, if an attacker damages an encrypted voice packet, it will decrypt to noise, which would sound like static. First of all, as with a cipher, the secret key should remain secret.

The security notion that posits that forgeries should be impossible to find is called unforgeability. Obviously, it should be impossible to recover the secret key from a list of tags; otherwise, attackers could forge tags using the key. What can an attacker do to break a MAC? The most basic model is the known-message attack, which passively collects messages and their associated tags for example, by eavesdropping on a network. But real attackers often launch more powerful attacks because they can often choose the messages to be authenticated, and therefore get the MAC of the message they want.

The standard model is therefore that of chosen-message attacks, wherein attackers get tags for messages of their choice. To prevent such replay attacks, protocols include a message number in each message. This number is incremented for each new message and authenticated along with the message.

The receiving party gets messages numbered 1, 2, 3, 4, and so on. Because the key is secret, the output values are unpredictable to an attacker. Key derivation schemes use PRFs to generate cryptographic keys from a master key or a password, and identification schemes use PRFs to generate a response from a random challenge.

PRF Security In order to be secure, a pseudorandom function should have no pattern that sets its outputs apart from truly random values. The erudite phrase for that security notion is indistinguishability from a random function.

Creating Keyed Hashes from Unkeyed Hashes Throughout the history of cryptography, MACs and PRFs have rarely been designed from scratch but rather have been built from existing algorithms, usually hash functions of block ciphers. Insecurity Against Length-Extension Attacks Recall from Chapter 6 that hash functions of the SHA-2 family allow attackers to compute the hash of a partially unknown message when given a hash of a shorter version of that message.

The ability to thwart length-extension attacks was mandatory for SHA-3 submissions. Insecurity with Different Key Lengths The secret-prefix construction is also insecure when it allows the use of keys of different lengths. Therefore, the result of the secret-prefix construction Hash K M will be the same for both keys. The Secret-Suffix Construction Instead of hashing the key before the message as in the secret-prefix construction, we can hash it after.

Putting the key at the end makes quite a difference. However, the secret-suffix construction is weaker against another type of attack. To exploit this property, an attacker would: 1. Find two colliding messages, M1 and M2 2. The key, K, is usually shorter than one block that is filled with 00 bytes and XORed with opad. The resulting block is the first block processed by the inner call to Hash—namely, the rightmost Hash in the equation, or the top hash in Figure Recall the birthday attack from Chapter 6.