# Lösungsvorschlag Information Security FS09

## Aufgabe 1 True / False Questions

1. True, this follows from the triangle equation: ${\displaystyle 0\leq \Delta ^{D}(R,T)\leq \Delta ^{D}(R,S)+\Delta ^{D}(S,T)=0}$.
2. False, its not posible to create dots.
3. True, if you can easily compute the discrete logarithm, then you can derrive ${\displaystyle x_{A}}$ from ${\displaystyle y_{A}=g^{x_{A}}}$ and use this to compute the shared key ${\displaystyle K_{AB}=y_{B}^{x_{A}}}$
4. False, because B does not Trust T, B cant know if a message from A which is passed trough T is really from A.
5. False, we can only interfer ${\displaystyle Trust_{A,Y,\min(2,3)}=Trust_{A,Y,2}}$.
6. False, if x is distributed uniformly then we can use ${\displaystyle x'=1\dots 1}$ to solve ${\displaystyle f(x')=f(x)}$ in at least half of the situations.
7. False Siehe Def. von one-sided key. B weiss nicht, wer alles seinen public key kennt, aber A kann nicht davon ausgehen, dass nur B auch seinen pK kennt.
8. True, the Authentication Server is on-line, since it distributes session keys. (in-line would mean forwarding messages, off-line might mean a certificate authority).

## Aufgabe 2

a)

i) See script, Def. 2.1.

ii) This is not a one-way function since for an image f(x1,x2) = x1*x2 = y, an algorithm that outputs the pair (x1',x2') = (y/2,2) if y is even (and something arbitrary otherwise) will succeed with high probability, i.e. P(f(x1',x2') = y) is not negligible. This is since x1, x2 are chosen uniformly at random, so one of them is even (and, with this, their product) with high probability.

b)

A possible construction is ${\displaystyle h(x_{1}\mid \mid x_{2}\mid \mid x_{3}):=f(x_{1})\mid \mid g(x_{2})}$, where ${\displaystyle x_{i}\in \{0,1\}^{m}}$ for ${\displaystyle i\in \{1,2,3\}}$. We can use the same argument as in example 2.2 of the script to proof that the function is one-way. Furthermore any pair ${\displaystyle (x_{1}\mid \mid x_{2}\mid \mid x_{3},x_{1}\mid \mid x_{2}\mid \mid x_{3}')}$ with ${\displaystyle x_{3}\neq x_{3}'}$ is a collision.

Note: In the construction above, it does not matter which function is one-way and which one is collision resistant.

## Aufgabe 3

a)

i) c = m^e (mod n). Using euclid's extended algorithm, we can compute d with k*phi(n) + d*e = 1, i.e., the multiplicative inverse of e mod phi(n). Raising c to d gives c^d = (m^e)^d (mod n) = m^(d*e) (mod n) = m, where in the last step, we used Fermat's theorem (Corollary 2.15)

ii) We have the equations n = p*q and phi(n) = (p-1)*(q-1) = p*q - p - q + 1 = n - p - q + 1. Since we know both n and phi(n), we can solve these equations for p and q. This leads to the formula

${\displaystyle p,q={\frac {\pm {\sqrt {(n-\varphi (n)+1)^{2}-4n}}+(n-\varphi (n)+1)}{2}}}$

b) Alice sends g^x, and Bob sends g^y, while g in this case is 2. Writing down 2^1, 2^2...(mod 11) gives 2 - 4 - 8 - 5 - 10 - 9 - 7 - 3 - 6 - 1. Therefore, x = 6 since 2^6 (mod 11) = 9 and y = 7 since 2^7 (mod 11) = 7, the shared secret key is 2^(6*7) = 2^42 (mod 11) = 2^ (42 mod 10) = 2^2 = 4. (In the last step, Fermat was used, but you can see it easily when writing down the generated numbers as above.)

## Aufgabe 4

a)

i) (A,B): We use the following chains, according to Propositions 3.2 and 3.3: A .<-- T5 .==. B , with dots on A's side, and B must trust T5

A <-->. T4 <-->. T6 ==. B. with dots on B's side, and A must trust T4 and T6

From these chains, we can establish a secure channel A .<-->. B

(B,C): B -->. T7 <--. C, with dots on C's side, and B must trust T7.

From this, we can get the channels with a dot on C's side, i.e., a confidential channel B -->. C and an authenticated channel B <--. C

According to Proposition 3.3., a secret channel can't be achieved since there is no path from B to C where there is always a dot on B's side.

b) Without public key cryptography, we can no longer apply a transformation of the form A .--> B to A .<-- B

For (A,B), we can still derive A.<-- B, and A -->. B , from which we can get a secure channel A .<-->. B

(B sends a key over the confidential channel to A, giving A.==B , which A then uses for a MAC, transforming A.== B and A -->. B to A .-->.B , a secret channel over which a secret key A.==.B can be sent, giving a two-sided secret channel A.<-->.B)

For (B,C), we can still derive an authenticated channel B <--. C if B and T7 transform their channel B -->. T7 to B <--. T7

(B transmits a key over the confidential channel which T7 uses as MAC). From B <--. T7 <--. C, we can obtain B <--. C if B trusts T7.

However, the confidential channel B -->. C can no longer be obtained as we need public key cryptography to transform T7 <--. C into T7 -->. C.

## Aufgabe 5

a) See Exercise Sheet 6 b) Proof for Aut(A,B):

Aut(A,W), Trust(A,W,3), Rec(W,X,2) |- Trust(A,X,2)

Aut(A,X), Trust(A,X,2), Cert(X,Y) |- Aut(A,Y)

Aut(A,W), Trust(A,W,3), Rec(W,Y,1) |- Trust(A,Y,1)

Aut(A,Y), Trust(A,Y,1), Cert(Y,Z) |- Aut(A,Z)

Aut(A,X), Trust(A,X,2), Rec(X,Z,2) |- Trust(A,Z,1)

Aut(A,Z), Trust(A,Z,1), Cert(Z,B) |- Aut(A,B)

Problem with Aut(A,C):

Since the only certificate for C is from V, we need Trust(A,V,i) with i >= 1 in order to derive Aut(A,C).

There is, however, no way to derive this, since the only recommendation for V comes from Y. We can only derive trust of level 1 for Y, which won't let us accept their recommendations.

A trust arrow of level 1 from A directly to V would make the derivation possible.

## Aufgabe 6

a) See transformations 2.16. (digital signatures) and 2.14. and 2.15. (Diffie Hellman, two variants, which can be interpreted as with or without client certification)

b) A . --> B and A --> B are transformed to A . <-- B using public key encryption.

Then, A .<-- B is transformed to A .== B by B sending a key to A.

Finally, A .== B is transformed to A .--> B again by using a MAC.

c) There are two important advantages:

1. Non-repudiation: When using digital signatures, A can declare herself liable for documents she signs. With public key encryption and MAC, this is not possible since B knows the key A uses for her MAC, he sent it to her himself.

2. Scalability: Digital signatures solve the quadratic blow-up problem; when A signs a message, everyone in possession of A's authentic public key can check it.

When A needs to use MACs, she needs to have a (one-sided) key for everyone who wants to check the authenticity of the message.

## Aufgabe 7

a) Public-key revocation is a way for a certificate authority to say that a certain public key they signed is no longer considered valid by them, for example if it might have been compromised.

One scheme is a Certificate Revocation List, short CRL, a public directory where a certificate authority keeps a signed list of all revoked public keys. The CRL is checked before a certificate is considered valid.

## Aufgabe 8

a) Consider two leaf nodes A and B. For secure communication between A and B, channels A .--> B and A <--. B are needed that can be established if A trusts every entity on the path from the root to B and B trusts every entity on the path from the root to A (including the root, not including A and B themselves).

In current browsers, the root authorities are configured in the browser, so the browser vendor may be seen as a root authority. Also, complete transitive trust is assumed, so all entities in the tree are automatically trusted.

b) An example is the "Millionaire's problem". Two millionaires want to find out who is richer without having to tell each other how rich they are, i.e., keeping their wealth secret.

## Aufgabe 10

A simple type-flaw attack may be found if we make additional assumptions about the length of the fields, that the length of (sid, I, R, S) equals the length of seskey.

Then, we can intercept the first message and reflect it back to I after removing the component "I", i.e. we send sid, {ni, sid, I, R, S}k(I,S) back to I. I misinterprets the bits (sid, I, R, S) as a session key and will use it, but since sid is sent in the clear and we assume I, R and S are known, that "session key" is known by the adversary.

Note that this additional assumption might not be acceptably and a different attack must be found.

## Aufgabe 11

b) t in H --> hash(t) in DY(H).

This rule idealizes one-wayness since there is no rule to obtain t from hash(t).

Also, it idealizes collision-freeness since "hash(t)" is assumed to be a unique value, that can only be derived from t.

d) An encrypted message is an "atomic block" in the sense that the attacker can do nothing other than decrypting it with the right key. Its contents can't be changed if the attacker doesn't possess the key. This isn't realistic since also parts of a ciphertext may be changed.

e) {t1}t2 in H -> For all t1' in g(t1), {t1'}t2 in H

## Aufgabe 12

a) Authentication: If R receives a missile launching command, I has sent the message at CurrentTime, and it has not been changed. In particular, the TargetCountry received by R is the same as sent by I.

Secrecy: The TargetCountry remains secret between I and R.

b) Since the TargetCountry doesn't appear in the hashed values, it may be changed by an attacker and the hash will still be accepted. The attacker's chances of guessing a ciphertext for an existing country may be low, but in missile launching, this risk can't be taken.

c) The attacker can compute hash(CurrentTime,I,ni). So he can try all possible values for password(I,R) and check if the last part of the decrypted message equals hash(currentTime,I,ni). If it does, the targetCountry field of this message is the one that was sent by I.

## Aufgabe 13

### (a)

The standard TLS session allows the user to secretly and authenitcally communicate with a server. If now the adversary has inserted his own root certificate he can issue a certificate for his evil website that immitates the original server the user wants to communicate with. The adversary can issue a certificate for his own website using the public key of the installed root certificate and the user will trust the evil site. So both secrecy and authentication fail, since the keys are negotiated with the adversary and he can even modify the original user requests.

### (b)

Now the adversary can delete the certificate of the CA that issued the certificate of the original website the user wanted to interact with. Now whenever the user tries to contact the correct site he will get an error because the trust chain could not be verified. So the user will stick to the evil site.

## Aufgabe 14

### (a)

One can define the two relations ${\displaystyle \rho _{M}\subseteq \ Subjects\times Roles}$ and ${\displaystyle \rho _{P}\subseteq \ Permissions}$ to decompose the users from the permissions.

## Aufgabe 15

### (a)

If there are two conflicting companies there should be no consultant that works for both companies.

### (b)

Before giving access to the database the system checks whether the intersection of companies that conflict with c and companies that hire s is empty. If it is empty the consultant can be hired, else not.