Fall 2001, CSE 597E: Quiz 1 and solution - 19 Sept 2001

Please write your Name, Student ID, and Section at the top of the page.
  1. [1 point] What is a one-way function? (only one answer, please)
    1. A function which has no inverse
    2. A function which looses information during the transformation
    3. A function with low complexity, but whose inverse is intractable
    4. A function which is computable, but whose inverse is not computable
    5. A function which is surgective but not injective.

  2. [1 point] What is a trap-door? (only one answer please)
    1. A trap for the attacker based on passing false information about the secret key
    2. An information which allows to find out whether there has been an attempt of attack
    3. A trap for the legal party based on corrupting the public key of the other party
    4. An information which makes it easy to compute the inverse of a one-way function
    5. A parameter which transforms an ordinary function into a one-way function

  3. [5 points] For each of the following sentences about symmetric and asymmetric cryptography, say whether it is true or false.
    1. In the asymmetric case each agent has a public key and a private key.   True
    2. In the asymmetric case there is a trusted party who has one public key; all the ordinary agents have secret keys.   False
    3. In the symmetric case the keys satisfy the symmetric property: {{M}k1}k2 = {{M}k2}k1.   False
    4. In the asymmetric case the secret key SK and the public key PK satisfy the following inversion property: {{M}PK}SK = M.   True
    5. In the symmetric case the protocols are symmetric, in the sense that for each action of an agent (during the protocol) there is a complementary reaction of his party.   False

  4. [1 point] What is the CSP? (only one answer please)
    1. A formalism to specify sequential programs (Calculus of Sequential Programs)
    2. A formalism to specify systems of communicating processes (Communicating Sequential Processes)
    3. A security protocol (Casper Security Protocol)
    4. A formal tool to prove the correctness of cryptographic algorithms (Cryptography Soundness Prover)

  5. [2 points] Describe briefly the meaning (behaviour) of the following specification of an intruder. 
       Intruder(X) = learn? m: messages -> Intruder(close(X U {m}))
                 []
                 say! m: X /\ messages -> Intruder(X)
    The symbols U and /\ here represent set union and set intersection.

    Answer: At each step the intruder has two possibilities:

  6. [Bonus question, points 5] Suppose that Angela and Bill live in two different islands and can communicate only by exchanging packages. Each of them also has various chains and locks and a key for each lock. A lock can be opened only by its own key, and there is only one copy of the key.

    The mailman can deliver packages from Angela to Bob and viceversa, but is dishonest and can open and steal or replace the content of any package which is not chained and locked.

    1. How can Angela send something to Bill, assuming that the mailman do not owns any chain/lock/key?

    2. How can the mailman steal the content of the package sent by Angela, if he owns a chain with lock and key?

    Answer:

    1. Angela send a package chained and locked. She keeps the key of the lock, say KA. When Bill receives the package, he adds another chain and lock and keeps the key of this new lock, say KB. Bill then sends the package back to Angela. When Angela receives the package, she removes her chain by unlocking the corresponding lock with KA. Then she sends the package back to Bill. Finally, Bill can open the package by using KB to unchain it.

    2. When Angela first sends the package, the mailman can add his own chain and lock with key KM. Then return the package to Anne, pretending that it comes from Bill. Angela will then remove her own chain and send the package to Bill again, via the mailman. The mailman can now remove his own chain with KM and open the pachage.