Out: Friday, May 1st, 2009

Due: Monday, May 11th, 2009, before class starts



Turn In: https://catalysttools.washington.edu/collectit/dropbox/andosw/5665




Read chapter 6, and optionally, skim through chapter 7.  These
chapters are hard, but understanding synchronization of threads is one
of the most important things you'll get out of this class.  You will
need to spend time to think about this and to work some problems.

Textbook problems: 6.11, 6.12, 6.13, 6.17 (give pseudocode)


Programming problems:

(1) Using the facilities available to you in the pthreads library,
    i.e., locks [pthread_mutex_init(), pthread_mutex_lock(), etc. ]
    and condition variables  [pthread_cond_init(), pthread_cond_wait(), etc.],
    implement a semaphore package.  You need to (a) decide upon the
    interface to your semaphore package, and codify it in a 451_semaphore.h
    file, and (b) implement the semaphore package in a 451_semaphore.c file.
    Obviously, you should use the C programming language, and implement
    assuming the Linux installation available on forkbomb.cs.

    Be sure to (c) include (rigorous!) test code in a 451_semaphore_test.c file,
    (d) include a Makefile to compile your test program, and (e) comment all
    of your code (including your Makefile!) well.

(2) Using your semaphore package, implement a bounded buffer producer/consumer
    package.  You should (a) decide upon the interface to your bounded buffer
    producer/consumer package, and codify it in a 451_bb_pc.h file, and
    (b) implement the package in a 451_bb_pc.c file.  Use C / Linux / forkbomb,
    as in part 1.

    Be sure to (c) include rigorous test code in a 451_bb_pc.c file,
    and (d) include a Makefile to compile your test program, and (e)
    comment all of your code (including your Makefile) well.
    
(3) Here is a block of AES cyphertext:

  0d 91 49 c6 59 01 e3 53 09 32 19 8c 3e 01 ee dd 
  59 7f b9 22 ab fc 5d c8 88 fd a2 16 85 3c 9d 81 
  e7 d7 66 27 a8 44 e1 62 a7 ee c6 9f 7c 72 2d e5 
  aa 5b 35 39 c0 47 f9 e3 28 e5 af 25 bd 37 ec 8f 
  4f 0f 9e 3f 7f eb ec 94 d4 e6 13 07 97 eb 9b e3 

    Note that it is 80 bytes long, i.e., 5 blocks of 16 bytes.  To
    produce the cyphertext, I encrypted an 80 byte array of plaintext
    ASCII characters, using a 128 bit (i.e., 16 byte) AES encryption
    key, using AES ECB mode encryption.  The last 12 bytes of the
    encryption key were zero, so the key was of the form (in hex):

       XX XX XX XX 00 00 00 00 00 00 00 00 00 00 00 00

    Using your bounded buffer producer consumer implementation, find
    the encryption key that I used, and the plaintext that the
    cyphertext decrypts to using this encryption key as a decryption key.

    You'll need to implement a brute-force key cracker to do this.
    Your implementation should spawn multiple key cracker threads
    (consumers), and a single producer thread that places ranges of
    keys to crack in the bounded buffer.  Make your key ranges (i.e.,
    things you place in the bounded buffer) be blocks of 1024 keys.

    Figure out how many processors your computer has, and spawn that
    number of consumer threads.

    The first person to email me the correct encryption key and plaintext wins!

    Here is a link to AES encryption/decryption code you should use,
    including an example program that shows how to use it in ECB mode:

        http://www.cs.washington.edu/education/courses/cse451/CurrentQtr/homework/aes_451.tar.gz