Alan Kaminsky Department of Computer Science Rochester Institute of Technology 4572 + 2433 = 7005
Home Page
Foundations of Cryptography CSCI 662-01 Spring Semester 2018
Course Page

CSCI 662-01—Foundations of Cryptography
Programming Project 2

Prof. Alan Kaminsky—Spring Semester 2018
Rochester Institute of Technology—Department of Computer Science

Overview
The AMD1 Hash Function
Software Requirements
Software Design Criteria
Submission Requirements
Grading CriteriaTest Cases
Late Projects
Plagiarism
Resubmission


Overview

Implement a hash algorithm to learn about implementation of cryptographic functions. Implement a collision attack on the hash algorithm to learn about cryptographic attacks.

Help with your project: I am willing to help you with the design of your project. I am willing to help you debug your project if the code isn't working. However, for help with design or debugging issues you must come see me in person. Either visit me during office hours or make an appointment. I will not help you with design or debugging issues via email. If it's the evening of the project deadline and I have gone home, you are on your own. Plan and work ahead so there will be plenty of time for me to help you if necessary.


The AMD1 Hash Function

Warning:
The AMD1 hash function is weak.
Do not use the AMD1 hash function for any real world application.

AMD1 Hash Algorithm

The AMD1 hash algorithm computes the 32-bit digest of a message (a byte sequence) as follows:

  1. Append padding: Append a byte of 80 (hex) to the message. Append zero or more bytes of 00 (hex) until the length of the message plus the padding is 12 bytes (mod 16). Treat the message length in bytes (not including the padding) as a 32-bit integer; append four bytes consisting of this integer in big-endian order.

  2. Initialization vector: The state (chaining value) is two 32-bit integers, A and B. Initialize these to 414D4431 (hex) and 48617368 (hex), respectively.

  3. Compress message blocks: For each 16-byte block of the padded message, apply the compression function to the state and the message block, replacing the state with the compression function's output.

  4. Return digest: The digest is the final state word A, packed into a four-byte array in big-endian order.

The AMD1 compression function is

Inputs: State words A and B, 16-byte message block M[0..15]
Outputs: Updated state words A and B
orig_A = A
orig_B = B
For r = 0 to 63:
    A = ((A rotr 8) + B) xor M[r mod 16] xor K[r]
    B = (B rotl 3) xor A
A = A + orig_A
B = B + orig_B

where "rotr n" is right rotation by n bits, "rotl n" is left rotation by n bits, "+" is addition (mod 232), and "xor" is bitwise exclusive-or. Note that the message bytes are unsigned values.

The AMD1 round constants K[0..63] (in Java) are

    private static final int[] K = new int[]
        {
        0x243F6A88, 0x85A308D3, 0x13198A2E, 0x03707344,
        0xA4093822, 0x299F31D0, 0x082EFA98, 0xEC4E6C89,
        0x452821E6, 0x38D01377, 0xBE5466CF, 0x34E90C6C,
        0xC0AC29B7, 0xC97C50DD, 0x3F84D5B5, 0xB5470917,
        0x9216D5D9, 0x8979FB1B, 0xD1310BA6, 0x98DFB5AC,
        0x2FFD72DB, 0xD01ADFB7, 0xB8E1AFED, 0x6A267E96,
        0xBA7C9045, 0xF12C7F99, 0x24A19947, 0xB3916CF7,
        0x0801F2E2, 0x858EFC16, 0x636920D8, 0x71574E69,
        0xA458FEA3, 0xF4933D7E, 0x0D95748F, 0x728EB658,
        0x718BCD58, 0x82154AEE, 0x7B54A41D, 0xC25A59B5,
        0x9C30D539, 0x2AF26013, 0xC5D1B023, 0x286085F0,
        0xCA417918, 0xB8DB38EF, 0x8E79DCB0, 0x603A180E,
        0x6C9E0E8B, 0xB01E8A3E, 0xD71577C1, 0xBD314B27,
        0x78AF2FDA, 0x55605C60, 0xE65525F3, 0xAA55AB94,
        0x57489862, 0x63E81440, 0x55CA396A, 0x2AAB10B6,
        0xB4CC5C34, 0x1141E8CE, 0xA15486AF, 0x7C72E993,
        };

Note: The AMD1 initialization vector is "AMD1Hash" in ASCII. The AMD1 round constants are the first 512 hex digits of the fractional part of π. The AMD1 round function is based on the round function of the SPECK block cipher.

Java Class

You will write a Java class named AMD1 that implements the HashFunction interface from the Practical: Hash Function Implementation lecture notes (web site password required). You may NOT alter the HashFunction interface in any way.

I will test your AMD1 class using the Hash program from the Practical: Hash Function Implementation lecture notes (web site password required). You may NOT alter that program in any way.

Test Vectors

Here are test vectors for the AMD1 hash algorithm (hexadecimal).

$ java Hash AMD1 ""
8287b7c2
$ java Hash AMD1 00
9f9433e1
$ java Hash AMD1 01
a0215dd0
$ java Hash AMD1 02
79577b8d
$ java Hash AMD1 03
4d862cb1
$ java Hash AMD1 ff
4b0359fd
$ java Hash AMD1 fe
4914e78e
$ java Hash AMD1 fd
f073baa5
$ java Hash AMD1 fc
5d4378ab
$ java Hash AMD1 0123456789abcdef
848a8551

AMD1 Collision Attack

You will write a Java class named AMD1Collision that finds a collision in the AMD1 hash function. The command line arguments and design of this program are up to you. The program must find a collision within one second. The program must print three lines of output: the first colliding message (hexadecimal), the second colliding message (hexadecimal), and the common digest of the two messages (hexadecimal). Here is an example of what my program prints (your program might be different):

$ java AMD1Collision 0123456789abcdef
0123456789ac80ce
0123456789ac9782
c6eaaa9b

You can verify this collision by running the Hash program on the two messages:

$ java Hash AMD1 0123456789ac80ce
c6eaaa9b
$ java Hash AMD1 0123456789ac9782
c6eaaa9b

You will submit the source file for your AMD1Collision program as part of your project. You will also submit a PLAIN TEXT FILE named collision.txt containing the following information:

  1. A DETAILED NARRATIVE DESCRIPTION (not pseudocode, not program code) of how your program finds a AMD1 collision.

  2. An example AMD1Collision program run showing the EXACT COMMAND you typed to run your program as well as the program's output.


Software Requirements

  1. The project must consist of two and only two Java classes named AMD1 and AMD1Collision, respectively.

  2. Class AMD1 must implement the above HashFunction interface.

  3. Class AMD1 must implement the AMD1 hash algorithm as specified above.

  4. Class AMD1Collision must be a main program that finds a collision in the AMD1 hash function.

    Note: The AMD1Collision program's command line arguments are up to you to specify.

  5. The AMD1Collision program must print three lines of output on the console. The first output line is the first colliding message (hexadecimal). The second output line is the second colliding message (hexadecimal). The third output line is the common digest of the two messages (hexadecimal). There is no whitespace at the beginning or end of each output line. Each output line is terminated with a newline.

  6. The AMD1Collision program's running time must be one second or less.

    Note: If your programs' output does not conform exactly to Requirements 1 through 6, you will lose credit on your project. See the Grading Criteria below.


Software Design Criteria

  1. The programs must use the coding conventions for cryptographic algorithms discussed in class as appropriate.

  2. The programs must be designed using object oriented design principles as appropriate.

  3. The programs must make use of reusable software components as appropriate.

  4. Each class or interface must include a Javadoc comment describing the overall class or interface.

  5. Each constructor and method within each class or interface must include a Javadoc comment describing the overall constructor or method, the arguments if any, the return value if any, and the exceptions thrown if any.

    Note: See my Java source files which we studied in class for the style of Javadoc comments I'm looking for.

    Note: If your program's design does not conform to Software Design Criteria 1 through 5, you will lose credit on your project. See the Grading Criteria below.


Submission Requirements

Your project submission will consist of a ZIP archive containing three files: AMD1.java, AMD1Collision.java, and collision.txt. Put the source files into a ZIP file named "<username>.zip", replacing <username> with the user name from your Computer Science Department account. On a Linux system, the command is:

zip <username>.zip AMD1.java AMD1Collision.java collision.txt

Send your ZIP file to me by email at ark­@­cs.rit.edu. Include your full name and your computer account name in the email message, and include the ZIP file as an attachment.

When I get your email message, I will store your Java source files in a directory. I will set my Java class path to include the directory with your source files, the directory with the interfaces and test programs, and the Parallel Java 2 Library. I will compile the Java source files using the Oracle JDK 1.8 compiler. I will then send you a reply message acknowledging I received your project and stating whether I was able to compile the source files. If you have not received a reply within one day, please contact me. Your project is not successfully submitted until I have sent you an acknowledgment stating I was able to compile the source file.

The submission deadline is Monday, April 2, 2018 at 11:59pm. The date/time at which your email message arrives in my inbox (not the time when I actually read the message) will determine whether your project meets the deadline.

You may submit your project multiple times up until the deadline. I will keep and grade only the most recent successful submission. There is no penalty for multiple submissions.

If you submit your project before the deadline, but I do not accept it (e.g. I can't compile all the source files), and you cannot or do not submit your project again before the deadline, the project will be late (see below). I STRONGLY advise you to submit the project several days BEFORE the deadline, so there will be time to deal with any problems that might arise in the submission process.


Grading Criteria

I will grade your project by:

I will grade the test cases based solely on whether your program produces the correct output as specified in the above Software Requirements. Any deviation from the requirements will result in a grade of 0 for the test case. This includes errors in the formatting (such as extra spaces), incorrect uppercase/lowercase, output lines not terminated with a newline, extra newline(s) in the output, and extraneous output not called for in the requirements. The requirements state exactly what the output is supposed to be, and there is no excuse for outputting anything different. If any requirement is unclear, please ask for clarification.

If there is a defect in your program and that same defect causes multiple test cases to fail, I will deduct points for every failing test case. The number of points deducted does not depend on the size of the defect; I will deduct the same number of points whether the defect is 1 line, 10 lines, 100 lines, or whatever.

When I grade your project, I will run your program on an Ubuntu 16.04 Linux system. The Java class path will include the directory with your compiled class files, the directory with the interfaces and test programs, and the Parallel Java 2 Library. I will run your program from the bash shell command line using Oracle's JDK 1.8; I will redirect your program's console output to a file; and I will look at the file's contents to determine if the output is correct. I STRONGLY recommend that you test your program in the same manner; that is, no Windows, no MacOS, no Eclipse, no IntelliJ, etc. If your program appears to produce the correct output on your machine, but your program does not produce the correct output on my machine, you will nonetheless lose points. If there's any doubt, you may visit me in my office and run your program on my machine.

After grading your project I will put your grade and any comments I have in your encrypted grade file. For further information, see the Course Grading and Policies and the Encrypted Grades.

Test Cases

The grading test case commands and correct outputs were as follows.

1.  java Hash AMD1 0cc7
    859a45a6
2.  java Hash AMD1 24e2fb66
    74f42930
3.  java Hash AMD1 6278017eca46
    f7879c54
4.  java Hash AMD1 a8be2a074f79c87d
    1c8db55c
5.  java Hash AMD1 a61742718b7cf8a5996a
    d15e2c4d
6.  java Hash AMD1 1aa25423c6dbe53c64a81a9a
    26a8af5e
7.  java Hash AMD1 ac6248012e5d93ab4a7e45b20c20
    aae87066
8.  java Hash AMD1 0795324c208515713faaf1290be0b9ad
    affa87cb
9.  java Hash AMD1 8d2984da05784d503a284d766ce1569d85b7
    c813e6aa
10. java Hash AMD1 1802ced306c499076c2b893e09d0171672b2a37a
    06655e28


Late Projects

If I have not received a successful submission of your project by the deadline, your project will be late and will receive a grade of zero. You may request an extension for the project. There is no penalty for an extension. See the Course Policies for my policy on extensions.


Plagiarism

Programming Project 3 must be entirely your own individual work. I will not tolerate plagiarism. If in my judgment the project is not entirely your own work, you will automatically receive, as a minimum, a grade of zero for the assignment. See the Course Policies for my policy on plagiarism.


Resubmission

If you so choose, you may submit a revised version of your project after you have received the grade for the original version. However, if the original project was not successfully submitted by the (possibly extended) deadline or was not entirely your own work (i.e., plagiarized), you are not allowed to submit a revised version. Submit the revised version via email in the same way as the original version. I will accept a resubmission up until 11:59pm Tuesday 10-Apr-2018. You may resubmit your project multiple times up until the deadline; I will keep and grade only the most recent successful resubmission; there is no penalty for multiple resubmissions. I will grade the revised version using the same criteria as the original version, then I will subtract 3 points (10% of the maximum possible points) as a resubmission penalty. The revised grade will replace the original grade, even if the revised grade is less than the original grade.

Foundations of Cryptography CSCI 662-01 Spring Semester 2018
Course Page
Alan Kaminsky Department of Computer Science Rochester Institute of Technology 4572 + 2433 = 7005
Home Page
Copyright © 2018 Alan Kaminsky. All rights reserved. Last updated 06-Apr-2018. Please send comments to ark­@­cs.rit.edu.