Cryptographic Hashes, Message Digest and Digital Certificates

Authentication of message is concerned with:

a. Protecting the integrity of a message

b. Validating identity of originator

c. Non-repudiation of origin (dispute resolution)

Authentication Requirements :

a) Disclosure:

• Release of message contents to any person or process not possessing the appropriate cryptographic key

b) Traffic analysis:

• Discovery of the pattern of traffic between parties

• In a connection oriented application, the frequency and duration of connections could be determined

• The number and length of message between parties could be determined on both environment.

c) Masquerade:

• Insertion of messages into the network from a fraudulent source.

• Includes the creation of messages by an opponent that are purported to come from an authorized entity.

• Also included a fraudulent acknowledgements of message receipt or non-receipt by someone else.

d) Content Modification:

• Changes to the contents of a message, including insertion, deletion, transposition and modification

e) Sequence Modification:

• Any modification to a sequence of message between parties, including insertion, deletion and reordering

f) Timing modification

• Delay or replay of messages

• In a connection oriented application, an entire session or sequence of messages could be replay of some previous valid session of individual messages in the sequence could be delayed or replayed.

• In a connection less application, an individual message (e.g Data gram) could be delayed or deplayed.

g) Source Repudiation:

• denial of transmission of message by destination

h) Destination repudiation:

• Denial of receipt of message by destination.

Authentication functions:

Message Authentication :

• A mechanism of source used to notify the integrity of message

• Assures the data received are exactly as sent (i.e. contain no modification, insertion ,deletion or replay)

• Assures that identity of the sender is valid

• When a hash function I used to provide message authentication, the hash function value is often referred to as a message digest.

Authentication function is of two levels of functionality :

• Lower Value produces an authenticator a value used to authenticate a message.

• Higher Value : indicates a receiver to verify the authenticity of message.

Grouped into three classes

• Message Encryption : The ciphertext of the entire message serves as authenticator

• Message Authentication Code (MAC) : The function of the message a secret key that produces a fixed length value that serves as that authenticator.

• Hash Function: A function that maps a message of any length into fixed length hash value which serves as the authenticator

Message Digest :

• A message digest is the summary of message

• Message Digest are used to verify the integrity of the data i.e. to check whether the message was modified or not after the sender sends it and before the receiver receives it.

• Consider an example of message of size 32 bits we arrange these 32 bits into 4 parts of each of 8 bits and place then row wise.

• Now we count the number of 1’s in each column of the numbers of 1’s are even then we say that the column has even parity and even parity is denoted by zero.

• If the number of 1’s are odd then we say that the column has odd parity and we denote it with ‘1’.

• After calculating the parity with the result is known as LRC i.e. Longitudinal Redundancy Check , this LRC is the summary of the original message.

• The sender sends the original message and the LRC to the receiver.

• The receiver separates the message and the LRC to block.

• The receiver calculates its own LRC and check whether LRC matches with sender LRC or not.

• If the values of senders LRC matches with the values of receiver LRC then the receiver has confidence that message was not modified during transmission.

• If the values of senders LRC does not match with the values of receiver LRC then the receiver understands that the message was modified during transmission.

Requirement of the Message Digest :

1. For a given message it must be very easy to calculate its message digest

2. For a given message digest it should very difficult to calculate original message

3. For given two messages if we calculate their message digest then their message digest should be difficult

Message Authentication Code (MAC)

• Use of a secret key to generate a small fixed size block of data called MAC or cryptographic checksum is appended to the message.

• The main difference between message digest and MAC, there is no cryptographic process involved whereas in message authentication code one single key also called as symmetric key is used by the sender and receiver to generate a message authentication code.

• This technique assumes that the two communicating parties say A and B shows a common key ‘k’.

Theory of operation

• When A has a message to send to B, it calculates the MAC as a function of the message and the key

• MAC = C(K,M) where, M= input message C= MAC function K= shared secret key MAC = message authentication code

• The message plus MAC are transmitted to the intended recipient.

• The receiver/ recipient performs the same calculation on the received message using the same secret key to generate a new MAC say Mac_2.

• The received MAC i.e MAC_2 is compared to the calculated MAC

• If the received MAC matches the calculated MAC, then

  a. The receiver is assured that the message has not been altered b. The receiver is assured that the message is from the alleged sender c. If the message includes a sequence number, then the receiver can be assured of the proper sequence.

MAC function :

• Similar to encryption, difference is that the MAC algorithm need not be reversible.

• May to one function.

• The domain of the function consists of messages of some arbitrary length, whereas the range consists of all possible MACs and all possible keys.

  a. If an n bit MAC is used, then there are 2^n possible MACs whereas there are M possible messages with N >> 2^n.

  b. With a k bit key, there are 2^k possible keys

• MAC does not provide a digital signature because both sender and receiver share the same key.

MD-5 hashing algorithm

• This algorithm is used to produce the message digest.

• It produces 128 bit message digest.

• It works in 5 stages

  a. Padding

  b. Append length

  c. Divide into blocks

  d. Initialize the chaining vectors

  e. Process the blocks

Overview of MD5

• Pad message so its length is 448 mod 572

• Append a 64 bit length value to message

• Initialize 4 word (128 bit) MD buffer (A, B, C, D)

• Process message in 16 word (512 bit) blocks

  a. Using 4 rounds of 16 bit operations on message block and buffer

  b. Add output to buffer input to form new buffer value

• Output hash value is the final buffer value.

a. Padding

Consider a message of size 100 bits, the main aim of this step is to make the length of the original message equal to a value which is 64 bit less than the exact multiple of 572

i.e for message of 1000 bits

i.e 512 X 3 is equal to 1536

1536-64 = 1472

1472-1000 = 472

Therefore 472 extra bits will be padded.

The padding bits consists of a single bit which is 1 followed by all 0’s.

The padding length is between 1 to 572

b. Append the length : The length of the message is 64 bits i.e. the length of the original message is expressed as 64 bit and this 64 bit are added after padding.

Total = 512 bits.

i.e the length of the total message is exact multiple of 512.

c. Divide into blocks :

Divide the input message obtained in the above step into blocks of size 512 bits.

d. Initialize the chaining variables :

• In this step we initialize 4 chaining variables ‘A’, ‘B’, ‘C’, ‘D’ each of size 32 bit

• The initial hexadecimal values of these chaining bits are shown as below:

  

• These chaining variables are stored in four variables ‘a’, ‘b’, ‘c’, ‘d’.

e. Process the blocks :

• In this step the actual algorithm begins each block of 512 bits is divided into 16 such blocks each of size 32 bits. There are four rounds in MD5, in each round there are 16 sub blocks as input and a ‘t’ array which consists of constants.

• There are 64 constants and each constant is of size 32 bits.

• Since there are four rounds and we use 16 constants for each round.

• The algorithms first perform a process ‘G’ on the variables ‘b’, ‘c’, ‘d’.

• Process ‘G’ for all the rounds will be different

• After process ‘G’ is ours, we add the result to ‘a’

• Add the result of ‘a’ with all 16 sub blocks

• Add the above result with ‘t’ array

• Performs circular left shift with ‘s’ bits and now add its result with ‘b’ the output of this step becomes the new ‘a’, ‘b’, ‘c’, ‘d’ for round 2

Secure flash algorithm (SHA)

• Most widely used flash function

• Produces 160 bit hash values

• It it based on MD5

• The input is a message with length equal to < 2^64 bits.

• The output is a message digest of length 160 bit

• The processing is done of 572 bit blocks

Steps

• Step1: append padding bits Message is padded with a 1 and as many 0’s as necessary to bring the message length to 64 bits fewer/ less than an even multiple of 512.

• Step2: Append the length 54 bits are appended to the end of the padded message. These bits hold the binary format of 64 bits indicating the length of the original message.

• Step3: Initialize MD buffer

  • 160 but buffer is used to hard the intermediate and final results.

  • The buffer is represented as 5-32 bit registers A,B,C,D,E

  • They are initialized as :

• Step 4: Process the message in 572 bit word blocks

  • The number of rounds = 4

  • Each round has 20 steps

  • Four different logical functions f_1, f_2, f_3, f_4

  • Each round make use of additive constant K_t where 0 <t<79</p>

  • Four different are used

  • The output of the 80^th round is added to the input to the 1^st round to produce the output

• Step 5: Output

  • After all 512 bit block is processed, the output from the I^th stage is 160 bit message digest

Comparison of SHA and MD5

1. Security against brute force attack :

• SHA operations are 2^160

• MD5 operations are 2^128

• It is difficult to have same message digest for two different messages

• Brute force attack is harder for SHA (160 vs 128 bits for MD5)

2. Security against crypt analysis:

• MD5 is undertake, SHA is not vulnerable.

3. Speed:

• MD5 executes faster when compared to SHA due to less but needed, 64 steps vs 80 steps

• Both depend on addition module of 2^32 and could seen well on 32 bit processors.

4. Simplicity and compactness :

• Both are simple to describe and implement.

• MD5 uses little endian, SHA uses big endian.

Hash based Message authentication code (HMAC)

This algorithm involves a cryptographic hash function and a secret cryptographic key. This is more secure than any other authentication code.

HMAC uses the algorithm like MD5 and SHA and checks to replace the embedded hash function with more secure hash function.

Working:

1. HMAC starts with taking a message M containing blocks (L) of length b bits.
2. An i/p signature is padded to the left of the message and the whole is given as input to the hash function which gives a temporary message digest MD'.
3. MD' again is appended to an o/p signature and the whole is applied a hash function again. The result is final message digest MD.

Steps:

1. Make length of key k=b

There are three possibilities.

• k < b
• k = b
• k > b

if k < b then expand 'k' such that it is equal to 'b'

if k = b then no change

if k > b then compress k such that k =b

1. Generation of i/p and o/p signature

$S_i = k^+ XOR ipad$

$S_o = k^+ XOR opad$

• Where $k^+$ is k padded with zeros on the left so that the result is b bits in length.

• ipad and opad are 0011 0110 & 0101 1010 respectively taken b/8 times respectively.

where,

H = Hash function

M = Original Message

$s_i$ = Input signature

$s_o$ = Output signature

$Y_i$ = $i^{th}$ block in original message M where (i = 1 to 2 )

L = N of blocks in MD

K = Secret key for hashing

IV = Initial vector (some constant)

MD' = Temporary message digest = H($S_i$ || M)

MD = Final message digest = H($S_o$ || M') or H($S_0$ || H($S_i || M$))