This is an old version of the compendium, written July 28, 2019, 8:30 p.m. Changes made in this revision were made by EvenMF. View rendered version.

TTM4135: Applied Cryptography and Network Security

# Preface This compendium will attempt to explain the core concepts of the subject. Feel free to edit, add or remove content if you feel like it would enhance the content.

# Introduction This section serves as an introduction to what the course is about, but some important concepts are introcduced. ## Definitions of fundamental concepts Let's start of with defining what this is all about. Information security : Minimizing vulnerabilities of information assets. From this we can define several other concepts. Vulnerability : Any weakness that could be exploited to violate a system or the information it contains. Information assets : Can include data, software and hardware, people and even buildings. Threat : A threat is a potential violation of security. All of these are so fundamental that you will most likely not be asked about this on the exam, this is just to provide some clarity when explaing more advanced topics. ## The CIA triadTraditional definitions of information security are based on three information security goals: Conﬁdentiality : Preserving authorised disclosure of information. In~~formation security are based on three information security goals~~tegrity : ~~Conﬁdentiality :~~ Pre~~ser~~ving authorized restrictions on information access and disclosure, including means for protecting personal privacy and proprietary information. A loss of confidentiality is the unauthorized disclosure of information. Integrity : Guarding against improper information modification or destruction, including information nonrepudation and authenticity. A loss of integrity is the unauthorizedenting unauthorised (accidental or deliberate) modification or destruction of information.

Availability

: Ensuring ~~timely and reliable access to and use of information~~resources are accessible when required by an authroised user. ## Passive and A ~~loss of a~~ctiv~~ailability is the disruption of access to or use of information or an information system~~e threats When concidering threats, there are two main types: passive and active. Passive threats : Passive threats do not alter information in the system. Such attacks may be eavesdropping and traffic analysis. Active threats : Active threats alter information in the system. Such attacks may be masquerade, replay, modification of messages, denial of service. ## Securit services and mechanisms Security service : A processing or communication service to give a specific kind of protection to system resources. Security mechanism : A method of implementing one or more security services. # Classical Encryption ## Exhaustive key search The most basic method of attack is exhaustive key search, sometimes called a brute-force attack, in which the adversary tries all possible keys. This attack cannot be prevented so all cryptosystems must have enough keys to make exhaustive search too difficult computationally. 128 bits is the samllest key size which would be acceptable to prevent exhaustive key search today. ## Statistics of Natural Language Many of the classical ciphers can be broken by studying the statistics of the messages. If you have a reasonably long message written in English, it is very likely that the most used character will be E, N, T, I and so on. By studying the character frequency of an encrpyted message you can often try to guess which character is supposed to be which (it will of course largely depend on the cipher used, and may not work at all on some ciphers. ## Transposition ciphers These types of ciphers are mosly based on switching the positions of the letters that appear in the message. For a transposition cipher the distributions of plaintext and cihpertext are the same. ## Substitution ciphers These types of cihpers are mostly based on switching out individual characters by other characters. For example switching E with Z or T with C. You can figure out if a simple substitution cipher has been used if the character frequency looks similar to the standard english character frequency only that other letters are used. A simple substitution cipher has n! different keys, where n is the size of the alphabet. ## Vigenére cipher If aplaintext comes from a natural language, such as English, the Vigenére cipher can be expected to have a "flat" frequency distribution of characters. Cryptoanalyiss of the Vigenére cipher often uses autocorrelation in order ot identify the period (key length) # Hill Cipher The Hill cipher is a historical cipher with the encryption equation C = KP mod n for k × k key matrix K and vectors C and P representing the ciphertext and plaintext. A fundamental weakness of the Hill cipher is that encryption is a linear function so a plaintext attack is easy. ## Kerckhoffs' Principle Kerckhoffs’ principle : The attacker has complete knowledge of the cipher (i.e the decryption key is the only thing unknown to the attacker. This one is asked about a lot. Make sure you know this one.

# Block Ciphers Iterated cipher : Most modern ciphers in this category, read more below. Product cipher : A product cipher is a cryptosystem in which the encryption function is formed by applying (or composing) several sub-encryption functions. Substitution-permutation network : An iterated cipher. Takes a block of the plaintext and the key as inputs, and applies several rounds of permutations, known as substitution boxes(S-box) and permutation boxes (P-box). A __S-box__ substitutes sub-blocks of size l bits (its input) by another block of bits (its output). It can be thought of as a substitution cipher. A __P-box__ takes the output from the S-boxes of one round, permutes the bits and feed them into the S-boxes in the next round. It can be thought of as a transposition cipher. At each round, the __round key__ is combined with some operation such as XOR. Feistel cipher : An iterated cipher in which the round function swaps the two halves of the block and forms a new right hand half ## DES ### Triple-DES To increase the security of DES, the algorithm may be run multiple times. Two times would be the simplest, but is vulnerable to a _meet-in-the-middle_ attack. To counter this, three runs are needed. This is often implemented as Encrypt-Decrypt-Encrypt. This allows backwards compatibility with normal DES, by using the same key for all three steps: $$ E(K_1, D(K_1, E(K_1, X))) = E(K_1, X) $$ While 3DES takes three keys as parameters, using it with only two keys is enough to stop the meet-in-the-middle attack, and often good enough: $$ E(K_1, D(K_2, E(K_1, X))) $$ Some applications, like PGP and S/MIME, still use three keys with 3DES. ## AES Consists of four stages: Substitute bytes : Uses an S-box to perform a byte-by-byte substitution of the block ShiftRows : A simple permutation MixColumns : A substitution that makes use of arithmetic over $GF(2^8)$ AddRoundKey : A simple bitwise XOR of the current block with a portion of the expanded key Only the `AddRoundKey` stage makes use of the key. The other three stages provides confusion, diffusion and non-linearity, but no security in themselves. When decrypting with AES, the inverses of the three first stages are used. The `AddRoundKey` stage is the same, because $ A \oplus B \oplus B = A $. # Transport Layer Security (TSL) Transport Layer Security (TSL) is one of the most widely used security services today. It's a general purpose service implemented as a set of protocols that rely on TCP. It can be implemented as part of the underlying protocol suite, or alternatively embedded in specific packages. TLS is designed to make use of TCP to provide a reliable end-to-end secure service. TLS consists of three important protocols: the Handshake Protocol, the Record Layer Protocol, and the Alert Protocol. ## The Handshake Protocol The Handshake Protocol is the most complex part of TLS. This protocol allows the server and client to authenticate each other and to negotiate an encryption and MAC algorithm and cryptographic keys to be used to protect the data sent in a TLS record. The Handshake Protocol is used before any application data is transmitted. The Hanshake Protocols consists of 4 different phases: Phase 1 : Establish security capabilities, including protocol version, session ID, cipher suite, compression method, and intitial random numbers. Phase 2 : Server may send certificate, key exchange, and request certificate. Server signals end of hello message phase. Phase 3 : Client sends certificate if requested. Client sends key exchange. Client may send certificate verification. Phase 4 : Change cipher suite and finish handshake protocol. ## The Record protocol The record protocol provides confidentiality and message integrity. The record protocol takes an application message to be transmitted, fragments the data into manageable blocks, optionally compresses the data, applies a MAC, encrypts, adds a header, and transmits the resulting unit in a TCP segment. Received data are decrypted, verified, decompressed, and reassembled before being delivered to higher-level users. ## The Alert Protocol The Alert Protocol is used to convey TLS-related alerts to the peer entity. As with other applications that use TLS, alert messages are compressed and encrypted, as specified by the current state. Each message in this protocol consists of two byes. The first byte takes the value warning or fatal to convey the severity of the message. If the level is fatal, TLS immediately terminates the connection. Other connections on the same session may continue, but no new connections on this session may be established. The second byte contains a code that indicates the specific alert. ## TLS Security - Different kinds of attacks: implementation errors, poor choice of cryptographic primitives, flaws in protocol. - Backward compatibility is a problem (downgrade attacks). - Several examples of the principle that “attacks only get better” over time. - TLS 1.3 simplifies the handshake. - TLS 1.3 adds new features (e.g. 0-RTT mode) which present new challenges. # IP Security - IPSec are located at the network layer. - IPsec Encapsulating Security PayLoad (ESP) protocol can operate either in transport mode or in tunnel mode. Transport mode : iphost-to-iphost security where protection covers to the payload of IP-data. Encrypts IP payload and any IPv6 extension headers following the ESP header. Tunnel mode : Network/gateway-to-network/gateway security. Protection for the entire IP-packet by adding outer IP-packet between the network gateways. - Internet Protocol security (IPsec) is a framework for ensuring secure communications over Internet Protocol (IP) networks. - It provides similar security services as TLS, but at a lower layer in the communications protocol stack. - Security can be added to both IPv4 and IPv6. - IP level security encompasses three functional areas: authentication, confidentiality, and key management. - The authentication mechanism assures that a received packet was, in fact, transmitted by the part identified as the source in the packet header. In addtition, this mechanism assures that the packet has not been altered in transit. - The confidentiality facility enables communicating nodes to encrypt messages to prevent eavesdropping by third parties. - The key management facility is concerned with the secure exchange of keys.

# Chapter 3: Classical Encryption Techniques: ## Symmetric Cipher Model A symmetric encryption scheme has five ingredients: Plaintext : This is the original intelligible message or data that is fed into the algorithm as input. Encryption algorithm : The encryption algorithm performs various substitutions and transformations on the plaintext. Secret key : The secret key is also input to the encryption algorithm. The key is a value independent of the plaintext and of the algorithm. The algorithm will produce a different output depending on the specific key being used at the time. The exact substitutions and transformations performed by the algorithm depend on the key. Ciphertext : This is the scrambled message produced as output. It depends on the plaintext and the secret key. for a given message, two different keys will produce two different ciphertexts. The ciphertext is an apparently random stream of data and, as it stands, is unintelligible. Decryption algorithm : This is essentially the encryption algorith run in reverse. It takes the ciphertext and the secret key and produces the original plaintext. There are two requirements for seccure use of conventional encryption: 1. We need a strong encryption algorithm. At a minimum, we would like the algorithm to be such that an opponent who knows the algorithm and has access to one or more ciphertexts would be unable to decipher the ciphertext or figure out the key. This requirement is usually stated in a stronger form: The opponent should be unable to decrypt ciphertext or discover the key even if he or she is in possession of a number of ciphertexts together with the plaintext that produced each ciphertext. 2. Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure. If someone can discover the key and knows the algorithm, all communication using this key is readable. ![](https://s3-eu-west-1.amazonaws.com/wikipendium-public/15474700970xe0c68.jpg) ### Cryptography Cryptographic systems are characterized along three independent dimensions: 1. __The type of operations used for transforming plaintext to ciphertext.__ All encryption algorithms are based on two general principles: substitution, in which each element in the plaintext (bit, letter, group of bits or letter) is mapped into another element, and transposition, in which elements in the plaintext are rearranged. The fundamental requirement is that no information be lost (i.e., that all operations are reversible). Most systems, referred to as _product systems_, involve multiple stages of substitutions and transpositions. 2. __The number of keys used.__ If both sender and receiver use the same key, the system is referred to as symmetric, single-key, secret-key, or conventional encryption. If the sender and receiver use different keys, the system is referred to as asymmetric, two-key, or public-key encryption. 3. __The way which the plaintext is processed.__ A _block cipher_ processes the input one block of elements at a time, producing an output block for each input block. A _stream cipher_ processes the input elements continuously, producing output one element at a time, as it goes along. ### Cryptoanalysis and Brute-Force Attack Typically the objective of attacking an encryption system is to recover the key in use rather than simply to recover the plaintext of a single ciphertext. There are two general approaches to attacking a conventional encryption scheme: Cryptoanalysis : Cryptoanalytic attacks rely on the nature of the algorithm plus perhaps some knowledge of the general characteristics of the plaintext or even some sample plaintext-ciphertext pairs. This type of attack exploits the characteristics of the the algorithm to attempt to deduce a specific plaintext or to deduce the key being used. Brute-force attack : The attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained. On average, half of all possible keys must be tried to achieve success. #### Type of Attacks on Encrypted Messages Ciphertext only : Encryption algorithm and ciphertext are known to cryptanalyst. Known plaintext : Encryption algorithm, ciphertext, and plaintext message chosen by crpytanalyst, together with its corrresponding ciphertext generated with the secret key are known to cryptanalyst. Chosen ciphertext : Encryption algorithm, ciphertext, and ciphertext chosen by crpytanalyst, together with its corrresponding plaintext generated with the secret key are known to cryptanalyst. Chosen text : Encryption algorithm, ciphertext, plaintext message chosen by crpytanalyst, together with its corrresponding ciphertext generated with the secret key, and ciphertext chosen by crpytanalyst, together with its corrresponding plaintext generated with the secret key are known to cryptanalyst. ## Transposition Techniques Encrypt the plaintext by performing some sort of permutation on the letters. ### The Rail Fence technique The simplest transposition cipher. The plaintext is written down as a sequence of diagonals and then read off as a sequence of rows. https://www.youtube.com/watch?v=VRiN9M0v3ZQ # Definitions These are definitions found in course material (mostly exercises) which may prove useful for the exam ##Chapter 1 AData origin authentication : prov~~ailability~~ides confirmation of the claimed source (origin) of a data unit (message) Entity authentication : ~~ensuring resources are accessible when required by an authorised user Cipher : See own section Conﬁdentiality : pre~~proventing unauthorised disclosure of information Data origin authentication : provides confirmation of the claimed source (origin) of a data unit (message) Entity authentication : provides confirmation of the claimed identity of an entity Integrity : preventing unauthorised (accidental or deliberate) modification or destruction of information Kerckhoffs’ principle : the cryptanalyst has complete knowledge of the cipher. The only unknown part is the decryption key.ides confirmation of the claimed identity of an entity

Non-repudiation : Ensures that you cannot hide the source (origin) of a data unit (message). Substitution : each character (or set of characters) is replaced by a different character (or set of characters) Transposition : the characters in the plaintext are mixed up with each other (permuted) ## Chapter 2 Confusion : This involves substitution to make the relationship between the key and ciphertext as complex as possible. Diffusion : This involves transformations that dissipate the statistical properties of the plaintext across the ciphertext. (A small change in plaintext should give a completely different ciphertext) Group generator : A group generator is a group element g that in the operation __$g^k \mod p$__ represents all the elements that are relatively prime to p. Consider for example the group G $\mathbb{Z}_5$. G consists of the elements {1, 2, 3, 4}. One or several of these group elements may be a group generator for G. A way to check this is to use __$g^k \mod 5$__ for the k group elements and see if they represent all the group elements. Example: $2^1 =2 \mod 5 = 2$ $2^2 =4 \mod 5 = 4$ $2^3 =8 \mod 5 = 3$ $2^4 =16 \mod 5 = 1$ 2 is a group generator for $\mathbb{Z}_5$ because all its elements ({1, 2, 3, 4}) are represented. Finite ﬁeld : placeholder ## Chapter 3 Electronic Code Book (ECB) Mode : The basic mode of a block cipher. Plaintext block $P$ is encrypted with key $K$ to produce ciphertext block $C_t$. Ciphertext block $C$ is decrypted with key $K$ to produce plaintext block $P_t$. ![ECB-image](https://image.ibb.co/f2nV0o/Capture.png) Cipher Block Chaining (CBC) Mode : A random initialization vector (IV) is chosen and sent together with the ciphertext blocks. $C_t=E(P_t\oplus C_{t-1},K)$ where $C_0=IV$ $P_t=D(C_t,K)\oplus C_{t-1}$ where $C_0=IV$ ![CBC-image](https://image.ibb.co/eCTnfo/Capture.png) CTR Mode : CTR is a synchronous stream cipher. The keystream is generated by encrypting successive values of a "counter", initialised using a nonce (randomly chosen value) N: $O_t=E(T_t,K)$, where $T_t=N||t$ is the concatenation of the nonce and block number t. Encryption: $C_t=O_t\oplus P_t$. Decryption: $P_t=O_t\oplus C_t$. ![CTR-image](https://image.ibb.co/mSz4RT/Capture.png) True Random Number Generator (TRNG) : is a physical process which outputs each valid string independently with equal probability Pseudo Random Number Generator (PRNG) : is a deterministic algorithm which approximates a TRNG. Message Authentication Code (MAC) : A message authentication code (MAC) is a cryptographic mechanism used for ensuring message integrity. A MAC tag should at least be of length $\log_2{I/R}$ where $I$ is a limit on how many invalid messages are detected before the key is changed and $R$ is the acceptable probability that a false message is accepted. Stream Cipher : Stream ciphers are characterised by the generation of a keystream using the short key and an initialisation value as input. Each element of the keystream is used successively to encrypt one or more ciphertext characters. Stream ciphers are usually symmetric key ciphers: sender and receiver share the same key and can generate the same keystream given the same initialisation value. Synchronous stream ciphers : The keystream is generated independently of the plaintext. Both sender and receiver need to generate the same keystream and synchronise on its usage. One Time Pad : The key is a random sequence of characters, all of them independently generated. Each character in the key is used one time only. The one-time pad provides perfect secrecy. Linear Feedback Shift Register : A LFSR is a common component in design of stream ciphers. ## Chapter 4 Factorisation problem : Given an integer of *m* bits, find its prime factors. Factorisation by trial division is an exponential time algorithm and is hopeless for numbers of a few hundred bits. A number of special purpose methods exist, which apply if the integer to be factorised has special properties. The best current general method is known as the number field sieve. The number field sieve is a sub-exponential time algorithm. Discrete logarithm problem : Let g be a generator of $\mathbb{Z}_p^*$ for a prime p. The discrete log problem over $\mathbb{Z}_p^*$ is: **given y in $\mathbb{Z}_p^*$ find x with y = $g^x$ mod p.** Big O-notation : placeholder Fermat test : *if* a number p is prime then $a^{p−1}$ mod p = 1 for all a with gcd(a, p) = 1. If we examine a number n and find that $a^{n−1}$ mod n $\neq$ 1 then we know that n is not prime. Miller-Rabin test : placeholder RSA Encryption equation : placeholder RSA Decryption equation : placeholder RSA Padding : placeholder Prime number theorem : placeholder Håstad's attack : placeholder ## Chapter 5 Generator of $\mathbb{Z}_p^*$ : placeholder Diffie-Hellman key exchange : placeholder Elgamal cryptosystem : placeholder Collision resistance : placeholder Second preimage resistance : placeholder One-wayness : placeholder Birthday paradox : placeholder HMAC : placeholder GCM Mode : placeholder ## Chapter 6 Digital signature : placeholder Existential forgery : placeholder Selective forgery : placeholder Digital Signature Algorithm (DSA) : placeholder Key predistribution : placeholder Session key distribution : placeholder Key agreement : placeholder Needham-Schroeder protocol : placeholder Kerberos : placeholder TODO: Scrape definitions from all exercises (currently they are just from exercise 1-6) # Ciphers ## Symmetric cipher (secret key cipher) encryption and decryption keys known only to sender and receiver. (DES) ## Asymmetric cipher (public key cipher) each participant has a public key and a private key, may allow both encryption and signatures. (RSA) ## Attacks ### Ciphertext only attack the cryptanalyst has available only the intercepted cipher text. ### Known plaintext attack the cryptanalyst knows a small amount of plaintext and its cipher text equivalent ### Chosen plaintext attack The cryptanalyst can obtain the cipher text equivalent of some plaintext which can be selected by the attacker, i.e the attacker has an "inside encryptor” available ### Chosen cipher text attack The cryptanalyst can obtain the plaintext equivalent of some cipher text which can be selected by the attacker, i.e. the attacker has an “inside decryptor” available. ## Historical ciphers - Caesar - Substitution - Vigenère. Caesar, but also uses a key in order to choose how many steps to shift the alphabet for each letter #### Key expansion Input : 16-byte key. Output : 176 bytes (44 words) The first four words are used in the initial AddRoundKey step. The next ten word-groups are used in the ten rounds of the cipher. ### RSA # Iterated ciphers - Encryption process divided into _r_ similar rounds - the sub encryption functions _g_ are the same for all rounds - Each key $K_i$ is derived from the overall master key K. The keys $K_i$ are called round keys or subkeys and are derived from K using a process called the key schedule. ## Encryption Given a plaintext block, P, a round function g and round keys $K_1, K_2, . . . ,K_r$ , the ciphertext block, C, is derived through r rounds as follows. $$W_{0} = P$$ $$W_{1} = g(W_{0}, K_{1})$$ $$W_{2} = g(W_{1}, K_{2})$$ $$.$$ $$.$$ $$.$$ $$W_{r} = g(W_{r−1}, K_{r})$$ $$C = W_{r}$$ # Pseudorandom number generation Generated numbers should be as random as possible. This is defined by two criteria: Uniform distribution : The frequency of occurence of ones and zeros should be approximately equal. Independence : It should not be possible to infer a subsequence from any other.