15-410 HW2 solutions (Spring, 2006)

Question 1 - Public Key Practicum

If you did this problem correctly, in a couple of hours your hw2 directory should contain a $USER.message.decrypted file. If not, check to see if there is a $USER.ERROR file. If not, a popular problem is that you used file names other than the ones specified in the assignment, the grading script wasn't able to guess what you meant, and the grader hasn't yet had the time to manually intervene.

By the way, your encrypted messages to us were read and, generally, appreciated.

Question 2 - Kerberos

A client wishing to send a LIST command to a print server should present:

Its ticket for the printing service, which will look like {principal=de0u,expires:2006-12-08-23:59:59,Ksession=404804230823}Ks
The encrypted command, which will look like {command="LIST"}Ksession



This information would be included in a message with some agreed-upon
format--for example, a 4-byte network-byte-order integer specifying
the number N of bytes of Kerberos ticket which follow,
the ticket itself, an integer specifying the length of the encrypted
command, and then the bytes of the command.
Many variations on this are possible--for example, it could be possible
to agree in advance on the size of a ticket block, and it would be safer
if the integer specifying the length of the command were also encrypted
(why?).

The server would use its secret key to decrypt the ticket,
which would reliably tell it the principal to which the session
key had been issued.  Next the server would use the session key
to decrypt the command string, at which point it would reliably
believe that de0u had issued the LIST
command.

Part B


Joe can receive all bytes of the traffic between Kelly's
machine and the print server, but he has no practical way
to determine the messages contained therein because he
doesn't know the session key used for the encryption.
He can of
course use the impractical approach of trying
all possible session keys--which might not be so impractical
after all if the Kerberos server doesn't choose them in
a truly random fashion, if the key space of the symmetric
cipher is too small, or ... imagine other threats here.


Note that Joe can receive all bytes of the traffic between
Kelly's
machine and the Kerberos server, including seeing
the Kerberos server give Kelly a ticket, and still not learn
anything useful--this time, because that traffic is encrypted
with Kelly's secret key.



One hole in the protocol as described is that if the print
server sends Kelly a very long response to the LIST
command Joe can assume Kelly has many jobs queued and
become bitter.  This traffic analysis problem can be avoided
if the print server returns a fixed-size message,
e.g.,

Jobs queued: 0000000000003; bytes queued: 0000342324303

or returns a message padded by a genuinely random number of
junk bytes.




Question 3 - Kernel Runtime Environment

Part A

PowerPC kernel authors must either write their kernels to run
with virtual memory turned off, which is very inconvenient in
practice, or must delicately arrange for all handler wrapper
code to run for a while with VM off and then turn it on,
i.e., save a trap frame to somewhere in physical memory which
will later be restored from via a virtual address.


Part B


In order to resume after a surprise it is necessary to retrieve
data from
%S_EFLAGS,
%S_EIP, etc.
Since there is only one instance of each of these registers
(the processor does not dump a trap frame onto an indefinite-length
stack),
two back-to-back surprises would be disastrous:  the first surprise
would store user code's resumption information into the backup registers,
and the second surprise would overwrite that information with
information about resuming the handler for the first surprise.
It would then be impossible to resume execution of user code.
Therefore, the processor must disable interrupts until the
OS-provided wrapper code can save the backup registers somewhere
safe (e.g., a stack, though other options are possible).
After the save step is complete the OS can turn interrupts back on.



It might be fun to speculate about whether wrapper code turns VM
or interrupts on first...





For further reading...

Here is last semester's homework page.

[Last modified Friday December 08, 2006]