Assignment 8, Solutions

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

  1. Background: The CryptoThumb USB drive (a fictional but typical modern product) has cryptographic firmware in its on-board processor. When you mount it on your computer, it shows up as two separate USB devices, A and B, for our purposes. Device A is the "virtual disk" that the drive provides you. Device B is an output-only device to which you can send passwords that are used as cryptographic keys. It uses the SHA-1 hash function to compute a 128-bit key from the password, then uses this key with AES to encrypt and decrypt data.

    All data output to device A is encrypted with the password most recent password sent to device B, and all input from device A is decrypted with the most recent password. If you have the CryptoThumb device driver installed, as soon as you mount the drive, it asks for a password, and there is also a way to change the password using the CryptoThumb password tool if you want to change passwords in mid session.

    The CryptoThumb documentation states that it only holds the current password in RAM and never stores it in flash memory. Only encrypted data is stored in flash memory. Furthermore, the drive includes a self-destruct feature. If a user tries to read any particular "disk address" on drive A repeatedly, changing the password before each try, more than 10 times, the CryptoThumb drive concludes that it is under attack and disables itself, erasing all stored data. It gives you 10 trials to allow for mistyped passwords.

    Engulf and Devour Corporation distributes CryptoThumb drives to all of its employees in an effort to protect its company business. The company is notorious for evil, as documented in Silent Movie.

    CryptoThumb drives are actually made by Fly-By-Night Computer Peripherals Inc., a low-cost high-volume contractor with no employees and no production facilities. FBN outsources all of its work to a variety of subcontractors.

    a) An Engulf and Devour employee drops his CryptoThumb drive. You guess that most employees don't use long passwords, so you suspect you could use a trial-and-error dictionary attack. The root of the file system on the drive would be stored in "disk address" 0. You have software that can recognize a properly decrypted file-system root sector. Describe how you would attack the drive without setting off its self-destruct mechanism. (0.6 point)

    I would repeatedly try to read the sector at "disk address" 0 using different passwords selected from my dictionary of commonly used passwords. If this was all I did, the drive would self-destruct after 10 trials, so after each trial, I always read a randomly selected disk sector in order to prevent the drive from self destructing.

    b) Fly-By-Night hires you on a short-term consulting contract to write the firmware for the new improved CryptoThumb 8G. You, being a crook, decide you would like to earn some extra money in the future because of your unique ability to extract data from CryptoThumb drives. Suggest firmware features you could add to the CryptoThumb 8G to help you crack the security on CryptoThumb 8G drives in the future. (0.6 point)

    The central challenge is to engineer "my unique ability" into the firmware. I could, for example, make the drive save the last several passwords used into a special password file, and include a special undocumented password retrieval command into the firmware interface. The command to read back the password can be arbitrarily obscure. For example, if the drive has n sectors, consider requiring the user to write to sector number n+1234 and then read from n+4321 in order to get the password record. In effect, "write 1234 read 4321" is the password to the password recovery mechanism. You tell nobody about this, of course!

  2. Background: The CryptoThumb Key is physically identical to the drive described above, but it has different firmware. Each CryptoThumb Key holds, inside the flash memory, a unique secret key, and a unique serial number. As with the drive above, when mounted, it appears as two devices, Device A is a conventional flash drive, while device B is a cryptographic engine that offers the following services: i) it will deliver its unique serial number request, and ii) it will encrypt or decrypt a block of data with the drive's secret key. The CryptoThumb I/O driver and the CryptoThumb utility cooperate to offer secure communication services.

    Crypto-Thumb maintains a public database on the Internet that returns the public key of any CryptoThumb drive when given the serial number of that drive. The CryptoThumb communications tool operates as follows: Given two computers, each with a CryptoThumb Key plugged in, with a drivers and support tools installed, the users create a data link between the two computers over the Internet.

    The CryptoThumb communications tool then begins the creation of a secure authenticated communications channel between the machines as follows: First, the two computers exchange the serial numbers of their thumb drives. Then, each machine gets the public key of the other from the CryptoThumb server.

    a) What is the security benefit of having the CryptoThumb do the encryption and decryption itself with the secret key instead of merely delivering the key to the user? (0.6 point)

    The user cannot extract the secret key from the drive. Therefore, the user cannot lose or accidentally reveal the secret key. If the drive documentation is honest, this means that the only way for the user to extract the secret key would be to encrypt a large number of messages and, by trial and error, try to find a key that produces the same cyphertext when given the same plaintext. If the key size is sufficiently large, this will be practically impossible.

    b) Suppose the security of CryptoThumb's data base server was compromised. What threat would this pose to a user of the CryptoThumb Key? (0.6 point)

    It would be possible for the attacker to masquerade as some legitimate user. Once the Carol, the attacker has substituted her public key for Bob's, then Alice might think she is communicating with Bob because she is using Bob's public key, when in fact, she is communicating with Carol. The data channel from Alice to Carol is, of course, secure, but the attempt to use cryptographic authentication fails.

    c) User X using CryptoThumb Key Kx on computer Cx wants to send a secure authenticated message M to user Y using CryptoThumb Key Ky on computer Cy. Note that CryptoThumb Key Ki holds private key KiPrivate and serial number KiNumber. The CryptoThumber server maps KiNumber to KiPublic. Which of the 4 processors encrypts or decrypts the message with what key in order to transmit the message from X to Y. (0.6 point)

    The processor on Cx encrypts with KyPublic

    The processor on Kx encrypts with KxPrivate

    The processor on Cy encrypts with KxPublic

    The processor on Ky encrypts with KyPrivate

    d) All CryptoThumb drives delivered by Fly-By-Night are identical. They are then plugged into a USB slot on CryptoThumb's database server, one at a time, by a robotic mechanism. This assigns them their unique ID and secret key. You are worried that CryptoThumb might not be honest. What threat does this pose? Is there any way that the folks at CryptoThumb could convince you that they were not threatening your security if you rely on their drives? (0.6 point)

    Their database server could retain secret records of the secret keys stored on each drive.

    They should not use their database server for this job. Instead, CryptoThumb should use a dedicated computer to assign IDs and secret keys to the drives. This computer must not have any network connections and must be isolated from all possible communication channels. Witnesses should be free to observe the initialization process, and at the end of initializing one batch of drives, the entire computer system used for that initialization should be destroyed to prove to the customers that CryptoThumb retained no records of the secret keys. This proof is extraordinarily difficult to make convincing, even if dynamite is used for the destruction.

  3. Background: A stage in a mix net operates by decrypting a batch of messages with some key and then sorting the output messages in order to prevent the association of the encrypted message with the decrypted message. Typically, each message input to a mix net has been encrypted with several keys, and the mix net includes a corresponding number of stages, each with its own decryption key.

    Typically, public key encryption is used with mix nets, so each message is encrypted with the public keys of all the mix-net stages, and the stages apply the private keys.

    a) A large industrial plant has decided to replace their old wood suggestion box with an Internet-based suggestion box using a 4-stage mix net to assure anonymity. The plant is unionized, and relations between the union and the management are very tense. Suggest who you would select as key custodians in order to assure everyone that the suggestions are actually anonymous. (0.7 points)

    Half of the custodians should be union representatives, and half should represent management. The hope is that union and management will not cooperate to violate the anonymization offered by the mix net. It might help to have one representative who is an outside member of the board of directors (who owns no stock), one who is directly involved in corporate management, one who is a union official, and one who is an employee but not a union member. The whole idea is to have the different key custodians sufficiently different that they are unlikely to cooperate to violate anyone's privacy.

    b) The stages for the 4 mix-net stages was purchased from a local computer dealer, and recently, both management and union officials have recently begun to suspect that someone is eavesdropping on the suggestion box and blackmailing people based on the content of their messages. Suggest what might have happened. (0.7 points)

    Someone at the computer dealer may have inserted something in the mix-net stages to save and copies of the keys for his own use. He then takes the public copy of the encrypted suggestion box, decrypts the suggestions without preserving anonymity, and then blackmails the authors of suggestions that contain content that either the union or management might consider dangerous.