SHA 1 Algorithm

This describes the working of SHA 1 algorithm that produces hash code.

1. Message Digest Algorithm : SHA-1
Shiva Ram Dam
MScInformation System Engineering
June 12, 2019
Pokhara University
Nepal

2. Introduction
•SHA1: Secure Hash Algorithm 1
•Designed by the United States National Security Agency
•Produces hash value known as Message Digest
2June 12, 2019 SHA-1 Algorithm

3. Salient Features
•Works for any input message that is less than 2
64
bits
•produces160 bits length message digest
•Infeasible to retain the original message from the message digest
•Same message digest to be produced from both sender and
receiver
•Purpose: Authentication , not Encryption
•widely used in security applications and protocols, includingTLS,
SSL, PGP, SSH, IPSec and S/MIME
3June 12, 2019 SHA-1 Algorithm

4. Message-HashcodeExample
abc
Abc
4June 12, 2019 SHA-1 Algorithm
a9993e36-4706816a-ba3e2571-
7850c26c-9cd0d89d
915858af-a2278f25-527f1920-
38108346-164b47f2
SHA

5. Abstract view of SHA
•Input to the SHA can be of
arbitrary length.
•Produces fixed length output
(i.e. 160 bits length)
June 12, 2019 SHA-1 Algorithm 5
SHA 1
Arbitrary Length
H(X)
160 bits
X

6. Steps:
1.Append padding bits
2.Append Length
3.Initialize hash bufffer
4.SHA processing
5.Output
June 12, 2019 SHA-1 Algorithm 6
Padding
X (X1, X2, ….Xn)
Compression
Function
512
bits
160 bits
H(X)
160 bits

7. 1. Padding
Process of adding extra bits (i.e. 0
followed after a 1)
June 12, 2019 SHA-1 Algorithm 7
Padding
X (X1, X2, ….Xn)
Compression
Function
512
bits
160 bits
H(X)
160 bits
Fig: Padding of string "abc" in bits

8. 2. Appending length
•After padding, length of the
message is represented in 24
bit
•In total, the string is a multiple
of 512 bits.
June 12, 2019 SHA-1 Algorithm 8
Padding
X (X1, X2, ….Xn)
Compression
Function
512
bits
160 bits
H(X)
160 bits
Fig: Padding of string "abc" in bits, finalized by the length
of the string, which is 24 bits

9. •This 512 bits input to the
compression function
•The message divided into 16
words.
•Each word consists of 32 bits.
•512/32 =16 words
June 12, 2019 SHA-1 Algorithm 9
Padding
X (X1, X2, ….Xn)
Compression
Function
512
bits
160 bits
H(X)
160 bits

10. 3. Initialize hash buffer
Initial values of Ho are predefined
and stored in registers ABCDE
These initial values are used in
Round 0.
June 12, 2019 SHA-1 Algorithm 10
H Hex values
Ho(A) 01234567
Ho(B) 89ABCDEF
Ho(C) FEDCBA98
Ho(D) 76543210
Ho(E) C3D2E1F0
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
CF

11. 4. SHA Processing
SHA1 has 80 rounds defined.
The Message Scheduler Algorithm
schedules each word to rounds as:
•W
0Round 0
•W
1Round 1
……
•W
15Round 15
•W
16Round 16
…..
•W
79Round 79
June 12, 2019 SHA-1 Algorithm 11
W
tis
calculated
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Word assigning to rounds:

12. 4. SHA Processing (contd.)
June 12, 2019 SHA-1 Algorithm 12
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Word assigning to round 0:

13. 4. SHA Processing (contd.)
June 12, 2019 SHA-1 Algorithm 13
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Word assigning to other rounds:
For others (i.eround 16-79)
W
[t] = S
1
(w
[t-16]XOR W
[t-14]XOR W
[t-8]XOR W
[t-3])
For example: when round is 16,
•W
[16] = S
1
(w
[16-16]XOR W
[16-14]XOR W
[16-8]XOR W
[16-3])
•Here W
0, W
2, W
8and W
13are XORed.
•The output is the new word for round 16.

14. 4. SHA Processing (contd.)
Stages Round
t=1 0 to 19
t=2 20to 39
t=3 40 to 59
t=4 60 to 79
June 12, 2019 SHA-1 Algorithm 14
Each stage has 20 rounds.
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Division of stages:

15. 4. SHA Processing (contd.)
At each stage:
June 12, 2019 SHA-1 Algorithm 15
Stage Predefinedvalue of k
t
1 K
1=0X5A827999
t
2 K
2= 0X6ED9EBA1
t
3 K
3=0X8F1BBCDC
t
4 K
4=0XCA62C1D6
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Constant values:

16. 4. SHA Processing (contd.)
Each round takes 3 inputs:
•32 bit word form 512 bit block
(i.e.W
t)
•The values from register
ABCDE
•Constant K
t
June 12, 2019 SHA-1 Algorithm 16
Source:
https://www.researchgate.net/publication/238180532_An_Architecture_for_a
_SHA1_Applied_for_DSA/figures?lo=1
Process in each round:

17. 4. SHA Processing (contd.)
Stage F
t
t
1 F
t(B.C,D) = (B ANDC) OR((NOTB)
ANDD)
t
2 F
t(B.C,D)= B XOR C XORD
t
3 F
t(B.C,D) = (BANDC) OR(B ANDD)
OR (C AND D)
t
4 F
t(B.C,D) = B XOR C XORD
June 12, 2019 SHA-1 Algorithm 17
Source: https://en.wikipediaorg/wiki/SHA-1
F
tat different stages:

18. 4. SHA Processing (contd.)
June 12, 2019 SHA-1 Algorithm 18
Source: https://en.wikipediaorg/wiki/SHA-1
•Output of F
tand E are added
•Value in register A is 5 bit circular-left
shifted.
•This then added to previous sum.
•W
tis added
•K
tintroduced
•B is circular-left shifted by 30 bits.
New values for next round
At each Round:
Denotes addition module 2
32

19. 5. The Output
June 12, 2019 SHA-1 Algorithm 19
•The 160 bit output from the final
round is modulo added to the initial
predefined values of Ho at registers
ABCDE.
•Output obtained thus is a 160 bit
hash code.
After Final Round:
Initial values of Ho
at ABCDE
32 bits 32 bits 32 bits 32 bits 32 bits
H(X)
160 bits

20. References
•https://resources.saylor.org/wwwresources/archived/site/wp-
content/uploads/2012/07/SHA-1-1.pdf
•https://www.youtube.com/watch?v=YCf80-8xhGs
•https://www.slideshare.net/karteek10/secure-hashing-algorithm
•https://slideplayer.com/slide/8199025/
•https://www.slideshare.net/VishakhaAgarwal4/secure-hash-algorithm
•https://brilliant.org/wiki/secure-hashing-algorithms/
•https://en.wikipedia.org/wiki/SHA-1
20June 12, 2019 SHA-1 Algorithm

21. QA session
21June 12, 2019 SHA-1 Algorithm

22. Thank You
22June 12, 2019 SHA-1 Algorithm