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
.
-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.
-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
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| | | +---------+
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
%
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`/
%
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! %
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 .
This completes the lab.
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.