# Information Security

# Information Security Part 1

## Lecture 1

- A system under the assumption that entities have infinite computing power is called a _information-theoretical_ secure system.
- A system under the assumption that an entity which wants to break the system has a computing power under a certain upper bound and the system is secure under this upper bound, is called a computationally secure system.

| | encryption | integrity |
|:- |:- | :- |
| private key | private key encryption| private key authentication |
| public key | public key encryption | signatures |

### Kerckhoffs' principle
> The cipher should remain secure even if the adversary knows the specification of the cipher.
>
The only secret is a short key $k$ that is chosen uniformly at random.

Why?
- Design details often can be reverse-engineered.
- Short keys are easier to protect, generate and replace.
- Design details can be discussed and analyzed in public.

### Physical unclonable function (PUF)
A fingerprint of a chip.

### Mathematical View
$\mathcal{K}$ := key space
$\mathcal{M}$ := plaintext space
$\mathcal{C}$ := ciphertext space

Encription:
$\mathcal{K} \times \mathcal{M} \to \mathcal{C}$
Decription:
$\mathcal{K} \times \mathcal{C} \to \mathcal{M}$

or:

$\forall k \in \mathcal{K}: Dec_k(Enc_k(m)) = m$

### Brute force Attack

$w \in \mathcal{K}, c = Enc_w(m) => \exists k \in \mathcal{K}: Dec_k(c) = m$
An attacker can try to decrept a message $c$, by decrypting it with every possible $k$ until the resuls looks like a valid message. We call such an attack; brute force attack. We protect against it, by choosing a large key space $\mathcal{K}$.

### Historical Ciphers
#### Caesar's Shirft Cipher
$Enc_k(m_0,...,m_n) = ((k + m_0) \% 26,...,(k+m_n) \% 26)$
$Dec_k(c_0,...,c_n) = ((c_0-k \% 26,...,(c_n-k) \% 26)$

Problem: The key space is very small and we can perform statistical analyis to find k.

#### Vigenere Cipher
_Mono-alphabetic_ substitution can easily be broken, with statistical analysis. Vigenere's idea: _poly-alphabetic_ substitution.

Approach: Perform _Caesar's Cipher_ with longer key:
$k = k_0,...,k_d$
$Enc_k(m_0,...,m_n) = ((k_0 + m_0) \% 26,...,(k_{n\%d}+m_n) \% 26)$

Attack
We can determine $d$ with _Kasiski & Babbage, Friedman_.
We can note all possible $d$ based on pattern repetition (as words that appear often, are likely to be hit again in the same way again).

We can calculate the _Index of coincidence (propability that any two randomly chosen letters are equal)_ using the following formulas:
$I_{c}(m) = \frac{\sum_{i=0}^{25}n_i \dot (n_i - 1)}{n \dot (n - 1)} \approx \sum_{i=0}^{25}p_{i}^2$
That is the proability that two letters choosen at random match. This probability is 6.8% for the english language and 3.8% for a random string.

### Defintion of Secure
An encryption scheme is _perfectly secret_ if for random variables $\mathcal{M, C}$ and every $m \in \mathcal{M}$ and $c \in \mathcal{C}$.
$P(M = m) = P(M = m | C = c)$

### A perfectly secret scheme: One-Time-Pad

$Dec_k(Enc_k(m)) = k \text{ xor } (k \text{ xor } m)$

Problem:
- key is not reusable
- key has to be as long as the message

### Shannon Theorem
In every perfectly secret encryption scheme we have $|\mathcal{K}| \ge |\mathcal{M}|$.

Proof:
If $c$ is a ciphertext, it must be a possible encryption of any plaintext $m$. [Otherwise it would be dependent on $k$ or $m$ and hence not _perfectly secure_.] For this to be true, we need a different key $k$ per message $m$, thus $|K| > |M|$.

### Do we need perfec secrecy?
How about a model where the _power_ of the adversary is _limited_.

> A system is secure if every TM that operates in time t can break it with probablity $\le \epsilon$.
>
### Notation

Negligible: Approching 0 faster than the inverse of any polynomial.

$Y \leftarrow M(X)$ = $Y$ The variable $Y$ takes the value that $M$ outputs (probabilistically) on input $X$ (assuming the random input is chosen uniformly).

$Y \leftarrow \mathcal{A}$ = $Y$ The variable $Y$ is choosen uniformly at random from set $\mathcal{A}$.

### Negligible Function
A function $\mu:\mathbb{N}\to\mathbb{R}$ is called a _negligible function_, if $\forall{c \in \mathbb{N}^{+}}$ there $\exists{N_c \in \mathbb{N}}$ such that $\forall{x\ge N_C}$: $|\mu(x)|\le \frac{1}{x^c}$.

Typically, we say that a scheme $X$ is secure if $\forall P(M \text{ breaks the scheme } X)$ is negligible.

With $k = \{0,1\}^n$ an adversary can guess $k$ with probability $2^{-n}$, or brute force in time $2^n$.

### CPA-security
(Enc, Dec) is CPA-secure (CPA = chosen-plaintext attack) if, every randomized polynomial time adversary guesses $b$ correctly with probability at most 0.5 + e(n), where e is negligible.

## Lecture 2
> IND-CPA: INDistinguishability under Chosen Ciphertext Attack

An encryption sheme is INDistinguishable under CPA if we send two messages ($m_1$, $m_2$) to an oracle which will send us back $Env(m_i)$ (b selected at random from to be 0 or 1) and only guess b with probability at most $0.5 + \epsilon(n)$ where $\epsilon$ is negligible.

If IND-CPA exists with $|k| < |m|$, then $P \neq NP$. And if $P \neq NP$ the adversary can guess the key.

If we can prove that we have an encryption that is IND-CPA, this would prove $P \neq NP$.


Who we can proove something?
- Suppose that some computational assumpation $A$ holds $\implies$ then scheme $X$ is secure. [most often used in cryptography]
- Suppose that some scheme $Y$ is secure $\implies$ then scheme $X$ is secure

### PRG
> Pseudo Random Generator implies secure encryption.

> does AES provide semantic security -> NO, because for the same msg and key it will produce the same ciphertext

A PRG takes a seed and create a OTP [G(s)] with the same length as the message. We then xor the message with the output of the PRG. Decryption can happen the same way.


#### Golomb's Postulates
> No finite sequence constructed by a linear feedback shift register is a truly random sequence. Golomb [1] introduced the notion of a pseudorandom sequence for a periodic binary sequence that satisfies three randomness postulates. These postulates reflect properties one would expect to find in a random sequence.
A run in a binary sequence is a set of consecutive Os or Is. A run of Os is denoted a gap and a run of Is is denoted a block. A gap of length is a set of k consecutive Os flanked by Is. A block of length is a set of k consecutive Is flanked by Os. A run of length is is a gap or length k or a. block of length k. In this terminology, the three randomness postulates of a periodic sequence are as follows:
R-1: In a period of the sequence, the number of Is and the number of Os differ by at most 1.
R-2: In every period, half the runs have length 1, one-fourth have length 2, one-eighth have length 3, etc., as long as the number of runs so indicated exceeds 1. Moreover, for each of these lengths, there are equally many gaps and blocks. R-3: The out-of-phase auto-correlation of the sequence always has the same value.
The R-2 postulate implies the R-1 postulate, but otherwise the postulates are independent, which follows from the observation that there exist sequences that satisfy some but not all of the postulates. Some examples are:
Example 1: The m-sequence 00001001011001111 10001101110101 of period 31 is an R-1, R-2 and R-3 sequence.
Example 2: The sequence 00100011101 of period 11 is an R-1 sequence. It is also an R-3 sequence since the out-of-phase auto-correlation is equal to —1. However, the sequence is not an R-2 sequence since there are two blocks of length 1 but only one gap of length 1.
Example 3: The sequence 0000010001101 of period 13 is an R-3 sequence with a constant out-of-phase auto-correlation being 1, but the sequence violates the R-1 and R-2 conditions.
Example 4: The sequence 01001101 of period 8 is an R-1 and R-2 sequence but not an R-3 sequence.
The three randomness postulates are inspired by the properties obeyed by maximum-length linear sequences (m-sequences). Also they can be interpreted as properties of flipping a perfect coin. R-1 says that heads and tails occur about equally often; R-2 says that after a run of n heads (tails) there is a probability 1 /2 that the run will end with the next coin-flip. R-3 is the notion of independent trials. Knowing the outcome of a previous coin-flip gives no information of the current coin-flip.
Any sequence obeying both R-1 and R-3 can be shown to have a value of the out-of-phase autocorrelation of -1, and therefore the period must be odd. Sequences which obey the randomness postulates of Golomb are sometimes also called pseudonoise sequences.
Tor Helleseth

A definition of what it means for a string to be random, however LFSRs has this property and has still found to be insuecure. -> We need something stronger!

**We call a PRG cryptographically secure if, the probability that a polynomial-time turing machine disdinguishes a random string from an output of the PRG is negligible.**

We can proofe the correctness of this statement, by assuming an adversary can attack the system, resulting at the conclusion, that the input what not random.


### One-Way Function
We can only prove that one-way function exist, only if $P \neq NP$.

### Stream Ciphers
In practice we use stream ciphers as PRG, whihc produce an infiinte stream of bits.


### Kasiski examination
A method of attacking polyalphabetic substitution ciphers, such as the Vigenere cipher.

The Kasiskis examination allows to deduce the length of the keyword, affter which a frequency attack can be performed. Kasiskis examination does this by looking for characters that are repeated in the ciphertext. Occurrences of a string are likely to be multiples of the keywords length.

### Index of Coincidence
A technique of putting two texts side-by-side and counting the number of times that identical letters appear in the same position in both texts.

## Lecutre 3

### Pseudorandom permutations PRP
A keyed permutation $F$ is _pseudorandom_, if it cannot be distiuished from a completly random permutation. It bijectivly maps one bitstring to another. For a strong PRP the attacker is also allowed to use $F^{-1}$.

### Block Cyper
Block ciphers cannot be used directly for encryption. (If we split the message and use the same key for each one to encrypt, we leak information).


### Feistel Networks
A way of repeatedly apply encryption on a message - used by DES.

### Triple Encryption
Certain encryption shemas are to easy to break by a brute fore attack. Applying the encryption twice still allows for a meet-in-the-middle attack, therefore we use triple encryption.


### AES
AES is based the _substituition-permutation network_ design principle and using a combination of both substitution and permutation. It is fast in both software and hardware. It encrypts 128-bits block with a key of 128 (10 cycles), 192 (12 cycles) or 256 (14 cycles) bits.

### Stream vs Block Ciphers
- stream ciphers are a bit more efficient
- stream ciphers appear to be less secure
- block ciphers are a better choice for most application

## Lecture 4 - Message Authenitcation

We say that $\text{MAC} = (\text{Tag},\text{Vrfy})$ is secure, if the chances that a polynomial-time adversariy A breaks the MAC is negligible in n.

### Mathematical View
$\mathcal{K}$ - key space
$\mathcal{M}$ - plaintext space
$\mathcal{T}$ - set of tags

A message authentication code (MAC) scheme is a pair (Tag, Vrfy), where
$\text{Tag}: \mathcal{K} \times \mathcal{M} \to \mathcal {T}$
$\text{Vrfy}: \mathcal{K} \times \mathcal{M} \times \mathcal {T} \to \{\text{yes},\text{no}\}$

It should always hold that
$\text{Vrfy}_{k}(m,\text{Tag}_k(m)) = \text{yes}$

### MAC

### Hash Functions


We need _collision resistance_! Problem: For a fixed hash function $\text{H}$ there always exist an algorithm that finds a collision in constant time.

We say an adversary $A$ breaks the function $H$, if $H^{S}(m) = H^{S}(m')$. We call a function collision-resistant, if the probability of breaking the function is negligible.

## Lecture 5 - Key Distribution and PK Crypto
- naive: pairwise keys
- need quadratic number of keys
- KDC (Key Distribution Center)
- feasible in one company
- infeasible on the internet
- relies on the honesty of KDC
- KDC needs to permanently available
- single point of failre
- Public-Key Cryptography
- same idea can also be used for authentication
- instead of public key and private key, we have a signing tag and a verification tag



# TODO

## Lecture 7 - Zero Knowledge Proofs and Commitments
> ZKP: Proving knwledge of a secret, without revealing it.

- Completeness: If both P and V are honest, protocol succeeds with overwhelming probability.
- Soundness: No P without knwledge of s can convince V with non-negligible probability.
- Zero Knowledge: The prover leaks no information

### Fiat-Shamir


### Summary
- information-theoretic, unconditional
- one time pad
- quantum cryptography
- computational
- based on 2 simulaneous assumptions
- some problems are computationally difficult
- our understanding of what _computational difficulty_ means is correct

### Commitment Scheme
A commitment scheme is a cryptographic primative that allows one to commit to a chosen value (or chosen statement) while keeping it hdden to others, with the ability to reveal the committed value later. Commitment schemes are binding, meaning they are designed so that a party cannot change the value or statement after they have committed to it.

## Exercise 1
### Show that _shift_, _substitution_ and _Vigenere ciphers_ are all trivial to break using CPA:
CPA: The adversary learn one or more pairs of plaintext/ciphertexts encrypted under the same key.
- shift cypher: uses one number as a key, therfore knowing one character of the plantext is enough to break the cipher
- substitution cyper: every character is mapped to another one, hence we have to know all but one character of the plaintext
- vigenere ciphers use a fixed length of character as key, we therefore need to know at least many characters from the plaintext as the key contains.

### The lecture slides describe an attack by Kasiski et al. on theVigenere cipher. To prevent the attack, the following modificationhas been proposed:
- Kasiski's method will mostlikely fail, as it the same word will look different in every block.
- We test for peridos of different length and check the output for repeated words. Once we find a lot of repeated words, we assume to have found t. Repeted words are likely to occure once we corrected for the additional shifting.

### Proof that a OTP without K = 0' is not perfectly secure any longer:
By not allowing K = 0' we're reducing the key space to $|K| < |M|$ [we have the same amount of characters giving us originally $|K| = |M|$], thus we can refute the claim.

### Prove or refute the following claim: Every encryption scheme, for which the size of the key spaceequals the size of the message space, and for which the key is chosen uniformly from the key space, is perfectly secret.
Refute: The key has to be applied properly. A function might take a key and message and simply return back the message. -> the size of the keyspace is a necessary, but not a sufficient condition

### Perfectly Scure

DEF: An encryption scheme (Gen, Enc, Dec) over a message space $\mathcal{M}$ is _perfectly secret_ if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$ for which $Pr[C=c] > 0$.

$Pr[M = m | C = c] = Pr[M = m]$

LEM: An encryption scheme (Gen, Enc, Dec) over a message space $\mathcal{M}$ is _perfectly secret_ if and only if for every probability distribution over $\mathcal{M}$, every message $m \in \mathcal{M}$, and every ciphertext $c \in \mathcal{C}$:

$Pr[C = c | M = m] = Pr[C = c]$

### P/R:

Sol:

# Part II

## Lession 1

### Security Properties
- CIA - The most common secuirty properties
- Confidentiality (Secrecy): No improper diclosure of information [public/private-key encryption, symmetric encryption]
- Integrity: No improper modification of information [MACs and digital signatures]
- Availability: No improper impairment of functionality / service [non crypto -> replication, lb, backups]
- others
- Authenticity: closely related to integrity, with a difference of emphasis
- Non-repudiatation / accountability: Establish responsbility for actions
- Plausibile Deniability: Contrary to non-repudiatation and can be seen as weak form of secrecy
- Privacy
- Anonymity: secrecy of principal identities or communication relationships
- Data protection: Personal data is only used in certain ways

### IBM Secure Coporcessor
- layers and owners each have a keypair
- private key of layers stored in persistent storage and protected from higher layers
- layers physically secured: parts of memory are read only, higher layers cannot access lower layers, tamper-proof packaging etc.
- layer i uses private key for
- outbound authenticat
- certifying integrity of i+1st layer
-

### Dolev-Yao Model
The Dolev-Yao model is a formal model used to prove properties of interactive cryptographic protocols.

## Dictionary

- Symetric Encryption
Use the same key to encrypt and decrypt.
- Block Ciphers (DES, AES)
Cipher that encrypts blocks of a message with a key in a way, that identical blocks produce distinct
- Stream ciphers (RC4)
- Elements of number theory
- Asymetric encryption (RSA, ElGamal, Rabin)
Use different key to encrypt and decrypt.
- Signature Schemes (RSA, ElGamal)
- Zero-Knowledge
- Multiparty Computations
- Private Information Retrieval
- PUFs
- Physically Unclonable Functions: $chip1(X) \neq chip2(X)$, are possible if the manufacturing process does not allow the produciton of identical circuits.
- Substituition-Permutation Network

- Feistel Cipher
Used by DES,

### CBC-MAC (cipher block chaining message authentcation code)
CBC-MAC is secure for fixed-length messages, any single key must only be used for messages of a fixed and known length.


The message length is necessary, otherwise we can construct the signature for $m = (m_1, m_2)$, by querying $tag_k(tag_k(m_1) \oplus m_2)$.

## Block cipher mode of operation
### ECB - Electronic Codebook (Penguin Encryption)
Encrypt each block with the same key and return all the ciphertext, decryption works by simply using the decryption function. This method lacks diffusion and thus does not hidde data pattern well, resulting in the pinguin-effect.


### Damgard-Merkle
given $h: \{0,1\}^{2L} \to \{0,1\}^{L}$ we construct $H: \{0,1\}^{m} \to \{0,1\}^{L}$


### CBC - Cipher Block Chaining
It addos on ECB by XORing each plaintext with the ciphertext of the previous block (using an IV to start). To decrypt the message we simply XOR the ciphertext, after appling the reverse function.

*we use PKCS#5 for padding


Encrypt:
$C_i = E_K(P_i \oplus C_{i-1})$
$C_0 = IV$

Decrypt:
$P_i = D_K(C_i) \oplus C_{i-1}$
$C_0 = IV$

Drawback: Cannot be parallelized, Message must be padded to a multiple of the cipher block size.

The IV makes sure identical messages get encrypted differently.

## CFB (chipher feedback mode)

Advantages over CBC:
- the block cipher is only ever used in the encryption direction
- msg does not need to be padded to a multiple of the cipher block size

## OFB (output feedback mode)
Like CFB, but we take the output before we and it with the message.



## Counter (CTR) mode


### Blum Blum Shub
Is a PRG that takes the form:
$x_{n+1} = x_{n}^2 \mod M$, where $M = p* q$ is the product of two large primes.

### Subsitution-Permutation Network

We xor the plaintext with a key and then substitude and permutate the output, we repeat these steps with different keys. It is strictly necessary to run multiple rounds, otherwise the key can be learned trivially by an adversary.

### DES - Data Encryption Standard
DES is the archetypal block cipher, based on a balanced Feistel Network.

### Symmetric vs. Asymmetric Algorithms
Symmetric algorithms are much faster than asymmetric algorithms. On the other hand, asymmetric algorithms encryption doesn't require a secure and authentic connection to transfair a key, furthermore only one "intentent" recipient can read the message, it is also possible to sign messages.

### Commitments
> A perfectly binding commitment cannot be opened to a value other than the value used to create the commitment, even by a computationally unbounded adversary. A perfectly hiding commitment hides the committed value even towards a computationally unbounded adversary.

Show that a commitment scheme cannot be perfectly binding and perfectly hiding simultaneously.

In order to be perfectly binding, only a single value can result in a given commitment. [so the sender can not choose different keys for different outputs] Otherwise an unbounded adversary could create all possible commitments using every possible input with every possible random string and find a second valid opening of the commitment.

However, for a perfectly hiding commitment scheme, there exists a random string for each possible input, for which the commitment scheme will produce the given commitment. [so the receiver can learn nothing about the received message]

This contradicts the condition for the perfectly binding commitment, i.e. the two are mutually exclusive.

### Network Security
- The authentication headers in IPv4 protects the integrity and authenticity of IP datagramms, but not their confidentiality.
- IPv4 allows to encapsulate payloads to protect confidentiality and optionally also integrity.
- IPSec provides authetication of IP addresses, whereas TLS provides only server-side authentication by default.

# Information Security Part 2

## Introduction
- security policy: what behavior is, and is not, allowed
- secuity mechanisms: mechanisms used to enforce the policy

Specification: $P$
System: $S$
Correct: $S \vDash P$

We can also make the environment explict, with a _malicious environment_ $E$.

$S || E \vDash P$

### CIA properties
- Confidentiality (Secracy): No improper disclosure of information
- Integrity: No improper modification of information
- Availability: No improper impairment of functionality / service

### Security Properties
- Authenticity - we know who sent the message
- Non-repudiation / accountability
- Plausible deniability - is contrary to non-repudiation and can be seen as weak form of secracy
- Privacy
- Anonymity: secrecy of principal identities
- Data protection: personal data is only used in certain ways

## IBM Secure Coprocessor
- multiple layers
- higher layers cannot compromise lower layers
- layers and owners each have keypair

Properties
1. **Outbound authentication:** It must be possible to distingush between a message from a layer $i$ with a particular software environment on a particular untampered device from a message from a clever adversary.
2. **Inbound authentication:** Suppose $A$ has ownership of a software layer in an untampered device, then only $A$ or a designated representative can load code into that layer in the device.
3. **Access to secrets:** Secrets belonging to layer $i$ are accessible only by code that Authority $i$ trusts executing on an untampered device in an appropriat execution environment.

The code in each layer can be updated remotly by the authority controlling that layer. Code update commands are signed by the authority (inbound authentication). Upon successful completion the authority receives a _receipt_ signed by the card (coutbound authentication). We the card ID, layer number, code version and a hash of installed code. We implicitly trust in the card manufacturer.

There might be a case, where the authority A does not trust new software at lower layers. One possibility to achieve this is to force a reboot of the card into a state where A can query and confirm the configuration of the lower layers after an update. The query should return a receipt including a code hash and version number for each layer. The control flow is passed to layer L code only after A's confirmation.

## Unilateral vs Multilateral Securty
- unilateral security
- secuirty properties given normally attributed to a single system
- security seen as unilateral problem: the system is secure if no attacker can cause it to deviate from its intended behavior
- multilateral secuirty
- goal is to protect particpants from each other
- security best described via trused third party
- challenge is implementing multilateral secuirty is to eliminate the need for this party. Typically this is not done by having the participants simulate the party in some secure way

## Threads
- Confidentiality -> Interception
- Integrity -> Modification, Fabrication
- Availability -> Interruption (e.g. DDOS)

## Security Protocols

- sign and encrypt, doesn't work, because the recipient can decrypt, re-encrypt and forward the message
- encrypt and sign, doesn't work, because we can intercept the mssage remove the signature and self sign the message


## Otway-Rees protocol

## Kerberos

- create a secure channel between $A$ and $B$ whenever they each share a key with the truseted authority $T$.


Kerberos requires that the user sends to the service an authenticator: its identity and a timestamp encrypted with the session key K provided by the ticket-granting server. K is guaranteed to be fresh and intended for communications between the user and the service only. In addition, the service should store recent authenticators to prevent replay attacks.

## SSL / TLS

Goal: secrecy, integrity, (optionally mutal) authentication
Protocols: HTTP(S), SMTP, IMAP,...

TLS guarantees: secrecy, integrity, and mutual authentication (given the client’s certificate)

### Handshake
1. Setup, negotiate cipher (DH, RSA, ...)
2. Exchange server certificate
3. Client key excahnge
(optional) authentication of client using client certificate
4. Finish, establishing session

#### Two-channel authentication
e.g. SMS TAN
Problem: can be fooled with man in the middle attack / pushing website. Even if the user has to confirm via SMS we could try man in the middle the sms converstaion.

### Session-Aware User Authentication
Idea: Make user authentication depends on both user's credentials and on state information from session where credentials are sent. Server can check if session in which it receives credentials is the same used by user when sending credentials.

## IPsec
- Authentication Header (AH) protects the integrity and the authenticity of IP packets
- Encapsulating Security Payload (ESP) protects confidentiality and optionally also integrity

### IPSec vs SSL
IPSec provides a secure connection a the IP-level. In more detail, IPsec provides authentication, confidentiality, and integrity for IP packets. Therefore, the loss of one (or more) IP packet has no influence on the other packets sent by the two parties . In contrast, SSL works at the transport-level. The loss of a packet, in this case, causes the abortion of the SSL stream.

### Modes
- Transport Mode: Encrypts only the data portion (payload) of each packet, but leaves the header untouched.
- Tunnel Mode: Entire IP packet encapsulated within the ESP. New header may contain different IP address, e.g. security gateway. Old header, as well as payload, encrypted (and optionally authenticated).

## Definitions

- PKI: Public Key Infrastructure
- MITM: Man in the Middle
- IKE: Internet Key Exchange Protocol

## Protocols

### S/MIME
- authentication
- message integrity
- non-repudiation of origin (using digital signatures)
- privacy
- data security

### Andrew Secure RPC protocol

Establish a fresh shared symmetric key, between two parties already using a symmetric key.

We can not simply send a new key over the channel, as this message can be used in a replay attack. The two parties therefore send back and forth a nonce.


The messages can no longer be replayed unless the same nonce is beeing used.

### CA (Denning & Sacco)

Another key exchange party, using a sever as an authority.


This sheme can be attacked, as we the authenticity guarantee is independent from the content of the message.


This can be fixed, by adding information about the recipient with the authenticity guarantee.


### IKE protocol

Typical key establishment protocol, where two parties use a master key to establish shared keying material.

1. Phase: Two parties negotiate an SA, they agree on keying material mechanisms (e.g. crypto-algorithms, hash functions,...).
2. The SA is used to create _child SAs_ to encrypt and authenticate further communications.

## Public-Key Infrastructures

## E-Voting

- Receipt-Freeness: It is not possible for a voter to construct a receipt that he can give to the adversary to prove how he voted.
- Coercion Resistance: Even if the adversary can give active inputs/commands to the voter during the procedure, it is not possile for the voter to prove how he voted

### Benaloh Cryptosystem

## Exercises

### Treats and Risk analysis

Threat agents, threats and vulnerabilities to email correspondence within your organisation

Threat agents: criminal organizations, espionage
Threats: access / modification of messages
Vulnerabilities: unprotected cleartext / non signed messages (sender adress can easily be spoofed)

### Dolev-Yao attacker
The Dolev-Yao attacker cannot break cryptography, which is assumed to be perfect, i.e., it cannot invert hash functions and it needs to know the correct key to encrypt or decrypt or sign messages. On the other hand, it has full control over the network, being able to read and block all messages, re-combine messages and inject the resulting message into the network. The Dolev-Yao attacker can also compromise selected agents and learn their keys. (We then want the considered security properties to hold between non-compromised agents.)

A similar technique has purportedly been used by the FBI to listen in on cell phone communications. They set up a rogue mobile cellular base station which induces nearby cell phones to connect to it instead of a cell phone tower. This allows the FBI agents to control and eavesdrop on the communication.

### Agreements
#### Non-injective agreements
A protocol guarantees that an agent _a_ in role _A_ has non-injective agreement with an agent _b_ in role _B_ on a set of data items _ds_ if, whenever _a_ completes a run of the protocol, apparently with _b_, then _b_ has been running the protocol, apparently with _a_, and _b_ was executing role _B_ in his run, and the two agents agreed on the data values corresponding to all the variables in _ds_.

A non-injective agreement is given, if they agree on who is in which role and they agree on all the data exchanged.

*an injective agreement, implies an non-injective agreement

#### Injective agreements
Injective agreements are non-injective agreements with the added requirement that for each run of the agent _a_ in role _A_ there is a _unique_ corresponding run of agent _b_. This uniqueness requirement rules out replay attacks on _a_.

Further - than beeing an non-injective agreement - , for every run f A there must be a unique run of B, i.e. the message needs to contain a unique number / nonce.

### Burrows-Abadi-Needham (BAN) logic
1. verification of message origin
2. verification of message freshness
3. verification of the origin's trustworthiness

### Network Security
- what security guarantees are provided by authentication headers in IPv4?
- _authenticity_ and _integrity_ of IP packets
- What security guarantees are provided by encapsulating security payloads in IPv4?
- confidentiality of IP packets
- Defense-in-depth is a strategy of using different security mechanisms to protect a system. In the case of networks, defense-in-depth consists of using
- technical mechanisms like firewalls or intrusion detection systems
- physical mechanisms like securing rooms containing servers, and
- administrative solutions like employee training and internal communications
The idea is that each mechanism should compensate the flaws and limitations that another mechanism may have.

- what does an X.509 certificate bind together?
- An X.509 certificate binds an owner name with a public key.

- What are the differences between the authentication guarantees provided by TLS and those provided by IPSec?
- IPSec provides authentication of IP addresses, whereas TLS provides authentication of entities like people, companies, servers, etc.
- IPSec provides mutual authentication, whereas TLS provides only server-side authentication by default

### Access Control

#### ACLs
ACLs (access control lists) are one way to encode (or represent) an access control matrix. They cannot, however, encode more expressive security policies. An access control list is a list of pairs of subjects and permissions associated to each object.


As they rely on a matrix, they do not scale well and they can not specify fine-grained constraints.

#### Capability Lists
As they rely on a matrix, they do not scale well and they can not specify fine-grained constraints.

#### Role-Based Access Control
RBAC shifts the conceptual focus away from the notion of assigning rights to individual users of the system to the notion that actions map to jobs within an organizational structure (i.e., role). The main advantages of this approach compared to the matrix model are the following.
- small data structures
- better manageability through separation of static and dynamic parts of the access control relation. In the matrix model, creating a new subject means filling the corresponding row of the matrix with the rights the subject should have on every object. In RBAC, it is often enough to assign a few roles to the subject, and the fine-grained part remains static in the permission assignment.
- As the number of roles is usually smaller than the number of subjects, creating and deleting objects requires less effort in RBAC than in the matrix model (the permission assignment is smaller than the full matrix).

#### Bell-LaPadula Model
BLP focuses on data confidentiality and controlled access to classified information, in contrast to the Bida Integrity Model which describes rules for the protection of data integrity. Entities are divided into subjects and objects. The model defines one discretionary access control (DAC) rule and two mandatory access control (MAC) rules with three security properties:

1. The Simple Security Property states that a subject at a given security level may not read an object at a higher security level.
2. The star (\*) property states that a subject at a given seurity level may not write to any other object at a lower security level.
3. The Discretionary Security Property states that use of an access matrix to specify the discretionary access control.

- read down: a subject with label x_s can only read information in an object with label x_o if x_s dominates x_o.
- write-up: a subject with label x_s can only write information to an object with label x_o if x_o dominates x_s.

### Pederson Commitment Scheme
- setup [receiver]
- pick group $G$ in which discrete log problem is hard
- pick generators $g, h \in G$, $h = g^a$
- public parameters: $G, g, h$
- commit [sender]
- pick random $r$
- output $c = g^xh^r$
- reveal [sender]
- output (x, r)
this scheme is perfectly binding and semantically binding

## RSA encryption
1. choose two large primes $p,q$
2. calculate $n = pq$
3. calcualte $\varnothing(n) = (p-1)(q-1)$
4. chose a private key $e$, with $1 \leq e \leq \varnothing(n)$ and $gcd(\varnothing(n), e) = 1$
5. compute public key $d$, with $de \mod \varnothing(n) = 1$

$Enc_{e,n}(m) = m^e \mod n$
$Dec_{d,n}(c) = c^d \mod n$

weakness:
- textbook RSA is deterministic i.e. every encryption on the same msg produces the same ciphertext
...

## ELGamal encryption
In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange.

- generation
- Alice generates an efficient description of cyclic group G of order q with generator g.
- encryption
- decryption

// TODO:

## Dictionary

- Nonce: An arbitrary number that can be used only once. It is used to ensure that old communications cannot be reused in replay attacks. They might also be used as initialization vectors and in hash functions.
- abelian group: a group in which the result of applying the group operation on two elements does not depend on the order in which they are written
- cyclic group: $\exists y \in G, \forall h \in G, \exists n \in \mathbb{N} : g^n \ h$
- Secrecy: When communicating with an uncompromised agent, the attack can't learn m.
- TLS is implemented in user space, not OS. Can also authenticate users.
- Defense-in-depth is the strategy of using different security mechanisms to protect a system. For networks:
- technical (firewall...)
- physical (securing rooms...)
- administrative (exployee training...)
- X.509 binds an owner name with a public key.
- Non-reputation: If a statement author can not dispute the authorship / validity of a contract.
- The Diffie-Hellman (DDH) assumption is a computational hardness assumption about solving the discrete logarithm in cyclic groups.
- forward secrecy: given the long-term secret of an honest communication party it is not possible for an adversery to decrypt preciously intercepted communication with other parties
- a semantically secure cryptosystem is one where only negligible information about the plaintext can be feasibly extracted from the ciphertext.

## Facts
- AES is based on a substitution and permutation network
- ELGamal encrpytion system is an asymmetric key encryption algorithm for public-key encryption

## Attacks
- CPA (Chosen-Plaintext Attack): We assume that the attacker can choose random plaintexts to be encrypted and obtain the corresponding ciphertexts.
- COA (Ciphertext-Only Attack): We assume that the attacker only has access to ciphertexts.
- CCA (Chosen-Ciphertext Attack): We assume that the attacker can request the decryption of some ciphertext.
- KPA (Known-Plaintext Attack) assumes that the attacker has plaintext, ciphertext pairs.