m
 m




 
 Content:

‡ Introduction.
‡ General Overview of Cryptography.
‡ SHA History.
‡ Hash Function.
‡ Message Padding.
‡ Computing The Message Digest.
‡ SHA-0 and SHA-1.
‡ SHA-0 and SHA-1 Diagram.
‡ Data Flow Diagram of SHA.
‡ Hash algorithms are called secure.
‡ Alternate Method of Computation.
‡ SHA Core applications.
 Introduction
‡ This standard specifies four secure hash algorithms, SHA-1 , SHA-256, SHA-384, and SHA-
512. All four of the algorithms are iterative, one -way hash functions that can process a
message to produce a condensed representation called a message digest . These algorithms
enable the determination of a message ͛ s integrity: any change to the message will, with a
very high probability, result in a different message digest. This property is useful in the
generation and verification of digital signatures and message authentication codes, and in
the generation of random numbers (bits). Each algorithm can be de scribed in two stages:
preprocessing and hash computation. Preprocessing involves padding a message, parsing
the padded message into m-bit blocks, and setting initialization values to be used in the
hash computation. The hash computation generates a message schedule from the padded
message and uses that schedule, along with functions, constants, and word operations to
iteratively generate a series of hash values. The final hash value generated by the hash
computation is used to determine the message digest. The four algorithms differ most
significantly in the number of bits of security that are provided for the data being hashed ʹ
this is directly related to the message digest length. When a secure hash algorithm is used
in conjunction with another algorithm, there may be requirements specified elsewhere
that require the use of a secure hash algorithm with a certain number of bits of security.
‡ For example, if a message is being signed with a digital signature algorithm that provides
128 bits of security, then that signature algorithm may require the use of a secure hash
algorithm that also provides 128 bits of security (e.g., SHA-256). Additionally, the four
algorithms differ in terms of the size of the blocks and words of data that are used during
hashing.
 General Overview of Cryptography

‡ Cryptography is the study of encryption and

decryption schemes.
ʹ Used to uphold the security principles of
confidentiality and integrity
 SHA history

‡ 1993
± The hash function SHA-0 was issued as a federal standard by NIST

‡ 1995
± SHA-1 published as the successor to SHA-0

‡ 2002
± SHA-2 variants
‡ SHA-256, SHA-384, and SHA-512 published
‡ 2004
± SHA-224 published
 Hash function

‡ Hash function ʹ
A hash function H is a transformation that takes a variable-size input m and returns a fixed-
size string, which is called the hash value h (that is, h = H(m)). Hash functions with just this
property have a variety of general computational uses, but when employed in
cryptography the hash functions are usually chosen to have some additional properties.
The basic requirements for a cryptographic hash function are:
the input can be of any length,
the output has a fixed length,
H(x) is relatively easy to compute for any given x ,
H(x) is one-way,
H(x) is collision-free.
A hash function H is said to be one-way if it is hard to invert, where "hard to invert" means
that given a hash value h, it is computationally infeasible to find some input x such that
H(x) = h. If, given a message x, it is computationally infeasible to find a message y not equal
to x such that H(x) = H(y) then H is said to be a weakly collision-free hash function. A
strongly collision-free hash function H is one for which it is computationally infeasible to
find any two messages x and y such that H(x) = H(y).
‡The hash value represents concisely the longer message or document from which it
was computed; one can think of a message digest as a "digital fingerprint" of the
larger document. Examples of well-known hash functions are MD2 and MD5 and
SHA. Perhaps the main role of a cryptographic hash function is in the provision of
digital signatures. Since hash functions are generally faster than digital signature
algorithms, it is typical to compute the digital signature to some document by
computing the signature on the document's hash value, which is small compared to
the document itself. Additionally, a digest can be made public without revealing the
contents of the document from which it is derived. This is important in digital time
stamping where, using hash functions, one can get a document time stamped
without revealing its contents to the times tamping service.
 MESSAGE PADDING

‡ The SHA-1 is used to compute a message digest for a message or data file that is provided
as input. The message or data file should be considered to be a bit string. The length of the
message is the number of bits in the message (the empty message has length 0). If the
number of bits in a message is a multiple of 8, for compactness we can represent the
message in hex. The purpose of message padding is to make the total length of a padded
message a multiple of 512. The SHA-1 sequentially processes blocks of 512 bits when
computing the message digest. The following specifies how this padding shall be
performed. As a summary, a "1" followed by m "0"s followed by a 64-bit integer are
appended to the end of the message to produce a padded message of length 512 * n. The
64-bit integer is l, the length of the original message. The padded message is then
processed by the SHA-1 as n 512-bit blocks.
Suppose a message has length l < 264. Before it is input to the SHA-1, the message is padded
on the right as follows:
a. "1" is appended. Example: if the original message is "01010000", this is padded to
"010100001".
b. "0"s are appended. The number of "0"s will depend on the original length of the
message. The last 64 bits of the last 512-bit block are reserved for the length l of the
original message.
 COMPUTING THE MESSAGE
DIGEST
‡ The message digest is computed using the final padded message. The
computation uses two buffers, each consisting of five 32-bit words, and a
sequence of eighty 32-bit words. The words of the first 5-word buffer are
labeled A,B,C,D,E. The words of the second 5-word buffer are labeled H0,
H1, H2, H3, H4. The words of the 80-word sequence are labeled W0, W1,...,
W79. A single word buffer TEMP is also employed.
To generate the message digest, the 16-word blocks M1, M2,..., Mn
defined in Section 4 are processed in order. The processing of each Mi
involves 80 steps.
Before processing any blocks, the {Hi} are initialized as follows: in hex,
‡ H0 = 67452301
‡ H1 = EFCDAB89
‡ H2 = 98BADCFE
‡ H3 = 10325476
‡ H4 = C3D2E1F0.
Now M1, M2, ... , Mn are processed. To process Mi, we proceed as follows:
a. Divide Mi into 16 words W0, W1, ... , W15, where W0 is the
left-most word.
b. For t = 16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).
c. Let A = H0, B = H1, C = H2, D = H3, E = H4.
d. For t = 0 to 79 do
TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;
E = D; D = C; C = S30(B); B = A; A = TEMP;
e. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.
After processing Mn, the message digest is the 160-bit string
represented by the 5 words
H0 H1 H2 H3 H4.
 SHA-0 and SHA-1

‡ The original specification of the algorithm was published in 1993 as the m
 
m 
, by US government standards agency NIST (National Institute of
Standards and Technology). This version is now often referred to as m . It was
withdrawn by NSA shortly after publication and was superseded by the revised
version, published in 1995 in FIPS PUB 180-1 and commonly referred to as m .
SHA-1 differs from SHA-0 only by a single bitwise rotation in the message
schedule of its compression function; this was done, according to NSA, to correct
a flaw in the original algorithm which reduced its cryptographic security.
However, NSA did not provide any further explanation or identify the flaw that
was corrected. Weaknesses have subsequently been reported in both SHA-0 and
SHA-1. SHA-1 appears to provide greater resistance to attacks, supporting the
NSA͛s assertion that the change increased the security.
‡ SHA-1 (as well as SHA-0) produces a 160-bit digest from a message with a
maximum length of (264 о 1) bits. SHA-1 is based on principles similar to those
used by Ronald L. Rivest of MIT in the design of the MD4 and MD5 message
digest algorithms, but has a more conservative design
 SHA-0 and SHA-1 Diagram

One iteration within the SHA-1 compression function. A, B, C, D and E are 32-bit words of the
state; r is a nonlinear function that varies;
denotes a left bit rotation by 
;
varies for each
operation. Wt is the expanded message word of round t, Kt is the round constant of round
t. denotes addition modulo 232.
 DATA FLOW DIAGRAM OF SHA

‡ SHA may be used to hash a message, M, having a length of up to 2^64-1

bits. The message is divided into eighty, 4 bytes words. The algorithm
uses five working variables of 4 bytes each, and a hash value of five, 4
bytes words. The final result of SHA is a 160-bit message digest. The
following diagram shows the basic data-flow of a SHA operation
 Hash algorithms are called secure

‡ It is impossible to find a message that corresponds to a given message digest.

‡ It is impossible to find two different messages that produce the same message
digest.
‡ If a message is changed even by a single character, the result will be a completely
different message digest.
‡ SHA has these properties and is therefore referred to as secure. It is designed to
work with the Digital Signature Algorithm (DSA). SHA is a one-way hash function.
One-way functions are characterized by two properties. The first is that they are
one-way. This means that you can take a message and compute a hash value, but
you cannot take a hash value and recreate the original message. It is also
collision-free and, thus, no two messages can hash to the same value.
‡ SHA produces a 160-bit message digest with a maximum length of 264 ?1. The
message M to be hashed must have a length of l bit, where 0 l 264. The message
digest is the fixed-length output of a message. The message digest is then input
to
 the DSA, which will then generate the signature for the message.
Signing the message digest instead of the message offers improved
performance because the message digest will be much smaller
than the message.
‡ The recipient of the message will then use the same hash algorithm
to verify the signature. Any change that occurs during transit will result
in a different message digest and, thus, the signature will not verify.
Once it is verified as true, the recipient is able to unlock the message.
This method prevents unauthorized users from viewing messages that
are not intended for them.
‡ When computing a message digest, SHA processes blocks of 512 bits.
The total length of the messagedigest will be a multiple of 512.
This process is known as padding of the message.
 ALTERNATE METHOD OF COMPUTATION

‡ The above assumes that the sequence W0, ... , W79 is implemented as an array of eighty 32-
bit words. This is efficient from the standpoint of minimization of execution time, since the
addresses of Wt-3, ... ,Wt-16 in step (b) are easily computed. If space is at a premium, an
alternative is to regard { Wt } as a circular queue, which may be implemented using an array
of sixteen 32-bit words W[0], ... W[15]. In this case, in hex let MASK = 0000000F. Then
processing of Mi is as follows:
‡ a. Divide Mi into 16 words W[0], ... , W[15], where W[0] is the left-most word.
‡ b. Let A = H0, B = H1, C = H2, D = H3, E = H4.
‡ c. For t = 0 to 79 do
s = t ^ MASK; if (t >= 16) W[s] = S1(W[(s + 13) ^ MASK] XOR W[(s + 8) AND MASK] XOR W[(s + 2)
^ MASK] XOR W[s]); TEMP = S5(A) + ft(B,C,D) + E + W[s] + Kt;
‡ E = D; D = C; C = S30(B); B = A; A = TEMP;
‡ d. Let H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.
 SHA Core applications
‡ SHA has been used for data integrity, authentication, and digital signatures in
many networks and storage systems. The core may be used to implement the
HMAC algorithm as defined in FIPS 198. HMAC-SHA-1 is used for IPsec and
TLS/SSL protocols. SHA can also be found in electronic funds transfers and
storage applications both for authentication and data integrity. SHA-1 can be
used in a variety of applications:

‡ Security applications that require authentication

‡ E-mail
‡ Electronic funds transfer
‡ Software distribution
‡ Data storage