$(8$ points$)$

Hashes and MACs

A Message Authentication Code $($MAC$)$ consists of two algorithms $(S,V).$ Algorithm

$S(k,m)$ uses a secret key $k$ to generate an integrity tag for a message $m.$ Algorithm

$V(k,m,t)$ uses a secret key $k$ to validate a given integrity tag $t$ for $m.$

Recall that a cryptographic hash function $h$ is a non$-$keyed function that outputs a short

hash $h(m)$ for an input message $m.$ The function is said to be collision resistant if it is

difficult to find a collision: two distinct messages $m_0,m_1$ such that $h(m_0)=h(m_1).$

Let us consider four mechanisms for providing file integrity for a single file $F$ on disk.

The file system must be able to detect any unauthorized modification to this file. We say

that the system is secure if an attacker cannot modify $F$ without being detected. You

may assume that the owner of file $F$ has a password known to the system, but not to the

attacker.

Method $1$: Compute an integrity tag for file $F$ and store the integrity tag in the

header of $F.$ Upon file open the file system checks that the integrity tag is valid.

$($a$)(2$ points$)$ Suppose the integrity tag is computed using a collision resistant

hash function applied to $F.$ Validating the integrity tag upon file open is done

by rehashing the file and comparing the result to the value in the file header.

Is the resulting system secure$?$

$($b$)(2$ points$)$ Suppose the integrity tag is computed as the MAC of $F$ using the

user's password as the MAC secret key. Is the resulting system secure$?$Method $2$: Compute an integrity tag for file $F$ and store the integrity tag in read

only memory $($say$,$ a disk partition that the attacker can read but not modify$).$

$($a$)(2$ points$)$ Suppose the integrity tag is computed using a collision resistant

hash function. Is the resulting system secure$?$

$($b$)(2$ points$)$ Suppose the integrity tag is computed using a MAC with the user's

password as the secret key. Is the resulting system secure$?$

In all sections, please justify your answer.