CS5430 System Security

CS5430 Homework 3: Nonces, Hashes, and Secret Sharing

General Instructions. You are expected to work alone on this assignment.

Due March 15, 2010, 9am. Submit your solution using CMS. No late assignments will be accepted.

To facilitate grading, format your solutions as follows.

Put your name and net id on each page of your solution.
Typeset your solution, using 10 point or larger font and use 8.5 x 11 inch paper.
Use at most one page (both sides, if necessary) for each problem (so what you submit comprises 6 sheets of paper).
Start each problem's solution on a separate side.

Solutions that do not satisfy the formatting guidelines will be returned, ungraded.

Problem 1:

The short protocol below is intended to convince B that it is communicating with A. Assume that these principals share a key K_AB and that r is an integer counter that B saves between executions of the protocol.

1.  A --> B: "A"
2.        B:  r := r + 1      //generate new nonce for challenge
3.  B --> A:  r
4.  A --> B:  Encrypt(K_AB , r )
5.        B:  Let m be the message just received.
6.            If Decrypt(K_AB, m) = r then SUCCESS
                                      else FAILURE

Justify the following claim about a possible protocol modification by exhibiting an attack that works against the original protocol but not against the modified protocol.

: A stronger protocol results if B chooses a random value for nonce r in step 2 instead of computing and using successive values for nonce r .

Problem 2:

In lecture, we discussed the following scheme for using a hash function H and a shared key K_AB in order to construct a one-time pad, which is then used to encrypt a message m. Note, juxtaposition of variables in the following is used to denote string concatenation. Thus H(x y z) would specify invocation of hash function H on the bit string that results from concatenating x, y and then z.

Protocol to encrypt message m with key K_AB and store the result in "ciphertext":
  b1 := H( K_AB )
  b2 := H( K_AB b1 )
  b3 := H( K_AB b2 )
   ...
  bn := H( K_AB bn-1 )
  ciphertext := m XOR b1 b2 b3 ... bn

In lecture, we assumed that:

Bit string b1 b2 b3 ... bn is at least as long as m.
Each "block" bi is significantly longer than 1 bit long.

Suppose this second assumption is relaxed and that each "block" bi is only 1 bit long. Execution of "b3 := H( K_AB b2 )" might, for example, assign to b3 the most significant bit in the output of H( K_AB b2 ).

One obvious effect of this changed assumption concerns cost---the code segment above would require many more invocations of the hash function and many more variables bi. But are there any consequences regarding the security of the scheme? Give a detailed justification (or specific attacks) to justify your contention.

Problem 3:

A Merkle Hash tree allows the hash of a long input to be recomputed cheaply if only a small part of that input is changed. Suppose:

The cost of computing a hash H(inp) is C x Len(inp), where C is a constant and Len(inp) evaluates to the number of bits in inp.
The output of a hash H is 512 bits, no matter how long the input.
Of interest is the value of H(inp), where inp is a sequence of 4K-bit blocks inp1 inp2 ... inpN for N a power of 2.
An update to inp changes the contents of exactly one of the 4K-bit blocks inpi

Give an expression for the cost of recomputing H(inp) by streaming inp into H in the obvious way.
Give an expression for the cost of recomputing H(inp) after a single block is updated, assuming a Merkle Hash tree were being used. .
Give an expression for the cost of initially setting-up a Merkle Hash tree for computing and recomputing H(inp)

Problem 4:

Shamir's scheme for implementing an (n,t) sharing of a secret s involves a random polynomial F of degree t-1 such that

F(0)=s
Each of the n shares s is a pair ( i, F(i) ) for i between 1 and n.

Consider a setting with n principals P1, P2, ..., Pn, and 3 secrets s1, s2, and s3, such that n>t+20 holds and

each principal is given a distinct share for secret s1 based on a suitable polynomial F1 for an (n,t) sharing,
each principal is given a distinct share for secret s2 based on a suitable polynomial F2 for an (n,t) sharing, and
each principal is given a distinct share for secret s3 based on a suitable polynomial F3 for an (n,t+5) sharing.

Protocols are sought that would allow some new principal A to learn certain information about these secrets. For each of the following, either (a) give a protocol and a mathematical argument to show why the protocol delivers what is expected or (b) explain why no protocol should exist.

A learns s1+s2 without learning either s1 or s2.
A learns s1+s3 without learning either s1 or s3.