04 Cryptographic Protocols

Question 1

How is a cryptographic protocol defined?

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

What are some general properties of a protocol?

Answer 2

• Everyone involved in the protocol must know the protocol and all the steps to follow in advance
• Everyone involved in the protocol must agree to follow it
• The protocol must be unambiguous, every step is well defined and there is no chance of misunderstanding
• The protocol must be complete (a specified action for every possible situation)

* Additional property of a cryptographic protocol:

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

Question 3

What are some applications of Cryptographic Protocols?

Answer 3

• Key exchange
• Authentication
  
  • Data origin authentication
  • Entity authentication
• Combined authentication and key exchange
• Secret splitting (all parts needed for reconstruction)
• Secret sharing (m out of n parts needed for reconstruction)
• Time-stamping
• Key escrow (ensuring that only an authorized entity can recover keys)
• Zero-Knowledge proofs (proof of knowledge of an information without revealing the information)
• Bling signatures (privacy-preserving time-stamping services)
• Secure elections
• Electronic money (like Bitcoins)

Question 4

Explain some concerns about the Diffie-Hellman (cryptographic protocol) for key exchange:

Answer 4

• The protocol does not realize any authentication
• Both parties (Alice, Bob)

Question 5

How does PFS (Perfect Forward Secrecy) takes place?

Answer 5

• PFS (Perfect Forward Secrecy) takes place when a separation of key exchange and authentication of the exchange happens.
• If a key exchange ensures PFS, then a compromise of one key in the future will not allow to compromise any data that has been protected with other keys exchanged before that compromise.
• Example: Alice and Bob sign the data exchanged to compute sk with their private keys. Even the compromise of a private key in the future will not allow to decrypt recorded data that has been protected with sk.

Question 6

What is Data Origin Authentication?

Answer 6

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.

Also called: data integrity.

Question 7

What is the relation of data integrity to cryptographic protocols?

Answer 7

• There are cryptographic protocols to ensure data integrity. They comprise just one protocol step and are not very “exciting”:
  
  • Example 1: everybody knows Alice’s public RSA key and its sure to know really Alice’s key, Alice then can insure data integrity of her messages by encrypting them with her private key.
  • Example 2: Alice can also compute MDC over her messages and append the MDC encrypted with her private key to the message.
• Data integrity of messages exchanged is often an important property in cryptographic protocols, so data integrity is a building block to cryptographic protocols.

Question 8

What is Entity Authentication?

Answer 8

• Entity Authentication is a security service that enables communication partners to verify the identity of their peer entities.
• Entity authentication is the most fundamental security service, as all other security services build upon it.

Question 9

How can Entity Authentication be accomplished?

Answer 9

• Knowledge: passwords.
• Possession: physical keys or cards.
• Immutable characteristics: biometric properties.
• Location: evidence to verify that an entity is at a specific place.
• Delegation of authenticity: the verifying entity accepts, that somebody who is trusted has already established authentication.
• ^ In communication networks, direct verification of the above means is difficult or insecure which motivates the need for cryptographic protocols.

Question 10

Why entity authentication is more than an exchange of (data-origin) authentic messages?

Answer 10

• Timeliness:
• A party B receiving authentic messages from A, can not be sure if the other member is actually participating in the communication at THAT specific moment or if a third party C is replaying old messages from A.
• This is of specific significance, when authentication is only performed at
  connection-setup time (tranmission of a PIN).

Question 11

What 2 means can be used to ensure timeliness in cryptographic protocols?

Answer 11

• Timestamps (requiring synchronized clocks)
• Random numbers (challenge-response exchanges)

Most authentication protocols do also establish a secret session key for securing the current session following the authentication exchange.

Question 12

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

Answer 12

• Arbitrated authentication:
  
  • Arbiter as a TTP (Truted Third Party) directly involved in every authentication exchange.
• Direct authentication:
  
  • A and B directly authenticate to each other.

Question 13

Describe the advantages and drawbacks of Arbitrated authentication:

Answer 13

• Advantages:
  
  • Allows two parties A and B to authenticate to each other without knowing any pre-established secret.
  • Even if A and B don’t know each other, symmetric crypto can be used.
• Drawbacks:
  
  • The TTP (Trusted Third Party) can become a bottleneck
  • The availability of the TTP is critical
  • The TTP can monitor ALL authentication activity

Question 14

Describe the advantages and drawbacks of Direct authentication:

Answer 14

• Advantages:
  
  • No online participation of a third party is required and no possible performance bottleneck is introduced.
  • Requires asymmetric cryptography or pre-established secret keys.

Question 15

Describe the meaning of some notation of Cryptographic Protocols (1):

Question 16

Describe the meaning of some notation of Cryptographic Protocols (2):

Question 17

Describe and elaborate on the Needham-Schroeder Protocol:

Answer 17

• Invented in 1978 by Roger Needham and Michael Schroeder.
• This protocol relies on symmetric encryption and makes use of a TTP (Thrusted Third Party).
• Procedure: the TTP shares secret keys K_A,TTP and K_B,TTP with A and B:
  
  • A generates random number r_A and sends:
  • A–> TTP: (A, B, r_A)
• TTP generates a session key K_A,B for secure comm betwen A and B, then replies to A:
  
  • TTP–> A: {r_A, B, K_A,B, {K_A,B, A}_{KB, TTP}}_{KA, TTP}
• _​A decrypts the message and extracts K_A,B. A confirms that r_A is identical to what was previously generated, so she knows the reply is a fresh reply from the TTP. Then A sends to B:
  
  • A–> B: {K_A,B, A}K_B,TTP
• _​B decrypts the message and obtains K_A,B. He then generates a random number r_B to answers A:
  
  • B–> A: {r_B}K A,B
• A decrypts the message, computes r_B-1 and answers with:
  
  • A–> B:{r_B-1)_{K A,B}
• ​B decrypts the message and verifies that it indeed contains r_B-1

Question 18

Elaborate on the security discussion of the Needham-Schroeder Protocol:

Answer 18

• The exchange of the random numbers r_B and r_A are supposed to ensure that an attacker, trying to impersonate A cannot perform a full protocol run with replayed messages.
• As old session keys K_A,B remain valid, an attacker can manage to get to know a session key to impersonate A.
  
  • E–> B: {K_A,B, A}_KB,TTP (E doing a replay)
  • B–> A: {r_B}_KA,B (E has to intercept this)
  • E–> B: {r_B-1}_KA,B
• This is how, E, without knowing K_A,TTP or K_B,TTP can impersonate A.
• Kerberos further fixes this vulnerability using timestamps.

Question 19

Explain how the Otway-Rees Protocol works:

Answer 19

• Otway-Rees protocol fixes the problem of the Needham-Schroeder protocol using index numbers and additional random numbers:

1. A sends a message to B containing an index i_A, her name A, B name, an and additional random number r_A encrypted with key K_A,TTP​​
   
   • A–> B: (i_A, A, B, {r_A, i_A, A, B}_KA,TTP
2. B generates a random number r_B and encrypts this together with the previous message using a key K_B,TTP. All this new longer message is send to TTP
   
   • B–> TTP: (i_A, A, B, {r_A, i_A, A, B}_KA,TTP, {r_B, i_A, A, B}_KB,TTP)
3. TTP then generates a new session key K_A,B and creates two encrypted messages, one for A and one for B and sends them through B
   
   • TTP–> B: (i_A, {r_A, K_AB}_KA,TTP, {r_B, K_AB}_{KB, TTP})
4. B decrypts his part of the message, verifies r_B and sends A her part of the message:
   
   • B–> A: (i_A, {r_A, K_AB}_KA,TTP)
5. Finally A decrypts the message and checks if i_A and r_A have not changed during the exchange. If not, she can be sure that TTP has send her a fresh session key K_A,B for communications. However, this does not authenticates B to A.

Question 20

Elaborate on the security discussion of the Otway-Rees protocol:

Answer 20

• The index number i_A prevents against replay attacks. However, this actually requires that TTP checks that the current i_A is bigger than the last i_A.
• As TTP will only generate the two messages if both parts of the message he received contain the same index number i_A and names A, B. Therefore, A and B are sure that both of them have authenticated to TTP during the protocol run.

Question 21

What is Kerberos and what are its key characteristics?

Answer 21

• Kerberos is an authentication and access control service for workstation clusters.
• Works on the basis of tickets to allow nodes communicating over a non-secure network to prove their identity to one another in a secure manner.
• It is aimed primarily at a client-server model and it provides mutual authentication (both user and server verify each other’s identity).
• Kerberos protoco messages are protected against eavesdropping and reply attacks.
• It is build on symmetric key cryptography and requires a TTP.
• Key characteristics as its design goals:
  
  • Security (protection against eavesdropping, active attacking, impersonation)
  • Reliability (using a services requires authentication, Kerberos should be highly reliable and available)
  • Transparency (transparent authentication process beyond password input)
  • Scalability (supporting a large number of clients and servers)

Question 22

How does Kerberos (v4) works? Describe its steps:

Answer 22

• User A, who wants to access one ore more services, provided by servers S1, S2… connected over an insecure network.
• Authentication: A will authenticate to an AS (Authentication Server) who provides a temporal permit that allows to demand access for services. This permit is a Ticket-Granting Ticket (Ticket_TGS).
• Access control: A then using this TGT can demand a Ticket Granting Server (TGS) to obtain access for a service provided by another specific server S1. The TGS decides if the access is permited and answers with a Service Granting Ticket (SGT) Ticket_S1 for Server S1.
• Key exchange: the AS (Authentication Server) provides a session key for communication between A and Ticket Granting Server (TGS), later the TGS provides a session key for communication between A and Server1 (S1). The use of these session keys also serves for authentication purposes.

Question 23

Graphically explain and elaborate on how Kerberos work:

Answer 23

Question 24

How does Multiple Domain Kerberos works?

Answer 24

• It work on the basis of having different realms where the AS, TGS and S1…Sn could be located.
• For example: an AS (Authentication Server) and a TGS (Ticket Granting Server) can be in Realm 1 but a needed Service S1 can be in another Realm 2.

1. A request to the AS the TGT inside Realm 1.
2. AS replies with a TGT and Session Key.
3. A uses the TGT to get anoter cross-realm TGT_rem from a TGS in Realm 1.
4. TGS R1 replies with a TGT_rem and Session Key.
5. A uses the obtained TGT_rem to request a SGT from a TGS in Realm 2.
6. TGS R2 replies with a SGT and Session Key.
7. A has obtained a SGT and Session Key that can be used to request a service from S1 in Realm 2.
8. S1 replies with a Service Authenticator.

Question 25

Graphically explain and elaborate on how Multiple Domain Kerberos work:

Answer 25

Question 26

Mention some new key characteristics that distinguish Kerberos 5 from Kerberos 4:

Answer 26

• Kerberos 5 was developed in response to weaknesses that became known to Kerberos 4.
• Includes explicit checksums to verify that messages were not altered.
• Supports multiple ciphers (more than DES).
• The messages to AS and TGS are very similar.
• Multidomain Kerberos is supported.
• For initial contact, A sends also a nonce “n” which helps to avoid replays if the time changes.
• A renewing of tickets is allowed.
• But, central servers are still potentials single-points-of-failure.
• But, some time synchronization is required for initial exchanges.

Question 27

What is X.509 and what are its main characteristics?

Answer 27

• X.509 is an international ITU-T Standard, part of the X.500 series that define directory services (versions in 1988, 1993 and 1995).
• X.509 defines a framework for provisioning of authentication services such:
  
  • Certification of plubic keys and certificate handling:
    
    • Certificate format
    • Certificate hierarchy
    • Certificate revocation lists
  • Three different dialogues for direct authentication:
    
    • ​One-way authentication (requires synchronized clocks)
    • Two-way mutual authentication (requires synchronized clocks)
    • Three-way mutual authentication based on random numbers

Question 28

Describe some characteristics of Public Key Certificates under X.509:

Answer 28

• A publick key certificate is a sort of passport, certifies that a public key belongs to a specific name.
• Certificates are issued by CA (Certification Authorities).
• If all users know the public key of the CA, all users can check every certificate issued by the CA.
• Certificates can avoid online-participation of a TTP.
• The security of the private key of the CA is CRUCIAL to the security of all users!

Question 29

Graphically list the elements of a Public Key Certificate under X.509 (versions 1,2 and 3):

Answer 29

Question 30

Graphically list the elements of the notation of a Public Key Certificate binding a public Key +K_A to a user A issued by Certification Authority CA:

Answer 30

Question 31

Explain how do Certificate Chains work:

Answer 31

• A and B have their own independent Certificate Authorities CA and CB
• If then A doesn’t know or doesn’t thrust CB (and therefore B’s certificate CB<> is useless, also in reverse direction).
• Therefore, constructing a certificate chain is needed.
• If CA and CB trust each other and then CA certifies CB’s public key CA<<cb>> and CB also certifies CA’s public key CB<<ca>&gt;.</ca></cb>
• Now A and B can check their certificates by checking a chain.
  
  • If A is presented CB<>, she tries to look up CA<<cb>></cb>
  • A finally checks CA<<cb>>,CB<<b>></b></cb>

Question 32

How does Certification Hierarchy works?

Answer 32

• Certificate chains are not limited to two certificates
• A can check the certificate of user G issued by CG
  
  • CA<<cc>>,CC<<cd>&gt;,CD&lt;<ce>&gt;,CE&lt;<cg>&gt;,CG&lt;<g>&gt;</g></cg></ce></cd></cc>
• This is established by a chain of trust between certification authorities
• X.509 suggests that authorities are arranged in a certification hierarchy (so navigation across CA’s is straightforward).

Question 33

How does Certificate Revocation works?

Answer 33

• If A’s private key is compromised by E (stolen private key and password, for example), then A can ask for revocation of the corresponding public key certificate.
  
  • Otherweise, “E” can continue impersonating A while that publick key certificate remains valid (or until the end of the certificate’s validity period).
• A worse situation occurs when the private key of a certification authority is compromised.
  
  • ​All certificates signed with this key have to be revoked.
• Revocation is done by maintaining a CRL (Certificate Revocation Llists)
  
  • Stored in the X.500 directory
  • When checking a certificate, it is also checked against the CRL
  • Cert revocation is a relatively slow and expensive operation

Question 34

Explain the three types of Authentication under X.509:

Answer 34

• One-way authentication:
  
  • A authenticates to B, sending t_A, r_A, B, sgnData_A, SessionKey, CA<>
  • B verifies the CA with +K_A, A’s signature, t_A and K_A,B
• Two-way authentication:
  
  • After the one-way authentication, if mutual authentication is seeked, then:
  • B creates a message with t_B, r_B, A, r_A, sgnData_B, SessionKey, CA<>
• Three-way authentication:
  
  • A sends a signed fresh random number A[r_B] to B
  • This is to verify that both have synchronous clocks
• X.509 focuses on signing authentication messages using asymmetric crypto
• BUT can be implemented using symmetric crypto by using an agreed authentication key AK_A,B previously and also appending a MAC computed with that key.

Question 35

Describe the 4 categories of formal validation methods for crytopgrahic protocols:

Answer 35

• Some protocol flaws can be discovered years later after publication,
• General approaches for analysis of specific protocol properties:
  
  • finite-state-machine based approaches, first-order predicate calculus
  • Drawback: security differs from correctness (not assuming malicious manipulation)
• Expert system based approaches:
  
  • Experts knowledge formalized as deductive rules for designers
  • Drawback: not well suited to find flaws in crypto protocols based on unknown attacking techniques
• Algebraic approaches:
  
  • Since crypto protocols are specified as algebraic systems…
  • Analysis is done by looking at algebraic-term rewriting properties of the model and see if the model can attain desirable/undesirable states
• Specific logic based approaches:
  
  • Set of predicates and a mapping of messages exchanged during a protocol run into to a set of formula
  • A set of rules allows to analyze the knowledge and belief obtained by peer entities of a crypto protocol during a protocol run