Problem Set 3

Out: 17 February 2005 Due: 24 February 2005 (beginning of class)

Collaboration Policy

Same as PS2, except for this assignment you may not work with the same person with whom you worked on PS2.

Permutation Cipher Redux

Since no one answered Question 4b from Problem Set 1 close to correctly, it seems appropriate to have another question on the permutation cipher. (See Lecture 6 for a discussion on that question.)

1. (20) How large is the set of messages that can be transmitted with perfect secrecy using the 8-bit transposition cipher (as in PS1, Question 4b) with an alphabet containing only 2 symbols? That is, strings in {0, 1}^*. Justify your answer by describing the elements of your message set, and why it is not possible to transmit any larger set of possible message without revealing some potentially useful information to a passive attacker. (Note: you may transmit as many blocks as you want, but they must all be encrypted using the same transposition key.)

Smashing Hashes

The attached paper — Adrian Perrig, Robert Szewczyk, J. D. Tygar, Victor Wen and David Culler, SPINS: Security Protocols for Sensor Networks. Wireless Networks, 2002 (originally in MobiCom 2001) — describes several protocols for securing sensor networks. These questions concern only µTESLA, a protocol that provides authenticated streaming broadcast without needing public-key encryption. (You are encouraged to read the whole paper, though, since it touches on many things we have seen in this class.)

2. (20) Since wireless communication in sensor networks is unreliable, it is possible that a node misses one of the released keys. How serious of a problem is it if a node misses a key release message? (Your answer should explain how the node can validate the next received key, and whether or not messages transmitted using the missed key can eventually be authenticated.)

3. (30) If µTESLA is used on a long-lived sensor network application, eventually the end of the hash chain will be reached (the sender would need to use K_n and have no more keys left). Suggest a modification to the µTESLA protocol that can be used to extend its lifetime indefinitely. Explain the security risks of using your modified protocol.

The paper (which was published in 2001, before the weaknesses in cryptographic hashing algorithms were known) suggests using MD5 as the cryptographic hash algorithm to generate the µTESLA hash chain. In Lecture 8 we saw a Perl program that demonstrates MD5 does not provide strong collision resistance, as is expected in a cryptographic hash algorithm. Make sure you understand the difference between weak and strong collision resistance (defined in Lecture 8) when you answer questions 4 and 5.

4. (20) How secure is the authentication provided by µTESLA if a hash algorithm that does not provide strong collision resistance is used?

5. (10) How secure is the authentication provided by µTESLA if a hash algorithm that does not provide weak collision resistance is used?

Censorship-Resistant Publishing

Note: this question was added on Friday, 18 February after Chenxi Wang's guest lecture.

6. (20) Censorship-resistant publishing schemes rely on secret sharing where some k out of n pieces of information are needed to construct a document, but fewer than k pieces provide no useful information. We can describe secret sharing schemes according to the value of n and k where n is the number of shares distributed, and k is the number of shares needed to recover the secret. For example, the last question on Problem Set 1 considered a (3, 3) secret-sharing scheme. For censorship-resistant publishing, we need a scheme where k < n, so if one of the participants refuses to provide her share, the others can still recover the document.

Invent a (2, 3) secret-sharing scheme using XOR as the only operation. Your answer should explain how a secret is divided into 3 shares, how any 2 of those shares can be combined to recoved the secret, and include a convincing information theoretical argument why any single share provides no information.

University of Virginia Department of Computer Science CS 588: Cryptology - Principles and Applications

cs588–staff@cs.virginia.edu