Secure Key Communication: Methods, Protocols, and Security

Posted on Apr 4, 2025 in Information Consulting and Management

Secure Key Communications

Three Methods for Secure Key Exchange:

  1. Trusted Third Party: A central server delegates keys. Every user has a secret key, and the server knows everyone’s keys.
    1. A → T: { A, B }
    2. T → A: { Na, Kab, B, {Kab, A}Kb }Ka
    3. A → B: { Kab }Kb

Problems with Trusted Third Party:

  • B doesn’t know who is communicating.
  • Replay attack.
  • If the server is compromised, it’s a single point of failure, and all user keys are compromised.
  • The server can crash due to a denial-of-service attack.

Needham-Schroeder Protocol

  1. A -> T : { A, B, Na }
  2. T -> A : { Na ,Kab, B,{Kab, A}Kb }Ka
  3. A -> B : { Kab, A }Kb
  4. B -> A : { Nb }Kab
  5. A -> B : { (Nb – 1) }Kab

Key Exchange (Diffie-Hellman)

  1. Alice selects a random integer x and computes p = (g^x) mod n. Alice selects a large prime n and a generator of the field n.
  2. Alice sends p, g, and n to Bob; x is kept secret.
  3. Bob selects a random integer y and computes q = (g^y) mod n.
  4. Bob then sends q back to Alice.
  5. Alice computes (q^x) mod n = g^(xy) mod n. Bob also computes (p^y) mod n = g^(xy) mod n. They both share the secret g^(xy) mod n.

Problems with Diffie-Hellman:

No authentication of the remote party leads to a man-in-the-middle attack, where Mallory is in the middle communicating to both A and B.

Public Key Cryptosystems (RSA)

  1. n = pq, where p & q are two large prime numbers. 1024-bit RSA is the size of n, phi = (p-1)(q-1)
  2. A public key, d that is relatively prime to n, is selected.
  3. Find e such that ed = 1 mod phi
  4. c = (m^e) mod n
  5. m = (c^d) mod n

n can be made secret. However, p & q must not be, else it is possible to compute the private key from the public key.

Problem with RSA:

  • Mallory somehow tricks A to think M’s key is B’s key. Now all messages are sent to Mallory, who is able to decrypt them.
  • RSA has poor resistance to spoofing: encrypt(k*m) = (k*m)^d = k^d * m^d = encrypt(k) * encrypt(m)

Digital Signatures

  1. Alice wants to sign a document certifying that she created the document.
  2. Alice encrypts the document with her private key. She sends both the encrypted version and the plain text version.
  3. Now anyone who knows Alice’s public key can decrypt the encrypted version and verify that it is the same as the plain text version.
  4. This verification proves that Alice signed the document since no one else should know Alice’s private key.

Public Key Infrastructure (PKI)

PKI is a system where a trusted third party (a principal that everyone trusts) vouches for the identity of a key. For example:

  1. Both Alice and Bob trust Trent. Everyone knows what Trent’s digital signature looks like.
  2. Bob creates a public key and goes to Trent. Trent sees both Bob and his public key, creates a certificate that says “This public key xxx belongs to Bob,” and signs it with his digital signature.
  3. Bob sends Alice his public key along with the certificate Trent gave him. Alice sees that the certificate bears Trent’s signature, so she uses the public key.

PGP: Every user has a public/private key pair and is capable of signing certificates. If a user can verify a certain public key really belongs to a user, then we can sign it. Trust is transitive.

Hashes: Cryptographic Tool for Integrity and Authentication

  1. Modification Detection Codes (MDC): Provides integrity
    1. Send message and hash separately. The hash must be sent over a secure channel.
  2. Message Authentication Codes (MAC): Provides integrity and authentication
    1. The hash function takes a key as a separate input; the output is dependent on the key and message.
    2. Send message and hash over an insecure channel.
  3. Digital Signature: Provides integrity, authentication, and non-repudiation

Hash function: A function that converts a pre-image into a smaller value called a hash value. The length of the hash reflects the secureness of the hash function (ideal hash, assuming two properties are satisfied).

Properties of Hash Functions:

  • One-way function
  • Collision resistance

Types of Strengths Against Attacks:

  1. Preimage-resistance
  2. Second preimage resistance
  3. Collision resistance (collision resistance implies second pre-image resistance)

Possible Attacks:

  • Birthday attack: Find two pre-images that hash to the same value: requires 2^(h/2) tries.
  • To find another pre-image that hashes to a given hash value: 2^h

MDC: Iterated like DES & AES

MD5

Hashes 512 bits at a time, 128-bit value, passed into the next hash function for the next block.

  • Breaking MD5: Differential cryptanalysis to find patterns between preimages and hash pairs.
  • Collision resistance: n1, collision found in seconds.
  • Chosen-text collisions: A few hours.
  • Pre-image resistance ~2^100 operations.

SHA1

Except the output is 160 bits and there are more rounds.

  • Collision resistance: Can be found in roughly 2^63 operations.