12-03-2014, 04:16 PM
Hardware Implementation of Hash Functions
Hardware Implementation.pdf (Size: 516.78 KB / Downloads: 56)
Introduction to Cryptographic Hash Functions
Hash algorithm is a type of cryptographic primitives. Hash algorithms take as input
a message of arbitrary length, and produce a hash or message digest as output. This
process can be denoted as:
h D H .M / ;
where M is the input message and h is the hash generated by the hash algorithm H .
Normally, the size of the hash h is fixed by the algorithm. For a cryptographic hash
function, the hash length should be large enough to prevent an attack from finding
two or more messages that generate the same hash. Currently, the most commonly
used hash algorithms are MD5 [1] and SHA-2 [2]
Construction of Hash Functions
Hash function can be constructed in several ways. The Merkle-Damg ̊
ard model,
illustrated in Fig. 2.1, has shown good properties over the years [4], and has been
adopted in the design of many successful hash functions such as MD5 and SHA-2.
In this model, the message is padded and divided into blocks of uniform length.
The blocks are then processed sequentially with a compression function F . Starting
with an initial hash, F repeatedly generates a new intermediate hash value from the
previous one and a new message block. The output of the final compression function
is the hash of the message. The Merkle-Damg ̊
ard model makes it easy to manage
large inputs and produce a fixed-length output. The security of this scheme relies on
the security of the compression function F . It can be proven that if the compression
ard
F is collision resistant then the hash function constructed from the Merkle-Damg ̊
model is also collision resistant [4].
Application of Hash Functions
Hash algorithms can be used to verify data integrity. After receiving data, one
can compute the hash of the received data, and compare it with the hash of the
original data, which may be sent through secure channels or obtained from a trusted
source. If they are the same, there is a high confidence level that the message
was not modified during the transmission (because of the 2nd-preimage resistance).
Nowadays, many software download sites provide the MD5 or SHA-2 hash of the
software available for downloading.
Hash algorithms can also be used together with public-key algorithms to generate
digital signatures. For example, Alice can sign a document by encrypting the hash
of the message with her private key. The ciphertext can be used as Alice’s signature.
Anyone who wants to verify the signature can decrypt the ciphertext with Alice’s
public key, and compare the decrypted value with the hash generated from the
message. This process is shown in Fig. 2.2. The left part of the figure generates
the signature with Alice’s private key, and the right part checks the signature with
her public key.
SHA-2 Performance
Table 2.4 summarizes the best performance of some SHA-2 implementations. The
techniques mentioned in the previous section yield good results. However, SHA-2
is actually slower than MD5 because of the increased level of interdependency and
complexity. These characteristics limit the amount of data forwarding pipelining
and low-level parallel computation that can be applied. Note that we have some
extremely low latency ASIC implementations for SHA-2. This is primarily due to
high clock rate, e.g., approximately 1 GHz in [26, 27].
[b]BLAKE[/b]
Blake is based on the HAIFA iteration mode with a compression function that uses
a modified version of the stream cipher ChaCha. While Merkle-Damg ̊
ard only uses
the previous hash value and the current message block in the compression function,
HAIFA also uses a salt and a counter that indicates how many blocks have been
processed as part of the input [35].
Depending on the message size and word length, different BLAKE hash
functions can be used. BLAKE-224 and BLAKE-256 operate on 32-bit words, with
block size of 512 bits and salt of 128 bits. BLAKE-384 and BLAKE-512 operate
on 64-bit words with block size of 1024 bits, salt of 256 bits. The numbers in the
algorithm name indicate the digest length.