# Lösungsvorschlag Information Security FS17

## Inhaltsverzeichnis

## 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?)

## 2 Historic Ciphers

#### a)

- Caesar's Shift: 26 keys
- Substitution Cipher: 26! keys
- Vignere Cipher: 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 . 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 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. BlockCiphers

#### 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 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 be messages, and .

Case 1: , no collision in H trivially for .

Case 2:

If , then there must exist such that but , so we found a collision in . Thus, because must be collision resistant, so must be .

## 6.

#### a)

Let denote the set of quadratic residues of G.

Associativity and commutativity are inherited from G.

**Neutral element**

**Closure**
if

**Inverse**
let denote the inverse of x.

If where g is a generator.

If for some k. Note that k*(p-1) is even since p is a prime.

#### b)

The adversary sees . 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:

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)

- . We know that , therefore . The private key is We should use the extended Euclidian algorithm to find the inverse.

#### b)

- Consider two messages and a key pair . Then and then
**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

#### b)

- Let .

XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XX T0 XX XX T0 XX XX XX XX XX XXXXXXXXXX XXXXXXXXXX [N3,N4] € H [N3,N4] € H Snd+-----------+ +-----------+Fst N3 € H N4 € H +--------------+Pair [N3,N4] € H

bfiedler: I don't have anything to say except fuck the guy/girl who wrote this question.

- T0 is defined as follows:

+-----------------------+ +---------------+ {[N3,N4]}pk(C) € IK u M sk(C) € IK u M El+-----------------------+ +---------------+El {[N3,N4]}pk(C) € H sk(C) € H +--------------------------------------+Dec [N3,N4] € H

#### c)

XXXXXXXXXXXXXXXXXXXXXX XX XX XX T0 XX XX XX XXXXXXXXXXXXX [N3,N4} € H +----------+ {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)

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

#### b)

#### c)

#### d)

## 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:

- (intercepted by )

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:

- 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)

### (3)

## 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 |
---|---|

### (c)

w | r |

Alternative solution:

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:

Note that is a random value. The values 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)

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.

#### 3

The network administrator can either:

- Request a signature from one of the trusted CAs (or request a new certificate from them).

- Create a company CA, which will be installed on all the necessary devices via an authenticated channel (tech support for example). Then the self-signed certificate can be verified successfully by all devices on which the company CA has been installed as a root certificate.