## (solution) COSC235 - Homework 1, part 2 Assigned September 4th, 2014; Due

I need help on this assignment. I would like an in-depth solution to each problem if applicable.

COSC235 - Homework 1, part 2?

Assigned September 4th, 2014; Due 11:59pm on September 18th, 2014

Prof. Micah Sherr Written questions {40 points} 1 (a) {10 points} A cryptosystem that offers perfect secrecy prevents an eavesdropper who observes

an encrypted transmission from learning anything about the plaintext, other than its size.

Show with a counterexample that the Substitution Cipher doesn?t provide perfect secrecy.

(b) {10 points} Consider the following modification to one-time pad (OTP) encryption. Rather

than share a single one-time pad, Alice and Bob have shared knowledge of two pads, P1 and

P2 .

Given a plaintext M , Alice creates the ciphertext C = M ? P1 ? P2 , where ? denotes xor and

|M | = |P1 | = |P2 | (i.e., the size of the message and the two pads are all equal). To decrypt, Bob

takes the ciphertext and xors it with P1 and P2 ; i.e., D(C) = C ? P1 ? P2 .

Argue that if a one-time pad offers perfect secrecy, then the above scheme must also be perfectly secure.

(c) {5 points} Prof. Pedantic, the esteemed Ineptitude Professor of Computer Science and Quackery at Wikipedia University, is developing a new terminal program (and associated service)

to log into the servers in his lab. Although he is aware of ssh, he refuses to use it because

he doesn?t like being hushed.1 Instead, he decides to construct his own novel protocol. Like

telnet and ssh, his remote console/terminal program should allow a remote user to type

commands and execute them on a remote machine. Since Prof. Pedantic doesn?t trust anyone

? particularly the students in his introduction to network security class ? he decides that all

communication should be encrypted.

Prof. Pedantic decides to use the AES encryption algorithm in ECB mode. Is this a good

choice? Give two reasons why or why not.

(d) {15 points} Prof. Pedantic designed a ?secure? communication protocol for two parties (Alice

and Bob) that have preshared secrets k1 (the confidentiality key) and k2 (the authenticity key).

?

1 Last revised on September 9, 2014.

Extra credit {0.0000001 points}: Explain that joke. 1 Prof. Pedantic doesn?t believe in traditional MACs, so he constructs his protocol as follows: to

send a message m, Alice (A) sends to Bob (B) the following:

A ? B : h r,

iv1 ,

iv2 ,

RC4H(iv1 |k1 ) (r, m),

RC4H(iv2 |k2 ) (r, m) i

where r is a nonce (to prevent replay attacks), iv1 and iv2 are fresh initialization vectors (IVs),

RC4k (r, m) denotes the encryption of message m using RC4 (a stream cipher) with key k and

nonce r, and H(x|y) is the SHA-256 hash of x concatenated with y. (Note that RC4 does not

natively accept an IV; hence, Prof. Pedantic embeds the IV into the effective encryption/decryption key using the hash function.)

The professor claims that the protocol achieves confidentiality and authenticity, as defined as

follows:

? confidentiality: an eavesdropper that observes a run of the protocol cannot learn the message m unless it knows the confidentiality key k1 ; and

? authenticity: if Bob receives hr, iv1 , iv2 , RC4H(iv1 |k1 ) (r, m), RC4H(iv2 |k2 ) (r, m)i and r is a

fresh nonce and the decryption of RC4H(iv1 |k1 ) (r, m) equals the decryption of RC4H(iv2 |k2 ) (r, m)

(using the corresponding IVs and keys), then message m must have been transmitted by

a party that knows both the confidentiality and authenticity keys (i.e., k1 and k2 ).

The professor?s intention is that Bob obtains m by decrypting RC4H(iv1 |k1 ) (r, m) using key k1

and iv1 . Further, Bob performs an authenticity check by ensuring that the decrypted message

matches the decryption of RC4H(iv2 |k2 ) (r, m) (via key k2 and IV iv2 ). He reasons that only a

sender that knows both k1 and k2 can cause the decryptions to match.

Does Prof. Pedantic?s scheme achieve confidentiality and/or authenticity, as defined above?

Briefly argue why or why not, for both confidentiality and authenticity. Assume that k1 and

k2 are random 128-bit keys that have been securely shared apriori between Alice and Bob, that

k1 6= k2 , and that the two IVs are also fresh. 2 Eavesdropping on Yourself {15 points} 2 Show that the UnencryptedIM program you wrote2 for Part I of Homework 1 is susceptible to

eavesdropping.

Do this by using tcpdump to conduct a packet capture on netid-alice-HW1. You?ll need to use root

(admin) privileges to perform a packet capture, so you?ll want to preface the command with sudo

to run as root. You should also set the ?snaplength? to 0 to capture packets in their entirety, and

you?ll want to save the capture to a file (see tcpdump?s -w option).

Hint: The manual page for tcpdump is your friend. You can access it by typing man tcpdump on

the Linux shell.

Then, on your own machine, open the captured pcap file with Wireshark, and take a screenshot

that shows that an adversary can clearly see the plaintext messages as they traverse the network.

have it, you will need to install it. Submit your screenshot with this homework as evidence that

an adversary can discern the plaintext IM messages.

(You do not need to write up anything for this question; just submit the screenshot.) A Simple, Encrypted P2P Instant Messenger {35 points} 3 As promised, you will be extending your earlier unencrypted messaging application (or the one

provided by the teaching staff) with encryption! We?ll call this new program EncryptedIM.

Your program should encrypt messages using AES-128 in CBC mode, and use HMAC with SHA-1

for message authentication. IVs should be generated randomly.

Your program should have the following command-line options:

EncryptedIM [-s|-c hostname] [-confkey K1] [-authkey K2]

where the -s argument indicates that the program should wait for an incoming TCP/IP connection on port 9999; the -c argument (with its required hostname parameter) indicates that the

program should connect to the machine hostname (over TCP/IP on port 9999). -confkey specifies the confidentiality key (K1) used for encryption, and -authkey specifies the authenticity key

(K2) used to compute the HMAC.

You should use SHA1 to hash keys K1 and K2 to ensure that they are of a constant size. You should

take the first 128 bits of the two 160-bit hashes as your respective keys.

2 Important note: For the entirety of this homework, you may use the TAs?/instructor?s solution to homework 1,

part 1 rather than your own, if you prefer. 3 For example, you may run ?EncryptedIM -s -confkey FOOBAR -authkey COSC235ISAWESOME?

on netid-alice-HW1, and then start ?EncryptedIM -c netid-alice-HW1 -confkey FOOBAR

-authkey COSC235ISAWESOME? on netid-bob-HW1. Note that the instance with the -s option

must be started before the other instance.

Along with your code, you must submit a brief protocol document in plain ASCII (no MS Word

please!) that describes the format of your messages. In particular, the document should describe

how/where the IV is transmitted, and the locations of the ciphertext and HMAC in the messages. Additional requirements and hints.

lowing: Please make sure that your program conforms to the fol- ? You may write your program in C, C++, Python, Ruby, Java, or Perl. Please see the teaching

staff if you would like to use another programming language. For submissions done in

C/C++/Java, we will ignore all submitted executables (or byte code) and will compile your

code from the submitted source files.

? Your program should verify that the HMAC is correct. If it is not, it should exit with an error

message. You should test that authentication is working properly by specifying different

authentication keys on netid-alice-HW1 and netid-bob-HW1: this should produce your error

message and cause the program to exit!

? You may only use libraries already installed on netid-alice-HW1 and netid-bob-HW1. Please

post requests for additional crypto libraries to Piazza.

? You may not collaborate on this homework. This project should be done individually. You

may search the Internet for help, but you may not copy (either via copy-and-paste or manual typing) code from another source. You may use code from the textbook, or from the

instructor or TAs.

? As with the first assignment, to aid in automated testing/grading, do not provide a prompt

to the user, and only write received messages to standard out. We will be using automated testing tools to evaluate your solutions, and printing additional messages or characters makes such automation far more difficult.

? Your program should not take in any additional command-line options other those described above. The -confkey and -authkey arguments are mandatory; they are not optional.

? Your program can terminate either when the user presses CTRL-C, or when end-of-file (EOF)

This portion of HW1 is worth 90 points (40 points for question 1; 15 points for question 2; and

35 points for the programming assignment). A non-comprehensive list of deductions for the pro4 gramming portion of this assignment is provided in Table 1.

We will award partial credit when possible and appropriate. To maximize opportunities for partial

credit, please rigorously comment your code. If we cannot understand what you intended, we

cannot award partial credit.

Description

Only included executables (no source code; applies to C/C++ and Java)

Compilation / interpreter errors

Compiles, but IMs are neither successfully transmitted nor received

Communication only works in one direction

IMs are not encrypted

IMs are encrypted, but not successfully decrypted

Lack of HMACs

Lack of HMAC verification

Incorrect HMAC verification

Received messages only appear after user presses [ENTER] (indicates that

select is used improperly)

General instability (e.g., occasional segfaults)

Run-time error (e.g., crash) on large input

Non-conformant command-line options (hinders automated testing)

No compilation instructions provided (applies to C/C++/Java)

Includes unnecessary prompts (hinders automated testing) Deduction

35

20

17

13

25

12

15

10

7

10

6

5

5

5

3 Table 1: Grading rubric. Note that this grading rubric is not intended to be comprehensive. Submission Instructions

Submit your solution as a single tarball (tar.gz archive) using Blackboard. To upload your assignment, navigate to the COSC235 course, click the ?Assignments? link on the left hand side, and

select ?hw1-part2?. Look for the ?Attach File? section and upload your submission. Be sure to hit

the ?Submit? button when done. Upload your assignment before 11:59pm on September 18th.

In the archive, include a single PDF or ASCII text document with your written answers to Question 1. Writeups submitted in Word, PowerPoint, Corel, RTF, Pages, and other non-PDF or

ASCII formats will not be accepted. Consider using LATEX to format your homework solutions.

(For a good primer on LATEX, see the Not So Short Introduction to LATEX.)

Include in the archive the written responses, all source code, and the protocol description. If your

program is written in a C/C++ or Java, please also provide compilation instructions.

Solution details:

STATUS

QUALITY

Approved

Sep 13, 2020

EXPERT

Tutor