CSE 484 / CSE M 584: Homework 2

Homework 2

This homework is focused on cryptography.

Overview

Due Date: Friday, May 8, 5pm
Group or Individual: Do this assignment as an individual. You may talk with others in advance of actually doing the assignment subject to the guidelines in the syllabus.
How to Submit: Submit a PDF to the Catalyst dropbox: https://catalyst.uw.edu/collectit/dropbox/franzi/35015. Your assignment does not need to be entirely typed / developed with computer software. You could hand-write your assignment, and hand-draw some diagrams, and then submit a PDF scan of your hand-written assignment. Please make sure that any handwritten responses are legible.
Total Points: 35

Questions

Q1 (3 points)
Compare and contrast symmetric encryption schemes (in general) with asymmetric encryption schemes (in general). How are they similar? How are they different? Please give at least 3 total differences and/or similarities.

Q2 (3 points)
What is the main concern cryptographers have with the Encrypt-and-MAC method for combining a symmetric encryption scheme with a symmetric MAC to create a symmetric authenticated encryption scheme?

Q3 (3 points)
You just joined a new company and learned that the company is building a new, custom block cipher for their encryption needs. They are designing the block cipher themselves, and want to make it ultra-secure, with 512-bit keys and 256-bit blocks. Based on the discussions in lecture, would you recommend that the company proceed with the design and use of this block cipher? Justify your answer.

Q4 (5 points)
This message was encrypted with the RSA primitive, where N=33 and e=3. Decrypt it and find the corresponding plaintext. Please show your work.

Tips: You are welcome to write a program to aid in the decryption, and you might want to compute the private decryption exponent d.

For this cryptogram 'A' is encoded as a 1 before encryption, 'B' as a 2, and so on.

Here is the cryptogram: 14 17 3 28 27 24 16 4 14 9 13 24 1 19 23 1 28 26 5 27 24 16 4 14 26 31 23 3 14 17 14 17 26 24 28 1 4 24 3 19 3 14 3 22 26

Q5 (8 points)
The following question has you use RSA, but with larger values (but still not anywhere close to the size of the numbers one would use in a secure cryptographic protocol like TLS/SSL).

You may use a program that you write, Wolfram Alpha, or any other computer program to help you solve this problem.

For all of these, it is sufficient to just include your number in the answer, unless the question explicitly asks for additional detail.

Let p = 9497 and q = 7187 and e = 3.

Compute N = p * q. What is N?
Compute Phi(N) = (p-1)(q-1). What is Phi(N)?
Verify that e is relatively prime to Phi(N). What method did you use to verify this?
Compute d as the inverse of e modulo Phi(N). What is d?
Encrypt the value P = 12345678 with the RSA primitive and the values for N and e above. Let C be the resulting ciphertext. What is C?
Verify that you can decrypt C using d as the private exponent to get back P. What method did you use to verify this?
Decrypt the value C' = 12345679 using the RSA primitive and your values for N and d above. Let P' be the resulting plaintext. What is P'?
Verify that you can encrypt P' using e as the public exponent to get back C'. What method did you use to verify this?

Q6 (5 points)
Suppose you, as an attacker, observe the following 32-byte (3-block) ciphertext C1 (in hex)

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 46 64 DC 06 97 BB FE 69 33 07 15 07 9B A6 C2 3D 2B 84 DE 4F 90 8D 7D 34 AA CE 96 8B 64 F3 DF 75

and the following 32-byte (3-block) ciphertext C2 (also in hex)

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03 51 7E CC 05 C3 BD EA 3B 33 57 0E 1B D8 97 D5 30 7B D0 91 6B 8D 82 6B 35 B7 8B BB 8D 74 E2 C7 3B

Suppose you know these ciphertexts were generated using CTR mode, where the first block of the ciphertext is the initial counter value for the encryption. You also know that the plaintext P1 corresponding to C1 is

43 72 79 70 74 6F 67 72 61 70 68 79 20 43 72 79 70 74 6F 67 72 61 70 68 79 20 43 72 79 70 74 6F

Compute the plaintext P2 corresponding to the ciphertext C2. Submit P2 as your response, using the same formatting as above (in hex, with a space between each byte). Please show your work or provide a brief explanation of your process for finding P2.

Q7 (5 points)
Consider an insecure version of SSH that uses ECB mode for encryption. Whenever a user types a key into the ssh client, that key is immediately encrypted and sent over the wire to the server. This immediate encrypt-after-key-press procedure is what enables the interactivity of a remote shell. Now consider the following sequence of plaintext packets (written in hex):

P1 = 6C 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII l P2 = 73 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII s P3 = 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII space P4 = 2A 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII * P5 = 2D 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII - P6 = 66 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII f P7 = 72 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII r P8 = 6F 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII o P9 = 6D 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII m P10 = 0D 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 // ASCII <enter>

This corresponds to a user typing "ls *-from<enter>" into their ssh client.

Suppose an attacker knows what the user is typing via some out-of-band channel (e.g., shoulder surfing) and also eavesdrops on this communications and intercepts the corresponding ciphertexts:

C1 = 4E B6 48 B2 E0 BE A5 B1 21 2F 07 54 DF CF A4 39 C2 = 11 70 78 65 88 89 06 62 82 0C 0A 6A 55 6F 87 46 C3 = EF 7F 1F 25 3E 99 98 8D 1A FC BE 7A D9 D6 ED 7E C4 = 5B 40 2B 18 0B 94 E8 13 DA F3 DE 21 A0 27 2E C4 C5 = 93 80 19 1F 06 B4 4B 19 9D 70 86 28 34 12 26 DC C6 = 68 74 EB 1B 16 5F 70 45 05 29 B9 66 0A CC D3 6C C7 = 56 E8 77 E1 7E BF 01 19 27 87 03 FE E1 1D 65 A8 C8 = 9D 37 51 F0 68 C8 F7 BA 44 B2 E9 5C 09 94 1D 5A C9 = 62 30 38 8F A4 D7 C1 68 56 88 CE 2C 29 2D F5 23 C10 = D5 89 74 7E 45 89 08 FA 5B 63 98 42 E6 B2 31 85

The attacker can now inject messages into the communications channel from the client to the server. One thing an attacker might try to do: generate a sequence of ciphertext packets that, when decrypted, are interpreted as "rm -rf *<enter>" on the server. Give such a sequence of ciphertext packets in your answer.

Q8 (3 points)
The following questions are all related to browser certificates:

Count the number of root certificates in your browser. How many do you see?
Explain the process you used to count the number of root certificates that your browser uses. In your answer, also describe your operation system and browser, including browser version number.
Did you find anything surprising when you looked at your browser root certificates? Explain your answer.