Applied Cryptography - CSCI 531, Spring 2011

Applied Cryptography - CSCI 531, Spring 2011

General Information

Time	:	MW 9:30am - 10:50am
Location	:	OHE 100C
Instructor	:	Bill Cheng (for office hours, please see instructor's web page), E-mail: <bill.cheng@usc.edu>. (Please do not* send HTML-only e-mails. They will not be read.)*
TA	:	(TBD)
Grader	:	Vikas Ediga, E-mail: <ediga@usc.edu>. (The grader will hold office hours the week after the announcement of each homework assignment's grades.)
Midterm Exam	:	during class, Wed, 3/9/2011 (firm)
Final Exam	:	8am-10am, Fri, 5/6/2011 (firm)

Class Resources

Description	:	textbooks, topics covered, grading policies, additional resources, etc.
Papers	:	required technical papers
Lectures	:	slides from lectures in HTML and PDF formats
Participation	:	rules about rowcalls.
Homeworks	:	homework assignments (please also see important information about programming assignments at the bottom of this page.)
Newsgroup	:	Google Group for discussing course materials and programming assignments. (This group is by invitation only.)

News

(in reversed chronological order)

4/27/2011: The final exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.
The final exam will cover everything from block ciphers (slide 1 of lecture 15) to the end of the last lecture. Here is a quick summary of the topics (not all topics covered are listed):
- block ciphers
  - modes of operation
    - CBC
    - CFB
    - OFB
  - cascade cipher and multiple encryption
    - meet-in-the-middle attacks
    - known-plaintext unicity distance
  - classical ciphers
    - simple transposition ciphers
    - mono-alphabetic substitution cipher
    - polygram substitution cipher
    - homophonic substitution cipher
    - cryptographic codes
    - polyalphabetic substitution cipher
      - Vigenere cipher and variants
      - Jefferson cylinders and rotors and the Enigma machine
  - AES
    - math for Rijndael
      - xtime()
      - multiplication in GF(2⁸)
      - multiplicative inverse in GF(2⁸)
        
        extended Euclidean algorithm
        table method
      - multiplication of polynomials with coefficients in GF(2⁸)
    - components and structure of Rijndael
      - SubBytes() and InvSubBytes()
      - ShiftRows() and InvShiftRows()
      - MixColumns() and InvMixColumns()
      - AddRoundKey()
      - key expansion
    - equivalent inverse cipher
    - security of Rijndael
- Generating Primes
  - math background
    - quadratic residue
    - square root
    - Legendre and Jacobi symbols
    - pseudosquares
    - Blum integers
    - integer factorization
      - Pollard's rho factoring algorithm
    - primality proving algorithms
      - using the factorization of n-1
      - Pocklington's theorem
  - probabilistic primality tests
    - Fermat's test
    - Carmichael number
    - Solovey-Strassen test
    - Miller-Rabin test
  - generating probable primes
    - RANDOM-SEARCH(k,t)
    - incremental search
  - generating provable primes
    - Maurer's algorithm
- Public-key Encryption
  - background
    - extended Euclidean algorithm
    - modular exponentiation algorithm
    - Chinese remainder theorem
    - residue number system
    - Garner's algorithm
  - RSA
    - the RSA problem
    - key generation
    - security of RSA
      - small exponent problem
      - forward search attack
      - multiplicative properties
      - common modulus attack
      - cycling attack
      - message concealing
  - Diffie-Hellman
    - the Diffie-Hellman problem
  - ElGamal
    - key generation
    - encryption/decryption
    - randomized encryption
  - Rabin
    - key generation
    - encryption/decryption
    - finding square roots
- Pseudorandom Bit Generators
  - linear congruential generator
  - polynomial-time statistical tests
    - statistics background
      - normal distribution
      - chi-square distribution
    - five basic tests
      - frequency (mono-bit) test
      - serial (two-bit) test
      - poker test
      - runs test
      - autocorrelation test
  - cryptographically secure PRBG
    - RSA pseudorandom bit generator
    - Blum-Blum-Shub pseudorandom bit generator
- Stream Ciphers
  - synchronous vs. self-synchronizing stream ciphers
  - LFSR
    - connection polynomial
    - linear complexity
    - Berlekamp-Massey algorithm
  - Non-linear FSR
    - de Bruijn FSR
  - Stream ciphers based on LFSRs
    - Geffe generator
    - correlation attacks and correlation immunity
    - summation generator
    - non-linear filter generator and knapsack generator
    - clock controlled generators
      - alternating step generator
      - shrinking generator
  - Stream ciphers not based on LFSRs
    - RC4
    - SEAL
- Hash Functions
  - keyed hash functions
    - MACs
  - unkeyed hash functions
    - MDCs
      - OWHF
      - CRHF
  - hash function properties
    - compression
    - ease of computation
    - preimage resistance
    - 2nd-preimage resistance
    - collision resistance
  - computational resistance for MACs
  - Yuval's birthday attack
  - one-way functions
    - compression functions
    - DES-based one-way functions
    - other one-way functions
  - iterated hash functions
  - Merkle's meta-method for hashing
  - Merkle Damgard strengthening
  - padding
  - MD5 & SHA-1 seriously broken
- HW6, HW7

3/25/2011: The statistics for CS 531 Midterm Exam are:
```
        Count = 22
          Avg = 48.43
       StdDev = 9.63
          Max = 64.50
          Min = 19.50
    
      1 60+ X
      5 55+ XXXXX
      6 50+ XXXXXX
      4 45+ XXXX
      4 40+ XXXX
      0 35+
      1 30+ X
      0 25+
      0 20+
      1 15+ X
```
Please read the following carefully!
I graded your exam. The exam will *not* be returned back to you. If you would like to see/discuss your exam, please make an appointment with me for a 15-minute timeslot during the following periods for the next 2 weeks:
```
       Tue     10:30am - 11:15am
       Thu     10:30am - 11:15am
       Fri     12:30pm -  2:30pm
```
If you are a DEN student, the appointment can be for a phone appointment. Over the phone, I can tell you where you have lost points.
Here are some important rules:
1. You must have an exam appointment in order for you to see and discuss your exam. (This means that if you go ask me a question during office hours, and afterwards, you say, "I know I don't have an appointment, but can I see my midterm?", I would ask you to make an appointment and come back to see your exam during appointment time.)
2. Also, if you make an appointment and do not show up, and do not cancel 30 minutes before your appointment, I will not give you another appointment to discuss your exam. I'm sorry to have to be so strict with this. But I've been stood up by students too many times!
3. When you make an appointment, please e-mail at least 2 of your preferred time slots. Once we have agreed on a time slot, you must either come to the appointment or cancel it 30 minutes before the appointment in order to reschedule.
4. Your appointment will be 15 minutes long. If you are taking up a lot of time and there is another student waiting for the next appointment, I will most likely ask you to make another appointment to finish your current appointment.
Please note that the deadline for discussing about your exam will be Friday, 4/15/2011.
I have applied one standard to all exams. If I have made a mistake was made, I will change your score. But if there was no mistake, there is no point arguing that you should have gotten 2 points here instead of 1 point. Everyone got the same number of points for answering the same way. And please remember, better answers may receive more points.
I always get question regarding class letter grade at this time. At the end of the semester, after all the scores are in, I will plug in all your scores in the equation given on the course description web page and computer your overall score and plot everyone on the same curve. Around the class average is a grade of B+.
By the way, I exepect everyone to get close to perfect scores for the homework assignments since solution guidelines were posted way before the assignments were due. So, please do not expect an A just becuase you do very well in the homework assignments.
One final note... The coverage of the final exam will *not* overlap that of the midterm. So, if the *only* reason you want to discuss your midterm exam is because you are concerned that the same problem will be asked in final exam, then you really don't need to discuss your midterm exam!

3/2/2011: The midterm exam will be closed book, closed notes, and closed everything (and no "cheat sheet"). Also, no calculators, cell phones, or any electronic gadgets are allowed. Please bring a photo ID. Your ID will be collected at the beginning of the exam and will be returned to you when you turn in your exam. There will be assigned seating.
The midterm exam will cover everything from the beginning of the semester till the end of DES (last slide of lecture 14 on 3/2/2011).
Here is a quick summary of the topics (not all topics covered are listed):
- overview
  - functions
    - bi-jections and inverses
    - one-way functions and trapdoor one-way functions
    - permutations
  - encryption schemes
    - max number of permutations
    - model of communication and channels
  - types of adversaries
  - types of cryptanalysis
  - symmetric-key encryption
    - model of communication and channels
    - block ciphers
      - substitution ciphers
        
        mono-alphabetic substitution cipher
        homophonic substitution cipher
        polyalphabetic substitution cipher
      - transposition ciphers
      - composition of ciphers and product ciphers
    - stream ciphers
      - Vernam ciphers and one-time pad
    - key space issues
  - digital signatures
    - signing and verification transformations
  - authentication and identification
    - entity vs. data origina authentication
  - public-key cryptography
    - necessity of authentication
    - digital signature from reversible public-key encryption
  - cryptographic hash functions
    - one-wayness
    - weak collision-resistance
    - strong collision-resistance
    - keyed vs. unkeyed hash functions
  - protocols and mechanisms
    - protocol failures
  - key management
    - symmetric-key and trusted third party
    - public-key and certificate authority
  - attacks
    - ciphertext-only
    - known-plaintext
    - chosen-plaintext
    - chosen-ciphertext
  - security models
    - unconditional security
    - complexity-theoretic security
    - provable security
    - computational security
    - ad hoc security
- block ciphers
  - attacks
    - complexity of attacks
  - modes of operation
    - ECB
  - cryptanalysis of classical ciphers
    - language statistics
    - method of Kasiski
    - index of coincidences
  - DES
    - product ciphers
    - Fiestel
    - DES algorithm
      - P
      - S
      - E
    - DES key scheduling
      - V
      - PC1
      - PC2
    - DES properties
    - DES weak and semi-weak keys
    - cryptanalysis of DES
- HW1, HW2, HW4

1/3/2011:
- Registering with the class mailinglist is required for this class. This is not the same as the class discussion Google Group. You will be receiving HW and exam scores through this list via individual e-mails. If you have not done so, please visit the mailinglist page after the semester starts. (You do not have to be registered for the course to register with the class mailinglist.) In the registration confirmation e-mail, you will also get your user ID and password for accessing protected area of this web site.
- Watch this area for important announcements.

Prerequisites

CS 102L (Data Structures) or graduate standing. It is assumed that you know how to write programs, and how to debug them and make them work correctly.

Important Information about Programming Assignments

All homework assignments are programming assignments to be done in C/C++. No other programming language will be accepted and your program must compile and run with a Makefile on nunki.usc.edu. (Sorry, no Java.) You must be familiar with the UNIX development environment (vi/pico/emacs, cc/gcc or g++/CC, make, etc.)

If a student signs up late for this class, he/she is still required to turn all projects and homeworks on time or he/she will receive a score of 0 for these assignments. No exceptions!