# 1 True or False

• a) T
• b) F
• c) F
• d) T
• e) F
• f) F (see discussion)
• g) F
• h) T
• i) T
• j) T

# 2

a) The claim is incorrect. Consider a set of plaintexts ${\displaystyle M=\{a,b\}}$ with distribution ${\displaystyle P[M=a]={\tfrac {1}{4}}}$ and ${\displaystyle P[M=b]={\tfrac {3}{4}}}$. If we encrypt using any perfectly secret encryption scheme, we know for every ${\displaystyle c\in C}$:

${\displaystyle P[M=a|C=c]=P[M=a]\neq P[M=b]=P[M=b|C=c]}$

b) An encryptions scheme is CPA-secure if no poly-time probabilistic Turing Machine adversary A can win the following game with probability at most ${\displaystyle 0.5+\varepsilon (n)}$ where ${\displaystyle \varepsilon }$ is negligible:

• In the learning phase, A can get encryptions for chosen plaintexts from an oracle.
• In the challenge phase, A can supply two messages, receives the encryption for a random one of them, and has to guess which one it was.

# 3 Block Ciphers

Using OFB basically constructs a stream cipher. Starting with a random seed, a stream of blocks is generated by pushing block i through the block cipher to generate block i+1. With the stream of blocks, the message gets encrypted using XOR. Decryption works in a similar way: First, the same stream is generated using the seed supplied together with the ciphertext. Then the ciphertext gets XOR'd with the stream to get back the plaintext.

# 4 Message Authentication Codes

• a)

First, the message length is prepended to the message. Then the message is pushed through CBC mode encryption, but discarding all ciphertext blocks except the last one. Instead of using PKCS#5 padding like in usual CBC mode, the message is padded using 0.

• b)

Assume the attacker has gotten message-tag pairs (m,t) and (m2,t2). For the message (m || m'), where m' is m2 with the first block XOR'd with t, t2 is also a valid tag. Thus, the attacker can generate a valid message-tag pair and the scheme is insecure.

# 5

• a)

Divide m into blocks of size L, padded with 0 in the end. Add a block containing the length of m (not considering the padding). Then, starting with a predefined, arbitrary IV, always take 1 new message block and the output of the last use of h, and use h on their concatenation. When all blocks are used up, the last output of h is H(m).

• b)

Assume ${\displaystyle {\hat {H}}}$ is not collision resistant. This means we can find a collision, x and x', such that ${\displaystyle {\hat {H}}(x)={\hat {H}}(x')}$.

Case distinction:

${\displaystyle H(x)=H(x')}$: We have also found a collision in H, which should be collision resistant.

${\displaystyle H(x)\not =H(x'):H(H(x))=H(H(x'))}$. Because ${\displaystyle H(x)\not =H(x')}$, this is a collision in the second use of H, which should be collision resistant.

# 6 Pseudorandomness

• a)

Assuming the two parties share a key k. XOR the message with G(k) both for encryption and decryption. This can only be done once to stay secure. For repeated use, concatenate key with IV and supply the IV together with the ciphertext.

• b)

The attacker can learn ${\displaystyle F_{k}(0)}$ and ${\displaystyle F_{k}(1)}$. If they only differ in the last bit, he can output that the function is not random, if they don't he can output that the function is random. Because it is very rare for a truly random function to have this behaviour, he wins with a high probability.

# 7 Meet-in-the-Middle Attack

• a)

For a message-ciphertext pair (m,c) the attacker calculates ${\displaystyle F_{k}(m)}$ and ${\displaystyle F_{k}^{-1}(c)}$ for all possible keys. He sorts the two lists and finds matches. The keys used to generate the matches are candidate keys. The attacker filters these candidate keys using 2 more message-ciphertext pairs.

This attack only scales exponentially with |k|, not with 2*|k|, the security does not increase through double-DES.

• b)

From ${\displaystyle 2^{56}\cdot 2^{56}}$ key pairs, only about ${\displaystyle 2^{48}}$ will match on a given (m,c) pair, because the probability of a random key pair matching is ${\displaystyle 2^{-64}}$. ${\displaystyle (2^{56}\cdot 2^{56}\cdot 2^{-64}=2^{48})}$

• c)

The number of candidate keys is reduced to ${\displaystyle 2^{48}\cdot 2^{-64}=2^{-16}}$ by adding a second (m,c) pair on average. As we know to have at least one matching key, we are left with only one possible key with high probability.

# 8

• a)

The adversary intercepts the messages from Alice and acts as if he is Bob. At the same time, he starts another run of the protocol with Bob, pretending to be Alice. Because the messages carry no authentication, this is not detectable for Alice and Bob.

• b)

${\displaystyle c_{2}/c_{1}=m_{2}/m_{1}}$, thus ${\displaystyle m_{2}=m_{1}*c_{2}/c_{1}}$. The adversary can't recover x, because he gets no more information about x compared to just intercepting a correct run of ElGamal.

# 9

We use the following abbrevations: ${\displaystyle hA=has(IK\cup M)}$, ${\displaystyle A=(IK\cup M)}$.

• a)
                                              ${\displaystyle \{K_{1}\}_{pk(I)}\in A}$                   ${\displaystyle sk(I)\in A}$
-----------------------${\displaystyle el.}$       --------------------${\displaystyle el.}$
${\displaystyle {\{K_{2},N_{1}\}}_{K_{1}}\in A}$                           ${\displaystyle \{K_{1}\}_{pk(I)}\in hA}$                   ${\displaystyle sk(I)\in hA}$
--------------------el.              ------------------------------------------------------------ ${\displaystyle dec}$
${\displaystyle {\{K_{2},N_{1}\}}_{K_{1}}\in hA}$                                         ${\displaystyle K_{1}\in hA}$
--------------------------------------------------------------------------- ${\displaystyle dec.}$
${\displaystyle (K_{2},N_{1})\in hA}$
---------------------------- ${\displaystyle fst.}$
${\displaystyle K_{2}\in hA}$


• b)
                                                          ${\displaystyle \{K_{1}\}_{pk(I)}\in A}$                ${\displaystyle sk(I)\in A}$
------------------${\displaystyle el.}$     --------------------${\displaystyle el.}$
${\displaystyle \{K_{1},N_{1}\}_{K_{1}}\in A}$                 ${\displaystyle \{K_{1}\}_{pk(I)}\in hA}$              ${\displaystyle sk(I)\in hA}$
----------------------${\displaystyle el.}$    ----------------------------------------------------- ${\displaystyle dec}$
${\displaystyle \{K_{1},N_{1}\}_{K_{1}}\in hA}$           ${\displaystyle K_{1}\in hA}$
----------------------------------------------${\displaystyle dec.}$
${\displaystyle (K_{2},N_{1})\in hA}$
--------------------------${\displaystyle snd.}$
${\displaystyle \{N_{2}\}_{h(N_{1})}\in A}$                        ${\displaystyle N_{1}\in hA}$
------------------${\displaystyle el.}$           --------------------${\displaystyle hash}$
${\displaystyle \{N_{2}\}_{n(N_{1})}\in hA}$                      ${\displaystyle h(N_{1})\in hA}$
-------------------------------------------------${\displaystyle dec.}$
${\displaystyle N_{2}\in hA}$


• c)
• d)

# 10 Secrecy

• a)
• PK(B):
• i) F
• ii) F
• iii) T
• PK(A): The protocol is not functional
• K(A,B):
• i) F
• ii) F
• iii) T

(Disagree with these response ! See discussion !)

• b) When communicating with an un-compromised agent, the attacker can't learn m.

More precisely (slightly adapted from lecture slides and added emphasis): A term x is secret (from the point of view of A) if, whenever A tries to communicate with a non-compromised agent, the intruder may not learn x.

# 11

• a)
• i) No, n could've come from an attacker
• ii) No, implied from i)
• iii) Yes, because {A,n} got signed by B, he must've communicated to A once
• iv) Yes, because n is fresh each time, it must be a one-to-one matching
• b) For injective agreement, the runs of the protocol of A and B have a one-to-one matching. Non-injective agreement only says that the other party has ran the protocol with you with these values in the past.

# 12

• a)

No on all of them, there is no guarantee on any message on who sent it and B doesn't have to send back the nonce it got, confirming it's identity.

• b)

n. Whoever can send back n has to have been able to decrypt it before. Only B is able to do that. Because n is fresh, B must have been recently running the protocol.

# 13 Role-based access control

• a)

Role1: {p2, p3, p5}, {u3, u4, u6}

Role2: {p1, p4, p6}, {u1, u2, u3}

Role3: {p1, p3, p5}, {u2, u5, u6}

• b)

3. There are 6 different permission sets. To get that, you must at least have ${\displaystyle log_{2}(6)}$ roles, in the best case.

# 14 FunBAC vs RBAC

• a)

Bob and Charlie can Read File, Search Directory and Modify database

• b)

Alice and David can Read file, Bob can Search Directory and Modify Database, Charlie can Update serer

• c)

g2 from b) can't be expressed with just one role.

• d)

She is wrong. A counterexample would be: Only one role R1, Alice is in R1. R1 can Read File.

# 15 Security Automata

• a)

${\displaystyle Q_{0}:=\{(f_{\bot },\bot ,\bot )\}}$

Where ${\displaystyle f_{\bot }}$ is the function mapping every ${\displaystyle u\in U}$ to ${\displaystyle \bot }$.

• b)

${\displaystyle \delta }$ is defined as follows:

{\displaystyle {\begin{aligned}\delta ((f,cu,t),{\text{announce}}(u,t'))&={\begin{cases}\{(f',cu,t)\}&{\mbox{if }}u\neq cu,{\text{ where }}f'{\text{ is the function obtained from }}f{\text{ by changing the value of }}f(u){\text{ to }}t'\\\{(f,cu,t)\}&{\mbox{otherwise}}\end{cases}}\\\delta ((f,cu,t),{\text{startUse}}(u))&={\begin{cases}\{(f',u,0)\}&{\mbox{if }}cu=\bot ,{\text{ where }}f'{\text{ is the function obtained from }}f{\text{ by changing the value of }}f(u){\text{ to }}\bot \\\emptyset &{\mbox{otherwise}}\end{cases}}\\\delta ((f,cu,t),{\text{release}}(u))&={\begin{cases}\{(f,\bot ,\bot )\}&{\mbox{if }}cu=u\\\emptyset &{\mbox{otherwise}}\end{cases}}\\\delta ((f,cu,t),{\text{tick}})&={\begin{cases}\{(f_{tick},cu,t)\}&{\mbox{if }}t=\bot \land (\forall u\in U{\text{ }}f(u)=\bot \lor f(u)>0)\\\{(f_{tick},cu,t+1)\}&{\mbox{if }}t<1\land (\forall u\in U{\text{ }}f(u)=\bot \lor f(u)>0)\\\emptyset &{\mbox{otherwise}}\end{cases}}\\\end{aligned}}}

${\displaystyle {\text{Where }}f_{tick}{\text{ is the function obtained from }}f{\text{ by changing }}\forall u\in U{\text{ the value of }}f(u){\text{ to }}f(u)-1{\text{ if }}f(u)\neq \bot }$

bfiedler: für ${\displaystyle {\text{tick}}}$ sollte es entweder ${\displaystyle f_{tick}(u)>0}$ oder ${\displaystyle f(u)>1}$ in der Bedingung heißen.

# 16

 Heuristik "Secure Communication with Humans" wasn't covered in FS17

# 17

• a)

TLS is implemented in user space, not in OS. Can also authenticate users (IPsec can only authenticate IP addresses).

• b)

Defense-in-depth is the strategy of using different security mechanisms to protect a system. For networks, consists of :

• technical mechanisms (firewalls, IDS...)
• physical mechanisms (securing rooms ...)
• administrative solutions (employee training, communications...)

Each mechanism should compensate the flaws and limitations that another mechanism may have.

• c)

Spam Filtering, Conditional Forwarding, (virus scanners...)

• d)

No guarantees! The ISP can emit any certificate and impersonate any website.

• e)

It binds an owner name with a public key.

• f)

Individual verifiability: each voter can verify that his vote is recorded as a cast. In traditional voting there is no way to do that.

• g)

Let ${\displaystyle M_{1}}$ and ${\displaystyle M_{2}}$ denote the addresses of the mixes. Alice ${\displaystyle A}$ wants to be an anonymous sender, Bob ${\displaystyle B}$ is the one who replies to her. ${\displaystyle K_{B}}$ is Bob's public key. Alice chooses the following path: ${\displaystyle A\rightarrow M_{1}\rightarrow M_{2}\rightarrow B}$.

Alice first sends the following message into the network: ${\displaystyle \{R_{1},M_{2},\{R_{2},B,\{K_{x},ADDR\}_{K_{B}}\}_{K_{2}}\}_{K_{1}}}$, where ${\displaystyle ADDR=\{R_{K_{2}},M_{1},\{R_{K_{1}},A\}_{K_{1}}\}_{K_{2}}}$ and ${\displaystyle R_{1},R_{2},R_{K_{1}},R_{K_{2}}}$ are random strings. Alice keeps ${\displaystyle K_{x},R_{K_{1}}{\text{ and }}R_{K_{2}}}$ locally stored!

Bob can now send his message back, by sending the following message into the network: ${\displaystyle \{R_{0},M\}_{K_{x}},ADDR}$

${\displaystyle R_{0}}$ is again a random string. The mix servers then decrypt the outermost layer of ADDR, and encrypt the message of Bob with the provided key ${\displaystyle R_{K_{1}}{\text{ or }}R_{K_{2}}}$. Since Alice has locally stored ${\displaystyle K_{x},R_{K_{1}}{\text{ and }}R_{K_{2}}}$, she can decrypt the final message ${\displaystyle \{\{\{R_{0},M\}_{K_{x}}\}_{R_{K_{2}}}\}_{R_{K_{1}}}}$.