# Lösungsvorschlag Information Security FS17: Unterschied zwischen den Versionen

## 1. True / False

a) False, md5 is broken, as SHA1
b) False
c) False, subpolynomial
d) False, everything is wrong
e) True
f) True (you can use hardcore bit of all kind of one way functions)
g) True, superpolynomial
h) False, perfectly hiding and semantically binding
i) True
j) False (? unsure, we can call them stream ciphers, isn't it?)

To f) what about a one way function f(x) = h(x)||0^10 where h is SHA3

## 2 Historic Ciphers

#### a)

Caesar's Shift: 26 keys
Substitution Cipher: 26! keys
Vignere Cipher: ${\displaystyle \approx 26^{|k|}}$ where |k| is the key length

#### b)

Caesar's Shift: 1 pair
Substitution Cipher: 25 different pairs
Vignere Cipher: |k| subsequent letter pairs

## 3. Pseudorandomness and One-Way Functions

#### a)

Informal
A pseudorandom permutation maps a bitstring of length n to another seemingly random bitstring of length n.
Formal
The oracle chooses uniformly at random scenario 1 or 0. If 1, it outputs the true random permutation of the input m of length n i.e. PRP(r). If 0, it chooses a random key k and outputs the psudorandom permutation ${\displaystyle F_{k}(m)}$. After some number of repetitions, the distinguisher needs to decide for the given string if the oracle chose 0 or 1. The permutation is pseudorandom if for every polynomial-time turing machine D, we have that ${\displaystyle |P(D(r')=1)-P(D(PRP(r))=1)}$ is negligible in n.

#### b)

We prove that g is a one-way function by reduction to f which we assume to be one-way. Assume that we have a adversary for inverting g(x1,x2), then we can build a adversary for inverting f according to the image below:
          +----------------------------------------+
|                                        |
|                +----------------+      |
f(x1)   |       f(x1),x2 |                |  x1  |
+-------->-------+-------->+                +-------------->
|      ^         |                |      |
|      |         |                |      |
|      |         |                | x2 + |
|  +---+         | Adversary      +--->+ |
|  x2 is u.a.r.  | for g(x1,x2)   |    + |
|  generated     +----------------+      |
|                                        |
+----------------------------------------+

All processing within the adversary can be done in polynomial time. The existance of this contradicts our assumption that f is one-way.

## 4. Block Ciphers

#### a)

Assuming your key mixing layer uses XOR:
M⊕K0⊕K1⊕... Kr
K0⊕K1⊕...Kr effectively compresses into one, single key
Equivalent to M⊕K in terms of security
More importantly, since the only key addition layer is at the front, and the S-box and permutation layer are assumed to be publicly known, a single known plaintext attack could break the construction: Simply encrypt the known block of information and then invert the permutation and S-box layers on the ciphertext. This leaves us with M⊕K, which, since we know M, means we can do M⊕M⊕K and recover K. Granted, K is only the XOR sum of K0⊕K1⊕...Kr, but we don't actually need the values of K0,K1,...Kr individually. We only need their sum in order to perform the encryption/decryption operation.
It is important for there to be key addition layers before and after the application of a round function, if the round function is to provide security. They do not have to be immediately prior to or after each application, i.e. adding a key, iterating the core permutation a bunch of times, then adding a key again is a valid strategy as well.
(taken from https://crypto.stackexchange.com/questions/40855/substitution-permutation-network-construction)

#### b)

The adversary can then change only one bit and know that only the content of this block is changed. If the whole message would change, it would likely turn into the wrong format.
Another issue is that if only one block changes, so blocks are independent, and you can shuffle them as you want, to create forged messages.

## 5.

#### a)

If we omit L the construction is no longer collision resistant. We can create simple collisions by using padded bits as part of the message. E.g. consider two messages 1 and 10, which both get padded to the same 1000 for blocksize of 4 bits and thus have the same hash.

#### b)

Assuming h is collision resistant, this is collision resistant, as we either have the same ${\displaystyle z_{B}}$ in which case we have a different length, meaning the output is different. The downsides are increased output length and leaking the message length.

bfiedler: I'd prove this differently:

Let ${\displaystyle m,m'}$ be messages, ${\displaystyle z_{B}||L=H^{s}(m)}$ and ${\displaystyle z_{B}'||L'=H^{s}(m')}$.

Case 1: ${\displaystyle L\neq L'}$, no collision in H trivially for ${\displaystyle m,m'}$.

Case 2: ${\displaystyle L=L'}$

If ${\displaystyle z_{B}=z_{B}'}$, then there must exist ${\displaystyle i\in \{0,..,B\}}$ such that ${\displaystyle m_{i}||z_{i-1}\neq m_{i}'||z_{i-1}'}$ but ${\displaystyle h(m_{i}||z_{i-1})=h(m_{i}'||z_{i-1})}$, so we found a collision in ${\displaystyle h}$. Thus, because ${\displaystyle h}$ must be collision resistant, so must be ${\displaystyle H}$.

## 6.

#### a)

Let ${\displaystyle QR_{G}}$ denote the set of quadratic residues of G.

Associativity and commutativity are inherited from G.

Neutral element ${\displaystyle 1\in QR_{G}{\text{ since }}1^{2}=1}$

Closure if ${\displaystyle x,y\in QR_{G}{\text{ then there exist a,b, s.t. }}x=a^{2},y=b^{2}{\text{ then }}x*y=a^{2}*b^{2}=(a*b)^{2}{\text{ therefore }}x*y\in QR_{G}}$

Inverse let ${\displaystyle x^{-1}}$ denote the inverse of x.

If ${\displaystyle x\in QR_{G}=>x=a^{2}=g^{2i}}$ where g is a generator.

If ${\displaystyle x*x^{-1}=1{\text{ then }}x*x^{-1}=g^{k*(p-1)}}$ for some k. Note that k*(p-1) is even since p is a prime.

${\displaystyle x*x^{-1}=g^{2i}*g^{y}{\text{for some y. y needs to fulfill 2i + y = k*(p-1), therefore y needs to be even which means }}x^{-1}\in QR_{G}}$

#### b)

The adversary sees ${\displaystyle g^{x},g^{y}}$. From those she can compute the parity of x and y and therefore the parity of xy. This reduces the keyspace by 50%

The parity is computed as follows: ${\displaystyle {\text{x is even}}<=>g^{x}\in QR_{G}<=>(g^{x})^{(p-1)/2}=1}$

bfiedler: You can go further and compute the entire private key in polynomial time using a sophisticated square root algorithm, determining the next bit, and so on.

## 7.

#### a)

${\displaystyle \phi (n)=(11-1)\cdot (13-1)={120}}$. We know that ${\displaystyle d\cdot e\equiv _{120}1}$, therefore ${\displaystyle d=7}$. The private key is ${\displaystyle (7,143)}$ We should use the extended Euclidian algorithm to find the inverse.

#### b)

Consider two messages ${\displaystyle m_{0},m_{1}}$ and a key pair ${\displaystyle \{(e,n),(d,n)\}}$. Then ${\displaystyle Enc(m_{0})=m_{0}^{e}\mod n=c_{0}}$ and ${\displaystyle Enc(m_{1})=m_{1}^{e}\mod n=c_{1}}$ then ${\displaystyle c_{0}\cdot c_{1}=(m_{0}^{e}\mod n)\cdot (m_{1}^{e}\mod n)=(m_{0}^{e}\cdot m_{1}^{e})\mod n=(m_{0}\cdot m_{1})^{e}\mod n=Enc(m_{0}\cdot m_{1})}$
Solution: we use random padding e.g. PKCS#1. This solves the problem.
Random fact: This is partial homeomorphic encryption.

#### c)

No, it is deterministic. If we use random padding, as explained in b, it is believed to be CPA secure.

## 8.

#### a)

Not possible, because we need sk(B) to find K(A,B) which is not in ${\displaystyle has(IK\cup M)}$

#### b)

Let ${\displaystyle H\equiv has(IK\cup M)}$.
 XXXXXXXXXXXXXXX   XXXXXXXXXXXXXXX
XX    T0     XX   XX    T0     XX
XX         XX     XX         XX
XXXXXXXXXX        XXXXXXXXXX
[N4,N3] € H    [N4,N3] € H
Snd+-----------+  +-----------+Fst
N3 € H   N4 € H
+--------------+Pair
[N3,N4] € H


T0 is defined as follows:
  +-----------------------+   +---------------+
{[N4,N3]}pk(C) € IK u M     sk(C) € IK u M
El+-----------------------+   +---------------+El
{[N4,N3]}pk(C) € H       sk(C) € H
+--------------------------------------+Dec
[N4,N3] € H


#### c)

                                             XXXXXXXXXXXXXXXXXXXXXX
XX                XX
XX      T0      XX
XX            XX
XXXXXXXXXXXXX
[N4,N3] € H
+----------+Snd
{sk(A)}h(N3) € IK u M     N3 € H
el+---------------------+  +--------+Hash
{N1}pk(A) € IK u M      {sk(A)}h(N3) € H        h(N3) € H
el+----------------+     +---------------------------------+Dec
{N1}pk(A) € H           sk(A) € H
+---------------------------------+Dec
N1 € H


## 9.

#### a)

${\displaystyle A\to B:B}$

Any message that does not contain sk(A) or sk(B) would work.

#### b)

${\displaystyle B\to A:N_{1}}$

${\displaystyle A\to B:\{B,N_{1}\}_{sk(A)}}$

#### c)

A → B: {B, N_1}_sk(A)

Injective agreement is not possible. We need some challenge response mechanism otherwise the message can always be replayed! The previous wrong solution doesn't work because a nonce is only unique from the senders pov.

#### d)

${\displaystyle A\to B:\{A\}_{sk(A)}}$

${\displaystyle B\to A:\{s\}_{s}}$

## 10.

#### a)

Alice's claim holds. The definition implies that when A is communicating with a compromised agent, then the intruder may learn m.

I don't agree. Secrecy claims only hold between honest agents. See Formal Methods For Information Security (mod3-protocol-properties - Slide 37) So precisely for this trace, the property does not hold. I'm seeing your point, that it may hold because it's not a "good situation" but I think there is a difference between a property that holds for a trace and for a protocol. For the protocol, the secrecy claim of Alice holds, for this run it doesn't. Precisely, because the following property is not verified (the Honest claim is not verified)

[Source : mod3-protocol-properties - Slide 37 ]

Different opinion: According to slide 61 of Part-II_Week-1_Protocols1.pdf: "Whenever an agent performs a role, trying to communicate with a non-compromised agent, and executes a secrecy claim of a term x, then the intruder may not learn x." As the premisse of the implication is false in this case, the whole statement is true, therefore the secrecy claim holds.

Answer : It seems closer to what was expected. I'm convinced.

#### (b)

1.

I can MITM the traffic between A and B acting as the responder for A and as intiator for B.
The exchanged messages are:
${\displaystyle A\rightarrow B:A,\{N\}_{pk(B)}}$ (intercepted by ${\displaystyle I}$)
${\displaystyle I\rightarrow B:I,\{N\}_{pk(B)}}$
${\displaystyle B\rightarrow I:\{N\}_{pk(I)}}$
${\displaystyle I\rightarrow A:\{N\}_{pk(A)}}$

2.

From B's perspective, only B itself or its partner (initiator) knows the nonce, hence secrecy of N is guaranteed from B's perspective.
Scyther finds an attack on the protocol, using an evil initiator Eve who knows the nonce after a run with B. I am not sure if this is considered an attack on secrecy - see this for more discussion.
Alternative Solution: A possible attack looks as follows:
${\displaystyle A\rightarrow I:I,\{N\}_{pk(I)}}$
${\displaystyle I\rightarrow B:A,\{N\}_{pk(B)}}$
${\displaystyle B\rightarrow I:\{N\}_{pk(A)}}$
${\displaystyle I\rightarrow A:\{N\}_{pk(A)}}$
As B tries to communicate with non-compromised agent A (in the responder role), this attack violates the definition of secrecy, since I learned N.

## 11.

Property Automaton exists?
1 yes
2 no
3 yes

### (1)

${\displaystyle Q={\mathcal {P}}(S\times O)}$

${\displaystyle Q_{0}=\{\emptyset \}}$

${\displaystyle \delta (q,read(s,o))=\{q\cup \{(s,o)\}\}}$

${\displaystyle \delta (q,write(s,o))={\begin{cases}\emptyset ,&{\text{if }}(s,o)\notin q\\\{q\},&{\text{else}}\end{cases}}}$

### (3)

${\displaystyle Q={\mathcal {P}}(S\times O)}$

${\displaystyle Q_{0}=\{\emptyset \}}$

${\displaystyle \delta (q,write(s,o))=\{q\}}$

${\displaystyle \delta (q,read(s,o))={\begin{cases}\emptyset ,&{\text{if }}\exists s'\in S.(s',o)\in q\land l(s')

## 12.

### (a)

A subject s can only read an object o if the security label of the subject dominates the security label of the object.

### (b)

Subject Label
${\displaystyle s_{1}}$ ${\displaystyle ({\text{Public}},\emptyset )}$
${\displaystyle s_{2}}$ ${\displaystyle ({\text{Public}},\{A,B\})}$
${\displaystyle s_{3}}$ ${\displaystyle ({\text{Secret}},\{A,B\})}$
${\displaystyle s_{4}}$ ${\displaystyle ({\text{Public}},\{B\})}$
${\displaystyle s_{5}}$ ${\displaystyle ({\text{Secret}},\{A\})}$

### (c)

${\displaystyle o_{1}}$ ${\displaystyle o_{2}}$ ${\displaystyle o_{3}}$ ${\displaystyle o_{4}}$
${\displaystyle s_{6}}$ w r

Alternative solution:

${\displaystyle o_{1}}$ ${\displaystyle o_{2}}$ ${\displaystyle o_{3}}$ ${\displaystyle o_{4}}$
${\displaystyle s_{6}}$ r, w r, w

This works since subject needs to have the exact label (Secret, {A}) and (Public, {A}) at the same time.

bfiedler: This is very elegant, I'll definitely remember this.

## 13.

Alice needs to construct the following message: ${\displaystyle \{R_{3},\{R_{2},\{R_{1},\{R_{0},m\}_{pk(Bob)},Bob\}_{pk(Z)},Z\}_{pk(W)},W\}_{pk(X)}}$

Note that ${\displaystyle \forall i\in \{0,1,2,3\}.R_{i}}$ is a random value. The values ${\displaystyle \{Bob,Z,W\}}$ denote addresses of the corresponding mixes and Bob.

These random values are necessary to have randomized encryption i.e. to ensure the same message over the same hops encrypts to a different ciphertext. The IDs are included such that the mixes know who to forward the message to.

## 14.

### (a)

${\displaystyle \{1,13,14,15,16\}}$ are all possibilities.

### (b)

#### 1

Good placement. The webserver is protected by firewall from the Internet (securing it against threats from outside) and the company network is protected by a firewall from the webserver, so that even if somebody compromises the webserver, the company network is protected.

#### 2

Ideally, a VPN server should live in its own DMZ (De-militarized zone), so that it cannot interfere with company-critical services such as the database server. However, in the given diagram the VPN server cannot be placed in another network without severely obstructing the remote employees possibilities.

### (c)

No protection.

Case 1: BYOD-policy may infect network with malware from somewhere else.

Case 2: Firewall cannot read traffic between HTTP + TLS connections from clients inside the network (also cannot decrypt PGP-encrypted E-mails, etc.).

### (d)

#### 1

X509 certificates guarantee mutual authentication, ensuring both the client and server verified each other's identity.

#### 2

Using self-signed certificates may cause users to experience issues (connecting with the VPN for example) because the certificate is not trusted by one of the (OSes) root of trust.