CS558: Network Security
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.
- 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.
- Give a pseudo-code algorithms to
- sign all n blocks (assume you are given a
PKsignSK(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 PKverifyPK(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=3k)
- 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.