Midterm Solutions and Comments

Part of material for 22C:169, Spring 2005
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

Grade Distribution

Median = 9.?            X X   X
Mean   = ?.??   X   X   X X   X
                X   X   X X   X   X       X
                X   X X X X X X   X X     X   X
       0 . 2 . 4 . 6 . 8 . 10. 12. 14. 16. 18. 20


Consider a smartcard with 32K bytes of Flash EEPROM and 512 bytes of RAM. This is used to authenticate customers in ATM transactions using a two-step authentication process:

First, immediately after insertion in the ATM, the card engages in a dialogue with the ATM to authenticate the smartcard as being valid for one particular bank account.

Second, the ATM and card cooperate to authenticate the smart-card user, for example, by having the user enter a PIN on a keypad on the ATM.

You may assume that all ATMs are networked and have fast access to the bank's database, indexed by account number.


  1. Assume that the smartcard and the bank's server share a secret key (for example, a random number associated with the bank account number. If the smartcard passes its key to the ATM, or if the ATM passes its key to the smartcard for validation, an eavesdropper could intercept the key and use it to forge a new smartcard.

    Suggest a solution to the smartcard authentication problem that allows the card to prove to the ATM that it has the same secret key that the ATM has without disclosing the key. (5 Points)

    There are many reasonable solutions. All of them assume that the key is held locally by the card and never transmitted between the card and ATM (of coursee, when the card was issued, a key must have been loaded in the card as part of the issue process.)

    One idea: Generate a random number n within the ATM (or nonse, a time stamp, possibly combined with the ATM ID in order to guarantee that it will never be reused or seen elsewhere). Pass this number to the card. The card will return f(n, key). The ATM (which gets the key using a secure link to the bank's database) also computes f(n, key), and then compares it with the value returned by the card. The function f should be a trapdoor function.

    Another idea: Generate a random number, as above, within the ATM, and encrypt it using the key from the bank's database. Send the encrypted key to the card, which decrypts it using the card's key. The ATM returns the decrypted result, which is compared with the original. The cryptography here is a symmetric key cypher. This scheme is no weaker than the first one because in both, the eavesdropper has equivalent information from which to launch an exhaustive search for the key (assuming strong cryptosystems were used for the trapdoor function and symmetric key crypto).

    1 in 3 students had answers that earned 4 points or more. A similar number earned from 2 to 3 points, with answers that were as much right as wrong, and a similar number earned less credit, with answers that conveyed limited understanding of the problem.

  2. You have found that the ATM to smartcard protocol exchanges all of its messages in textual format, mostly in the form of numbers encoded in hexadecimal and terminated with a newline. Just for fun, you program a smartcard program that accepts an input from the ATM, ignores it, and returns a very long string as a reply. When you put this card in the ATM, the screen goes blue and the machine ceases working. Give two brief explanations of what probably happened.

    a) Give a very brief explanation for someone who knows about security. (1 Point)

    The ATM was vulnerable to a buffer overflow attack of some kind. About half the class gave essentially this answer.

    Some speculated that it was waiting for a newline. The screen going blank and the ATM ceasing to work is not a symptom of "normal behavior" such as hanging in a loop awaiting a newline.

    Some spoke of "memory protection errors", a term that implies mechanisms about which we have no basis for speculation.

    Perhaps 1 in 5 gave answers that were sufficiently strange that no credit could be granted.

    b) Give the explanation you would give to the junior college graduate with an associate's degree in computer technology who wrote the code. (2 Points)

    It is likely that the long input string was copied to a shorter buffer in the application program without checking that the string would fit in that buffer. The standard C library routines gets(), strcpy() and strcat() invite this error because they have no provisions for checking the buffer length. When the buffer is over-filled, the additional data in the string is likely to overwrite variables. If the buffer is a local variable, overflowing the buffer is likely to destroy the return address, so that, when the called routine returned, it took a wild jump into unpredictable memory causing the application to termiate.

    Only one in 1 in 7 got this right.

    1 in 4 said that the buffer overflow would likely overwrite the machine code. This is an unlikely outcome (very few computer systems designed since 1970 have encouraged mixing code and data in a way that makes this likely, and many systems designed since then routinely locked code so that it was read-only.)

    1 in 4 gave weak explanations, from which it was difficult to understand what they hypothesized, or proposed such relatively unlikely causes of the failure as unhandled exceptions of some kind. These answers could earn half credit.

  3. Assume that the smartcard has a copy of the PIN stored in its Flash memory. When the user enters a pin on the ATM keypad, the ATM must somehow verify that the PIN entered is the same as the PIN stored on the card. Obviously, one cannot just send the PIN to the other as plaintext and enquire "is this the right PIN?", accepting a yes or no answer.

    a) Suppose the ATM encrypts the PIN, transmits the encrypted PIN to the smartcard, and then lets the card decrypt the PIN and check it. Ignoring questions about what key (or keys) are used, does this solve any of the problems with the original scheme? (1 Point)

    This is a bad idea because the response from the card to the ATM is implied to be either "match" or "no match", so independent of the security of the cryptography used, we could attack the system by building a card that always claims "match". Even if the system first validated the card, we could mount a man-in-the-middle attack, using a valid card, and then substituting "match" for whatever reply the card made, in order to defeat the PIN checking done by the ATM.

    Half the class got this. Another quarter of the class earned partial credit by identifying secondary security problems without seeing this primary problem.

    b) Suppose the smartcard encrypts the PIN, transmits the encrypted PIN to the ATM, and then the ATM decrypts the PIN and checks it. Ignoring questions about what key (or keys) are used, does this solve any of the problems with the original scheme? (1 Point)

    This scheme is quite workable. More students got full credit here than on part a. Fewer students focused on secondary issues, and fewer earned no credit. Apparently, some students had difficulty "ignoring questions about what key (or keys) are used" and thought that this implied that bad key management was used (where in fact, it was just pushing this issue off until part c, where the key management question is addressed directly.)

    c) Go back and check the original background information provided for this exam. This information contains hints that are sufficient to answer the following: What key or keys should be used for the cryptography outlined in parts a and b, and is this symmetric key or a public key cryptography. (2 Points)

    We are given that the smart card has only a small EEPROM. This prevents the smart card from holding any significant database of public keys. Furthermore, customers expect that, when a new ATM is installed, their card will work in that ATM without any special preparation, so even if the card could hold an infinite database, it could not hold the public keys of all ATMs. So, any answer involving public key cryptography must not require the smart card to know the public key of the ATM.

    Question one suggested that the bank database and the card could easily share a private key.

    1 in 5 did well here, and a few more lost credit for vague or odd but basically sound answers. 1 in 3 suggested using public key cryptography in a way that required a database of ATM keys on the card, earning half credit. Almost as many proposed weaker schemes, for example, using the PIN as a key; using a 4-digit key is dangerously weak in the first place, and this suggestion contradicts the assumptions of both parts a and b, where it is plainly stated that the PIN is encrypted and transmitted.

  4. Background: A computer system has a paged memory management unit, so that the most significant bits of the virtual address select the page-table entry to use, where the page-table entry identifies the actual physical address where the indicated page is stored. On this machine, traps turn off the MMU. There are two operating systems for this machine:

    OS-A allocates the entire virtual address space to the user process, and the entire operating system runs with the MMU turned off, so in effect, all system calls are done directly by trap handlers.

    OS-B splits the virtual address space so that the high pages of the virtual address space are allocated to the user process, while the low pages are used by the system. In user state, the low pages of the virtual address space are all invalid. The trap handler simply makes the low pages valid and then turns the MMU back on to execute the system code in the low part of the address space.

    a) When a user passes a pointer to a system call in OS-A, what extra work, if any, does the system have to do in order to access the memory location that the user intended to be referenced by that pointer? (2 Points)

    The system must take pointers passed by the user and perform virtual to physical address translation on those pointers before using them, since the user's pointers are useless with the memory management unit turned off. This translation involves replacing the page field in each of the user's pointers with the physical address of that page, and it may involve more complex operations if the pointer refers to an object that could span a page boundary.

    1 in 5 did well here, and a similar number earned 3/4 credit by having answers that were largely correct, for example, by suggesting that the MMU would have to be turned back on before the pointer could be used (unfortunately, if the MMU is on, the operating system code cannot be executed, so this will not work).

    Half the class earned no credit, frequently expressing a complete misunderstanding of how the systems operate or of what an MMU does. This is of great concern. 22C:60 is supposed to cover this issue in at least a little detail, and all of the texts I have seen for 060 contain at least some coverage.

    b) When a user passes a pointer to a system call in OS-B, what extra work if any, does the system have to do in order to access the memory location that the user intended to be referenced by that pointer? (2 Points)

    No work at all. The system may directly follow any pointer passed by the user, since the system is in the same address space.

    1 in 4 did well here. A significant number, however, diluted good answers by mixing in questions of parameter validation. Validation is not needed to access memory, but only to determine if this access is permitted, a separate question (part d).

    c) Does OS-A require extra code for parameter validation in order to protect it from damaging itself because of invalid pointers passed by users? (2 Points)

    No. All pointers issued by the user are inherently legal, because the entire virtual address space belongs to the user. The translation discussed in part a does all the work necessary to prepare for use of such pointers.

    1 in 3 did well here.

    d) Does OS-B require extra code for parameter validation in order to protect it from damaging itself because of invalid pointers passed by users? (2 Points)

    Yes. All pointers must be compared with the fence value that splits the address space between user and system. Failure to do so allows the user to issue an address to a system call that causes the system to perform unsafe operations on system memory, perhaps altering or disclosing critical information.

    Half the class got this. Misunderstandings frequently centered on the very nature of system calls.