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

(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.
Note that Wireshark is available (for free!) on Linux, Mac OSX, and Windows. Unless you already
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)
is received. To generate EOF from the terminal, press CTRL-D. Grading
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.
Please post questions (especially requests for clarification) about this homework to Piazza. 5