ECE 545 Project



The primary project in this course will be the implementation of a cryptographic hash function, including FPGA synthesis, implementation, and advanced testbench generation. You will use the algorithmic state machine design methodology to design your hardware implementation.

Project Tips/Frequently Asked Questions

  • If you are having problems in synthesis and implementation which says "The design is too large for the given device and package" use a larger Spartan 3 device. By default the device is xc3s50. Choose a larger device, such as a xc3s1000 or xc3s4000, to fix this problem.
  • For this project you can assume the padded_message_length can fit into a single FIFO word (a single 32-bit or 64-bit value). This means you can assume the length of padded message will always be less than 2^32 or 2^64 bits; in the three-block test case the length of the padded message will be 1536 or 3072 bits.
  • When padding a raw_message to create a padded_message because careful of getting too close to the block boundary. Some algorithms (i.e. SHA) need two blocks, not one, to hold the raw_message_length field that is appended at the end during padding (this is different from the padded_message_length). Check the specification of your function carefully. Instead of having a raw message close to the block boundary, it is better to make the raw message slightly short enough such that no boundary issues occur.
  • For those working on SHA variants, you can first test your circuit using the single-block tests given in the SHA specification PDF. This will show you step by step what values should be in your registers; this will help with debug. After this, you can perform your three-block test.
  • Be careful of any endianness issues (MSB to LSB, or LSB to MSB) which may occur between the C code and VHDL code.
  • For the testbench, you should instantiate an input FIFO, output FIFO, and the hash function. In the testbench, you should first put the hash function in reset mode and hold it in reset. Then, you should write the value of 1536 or 3072 into the input FIFO. Then, load the values from hash_input.txt into the input FIFO. Then, stop writing to the input FIFO. HW6 solutions given an example of this. After the input FIFO is written, de-assert the reset of the hash function; since the input FIFO hold data, the hash function will begin to operate. After it is done it will write data to the output FIFO. You can compare the contents of the output FIFO with hash_output.txt to see if the function worked. NOTE: If you use this method, you should have a different reset signal going to the FIFOs versus the hash function.
  • For post-synthesis simulation in Aldec, if you are using a separate FIFO VHDL file, be sure to place that VHDL filename in your list of files to be simulated.
  • If you are running Aldec, and having issues with simulations after recompiling or making changes to the VHDL code, you can always start a project from scratch to be safe. Or, you can use the "Design...Clear Implementation Data" command (removes synthesis and implementation data) and the "Workspace...Delete Simulation Data" command (removes simulation data).
  • For post-route simulation, you may need to slow your clock down considerably beyond what the tool reports. For example, if you are having problems, trying running slow, such as at 100 ns. The reason you may get errors is that the critical path reported by the tools does not take into account delay to and from the FPGA input pads, which may be longer than the critical path internally. Your core may be able to run at 10 ns, but the input/output paths to the pads may take 20 ns, so run slower to make sure you do not have issues.
  • You do not need need to synthesize the FIFOs because they are only part of the testbench. Synthesize the hash function only.

    Slides

    Slides-Set 1-Project Intro
    Slides-Set 2-Project Details (updated p. 14, 15, 21, 23, 25, 30, 31)
    Slides-Set 3-Hash Function Padding

    Entity

    To standardize your design, use the following entity EXACTLY:

    entity [hashname] is -- use sha1, sha256, sha512, tiger, or ripemd160 as entity name instead of [hashname]
      port (
        clock: in std_logic;
        reset: in std_logic;
        idata: in std_logic_vector(31 downto 0); -- use (63 downto 0) for TIGER and SHA-512
        fifoin_read: out std_logic;
        fifoin_empty: in std_logic;
        odata: out std_logic_vector(31 downto 0); -- use (63 downto 0) for TIGER and SHA-512
        fifoout_write: out std_logic;
        fifoout_full: in std_logic);
    end [hashname];

    Deadlines

    Part 1 - Team Selection (Due: Tuesday, September 16, 2008, 4:00 pm)
    In this project you will work in groups of two. If you prefer (due to work, family, personal reasons, etc.) to work alone you may do so. However, the requirements of the project are the same for a group of one or two. By the due date, email Dr. Hwang to let him know: Part 2 - Test Vectors, Pseudocode, High-Level ASM (Due: Tuesday, October 7, 2008, 4:00 pm)
    In this part of the project you will create test vectors for your hash function, write the pseudocode for the algorithm, and create a high-level algorithmic state machine.

    Test Vectors
    Create test vectors that you will use for your VHDL implementation. Start with a software implementation (i.e. C code) and perform the following steps:
    1. 1. Create a raw message to be hashed.
    2. 2. Pad this raw message to create a padded message. Make sure the raw message is long enough such that the padded message is exactly three input blocks (i.e. the padded message should be exactly 1536 bits for SHA-1, SHA-256, RIPEMD-160, and TIGER and exactly 3072 bits for SHA-512).
    3. 3. Create a file, called hash_input.txt which holds the padded message in the following format (useful for VHDL):
      • For SHA-1, SHA-256, and RIPEMD-160: each line of the text file should hold a 32-bit input value in hexadecimal format (i.e. ABCD304F). For example, for a 1536-bit padded message, there will be 48 lines in the text file.
      • For TIGER and SHA-512: each line of the text file should hold a 64-bit input value in hexadecimal format (i.e. ABCD304FE4562B08). For example, for a 1536-bit padded message for TIGER, there will be 24 lines in the text file; for a 3072-bit padded message for SHA-512, there will be 48 lines in the text file.
    4. 4. Create a file, called hash_output.txt which holds the hash function output in the following format (useful for VHDL):
      • For SHA-1, SHA-256, and RIPEMD-160: each line of the text file should hold a 32-bit output word in hexadecimal format. For example, SHA-1 creates a 160-bit hash value, so there will be 5 lines in the text file.
      • For TIGER and SHA-512: each line of the file should hold a 64-bit output word in hexadecimal format. For example, SHA-512 creates a 512-bit hash value, so there will be 8 lines in the text file.
    NOTES: Pseudocode
    Write pseudocode for your algorithm, including receiving input data, hash processing, and writing output data. You do not need to turn in your pseudocode, but you should use it to produce your high-level ASM.

    High-level Algorithmic State Machine (ASM)
    Produce a high-level ASM for your design. Make sure you pay special attention to using the correct steps to read data into your module, incrementing the counters, counting to the correct values during hash function execution, and using the correct steps to write data from your module. Remember: Some "internal" controls to your datapath will be generated in the datapath and used in the datapath; since these "internal" controls never leave the datapath they do not need to be accounted for in the high-level ASM.

    What to Submit
    Submit your test vector files (plus brief paragraph of explanation) and high-level ASM (either drawn electronically, or hand-drawn and scanned) via Blackboard.

    Part 3 - Datapath, Controller ASM (Due: Tuesday, October 21, 2008, 4:00 pm)
    In this part of the project you will create your datapath block diagram, top-level interface diagram, and detailed controller ASM.

    You should submit:
    1. 1. [Optional: High-level ASM, if you made any changes. No need to turn in if no changes were made.]
    2. 2. Datapath block diagram of the design. You can show the datapath on multiple pages in a hierachical format if you wish.
    3. 3. Top-level interface diagram of design.
    4. 4. Detailed controller ASM. This should include exact signal names going to/from the controller and to/from the outside world.
    When you turn in the final datapath, controller ASM, and top-level interface diagram, I should be able to take these and code VHDL from them. Submit all files via Blackboard; scan in any hand-drawn diagrams.

    Part 4 - VHDL, Results, and Project Report (Due: Tuesday, November 25, 2008, 4:00 pm)
    In this part of the project you will submit your final design (targeted to Spartan 3) and all related files.

    You should submit the following via Blackboard:
    1. 1. Project report document in Word .doc or PDF format. Your project report is a significant part of your project grade. Be sure to take adequate time to create a clear and readable report. Your project report should include the following sections, labeled from (a) through (j):
      1. (a) Summary of project.
        -  Discuss whether you completed all parts of the project successfully. If not, discuss how far you got on the project.
        -  Discuss whether functional, post-synthesis (post-translate), and post-route simulation matched the expected output (hash_output.txt) given the input (hash_input.txt). If not, discuss how you verified your design.
        -  Discuss whether the design and test bench met the specification (entity ports correct, testbench used fifos and file input/output, etc.).
        -  Discuss problems encountered, deviations from specification, unresolved issues, etc.
      2. (b) Summary of optimizations made to your design. Specifically, make sure to discuss whether you were able to overlap data input cycles with hash function computation cycles. Discuss any other optimizations performed. You can go through the list in Lecture 11 as a framework for this section.
      3. (c) List of source code and short description VHDL files. List of test bench files.
      4. (d) Brief explanation of top-level test bench. Discuss any issues you had with the test bench, test files, etc. Discuss how you obtained hash_input.txt and hash_output.txt from a non-VHDL source (C, Java, Matlab, hash calculator, etc.), including how you obtained the padded message (hash_input.txt) from a raw message.
      5. (e) TABLE 1: Results after synthesis, including
        -  resources (exact Spartan 3 device used, slices, LUTs, flip flops, BRAMs--as much information as the synthesis tool reports)
        -  maximum clock frequency after synthesis (MHz)
        -  minimum clock period after synthesis (ns)
        -  clock cycles between input blocks (cycles). See Lecture 9 for information on this.
        -  maximum throughput (Mb/s) = (512 or 1024 bits per input block) / (minimum clock period * clock cycles between input blocks)
        -  the number of warnings reported during synthesis
        -  the number of errors reported during synthesis
      6. (f) Synthesis discussion. Discuss the major warnings or errors reported in synthesis. Discuss if post-synthesis (or post-translate) simulation output matched the expected hash output. Discuss any other problems encountered or improvements made related to synthesis.
      7. (g) TABLE 2: Results after implementation, including
        -  resources (exact Spartan 3 device used, slices, LUTs, flip flops, BRAMs)
        -  maximum clock frequency after implementation (MHz)
        -  minimum clock period after implementation (ns)
        -  clock cycles between input blocks (cycles). See Lecture 9 for information on this.
        -  maximum throughput (Mb/s) = (512 or 1024 bits per input block) / (minimum clock period * clock cycles between input blocks)
        -  the number of warnings reported during implementation (translate, mapping, place, route)
        -  the number of errors reported during implementation (translate, mapping, place, route)
      8. (h) Implementation discussion. Discuss the major warnings or errors reported in implementation. Discuss if post-route simulation output matched the expected hash output. Discuss any other problems encountered or improvements made related to implementation.
      9. (i) Discussion of critical path in the design.
      10. (j) Final versions of datapath block diagrams, detailed controller ASM, high-level interface diagram. These should be scanned.
    2. 2. All VHDL source code files.
    3. 3. All VHDL testbenches and test files (i.e. hash_input.txt, hash_output.txt). The testbench should instantiate an input FIFO, an output FIFO, and the hash engine. Also include all non-VHDL code you used to generate hash_input.txt and hash_output.txt (i.e. C, Java, Matlab, hash calculator, etc.).
    4. 4. Simulation waveforms for three points: 1) functional simulation, 2) post-synthesis or post-translate simulation, 3) post-route simulation. Test your design at some reasonable clock frequency (i.e. 10 MHz) and not the maximum clock frequency. These waveforms are very important for your final grade!
    5. 5. Synthesis report, implementation report(s), static timing analysis report

    Hash Functions

    SHA-1
    Teams: Rogawski & Xin, Brewster, Worrell, Tarlecki
    Hash Function Information: NIST PDF Specification, Wikipedia
    Reference Code: Search the web. For example, here is one example. Be sure to test any code against some NIST test vectors to ensure compliance.
    Example FPGA Implementation: paper slides

    SHA-256
    Teams: Ford & Charankar, Mbonu, Williams, Win
    Hash Function Information: NIST PDF Specification, Wikipedia
    Reference Code: Search the web. For example, here is one example. Be sure to test any code against some NIST test vectors to ensure compliance.
    Example FPGA Implementation: paper slides

    SHA-512
    Teams: Cressin & Nguyen, Homsirikamol & Adane, Sobczyk
    Hash Function Information: NIST PDF Specification, Wikipedia
    Reference Code: Search the web. For example, here is one example. Be sure to test any code against some NIST test vectors to ensure compliance.
    Example FPGA Implementation: paper slides

    RIPEMD-160
    Teams: Villareal & Mitchell, Doan & Gewertz, Kelly
    Hash Function Information: PDF Specification, Project Web Page, Wikipedia
    Reference Code: Project Web Page
    Example FPGA Implementation: paper1 paper2

    TIGER
    Teams: Sharma and Abirami, Chaudhry, Kormendi, Koonaparaju
    Hash Function Information: HTML Specification, Project Web Page, Wikipedia
    Reference Code: Project Web Page
    Example FPGA Implementation: paper
    Notes: The TIGER project is being supervised by Dr. Kris Gaj (kgaj@gmu.edu). Email Dr. Gaj with questions on this project. A note about padding: there is a minor discrepancy between the specification and the C code; follow the C code method of padding. This should not affect your project (since padding is not done in VHDL) but you should be aware of the issue, which is noted here (scroll to Tiger section).