FPGA Implementation of Whirlpool and FSB Hash AlgorithmsOutlineSlide 3What is a Hash?SHA-3 CompetitionProject GoalsSlide 7Test HarnessHash AbstractionMemoryOn FPGAIn SimulationMessage Input VMH FormatTestingSlide 15Typical Hash StructureSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Whirlpool IntroductionWhirlpool PreprocessingWhirlpool PreprocessorWhirlpool CompressionSlide 30Slide 31Whirlpool ImplementationSlide 33Whirlpool FinalizationWhirlpool ResultSlide 36Fast Syndrome-Based hash functionFSB PreprocessingFSB CompressionSlide 40FSB FinalizationClosing Remarks6.375 Final PresentationJeff Simpson, Jingwen Ouyang, Kyle FritzFPGA Implementation of Whirlpool and FSB Hash AlgorithmsOutline•Overview•Test Harness•Hash Algorithms–Whirlpool–FSB•Closing RemarksOutline•Overview•Test Harness•Hash Algorithms–Whirlpool–FSB•Closing RemarksWhat is a Hash?•A hash is a fingerprint of sorts – a small key which can be used to identify a larger data set.•Hashes have many uses–Identifying that a data set is correct.–Performing database indexing–Cryptographic functionsSHA-3 Competition•National Institute of Science and Technology (NIST) is holding a competition to write the successor to the SHA-2 hashing algorithm.•Over 50 algorithms have been submitted for consideration.•NIST will make the final decision, but the community is performing analysis and making recommendations.Project Goals•Implementation of hash algorithms on the Altera DE2-70 FPGA–Whirlpool hash–FSB hash (SHA-3 candidate, uses Whirlpool)•The process and results of implementing the SHA-3 candidate algorithm will serve as an analysis of the algorithm.Outline•Overview•Test Harness•Hash Algorithms–Whirlpool–FSB•Closing RemarksTest Harness•Provide a layer of abstraction•Simplify memory access•Provide FPGA interface•Provide simple and fast end-to-end testingHash Abstraction•Put Length•Put Word•Get Hash•Get Table Lookup•Put Table Lookup ResponseHash does not need to know anything about memory organization, addressing, or interfaceTest harness does not need to know anything about the Hash function.Memory0400000:040105F – NIOS (4KB)0410000:0417FFF – Input Message (32KB)0440000:0447FFF – Hash Memory (32KB)1000000:17FFFFF – Lookup Tables (8MB, Flash)On FPGA•Intel HEX file is generated from test-case data for loading FPGA•Altera flash image is generated from lookup table•NIOS signals for the hash to start, then reads the result from memory when the hash has completed.In Simulation•Verilog VMH file generated from test-case data, AND lookup table.•Hash is commanded to start automatically.•Result is displayed (saved to output log file)Message Input VMH Format@0002 // Message size in bits (64)@0004 // Data address@0005 // Result address@400000 //Lookup table data (simulation only)Testing•A suite of test-cases is used for automated testing•Reference hashes are automatically generated and compared to the simulation results.•FPGA results can be automatically compared in the same fashion.•A NIOS-based message generator is used to test message input > 32KBOutline•Overview•Test Harness•Hash Algorithms–Whirlpool–FSB•Closing RemarksTypical Hash StructurePreprocessing Compression FinalizationFPreprocessing491dafTypical Hash StructureCompression FinalizationFTypical Hash StructurePreprocessing Compression FinalizationF491daf3cTypical Hash StructurePreprocessing Compression FinalizationF491daf3c00000000Typical Hash StructurePreprocessing Compression FinalizationF491daf3c000000008 020Typical Hash StructurePreprocessing Compression FinalizationF46a931ff3c8020Typical Hash StructurePreprocessing Compression FinalizationF46a931ff3c8020Typical Hash StructurePreprocessing Compression FinalizationFa903bd55Typical Hash StructurePreprocessing Compression FinalizationFa903bd5503bd55Outline•Overview•Test Harness•Hash Algorithms–Whirlpool–FSB•Closing RemarksWhirlpool Introduction•A stand-alone hash function based on a substantially modified Advanced Encryption Standard (AES) •Given a message less than 2256 bits in length, it returns a 512-bit message digest.•Whirlpool is not a SHA-3 candidate•Will never be patented, free for public use•No Bluespec implementations existWhirlpool Preprocessing•Input: A input message being hashed (any size)•Padded input:–A ={ message,1, 0,0,0,…,0,0,0} (512N + 256 bits)–B =message length (256 bits)–Padded input = {A,B} (512 N + 512 bits)•Output: Split the padded input to small message blocks (512 bits each)Message bits Message bits 1 Zeroes Zeroes LengthWhirlpool Preprocessor•Input words are shifted into the message block one bit at a time until any of the following events:–Message block is full: It is sent and a new one is started.–Input word is finished: The next one is loaded.–Message is complete: The block is padded with a 1 and the message length (in bits) before being sent.•Because these events happen independently, the preprocessor does not depend on message size, message block size or input word size.•It requires very little logic, but is rather slow, as it requires 1 cycle per bit, minimally.Input WordsMessage BlockWhirlpool Compression•Inputs:–Current hash from previous iteration (8 bit x 64 vector)–Small message blocks (512 bit)•Output:–Intermediate Hash (8 bit x 64 vector)WWhirlpool Compression•Block Diagram:–init: •takes in message blocks and resets internal states–processBuffer: •computes internal state from an internal block cipher–finalize: •newHash = currentHash ^ input message ^ state •newHash is sent out as result when there is no more input message blocksinit processBuffer finalizeWhirlpool Compression•Internal block cipher in processBuffer:–Originally uses a randomly generated box, lack internal structure, hard to implement efficiently in hardware–Current version uses S-box, which has nice patterns for hardware implementationWhirlpool Implementation•Do one branch at a time–Reuse hardware–Save logic–Take longer time•10 rounds of iteration–Big for-loop takes a lot of logic, and increases critical path–Use counter to break into multiple cyclesWhirlpool Implementation•Use registers with ready bits instead of FIFOs•Put s-box’s lookup table onto SRAM –One table lookup per cycle•Concatenate vectors to avoid multi-layered MUXC3C2C1C0C3[2]C2[1]C1[3]C0[0]C2[1]C[9]C[15:12]C[11: 8]C[
View Full Document
Unlocking...