• This project is due at 11:59pm on Friday, Jan 31, 2020.

Description and Deliverables

In this project, you will learn 2 different ways to generate a public and private key, how to manage keys and identities of other people, and how to use your key to sign your assignments. The first way will be to use the famous gnugp program (which is based on the original pgp program, which stands for “Pretty Good Privacy.” You will also answer some written questions that test your knowledge about the security game for encryption.

To receive full credit for this project, you will turn in the following three files:

1. A file named key.pub which includes your public key in ASCII format. Your public key must meet the following four requirements:

   • Use RSA encryption and be 4096 bits long
   • Include your name and Husky email address
   • Be signed by at least two of your classmates
   • Include your picture.

2. A file named message.txt.asc that is encrypted using the class public key and signed by your private key. The unencrypted message.txt file should be in plain ASCII format (no Word or PDF docs), and contain (1) your first and last name, (2) your gitlab user name, and (3) the string “CY2550”.

   For example, a valid message.txt might look like this:

   abhi shelat abhvious CY2550
   

3. A file named responses.txt that contains the written answer to the questions below.

and ensure that your Keybase profile has the same PGP key and follows at least 2 people in the class.

Tools

There are many tools that support the PGP standard. In the remainder of this document I will provide a brief tutorial for using GNU Privacy Guard (GnuPG, or simply GPG), which is a free, open-source, command line implementation of PGP. You are welcome to use other tools if you wish, so long as they offer the necessary features to complete all the requirements of the project.

To install GPG under a Debian-based Linux distro, simply run:

$ sudo apt install gnupg

On recent Linux distributions, such as Ubuntu 19.10, this will install GPG version 2, which is what this assignment will assume you are using. On older Linux distributions, such as Ubuntu 16.04, version 2 of GPG can be installed via the “gnupg2” package instead (note that this method also changes the command to invoke GPG from “gpg” to “gpg2”). Other installation options for Linux, Windows, and macOS are available on the GnuPG homepage

GPG Tutorial

There are a number of useful command line arguments for GPG that you will need to complete this assignment. If you ever get stuck, you can always type

$ gpg -help

to see a list of common command line arguments, or

$ man gpg

to open up the manual page for GPG. Alternatively, you can Google “man gpg” to find an online version of the manual page.

$ gpg --full-gen-key

is the command to generate a new keypair. The --full modifier lets you choose your encryption algorithm and key length; if you use the abbreviated –gen-key command you will not be given these options and the default algorithm/key length will be used. Note: you are welcome to choose an expiration date for your keypair if you want to, but make sure your keypair will not expire until the end of the semester at least!

$ gpg --edit-key <UID>

where corresponds to your user id, allows you to change aspects of the key with given UID. This commands drops you into an interactive mode with many commands, which can be listed by typing “help”. Commands that might be useful for this project include “addphoto” and “sign”. When you’re done editing a key, type “quit”. You’ll probably want to edit your key before you export it and get it signed by your classmates.

$ gpg --list-keys
$ gpg --list-sigs
$ gpg --check-sigs

all show the keys in your keyring. The first shows the keys, the second also shows their signatures (if they have any), and the last attempts to verify the signatures. Of course, you can only verify a signature from user X if you have imported a copy of X’s public key.

$ gpg --import <file>

is the command to import key material from the given file. This will be very useful, since you’ll need to import the course public key, as well as public keys from your classmates (so you can sign them).

$ gpg --armor --export <UID>

is the command to export the public key with the given UID from your keyring. You’ll need to export your public key so that you can give it to your classmates and receive their signatures. You’ll also need to export your classmates’ public keys after you sign them. Strangely, GPG prefers to output things in binary format, which is not particularly useful, so you almost always want to add the ASCII “armor” command line option.

$ gpg --armor --export-secret-keys

is the command to export all of your private keys. YOU SHOULD NEVER SHARE YOUR PRIVATE KEYS WITH ANYONE. THAT IS WHY THEY ARE CALLED PRIVATE KEYS. However, backing up your private keys is a good idea, possibly to a removable USB drive that you keep in a locked safe, or to a Yubikey.

$ gpg --armor --sign <file>

is the command to sign the given file using your private key. By default, GPG creates a new file with a “.asc” extension containing the ASCII armored, signed message.

$ gpg --armor --recipient <UID> --encrypt <file>

is the command to encrypt the given file for the given recipient. Obviously, you can’t encrypt something for someone if you don’t have their public key. Just as with signing, GPG produces a new file with a “.asc” extension containing the ASCII armored, encrypted file. Note that in this assignment you will need to sign and encrypt a file for me, which means you may need to combine command line arguments to produce the correct output.

$ gpg --decrypt <file>

is the command to decrypt the given file (and verify its signature, if one is present). Obviously, you can only decrypt a file if you hold the corresponding private key.

$ gpg --default-key <UID>

By default, GPG always uses the first private key in the keyring for signing, encryption, and decryption. If you have multiple private keys, this is the optional command line argument you need to select one other than the default when performing operations.

Backing Up Your Private Key

In the past, over 1/3 of students in the course lost access to their private key throughout the semester. This happened for a variety of reasons, including people choosing short expiration times for their keys, or because they used GPG inside a VM and the VM failed/became unbootable. You will need the keypair you generate during this project multiple times over the course of the semester. Thus, it is critical that you not lose your keys! You should make a backup of your private key, using the gpg –armor –export-secret-keys command, and store the backup in a secure, reliable location. Do not store your backup inside a VM!.

Using Keybase to manage your keys and your identities

The first part of this project introduced you to the classical way of setting up your public key using a “web of trust” to help bind your identity to your key by having your friends sign your key. Can such a scheme scale to handle 1b users on the internet?

The keybase platform is a modern take on how to establish internet-scale identity. Keybase is an application platform that augments pgp with the ability to bind your key to public identities such as (a) your twitter account, (b) your github/gitlab account, (c) a reddit account, etc. The platform makes it simple to download someone else’s key, verify that it is them by checking their twitter/github/etc account, and then send them encrypted or signed messages. Recently, it uses this infrastructure to build applications such as secure group chat, secure git hosting, and secure file sharing.

You can see my profile at keybase.io/abhi and import my pgp key using

$ curl https://keybase.io/abhi/pgp_keys.asc | gpg --import

You can also upload your newly created pgp key to Keybase for others to find. First, create a keybase account by visiting keybase.io and clicking the “Login” link, and creating a new account. Then install the keybase client on your machine. Finally, you can upload your key using the keybase tool. Read the instructions and figure out how to do that.

Next, follow at least two other people in the class on keybase and verify that their PGP keys correspond to their identity. You can, for example, follow me abhvious with PGP key 9CB4 0F15 612B 3E15.

Questions

Answer the following questions in a file named response.txt

1. What is your keybase user name?

2. In class, we have learned how Alice and Bob can send private messages using a private key encryption method, and how Alice and Bob can ensure message integrity using a Message Authentication Code (MAC). Suppose Alice and Bob want to achieve both privacy and integrity. Alice proposes the following scheme which should work using any secure private encryption scheme $(\textrm{Gen},\textrm{Enc},\textrm{Dec})$ and any secure MAC scheme $(\textrm{GenMac},\textrm{Sign},\textrm{Verify})$:

   1. First, run the Gen algorithm for the encryption scheme to produce a key $k_e$. Then run the GenMac algorithm for the MAC scheme to produce a key $k_m$. Alice and Bob are given the pair $(k_e, k_m)$.
   2. To send a message $m$, Alice first computes $c \gets \textrm{Enc}(k_e, m)$ and then computes $a \gets \textrm{Sign}(k_m, m)$ and sends $(c, a)$.
   3. Upon receiving a pair $(c, a)$, Bob first decrypts $m’ \gets \textrm{Dec}(k_e, c)$, and then verifies $\textrm{Verify}(k_m, m’, a)$. If the Verify operation succeeds, then Bob accepts the message.

   In other words, this new scheme simply runs the encryption and the message authentication code together on the same message. Does this scheme achieve both privacy and integrity as designed? If yes, explain in words why the scheme achieves both privacy and integrity. If not, describe why the system could fail to achieve one of the properties.

3. [BONUS] In class we discussed how using your one-time pad key twice breaks all of the security properties. In this exercise, we will explore why this is true. You can read about Project Venona to learn how such an attack was carried out over several years against Soviet diplomatic telegrams.

Recall that the encryption of the first message would be $$ c_1 = m_1 + k $$ and the encryption of the second message would be $$ c_2 = m_2 + k $$

Your attack can make use of two observations: First, if two ciphertexts have the same value at a position, then their plaintexts also have the same character.

Second, your attack can first xor any two ciphertexts that you have: $$ c_1 + c_2 = (m_1 + k) + (m_2 + k) = m_1 + m_2 $$ The last equality in that question follows because $k+k = 0 \bmod 2$, when you xor the same string with itself (over the binary alphabet), then you get 0.
Now the attack can proceed by guessing a word, $w$, and the position that it appears in the first message $m_1$. Make your guess, and then xor the guess in the corresponding position of $m_1 + m_2$. The result would correspond to a word in $m_2$ at the same position; validate your guess based on how likely the resulting word is English.

Suppose that Alice uses the same key to encrypt the following four messages (written in hexadecimal):

Ciphertext 1    37  51  50  23  65  2A  5B  84  E4  6B  1F  71  2F  7   28  8C  67  D1  1F  E7  B4  5E  43  B5  F7  33  2F  A9  9C  74  18  72  F8  29  5A  A2  C2  EC  96  3C  2E  6D  5C  94  C2  E6  76  7B  1E  B3  A7  6   9A  38  39  E4  5E  D1  E   89  4D  71
Ciphertext 2    2D  49  48  23  64  36  2E  83  E9  66  70  6A  22  1A  5C  8B  7A  A5  18  81  D5  56  43  AD  F1  5C  28  B3  F9  7E  5   15  FB  21  4A  BE  C2  E2  94  53  3A  65  5A  93  B1  90  60  7C  1C  B0  A3  74  ED  32  25  96  4F  B9  10  9F  4D  71
Ciphertext 3    37  4E  5A  23  68  33  47  9B  81  77  18  7C  3F  74  45  8B  66  A5  13  88  D5  5E  43  A8  F7  40  46  A6  FA  64  14  67  96  34  46  BE  AF  85  8C  54  2D  C   52  89  AD  F4  13  60  2   DD  A9  60  99  50  35  F8  4F  B4  B   9E  28  15
Ciphertext 4    21  5F  3F  57  65  20  2E  87  F3  6A  13  76  22  1A  4F  EE  67  C3  77  8A  AC  32  5E  B6  E7  5E  24  B4  9C  63  1E  78  F3  34  46  B2  AC  E2  F8  4B  21  6F  5E  83  A6  90  67  61  18  AE  C6  71  8C  29  5C  F5  54  BC  1C  9F  4D  71

Recover all four plaintext messages. Hint: The messages are all in English upper-case with spaces, but the symbols are encoded using the ASCII mapping. For example, the character ‘A’ is encoded in ASCII as hex 41. If I guess that the first symbol in message 1 is an ‘A’, then the first key byte would be ‘41 XOR 37 = 0100 0001 XOR 0011 0111 = 0111 0110 = 76’. This means that the first character in the second message would be 2D XOR 76 = 5b which in ASCII corresponds to the letter ‘[’ which is invalid. Similarly, the first character in the third message (which is the same as the first character in the first message) would be an ‘A’ as well. Continue in this way with guessing and checking to recover all the messages.

Submitting Your Project

1. Lets assume that your gitlab repo is stored locally in your ~/cy2550 directory. Create a new directory named project1.
2. Add the files key.pub, message.txt.asc, and responses.txt to the project1 directory.
3. Add these files to a commit and push them to your repo.

     $ cd ~/cy2550
     $ git add project1/key.pub project1/message.txt.asc project1/responses.txt
     $ git commit -m "project1 files"
     $ git push
   

4. You can update your files as many times as you like before the deadline. Just makes your changes locally, and then add them to another commit and push them to the repo.

Grading

This project is worth 6% of your final grade, broken down as follows (out of 100):

• 10 points - turning in a 4096 bit, RSA public key
• 10 points - having a picture in your public key
• 20 points - answering both questions in responses.txt
• 20 points - having two valid signatures on your public key from your classmates
• 10 points - having your same pgp key in keybase with two followers
• 30 points - turning in a correctly encrypted, signed, and formatted message.txt
• 10 points (Bonus) - turning in all 4 correctly decrypted ciphertexts in responses.txt

Points can be lost for turning in files in incorrect formats (e.g. not ASCII), failing to follow specified formatting or naming conventions, having signatures that do not verify, encrypting messages using the wrong keys, etc.

Tips

• A big part of this assignment is social, i.e. signing each others’ public keys. Take the pain out of key signing by throwing a Key Signing Party (Google it)!
• The assignment clearly states that message.txt needs to be signed and encrypted. That does not mean signed then encrypted, or encrypted then signed. The difference here is subtle but substantial, and you will lose points if you turn in the wrong thing.
• How can you tell if your message.txt is signed and encrypted correctly? You can’t, obviously, because you don’t have my private key. Instead, I suggest signing and encrypting a message for one of your friends (you’re going to have their public keys, right?) and having them verify that it worked correctly.