Problem Set 3
CSC507/CSC609
Feb 2016

Due: March 2

Problem numbers and pages refer to second edition.

1. Implement the Small Space Birthday Attack, Algorithm 5.9 in the textbook; using
   a truncated form of md5.
   
   Use any computer language or scripting language of your choice. The md5 program
   is available at the command line as "md5" or "md5sum" depending on your flavor
   of unix. For Windows, install Cygwin, or find a native md5 application.
   
   To carry out the attack, and confirm that it works in O(sqrt(n)) time, limit the
   number of bits in md5 as follows. 
   
   Have n as a parameter, take only the leftmost n hexdigits. You can begin with
   anything as x0, in this example the text "0" and the next values are:
   
   # echo -n 0 | md5
   # cfcd208495d565ef66e7dff9f98764da
   # echo -n cfcd | md5
   # 00e091d37ca2bcf0d311e8426925cf09
   # echo -n 00e0 | md5
   $ 3754121ac0f451b4961f6bc97605bb6d

   That is, the sequence for n = 4 is cfcd, 00e0, 3754, ...
   
   Find collisions for n = 4, 6, 8, 10, 12, and 14. Give the number of steps to find the
   collision. Compare to O(sqrt(n)).
   
2. Problem 5.1 in the textbook.

3. Problem 4.26 in the textbook.

4. Matching Pennies Game using Oblivious Transfer.

   The textbook defines a protocol called a commitment scheme.

   To uses a commitment scheme in matching pennies, Alice commits to heads or tails, 
   giving Bob the commitment c. Bob chooses his heads or tails and announces the choice 
   in clear to Alice. Alice then opens her commitment.
   
   A commitment scheme consists of a a commitment protocol and an open protocol.
   Alice choses a message, m, and produces for Bob a commitment c, which is both
   binding and hiding. Later Alice can open the commitment by producing m and additional
   information. Bob is convinced that Alice had previously commited to m because it matches
   the c provided, and Alice is convinced that Bob did not know m even when provided with c, 
   until she opened the commitment.

   We gave an implementation of a commitment scheme using hashing, and indicated that the
   protocol was hiding when the hash is preimage resistant; and that the protocol was
   binding when the hash is second preimage resistant. A collision resistent hash is 
   both preimage and second preimage resistant.
   
   There are several fundamental cryptographic primitives, upon which all cryptography
   can be built. We have seen: the pseudorandom number generator, and the cryptographic
   hash function. Also among these is the protocol of oblivious transfer. 
   
   Oblivious Transfer provides a magic box, T, that can contains left and right
   compartments. In a protocol involving Alice and Bob, Alice chooses t1 and t2 from 
   some declared domain of objects, and places one in the left compartment of T, and 
   the other in the right compartment of T. Alice then gives the box to Bob. 

   Bob is allowed to choose left or right, and receives then t1 or t2, the value that 
   Alice placed in that side of the box.
   
   The requirements of oblivious transfer are:

     * Bob, having received t1 will know nothing about t2 (or about t1 if t2);
     * Alice will not know whether Bob received t1 or t2.
   
   Your challenge is to design a fair matching pennies game using Oblivious Transter,
   and argue it's security.