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

> 	That is not what Mr Shannon says,  Shannon's law relates date

   That's Dr Shannon to you, kid.....