read chapters 7 and 14 (at least the relevant parts on KDC and Kerberos).

- OFB mode is maleable: flipping 1 bit of ciphertext flips the
corresponding bit of the plaintext. How hard is it for an Attacker to change
this bit of plaintext (without being noticed) if redundancy is added to the
plaintext message by appending:
- a block of
*k*0s - a checksum of all the
*k*-bit blocks of the plaintext - a
*k*-bit hash of the message - a
*k*-bit MAC of the message

(be very precise in your answers, in particular comparing precisely all the above costs to the Attacker)

- Summarize the relevance of the above problem to the other modes of
operation: ECB, CBC, OFB, and COUNTER.

- a block of
*Consider a signature scheme which uses Merkle tree on*n*blocks (you can assume that*n*=2*^{k}) and issues a single PK signature on the root value.*Give a pseudo-code algorithms to**sign all*n*blocks (assume you are given a*PKsign_{SK}(m)*routine and the secret key*SK*)**select the signature just for the block number*i*(assume numbering from 0 to n-1), given as input*

(revisit the item above to adjust your data structures so that this signature is computed efficiently (store the data needed to compute such signatures efficiently).*verify the above signature of the block number*i*(assume you are given a*PKverify_{PK}(m, sig)*routine and the public key*PK*)**modify block number*i*and re-sign the whole database (i.e. all*n*blocks)*

*Modify your algorithms above to use a ternary version of the Merkle tree (each node has three children; if you wish, you can now assume that*n*=3*^{k})

n__Extra credit__: Assume your memory is limited by O(lg*) in addition to the read-only*n*blocks, so you cannot store the tree as in (a,b) above. Give an efficient algorithm to evaluate the Merkle Tree Hash (i.e. to compute the root value). Try to compute and optimize the constants in the O().*

*Give the efficiency (time and space requirements) for*n__all__your algorithms; assume that*is fairly large (so you want to avoid costs of*n*or above as much as possible)**and make sure that your algorithms are as efficient as possible.*

- 7.3b
- 7.4
- 7.12