7 Homework 5A

Due:

Tuesday, 2/6 at 9PM

This assignment may be done with an approved PARTNER.

This assignment is entirely AUTOGRADED.

What to Download:

hw5a.rkt

Please start with this file, filling in where appropriate, and submit your homework to the HW5A assignment on Gradescope. This page has additional information, and allows us to format things nicely.

7.1 Problem 1

Cryptography, or the science of secret communication, is about as old as math itself. Modern cryptography was born alongside with computers, as during WWII, information was sent over radio and secure communication was critical. Machines were used in what became an arms race, where more sophisticated codes were developed using complex machinery, and at the same time, some of the earliest "computers" were created in order to break them.

One of the first, and most important, cryptanalysis (code breaking) results was done by teams at Bletchley Park, a British estate that housed one of the first machines that could conceivably be called the computer. While many were involved in the effort, including a team of Polish mathematicians, a key figure in the effort was a British mathematician and one of the pioneers of the entire field of computer science named Alan Turing. For his contributions to this early work on computation, and many other things, the highest award in computer science (our "Nobel Prize") is named the Turing award.

Despite his critical role in the effort, and ground breaking work for the field as a whole, Turing was prosecuted for homosexuality after the war, and died by apparent suicide a few years later at the age of only 41. More than a half century later, the British Government apologized for his treatment and officially pardoned him.

Much of cryptanalysis relies upon detecting patterns, and indeed, the ability to do that at scale was exactly how the Bletchley Park team was able to use machines to break the German Enigma.

"Perfect encryption" via so-called one-time pads, or the other hand, has no patterns, and thus is not vulnerable to that type of analysis, even in theory. It is, in effect, unbreakable. It relies, on the other hand, on a secret key, shared beforehand, that is as long as the message itself, which aside from limited cases, is difficult to imagine (the "Red Telephone" in movies between the US and USSR is fiction, but keys to enable this form of encryption were exchanged via embassies). Most modern cryptography, on the other hand, relies upon being able to negotiate secure communication between parties that have never interacted before (you and an online shopping website, for example).

One-time pads, however, still do have value, in that they are provably impossible to break, and we will show why that is in this problem. Further, most realistic cryptosystems, while much more complex, share elements with this incredibly simple one.

First, we will define types for bits, messages (of fixed length of six bits), and keys (of fixed length of six bits). In a realistic setting, we could translate text into bits (each letter getting a unique assignment of bits), and split our message into chunks of length six. We define contracts for "Bit" and "Message". Note that we require Key and Message be lists of length exactly 6.

The way one-time pads work is via exclusive-or (XOR). To both encrypt and decrypt, we XOR each bit in the message with a corresponding bit in the key. This should result in an encrypted message for which it is impossible to determine the original without knowing the key. We want to prove that, and we’ll do it in the following way. First, we define encryption and decryption, which use the key (which is the same length of the message), XOR’d bit by bit with the message:

Your task is to define the following property, that captures the fact that encrypt/decrypt result in perfect secrecy. It should state that for a given encrypted message and any possible original message, there exists some key that would have produced it. That means that without knowing something about the key, there is no way of knowing which message was encrypted, since for any other message, some key could have produced the encrypted message. Note that we haven’t talked much about logical exists (\exists), but if you can compute such a key, that is essentially the same thing (to be more technical, it’s very close to an existential in constructive logic). To show that you have, indeed, computed the right key, your property should use the computed key to decrypt the message and ensure it is, indeed, equal to the given arbitrary message.

7.2 Problem 2

One key source of cybersecurity vulnerabilities are "timing attacks", which work by measuring how long a particular computation takes. If the computation takes different amount of time based on different secret values, the attacker may be able to learn information about those secrets.

In this problem, we’ll consider one of the classic examples of this: matching passwords.

In order to measure time, you’ll use a particular function provided by LSL: ticks. This takes, as an argument, a zero-argument function (called a "thunk"), like, e.g.,

(lambda () (+ 1 2))

Or

(define (myfun)

(+ 1 2))

ticks will call the thunk, and will record information about how long it took, returning a natural number. What this natural number counts is the number of letters compared by string=?, which we will use as a proxy for time. Actual timing information is noisy enough that it requires collecting more data and doing statistical analysis; this gets at the heart of the problem without those extra details.

You’ve been given a function check-password that takes as input a Password, which is list of characters (as strings). (Note we have defined the contract so you can’t generate examples of Password: instead, generate String and use explode). check-password checks in against the correct password (stored as a constant). It does it by using a password=? helper that calls string=? function on each letter.

You have two tasks. First, you need to write a specification that ensures that check-password does not leak timing information. In order to do this, you should define a timing-spec that takes two different passwords (as strings that are then exploded, as shown in starter code), and ensures (using ticks) that calling check-password on both results in the same number of ticks.

Once you have that spec, you should find that the implementation of check-password is indeed leaking timing information. An attacker could use that to guess the password, as the current implementation stops as soon as it finds a character that doesn’t match, so they could try passwords starting with "a", then "b", etc, until they found one that took a little longer: this would mean they discovered the first letter. Then they would continue with the second, etc. You can try this out with ticks (but don’t have to) by trying check-password with passwords that are longer and longer prefixes of the actual password.

Your next task is to go back and fix the implementation of check-password to not reveal that information.

One requirement: you may not do this by using equal? instead of string=?. The reason for this is that we are only recording timing information for string=?, so if you bypass this by using equal?, it will (artificially) act as though there is no time consumed in string comparisons, even though there is. This doesn’t mean an implementation that uses equal? is secure! The same timing information present in comparisons for string=? is there, we are just not tracking it.

Instead, figure out how to rewrite password=? so that the implementation no longer reveals any timing information. Hint: you may need to do pointless work, which is indeed an important element of this type of security!