- Introduction
- Ciphers
- Message Authentication Codes (MACs)
- Authenticated Encryption
- Key Exchange
- Public key encryption
This is a document containing basic principles and constructs for cryptography engineering, summarised from the Coursera course "Cryptography I". It can be used to either get a quick introduction & overview of the field or recollect basic principles you've already seen.
The 3 main steps in cryptography are:
- Specify precisely a threat model.
- Propose a construct.
- Prove that breaking this construct is impossible under the current threat model, usually by reducing to a problem that is known to be computationally hard.
Creating this formal proof is difficult. As a result, if there is one thing to know about cryptography it's the following:
Do not invent your own cryptography algorithm! Use standard algorithms and constructs that have been proven to be secure!
One of the most basic mechanisms to break a cipher is by leveraging known patterns in the message space. A trivial example is leveraging the known frequency of letters in the english alphabet to infer the key that is used for encrypting messages. Some historical examples are: the Caesar cipher, the Vigener cipher and rotor machines, such as the Enigma machine.
The XOR operator has the following important property:
- If
Yis a random variable with an unknown distribution over {0, 1}N. - If
Xis an independent variable with a uniform distribution in {0, 1}N. - Then
Z = X XOR Yis a variable with a uniform distribution in {0, 1}N.
This means that any underlying patterns in variable Y are removed when it's XOR'ed with a uniformly distributed variable X. This is the reason the XOR operator forms the basis for many cryptographic constructs.
A cipher defined over (K, M, E) is a pair of "efficient" algorithms (E, D) where
E: K x M -> Cis an encryption function and is often randomizedD: K x C -> Eis a decryption function and is always deterministic
The one-time pad (OTP) is the simplest example of a "secure" cipher, it's simply using the XOR operator:
E(k, m) = k XOR mD(k, c) = k XOR c
It's not easy to use in practice, because the key needs to be of the same size as the message to be encrypted.
There are various different definitions of security. One of these based on Information Theory is called perfect secrecy, which essentially defines that the ciphertext does not reveal any information at all about the plaintext. A cipher (E, D) over (K, M, C) has perfect secrecy if:
- For each m0, m1 in M, where len(m0) = len(m1) and
- For each c in C
- Pr[E(k, m0) = c] = Pr[E(k, m1) = c], where k is uniformly distributed in K
The one-time pad has perfect secrecy by definition thanks to the aforementioned property of XOR. However, it's been proved that perfect secrecy requires a key size at least equal or larger than the message size (|K| >= |M|). As a result, any algorithm having perfect secrecy is expected to be hard to use in practice, so there are alternative definitions of security that are used.
In order to create more practical ciphers, the main idea is to replace the "random" key by a "pseudorandom" key. To do this, a pseudorandom generator (PRG) is used, which is a deterministic function that expands a key from a small space to a much larger space: G: {0, 1}s -> {0, 1}n, where n >> s
Leveraging a PRG, we can use a small key, expand it to the message's size and then perform an XOR operation (as in the one-time pad):
C(k, m) = m XOR G(k)D(k, c) = c XOR G(k)
Note that these kind of stream ciphers cannot have perfect secrecy, so we need a different definition of security. The security of the cipher will essentially be derived from the underlying PRG. So, a stream cipher will be secure iff the underlying PRG is secure.
Here are some simplified properties of PRGs:
- A PRG is secure iff its output is indistinguishable from a random distribution.
- A PRG is unpredictable iff for each i, there is no "efficient" adversary that can predict bit (i+1) for non-negligible probability.
- It's been proven that a PRG is secure iff it's unpredictable.
An alternative definition of security for ciphers is the semantic security, which is defined in the following way. The challenger is a party making use of the cipher and the adversary interacting with the challenger via the cipher and trying to break it. The adversary provides 2 different messages of the same size m0, m1 for encryption to the challenger that can operate in one of 2 modes, b0 and b1. In b0, the challenger returns the encryption of m0, while in b1, the challenger returns the encryption of m1. A cipher is semantically secure iff the adversary cannot predict which mode the challenger is in with non-negligible probability. As a result, if the ciphertext reveals even a small amount of information about the plaintext, this information can be leveraged from the adversary to identify the current mode of the challenger.
As it was implied above, stream ciphers that use a secure PRG are semantically secure.
Notes:
- Never use a stream cipher key more than once!! That's called a two-time pad and it's insecure.
- Avoid using related keys.
- A stream cipher does not provide any integrity. The ciphertext can be modified with predictable changes in the plaintext and without being detected.
Contrary to stream ciphers, block ciphers operate on fixed-length groups of bits, called blocks. The key size does not have to be the same as the message size.
Most block cipher algorithms are classified as iterated block ciphers which means that they transform fixed-size blocks of plaintext into identical size blocks of ciphertext, via the repeated application of an invertible transformation known as the round function, with each iteration referred to as a round. Usually, the round function R takes different round keys Ki as second input, which are derived from the original key, using a method called key expansion. Because of this iterative nature, they tend to be slower than stream ciphers.
Block ciphers make use of 2 basic mathematical constructs, pseudo-random functions (PRFs) and pseudo-random permutations (PRPs):
- A PRF is defined over (K, X, Y),
F: K x X -> Y, such that there exists an efficient algorithm to calculateF(k,x) - A PRP is defined over (K, X),
E: K x X -> X, such that- there exists an efficient algorithm to calculate
E(k,x) - The function
E(k, .)is one-to-one - There exists an efficient inversion algorithm
D(k, x)
- there exists an efficient algorithm to calculate
Note the following:
- Functionally, any PRP is also a PRF.
- A PRP is a PRF, where X = Y and is efficiently invertible.
The security of PRFs and PRPs is also established on the notion of randomness. Let's assume Funs[X, Y] the set of all functions from X to Y and SF = { F(k, .) s.t. k in K}, which is a subset of Funs[X, Y]. The PRF F is then secure iff a random function in Funs[X, Y] is indistinguishable from a random function in SF. The same logic applies for the security of PRPs.
One type of iterated block ciphers is known as a substitution-permutation network, which performs several alternating rounds of a substitution stage (called S-box) followed by a permutation stage (called P-box). These opeations must have specific properties to ensure security. For instance, S-boxes should not be linear, i.e. no output bit should be a linear function of the input bits. AES is an example of a substitution-permutation network.
A different type of iterated block cipher is known as a Feistel network. In this type, each block of plain text is split into two halves, the round function is applied to one half, using a subkey, and then the output is XORed with the other half. The two halves are then swapped. 3-DES is an example of a Feistel network.
It's been proven (Luby-Rackoff theorem '85) that if the round function F is a secure PRF, then a 3-round Feistel network is a secure PRP.
Also, starting from a PRG, we can actually build secure PRFs (see GGM PRF). As a result, we can also build a secure PRP (and thus block cipher) from a secure PRG.
Some of the attacks on ciphers are the following:
- Exhaustive search (brute-force) attacks. The key size of each cipher must be selected in such a way that these attacks are computationally extremely hard to perform.
- Side-channel attacks. The code should behave the same way under all the possible conditions, so that the attacker cannot get information from environmental conditions, such as execution time, device temperature etc. This implies that even if you use a standardised protocol, your implementation might be broken, so you should use crypto primitives provided by libraries as much as possible.
- Linear and differential attacks, where the attacker can leverage given input/output pairs to identify useful relations and recover the key in much smaller time than with an exhaustive search. This is why it's important for ciphers to not have any linearity at all and appear to be fully random permutations.
- Quantum exhaustive search attacks, which can only become feasible with the development of quantum computers.
A block cipher by itself allows encryption only of a single data block of the plaintext. In order to encrypt multiple blocks (the whole text), each cipher can be used in different ways, which are called modes of operation. In these modes, the same key might be used for multiple blocks (and in some cases even for multiple messages). Note that using a secure block cipher in an insecure mode makes the whole encryption insecure! For example, the Electronic Code Book (ECB) mode is one of the notoriously insecure modes, because equal plaintext blocks will generate equal ciphertext blocks, thus making patterns in the plaintext evident in the ciphertext as well. The main idea is to use some additional source of randomness to create what is called probabilistic encryption, so that when encrypting the same blocks of plaintext several times it will, in general, yield different blocks of ciphertexts. Some of the secure modes following this approach are the following:
- The cipher-block chaining (CBC) mode selects a random initialization vector (IV), which is added in an XOR manner to the first plaintext block before it is being encrypted. The resultant ciphertext block is then used as the new initialization vector for the next plaintext block.
- The counter (CTR) mode makes use of a unique (but not necessarily random) initialization vector. The needed randomness is derived internally by using the initialization vector as a block counter and encrypting this counter for each block.
In general, there are 2 ways to use a block cipher:
- using a one-time key, where a different key is used for each message.
- using a many-time key, where the same key is used for multiple messages.
The initial description of semantic security covers the one-time key, where the attacker essentially has the capability of submitting a single message in the attempt to break the cipher. However, when a many-time key is used, the attacker is much more powerful, since the attacker can now see many ciphertexts with the same key. As a result, the notion of semantic security for many-time keys is slightly extended in the following way: the adversary can submit i pairs of messages (mi,0, mi,1), receiving the ciphertext of one of them (ci = E(k, mi,b) depending on the challenger's mode (b) and then attempting to predict the challenger's mode with significant probability. This is referred to as a chosen-plaintext attack (CPA) and protocols that are secure against this kind of attack are called CPA-secure.
Message Authentication Codes are used to guarantee integrity, not confidentiality.
A MAC I = (S, V) defined over (K, M, T) is a pair of algorithms:
S(k, m) = tis the signing algorithm generating a tag t for a messageV(k, m, t) = yes/nois the verifying algorithm verifying whether t is a valid tag for a message
A MAC is secure iff an attacker when given a valid pair (m, t) cannot produce another valid pair (m', t'), unless m' = m and t' = t. This is called existential forgery.
A MAC can be built using a PRF F: K x YX -> Y in the following way:
S(k, m) = F(k, m)V(k, m, t) = (F(k, m) == t)
It can be proved that the MAC will be secure iff the PRF is secure, as long as |Y| is large (say 280). This is so that potential attackers cannot just "guess" the tag.
So, there are MACs built out of block ciphers (e.g. CBC-MAC) or hash functions (e.g. HMAC).
So far, we've seen:
- encryption schemes that are secure against CPA attacks. These provide confidentiality and they are secure against eavesdropping, but not secure against active attacks (where the attacker can tamper with the data).
- message authentication codes that protect a message's data integrity and authenticity
Authentication encryption is a form of encryption which ensures both confidentiality and integrity, thus being secure agaist tampering. It can be built using a combination of a CPA-secure cipher and a MAC. However, only specific combinations of them are fully secure.
Actually, it can be proved that CPA security cannot even guarantee secrecy under active attacks. As a result, an authenticated encryption scheme should be used always, instead of a scheme that is only CPA-secure.
An authenticated encryption system (E, D) is a cipher where:
- as usual E: K x M x N -> C
- but D: K x C x N -> M U {⊥}, where the symbol ⊥ is returned when a ciphertext is rejected
A cipher provides authenticated encryption iff it provides:
- semantic security under a CPA attack
- ciphertext integrity, which means the attacker cannot create new ciphertexts that decrypt properly
More specifically, the ciphertext integrity challenge is defined in the following way: the attacker can send multiple messages to the challenger, who returns the encryption of these messages. Then, the attacker attempts to create a new, different ciphertext, which is not rejected by the challenger and is decrypted properly. If the attacker cannot achieve that with a significant probability, then the system has ciphertext integrity.
Interestingly enough, authenticated encryption provides even stronger guarantees, since it also protects against the so-called chosen ciphertext attacks (CCA). A CCA attack in when the attacker is also able to decrypt multiple ciphertexts, on top of all the other capabilities discussed.
However, there are still some attacks that are not prevented by authenticated encryption:
- replay attacks
- side-channel attacks
There are 3 potential ways to implement authenticated encryption, combining a cipher and a MAC:
- encrypt-then-mac, where the plaintext is first encrypted, then a MAC is produced based on the resulting ciphertext.
- encrypt-and-mac, where a MAC is produced based on the plaintext and the plaintext is encrypted without the MAC.
- mac-then-encrypt, where a MAC is produced based on the plaintext, then the plaintext and MAC are together encrypted to produce a ciphertext based on both.
The first option (encrypt-then-mac) is the only one that has been proven to reach the highest definition of semantic security in authenticated encryption, which contains CPA-security, CCA-security & ciphertext integrity.
As always, prefer existing standards (e.g. GCM), instead of implementing a custom combination of encrypt-then-mac yourself, because there's still space for mistakes.
So far, we've seen symmetric algorithms, where there is a single key used by any parties involved. However, we still need to have a way to exchange this key in a secure way, a process which is called key exchange.
Of course, that could be trivially solved with a trusted third party (TTP), which would hold all the symmetric keys of the involved parties and would be responsible for distributing new symmetric keys for each pair of parties that want to communicate. The main question is: can this be achieved without any trusted third party? And the answer is yes, through the use of public key cryptography.
A public key encryption system is a triple of algorithms (G, E, D), where:
G()is a randomized algorithm that outputs a key pair(pk, sk), wherepkis a public key andskis a secret keyE(pk, m)is a randomized algorithm that takes m in M and outputs c in CD(sk, c)is a deterministic algorithm that takes c in C and outputs m in M or ⊥
The system must satisfy the consistency property, which is that for every m in M and every (pk,sk) generated by g, the following holds: D(sk, E(pk, m)) = m
Having such a system, a key exchange could be performed in the following way:
- Party A could generate a key pair
(pk, sk)and send the public keypkto Party B. - Party B could generate a random number and send it back to Party A encrypted with the public key
pk. - Party A would then decrypt with the secret key
skand retrieve the random number, which acts as the shared secret key.
In the context of public key systems, the notion of semantic security takes the form of indistinguishability under chosen plaintext attack (IND-CPA). The challenge for this has the following form: the challenger sends a public key to the attacker, who sends back 2 messages (m0, m1) and receives the encryption of one of them (under the secret key). If the attacker is not able to identify which message was encrypted with significant possibility, then the system is said to be IND-CPA secure. Of course, there's another stronger notion of this security under chosen ciphertext attacks (IND-CCA).
Similar as before, this key exchange using only a public key encryption system is secure against passive attacks / eavesdropping (iff the system is IND-CPA), but it's not secure against active (man-in-the-middle) attacks. To secure it against active attacks as well, one could use digital signatures to add authentication (i.e. SSH, SSL/TLS). This is not covered in this course.
As described so far, symmetric cryptography's main property for security is randomisation.
In the case of asymmetric cryptography, this is not enough. Because of the asymmetry introduced, there has to be some structure that allows an easy computation in the forward direction (generating the key pair), but makes the inverse direction (discovering the private key from the public key) extremely hard computationally. The main building block for this are what are called intractable problems, which are problems for which there is no known efficient algorithm to solve them.
2 of these intractable problems leveraged in public key cryptographic systems are the following:
- The discrete logarithm problem (DLOG). For instance, calculating the logarithm of a number is relatively easy for real numbers, but it's an extremely harder problem in modular arithmetic.
- The factoring problem, which is the problem of distinguishing prime numbers from composite numbers and resolving the latter into their prime factors.
There's an important difference between symmetric and assymetric encryption: in the former, the attacker cannot create new ciphertexts (without the secret key), while in the latter the attacker can do so (using the known public key). This has the following implication: symmetric encryption systems do not require CCA security (but some of them, such as authenticated encryption, provide it as "extra". On the other hand, asymmetric (public-key) systems directly require CCA security.
There are 2 basic categories of public key encryption systems:
- based on trapdoor permutations
- based on Diffie-Helman
A trapdoor function X -> Y is a triple of efficient algorithms (G, F, F-1), where:
G(): a randomized algorithm that outputs a key pair (pk, sk)F(pk, .): a deterministic algorithm that defines a function X -> Y- F-1(sk, .): a function
Y -> Xthat inverts F
This triple of algorithms is considered to be a secure trapdoor function iff it can be evaluated, but it cannot be inverted without the private key.
Having :
- a secure trapdoor function (G, F, F-1)
- a symmetric authentication encryption system (Es, Ds) defined over (K, M, C)
- a hash function H: X -> K
we can construct a public key encryption system (G, E, D) in the following way:
- we use as generation function the function G from the trapdoor function
- E(pk, m) is defined in the following way:
- x is a random value in X
- y <- F(pk, x)
- k <- H(x)
- c <- Es(k, m)
- output (y, c)
- D(sk, (y, c)) is defined in the following way:
- x <- F-1(sk, y)
- k <- H(x)
- m <- Ds(k, c)
- output m
As long as the trapdoor function is secure, the symmetric encryption system provides authenticated encryption and H is a "random oracle", then (G, E, D) is CCA secure
Security Note: Never encrypt just by applying directly F to plaintext, because it's deterministic and thus cannot be semantically secure!
We've already seen how authenticated encryption systems are built, so the only mysterious question left is: how can I build a secure trapdoor function ?
RSA is one of the most widely used trapdoor functions, its security hardness relies on properties of modular arithmetic. It works in the following way:
- For the generator G():
- choose 2 random primes p,q ~ 1024 bits and calculate N = p * q
- choose a random integer e, so that it's invertible in phi(N) = (p-1) * (q-1)
- calculate d as the modular multiplicative inverse of e
- pk = (N, e) and sk = (N, d), where N is said to be the "key size"
- The F(pk, x) = xe
- F-1(sk, y) = yd = xed = x
To invert the RSA function , an attacker must compute x from xe. The best known algorithm for this involves factoring N, which is an intractable problem.
In order to calculate the private key d from the public key e via modular multiplicative inversion, an attacker must also know the factors of N (p & q).
Security Note: Security of the public key system should be comparable to the security of the symmetric cipher to maintain overall security. However, for RSA this implies much larger keys than the associated ciphers, since factorisation can at least be solved more efficiently than an exhaustive attack used for symmetric ciphers.
| Cipher key size | RSA modulus size (N) |
|---|---|
| 80 bits | 1024 bits |
| 128 bits | 3072 bits |
| 256 bits (AES) | 15360 bits |
There's a second category of public key encryption systems that are based on the Diffie Helman protocol, so let's see what that is first.
Diffie-Hellman is a protocol that can be used for key exchange, which works the following way:
- Alice and Bob agree to use a modulus p and base g. These are selected so that p is prime and g is a primitive root modulo / generator, which ensures that the resulting shared secret can take any value from 1 to p-1.
- Alice chooses a secret integer a, then sends to Bob the value A = ga mod p
- Bob also chooses a secret integer b, then sends to Alice the value B = gb mod p
- Alice can compute the shared secret key as s = Ba mod p = gab mod p
- Bob can compute the shared secret key as s = Ab mod p = gab mod p
The modular exponentiations made by Alice & Bob can be done efficiently. An attacker seeing the public data exchange is given g, p and ga mod p, but cannot calculate the secret a, since this is the problem of discrete logarithm (DLOG), which is an intractable problem.
This protocol can be generalised to finite cyclic groups, which do not necessarily use multiplicative groups of integers (i.e. Diffie-Helman with elliptic curves).
We've described above how we can build a key exchange protocol out of a public key encryption system. El Gamal demonstrates something even more interesting; how we can build a public key encryption system out of a key exchange protocol, such as Diffie-Helman. The associated public-key encryption system (G,E,D) is constructed in the following way:
- G a finite cyclic group of order n
- (Es, Ds) a symmetric authenticated encryption system
- H a hash function
- The key generation function G:
- choose random generator g in G and a random a in {0, 1, .., n-1}
- sk = a, pk = (g, h), where h = ga
- E(pk, m) = E((g,h), m):
- b random number in {0, 1, .., n-1}
- u <- gb
- v <- hb
- k <- H(u, v)
- c <- Es(k, m)
- output (u, c)
- D(sk, (u,c)) = D(a, (u, c)):
- v <- ua
- k <- H(u,v)
- m <- Ds(k, c)
- output m
For the general view of Diffie-Helman protocols in the group G, an attacker having g, ga and gb, should not be able to identify a pair (u1, v1), where u1a = v1. If that's true, then we can say the Interactive Diffie-Helman (IDH) assumption holds.
So:
- If IDH holds in the group G
- (Es, Ds) provides authenticated encryption
- H is a "random oracle"
then El Gamal is CCA secure.
