Re: What's Wrong With Content Protection
John --
Great essay... thanks for replying at such length!
I'm going to decline your (perhaps rhetorical) invitation to provide
a devils-advocate counter-argument, because I'm not the right person to
do so; I am far too liberal in my own views to be a fair representative
of the "dark side". In any case, I was asking more for an education
(which you have generously provided) than an argument.
Cheers,
Ron Rivest
Re: key agility and IPsec
Steve -- Don't your statistics support the argument that key agility is *not* likely to be terribly important by itself? With a cache capable of storing only 5 key setups, you get at least a 75% hit rate, by your statistics. This effectively reduces key setup time by a factor of *four*, making it really second-order compared to the bulk of the encryption work to be done. Depending on the algorithm, a cache for 5 key setups is pretty minimal. For example, a setup key for RC6 requires only 176 bytes; a kilobyte of RAM would easily do for a five-key cache. I like your miss-rate statistics, but feel they support better the argument that ``key agility is not terribly important by itself'' rather than the statement ``key agility is terribly important.'' Cheers, Ron
Key agility
Hi Steve (Bellovin) -- Good to see you again at AES3. I want to respond to your comments about key agility that you made at AES3, and also in your note posted here at "[EMAIL PROTECTED]". While key agility may be very important for some applications (e.g. ATM networks), and while more key agility is clearly better than less key agility, I must say that I don't quite buy the argument you made at AES3 regarding its importance for IP traffic. If we are talking IP traffic (as for VPN's---your example), then what we care about is the distribution of packet sizes. You mention that many packets are very small (40--64 bytes), which is true, and then "conclude" from this that key agility is particularly important for such IP traffic. I did a little research into Internet packet size distributions. The common folk theorem is that "more than half the `packets' are mice, but more than half the `payload' are elephants" It is indeed the case that are many small packets, but the average packet size is nonetheless quite large. The most authoritative reference I could find is "Wide-Area Internet Traffic Patterns and Characteristics" (Extended version) http://www.vbns.net/presentations/papers/MCItraffic.ps (shorter version in Nov/Dec 1997 issue of IEEE Network) The authors conclude (section 6) that -- "About 40% of all packets are 40 bytes." but -- "Average packet sizes vary from 175 bytes to more than 400 bytes." Their figure 4a suggest that the average packet size they observed may be around 300 bytes. Suppose we accept this figure of 300 bytes as an average packet size. This amounts to about 19 AES blocks. If an AES key setup (subkey generation) takes as much time as k encryptions, then key setup incurs a relative overhead overall of only k/(19+k) For example, the Weaver et al. AES3 paper (on FPGA implementations), gives a latency for RC6 of 102 cycles for encryption and 264 cycles for subkey generation. An average packet of 19 blocks would take 264 + 19*102 = 2202 cycles. The additional overhead for subkey generation is only 264/1938 = 13.6% While this is nonzero, it is certainly not a killer, and no cause for alarm. (Moore's Law currently gives us about 1% a *week*...) This argument gets more complicated if you consider various pipelining modes, but I think the point is made. * Conclusion: even though most packets are small, the fact that the* * average packet size for Internet traffic is nonetheless relatively * * large means that the average computational overhead for subkey * * generation need not be terribly large, even if subkey generation is * * relatively slow compared to encryption/decryption. * I also note that the other statistics I could find seem to indicate that the average IP packet size is *increasing* with time. Comments? Have I overlooked something? Cheers, Ron Rivest
Average packet size (math)
Steve -- To make the argument clearer (since I received an inquiry about it): (total work) = (setup cost per packet)*(total number of packets) + (encryption cost per byte)(total number of bytes) for any data stream. Thus: (work/byte) = (setup cost per packet)*(total number of packets)/(total number of bytes) + (encryption cost per byte) = (setup cost per packet) / (average number of bytes per packet) + (encryption cost per byte) by which we see that it really is the *average* packet size that matters, not the minimum, mode, or median... Cheers, Ron
Export control of Java VM ??
Here's a thought exercise: What happens if someone applies for an export license for a Java Virtual Machine, which he intends to use as an "encryption routine"? The idea (which is not new) is that a Java program (Java byte code) would be the "key" for the encryption. It specifies how to turn the input message into the output plaintext. Thus, the VM is doing the encryption work as specified by the byte-coded "key". If a license is required to export Java VM's, there is obviously a huge problem. If no license is required for exporting a VM for this purpose, then export controls are effectively dead. If they say, ``The VM is OK to export, but your `keys' are really programs, and require export approval'' (which is the sensible response) then we see that implementing the export regs requires the ability to distinguish ``keys'' from ``programs''. This gets into gray areas very quickly. Why is not a DES key a "program" that is interpreted by the DES engine? What distinguishes repeated substitution and permutations of the usual crypto sort from a ``Post tag'' system (*) which does substitutions and rotations, and is computationally universal? I note that in TwoFish the substitutions are key-dependent, and so correspond closely to have a set of Post tag rewrite rules (i.e. an arbitrary program) as the key. Does the proper interpretation of the export regs means one should apply for export control approval on a key-by-key basis? (There might be some who would like this...) If no per-key approval is needed, then I don't see why one can't distribute code that embodies a fixed transformation procedure, since this is really a "key" rather than a "program". That is, the distributed specifies a single transformation out of a large universe of possible transformations. Thus, a routine that computes: y = AES(M,k0) for transforming a message according to some fixed 256-bit AES key k0 is really more like a key (it is k0 in another representation) than it is like a general-purpose encryption routine. Of course, it may (or may not) be easy to modify such distributed code to handle arbitrary keys (;-)) Food for thought... Cheers, Ron Rivest --- (*) A Post tag system has a number of rewrite rules of the form L_i -- R_i where L_i and R_i are strings over some alphabet (e.g. binary). As long as the prefix of the input matches some L_i, that L_i is removed from the beginning of the input, and the replacement R_i is added to the end of the input.
The Beer Bottle Cipher (some fun summer reading for you...)
The Beer Bottle Cipher
Ron Rivest
6/30/99
Last week an MIT student hacker broke into the famous Yale University
secret drinking society known as "Skull and Bones". He made a
startling discovery that has implications for national security,
saloons, and camp counselors nationwide.
What he discovered gives a surprising explanation for the origin and
meaning of the well-known drinking song "99 Bottles of Beer on the
Wall." The song, familiar to many, starts with the verse:
99 bottles of beer on the wall,
99 bottles of beer.
Take one down,
Pass it around,
98 bottles of beer on the wall.
Successive verses are the same, with the numbers reduced by one each
time. The song ends (sadly, but in glorious harmony) with "No bottles
of beer on the wall".
Apparently, this drinking song describes an encryption procedure used
by Skull and Bones' members to protect sensitive information. The
procedure, called the "Beer Bottle Cipher," was devised in the early
1700's by a mathematically-inclined Skull and Bones member. The song
was crafted as a mnemonic for the procedure.
The MIT student discovered a yellowed manuscript in the SB vault
describing the origin and meaning of the song. ("Lock-picking that
vault was a piece of cake," the student was reported as saying.)
The Skull and Bones society uses the Beer Bottle Cipher to protect
its most valuable information. For example, it protects embarassing
personal secrets revealed by new members at their initiation ceremony.
(Details of the initiation ceremony, such as whether it is actually
held in the nude, as has been reported, were not described in this
manuscript.)
The MIT student has anonymously posted a copy of the manuscript on the
Net. This note gives a technical overview of the cipher.
This discovery may have implications for the current congressional
debate about encryption policy, since current export policy would
now prohibit the singing of this song in the presence of foreigners.
(In recognition of this development, the U.S. Navy has just instructed
its sailors to begin the song with 56 bottles of beer rather than the
conventional 99 bottles of beer when they are in a foreign port, or in
the presence of foreigners. And Louis Freeh is rumored to be asking
Congress to pass a constitutional amendment banning the song altogether.)
We now give the encryption procedure itself.
Suppose we start with "n bottles of beer on the wall". Imagine that
this row of bottles holds an n-digit number---each bottle holds one
decimal digit. (Imagine the bottles lined up left to right, with the
left-most bottle holding the most-significant digit.)
The plaintext to be encrypted is first represented as a number, using
two bottles for each letter (A = 01, B = 02, and so on). A "space" is
represented as 00. Thus, the secret "BALD MOTHER" would be
represented by the number 0201120400131520080518, using 22 bottles.
If, as in this case, the plaintext needs fewer than 99 bottles, then
it uses just the right-most bottles, and the left-most bottles hold
zeros, so the total number of bottles is 99. (For longer secrets,
start out with more bottles, and sing more verses.)
There is also an encryption key, known as the "skull". The skull is a
long secret number known only to the president and vice-president of
the society. (George Bush (senior) is believed to have served as an
SB president, which may help explain his later political successes.)
In addition, there is the "table", which is where the "empties" go.
That is, when you "take one down, pass it around", one bottle is taken
off the wall (from the right end) and put down at the right end of the
row of empties. In the encryption procedure the bottles on the table
are not really empties, since they still contain digits, and the
actual procedure is a bit more complicated.
Anyway, you start with n bottles of beer on the wall holding the
plaintext and end up when the song is over with n empties on the table
holding the ciphertext.
The procedure is complicated enough that you probably should not be
drinking beer when you try to do it. The song helps you keep on
track throughout.
Once you have got set up to encrypt, with the plaintext on the wall,
skull in hand, and table empty, you just sing the song. Each phrase
in the song tells you exactly what to do next. The four phrases are:
"k bottles of beer"
"on the wall"
"Take one down"
"Pass it around"
Each phrase has a meaning, instructing you how to encrypt, as follows:
"k bottles of beer"
-- First you take the left-most bottle of beer on
the wall and move it over to the right-most end.
