Cryptography-Digest Digest #752, Volume #11 Thu, 11 May 00 03:13:01 EDT
Contents:
Re: Request for cryptanalysis: lja1 (David A. Wagner)
Re: Why no civilian GPS anti-spoofing? / proposal (zapzing)
Re: Is Microsoft CryptoAPI's CALG_MAC really CBC-MAC? (David A. Wagner)
Re: Why no civilian GPS anti-spoofing? / proposal (Paul Rubin)
Re: Why no civilian GPS anti-spoofing? / proposal (Paul Rubin)
Re: Scary Possibility: Ticklish Chips (zapzing)
Re: UK issue; How to determine if a file contains encrypted data? (zapzing)
Re: Cipher Contest (Anders Thulin)
Re: Actually, my experience and then postings since the fall of 1999 provide an
excellent behavior study - the Game of General ... ("Felix Alton Marz")
Re: Why no civilian GPS anti-spoofing? / proposal (David Hopwood)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Request for cryptanalysis: lja1
Date: 10 May 2000 21:37:10 -0700
In article <[EMAIL PROTECTED]>,
Andru Luvisi <[EMAIL PROTECTED]> wrote:
> void lja1e_cycle(unsigned char *key, unsigned char *block, int blocksize)
> {
> unsigned char acc;
> int i, j;
>
> for(i = 1; i <= blocksize; i++)
> {
> for(j = 0, acc = 0; j < blocksize - 1; j++)
> {
> acc += key[block[(i + j) % blocksize]];
> acc = key[acc];
> }
> block[(i + j) % blocksize] ^= acc;
> }
> }
Note that there is no round-dependence, i.e., all rounds compute exactly
the same deterministic function. Thus, there are slide attacks.
But, there are also more subtle attacks. Consider encrypting a plaintext
of the form (X,X,X,..,X), i.e., one where all bytes take on the same
value. If applying the compression scheme to the input (X,X,..,X)
yields the output 0 (happens with prob. 1/256), then (X,X,X,..,X) is
a fixpoint of the round function, and thus is left unmodified during
all rounds of encryption. In other words, (X,X,X,..,X) encrypts to
(X,X,X,..,X) with probability 1/256.
These ideas can probably be extended to get a key-recovery attack.
The fix should be easy: mix a counter 'ctr' in at every round. e.g., add
unsigned char ctr = 0;
and then replace
block[(i + j) % blocksize] ^= acc;
by
block[(i + j) % blocksize] ^= acc ^ (ctr++);
Note, however, that the counter should not be reset to zero after every
cycle (every n rounds), otherwise slide attacks may still be possible.
By the way, once you make these tweaks, the question still remains how
many cycles are needed. I don't know the answer, but at least I can
say that you need more than just one cycle. There are easy attacks on
one cycle of this scheme, since you can note that given known plaintext
you can easily recover all of the F-function outputs; moreover, the
F-function inputs are all known for the first and last rounds of the
cycle, so this should be enough to recover the key[] array (certainly
in a chosen-plaintext attack, perhaps also in a known-plaintext attack).
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: Thu, 11 May 2000 05:24:43 GMT
In article <GzLR4.8958$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> zapzing <[EMAIL PROTECTED]> wrote:
> > Such as causing a plane to fly into a mountainside.
> > Yikes. We certainly don't want that to happen.
> > Why won't the fedgov let us have the anti-spoofing
> > signals to prevent such a catastrophie?
>
> This is nonsensical. Except for _very_ limited corridors, commercial
> airliners would be flying well above the highest elevation on the
> map. Since the altimeter is a mechanical device, it wouldn't be
> affected by gps problems.
>
Or if they were landing.
Then, by definition, they would start to take
their altitude down. And if they were confused
about their actual location, They might
run into a mountain at that time.
> > simply include the current time in the signature,
> > and put clocks in the little black boxes.
>
> Synchronising every reciever to the same clock without using the gps
> signal would be a nightmare. And I'm still not sure it's possible to
> timestamp an stream of data. Which brings us to the sci-crypt
> relevance. Is it possible to authenticate the route broadcast data
> traveled, rather than just the origin?
>
If you are using a public key system, then
you would include the time in the message
block that is being encrypted. Everyone
could decode and see that at least the
signal claims to have been sent at such
and such a time. And since only the
legitimate transmitters have the encoding
key, it must have come from a legitimate
transmitter. Not susceptible to a replay
attack. No Problemo.
> --
> Matt Gauthier <[EMAIL PROTECTED]>
>
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: Is Microsoft CryptoAPI's CALG_MAC really CBC-MAC?
Date: 10 May 2000 21:50:21 -0700
In article <8fdb2v$q2v$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> Schneier says that the CBC-MAC specification is the last block of a
> block
> cipher in CBC or CFB, with this last block encrypted a second time in
> CBC
> or CFB. The CALG_MAC description does not have this last block
> encrypted a
> second time.
To prevent certain attacks, one should either
(1) prepend (not append) a length field to the message before applying
CBC mode, or
(2) encrypt the output of CBC mode under an independent key.
(There could well be other defenses I don't know of, too.)
If you just use the last block of output of a standard CBC mode encryption
of the message, the resulting MAC is secure for fixed-length messages, but
insecure when the attacker can choose messages of different lengths.
For more details, see http://www-cse.ucsd.edu/users/mihir/papers/cbc.ps,
Section 5; or, http://www.cs.technion.ac.il/~erez/pra2.ps.Z
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Crossposted-To: sci.geo.satellite-nav
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: 11 May 2000 05:37:04 GMT
Roger Fleming <[EMAIL PROTECTED]> wrote:
>ObCrypto: the beginning of this thread was about the necessity of digitally
>signing GPS signals. Now according to www.tfhrc.gov, the US FAA is _not_
>proposing to allow 'plain' GPS to be used to automatically navigate aircraft,
I don't think automatic navigation was part of the scheme I saw. They
just wanted to make the AT corridors smaller based on having precise GPS
navigation available.
>because the system availability (at the necessary accuracy) is too poor, only
>about 95%. Instead they will use WAAS, an augmented GPS-like system with
>99.999% availability at 4-7m accuracy, and alarms when accuracy degrades. This
>system is still under design; if you think you have a strong case to include
>authentication features, write to the FAA!!
Good idea but I wanted to run the idea past the newsgroup first.
>For ordinary GPS, I suggest the nature of civilian GPS signals - without
>extreme modification - makes digital authentication completely impossible,
>because:
>a. the important point is not the bits in the signal (which are actually
>predetermined), but their timing, so replay attacks are what matters;
That's correct. I'm actually not sure how the military system avoids
this problem, even with an unpredictable spreading code.
>b. the signal is more-or-less cyclic, so replay attacks can include 'future'
>messages (actually from the past cycle); and
The code doesn't have to be cyclic since the receiver can be assumed
to have a fairly accurate clock. Since it's for fancy receivers (not
wristwatches) we can probably assume millisecond accuracy even without
reference to the usual C/A code.
>c. The timing errors we are concerned about are not the sort we normally
>consider in communication protocols (did this message arrive before or after
>that one? Is this message still fresh?) but of the order of a fraction of a
>bit - I don't know how to authenticate that!
It's not easy.
>OK, let's assume we can authenticate the 50 bps ephemerides signal, probably
>on a secondary channel (to provide backward compatibility).
We're talking about new carriers (L5 and maybe one other), not the existing
service. No need for backward compatibility since it's new.
>How do we authenticate timing of the 1 Mbps C/A PRN code to less than
>1 microsecond of accuracy (preferably, less than 50 ns)? Bear in mind
>that although the satellite clocks are extremely accurate, the
>receiver clocks are inherently less accurate than 1 us but gain
>accuracy by trusting this signal and locking on to it... If anyone
>can see how to solve this, speak up now! The next generation of GPS
>satellites is due to be launched in 2005. Maybe your idea could be on
>board...
One idea I've had is to selectively omit some chips from the message,
and just not transmit anything in that frame (or put it at some
out-of-sequence frequency). Exactly which chips would be omitted
would be cryptographically unpredictable but it would be on the order
of a few hundred chips per second, i.e. 0.1% of the total chip rate.
The correlator would have some special logic to record the "serial
numbers" of the missing chips. Then every few seconds the transmitter
would send a digitally signed message saying where the missing chips
were supposed to be. Perhaps the attacker could have a spoofing
transmitter receiving the real signal and re-sending it after a tiny
delay, creating artificial multipath distortion. I don't know if there's
any way around that.
One thing that occurs to me is it sounds hard to spoof GPS when the
target is an airplane, since the airplane can simply use directional
antennas that point upwards at the satellites, and attentuating any
signals coming from the ground. The spoofing transmitter would have
to be above the airplane. I don't even know how the US military plans
to deal with that when they want to jam the L1 C/A code.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
Date: 11 May 2000 05:38:31 GMT
In article <8fdg6h$vhn$[EMAIL PROTECTED]>, zapzing <[EMAIL PROTECTED]> wrote:
>If you are using a public key system, then you would include the time
>in the message block that is being encrypted. Everyone could decode
>and see that at least the signal claims to have been sent at such and
>such a time. And since only the legitimate transmitters have the
>encoding key, it must have come from a legitimate transmitter. Not
>susceptible to a replay attack. No Problemo.
The thing is, there's not exactly a message block being encrypted or
signed. It's more complicated than that, and it's not obvious that there's
a workable answer.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Scary Possibility: Ticklish Chips
Date: Thu, 11 May 2000 05:36:36 GMT
In article <8fb8jp$4q8$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Jonathan Thornburg) wrote:
> zapzing wrote:
> > Here's something to keep you awake at night:
> > What if some of the chips for doing DES etc. have
> > been made "ticklish" , that is what if some
> > sort of irritant, such as a dose of radiation
> > or an electrical input that is out of band
> > would prompt the chip to divulge its key.
>
> In article <[EMAIL PROTECTED]>,
> Volker Hetzer <[EMAIL PROTECTED]> wrote:
> > Much easier. You design a chip. You give
> > the design to a company for manufacturing.
> > Manufacturer has connections to government
> > and - your chip has an undocumented debug
> > feature triggered by a certain combination on
> > your 100+ pins or a specific fluctuation in the
> > power supply.
>
> More generally, anyone along the way can introduce hardware backdoors,
> just as anyone along the software path can introduce software
backdoors.
>
> The following (very funny) posting by Henry Spencer to the Linux-IPSEC
> mailing list from about 6 months ago makes this point quite well:
>
Yes, this is what I was asking about.
I thought that perhaps superencrypitng with
several chips would do the trick, but I can s
see that they can just be attacked from the
last chip and then going back. Your idea of
having a peer reviewed design is much better.
> ##
http://www.sandelman.ottawa.on.ca/linux-ipsec/html/1999/09/msg00240.html
>
_________________________________________________________________
>
> Re: linux-ipsec: Intel IPSEC accelerator gives 3DES protected 100Mbit
Ethernet
>
_________________________________________________________________
>
> * To: Linux IPsec <[EMAIL PROTECTED]>
> * Subject: Re: linux-ipsec: Intel IPSEC accelerator gives 3DES
> protected 100Mbit Ethernet
> * From: Henry Spencer <[EMAIL PROTECTED]>
> * From: [EMAIL PROTECTED]
> * Date: Thu, 16 Sep 1999 10:48:52 -0400 (EDT)
> * In-Reply-To: <[EMAIL PROTECTED]>
> * Reply-To: [EMAIL PROTECTED]
> * Sender: [EMAIL PROTECTED]
>
_________________________________________________________________
>
> William H Geiger writes:
> > I don't know if you still follow the CP list but we have
> > been having a long debate on the trustworthiness of Intel
> > hardware, especially their RNG...
>
> At first I thought this was pretty much a non-issue here. The
problem
> with the RNG is that it's so hard to decide whether its output is
"really"
> random. But 3DES is a deterministic transform which can be tested
against
> other implementations, so you can easily establish whether the chip
is
> really doing 3DES or not.
>
> Alas, then I got to thinking. Suppose one built a 3DES accelerator
chip
> so that, if and only if:
>
> (a) the chip is doing near-continuous encryptions at high speed, and
> (b) the keys are changing every packet or two, and
> (c) the chip detects -- via a simple mechanism like a little hash
table --
> a key which has appeared before, recently, and
> (d) this key has not been marked "compromised" in the hash table, and
> (e) an internal 16-bit packet counter is all-1s,
>
> then
>
> (!) mark the key compromised in the hash table, XOR the key with the
> string "GOTCHA, YOU OPEN-SOURCE WEENIES -- NSA RULES!", prefix it
with a
> random-looking constant bit pattern, and sprinkle the resulting bits
into
> the encrypted data, in a haphazard but deterministic pattern.
>
> This is, of course, an encryption error. But rules (a)-(e) make it
> essentially irreproducible, so it won't happen a second time (and
will be
> quite difficult to reproduce even in a test setup). Almost certainly
it
> will get written off as a random error, and the affected packet will
be
> re-processed correctly and re-sent, and all will be well.
>
> Except that an eavesdropper on the high-speed wire just looks for the
> constant bit pattern in the right places in a packet, and (almost)
every
> time he sees it, he's nabbed an encryption key.
>
> There's no limit to the complexity that can be added -- especially if
> you're willing to consider active wiretapping, with the chip going
into
> this mode only if it sees (say) an ICMP ping with the right data in
it --
> to defeat attempts to find this sort of thing on the test bench.
>
> I fear I agree with William; nothing short of peer review of the
hardware
> design makes such a device trustworthy.
>
> Henry
Spencer
>
[EMAIL PROTECTED]
>
([EMAIL PROTECTED])
>
> -
> This is the [EMAIL PROTECTED] mailing list. It
is a
> restrict-Post filtered version of [EMAIL PROTECTED]
>
_________________________________________________________________
>
> --
> -- Jonathan Thornburg <[EMAIL PROTECTED]>
> http://www.thp.univie.ac.at/~jthorn/home.html
> Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische
Physik
> Amount of all stock owned by the least wealthy 90% of America:
18%
> Amount of all stock owned by the most wealthy 1% of America: 41%
> -- Economic Policy
Institute
>
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: UK issue; How to determine if a file contains encrypted data?
Date: Thu, 11 May 2000 05:45:29 GMT
In article <[EMAIL PROTECTED]>,
Andy Dingley <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Richard Herring) a �crit :
>
> >Wouldn't help. It's possession that counts, not how you acquired it.
> >If They "have reason to believe" that it contains encrypted data,
> >the onus is on you to provide the keys.
>
> So what happens with a large jpeg, when one of Straw's minions asserts
> that it contains something steganographic (even if it doesn't) and
> you're faced with a 2 year jail sentence for refusal to provide the
> keys to something that doesn't even have them,
>
> The UK. It's the best place to do e-commerce, honest.
>
I see your point. I guess it is time
to find another country to be a part
of. At least the exchange rates are
favorable!
Here in America, they are thinking
of outlawing the science of Astronomy,
because some astronomers have taken to
tracking low earth orbit objects,
including fedgov spy sattelites. They
don't like that, so they just talk
about outlawing astronomy. So when
you find a favorable country, let me
know.
I just posted something on
tal.politics.crypto about this
recently
--
Do as thou thinkest best.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Cipher Contest
Date: Thu, 11 May 2000 06:19:54 GMT
Adam Durana wrote:
> For all of you who have been posting algorithms of your own design, you
> should really look at http://www.wizard.net/~echo/
Looks blank to me. Invisible writing???
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Hj�lmaregatan 3B, 212 19 Malm�, Sweden
------------------------------
From: "Felix Alton Marz" <[EMAIL PROTECTED]>
Crossposted-To: soc.culture.usa,soc.culture.soviet
Subject: Re: Actually, my experience and then postings since the fall of 1999 provide
an excellent behavior study - the Game of General ...
Date: Thu, 11 May 2000 01:47:50 -0500
You know this all seems like a big joke, but I have a sneaking suspicion
that this guy is only half kidding.
"Markku J. Saarelainen" <[EMAIL PROTECTED]> wrote in message
news:8fcdm4$p9l$[EMAIL PROTECTED]...
>
>
> Actually, my experience and then postings since the fall of 1999
> provide an excellent behavior study. It is like a multi-player game as
> it was intended to be. I especially liked some physical interaction
> such as
>
> 1. the Gwinnett county police coming in and illegally searching the
> place,
>
> 2. two persons saing straight to my face "fuck you" and giving the
> finger,
>
> 3. some people calling in (national hotlines, individuals and so on),
>
> 4. getting involvement from Europe and people doing things and
> communicating all kinds of messages (on phone, telegrams, letters and
> so on),
>
> 5. my ex-spouse and her lawyer using my Internet postings in the court
> room (they used that the double-double agent posting :),
>
> 6. the Gwinnett county�s public library�s network shut down or
> distrupted by the CIA/NSA,
>
> 7. people in the cafe in Barnes & Nobles and Borders Bookstore coming
> close to me and telling they are my friends and playing the chess (it
> was likely an effort to get me in),
>
> 8. some people following me from Atlanta to Miami in March, 2000 and
> Jack and two of his friends (one was his wife) coming and telling me
> that he identifies me from a picture and said my name "Mark" that I
> used for years (actually it was invented by my ex-spouse�s grandmother,
> Mrs. Etherton, because she was not able to say my name - and then later
> evolved to other regular business application),
>
> 9. a person with an ear device in New Mexico and my extraordinary
> behavior in Toas, New Mexico,
>
> 10. my ex-spouse bringing a picture of a lion and a cat from her office
> and many others.
>
> And all this has resulted from posting or emailing specific issues and
> matters on the Internet. I have posted many here on the USENET, but I
> have few others that I have still in my notebooks that I have posted.
> It is like I knew what would happen. So in many ways, it has been
> a "human interaction" intelligence agent game (an element of the Game
> of General (M)), where people are real and communication processes are
> both electronic and human. In many ways, it was also a ploy to take
> down all those who were violating my privacy since 1994. You see the
> game started already in February, 1999 (and for those who think you
> started the game - I am so amused :) ). I really wanted to fire Boris
> Yeltsin, because he did more damage to the Russian Federation than good
> in my opinion (CNN check your log files from February, 1999 :) ).
>
>
> Yours,
>
> M
>
> P.S. Actually, you can play this game from anywhere around the world.
>
>
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
------------------------------
Date: Thu, 11 May 2000 02:22:42 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Why no civilian GPS anti-spoofing? / proposal
=====BEGIN PGP SIGNED MESSAGE=====
Roger Fleming wrote:
> For ordinary GPS, I suggest the nature of civilian GPS signals - without
> extreme modification - makes digital authentication completely impossible,
> because:
>
> a. the important point is not the bits in the signal (which are actually
> predetermined), but their timing, so replay attacks are what matters;
> b. the signal is more-or-less cyclic, so replay attacks can include 'future'
> messages (actually from the past cycle); and
> c. The timing errors we are concerned about are not the sort we normally
> consider in communication protocols (did this message arrive before or after
> that one? Is this message still fresh?) but of the order of a fraction of a
> bit - I don't know how to authenticate that!
b. is not difficult to fix, by including sequence numbers that don't repeat.
a. and c. are very difficult, though. The worst case is a faked clock signal
that gradually drifts away from the correct value, by delaying the signal
from the satellite by an increasing time. I can't see how that could be
distinguished from genuine clock drift.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBORoLAzkCAxeYt5gVAQF1ggf/dnXX1XDRhjiJSMTezFGXNwZl0HFUMK3z
6Dc6Z/lrhZXVFxUqGdxnPkTw316SuyHo7/GjrrVMfTZzGSRHGTCUUHecQjXeA+Xg
s9ubzFwEeazEerhLgkPcI8myILC75/SynmP06zREIaVbS7KqKgF8CUxBXOqcf9Nf
wTNuXwhLiGq/0M1kJ0Sgr/xYxLs6ReAnROAqpLxP0vQuoUtjCNq6ml8EjbWde+Ox
eNWHsgTx/GNsk/QIA8vtbKFlT0SVfktrMGIsYNZRZE6sjLhGyhWOGVMJ/2YsUEMs
SgrZ5tkhi2k5Pty1PL71UQErE9lGuWK0Nd7lw952hp/YncCcGoe4Ww==
=95C6
=====END PGP SIGNATURE=====
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
