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.
Note: This compendium has only been written by a few people who are/were fellow students like yourself, and there are bound to be errors and missing content. Please be critical when using this compendium and please make your own contributions to improve 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 triad
Traditional definitions of information security are based on three information security goals:
 Conﬁdentiality
 Preserving authorised disclosure of information.
 Integrity
 Preventing unauthorised (accidental or deliberate) modification or destruction of information.
 Availability
 Ensuring resources are accessible when required by an authroised user.
Passive and Active 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 bruteforce 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.
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.
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.
Block Ciphers
 Product cipher
 A product cipher is a cryptosystem in which the encryption function is formed by applying (or composing) several subencryption functions.
 Iterated cipher
 An encrpytion process that is divided into r similar rounds, the subencryption functions are all the same function, g, called the round function. Each key is dervied from the overall master key K. The keys are called round keys or subkeys and are derived from K using a process called the key schedule.
Most modern ciphers are in a special class of product ciphers known as iterated ciphers. There are two types of iterated cihpers:
 Substitutionpermutation network
 An iterated cipher. The block length must allow each block to be split into subblocks. Substitution and permutation is then performed in a certain fashion.
 Feistel cipher
 An iterated cipher in which the round function swaps the two halves of the block and forms a new right hand half
Data encryption standard (DES)
 DES is a 16round Feistel chiper with key length of 56 bits and data block length of 64 bits.
 DES is no longer concidered secure.
TripleDES
To increase the security of DES, the algorithm may be run multiple times. Two times would be the simplest, but is vulnerable to a meetinthemiddle attack.
To counter this, three runs are needed. This is often implemented as EncryptDecryptEncrypt. This allows backwards compatibility with normal DES, by using the same key for all three steps:
While 3DES takes three keys as parameters, using it with only two keys is enough to stop the meetinthemiddle attack, and often good enough:
Some applications, like PGP and S/MIME, still use three keys with 3DES.
AES
 Symmetric key block cipher
 128bit data block; 128, 192 or 256bit master key
 Number of round, NR, is 10, 12 or 14 (for 128, 192, 256bit keys)
 Bytebased design
 Structure is essentially a substitutionpermutation network
Consists of four stages:
 Substitute bytes
 Uses an Sbox to perform a bytebybyte 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 nonlinearity, 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
Modes of operation
Electronic Codebook (ECB) Mode
 Randomised: No
 Padding: Required
 Error propagation: Errors propagate within blocks
 IV: None
 Parallel encryption: Yes
 Parallel decryption: Yes
Cipher Block Chaining (CBC) Mode
 Randomised: Yes
 Padding: Required
 Error propagation: Errors propagate within blocks and into specific bits of next block
 IV: Must be random
 Parallel encryption: No
 Parallel decryption: Yes
Counter (CTR) Mode
 Randomised: Yes
 Padding: Not required
 Error propagation: Errors occur in specific bits of current block
 IV: Nounce must be unique
 Parallel encryption: Yes
 Parallel decryption: Yes
CMAC (CBCbased MAC)
Integrity and confidentiality?
CCM mode (Counter mode with CBC MAC)
This mode combines CBCMAC for authentication of all data (payload plus associated data) and CTR encryption for the payload.
Authenticated encrpytion.
Psueodorandom numbers and stream ciphers
Randomness
 TRNG
 A true random number generator is a physcial process which outputs each valid string indpenedently with equal probability.
 PRNG
 A psuedo random number generator (PRNG) is a deterministic algorithm which approximates a TRNG.
 TRNGs can be constructed from physical devices and used as seeds for PRNGs
 PRNGs can be constructed from other primitives including block ciphers.
 TRNGs cna be used to make unbreakable encryption via the one time pas.
 PRNGs can be used as practical synchronous stream ciphers.
Onetime pad
A stream cipher that provides perfect secrecy. The key is a random sequence of characters, all of them independantly generated. Each character in the key is used one time only. A non periodic binary synchronous stream cipher.
Linear Feedback Shift Registers (LFSR)
The A5 cipher
 The A5 is a binary synchronous stream cipher applied today in most GSM mobile telephones.
 The A5/1 alogirhtm uses three linear feedback shift registers (LFSRs) whose output is combined.
 The three LFSRs are irregularly clocked which means that the overall output is nonlinear. The effective key length is 54 bits.
RC4
 A wordbased stream cipher.
 Simple and efficient for software implementation
 Too weak to be used today.
Public key cryptography
 Uses a oneway function, a function that is easy to perform one way, but hard to reverse
 Two pairs of keys: One public key for encryption, one private key for decryption.
 It is almost impossible to use the public key to learn the private key (one has to crack the one way funciton).
 Public key cryptography has two main advantages in comparaison with shared key (symmetric key) cryptography.
 The key management is simplified: keys do not need to be transported confidentially.
 Digital signatures can be obtained.
Number theory for public key cryptography
Chinese Remainder Theorem
Can be used to speed to RSA decrpytion.
Testing for primality
 Fermat Test can test if a number is a prime number.
 If a number satisfies Fermat's equation then we assume that it is prime.
 The Fermat test can fail but it is very unlikely to in practice.

The fermat test's failure can be reduced by repeating the test with different base values.

If the test outputs composite then n is definitely composie.
 The test cna output probable prime if n is composite (psuedoprime).

There are some composite numbers for which the test will always output probable prime (Carmichael numbers).

The MillerRabin test works on the same idea as the Fermat test.
 Can be guaranteed to detect composites if run sufficiently many times.
 Most widely used test for generating large prime numbers.
Two hard problems
 Integer facotisation
 Given an integer of m bits, find its prime factors.
Discrete logarithm problem (with base 2): Given a prime p of m bits and an integer y with 0 < y < p, find x such that y = (2^x)modp
 There are no known polynomial algorithms to solve either of these two problems.
 The best known algorithms are subexponential: they are slower than any polynomial algorithm but faster than any exponential function.
RSA
 A publickey crpytosystem and digital signature scheme.
 Based on integer factorisation problem.
 Implementation
 Key genreation (choice of e, genreating large primes)
 Encryption and decryption algorithms (fast exponentiation, using CRT for decryption)
 formatting data (padding)
 Security
 Standardised padding should always be used before encryption
 Factorisation of the modulus is the best known attack against RSA in the case that standardised padding is used.
 Finding the private key from the public key is as hard as factorising the modulus.
 It is an opten problem whether there is any way of breaking RSA encryption without factorising the modulus.
Other public key cryptosystems
DiffieHellman key exchange
 Designed to allow two users, ALice and Bob, to share a secret usign only public communications.
 Public knowledge: large prime p, generator g of Zp
 Alice and Bob each select random values a and b respectively where 0 < a, b < p1
 Alice sends g^a mod p to Bob (over an insecure channel.
 Bob sends g^b mod p to Alice (over an insecure channel)
 Alice and Bob both compute secret key Z = g^(ab)mod p
 An attacker who can find discrete logarithms can break the protocol, it is unknown whether a better way exists.
Elgamal cryptosystem
 Turns the DiffieHellman protocol into a cryptosystem.
 Alice combines her ephermeral private key with Bob's longterm private key.
Elliptic curves
 Elliptic curves are algebraic sturctures formed from cubic equations.
 An example is the set of all (x,y) pairs which satisfy the equation: y^2 = x^3+ax+bmodp this is a curve over the field Zp. Elliptic curves can be defined over any field.
 Once an identity element is added, a binary operation (like multiplication) can be defined on these points. This operation forms a group over the elliptic curve points, often called the elliptic curve croup
Hash functions and MACs
A hash function H is a public function such that:  H is simple and fast to compute  H takes as input a message m of arbitrary length and outputs a message digest H(m) of fixed length.
Interated hash functions
 Cryptographic hash functions need to take arbitrarysized input and produce a fixed size output.
 As we saw from block ciphers, we can process arbitrarysized data by having a function that processes fixed sized data by having a function that processes fixedsized data and use it repeatedly.
 An iterated hash function splits the input into block of fixed size and operatess on each block sequentially using the same function with fixedsize inputs.
 MerkleDamgård construction: Use a fixedsize compression function applied to multiple block of the message.
HMAC
 Built from an interated cryptographic hash function H, e.g., MD5, SHA1, SHA256, ...
 Standardized and used in many applications including TLS and IPsec.
Authenticated encrpytion.
 Galois Counter Mode (GCM) provides authenticated encryption.
Digital Signatures and Certificates
 Digital signatures use public key cryptography to provide the properties of a MAC and more.
 Only the owner of the private key can generate a correct digital signature.
 Digital signatures provide the nonrepudiation security service. A judge can decide which party formed the signature.
Digital signature elements
 A digital signature scheme has three algorithms:
 Key generation
 Signature generation; and
 signature verfication.
 Key generation outputs two keys:
 A private signature generation key or simply singning key, Ks:
 a public signature verification key, Kv.
Digital certificates
 When using a public key to encrypt a message or to verify a digital signature, it is essential to be confident of the correct binding between a public key and its owner.
 Normally this is achieved through use of digital certificates which contain the public key and owner identity, and usually other information such as signature algorithm and validity period.
 The certificate is digitally signed by a party trusted by the certificate verifier, normally called a certification authority or CA.
 Certificates play a central role in key management for public key infrastructures.
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 endtoend 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 higherlevel users.
The Alert Protocol
The Alert Protocol is used to convey TLSrelated 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. 0RTT mode) which present new challenges.
Email security
DomainKeys Identified Mail (DKIM)
 Allows sending mail domain to sign outgoing mail using RSA signatures (currenty supported signature algorithm)
 Receiving domain can verify origin of mail
 Widely used by prominent email providers including Gmail
 Helps prevent email spoofing and hence reduce spam and phishing.
 Public verification key of sneding domain retrieved using domain name system (DNs).
STARTTLS
 Extension to mail protocols SMPT, POP and IMAP run over TLS connections.
 Provides linkbylink security, not endtoend security
 Oppertunistic use of TLS security (encryption)  use it if possible.
 Defined for IMAP and POP3 (RFC 2595) and for SMPT (RFC 3207)
 Widely used by prominent email providers including Gmail and Microsoft Outlook
 Vulnerable to socalled STRIPTLS attacks  attacker interrupts TLS negotiation and connection falls back to plaintext transmission.
PGP
 Protection of email message contents
 Hybrid encrpytion  a new random "session key" is generated for each object (message) and the session key is encrpyted with the longterm public key of recipient.
 Signing using RSA or DSA signatures.
 Compression using Zip
 Coding using radix64 to ensure that binary strings can be sent in email body.
IP Security
 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.

IPSec are located at the network layer.

IPsec Encapsulating Security PayLoad (ESP) protocol can operate either in transport mode or in tunnel mode.

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.
IPsec modes
 Transport mode
 iphosttoiphost security where protection covers to the payload of IPdata. Encrypts IP payload and any IPv6 extension headers following the ESP header.
 Tunnel mode
 Network/gatewaytonetwork/gateway security. Protection for the entire IPpacket by adding outer IPpacket between the network gateways.
IPsec architectures
Gatewaytogateway architecture
 Provides secure network communications between two networks.
 Network traffic is routed through the IPsec connection, protecting it appropriately
 Only protects data between two gateways
 Most often used when connecting two secured networks, such as linking a branch office to headquarters over the internet
 Can be less costly than private wide area network (WAN) circuits.
Hosttogateway architecture
 Commonly used to provide secure remote access.
 The organisation deploys a virtual private network (VPN) gateway onto their network.
 Each remote access user establishes a VPN connection between the local computer (host) and the gateway.
 VPN gateway may be a dedicated device or part of another network device.
 Most often used when connecting hosts on unsecured network to resources on secured networks.
Hosttohost architecture
 Typically used for special purpose needs, such as system administrators performing remote management of a single server.
 Only model that provides protection for data throughout its transit (endtoend).
 Resourceintensive to implement and maintain in terms of user and host management.
 All user systems and servers that will participate in VPNs need to have VPN software installed and/or configured.
 Key management is often accomplished through the manual process.
old
Chapter 1
 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
 Nonrepudiation
 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 is a group generator for
 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$ .  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_{t1},K)$ where$C_0=IV$ $P_t=D(C_t,K)\oplus C_{t1}$ where$C_0=IV$  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=Nt$ 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$ .  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 onetime 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 subexponential 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 Onotation
 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.  MillerRabin test
 placeholder
 RSA Encryption equation
 placeholder
 RSA Decryption equation
 placeholder
 RSA Padding
 placeholder
 Prime number theorem
 placeholder
 Håstad's attack
 placeholder
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
 16byte key.
 Output
 176 bytes (44 words)
The first four words are used in the initial AddRoundKey step. The next ten wordgroups 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
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.