CPSC 253 Lecture 6: Hash Functions & Message Authentication

Hash Function

• In message authentication, this takes a variable-sized input message and produces a fixed-sized output

• Output: hashcode/hash value/message digest

• Creates efficient storage structures for associative arrays in the memory of a computer

  • Associative arrays are like phone directories with <name, identifier> pairs

Hashcodes in modern processing algorithms

In the MapReduce framework used in Hadoop, this function type is applied to the “keys’ related to the Map tasks in order to determine their bucket addresses, with each bucket constituting a Reduce task.

SHA-512(Secure Hash Algorithm)

• Takes input messages of length up to 2¹²⁸ bits and produces an output of a 512-bit message digest (MD)

• A series of this algorithm type has been developed by the National Institute of Standards and Technology and published as Federal Information Processing Standards (FIPS).

Hashcode/Message digest

• Fixed-size fingerprint (unique) of a variable sized message

• Most commonly used hash functions range in length from 160(SHA-160) to 512(SHA-512) bits depending on the algorithm used to produce this.

Apache Project

• Distributed computing of large data sets across a cluster of computers

• Parallel computing

What is being depicted in this figure?

• Symmetric encryption/decryption using the same key

• Party B creates a new hash code after getting the message

• The message and hash code are put together to make a composite message

• Receiver decrypts message, seperates hashcode, and compares it to the recieved message’s hashcode

• Guarantees message authentication(hashcode) and confidentiality(encryption)

What is being depicted in this figure?

• Message Authentication Code(MAC)

• The message is left unencrypted while the hash code is encrypted

• Method to implement hashing

• Useful when confidentiality is not a concern but message authentication is needed

• Only the receiver with the key knows the real hash code, so they can verify the authenticity of the message.

  • Symmetric key

What is being depicted in this figure?

• Used in digital signatures

• Public key encryption

• Sender encrypts Hash code of the message with their private key.

• The receiver can get the hash code with the sender’s public key and authenticate that the message came from the intended sender.

• Confidentiality isn’t important in this case

• Message authentication is, though

What is being depicted in this figure

• Guarantees message authentication and confidentiality

• Symmetric-key confidentiality.

• Shared secret: extra binary bits/secret string both sender and reciever know is appended to the message

• No encryption

• Authenticated message but no confidentiality because the message is unencrypted

• For party B, the hashes must match

• Message authentication and confidentiality are real

• Symmetric key based confidentiality to the transmission between the sender and receiver.

What are the conditions for a secure hash function?

• One-way property: computationally infeasible to find a message that corresponds to the given hashcode

• Strong collision resistance: Computationally infeasible to find 2 different messages that hash to the same hashcode value. 1 to 1 mapping, otherwise you have a collision.

For a ___ there should not correspond another message with the same hashcode

given message

• Weaker ver of strong collision resistance property

Birthday Attack

Possibility that another message has the same hashcode as your original message.

Collision resistence def on slide 19 is wrong

Authentication

• Message has not been altered in anyway

• Send unencrypted plaintext messages with encrypted hashcodes

  • Eliminates computational overhead for encryption/decryption in the main message and allows for authentication

• Only works if hash function has perfect collision resistance

  • If it doesn’t an adversary could compute the hashcode of the message and replace it with a different message w/ the same hashcode value

How are messages processed when computing the hashcode?

• Messages are sequences of n-bit blocks

• Processed 1 block at a time in an iterative fashion to generate its hashcode

XOR hash algorithm

• Start with 1st n-bit block

• XOR it with the 2nd block bit by bit and use that result to do the same with the next one

• Produces a longitudinal parity check(hashcode type)

Longitudinal parity check

• Stored and fetched bits should be the same

• Should add to 0 when XOR

Slide 31

25 + 423=448+64=512

How can you spot alterations of the input message?

• Since message digests depend on every bit in the input message, any alteration during transmission would cause the new message/hash value not to match the original

• Can be used to check for forgeries, unauthorized alterations, etc.

Why are these 2 hashcodes different?

• There is an extra space in one of the messages.

• Produces a 160 bit hashcode.

• 40 hex characters

How many distinct hashcode values can you have with n bits?

• 2ⁿ

• This is prevent multiple messages having the same hashcode

• In any given context there is some sort of upper bound on different types of possible messages

XOR hash algorithm weaknesses

• Not good for message authentication

• Adversary can modify the main message and add a suitable bit block before the hashcode so that the final hashcode remains unchanged.

XOR Hash Algorithm Strengths

Hashcode made can be used for data integrity checks in the presence of completely random transmissions errors.

What is this a representation of?

A hashcode produced by the XOR algorithm

{X₁, X₂, . . . , X_m}

The bit blocks of a message in a hashcode

∆(M)

Hashcode produced by an XOR algorithm. M is the message

M = {X₁ || X₂|| . . . || X_m}

Concatenated bit blocks

How could an adversary create a forgery from {M, ∆(M)}?

Replace X₁ through X_m-1 with new bit blocks Y₁ through Y_m-1 given by the following equation

What is the hashcode for this function?

• Due to the properties of the XOR operator, it will be the same as the original ∆(M)

• So when the forged message is concatenated with ∆(M) the recipient won’t suspect any changes

What are some things that can increase the probability of collisions in the XOR algorithm?

• Character encoding is based on ASCII or a variant

  • Causes the highest bit in every byte to be 0

• As a result, some of the N bits in the hash code will be 0, reducing the number of unique hash code values

• In an N-bit hashcode you want the probability of a hashcode value to be 1/2ⁿ

What is this table displaying?

Different characters and their Binary, Oct, decimal, hexadecimal values

Rotated-XOR algorithm

• Performs a 1 bit circular shift of the partial hashcode obtained after each n-bit block is processed.

• This increases the amount of distinct hashcode values available for different messages

Issues with Rotated XOR algorithm(ROXR)

• The original message(M₁) and its hashcode(h₁) can be taken and replaced with new ones(M₂ and h₂)

• Then you can append a block of gibberish at the end of the new message to force the hashcode of the composite to be the same as the original

• Not good for authentication

How does the SHA-1 algorithm pad a message before hashing?

• Goal is to make the message a multiple of 512 bits

• With a message M with a length of L bits

• Append 1 bit to the end of the message with K(zero bits) where K is the smallest non negative solution to:

  • (L+1+K) % 512 = 448

• Then append the 64-bit block that’s a binary representation of the length integer L

For the message “abc” and length L = 24 bits what would the bit pattern look like?