1

CS-591 I1 Midterm Exam Spring 2001

SOLUTIONS

Instructions

  • This is a closed book exam.
  • There are 4 sections on a total of 7 pages (including this one).
    Make sure that you have all the pages.
  • Each question is independent from others.
  • Maximum score is 100.
  • Budget your time wisely.
  • Read questions carefully; be sure you understand the question before starting to work on it. Be sure to follow directions. Ask if you have any questions.

Good Luck!

Please do not write below this line!

  1. ______Mod Arithmetic (20+10pts)
  2. ______RSA(30pts)
  3. ______DH(20pts)
  4. ______SSL(30+10pts)

1.Modular Arithmetics (20+10 points)

  1. Compute 3201mod 11. (hint: use Fermat’s theorem)

By Little Fermat Theorem, 310 mod 11 = 1.
So, 3201 mod 11 = 31 * (310) 20 mod 11 = 3

  1. Compute 2802mod 505. (hint: 505=101*5)

Similarly to the above, but now using Euler’s theorem:
2(505) mod 505 = 1.

(505)= 400.

So, 2802 mod 505 = 22 = 4

  1. Extra Credit: What is gcd(n,n+1)?
    Let d be a divider of n, so d=i * d
    If d also divides n+1 then it must divide (n+1)-n=1.
    Therefore, d=1. Namely, any common divider of n, and n+1 must be equal to 1.
    So, gcd(n, n+1)=1
    An even simpler (but less direct) way to see it is by applying Euclid’s gcd algorithm: gcd(n, n+1) = gcd( n+1 %n, n) = gcd(1,n)=1.

2.RSA (30 points)

  1. Given RSA signatures X and Y for messages x and y, compute the signature of message x*y. (Assume there is no hashing: i.e. X=xd mod n for some unknown private exponent d and the public modulus is n)
    Signature of x*y is equal to
    (x*y)d mod n = xd * yd mod n = X*Y mod n
  2. Suppose, Amason is using RSA with modulus n and public exponent e. One day they are hacked, and their private key d becomes known to the attackers. Bob, the security consultant, suggests that instead of regenerating the new keys completely from the scratch, only the new exponents e’, d’ need to be re-computed, leaving the modulus n unchanged (after all, indeed modulus computation requires more work).
    Is this safe? If yes, explain why. If not, show how the pirates can compromise the new system (i.e. compute new d’ from e, d, n, e’).
    Not safe: Bob clearly has not taken this class. We discussed in class the scenario of using the same modulus for many users and why it is not secure. This is essentially the same issue here.
    We know that e*d mod (n) =1.
    Suppose, (using extended gcd) you found x such that
    x*e’ mod (e*d–1) = 1
    Then x*e’ mod (n) = 1, so x=d’.
    If extended gcd returns r>1, then try to find x again, now using (e*d-1)/r in place of (e*d–1).
    The above describes how attackers can determine the private key corresponding to any public key.
  3. Attacker Attila intercepted some packets c1,c2, …, ck, encrypted using RSA with public exponent e and modulus n=pq (i.e. Attila knows only ciphertexts, n, e, but not p, q). His spies also learnt that one of the plaintext packets mi (for some i, s.t. ci=mie mod n) is divisible by p.
    Can Attila decipher all intercepted packets now? How or why not?
    Yes, Attila can now factor n as follows, and thus decipher not only the intercepted packets but also all the other messages encrypted with the same keys:
    For each cicompute ri = gcd(ci,n). If 1< ri <n, then ri = p. This will be the case for i for which mi is divisible by p. Indeed, if mi = p*k, for some integer k>0, then ci=miemod n = peke mod (p*q). Therefore, ciis also divisible by p.
    We do need to note two possible “failures” for Attila: if mi which is divisible by p is either 0 or n. In either of those case Attila would learn nothing. But these two cases are “illegal” messages since neither message is in Zn*.

3. DH (20 points)

  1. Turn DH scheme into a public key encryption system: i.e. specify the Public Key P, Private Key S, and algorithms EncryptP(M) taking the public key P and message M and encrypting it, andDecryptS(C) taking private key S and encrypted message (ciphertext) C and decrypting it.
    P=p, g, ma= ga mod p
    S= p, g, a
    EncryptP(M):
    bRandom {1,…,p-1}
    Kmab mod p
    c M*K mod p
    mb gb mod p
    C  <c, mb
    Return ( C )
    DecryptS(C):
    # Let C=<c, mb
    K mba mod p
    M c/K mod p # to divide by K: compute K-1 using ExtGCD
    Return( M )
  2. Can the above public key encryption be turned into the signature as easily as for RSA encryption scheme is turned into signature: for RSA public (encryption) key becomes the verification key and the private (decryption) decryption key becomes the signing key?
    If yes, show the resulting signature scheme; if not, explain why.
    (ElGamal and DSA are more complex transformations of DH than what is asked for above)
    It is hard to turn the above algorithm into Signature in the most direct way. For RSA, to sign a message we simply apply RSA-Decrypt algorithm to it, and to verify RSA-Encrypt. Here this would not work, since the decrypt algorithm requires mb which is generated by the other party. In the translation, it would require input from Verifier to generate a signature.
    Putting it differently, DH is turned into an encryption scheme easily, because the messages from one party are turned into the Public Key, and it is the other’s party move first (i.e. to encrypt). Thus the party acting first (encrypting) has all the necessary info already. For Signature, the party which has the Public Key must “move” first, but it has no input from the other party at that stage. So, DH cannot be emulated in this scenario.

4.SSL (30+10 points)

Consider the following threats to web security and briefly (but concisely!) describe how these are addressed in SSL (if possible, start by a specific SSL message(s) used to address the threat; also, some are really as simple as they look):

  1. Man-in-the-Middle.
    This is prevented by authenticated (relevant) handshake messages. Namely, the Server’s Certificate message contains Server’s Public Key (PK), authenticated by a trusted CA. If RSA is used, then the PK is the encryption key, so that when the client encrypts ClientKeyExchange message, he can be sure that the Man-in-the-Middle would not be able to decrypt this message. If DH is used, then the Server’s DH message (either part of Server’s Certificate or ServerKeyExchange) is authenticated (once again the trust is rooted in CA via certificate). Thus authenticating even just the server excludes Man-in-the-Middle attack.
  2. Replay: earlier SSL handshake messages are re-used (replayed).
    Replay attack is eliminated by using random values in ClientHello and ServerHello, and using these values for master secret generation and authenticating the handshake exchanges in MAC of the Finished messages (where the MACs are protected by encryption).
  3. Confidentiality: preventing attacker from getting the transmitted information.
    Confidentiality is achieved by encrypting the data exchanged by Server and Client (after ChangeCipherSpec message) with the keys derived from master secret. The master secret is derived by using the public key cryptography (DH, RSA) and excluding man-in-the-middle attack (see above).
  4. Brute-force attack: exhaustive search of all keys, for each, trying to decrypt the intercepted message
    Brute force attacks are prevented in general by making sure that the keys used are sufficiently long, so enumerating all the possibilities for them is infeasible.
  5. For Key Exchange.
    For key exchange this means selecting keys as long as 1024 or more bits for the modulus. This is done in part because the mathematical nature of the algorithms opens up attacks more efficient than the simple enumeration of all possible keys.
  6. For symmetric (conventional) encryption.
    For symmetric keys, over 80 bits is considered sufficiently long for the keys for the most straightforward enumeration of the keys. 56 bits – as used by DES – is no longer considered to be safe, but it still requires considerable resources to attack. Most modern ciphers use 128 bit keys or even more.
  7. Known-plaintext attack: Some messages sent over an SSL connection can be predictable (e.g. HTTP GET). An attacker can build a dictionary of every possible encryption for each such known plaintext message. Each intercepted message (or its segment – how long such a segment should be?) is looked up in the dictionary, and if a match is found, then the corresponding key is used. If there are a few matches, then all the keys must be used on longer intervals, to determine which is correct.
    In order to mount even an exhaustive search attack requires knowing when a correct key is discovered. This can be achieved by various variations of the known plaintext attacks. Namely, if the plaintext for a message is output when trying one of the candidate keys, we can (usually) conclude that this candidate key is indeed the real key. Thus, known plaintext is important for mounting a successful exhaustive search attack. Sometimes if the precise plaintext is not known, some information about it is: e.g. the message format, etc. This can be sufficient for the attack. However, this attack is prevented by the same attack as above: sufficiently large key sizes.
  8. Password sniffing: passwords in HTTP or other application traffic are eavesdropped.
    The standard way to prevent password sniffing is by running the application using passwords over SSL. Then the passwords are protected by SSL (as in item c above).
  9. IP spoofing: attacker uses forged IP addresses to trick a host into accepting bogus data.
    SSL is run over TCP/IP assuming no security from the underlying (TCP) layer. Thus, from the SSL point of view, IP specifics are irrelevant. Thus, SSL addresses the issues of the application level security. Even if the adversary completely controls the network, she should not be in possession of the private keys, which would allow the adversary to impersonate any other parties.