# HomeWork 5

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

1. 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.

2. Consider a signature scheme which uses Merkle tree on n blocks (you can assume that n=2k) and issues a single PK signature on the root value.
1. Give a pseudo-code algorithms to
1.  sign all n blocks (assume you are given a PKsignSK(m) routine and the secret key SK)
2. 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).
3. verify the above signature of the block number i (assume you are given a PKverifyPK(m, sig) routine and the public key PK)
4. modify block number i and re-sign the whole database (i.e. all n blocks)

2. 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=3k)

3. Extra credit: Assume your memory is limited by O(lg n) 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 all your algorithms; assume that n 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.

3. 7.3b
4. 7.4
5. 7.12