COS 496: Information Security

Spring 1999

General information
Schedule
Homework

SOLUTION AVAILABLE

Assignment 1: Breaking a Cryptosystem

Your task in this assignment is to break a cryptosystem, or at least to learn what you can about how it works. The system in question is a modified version of the VCR Plus+ coding scheme. (In other words, the story below is slightly fictionalized to make this a better assignment, and I have slightly simplified the actual VCR Plus+ cryptosystem to make it a bit easier to break.)

VCR Plus+

VCR Plus+ was a product designed to make it easier to program your VCR. The product itself was about the size and shape of a typical remote control. When you first bought it, you would tell it what kind of VCR you had, and it knew how to control most common VCRs by emitting infrared signals, as the VCR's own remote control would do.

The other part of the VCR Plus+ system was a coding (or encryption) scheme that assigned an eight-digit (base 10) numeric code to any (starting time and date, duration, channel number) combination. The TV schedules in newspapers would print the VCR Plus+ code for each show next to that show's listing, and a person could tell VCR Plus+ to record a show by simply entering that show's code number into the VCR Plus+ device. The device knew how to decode the code numbers, and it had a built-in clock, so it knew when to start and end the recording.

Once you told VCR Plus+ that you wanted to record a show, VCR Plus+ waited until the show came on, and then issued the appropriate infrared commands to turn on your VCR, set it to the correct channel, and start recording. When the show ended, VCR Plus+ would issue infrared commands to stop recording and turn off your VCR.

The VCR Plus+ company made money two ways. First, they sold the VCR Plus+ device itself. Second, they sold newspapers the right to print the codes. Both parts of the business model relied in part on the inability of third parties to figure out the algorithm for mapping between a (starting time and date, duration, channel number) combination and the corresponding numeric code. As long as the algorithm wasn't broken, nobody could clone the VCR Plus+ hardware, and newspapers couldn't figure out the codes on their own so they had to pay in order to learn the codes.

If the cryptosystem was broken, this would likely cost the VCR Plus+ company a lot of money. In fact, the cryptosystem was eventually broken.

The VCR Plus+ Cryptosystem

The cryptosystem is a "black box" that takes three inputs:

the year, coded as a two-digit integer (i.e. 1998 is represented as 98),
the month, coded as an integer with 1 for January and 12 for December, and
the numeric code from the newspaper

The cryptosystem produces the following outputs:

the year in which to start taping, coded as a two-digit integer (this output is identical to the year input),
the month in which to start taping, coded as an integer (this output is identical to the month input),
the day of the month in which to start taping, coded as an integer,
the TV channel to tape, coded as an integer, and
an index into a table that says the starting time and duration of the show.

[To simplify your life, we'll assume you get to see the table index. In real life, you'd only see the result of the table lookup and you'd have to deduce the table's contents.]

The cryptosystem had two objectives. First, it was supposed to be hard to break. Second, the codes for popular shows (such as those with small channel numbers and small table indices) were supposed to be shorter, on average, than the codes for less popular shows; this would make it easier, on average, for customers to enter the codes for the shows they watched.

Tools

As a tool to help you analyze the VCR Plus+ system, we have provided you with Java code that allows you to have various combinations of year, month, and day run through the decoding process. You can download the code from here. It does not do the decoding itself but rather connects across the net to a server that does the decoding.

You can use our code in two ways: you can manually enter inputs and observe the outputs, or you can write a program that decodes a sequence of values and either outputs the results for you or looks for patterns itself. Do whatever makes sense to you. If you do succeed in breaking the cryptosystem, you will probably break it little by little in a series of steps in which you learn progressively more about how it works. If you don't break it completely, don't worry; just write up whatever you have figured out about how it works.

Hints

The cryptosystem is not built on standard crypto algorithms like DES or RSA. So don't worry if you don't know about such systems, and don't spend a lot of time looking at crypto textbooks. We'll cover these algorithms later in the semester, but you shouldn't need them now.

It helps to explore the space in a systematic way.

One general and frequently useful trick in cryptanalysis is called "differential cryptanalysis." The idea is to change the input slightly and see how that small change propagates through to the output. By doing this repeatedly, you might be able to learn something about which parts of the output are affected by which kinds of changes in the input.

Since differences in the length of the input are supposed to be correlated with differences in the characteristics of the output, the behavior of the algorithm might change depending on the length of the input. Maybe some input lengths are easier to analyze than others.

NEW HINTS

We're giving you two new hints, as of Tuesday, February 9.

First, here is Java source code for the NoMod class, which is used as part of the decoding process. The first step in decoding is to take the code that is input and run it through the NoMod.multLoop method. Here is the first line of code used in the decoding process:
int afterMult = NoMod.multLoop(new NoMod(code), NoMod.DecodeConst).toInt();
The afterMult variable is then fed into the remainder of the decoding process.

Second, you should note that the day output is the easiest one to reverse-engineer. In other words, it might be a good idea to focus first on determining how the day is calculated. The day then serves as input to other parts of the decoding logic.