Programming Project #4
CMPS 111, Fall 2007
Assigned: November 26th
Due: Friday, December 7th at 10 PM
(automatic extension to Wednesday, December 12th at 10 PM)
NOTE: You may use at most one grace day for this project. No
project will be accepted after 10 PM on Thursday, December 13th.
Remember: your project must be turned in online.
Purpose
The main goal for this project is to use a combination of system calls and user program to implement encryption for the MINIX 3 file system. You must implement:
- A system call that adds an encryption key for a particular user ID.
-
Operating system code that applies the key to a file if all of
the following characteristics apply:
- The key is set for the current user
- The file has its encryption bit set
- A program that encrypts or decrypts a file and sets its encryption bit appropriately.
As with the previous project, you will experiment with operating system kernels, and to do work in such a way that may very well crash the (simulated) computer. You'll get experience with modifying a kernel, and may end up with an OS that doesn't work, so you'll learn how to manage multiple kernels, at least one of which works.
You should also read over the general project information page before you start this project. In them, you will find information about MINIX 3 as well as general guidelines and hints for projects in this class.
Details
The goal of this assignment is to give you additional experience in modifying MINIX 3 and to gain some familiarity with file systems, system calls, and encryption. As with earlier programs, you won't have to write too much code, but it'll be critical to understand where the code goes. Obviously, most (if not all) of your code will go into the fs server in MINIX, so that's a good place to start looking.
The best place to encrypt or decrypt data is at the same time as
it's copied between kernel space and user space, a task that's
accomplished using the sys_vircopy function.
Encryption and decryption can be done in several ways. You
could copy a few bytes at a time to a buffer in the FS server
and operate on them before copying them again to the user. This
approach is simple, but it involves a separate buffer which
you'll have to track. A second approach would involve doing the
encryption or decryption in the buffer itself. Encryption is
easy: just encrypt the data after you copy it. Decryption is
tougher, since you don't want to leave decrypted data in the
buffer. To get around this, decrypt the part of the buffer
you're copying, copy it to the user, and then re-encrypt it.
Either approach (separate buffer or operate in the real
buffer) is acceptable, and you may mix and match
if
that's easier for you.
So how do you know if a file is to be encrypted? As discussed
in class, each file has permission bits associated with
it. Fortunately (for us), one of the permission bits
is reserved for future use
: S_ISVTX (01000 in octal,
defined in sys/stat.h. If this bit is set using the
chmod system call (or command), the file should be
encrypted and decrypted automatically, assuming the key is
available. If this bit is not set, the file is never encrypted.
Note that if no key is available for the user reading or writing
the file, the file is not encrypted or decrypted either. This
means that a file with the bit set can't be read if the key
hasn't been set first.
The encryption algorithm you'll be using is AES, which takes a 128 bit key; for this assignment, the high-order 64 bits will all be zero. You'll be using it in CTR mode, with the counter counting the offset in 16 byte chunks. Thus, to encrypt bytes 1024–1039 of the file, you'd set the CTR value to 1024/16=64. For each 16 byte chunk, encryption and decryption are done using the same function: data^=AESencrypt((ctr|(fileid<<64),userkey). Sample code that encrypts or decrypts a file (they're the same operation!) is available as part of the AES tar file.
You'll need to write a single system call for this assignment.
setkey(unsigned int k0, k1): this call sets the key for
the current user. The two most significant integers (half the
AES key) are zero, with k0 and k1 occupying the
other positions. Obviously, it doesn't matter which
places are filled in the key, as long as the files aren't being
shared and your setkey() system call is consistent
about which values go where. If both k0 and k1
are zero in setkey(), encryption and decryption are
disabled for that user.
Encryption for a file is enabled by setting the sticky bit (01000 in octal). In order to enable this, you'll need to modify the ALL_MODES constant in minix/const.h to be 0007777. Once this has been done (and the kernel recompiled), you can use chmod to set the sticky bit and enable encryption for a file.
Of course, merely enabling encryption doesn't encrypt the file automatically. You should write a program that takes three arguments: the letter e (encrypt) or d (decrypt), a 64 bit key, and a file name. Your program should ensure that the file is encrypted or decrypted as necessary (use the current sticky bit setting to determine if encryption / decryption is necessary) and set the sticky bit properly using the chmod() system call. Note that, to properly encrypt the file, you'll need the file ID (inode number), which you can obtain with the stat() system call. You are encouraged to use the sample code that encrypts a file as a base for your program.
Once you've set up the file to be encrypted, access to it should work properly if the key is set in the kernel. Of course, access to non-encrypted files should always work properly. Note that you don't need to support memory-mapped encrypted files; you just need to handle read and write properly.
Deliverables
You must hand in a compressed tar file of your project directory, including your design document. You must do a "make clean" before creating the tar file. In addition, you should include a README file to explain anything unusual to the teaching assistant. Your code and other associated files must be in a single directory; the TA will copy them to his MINIX installation and compile and run them there. You should have two subdirectories in your tar file below your main directory: one containing the kernel source files from the servers/fs directory, and the other containing your user program.
Do not submit object files, assembler files, or executables. Every file in the tar file that could be generated automatically by the compiler or assembler will result in a 5 point deduction from your programming assignment grade.
Your design document should be called design.txt (if plain ASCII text, with a maximum line length of 75 characters) or design.pdf (if in Adobe PDF), and should reside in the project directory with the rest of your code. Formats other than plain text or PDF are not acceptable; please convert other formats (MS Word, LaTeX, HTML, etc.) to PDF. Your design document should describe the design of your assignment in enough detail that a knowledgeable programmer could duplicate your work. This includes descriptions of the data structures you use, all non-trivial algorithms and formulas, and a description of each function including its purpose, inputs, outputs, and assumptions it makes about the inputs or outputs. A sample design document is available on the course web page.
Hints
- START EARLY! You should start with your design, and check it over with the course staff.
- Experiment! You're running in an emulated system—you can't crash the whole computer (and if you can, let us know...).
- You may want to edit your code outside of MINIX (using
your favorite text editor) and copy it into MINIX to
compile and run it. This has several advantages:
- Crashes in MINIX don't harm your source code (by not writing changes to disk, perhaps).
- Most OSes have better editors than what's available in MINIX.
- START EARLY!
- Look over the operating system code before writing your design document (not to mention your code!). Leverage existing code as much as possible, and modify as little as possible.
- For this assignment, you should write fewer than 200 lines of kernel code. Your system call should go into fs/protect.c, and you can keep a table of keys and users local to the fs server.
- rw_chunk in fs/read.cs is the code that actually reads (or writes) data in a file. It's likely that encryption code near the sys_virtcopy routine will be easiest.
- Play around with the encryption code outside the kernel first so you're comfortable with it. You should get the program to encrypt / decrypt files working at user level before putting encryption code into the kernel. You can either add the AES code to an existing fs C file, or you can add the code to the list of C files in the makefile. However, you must ensure that the AES code gets linked into the fs server somehow.
- Did we mention that you should START EARLY!
We assume that you are already familiar with makefiles and debugging techniques from earlier classes such as CMPS 101 or from the sections held the first week of class. If not, this will be a considerably more difficult project because you will have to learn to use these tools as well.
This project doesn't require a lot of coding (typically fewer than 200 lines of code), but does require that you understand how to use MINIX and how to use basic system calls. You're encouraged to go to the class discussion section or talk with the course staff during office hours to get help if you need it.
You should do your design first, before writing your code. To do this, experiment with the existing shell template (if you like), inserting debugging print statements if it'll help. It may be more "fun" to just start coding without a design, but it'll also result in spending more time than you need to on the project.
IMPORTANT: As with all of the projects this quarter, the key to success is starting early. You can always take a break if you finish early, but it's impossible to complete a 20 hour project in the remaining 12 hours before it's due....
Project groups
You may do this project with a project partner of your choice. However, you can't switch partners if you already had a partner for Project #2. If you choose to work with a partner (and we encourage it), you both receive the same grade for the project. One of you should turn in a single file called partner.txt with the name and CATS account of your partner. The other partner should turn in files as above. Please make sure that both partners' names and accounts appear on all project files.
Last updated 27 Nov 2007 by Ethan L. Miller