MESSAGE INTEGRITY &
MESSAGE
AUTHENTICATION
Goal
■ The message indeed originated from Sender.
■ The message was not tempered with on its way to Receiver.
Hashing
Properties
■ Deterministic — for any input into the cryptographic hash function,
the resulting output will always be the same.
■ Fast — Computing the output of the hash function, given any input, is
a relatively fast process (doesn’t need heavy computation)
■ Unique — Every input into the function should result in a completely
random and unique output (in other words, no two inputs result in the
same output)
■ Irreversible — Given an output of a hash function, the original input
is unable to be obtained
Authentication Key
■ Alice creates message m, concatenates s to m, calculates H(m+s),
sends Bob (m, H(m+s)). H(m+s) here is called the message
authentication code (MAC).
■ Bob receives (m, H(m+s)), calculates the MAC using his s, check
whether it is the same H(m+s) he received from the message.
Message Integrity
Demo
■ [Link]
■ [Link]
Cryptographic Hash function
criteria
■ Preimage resistance
■ Second Preimage resistance
■ Collision resistance
Preimage resistance
■ Given a hash function h and y = h(M), it must be extremely
difficult for intruder to find any message, M’, such that y = h(M’)
Second Preimage resistance
■ It ensures that a message cannot be easily forged
■ Given a specific message and its digest, it is impossible to create
another message with the same digest
Collision resistance
■ It ensures that an intruder cannot find two messages that hash to
the same digest.
Hashing Function
(SHA512)
■ Developed by the National Institute of Standards and Technology (NIST)
■ Also referred as Secure Hash Standard (SHS)
■ Based on MD5
SHA (Secure Hash Algorithm)
■ Generates 512-bit message digest
■ Based on Merkle-Damgard scheme
■ Message digest creation in SHA-512:
SHA-512
Message Preparation
■ SHA-512 insists that the length of the original message be less than 2128
bits
■ This is not usually a problem
■ 2128 bits is probably larger than the total storage capacity of any system
Length field and padding
■ Addition of 128-bit unsigned integer length field to the message defining
the length of the message
■ This is the length of the original message before padding
■ We need to pad the original message to make the length a multiple of 1024
■ Length of the padding field can be calculated as:
■ (|M| + |P| + 128) = 0 mod 1024 => |P|=(-|M|-128) mod 1024
Words
■ SHA-512 operates on words
■ Word = 64 bits
■ After the padding and the length field are added to
the message, each block of the message consists of
sixteen 64-bit words
■ Message digest we get will be of eight 64-bits words
Word
Expansion
■ Before processing, each block must be expanded
■ A block is mode of sixteen 64-bits words
■ SHA-512 needs 80 words in the processing
■ So the 16-word block needs to be expanded to 80 words, W 0
to W79
■ The 1024-bit block becomes the first 16 words
■ The rest of the words come from already-made words
according to the operation shown in fig.
Word Expansion
Message Digest Initialization
Structure of each round
■ The Majority function
– It is a bitwise function
– Takes three corresponding bits in three buffers and do
calculations
– The resulting bit is the majority of three bits
– The two or three bits are 1’s, the resulting bits is 1
– Otherwise 0
Structure of each round
■ The Conditional function
– Also a bitwise function
– Takes three corresponding bits in three buffers and do
calculations
– The resulting bit is the logic “If Ej then Fj; else Gj”
Structure of each round
■ The Rotate function
– Right-rotates the three instance of the same
buffer
– Applies the X-OR operation on the results
Structure of each round
■ The right rotation function RotRi(x), right rotates its argument i bits
■ The addition operator used in the process is addition modulo 264
■ i.e., the result of adding two or more buffers is always a 64-bit
word
■ There are 80 constants K0 to K79, each of 64-bits in hexadecimal
format
■ There are 80 constants, K0 to K79, each of 64
bits. Similar These values are calculated from
the first 80 prime numbers (2, 3,…, 409). For
example, the 80th prime is 409, with the cubic
root (409)1/3 = 7.42291412044. Converting this
number to binary with only 64 bits in the
fraction part, we get
Examples of Hash
References
■ Cryptography and Network Security by William
Stallings
■ Cryptography and Network Security by Behrouz
Forouzan