Cryptographic Hash Function

 1. Cryptographic Hash Function : 

A hash function H accepts a variable-length block of data M as input and produces a fixed-size hash value h = H(M). A good hash function have always input and outputs that are evenly distributed and apparently random. The hash function works on data integrity. so change in any bit say 'M' it will change to the hash code. 

This kind of hash function are needed for security applications and referred to as a cryptographic hash function. 

A cryptographic hash function is an algorithm which is computationally infeasible and having some properties : 

A. The one way property.

B. The collision free property. 


Fig. 1. Cryptographic Hash Function; h = H(M)


2. Application of Cryptographic Hash Function : 

 It is widely used in security applications and internet protocols. 

2.1 Message Authentication : It is a mechanism or service used to verify the integrity of a message. It means it assures that the data sent are exactly what you received. When a hash function is used to provide a message authentication, the hash function value is often referred to as a message digest. 

message digest : A message digest algorithm or a hash function is a procedure that maps input data of an arbitrary length to an output of fixed length. 

The hash function must be protected and transmitted in secure fashion.

Suppose a message is transmitted with some calculation of hash value and on the receiver side the receiver calculates the same hash calculation if there is some  mismatch between the hash values then receiver understand that there is a person in the middle of the communication. 

Fig. 2 Attack Against Hash Function

Figure 3, 4, 5, 6. discuss a variety of ways in which a hash code can be used to provide message authentication. 

The message plus concatenated hash code is encrypted using symmetric encryption. because only A and B share the secret key, the message must have come from A and has not been altered. The hash code provides the structure or redundancy required to achieve authentication. Because encryption is applied to the entire message plus hash code, confidentiality is also provided (as seen in Fig. 3). 
Fig. 3

only hash code is encrypted, using symmetric encryption. This reduces the processing burden for those applications that do not require confidentiality (as seen in Fig. 4). 
Fig. 4


It is processing to use a hash function but no encryption for message authentication. The technique assumes that the two communicating parties share a common secret value S. A computes the hash value over the concatenation of M and S and append the resulting hash value to M. Because B possesses S, it can recompute the hash value to verify. Because the secret value itself is not sent, an opponent cannot modify an intercepted message and cannot generate a false message (as seen in Fig. 5). 
Fig. 5


Confidentiality can be added to the approach of method discussed above by encrypting the entire message plus the hash code (as seen in Fig. 6). 
Fig. 6

Note 1 : Message authentication is achieved using a message authentication code. 😖 Don't worry Message authentication code will be discussed deeply in my upcoming blogs.😎  

2.2 Digital Signatures :
 In case of digital signature the hash value is encrypted user's private key. Anyone who knows the user's public key can verify the integrity of the message that is associated with the digital signature. In this case, an attacker who wishes to change the message, would need to know the user's private key. The implications of digital signatures so beyond just message authentication. 
The below figure (as shown in Fig. 7) described a simplified manner, how a hash code is to provide a digital signature. 
Fig. 7 : Simplified Examples of Digital Signatures

2.3 Other Application :
Hash Function are commonly used to create a one way password file. There is a scheme in which a hash of a password is stored by an operating system rather than the password itself. Thus the actual password is not retrievable by a hacker who gains access to the that password is compared to the stored hash value for verification. 
Hash functions can be used for intrusion detection and virus detection. 

3. Two Simple Hash Functions : 
In this case, I will present two simple, insecure hash functions. All hash functions operate using the following general principles. 
The input is seen as a sequence of n bits. The input is processed one block at a time in an iterative fashion to produce an n-bit hash function. 

Ci = Bi1 xor Bi2 xor -----Bm

Here Ci = ith bit of the hash code, 1<=i<=n
m = number of n-bit blocks in the input
Bij = ith bit in jth block

This operation produce a simple parity for each bit position and is known as a longitudinal redundancy check. 
Each n bit hash value is equally likely. The probability that a data error will result in an unchanged hash value is (1/(2^n)). So data is less effective for more predictably.

A simple way to improve matters is to perform a one bit circular shift or rotation on the hash value after each block is processed. 
The procedure can be compressed as below-
A. Initially set the n bit hash value to zero .
B. Process each successive n-bit block of data as follows--
    a. Rotate the current hash value to the left by one bit. 
    b. Xor the block into the hash value.

Fig. 8: Two Simple Hash Functions


Encryption with Xor or rotate Xor is useless, unless message is not encrypted with that functions. 

Given a message  'M' consisting of a sequence of 64 bit blocks X1, X2, ----Xn defines the hash code h = H(M) as the block by block XOR of all blocks and append the hash code as the final block. 

    h = Xn+1 = X1 xor X2 xor -----xor Xn

Next, encrypt the entire message plus hash code using CBC mode to produce the encrypted message     Y1, Y2,---Yn+1.

    X1 = IV xor D(K,Y1)
    Xi = Yi-1 xor D(K, Yi)
    Xn+1 = Yn xor D(K, Yn+1)

But, Xn+1 is the hash code:
    Xn+1 = X1 xor X2 xor -------xor Xn
             = [IV xor D(K, Y1)] xor [Y1 xor D(K, Y2)] xor---xor [Yn-1 xor D(K, Yn)]

The terms in the preceding equation can be xored in any order, it follows that that the hash code would not change if the ciphertext block user permutated.    

4. Security Requirement for Cryptographic Hash Functions  : 

Table 1 : Requirements for a cryptographic Hash Function H. 

Requirements

Description

1. Variable Input Size

H can be applied to a block of data of any size.

2. Fixed Output Size

H produces a fixed length output.

3. Efficiency

H(x) is relatively easy to compute for any given x, making both hardware and software implementations practical.

4. Preimage resistant (one-way property)

For any given hash value h, it is computationally infeasible to find y such that H(y) = h

5. Second preimage resistant (weak collision resistant)

For any given block x, it is computationally infeasible to find y!=x with H(x) = H(y)

6. Collision resistant (strong collision resistant)

It is computationally infeasible to find any pair (x,y) such that H(x) = H(y).

7. Pseudorandomness

Output of H meets standard tests for pseudorandomness.


5. Hash Function Based on Cipher Block Chaining : 

Divide a message M into fixed size blocks M1, M2,----Mn and use a symmetry encryption system such as DES to compute the hash code G as
    Ho = initial value
    Hi = E(Mi,Hi-1)
    G = Hn

This is similar to CBC technique, but in this case, there is no secret key. This scheme is subject to the birthday attack, and if the encryption algorithm is DES and only a 64 bit hash code is produced, then the system vulnerable. 
We assume that the opponent intercepts a message with a signature in the form of an encrypted hash code and that the unencrypted hash code is m bit long. 
1. Use the algorithm defined at the beginning of this subsection to calculate the unencrypted hash code G. 
2. Construct any desired message in the form Q1, Q2, ---, Qn-2.
3. Compute Hi = E(Qi, Hi-1) for 1<=i<=(n-2).
4. Generate 2^(m/2) random blocks for each block X, compute E(X,Hn-2). 

Generate an additional 2^(m/2) random blocks, for each block Y. compute D(Y,G) where D is the decrypted function corresponding to E.

5. Based on the birthday paradox, with high probability there will be an X and Y such that E(X,Hn-2) = D(Y,G).
6. From the Message Q1, Q2,----Qn-2, X,Y. This message has the hash code G and therefore can be used with the intercepted encrypted signature. 

Above attack is known as a meet in the middle attack. A number of researchers have proposed refinements intended to strengthen the basic block chaining approach. 

    Hi = E(Mi, Hi-1) xor Hi-1
OR
    Hi = E(Hi-1, Mi) xor Mi

----------------------------------------------------------Thank-You-------------------------------------------------------

Comments

Post a Comment

Popular posts from this blog

Elliptic Curve Cryptography (ECC) and ECDSA

Image
Elliptic Curve Cryptography (ECC) Elliptic curve (EC) was first introduced by Neal Kobiltz and Victor Miller in 1985. Elliptic curve is a non-singular curve that is operated on a finite field Zq (where q is the order of elliptic curve). EC consists of set of points that satisfies the following equation as follows.                                                                   Y 2 = X 3 + aX + b Where {X,Y,a,b} ∈ Zq, and 4a 3 + 27b 2 ≠ 0. Next, we discuss the encryption and decryption mechanism between two parties (Say α and γ ). Remark 1: Elements selected from party α is represented by capital letters whereas elements selected from party γ is represented by small letters. i) Key Generation: 1. Secret key: Each party α and γ selects secret keys S ∈ Zq and s ∈ Zq. 2. Public key: P ...
Read more

Fast Base Conversion and Its Application

Image
Fast Base Conversion (FBC) is a technique used to convert a number from one modulus space to another. For example, if we have 14 m o d     77 14 \mod 77  and want to convert it to x m o d     390 x \mod 390 , FBC is widely used. Mathematically, it can be represented as follows: Here, the above equation represents an integer x x  in modulus q q , and FBC converts this integer into the modulus space t t . The modulus q q  is the product of small coprime moduli (i.e., q = q 1 q 2 … q k q = q_1 q_2 \dots q_k ​ ), and x x  is an integer such that x ∈ [ 0 , q ) x \in [0, q) . We also note that q q  and t t  are coprime numbers. Here, we remark that it is not necessary for the above equation to produce the exact result for x x . Instead of x m o d     t x \mod t , it will provide x ′ m o d     t x' \mod t . Thus, the output of the above equation is as follows: FBC ( x , q , t )  =  x  +  A q  mod  t , where A ∈ [ 0 , k − 1 ] A \in [0,...
Read more

NP-Hardness vs Cryptographic Hardness

To understand the gap between these two terms, we divide this blog into two parts. In first part, we discuss complexity theory, and in second part, we explore cryptographical perspective.  Complexity Theory:  For a better understanding of complexity theory, we refer readers to [1] Language L : A language L is a set of strings defined over an alphabet set Σ. Class P  (polynomial time) : A language L is in P if L is decidable in polynomial time by a deterministic Turing machine. Example: Language = Reachability. Input: Graph G(V,E), and s,t ∊ V(G). Question: Does their exist a path from s to t ?  The above Language is an example of Class P  (hint: can be easily solved by BFS/DFS algorithm).  Class NP (non deterministic polynomial time) : A language L  ∊  NP  if the certificate for L can be verified by a non-deterministic Turing machine in polynomial time.   A certificate for a language L is an instance of the solution ...
Read more