Key exchange

Question 1

How to attack a protocol that has a key establishment with a trusted third party?

Answer 1

• Eve can record the particular message, and also record the token sent
• Eve can store all of these messages and then spend computational power on breaking the session key which breaks integrity and confidentiality
  
  • could be computational or break the system
• If Eve manages, Bob would believe he’s talking to Alice
• You can have adversaries impersonating users

Question 2

How do we securely exchange a key without a trusted third party?

Answer 2

The output of the protocol are session keys kA and kB, generated by Alice and Bob respectively. These keys a re strings of bits (0 or 1), and the length of these strings is determined by the security parameter n. if Alice and Bob execute the protocol honestly, they will end up with the same key. This shared key K can then be used for secure communication between Alice and Bob, ensuring that even if the communication channel is observed by others, only Alice and Bob can decrypt the messages sent between them. The use of a probabilistic protocol makes it difficult for an attacker to predict or reproduce the key, thereby providing security for the key exchange process.

Question 3

How do we establish the security of a key exchange protocol?

Answer 3

A key exchange protocol is secure in presence of an eavesdropper, if for all probabilistic polynomial-time* adversaries A their success probability is only negligibly* better than ½ to guess if a random number of bits is the key between two random bits.

Question 4

If we want to brute force a merkle puzzle key exchange, how many brute force decryption attempts do we need to solve the puzzle? Is the Merkle puzzle key exchange actually secure?

Answer 4

• Needs 2^l brute force decryption attempts to solve
  
  • l = actual length of the random bits in the key

Its only secure against eavesdropping

Question 5

Give an example of a symmetric approach to key exchange and an asymmetric approach

Answer 5

Symmetric: Merkle Puzzle Key Exchange
Asymmetric: Diffie Hellman Key Exchange

Question 6

Briefly explain the Merkle Puzzle Key Exchange

Answer 6

• Alice generates a large number of cryptographic puzzles, making it impractical for an eavesdropper to solve all of them within a reasonable time frame.
• The structure of the puzzle ensures that each puzzle is unique and that the key is securely embedded within it.
• Alice sends all puzzles to Bob, Bob randomly selects one puzzle, solves it, sends x as the identifier. Alice, because she can solve all of the puzzles quickly because she generated them looks up x

Question 7

In Merkle Puzzle Key Exchange, what is the workload for Alice and Bob and what is the workload for Eve?

Answer 7

For alice and bob: O(n) = 2^32 because thats the amount of puzzles generated.

For Eve: O(n^2) = 2^64
Quadratic Gap best known for black-box symmetric block ciphers

Question 8

What is the order of a generator?

Answer 8

Order of g in (Z_p)^* is the size of the generated group <g> (the group generated by g)</g>

Question 9

p = 5, g = 3: {1, 3, 3^2, 3^3}. What is the order of <g></g>

Answer 9

ord(g) = 4

Question 10

What is the difficult algebraic expression that makes the Diffie-Hellman problem intractable?

Answer 10

given g^a and g^b, its computationally unfeasible for the adversary to compute g^{ab}

Question 11

Given
p = 1013
g = 3
a = 372
b = 268
can you compute the session key for the Diffie hellman key exchange?

Answer 11

417
sagemath:
A = (ga) % p
B = (gb) % p

sesh_key = (Ba) % p
sesh_key1 = (Ab) % p

Question 12

In order for a Diffie-Hellman key to be secure, what should the bit size be?

Answer 12

Use at least 3072-bit keys for DH/RSA.

Question 13

What is the best known algorithm to break DH/RSA? What is the expected running time?

Answer 13

General Number Field Sieve
Expected running time O(exp(log(n)^{1/3}))

Question 14

What type of attack is Diffie-Hellman vulnerable against?Why? and how can we prevent against it?

Answer 14

Man -in -the-Middle Attack
This can happen because Diffie Helman does not have authentication/ its secure against eavesdroppers but needs additional security against active adversaries.

We can protect against it by having message confidentiality and message integrity

Question 15

how can you create a secure channel?

Answer 15

Extract-then-Expand: Takes the session key and extracts the symmetric cipher keys and mac keys from random salt, Generate one separate key per use and direction

Question 16

How would you employ cryptographic primitives to gain confidentiality, secrecy, and integrity?

Answer 16

• Confidentiality: Encryption (cipher) (using symmetric because we need it to be efficient and quickly)
• Integrity: MAC

Question 16

Create a cyclic group G := (Z p )* with a generator g, where g is meant to create the entire group with order p-1. We set p to 147573952589676412931. This setup will be used for the following exercises with the Diffie Hellman Key Exchange: g = 106090574620621767288, p = 147573952589676412931, q = 4327489.

1. Establish the exponent group of the group setup above. {1,2,…,q−1}
2. Create secret exponents a and b for Alice and Bob, by choosing them uniformly at random from the exponent group.
3. Create the Diffie Hellman half-keys A and B for Alice and Bob.
4. Compute the final session K key for both sides of the key exchange.
5. Convince yourself that the key exchange is correct.

Answer 16

1. The exponent group here is the set {1,2,…, q −1}, meaning all the integers from 1 up to q−1.
2. a = 456
   b = 500
3. A: 112538468946762750816
   B: 82480805734946653587
4. 54648765558687598099
5. Theyre equal

Question 17

What security properties do we expect of a secure channel?

Answer 17

→ Message integrity - It is assured who sent the message. Manipulations of messages will be detected.

→ Message confidentiality - Messages can only be read by the two intended participants.

The two main properties we expect from secure channels are message confidentiality and message integrity.

Question 18

• What is the preferred method to establish key materials for a secure channel?

Answer 18

→ Compute four keys for symmetric ciphers and message authentication codes, with a salted key derivation function, one separate key for each cryptographic primitive and communication direction.

Correct. Pay attention to the need to have a separate key for each direction and the need to use a random salt in the KDF to boost entropy.

The way forward is:

• Use a strong key derivation function with a random salt.
• Create four keys, one for each communication direction (A->B and B->A) as well as for each cryptographic primitive.
• Use symmetric ciphers and message authentication codes.

Question 19

What are foundational laws of number theory we keep encountering in asymmetric cryptographic algorithms and protocols?

Answer 19

→ Fermat’s Theorem - Modulo a prime p, any element raised to p-1 will be congruent to 1.

→ Euler’s Theorem - For any composite modulus N, any element raised to the group order will be congruent with 1.

→ Drawing the e-th root. Finding the element that you’d need to raise to e to gain the desired outcome.

Question 19

What methods are preferable to establish a secure channel?

Answer 19

→ Encrypt-then-MAC - Encrypt the messages first with a symmetric cipher then apply a MAC to the cipher text.

Question 20

With the pocket calculator you would also use in the exam (or a comparable one), compute 20011 mod 23.

Answer 20

→ 1
20011 % 23 in sagemath

Question 21

Compute the multiplicative inverse of 19 mod 251 with Fermat’s theorem.

Answer 21

-> 185
(19^249) % 251 in sagemath

Question 22

Which computations are feasible in polynomial time?

→ Compute a^e mod N with square-and-multiply
→ Compute a*b mod N
→ Compute a^e mod N with repeated multiplication. (Naive exponentiation)
→ Compute the Extended Euclidian Algorithm (EAA)
→ Computing a+b mod N

Answer 22

→ Compute a^e mod N with square-and-multiply

Correct. Square-and-multiply modular exponentiations take cubic complexity.

→ Compute a*b mod N

Correct. This can be done with square complexity.

→ Compute a^e mod N with repeated multiplication. (Naive exponentiation)

Incorrect. The complexity is O^(2n), exponential.

→ Compute the Extended Euclidian Algorithm (EAA)

Correct (square complexity)

→ Computing a+b mod N

Correct. The complexity is linear.

Question 23

For a composite modulus N = 4460543, composed of the prime factors p=2111 and q=2113, find the corresponding multiplicative inverse d of e=23 to be able to draw the e-th root efficiently.

Answer 23

If we know N, p, q and e

we can compute the eth root, by computing phi(N) = (p -1) x ( q - 1)

then get the modular inverse by doing EEA(e, phi(N) )

4262567

from sympy import mod_inverse

N = 4460543;
p = 2111;
q = 2113;
e = 23;

phi_N = (p - 1)*(q-1);

d = mod_inverse(e, phi_N)
print(d)