[ Security ] Ch05. Public Key Infrastructure (PKI)

Symmetric Key Distribution

• Symmetric key cryptography is more efficient than asymmetric key cryptography for enciphering large messages
• Symmetric key cryptography, however, needs a shared secret key between two parties.
  • For n people, we need n(n-1)/2 shared secrets.
• Problems:
  • The number of keys
  • The distribution of keys is another problem.
• Solution: Use a trusted third party

Key-Distribution Center

• Key-Distribution Center (KDC) is a practical solution that use a trusted third party
• To reduce the number of keys, each person establishes a shared secret key with KDC
• A secret key is established between the KDC and each members* How Alice can send a confidential message to Bob
  1. Alice sends a request to the KDC stating that she needs a session (temporary) secret key between herself and Bob.
  2. The KDC informs Bob about Alice’s request.
  3. If Bob agrees, a session key is created between the two.

• Problems of KDC
  • The database of KDC can be the main target of attackers
  • When a problem occurs at the KDC, the entire network is shut down
  • Communication bottleneck may occur at KDC

Multiple Key-Distribution Center

• To solve the problem, we need to have multiple KDCs
  • We divide world into domains
  • Each domain can have one or more KDCs

Session Keys

• A KDC creates a secret key for each member
  • This secret key can be used only between the member and the KDC, not between two members
• If Alice needs to communicate secretly with Bob, she needs a secret key between herself and Bob.
• A KDC can create a session key between Alice and Bob, using their keys with the center.
• A session symmetric key between two parties is used only once

Needham-Schroeder Protocol

Otway-Rees Protocol

---

Symmetric Key Agreement

• Alice and Bob can create a session key between themselves without using a KDC.
• This method of session key creation is referred to as symmetric key agreement

→ Diffie-Hellman Protocol

⭐️ Diffie-Hellman Protocol

① Alice chooses a large random number x such that 0 ≤ x ≤ (p – 1) and calculates R$_1$ = g$^x$ mod p.
② Alice sends R$_1$ to Bob ( but not sends the value of x )
③ Bob chooses another large random number y such that 0 ≤ y ≤ (p – 1) and calculates R$_2$ = g$^y$ mod p.
④ Bob sends R$_2$ to Alice (but not sends the value of y).
⑤ Alice calculate K = (R$_2$)$^x$ mod p.
⑥ Bob calculate K = (R$_1$)$^y$ mod p.Both have reached the same value without Bob knowing the value of x and without Alice knowing the value of y.

• Ex_ p = 7, g = 3
  3$^1$ mod 7 = 3
  3$^2$ mod 7 = 2
  3$^3$ mod 7 = 6
  3$^4$ mod 7 = 4
  3$^5$ mod 7 = 5
  3$^6$ mod 7 = 1
  → Primitive root : 모든 나머지가 다 나올 수 있는 값

• Example) Assume that p = 23 and g = 7

  • The steps are as follows:
    ① Alice chooses x = 3 and calculates R$_1$ = 7$^3$ mod 23 = 21
    ② Alice sends the number 21 to Bob
    ③ Bob chooses y = 6 and calculates R$_2$ = 7$^6$ mod 23 = 4
    ④ Bob sends the number 4 to Alice
    ⑤ Alice calculates the symmetric key K = 4$^3$ mod 23 = 18
    ⑥ Bob calculates the symmetric key K = 21$^6$ mod 23 = 18
    ⑦ The value of K is the same for both Alice and Bob;
    g$^{xy}$ mod p = 7$^{18}$ mod 23 = 18.

• More realistic example) We used a program to create a random integer of 512 bits (the ideal is 1024 bits). The integer p is a 159-digit number. We also choose g, x, and y as shown below:

Analysis of Diffie-Hellman

• The Diffie-Hellman concept is simple but elegant
• The secret key between Alice and Bob is made of three parts: g, x, and y
  • However, 1/3 of the key is public: g.
  • The other 2/3 of the key must be added by Alice and Bob
• Although the key in Alice’s hand (g, y, and x) and the key in Bob’s hand (g, x, and y), these two keys are the same because g$^{xy}$=g$^{yx}$
• Although the two keys are the same, Alice cannot find the value of y used by Bob because the calculation is done in modulo p.

Security of Diffie-Hellman

• The Diffie-Hellman key exchange is susceptible to two attacks:
  • Discrete logarithm attack
  • Main-in-the-Middle attack
    • Eve does not have to find the value of x and y.
    • Eve can fool Alice and Bob by creating two keys; one between herself and Alice, one between herself and Bob.
• Discrete logarithm attack
  • Eve can intercept R$_1$ and R$_2$.
  • If the x and y found from R$_1$ and R$_2$, the symmetric key K can be calculated.

Station-to-Station Protocol

• Based on Diffie-Hellman
• It uses a digital signatures with public key certificates to establish a session key between Alice an Bob
• It prevents man-in-the-middle attacks
  • Eve cannot send her own R2 to Alice and pretend it is coming from Bob because Eve cannot forge the private key of Bob to create the signature

---

Public Key Distribution

Public Key Distribution

• In asymmetric key cryptography, people do not need to know a symmetric shared key; everyone shield a private key and advertises a public key
• Everyone has access to everyone’s public key; public keys are available to the public.
• Then, how to distribute a public key?

• Public Key Distribution using Certificate
  • Certificate Authority (CA) binds a public key to an entity and issues a certificate
    • CA : 일종의 trusted center
  • CA has a well-known public key itself that cannot be forged
  • To prevent the certificate itself from being forged, the CA signs the certificate with its private key

→ Public Key Infrastructure (PKI)

Public Key Infrastructure (PKI)

• Public Key Infrastructure (PKI) is a model for creating, distributing, and revoking(폐기) digital certificates based on the X.509
  • IETF has created the Public Key Infrastructure X.509 (PKIX)
• PKI’s duties
  • Certificates’ issuing, renewal, and revocation
  • Key’s storage and update
  • Providing services to other protocols
  • Providing access control

Digital Certificate

• Digital version of a paper-based passport
• Identifies a person/organization uniquely on the internet
• Binds a user with its public key
• A public key certificate signifies the association between my public key and me
  • Like a driver license or passport
• Q: Who can approve the association ?
  A: A trusted entity – Certificate Authority (CA)
• Q: What is the content of a digital certificate?
  A: X.509 standard

• Digital Certificate Contentes
  • Main contents are the subject name (user), validity and public key
  • Signed by a Certificate Authority (CA)
  • Provides guarantees about a user’s identity
  • CA is a trusted agency that can issue digital certificate.
    • ex) VeriSign, Entrust, …
  • Government decide who can and cannot be CA.
  • CA signs “Certificates”
  • Certificate is a signed message, saying “I, the CA, guarantee that 48924579 is A’s public key”
  • If everyone has a certificate, a private key, CA’s public key, they can authenticate someone’s public key info.
  • A participant transmits its certificate to convey its public key information
    • Other participants can verify that the certificate was created by the authority
  • X.509 Certificate Format

Certificate Authority

• A user must remember its private key and have access to other users’ public key
• All users have a copy of the public key of the CA
• The CA sign’s A’s digital certificate with private key of CA and sends to A
• When B gets A’s certificate, B can verify it using public key of CA
• The certificate can be sent by A without any interaction with the CA

How Does CA Sign a Certificate ?

• A message digest of all but the last fields of the certificate is taken (e.g. using SHA1) → Message Digest
• Message Digest is signed with CA’s private key → Digital signature
• Digital signature is stored in the last field of the certificate

How Do You Verify a Certificate ?

• A message digest of all but the last fields of the certificate is taken (e.g. using SHA1) → MD1
• Digital signature in the last field of the certificate is de-signed with CA’s public key → MD2
• If MD1 = MD2, verified;
  else reject

CA’s Public Key

• How do we get CA’s public key of some certificate ?
  • Get CA’s certificate – which approves the association between the public key with CA
  • Who signs CA’s certificate?
• The organization of CAs
  • CA hierarchies and self-signed certificate
  • Cross-certification

CA Hierarchy

• There can be multiple level CAs
• Useful for delegation of work
• Each higher level CA vouches for its subordinate CA

Self-Certification

• Self-certification: Self-signed certificate for root CA
• Who signs for root CA?
  1. Root CA is automatically considered as trusted CA
  2. Software contains a pre-programmed, hard coded certificate of the root CA.
  (This certificate comes as part of the basic software such as Web Browser.)
  3. The root CA signs its own certificate
  (self-signed certificate)

Cross-Certification

• In some cases, even root CAs can be different
• In such cases, they certify each other
• Creates a cross level trust

PKI Components

• The interaction between PKI components
  • End user
  • Certification Authority (CA)
  • Registration Authority (RA)
  • Key recovery server
  • X.500 directory

• RA ( Registration Authority ) : an intermediate entity between the end users and the CA
  • Share the workload of CA
    • Accept and verify registration info about new users
    • Generate keys on behalf of the end users
    • Accept and authorize requests for key backups and recovery
    • Accept and authorize requests for certificate revocation
    • RA does not generate certificate
  • CA becomes an isolated entity, which makes it less susceptible to security attacks

• Key Recovery Server
  • Q: End users lose their private keys?
  • A1: CA must revoke the corresponding certificate
    → a new key pair must be generated
    → a new corresponding certificate must be created
  • A2: A key recovery server
    • CA backs up private keys at the time of creation

• Certificate Directory
  • Q: Where to store the certificates?
  • A1: End user stores on his local machine
  • A2: CAs use a certificate directory
    (or a central storage location)
    • Provide a single point for certificate administration and distribution
      (ex. for later certificate revocation)

Certificate revocation

• Reasons for certification revocation:
  • The private key is compromised
  • The CA made mistakes while issuing a certificate
  • The certificate holder leaves a job,…
• Before using a certificate, we check
  • Does the certificate belong to the owner? (check certificate signature)
  • Is the certificate valid, or is it revoked?

• Certificate Revocation Check Mechanisms
  • It is necessary to check the validity of a certificate before it is used
  • Two mechanisms: Online Checks and Offline Checks

Certificate Revocation List (CRL)

• File containing a list of invalid certificates
• Issued periodically by a CA
• Example of CRL
• A revocation agency (RA) issues a list of revoked (“bad”) certificates
  • It is updated and published regularly (e.g. daily).
  • It does not include certificates whose validity is over.
  • Users must check the most recent CRL in addition to checking the expiry date and signature.
• Why do you then need expiry?
  • Makes the revocation mechanism more efficient – CRLs of currently non-expired certificates are of manageable size.
  • Many deployed systems do not check for revocation, only expiry

• Validating a Certificate using CRL

OCSP (Online Certificate Status Protocol)

• OCSP can be used in place of, or in addition to, CRL s
• Client sends a OCSP request for certificate status info to a server (OCSP responder) provided by CA
  • The server consults with X.500 directory and sends back a response of “good”, “revoked” or “unknown”
  • The response is signed (by CA, or a Trusted Responder, or an Authorized Responder certified by the CA).
• Provides instantaneous status of certificates

HGU 전산전자공학부 고윤민 교수님의 24-2 컴퓨터 보안 수업을 듣고 작성한 포스트이며, 첨부한 모든 사진은 교수님 수업 PPT의 사진 원본에 필기를 한 수정본입니다.