Computer System Security
Lab 2 - Session Key Establishment and Man-in-the-Middle Attacks

Introduction

This lab consists of two parts. In the first part, you will analyze a protocol whose goal is to enable two parties to securely establish a common session key. The protocol, however, is broken: in particular, it is susceptible to a man-in-the-middle attack. Your job is to devise such attack, and then carry it out against a prototype implementation of the flawed protocol that we have provided.

In the second part of this lab, you will suggest a correction to the protocol, and modify our prototype so as to implement your fix. By doing the lab, you will exercise your protocol analysis and design skills, and work first-hand on a concrete example of a very common form of attack on communication protocols.

Software Setup

The files you will need for this lab are available in ~class/src/lab2.tar.gz. To install them in your account, log into a class machine and type the following: 

% tar xzf ~class/src/lab2.tar.gz
% cd lab2
% ls
Makefile        mtm.h           mtm_cert.c      mtm_pki.c
edu.h           mtm_alice.c     mtm_launcher.c  mtm_prot.c
edu_misc.c      mtm_bob.c       mtm_mallory.c
% make
%

We have set up the appropriate libraries and header files so that you can compile against libdcrypt on the class machines. If you are instead working on your own machine, you should install the dcrypt library in your system. (You will also need to have the GNU MP and dmalloc libraries installed in your machine.)

Please notice that the dcrypt library has changed from what was given out for the previous lab. If you are working on your own machine, make sure to upgrade before proceeding with this lab!

Lab Specification

The Protocol

 To keep things simple, the session-key establishment protocol we will consider assumes the presence of a Plublic-Key Infrastructure. What we mean by this is that, before starting the execution of the protocol, both parties, Alice and Bob, know the public key of a Certification Authority, whose job is to produce certificates---signed statements binding identities to public keys.
Alice -> Bob: {g, p, Na, "Bob"}Ka-1, ga mod p, certa
Bob -> Alice: {Na, Nb, "Alice"}Kb-1, gb mod p, certb

This is a variant of the Diffie-Hellman Protocol, in which additionally the parties use nonces and signatures with the hope of attaining additional security. Alice, the initiator, selects a large prime p and an element g of large order modulo p, along with a secret exponent a. Upon receiving her message, Bob checks the certificate certa, extracts Alice's public key KA from it, and verifies the validity of Alice's signature. Bob then selects his own random exponent b, computes the session key K from Alice's message as K=gab mod p, and includes the value yb=gb mod p in his reply. After performing similar checks on Bob's certificate and signature, Alice can recover the same session key as K=yba mod p.

An eavesdropper intercepting the communication between Alice and Bob can easily obtain the values ya=ga mod p and yb=gb mod p: however, it is widely believed that no efficient computation can recover K=gabmod p (and in particular you are not expected to disprove this conjucture the complete this lab :).

Our Prototype

We have already implemented for you a simple certificate generation utility to setup a toy Public-Key Infrastructure: take a look at its source file (~class/src/lab2/mtm_pki.c). To use the mtm_pki utility to generate certificates, first run it as follows: 

% ./mtm_pki init
%
This will create a directory named .pki/ within the current directory, along with two files: .pki/ca.priv and .pki/ca.pub, holding keys needed respectively to sign and to verify certificates.

Once the Public-Key Infrastructure has been initialized using the init command for mtm_pki, you can issue certificates using the cert command: 

% ./mtm_pki cert -g alice.priv alice.pub alice
%
This will create three files: alice.priv, alice.pub and alice.cert. The first two files store a newly generated private key/public key pair for a digital signature algorithm, whereas the last file contains a certificate binding the public key just placed in alice.pub to the identity alice. Such certificate is signed using the private key that was generated the last time you ran mtm_pki init.
If you don't provide the -g option, then mtm_pki cert will not generate a new private/public key pair for you; this is useful so that so that you can create certificates for existing public keys as well.
You can choose a different name for the certificate file using the -o option: 
% ./mtm_pki cert -o alice.cert.new -g alice.priv alice.pub alice 
% ls  alice.cert*
alice.cert      alice.cert.new
By default, certificates generated with mtm_pki cert are valid for 30 days. You can change this behavior using the -e option; for example, the following creates a certificate set to expire in 100 days: 
% ./mtm_pki cert -e 100 -g bob.priv bob.pub bob
%

To check the validity of a certificate created using mtm_pki cert, give the check command to mtm_pki: 

% ./mtm_pki check alice.cert alice.pub alice
Valid certificate

Part A

The tarball ~class/src/lab2.tar.gz contains two programs, mtm_alice.c and mtm_bob.c, which together implement the protocol described above. To simplify the task of mounting a man-in-the-middle attack, all communication between Alice and Bob is explicitly routed through Mallory, the man in the middle. A launcher program, mtm_launcher, takes care of setting up the communication channels, according to the following diagram: 

    +-------+                +---------+                +-------+
    |       | --->------>--- |         | ---<------<--- |       |
    | Alice |                | Mallory |                |  Bob  |
    |       | ---<------<--- |         | --->------>--- |       |
    +-------+                +---------+                +-------+
         \                        |                        /     
          \                       |                       /      
           \                      |                      /       
            \                     v                     /        
             \               +---------+               /         
              >-->------>--- |         | ---<------<--<          
                             | Launcher|                         
                             |         |                         
                             +---------+
After you have figured out the attack on our flawed protocol, in Part A of this lab you will have to modify the code of the man in the middle so as to mount your attack against Alice and Bob. To do this, you should fill out some details in Mallory's code, which is contained in the file mtm_mallory.c. The skeleton code for mtm_mallory that comes bundled within ~class/src/lab2.tar.gz simply relays any message received from one party to the other. You shouldn't need to change anything else in the skeleton code besides mtm_mallory.c to complete Part A.

To see the prototype implementation in action, first build it using make: 

% make
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -I. -I/usr/local
/include/ -c mtm_pki.c
...
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -I. -I/usr/local
/include/ -c mtm_mallory.c
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -o mtm_mallory m
tm_mallory.o mtm_prot.o mtm_cert.o edu_misc.o -L. -L/usr/local/lib/ -ldcrypt -ld
malloc -lgmp
%
(Notice that you may have to fiddle with the Makefile a bit if you are working on your own linux box.)

Now, create the PKI and the certificates for Alice and Bob, and then run the launcher: 

% ./mtm_pki init 
% ./mtm_pki cert -g alice.priv alice.pub alice 
% ./mtm_pki cert -g bob.priv bob.pub bob 
% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Received from Alice:
====================
cZVjLBh0dajGWyPIthcXfA==

Sent to Bob:
============
cZVjLBh0dajGWyPIthcXfA==

Mallory couldn't break the protocol.
The secret was: 0xb919cd5e3830639be9f900ff4a06af1d

Mallory said:
Attack not yet implemented!

%

A brief explanation of what happened is the following: first, Alice sent Bob flow 1 according to the protocol described above. Mallory intercepts the message, and prints it out to terminal for you. Then, Mallory should compute what to send to Bob on behalf of Alice, and print that to terminal as well. Currently, the attack is not implemented, so Mallory just forwards to Bob whatever Alice sent. Bob then continues with the protocol, and his message to Alice is again intercepted by Mallory, who prints it out to the terminal, and then just relays it to Alice.

At this point, Alice and Bob share a session key K. To check that the session key was established correctly, the test continues with Alice picking a random number and sending it to the launcher (notice that this channel is not available to Mallory, so he cannot see the value chosen by Alice). Alice then encrypts this random number (using AES) with the session key K, and sends the ciphertext to Mallory. Our dummy implementation of Mallory is not able to come up with the necessary session key to decrypt such ciphertext, so it just relays this to Bob. Using the just-established session key, Bob can decrypt Alice's message and recover the secret number, which he then passes to the launcher for comparison to the value sent by Alice (again, this channel from Bob to the launcher is not available to Mallory). Finally, the launcher expects to receive from Mallory a "guess" to the secret value sent from Alice to Bob: since the current code for Mallory does not implement the attack, Mallory instead passes to the launcher the string "Attack not yet implemented!\n", and the test concludes.

Once you have done your changes to mtm_mallory.c, the output of mtm_launcher should instead look as follows: 

% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Received from Alice:
====================
slB6HQSaGYSTAkUl2OlOGw==

Sent to Bob:
============
EEUnq7il0hVGakYOZsZpBQ==

Successful man-in-the-middle attack!
Recovered secret was: 0x7f40ed8a68ff383a5ba533e0b65562db
%

What to Hand in

You should submit three files:

No special format is required for the description of the attack on the protocol. An ASCII file named attack.txt showing the interleaving of messages that give rise to the man-in-the-middle attack is sufficient. You can hand this in ahead-of-time if you want.

To make a tarball with your code, run the following commands (from the directory where your source files are located): 

% cd ..
% tar cf mtm.tar lab2/
% gzip mtm.tar
%
(If the name of the directory containing your sources is not lab2, then substitute the appropriate name in the second command above.)

To create a script file, use the script command. When you run script, everything you type gets saved in a file called typescript. Press CTRL-D to finish the script. For example: 

% script
Script started, output file is typescript
% ./mtm_pki init 
% ./mtm_pki cert -g alice.priv alice.pub alice 
% ./mtm_pki cert -g bob.priv bob.pub bob 
% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Received from Alice:
====================
slB6HQSaGYSTAkUl2OlOGw==

Sent to Bob:
============
EEUnq7il0hVGakYOZsZpBQ==

Successful man-in-the-middle attack!
Recovered secret was: 0x7f40ed8a68ff383a5ba533e0b65562db
% ^D
% ^D Script done, output file is typescript 
%

As usual, copy your files to the directory ~class/handin/lab2/logname (where logname is your login name on the class machines): 

% cp attack.txt mtm.tar.gz typescript ~class/handin/lab2/`logname`/
%

Part B

In Part B of this lab, you will suggest a fix to the flawed protocol described above. You should provide an informal (but convincing) argument why your suggestion is secure, and in particular why it resists the man-in-the-middle attack that you implemented in Part A.

You should then modify our prototype implementation so as to reflect the changes to the protocol that you suggested (in particular, you may want to consider changing one or more of the following files: mtm_prot.c, mtm_alice.c and mtm_bob.c).

Once you have done your changes, your fixed version of the protocol should detect the attack and abort the interaction: 

% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Sent to Bob:
============
...
error reading/parsing alice's message:
...
Unexpected end of file
error parsing bob's message:
(null)Unexpected end of file
error reading/parsing bob's message:
(null)Unexpected end of file
reading from Alice: Undefined error: 0
%

Rolling back the code of mtm_mallory.c to the skeleton code provided within ~class/src/lab2.tar.gz, your new version of the protocol should work fine: 

% mv mtm_mallory.c mtm_mallory.c.attack 
% cp ~class/src/lab2/mtm_mallory.c . 
% make 
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -I. -I/usr/local
/include/ -c mtm_mallory.c
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -o mtm_mallory m
tm_mallory.o mtm_prot.o mtm_cert.o edu_misc.o -L. -L/usr/local/lib/ -ldcrypt -ld
malloc -lgmp
% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Received from Alice:
====================
+7HtUo62wV1ELWLIlu10LA==

Sent to Bob:
============
+7HtUo62wV1ELWLIlu10LA==

Mallory couldn't break the protocol.
The secret was: 0xfd1f9ae158c41c8222f1629eff7f9739

Mallory said:
Attack not yet implemented!

%

What to Hand in

Also for Part B, you should submit three files:

No special format is required for the description of the fixed protocol. An ASCII file named fixed.txt, describing the protocol with the usual "message syntax" (like the one we used for our flawed protocol), along with a convincing informal argument that the protocol you suggest is secure, is sufficient. You can hand this in ahead-of-time if you want.

To make a tarball with your code, run the following commands (from the directory where your source files are located): 

% cd ..
% tar cf fix.tar lab2/
% gzip fix.tar
%
(If the name of the directory containing your sources is not lab2, then substitute the appropriate name in the second command above.) Please choose different names for your tarballs from Part A and Part B so as to avoid overwriting!

To create a script file, use the script command. When you run script, everything you type gets saved in a file called typescript. Press CTRL-D to finish the script. For example: 

% script typescript.fix
Script started, output file is typescript.fix
% ./mtm_pki init 
% ./mtm_pki cert -g alice.priv alice.pub alice 
% ./mtm_pki cert -g bob.priv bob.pub bob 
% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Sent to Bob:
============
...
error reading/parsing alice's message:
...
Unexpected end of file
error parsing bob's message:
(null)Unexpected end of file
error reading/parsing bob's message:
(null)Unexpected end of file
reading from Alice: Undefined error: 0
%
% mv mtm_mallory.c mtm_mallory.c.attack 
% cp ~class/src/lab2/mtm_mallory.c . 
% make 
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -I. -I/usr/local
/include/ -c mtm_mallory.c
gcc -g -O2 -ansi -Wall -Wsign-compare -Wchar-subscripts -Werror -o mtm_mallory m
tm_mallory.o mtm_prot.o mtm_cert.o edu_misc.o -L. -L/usr/local/lib/ -ldcrypt -ld
malloc -lgmp
% ./mtm_launcher 
Received from Alice:
====================
MTM-Flow1-1:param=(p=0xf79f1bc68ff0853731fcdf48c726fcd0fd7d67787865d1022d3e6ae51
b26db9486307c77040f44229c772b392c9f98a9028bfbc3cc71966511d89a947ae0d87ea8fccfcc3
...
Received from Alice:
====================
+7HtUo62wV1ELWLIlu10LA==

Sent to Bob:
============
+7HtUo62wV1ELWLIlu10LA==

Mallory couldn't break the protocol.
The secret was: 0xfd1f9ae158c41c8222f1629eff7f9739

Mallory said:
Attack not yet implemented!

% 
% ^D
% ^D Script done, output file is typescript.fix

As usual, copy your files to the directory ~class/handin/lab2/logname (where logname is your login name on the class machines): 

% cp fixed.txt fix.tar.gz typescript.fix ~class/handin/lab2/`logname`/
%

If you have any problems with/question about either part of the lab, please contact the TA or the instructor at email address.

This completes the lab.

Collaboration policy

You must write all the code you hand in for the programming assignments, except for code that we give you as part of the assigment. You are not allowed to look at anyone else's solution. You may discuss the assignments with other students, but you may not look at or copy each others' code.