minow@decvax.UUCP (Martin Minow) (05/08/87)
I just bought a very nice 20 Mbyte one-time pad for my [imaginary] encryption device. I was suprised to discover that it had another function. When placed in a CD player, it creates about an hour of very nice music. Since these disks are distributed world-wide, (and the bits are easy to pull off the disks), it seems that two people could set up a reasonably secure communications path by having a common disk library and a (secretly transmitted) algorithm for selecting the disk/track/index for a new message. This could be as simple as multiplying the date by the phase of the moon and dividing the result by the Dow Jones average. Without knowledge of the disk library and selection algorithm, an intruder would have a tough time reading the traffic. (By the way, the raw cd bits have high redundancy. There are ways to turn this into suitably random data. Even if you tossed all but the low-order bit of each sample, you still get 1.2 Mbytes of pretty random data.) Have I forgotten something? Martin Minow decvax!minow The above does not represent the position of Digital Equipment Corporation
gwyn@brl-smoke.UUCP (05/08/87)
In article <57@decvax.UUCP> minow@decvax.UUCP (Martin Minow) writes: >Have I forgotten something? What you described amounts to a "book code". Unlike real books, CDs are quite amenable to computerization. While this is an advantage for the encryptor, it is an even bigger advantage for the analyst. The real problem is that, despite initial appearances, the key space is rather small. A dedicated cryppy would have a complete CD library; he would also preprocess the library to develop a file of characteristic statistical signatures so that he could relatively quickly determine which key you actually used for your message. One-time pad systems really MUST use truly random keys to guarantee unbreakability. The keys could be distributed as magtapes, CD disks, and so forth, but you need to limit distribution to just the intended communicators, not record stores. The best scheme would be to have the key automatically destroyed as it is used.
devine@vianet.UUCP (Bob Devine) (05/09/87)
I like the idea. It gave me a grin thinking that somebody from
a spook organization would have to go to a record store looking for the
latest CD by "Prince" or even "Billy and the Boingers"!
> Have I forgotten something?
One problem would be that the CD doesn't really contain random
bits. A musical note follows some rules about placement so that the
delta between bytes may be small. This gives, in essence, a psuedo-
random number because one could predict what the next value taken from
the CD might be. Repetition also reduces the randomness. Consider a
Philip Glass composition versus a selection with a wider melodic and
dynamic range.
This method is not a one-time pad. You should not reuse that part of
the CD again for a different message. A destructive read would accomplish
that but then the evidence of what part of a CD is good/bad would help
someone trying to guess what track/sectors were used for a new message.
Bob Devine
PS. What happens if the encrypted data is played backwards? :-)karn@faline.UUCP (05/11/87)
While custom-made CDs with random bits would make excellent one-time pads, using commercially available music recordings would be a very bad idea. Even if you disregard the statistical attacks that would be possible because of the high degree of correlation (non-randomness) between samples on all music recordings (with the possible exception of Billy and the Boingers), the system is not very secure. The effective "key space" is well within range of a brute force attack. Assume there are 20,000 titles available on CD (this is a guess). If each message is encrypted with the CD contents starting at the beginning of the disk, then the effective "key" (ie., the title of the disk) is less than 15 bits. You could make the effective key longer by starting at some random point on the disk and wrapping around back to your starting point. A typical CD has 60 minutes of music; this is 5 gigabits. Log2(5e9) is about 32, so you can add 32 bits to your key for a total of 47 bits. You're better off sticking with DES for the time being. There is precedent for using audio recordings to hold one-time-pad keys. The vocoder system developed for secure voice conversations between Roosevelt and Churchill in WWII used audio recordings of the noise generated by a mercury vapor rectifier. Two copies were made, the originals destroyed, and the records sent to Washington and London. Phil
viavant@ernie.Berkeley.EDU (Steven Viavant) (05/13/87)
Regarding using CDs for one time pads: Phil Karn (I think?) states that the available key length is too small, based on ~20,000 titles ~= 15 bits, plus ~5e9 bits per title => ~32 bits to use as an index into the position to begin the X-or pad operation (with wrap-around). I like his analysis, however: Couldn't the effective key-length be made (arbitrarily?) large by including extra information (bits) in the key, to be interpreted by the receiver according to a predefined protocol. For example, the key might specify CD-title (15 bits), index into starting position (32 bits), and "x" bits used as a seed for a psuedo-random number generator. The first bit of the decoding pad would be specified by the title and index; subsequent bits in the pad would be determined by "skipping" over a number of bits in the CD, that number determined by (say) the middle eight bits of the succesive iterations of the psuedo-random number generator. This would both extend the effective key-space, and diminish the effect of the undesirably large correlation that succesive bits on a CD tend to exhibit. I doubt that one would achieve the full potential secrecy of the length of key employed, but we should still get an effective key space which is exponential in the length of the key (though perhaps somewhat less than 2^(key-length)). One could also decide to cycle through several different CD titles before wrapping around (as specified in the key), if there were difficulty in coming up with a (fast) "random" number generator with a large enough period in its middle "x" bits. Steven Viavant Sign me: just curious, not a cat. Steven viavant@ernie.berkeley.edu
devine@vianet.UUCP (Bob Devine) (05/13/87)
In article <573@faline.bellcore.com>, karn@faline.UUCP writes: > [the "key space" that is used for identifying a CD in the CD one-time-pad > idea is too small for it be secure. A cracker could find CD identity.] There are ways of expanding the id field so that a large, sparse field is used. But there still exists a problem of how THAT equivalence of CD_id :: CD information is transmitted.... It's sort of like the key distribution problem for DES.