CS 361S - Network Security and PrivacySpring 2014Homework #1Due: 11am CST (in class), February 11, 2014YOUR NAME:Collaboration policyNo collaboration is permitted on this assignment. Any cheating (e.g., submitting anotherperson’s work as your own, or permitting your work to be copied) will automatically resultin a failing grade. The Deparment of Computer Science code of conduct can be found athttp://www.cs.utexas.edu/undergraduate-program/code-conduct.Late submission policyThis homework is due at the beginning of class on February 11. All late submissionswill be subject to the following policy.You start the semester with a credit of 3 late days. For the purpose of counting latedays, a “day” is 24 hours starting at 11am on the assignment’s due date. Partial days arerounded up to the next full day. You are free to divide your late days among the take-homeassignments (3 homeworks and 2 projects) any way you want: submit three assignments1 day late, submit one assignment 3 days late, etc. After your 3 days are used up, nolate submissions will be accepted and you will automatically receive 0 points for each lateassignment.You may submit late assignments to Vitaly Shmatikov or Oliver Jensen. If you aresubmitting late, please indicate how many late days you are using.Write the number of late days you are using:1Homework #1: A Trip to Molvanˆıa (50 points)Molvanˆıa is a small, land-locked republic in Eastern Europe famous for its phishers, spam-lords, botmasters—and computer security researchers. It also produces 83% of the world’sb33tr00t. Most people get to Molvanˆıa either by air or by accident, but in this homework,we travel there virtually.Problem 1 (5 points)Molvanˆıan PCs still run Windows 98. Therefore, passwords in Molvanˆıa are hashed usingMicrosoft’s LAN Manager (LM) hash, which works as follows:• The password is converted into upper case, null-padded to 14 characters, and split intotwo 7-character halves.• Each half is separately converted into a DES key. This key is used to encrypt theASCII string “KGS!@#$”, producing an 8-byte value.• The two 8-byte values are concatenated, resulting in a 16-byte hash.Suppose the attacker obtains a file with n hashed passwords. How much work would heneed to do to crack these passwords by brute-force search? Show your calculations.Problem 2 (5 points)MMACs (Molvanˆıan Message Authentication Codes) are intended to provide authenticationand integrity for email messages between Molvanˆıan diplomatic missions. All missions sharethe secret key K. Each message M sent by one mission to another is accompanied by aMMAC, which is constructed as MH(K, M).MH is a hash function with 320-bit output invented by Molvanˆıan cryptologists. Theytook SHA-1 (which is assumed to be one-way and collision-resistant—at least for the purposesof this problem) and used it as a building block to create MH. They even proved that MH,too, is one-way, collision-resistant, and hides the key.As it turns out, MMAC is completely broken. Someone eavesdropping on a single MMAC-protected message call can gather enough information to forge valid MMACs in the future,2that is, to send any message they want accompanied by a forged MMAC that will passverification by any Molvanˆıan mission.How is M H constructed? (Important: your construction must be one-way, collision-resistant, hide the key, and still make the above scheme vulnerable to forging.)Problem 3 (5 points)Molvanˆıan Telecom is selling a fancy smartphone model called jPhone. Each jPhone stores along, randomly generated secret value. The phone service provider keeps all secrets, togetherwith the corresponding cell phone numbers, in its database.When a jPhone user wishes to buy a new ringtone, the jPhone transmits its phone numberfollowed by the secret (in the clear) to the ringtone server. The server checks in its databasewhether the secret corresponds to the provided phone number and, if it does, downloads theringtone to the phone and bills the account of the phone’s owner.This design is vulnerable to a cloning attack. Someone eavesdropping on a jPhone trans-mission can easily intercept a (phone number-secret) pair. He can then hack his own jPhone’stransmission software to use the intercepted pair, enabling him to download ringtones whichare billed to the victim’s account.Design an authentication scheme for jPhone based on a cryptographically secure hashfunction that prevents passive attackers from exploiting eavesdropped messages between thejPhone and the ringtone server.Problem 4To access his account online at the Bank of Molvanˆıa, a user must install a client programon his Windows 98 PC. The user’s password is set up when the account is created and storedon the bank’s server.3When the user logs in, the client prompts him for his password p, computes HMAC1ofp and current time t rounded to a minute, and sends the result to the server. The serverrecomputes HMAC using p and its own time. If the resulting value is equal to the valuereceived from the client, the server allows access.Problem 4a (5 points)Unfortunately, Windows 98 PCs crash a lot and when they crash, the clock resets to midnight,January 1, 1980. Subsequently, the client’s timestamps are all wrong and authentication fails.The Bank of Molvanˆıa hired George Spelvin, Molvanˆıa’s premier security expert, to fixthe problem. Spelvin suggested the following clever modification to this authenticationscheme. Instead of the client generating the timestamp t, the server sends t to the client asthe challenge. The client’s response is computed as before.Does this modification have any security consequences? (Hint: consider an active man-in-the-middle attacker who controls the network.)Problem 4b (5 points)Modify Spelvin’s scheme so that it is secure against an active man-in-the-middle attacker,but still does not require the client to generate its own timestamps. Your solution shoulduse only timestamps, passwords, and HMAC.Problem 5The Bank of Molvanˆıa adopted the following defense against phishing. The first time a usercomes to the bank’s website, she enters her username and password as usual, and is givena choice between several pictures. The association between the username and the chosen1This HMAC uses SHA-1, not LAN Manager hash.4picture is stored in the bank’s database. In all subsequent sessions, the user types in herusername and expects to be shown a picture. Unless she sees the picture she