Previous lecture

Table of contents

Next lecture

I mentioned the fact that under the Digital Millennium Copyright Act (the DMCA) a new Federal crime was defined: "circumvention". this is crime of attempting to get around protection of digital intellectual property. Success in this attempt is not necessary for the crime to be committed -- merely attempts! There are some mitigations, such as "encryption research." However, before such research is done, notification of the copyright {holders/protectors} must be made (attempted?). Their agreement to the work need not be obtained -- merely notification. This is all rather silly. However, the person who is likely most responsible for the DVD cracking (a young man in Norway) was arrested and held overnight in jail for his activity, as was a person who showed defects in the system used for cash card transactions in France.

The discussion of DES was perhaps not as lively as I'd like. Students generally did not review the background of DES as I had asked (sigh!). I have got to make clear how participation in a discussion will (positively!) affect students' grades. We briefly looked at what DES was: a certain kind of block cipher. Mr. Radomirovic gave a short presentation on block ciphers and wrote some notes (lightly edited by me) which were not handed out [PDF|PS|TeX]. In the future, it might be interesting to have students create their "own" block ciphers in class and encrypt and decrypt. Each student could get instructions for a transposition and substitution depending on their name, for example, and pass the result on. A "round" would consist of passing the information through, say, 4 students. The exercise could be designed to allow encryption and decryption with the same key, passing information back and forth. We could also create a Maple environment for such block ciphers.

We tried to emphasize that block ciphers were basically simple, and that the cryptological complexity was achieved by repeating them (further "rounds"). The security was attained by a concatenation of permutations and substitutions. The usefulness in the real world was earned by the fact that block ciphers were fast. Block ciphers were examples of what are classically called "symmetric" cryptosystems: both Alice and Bob need to share common information (the key) to encrypt and decrypt. This sharing is different from the asymmetric system of RSA. The key determines which permutations and substitutions are used. The simplicity and speed of block ciphers make them particularly useful for lots of transactions (millions and millions each day). In the "real world", users of something like DES might exchange keys via Diffie-Hellman or RSA (a negotiation which takes some time) and then use a block cipher to communicate messages back and forth, chopping each message up into blocks of the correct length for the algorithm.

Discussion shifted to the social and political implications of the introduction of DES. Its use was originally supposed to be obligatory for certain financial institutions (those connected with the U.S. Federal Reserve System, for example). But the use began to spread, since it was available cheaply and easily, and its security was, in effect, endorsed by government agencies. It spread world-wide. Questions began to be asked. The original design was adapted from an IBM block cipher called "Lucifer" whose key size was 64 bits. The key size for DES was shortened to 56 bits, with an additional 8 bits added for "checking" (like casting out 9's). Numbers like 64 (a power of 2) are useful in computer design. The message blocks for DES were also 64 bits long. Some people questioned this change as serving the purpose of certain U.S. agencies. They could somehow "crack" DES, by exhaustive search if nothing else. The selection of certain permutations (in the design of DES: the "S-boxes") was also viewed as suspicious by some observers. Perhaps a sort of trapdoor was built into the design so that the encryption would be vulnerable to those who knew the tricks. Others remarked that such design would be foolish, and would leave the financial establishment (and others) vulnerable to any who happened to discover the trapdoor. Further mystery was engendered by the appearance of lists with "keys to avoid" (these keys, it turned out, made the system vulnerable to an attack discovered in the civilian world years later: differential cryptanalysis).

DES was introduced in about 1975 and rapidly became the most widely used cryptosystem ever. Statements were made about the high quality of its security by government officials. Others said that while there might be hypothetical vulnerabilities via trapdoors (paranoia?), DES would be vulnerable to an exhaustive search. Even fairly recent statements by officials seemed to imply exaggerated estimates of the difficulty of breaking DES via exhaustive search. In fact, special purpose machines can now break a DES message by exhaustive search within a few hours. I perhaps should have remarked that the introduction of DES seemed to have started an epidemic of paranoia about U.S. (and other?) governments "reading peoples' mail". That is, almost demonizing the NSA (e.g., the movie, "Enemy of the State").

The current official recommendation is that DES be replace by "triple DES", with three keys and three repetitions of DES. There was some discussion about whether this would be three times as much work for exhaustive search. I tried to explain that the work involved would be much much more, but it isn't clear I was successful. Again the lack of understanding of exponentiation intervened: A^3B compared to A^B and also compared to just tripling A^B.

We then briefly spoke about the AES competition: that the winner would need to work very fast, in a variety of applications, from big computers down to smart cards. The competition was open, in contrast to the selection of DES, and "peer review" was being encouraged vigorously. Most of the half-dozen finalists had substantial non-U.S. participation, also contrasting interestingly with DES. The design criteria and the entries were being openly questioned.

A paper on DES is requested within a week. I think presentations by student groups here might have been much more effective, with the stipulation that questions on some student presentations would be on the final exam!

Previous lecture

Table of contents

Next lecture