Chapter 5  Hash funtions and other topics  Link to a network and security course I did in 2004

What is a Hash functionInput x, Output h(x)  Hash functions can be used just as symmetric key can be used.

Must provide the flollowing:

bulletCompression:  Fixed size output, regardsless of input.
bulletEfficiency:  Easy to compute h(x) for any input of x
bulletOne-way:  It should be difficult to invert the hash
bulletWeak collision resistance:  Impossible to find y (y not equal to x) so that you can find h(y)= y = h(x)
bulletStrong collision resistance:  Impossible find y or x (y not equal to x) so that you can find h(x)=h(y)

Can be used because:

bullet

Used in digital signature

bullet

Saving bandwidth because of saving space

bullet

Collisons must exist since the input space is much larger than the output space (only MD5 128 bits).

bullet

Avalanche effect.  Small change in input, gives large change in output.

 

 

Question:  We must have collision resistance, both weak and strong.  Then it says over that " collisions must exist"...

Collision:  Two distinct inputs creates the same output.  Here the birthday problem comes in.  Is the Hash secure?

Secure hash: 2N/2 to break

Secure symmetric key: 2N-1 to break

bullet

Minimalizing data tranfer by using hashing: rsync

bullet

Non-cryptographic hash: CRC with  XOR  CRC is used in WEP.  CRC is only designed to detect transmission errors, not tampering with data.

bullet

Cryptographic hashes: Tiger hash 192 bits (3*64 bit words), HMAC (message authentication code)

 

Tiger:  Optimal performance on 64-bit processors.  Input is divided into 512 bit blocks (8 x 64).  4 S boxes is used.  Uses the same message stuffing as MD5 and SHA.  Output of Tiger is 192 bits (3x 64 bit words).

bullet

MD5 (message digest) and SHA (secure hash algorithm).  These two consist of a number of rounds just as block ciphers.

 

HMAC:  As any MAC (message authentication code), it can be used for data integrity and the authenticity of a message.  Using a cryptographic hash function together with a key.  Uses hash such as MD5 (128 bits) and SHA-1 (180) bits.  The bit size of the hash function is the same as for the undelying functions used.

K-way collision: page 9

Question:  Input is divided into 512 bit blocks, MD5 and Sha use 128 and 180 bits.  What is the connection?

THE CONNECTION IS THAT 512 IS INPUT AND 128, 180 AND 3X 64 IS OUTPUT.

 

Uses for HMAC:

bullet

online bids

bullet

Spam reduction  work for the sender, but none for the receiver

bullet

Digital signature efficiency, data corruption detection

 

   Applications using HMAC functions:
bulletauthentication
bulletmessage integrity
bulletmessage fingerprinting
bulletdata corruption detection
bulletdigital signature efficiency

  A hash function can be used to do anything that can be done with symmetric key cipher and vice versa.

bulletOnline bids are hashed
bullet

Spam reduction by having the sender doing 2N hashes and the receiver none (with zeros in the first N bits).

 

Random numbers:
bulletRequired to generate symmetric keys
bulletRSA key pairs
bulletDiffie-Hellman exponents
bulletSecurity protocols
bulletSimulations and statistics
bulletCryptographic random (unpredictable) and statistically random
bullet