Solution to Assignment 1

The real VCRplus+ decoding scheme was broken by Ken Shirriff, Curt Welch, and Andrew Kinsman, at least for codes of up to six digits.  They wrote a paper describing how they did it.  Here is a summary of their method, adapted to account for the (minor) differences in terminology between our assignment and reality.

1. First, they examined the one-digit codes and determined completely how the decoding algorithm handled them.  When the code has one digit, the two hardest parts of the decoding algorithm are taken out of the picture, since NoMod.multLoop maps every one-digit number to itself, and the offsetLoop code always gets zero as its input.  By trying the one-digit codes in various months and years, they reverse-engineered the computation of the date, channel, and table index.
2. Next, they tried the two-digit codes.  In this scenario, the only new element was that the MultLoop code came into play.  They correctly guessed that there was some mystery preprocessing step going on before the rest of the computation took place.  Since they understood most of the decoding algorithm, they were able to work backwards from the day, channel, and table entry to figure out what the output of the mystery step was.  They determined that the mystery step depended only on the code and not on the month or year.  They then built a table that showed, for each two-digit code, what the output of the mystery preprocessing step was.  From that they figured out that the output of the mystery step was (almost always) the NoMod product of the code with the constant 31.  There were a few exceptions, but those were all cases where the output would have had one digit; a little more trial and error determined the NoMod.multLoop code.
3. Next, they moved on to three-digit codes.  The easiest hypothesis was that the same algorithm as in the two-digit case was being applied.  They only missing piece was what the next digit of the NoMod multiplication constant was.  This was easily determined.
4. When they moved on to four-digit codes, the offsetLoop code came into play and things got more complicated.  They observed, though, that the day usually depended only on the last three digits of the code, with a few exceptions.  This led them to conclude that the day depended only on the last three digits of the NoMod.multLoop computation.  By looking at the exceptions where the day was unexpected, they figured out which codes caused NoMod.multLoop to loop more than once.  This told them which codes caused the multLoop result to have a leading zero after the first iteration, and from that they figured out the fourth digit of the NoMod multiplication constant.  Now they knew the entire output of the NoMod.multLoop computation, and that allowed them to determine the inputs to the offsetLoop computation.  They then broke the offset loop computation by trial and error.
5. Moving on to five and six digits, the main challenge was to determine the fifth and sixth digits of the NoMod multiplication constant.  They did this as in step 4, by seeing which codes led to unexpected day values, thereby determining which codes caused the first iteration of NoMod.multLoop to generate a value with a leading zero.
6. Finally, they turned to the seven- and eight-digit codes, which they were unable to figure out.