20-ECES-653-001Network SecurityFall 2004

Acceptable Solutions to 2004 Midterm Exam

Question 1: Zero-Knowledge Proofs

  1. Consider the term "zero-knowledge proof." Is there really a proof? Explain.

    Actually there is not a proof. A "zero-knowledge proof" consists of some iterations of transactions, each of which either results in the verifier surely being convinced that the "prover" cannot prove anything or the verifier having a modicum of confidence that the "prover" is the one knowing "the secret". Confidence is improved through repeated rounds but the verifier is never completely sure that the "prover" is who it says it is.

  2. You probably know that it is possible with four colors to color a map so that no two bordering principalities are the same color. However, for some maps three colors are enough. How can a person demonstrate to another that he or she knows how to color a particular map with three colors without giving away how to do it?

    Use the language of graphs for simplicity (vertices and edges - a vertex represents a country and an edge represents a border). Suppose the Prover constructs a large, 3-colorable graph and uses colors red, green, blue to color the vertices. Such a construction is easily accomplished: just create N vertices, color them, and add edges between vertices of different colors. Say the resulting graph has E edges.

    A round proceeds as follows. The Prover randomly permutes the colors red, green, and blue and the 3-color graph. The Prover covers the vertices so that their color is hidden from the Verifier and shows the graph with covered vertices to the Verifier. The Verifier selects two adjacent vertices at random. The Prover removes the covers from the two chosen vertices. The Verifier checks that they are colored differently.

    If the Prover does not have a 3 coloring, then at least one edge will intersect two vertices of the same color (the fake Prover must commit the colors before showing the graph to the Verifier). Therefore, the Verifier will discover a "bad" edge with probability at least 1/E. But a Prover that has a 3-coloring will always show a "good" edge. By repeating this process H*E times, a fake Prover has probability no greater than (1-1/E)H*E of deceiving the Verifier. Choose H to reach an acceptable probability of making a mistake.

  3. Why is your proposed method a zero-knowledge proof? Or is it?

    Yep, it is! Any "bad" rounds can be edited from a "taping" of the proceedings. Hence a third party cannot say for sure whether the Prover is genuine or the Verifier is tricking him by editing the tape.

Question 2: Handshake Protocols

  1. Assume a Server and Client share a secret key, K. Consider the following handshake between Client and Server. The Client initiates the handshake by identifying itself to the Server. The Server responds by sending a random number R to the Client. The Client then encrypts R with K and sends the result to the Server.

    1. What has been accomplished?

      The Server authenticates the Client: supposedly, only the real Client would know the secret key and be able to encrypt with it.

    2. The encryption can be carried out by means of some secret key encryption system such as AES. How else can the encryption be done? Explain!

      A publicly known hash algorithm can be used. The Client can take the message digest of K concatenated with R and send the result to the Server. Since the Server knows both R and K, it can also take the message digest of these and compare the result with that received from the Client. By using a random number, it would be hard for an eavesdropper to record a response and reuse it later to spoof the Client to the Monitor.

    3. What are the weaknesses of this handshake?

      1. Authentication is not mutual.
      2. Vulnerable to off-line password quessing attack if K is based on a password.
      3. Once authentication is completed, impersonator may take over the connection, using the Client's IP address, and communicate with the Server as though it were the Client.
      4. If the Server is compromized, the attacker will likely be able to impersonate the Client to other Servers if they all use the same K.

  2. Suppose Client A wants to establish a session key for communication with Client B using a KDC. Both clients share secret keys with the KDC. Client A sends a request for a ticket to B to the KDC: it consists of B's identity and a nonce. The KDC sends a session key KAB, the nonce, B's identity, and a ticket, encrypted with A's key, to A. Client A decrypts the message and sends the ticket to B. Client B decrypts the ticket and shares a session secret with A.

    1. Describe the ticket.

      The ticket is the session key plus the identity of A encrypted with B's secret key.

    2. Authentication is missing. How can the handshake be changed to support authentication of all parties?

      The KDC authenticates itself to A with the nonce that is sent by A. When A sends the ticket to B, it includes another nonce encrypted with the session key which it now has after decrypting the KDC's response to its request. Then B decrypts the ticket to get the session key, then decrypts the nonce. The nonce, or a predictably modified version of it, is encrypted with another nonce created by B using the session key. This is sent to A. A decrypts with the session key and verifies the nonce. Then encrypts a predictably modified version of B's nonce and sends it back to B. B decrypts and checks the nonce. The two additional nonces allow A and B to authenticate each other.

    3. Even after adding authentication, this protocol is vulnerable to what type of attack?

      Suppose an attacker saves responses from the KDC to A. Then suppose the attacker finds out A's key, saves it, and then A changes its key realizing it has been attacked. There is nothing to make an older (before the key change) ticket to B invalid after a such a change. The attacker can then decrypt an older response from the KDC to get the ticket to B. Without decrypting the ticket, A sends it to B with a nonce it creates. Since the attacker has the (old) session key (with no way for B to know that this is an old session key) it can decrypt the session key and send a nonce with the ticket, convincing B that it is A.

    4. How can the protocol be modified to protect against this attack?

      Have A first connect to B and request an encrypted nonce, then use that nonce throughout the exchange.

Question 3: Public Key Encryption

  1. Describe how messages are encrypted using a public key encryption system.

    Every communicating party has a public key and a private key. The private key stays with the party but the public key is published openly so anyone can see it. There is also an encryption algorithm and a decryption algorithm that is known to all parties. If A wants to send an encrypted message to B, A acquires B's public key then applies the encryption algorithm with the key to the plaintext message. The encrypted result is sent to B. B applies the decryption algorithm with its private key to the encrypted message to decrypt.

  2. Describe how messages may be ``signed'' using a public key encryption system.

    Suppose signing is possible and A wants to sign a plaintext message intended for B. Then A uses its private key to encrypt the message using the encryption algorithm. The encrypted result is sent to B. B decrypts with A's public key. The result is compared with the plaintext message which is also sent by A. If there is a match then the message was signed by the correct party.

  3. What is the Chinese Remainder Theorem?

    If the prime factorization of N is N1*N2*N3*...*Nk, then the system of equations
         P1 = X mod N1
    P2 = X mod N2
    P3 = X mod N3
    ...
    Pk = X mod Nk
    has a unique solution X given any P1...Pk where X < N.

  4. State one application of the Chinese Remainder Theorem in cryptography.

    Suppose everyone's RSA public key e part is 3. Consider the same message m sent to three people. Suppose the other half of the public key of all these people is N1, N2, and N3, respectively. Then the encrypted messages are
        
    C1 = m3 mod N1
    C2 = m3 mod N2
    C3 = m3 mod N3
    By the Chinese Remainder Theorem one can compute m3 mod N1*N2*N3. Since m is smaller than any of the Ni, m3 is smaller than N1*N2*N3 so it is uniquely determined and taking the cube root finds m.

  5. What is a ``secure random number''?

    This depends on the application. In RSA we need a p and q such that (p-1) and (q-1) are relatively prime to public key exponent e. That means p-1 = 1 mod 3 if e = 3. In other words, p = 2 mod 3.

  6. How might a secure random number be obtained?

    Choose a random odd number, multiply by 3 and add 2, then test for primality. The test for primality may proceed as follows: 

          Calculate b, the number of times 2 divides p-1
      Calculate m such that p = 1 + 2b m
      Choose a random integer a such that 0 < a < p.
      If am = 1 mod p or a2jm = -1 mod p, for some 0 ≤ j ≤ b-1,
      then p passes the test.  A prime will pass the test for all a 
      A non prime number passes the test for at most 1/4 of all possible a
      Hence, repeat N times and probability of error is (1/4)N