Fwd: Re: Fwd: Re: FH radios [Dave Emery] [Vaughan Pratt]
-----BEGIN PGP SIGNED MESSAGE----- I forwarded a cypherpunks message to technomads, where it got a killer response, so I'll bounce it back to Cypherpunks... Stig - ------- start of forwarded message (RFC 934 encapsulation) ------- From: Vaughan Pratt <pratt@cs.stanford.edu> To: technomads@UCSD.EDU Subject: Re: Fwd: Re: FH radios [Dave Emery] Sender: pratt@cs.stanford.edu Date: Tue, 26 Dec 1995 12:00:43 -0800 Message-Id: <199512262000.MAA23334@Coraki.Stanford.EDU> In-reply-to: Your message of "Tue, 26 Dec 1995 07:07:00 PST." <m0tUayp-0006F0C@hackvan.com>
Thus in a frequency-hopping radio you can push the retuning (read RF phase-locked loop) technology to its limit and build transmitters and receivers around them. These typically hop in the order of 100 times a second. The adversary has to find the uncorrelated signal very quickly indeed *and* have PLL technology at least as good as yours to recover anything from it. Finding the signal generally means listening to all frequencies at once, requiring huge amounts of hardware parallelism and/or realtime computing power. Once you throw ten or so radios onto the same band, it's no longer any use looking for the strongest signal, making that approach useless.
This is nowhere near the limit of the technology. 15 years ago, I was working on PLLs that would stabilize within a couple degrees of final phase within 3.5 microseconds. That permits you to do useful work at 100,000 hops per second.
There is also a newer technology called direct digital synthesis or DDS that works by accumulating phase (adding to the previous value) each tick of a high frequency clock in a register at a rate determined by the contents of another register (the value here sets the frequency) with the upper bits of the accumulated phase being used to address a sine/cosine lookup table rom which in turn feeds digital output values into a D/A converter. The output of the D/A converter is a sampled approximation of a sine or cosine wave at a frequency set by the increment register. The sample rate is set by the high frequency clock rate.
This is all wishful thinking. A 26-MHz wide channel such as 902-928MHz has a channel capacity of 2*26 Mbs or 6.5 megabytes/sec. So if someone can tell *that* you are transmitting somewhere within that channel then they simply record *everything* at that data rate in the entire channel, your transmission and everyone else's, for the necessary time. A $600 3.5Gb Sequel drive can record a ten-minute transmission; then the eavesdropper can use one Pentium or two dozen, budget permitting, to extract your message from that data. If all you are doing is frequency hopping or spread spectrum, reconstruction is a very undemanding algorithmic task, and one Pentium should be able to reconstruct your signal the same day, two dozen the same hour.
But to get back to the original point of this thread - while such techniques are possible (as is full hard encryption), it is my understanding that actual conusmer 900 mhz digital cordless phones that use frequency hopping use a very limited set of frequencies and a small set of fixed hopping patterns and don't hop very fast.
Hopping speed is almost completely irrelevant to the computational complexity of this problem.
When the brand of cordless phones that most emphasizes security from eavesdropping in its point of sale advertising display is the one that uses open FM with simple speech inversion you know there is something wrong, particularly when the company that makes it is a pioneer in really secure digital speech over handheld radios (and a big governmeent contractor).
To put it mildly. You can never overestimate the cost of decryption. What looks expensive enough today to decrypt can plummet by orders of magnitude on alarmingly short notice. We used to think TCP was mildly secure until easily installed sniffers became freely available on the internet that would reconstruct a telnet connection and print out the first 100 characters, making it child's play to extract passwords. If you think that you are secure because the effort of an attack seems on the high side, bear in mind that the tasks in a systematic attack can by definition of "systematic" be programmed, greatly easing the attacker's task. And once programmed, the program can be distributed to all and sundry on the internet. If a given level of cryptographic strength seems adequate for a message, add several orders of magnitude and maybe you'll be lucky. I know of only two really satisfactory places to hide information worth hiding: combinatorial search space (read: real encryption such as DES or RSA, with a hefty key), and the real world, which as a search space is approximately the size corresponding to a combinatorial space encrypted with a 256-bit key (i.e. the world seems bigger than 128 bits and smaller than 512). The latter is distributed in space-time and frequency (momentum-energy); if you consider only space-time or only frequency the universe looks like only a 128-bit hiding place in either case. Both together give you 256 bits (very approximately, that's a very round binary number). Vaughan Pratt - ------- end ------- -----BEGIN PGP SIGNATURE----- Version: 2.6.2 Comment: Processed by Mailcrypt 3.3, an Emacs/PGP interface iQCVAwUBMOCS5khaKuRiAqcVAQEJEAP/WNqKrjrGk5LpYt5fw70BtFYZEIMqkBzu TQscTmoK2sSOeI9yjxmOp8aQhArLpOdN0ZQgfwkuelfV+/n73ms3hMV+JIDOvuFx hirE1iBvZDMgEPX1BdyP94Me13a1f8mBKTTG1cPLIYKLSTZ1tmQ/MVI0EYN9H16U AETV7FJilvM= =l+fI -----END PGP SIGNATURE-----
This is all wishful thinking. A 26-MHz wide channel such as 902-928MHz has a channel capacity of 2*26 Mbs or 6.5 megabytes/sec. So if someone
That is not what Mr Shannon says, Shannon's law relates date rate, bandwidth and signal to noise ratio - the "channel capacity" of 26 mhz of spectrum is determined by the signal to noise ratio in the 26 mhz channel and ranges from much less than 26 mbs to several times that rate depending on the signal to noise ratio (and of course how clever the modulation technology is at exploiting it). Witness a 28.8 kb modem which stuffs 28.8 kb into less than 3.2 khz given about 32 db gross SNR. But more significant to the predection recording technique you are talking about is how many samples a second it takes to reproduce information in the 26 mhz bandwidth. Crudely, as a rule of thumb the Nyquist criterion would suggest that you need to sample at twice the highest frequency (or 26 mhz if you downtranslate to DC). This means 52 megasamples per second. Now depending on how much junk there is in the 902-928 mhz band at the location of interest and how far below the other signals the signal of interest is, you might be able to get away with 8 bit samples (providing about 35 db dynamic range) but would probably need more bits than that for things to work reliably. Say 12 bits (72 Mbytes sec) or 16 bits (104 Mbytes/sec), Yes, perhaps compression could buy you back some of that, but you are still realisticlly talking about recording somewhere between maybe 20 and 100 Mbytes/sec. The low end of this range is about the upper limit of present day high performance disk system bandwidth. So you are not talking about a simple configuration with off the shelf disks and controllers (unless you run several in parallel). And one minute of audio gobbles up way more than a gigabyte, or less than 2 minutes per $K of disk cost. And that assumes some compression.
can tell *that* you are transmitting somewhere within that channel then they simply record *everything* at that data rate in the entire channel, your transmission and everyone else's, for the necessary time. A $600 3.5Gb Sequel drive can record a ten-minute transmission; then the eavesdropper can use one Pentium or two dozen, budget permitting, to extract your message from that data. If all you are doing is frequency hopping or spread spectrum, reconstruction is a very undemanding algorithmic task, and one Pentium should be able to reconstruct your signal the same day, two dozen the same hour.
I will agree that such techniques can be used, and am well aware that they have been used for the last 25 or so years by the NSA and other like organizations for handling this kind of problem (originally in the HF radio spectrum for finding and reading covert burst transmissions - at least so I have heard).
But to get back to the original point of this thread - while such techniques are possible (as is full hard encryption), it is my understanding that actual conusmer 900 mhz digital cordless phones that use frequency hopping use a very limited set of frequencies and a small set of fixed hopping patterns and don't hop very fast.
Hopping speed is almost completely irrelevant to the computational complexity of this problem.
I agree in general, though the degenerate case of very slow hopping permits of some simplifications and speedups since demodulating bits between hops can be done with less computation per sample than estimating where the next hop frequency is when it is unknown. And a phone that slowly hops in a fixed simple pattern onto a small number of channels can be demodulated by very simple approaches indeed, including much less sophisticated and costly ones than fast DSP of wideband sampled channels.
You can never overestimate the cost of decryption. What looks expensive enough today to decrypt can plummet by orders of magnitude on alarmingly short notice. We used to think TCP was mildly secure until easily installed sniffers became freely available on the internet that would reconstruct a telnet connection and print out the first 100 characters, making it child's play to extract passwords.
I must say that I was not amoung those who ever thought that TCP was secure, perhaps because I have spent too much time looking at packet dumps from protocol analyzers and bus traffic on logic analyzers. And even the oldest and slowest systems could reconstruct TCP - it was not a leap of system technology at all, but a leap of hacker application skills and awareness. I hate to even whisper the other places in the fragile web of our infrastructure that are vulnerable to intelligent attack ... there are many unexploited holes left even as we plug some of the obvious ones. The good thing is that people are begining to think about them.
If you think that you are secure because the effort of an attack seems on the high side, bear in mind that the tasks in a systematic attack can by definition of "systematic" be programmed, greatly easing the attacker's task. And once programmed, the program can be distributed to all and sundry on the internet.
That I agree with and think the current rash of sophisticated hacker tools in the hands of relatively unsophisticated kids who could in no way have created them proves your point well.
If a given level of cryptographic strength seems adequate for a message, add several orders of magnitude and maybe you'll be lucky.
I wouldn't consider hopping or spread spectrum cryptography. Historically they have been viewed as techniques for avoiding jamming and interference and sometimes also for making signals harder to find rather than as information security techniques. Their use in cordless phones is primarily to aviod interference from other users of the 902-928 band and not for security.
I know of only two really satisfactory places to hide information worth hiding: combinatorial search space (read: real encryption such as DES or RSA, with a hefty key),
I think we all agree that security by obscurity is not real security at all. But even the security of mathematical crypto is mostly unproven as of yet - we merely think things are difficult to compute because we don't know an easy way to do it, not because there is a clear proof that is true. Dave Emery
That is not what Mr Shannon says, Shannon's law relates date rate, bandwidth and signal to noise ratio - the "channel capacity" of 26 mhz of spectrum is determined by the signal to noise ratio in the 26 mhz channel and ranges from much less than 26 mbs to several times that rate depending on the signal to noise ratio (and of course how clever the modulation technology is at exploiting it). Witness a 28.8 kb modem which stuffs 28.8 kb into less than 3.2 khz given about 32 db gross SNR. Oops, mega*samples*, not megabits, how embarassing. I agree with your numbers, I was low by an order of magnitude or so on the quantity of data one would need to examine to reconstruct the message. But now that I think about what 902-928 MHz looks like in practice, I think I underestimated how hard things could get. If you're just trying to track a frequency-hopping signal where the rest of the power in the band is some mix of Gaussian noise and non-hopping signals, the carrier should be clearly visible as a spike hopping around in the band. As soon as you have two or more frequency-hopping signals however, keeping track of which carrier is which as they hop around looks *much* harder. If they hop at discernibly different times then you can correlate a carrier that disappeared with the one that appeared elsewhere at the same time. This easily described and implemented approach breaks down when two or more signals hop at the same time. Here you might try to associate some sort of signature with each signal to allow you to pair up the new carriers with the old, but you'd have to know more about the situation to say what signatures would be good. Similarly a single spread-spectrum signal should be easy to pick out, but multiple such sounds like an even bigger headache than multiple hoppers. But even the security of mathematical crypto is mostly unproven as of yet - we merely think things are difficult to compute because we don't know an easy way to do it, not because there is a clear proof that is true. Yes, this is a very important point (but presumably an obvious one to cypherpunks, maybe I should subscribe). Worse, even if we *could* prove a certain protocol secure, the proof will typically apply only to the protocol and not to any particular message transmitted using that protocol. There is a very big difference between proving the absence of a fast decryption algorithm for a given encryption scheme and proving that every message so encrypted is secure. One might call this distinction existential security vs. universal security. A universally T-secure channel is one for which every message is secure from all T-bounded attacks (algorithms taking time at most T expressed as a function T(n) of the length n of the message). An existentially T-secure channel is one such that for every T-bounded attack there exists an infinite set of messages all of which are secure from that attack, though not necessarily the same messages as you vary the attack. (As a practical matter it would be more useful to replace the function T by a fixed long duration such as a googol seconds, provided this could be achieved with messages of size at most say a kilobyte, a point of view advocated by e.g. Leonid Levin. This requires taking the state-symbol product of the computational model into account when measuring computational complexity since constant factors can no longer be neglected; here Kolmogorow complexity is a particularly natural setting. This still only addresses algorithmic attacks; for security against hardware attacks one should also appeal to limits set by physical constants like c and h-bar.) The danger is that someone will eventually demonstrate existential security for a protocol, the proof will as usual be trumpeted in the New York Times, and it will be interpreted by many as proving universal security. An intermediate notion is that of a uniformly existentially secure channel: there exist some messages secure from all attacks. But if those messages can be efficiently identified then such a channel can be converted to a universally secure channel simply by only transmitting secure messages. Modulo the identification problem, this shows that it is no easier to come up with a uniformly existentially secure protocol than a universally secure one. With a few exceptions, arising in e.g. quantum cryptography, we don't even have existentially secure protocols yet, let alone universally secure ones. Vaughan Pratt
participants (4)
-
Alan Horowitz -
Dave Emery -
stig＠hackvan.com -
Vaughan Pratt