# Lösungsvorschlag Information Security FS14

Wechseln zu: Navigation, Suche

# 1

• a) False, Alice should use Bob's public key.
• b) False, MACs only provide authenticity and integrity
• c) False, public key crypto is way more inefficient
• d) True
• e) False, anyone can compute hash functions
• f) True, a pseudorandom function is a pseudorandom permutation without the requirement of being an actual permutation
• g) True
• h) False, it relies on the DDH assumption
• i) True
• j) False, the encryption function is no injection (ciphertext 7)

# 2

The adversary computes $c'$ by:

• $k\leftarrow c\oplus m_{0}$
• $c'\leftarrow m_{1}\oplus k$

# 3

## (a)

We build a distinguisher D who is given access to an oracle, which answers to our queries $m$ with either $F_{1}(k,m)$ for a randomly chosen $k$ or $F'(m)$ (where $F'$) is a truly random function. We now query the oracle for any message $m$ and get back $f$. We outputs 1 for "pseudo-random" if the last bit of $f$ is 1. Our distinguisher D works in constant time and therefore is a legitimate polynomial time attacker.

The probability of success is

$P[D{\text{ is correct}}]=P[F_{1}\cap {\text{ last bit }}=1]+P[F'\cap {\text{ last bit }}=0]\geq {\frac {1}{2}}+{\frac {1}{4}}={\frac {3}{4}}$

This is non-negligible. Therefore $F_{1}$ is no PRF.

## (b)

We recall the security definition of a PRF. A PRF is called secure if there is no polynomial time probabilistic attacker that can win the following game: The attacker is given access to an oracle. The oracle either chooses a truly random function $f$, or a PRF with a random key $f_{k}$. The attacker can query the oracle for messages m and the oracle answers with either $f(m)$ or $f_{k}(m)$. In the end, the attacker wins the game if he can tell correctly what function the oracle used with a probability which is non negligibly better than 0.5.

We use this definition in a reduction proof. We assume that $F_{2}$ is not a secure PRF and build an attacker for $F$. From the definition we know that there exists a distinguisher $D$ which (when given access to an oracle) can tell if we used either $F_{2}$ or a truly random function.

We build a distinguisher $D'$ which can tell $F$ apart from a truly random function $F'$. We now instantiate the distinguisher $D$ and answer oracle queries in the following way: If $D$ asks for $m$, we ask our oracle for ${\overline {m}}$. When our distinguisher D made its decision, we output the same decision.

Our $D'$ only adds constant overhead to $D$, which is why it is a legitimate polynomial time distinguisher.

To see why this construction of $D'$ has the same probability of winning as $D$, we just have to recall the definition of $F_{2}$. If the oracle of our distinguisher $D'$ has chosen the function $F$ (and not the truly random function), then we simulate a perfect oracle for $D'$ for function $F_{2}$.

# 4

## (a)

To encrypt block i of the message compute

$c_{i}=F_{k}(IV+i)\oplus m_{i}$

The encryption of the "counter" is used as a key stream to encrypt the message using xor. The IV is optional and used to randomize the encryption and make it IND-CPA secure.

## (b)

• Parallel block encryption and decryption possible
• Errors in one block do not propagate
• No additional randomness needed during encryption
• Random Read Access

# 5

## (a)

The attacker must output a pair $(m^{*},\tau ^{*})$ such that ${\text{Verify}}(m^{*},\tau ^{*},k)=1$ and $m^{*}\not \in \{m_{1},...,m_{w}\}$

## (b)

No it is not. The attacker asks for the tags to two distinct messages $m_{0},m_{1}$ of equal length and obtains the tags $\tau _{0},\tau _{1}$ for them. He divides the messages and tags at the same position (of course at block border) and joins the first half of $m_{0}$ with the second half of $m_{1}$. The same procedure is performed with the tags. Now $(m_{0}^{\text{first-half}}\ ||\ m_{1}^{\text{second-half}},\tau _{0}^{\text{first-half}}\ ||\ \tau _{1}^{\text{second-half}})$ is a valid message the attacker has not queried for.

Alternative proof using two concrete messages:

We ask the oracle to encode the two messages $m_{0}=0^{2*240}$ and $m_{1}=1^{2*240}$. The two tags (see definition of MAC) will be $t_{0}=F_{k}(0^{*}||2^{*}||0^{240})||F_{k}(1^{*}||2^{*}||0^{240})$ and $t_{1}=F_{k}(0^{*}||2^{*}||1^{240})||F_{k}(1^{*}||2^{*}||1^{240})$ (where $x^{*}$ denotes the 8-bit encoding of the integer x). Now we can trivially compute a valid tag for $m'=0^{240}||1^{240}$ by setting $t'=F_{k}(0^{*}||2^{*}||0^{240})||F_{k}(1^{*}||2^{*}||1^{240})$.

# 6

## (a)

• It does not protect from replay attacks.
• Any receiver can impersonate Alice and do a broadcast himself, since he owns the key.

## (b)

We need to assign the keys for user $i$ to set $S_{i}$ such that for all pairs of users, no key set is included in the other and vice versa. Formally $\forall i,j{\text{ it holds that }}i\neq j\Rightarrow S_{i}\nsubseteq S_{j}$. A possible implementation would be that Alice shares two keys with every recipient $B_{i}$ such that two recipients have at most one key in common.

## (c)

The set of all distinct pairs is $S_{p}=\{(S_{i},S_{k})|i\neq k\wedge i,k<|S|\}$. Hence, the number of possible pairs is $|S_{p}|=\sum _{i=1}^{|S|-1}|S|-i$. For 5 keys, Alice can generate different pairs for 10 recipients, thus fulfilling the requirements.

The above argument is delicate in my opinion. I would argue via a concrete number of keys per recipient. As those pairs are binomialy distributed the highest number of combinations lies in the middle. Hence I define $\forall i,|S_{i}|=\lfloor l/2\rfloor {\text{ meaning for a given }}l{\text{ we can have }}n\leq {l \choose l/2}$ recipients. In our example with $n=10,l=5{\text{ we have }}{5 \choose 2}={\frac {5!}{2!3!}}={\frac {5\cdot 4}{2}}=10\geq 10=n$.

# 7

## (a)

• Modulo addition is defined as $\oplus =(\mod N)\ \circ \ +$ which is a function $\oplus ::\mathbb {Z} _{N}\to \mathbb {Z} _{N}$. Alternative proof: Addition of integers $a,b$ yields another integer. Say $a,b\in \mathbb {Z} _{N}:a\oplus b=c$. Now $c=(a+b)\mod N\implies c\geq 0\land c.
• Identity is 0 which is inherited by the integers ($a\oplus 0=(a+0)\mod N=a\mod N=a$ since $a\in \mathbb {Z} _{N}$ )
• Commutativity is inherited by the integers ($a\oplus b=(a+b)\mod N=(b+a)\mod N=b\oplus a$)

## (b)

$G{\text{ is cyclic}}:\Longleftrightarrow \exists g\in G\ \forall h\in G\ \exists n\in \mathbb {N} \ g^{n}=h$

## (c)

• $3^{1}=3$
• $3^{2}=2$
• $3^{3}=6$
• $3^{4}=4$
• $3^{5}=5$
• $3^{6}=1$

Therefore $\mathbb {Z} _{7}^{*}$ is cyclic with the generator $3$

ALTERNATIVELY

• $5^{1}=5$
• $5^{2}=4$
• $5^{3}=6$
• $5^{4}=2$
• $5^{5}=3$
• $5^{6}=1$

Therefore $\mathbb {Z} _{7}^{*}$ is cyclic with the generator $5$

# 8

## (a)

Given $c=m^{e}{\text{mod N}}$, it is hard to compute m if we do not know $\phi (N)$.

## (b)

Let $p,q$ be prime, $N=pq,\phi (N)=(p-1)(q-1)$ in

• public key: $(e,N)$ where $\gcd(e,\phi (N))=1$
• private key: $(d,N)$ where $ed=1\mod \phi (N)$

Now, encryption works as follows: $Enc_{(e,N)}(m)=m^{e}modN$

Decryption works similarly: $Dec_{(d,N)}(c)=c^{d}modN$

## (c)

$p$ and $q$ can only be 3 and 7.

• $\phi (21)=12\Rightarrow \gcd(5,12)=1\Rightarrow e$ is ok.
• $5\cdot 17=85,85\mod 12=1\Rightarrow d$ is ok.

# 9

## (a)

i. F) Reasoning: First-preimage resistance would be sufficient as the hash must be one of the chain and hence we have a given hash. (Note that weak collision resistance implies second-preimage resistance and second-preimage resistance implies first-preimage resistance.)

ii. T) Reasoning: It's not sufficient to precompute one rainbow table for the whole database as two identical passwords with different salts result in different hashes.

## (b)

Given the long-term secret of an honest communicating party it is not possible for an adversary to decrypt previously intercepted communication with other parties.

## (c)

ToDo:
Explain stuff here.
Alle momentan zu editierenden Einträge werden hier gesammelt.

## (d)

i. prevention, ii. resilience, iii. detection and recovery, iv. deterrence

# 10

a) A definition obtained from (): key freshness A key is fresh (from the viewpoint of one party) if it can be guaranteed to be new, as opposed to possibly an old key being reused through actions of either an adversary or authorized party.

Yes, if we assume that the old key K_AB wasn't used for a long time as is common and K_AB' is in a message enciphered by K_AB. (really unsure...)

I think not since with the attack detailed in b) the K_AB' is then not "new data", thus I wouldn't consider it a fresh key.

Alternative solution: I think an attacker can do a simple replay attack: Steps 1-3 are performed as usual. However then the Attacker can intercept B's message in step 4 and replace it with an old one. There is nothing in this message that guarantees freshness. (I think this is the correct solution...)

Comment on alternative solution: In message 4 there is a nonce that is supposed to be fresh. If A compares that to previously used nonces, an old message would be detected.

b) No. Adversary Eve could to a replay attack and replace the original message B->A: {K'_AB, N'_B}_K_AB with the first message and thus make A agree on the key A. (I think this is called an "reflection attack", because the message goes back to its originator...)

No, I think it's a typeflow attack (reuse the format of the message to alter the communication). A reflection attack would use one party has a "service" (to decrypt, encode etc.) and usually use another thread to do so.

c) No. A can be fooled but B creates his K'_AB itself. Therefore B can never be convinced to agree on a different secret than K'_AB.

d) add B to message 4, or add the hash of K'_AB in the 4th message. Or B signs the key in the 4th message. (not 100% sure)

I think the solution above does not prevent the attacker from replaying an older message sent by B. My idea would be to add another nonce $N_{A}'$ which couples steps 1-3 with step 4. So we would have:

3: A->B : $\{N_{B}+1,N_{A}'\}_{K_{AB}}$

4: A->B : $\{K_{AB}',N_{B}',N_{A}'+1\}_{K_{AB}}$

# 11

## (a)

Using a second-preimage attack he could replace the entry for the previously accessed document $e{\text{ by an entry }}e'{\text{ s.t. }}e'\neq e{\text{ and }}H(e')=H(e)$.

## (b)

Insertion and verificationn now take both $O(\log n)$ where before insertion took $O(1)$ and verification took $O(n)$.

## (c)

Prepend i to the input before hashing.

# 12 SSL

## a)

Insecure if password is insecure: Since you have input output pairs you can guess a password. If passwords are insecure, so you only need to guess polynomial many, then the protocol is insecure. Otherwise, it's secure.

secure I guess? The attacker has no way in finding out the password hash and therefore can't generate any message himself. Also the observation of the protocol doesn't let the attacker find out the key or the password hash.

I don't think so. A passive attacker can bruteforce J (if a weak password is used) and check if the password is correct by generating the MAC with J and verifiyng the tag.

Usually, precondition are that crypto is considered as "Perfect" for protocol modeling (c.f. Formal Methods for Information Security). Therefore, even in the real world this assumption would be true, it's behind the scope of the analysis. So I believe this one is "secure" under these asumptions. And J is not a password, but a hash of a password. Which is usually above 100 bits and with high entropy. (We may argue about rainbow table .. but well)

## b)

Secure: You cannot guess the password (like in a) because you don't have input output pairs.

An attacker can alter messages (there is no MAC that ensures integrity) and the client and server would "agree" on different keys.

Seems secure to me, since an attacker doesn't have J and thus can't correctly encrypt his own secret for DH. Even if an attacker alters the message he can't make any use of it, since he doesn't know the actual plaintext of what he sent. He also doesn't have a good way to try and brute force J as he doesn't know the plaintext of the two messages being sent.

## c)

Insecure: Eavesdropping attack: In the first message, send g^s mod p with your own s. The client will send you back g^c mod p, {J}_K. You can get K because K=g^(cs) mod p so you can decrypt the J.

A man-in-the-middle attacker can intercept $g^{s}\mod p$ and instead send $g^{s'}\mod p$ (where he knows $s'$). Now, the attacker can compute $K$ and therefore gains knowledge over the password hash $J$.

## d)

Insecure if certificate can be forged: If an attacker can obtain a fake certificate, then the protocol is insecure. Attack is similar to the one in c: Send fake certificate. Send g^s with own s, and sign it with the private key for your fake certificate. Then get g^c mod p, {J}_K which you can decrypt because you know K = g^(cs) mod p.

secure I guess?

I don't think so. short key (56bit DES) -> brute-force attacks are possible

# 13

## a)

Stack canaries are used to detect a stack buffer overflow before execution of malicious code can occur. A, at program start randomly chosen, small integer is placed in memory just before the stack return pointer. Most buffer overflows overwrite memory from lower to higher memory address, so in order to overwrite the return pointer, the canary value must be overwritten. This value is checked to make sure, it has not changed before a routine uses the return pointer on the stack.

## b)

A capability list stores to each subject a list of permissions (on objects) and an ACL stores to each object a list of permissions and users.

## c)

OS layer

• One might want a quick overview on all apps requesting a particular permission.
• If a permission changes (e.g. due to a OS upgrade) one can easily select and handle the affected apps.

application layer

• Uninstalling an app is faster as only the permission list for this app must be deleted (not every "file" has to be checked for permission given to this app) and the same holds for the installation of a new app.
• If only on app is launched at a time we are only interested in the permissions of this specific app as it is the only instance possibly able to request a "file".

## d)

storage covert channel: TR can lock a particular file to signal motion and unlock it otherwise s.t. AB can check if the file is currently locked or not and act accordingly.

timing covert channel: TR could use 100% of the CPU to signal motion and sleep otherwise s.t. AB could measure time passed between two context switches and send messages over the network respectively.

# 15 DDoS attacks

## b) Coremelt attack

### (i)

"[T]he attacker uses a collection of subverted machines sending data to each other to flood and disable a network link [...] There are 3 steps to launching a Coremelt attack:

1. Select a link in the network as the target link.

2. Identify what pairs of subverted machines can generate traffic that traverse the target link.

3. Send traffic between the pairs identified in step 2 to overload the target link."

Direkt zitiert von The Coremelt-Attack (Studer, Perrig), S. 3.

### (ii)

"an attacker can elude capability- and filtering-based DoS defenses because all traffic is desired by the receiver".

Wieder von The Coremelt-Attack (Studer, Perrig), S. 3.

### (iii)

"After acquiring the capability, the legitimate traffic requires no additional work and can proceed unhampered by the DoS attack. If we were to adopt puzzles for every packet, the puzzles may become the bottleneck rather than the links. During a Coremelt attack, the target link will increase the re- sources senders need to invest to complete puzzles, effectively degrading the performance of any machine using the target link."

Immer noch The Coremelt-Attack (Studer, Perrig), S. 14f.