University of Virginia, Department of Computer Science
CS588: Cryptography, Spring 2005


Do not open the exam until told to do so.

ProblemScoreGood Answer
1 10
2 20
3 20
4 20
5 10
6 20
7 ??
Total 100

This exam may be ridiculously long and difficult. Don't get stressed out if you can't answer every question. It is not necessary to answer every question correctly to get a satisfactory grade on the exam.

Please mark your final answers clearly (e.g., draw a box around them). If you need more space than is provided, you may use the backs of pages or the blank page attached to the exam. Be sure to indicate clearly where your answer is.


1. (10) There are 9 possible x86 opcodes that behave indistinguishably from the unconditional jump: JMP and 8 of the conditional jump instructions. Given that an opcode exhibiting the jump behavior is guessed, what is the conditional probability that the guessed opcode is JMP?

2. (20) The MicroVM described in the FEEB paper is injected on the stack using an attack technique that is not capable of pushing a NULL byte on the stack. This would be necessary if the intended byte at a given location matches the mask byte at that location. The paper claims,

As long as the masks are randomly distributed, two or fewer will be sufficient over 99.8% of the time, so we can nearly always inject the worm once 128 key bytes have been acquired.
Explain how you would estimate the probability that the 125-byte MicroVM can fit into 128 bytes of known key space. A clear explanation would include equations you could use to produce the probability estimate. You can assume all instructions are 1-byte long (not true for x86 code).

Client Authentication

3. (20) The Fu et. al paper suggests authenticating web clients using a cookie containing:
digest=MACk (exp=t&data=s)
Suppose the MACk(m) function used is:
Sign (k, SHA1 (m))
where Sign is a secure cryptographic signature using key k. Is the protocol vulnerable to an attacker who does not know the server key k but is able to compromise the weak collision resistance property SHA1 should have? If so, explain how such an attacker would be able to create a bogus cookie. Otherwise, explain why the protocol is still secure even when the attacker can find hash collisions.

4. (20) When you registered for the CS588 forum, the phpBB application sent you an email like this:

Welcome to UVa Computer Science Forums Forums


Your account is currently inactive. You cannot use it until you visit
the following link:

The value 0f027e468 is an "activation key" that is used to activate your account. This way, phpBB obtains evidence that the email address is valid before activating your account. It should be difficult for someone to guess the activation key associated with a particular email address, even if they know the activation key associated with other addresses. Make a reasonable guess how the activation key is calculated and checked.

Perfect Cipher

Section 2.1 of the FEEB paper mentions that the ISR implementation proposed by Kc et. al described two possible encryption routines. One is the XOR-pad that the paper focuses on; the other is a 32-bit transposition cipher. This is identical to the 8-bit transposition cipher you have seen in PS1 and PS3, except it operats on 32-bit blocks instead.

5. (10) Dana E. Quarles claims that the 32-bit transposition cipher is perfect, so there is no way to break this version of ISR. Her proof argument is:

Explain what is wrong with DEQ's argument.

6. (20) Suppose an attacker intercepts the following two blocks encrypted with the 32-bit transposition cipher:

     0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
     0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 

Pos: 1   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31
       2   4   6   8  10  12  14  16  18  20  22  24  26  28  30  32
Explain everything the attacker can learn about the corresponding two plaintext blocks.

7. (Bonus Challenge: don't spend time on this until you have answered the other questions) Suggest a strategy for attacking an ISR-protected server where the 32-bit transposition encryption technique is used instead of XOR masking.

8. (Optional, No credit) Is there any reason why your performance on this exam will not fairly reflect what you have learned in the course so far?

End of Exam

This page intentionally left almost blank.
You may remove this page and use it for scratch work or to draw pictures if you are waiting for inspiration on question 7.

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