Cryptographic Protocols

Question 1

What is a cryptographic protocol?

Answer 1

A cryptographic protocol is defined as a series of steps and message exchanges between multiple entities in order to achieve a specific security objective.

Question 2

Which additional characteristic a cryptographic protocol has that the others protocols doesn’t?

Answer 2

It should not be possible to do or learn more than what is specified in the protocol.

Question 3

What is data origin authentication?

Answer 3

Data origin authentication is the security service that enables entities to verify that a message has been originated by a particular entity and that it has not been altered afterwards

Question 4

data integrity is a synonym for which security service?

Answer 4

Data origin authentication

Question 5

What is entity authentication?

Answer 5

Entity authentication is the security service, that enables

communication partners to verify the identity of their peer entities

Question 6

why entity authentication is more than

an exchange of (data-origin-) authentic messages?

Answer 6

Because timeliness is also important to be sure that old messages are not being used to reply and that the person answering is really present on that moment.

Question 7

What are the two principle means to ensure timeliness in cryptographic protocols?

Answer 7

Timestamps (require more or less synchronized clocks) and 
Random numbers (challenge-response exchanges)

Question 8

which are the two main categories of protocols for entity authentication?

Answer 8

Arbitrated authentication and Direct authentication.

Question 9

How does the arbitrated authentication protocol work?

Answer 9

an arbiter, also called trusted third party

(TTP) is directly involved in every authentication exchange

Question 10

What are the main advantages of the arbitrated authentication protocol ?

Answer 10

1. This allows two parties A and B to authenticate to each other without knowing any pre-established secret
2. Even if A and B do not know each other, symmetric cryptography can be used

Question 11

What are the drawbacksof the arbitrated authentication protocol ?

Answer 11

1. The TTP can become a bottleneck, availability of TTP is critical
2. The TTP can monitor all authentication activity

Question 12

How does the Direct authentication protocol work?

Answer 12

A and B directly authenticate to each other

Question 13

What is the main advantage of direct authentication protocol?

Answer 13

no online participation of a third party is required and no

possible performance bottleneck is introduced

Question 14

What is the main drawback of direct authentication protocol?

Answer 14

requires asymmetric cryptography or pre-established secret keys

Question 15

How does the Needham-Schroeder Protocol work?

Answer 15

It uses a trusted third party (TTP). first A sends a message asking the TTP for a key to send message to B. The message contains:

1. A - > TTP: (A, B, r A )

The ttp then generates a key KA,B and send to A

2. TTP → A: {r A , B, K A,B , {K A,B , A} K B,TTP } K A,TTP

A decrypts the message and by the random number rA A knows that it is a fresh message from TTP. After A sends a message to B:

3. A → B: {K A,B , A} K B,TTP

B decrypts the message and obtains KB,TTP and send a random number to A:

4. B → A: {r B } K A,B

A decrypts and answer with rB -1 and send it back to B.

5. A → B: {r B -1} K A,B

B checks if the result is valid.

Question 16

There are any mean to impersonate someone using the Needham-Schroeder Protocol?

Answer 16

Yes, since old messages continue to be valid, if someone knows K A,B, it can use latter to impersonate A party during a communication.

Question 17

Which protocol solve the impersonate problem of the Needham-Schroeder one?

Answer 17

Otway-Rees Protocol, by adding a index to the exchange messages.

Question 18

how the Otway-Rees Protocol solve the problem of replying old messages?

Answer 18

Instead of only send message to TTP, A send the random number either to TTP and to B. B sends a random number by its own and then share with TTP attaching the index and the random number from A. TTP send the message with both encrypted random number to B. B verifies its random number and then send the A part to A. A check i A and r A to see if they are unchanged. If yes, then A is sure about the authenticity of the key.

Question 19

What is X.509?

Answer 19

X.509 is an international recommendation of ITU-T and defines a framework for provision of authentication
services, comprising Certification of public keys and certificate handling (format, hierarchy, revocation list) and Three different dialogues for direct authentication (one way and two way [requiring synchronized clocks] authentication and three way mutual authentication [entirely based on random numbers].

Question 20

What happened when the private key of a

certification authority is compromised?

Answer 20

This implies, that all certificates signed with this key have to be revoked.

Question 21

How Certificate revocation is realized?

Answer 21

by maintaining certificate revocation lists (CRL):

• CRLs are stored in the X.500 directory
• When checking a certificate, it has also to be checked that the certificate has not yet been revoked
• Certificate revocation is a relatively slow and expensive operation

Question 22

What is Perfect Forward Secrecy?

Answer 22

It is a characteristic in which is guaranteed that a compromise of a key in the future will not allow to compromise any data that has been protected with this key exchanged before that compromise.

Question 23

How can we guarantee the property of perfect forward secrecy (PFS)?

Answer 23

By doing the separation of key exchange and authentication of the exchange is possible to guarantee the property of perfect forward.

Question 24

Which cryptographic protocol for key exchange does not realize any authentication?

Answer 24

The Diffie-Hellman protocol

Question 25

What happens if it is used the diffie-hellman protocol to key exchange without authentication?

Answer 25

It cannot guarantee privacy of a communication following the exchange, it has to be combined with authentication.

Question 26

How does secret splitting work?

Answer 26

The Trend generate n-1 random strings (where n is the number of people to share the secret) and XOR with the original message. Distribute the random strings and the result of the XOR to each one of the participants. To recover it, just XOR the result and the random strings to recover the message.

Question 27

Secret splitting scheme is also known as…

Answer 27

all-or-nothing scheemes.

Question 28

What is a Secret Sharing?

Answer 28

It is a Scheme to distribute a secret among a group of participants.

Question 29

How does the (m,n)-threshold scheme work?

Answer 29

A secret is divided into n pieces, called shadows.
Any m of the shadows can be used to reconstruct the message M.

Example
Trent can divide his secret burger recipe among Alice, Bob, Carol, and Dave, such that any three of them can put their shadows together and reconstruct the burger recipe.
it is called a (3,4)-threshold scheme

Question 30

how does Shamir‘s Secret Sharing Scheme work?

Answer 30

It is an (m,n)-threshold scheme and uses a polynomial to “solve” and keep the secret.

1. Choose a public prime p, which is larger than the number of possible shadows and larger than the largest possible secret.
2. Generate an arbitrary polynomial of degree m – 1.
   e. g., for a (3,n)-threshold scheme, generate a quadratic polynomial (ax 2 + bx + M) mod p.
3. The coefficients are chosen randomly, they are kept secret and discarded after the shadows are handed out.
4. The shadows are obtained by evaluating the polynomial at n different
   points: k i = F(x i ), i=1,…,n.

Question 31

How can a secret be shared by two hostile delegations?

Answer 31

To share the secret such that 2 out of 7 from Delegation A and 3 out of 12 from delegation B are required to reconstruct the secret.

To solve this problem, make a polynomial of degree 3 which is the product of a linear and a quadratic expression.
Then give all members of delegation A a shadow that is the result of an evaluation of the linear equation
And give all members of delegation B a shadow that is the result of an evaluation of the quadratic equation
This way, the delegations have to cooperate in order to reconstruct the secret, because none of them has enough knowledge on its own.

Question 32

What is the Bit Commitment?

Answer 32

A protocol that allows a user to commit to a value while keeping it hidden and preserving the user’s ability to reveal the committed value later.

Question 33

How does the protocol of Bit Commitment Using Symmetric Encryption work?

Answer 33

1. Bob generates a random number R and sends it to Alice.
2. Alice generates a random symmetric key k, sends back:
   E k (R, committed bit)
3. Bob does not know k, so he cannot recover the committed bit.
4. Later, Alice reveals the key k, so Bob can verify the
   committed bit.

Question 34

How does the Bit Commitment Using One-Way Functions work?

Answer 34

Alice generates two random-bit strings, R 1 and R 2 .
1. Alice creates a message consisting of her random strings and the bit she wishes to commit to: (R 1 , R 2 , b).
2. Alice computes a one-way function on the message and sends the result, as well as one of the random strings, to Bob: H(R 1 , R 2 , b) R 1 .
3. Later, when Alice reveals her bit, she sends Bob the
original message: (R 1 , R 2 , b).
4. Bob computes the hash value and compares it and R 1 ,
with the hash value and the random string he received in 3.

Question 35

What is the goal of Fair Coin Tossing?

Answer 35

Create a random bit in a distributed setting between two parties without any party dictating.

Question 36

How does the Fair Coin Tossing work?

Answer 36

Alice has a secret: the factorization of a number n=pq with p,q being large primes and

p congruent q congruent 3 mod n

1. A sends n to B
2. B picks a random x in sqr(n) < x < n with gcd(x,n)=1.
   B computes a = x² mod n and sends it to A.
3. Knowing p and q, A computes the four solutions for the modular square root of a (using the Chinese Remainder Theorem). Call these x, n-x, y, and
   n-y. A cannot distinguish between x or n-x and y or n-y. She choses one of the four at random and sends it to B.
4. If B receives x or n-x, he learns nothing. But, if he receives y or n-y, he can factor n by by computing gcd(x+y,n)=p or q. B tells A whether he got the
   secret and if so wins, otherwise loses.