Defeating MITM with Eric's Secure Phone

-----BEGIN PGP SIGNED MESSAGE-----

[ To: cypherpunks, coderpunks, Perry's Crypto List ##
  Date: 09-Oct-97 ##
  Subject: Defeating MITM with Eric's Secure Phone ]

>Date: Wed, 8 Oct 1997 23:48:33 +0100
>From: Adam Back <aba@dcs.ex.ac.uk>
>Subject: computationally infeasible jobs for MITMs (Re: Secure
phone)

>How about this for a computerised method to do something similar. 
Aim
>of the game: to make the MITMs job computationally infeasible.

[Method using stegoed audio noise deleted.]

I prefer to work on the more immediately useful problem:
How can I secure my use of the (very nicely done) Comsec
secure phones using existing infrastructure?  I am concerned
with the MITM voice impersonation attack, since that's the
easiest attack on the system. (Actually, it's probably
easier to physically tap my office, but I can't fix that
right now.)

The simple MITM defenses (like restating your checksum
spontaneously in the middle of the conversation) take care
of lots of this.  Here's another way that may make some
sense, though it's a little hard to use:

1.	Exchange PGP-encrypted e-mail establishing a set of
sixteen different words, labeled for 0..f in each direction.
Thus:

0.	Dilbert
1.	Alpha
2.	Cable
3.	Swordsman
...
f.	Marxist

Now, the checksum reading is very hard to spoof.  Suppose I
get 0x33f. I say ``My checksum is Swordsman Swordsman
Marxist, or 33f.''

An attacker with digits besides 3 and f in his checksum
simply doesn't know how to impersonate me to the other
party.  He lacks the secret information we've shared.

Now, the problem with this is that it's too cumbersome.  I
would like the shared secret information to be usable with
less effort.

If we just want to detect the MITM eventually, then I can
send the other participant a PGP-signed e-mail, in which I
include the whole 6-digit checksum.  That won't prevent the
MITM attack from working once, but it will let us know
after-the-fact if our conversation was exposed.  If we find
evidence that our conversation was intercepted, then we can
start using my one-time word lists, or some other more
paranoid mechanism.

Still another approach, which may be applicable for some
people, is to write a simple calculator-type application
that uses a shared-secret to compute a checksum on the
checksum.  Thus, when I call Alice, I do the following:

1. Type the shared secret between Alice and me into the
calculator app.

2. Make the call to Alice and push the ``secure'' button.

3. Type the six-digit checksum into the calculator app.

4. Read the calculator's first three checksum digits.

5. Listen to her next three digits.

The simplest way to do this seems to be to just exchange a
six-digit hex value as a one-time password for a given
secure phone call.  This is done using PGP or some other
mail encryption package, and can legitimately be used to
exchange a long list of one-time passwords at once. Then,
use Windows' calculator application (with View set to
Scientific, and Mode set to Hex) to add your one-time
password to the checksum.  Thus:

1. I pull up Alice's latest encrypted e-mail, and get
today's phone password.

2. I open the Windows calculator, set it to View/Scientific
and hex mode, and type in the password (a six-digit hex
number) and ``+.''

3. I call Alice, say hello, and push the ``SECURE'' button.

4. I type the six digit hex checksum into my calculator.

5. I read the first three digits of the result to her.  She
reads the next three to me.

All of this (except for maybe re-reading the checksum in the
middle of the conversation) is probably overkill.  Still, it
may be worth something to someone.

Is there a clean way to have the secure phone box take input
from the dialpad on the phone, without sending it out on the
phone line?  If so, then maybe some later version could
include a PIN-secured mode, using EKE or SPEKE or something
similar.  (For a supported mode, the checksum wouldn't need
to be read over the phone anymore.  We would need to protect
the shared PIN from brute-force attack, however.)

>Adam


   --John Kelsey, jmkelsey@plnet.net / kelsey@counterpane.com

- -----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.2

mQCNAi5JqlEAAAEEAPCEHMBdDCAJ83/ibNM7ngCaaibv7YkTxcpKPjTO+WcjswFV
SEzMeTqW4MX2wSKdfcMq1HembbgfYs7v2UCnUFkLPZF19s3yUSISGcS7JxlBc3q1
7uj8W5XfBoGpgCYQqYFL2+AB/+3tLu7lU5iiEYCnevY5GQkq0kHx57Ag8goBAAUR
tCdKb2huIE0uIEtlbHNleSBKciA8am1rZWxzZXlAZGVscGhpLmNvbT6JAJUDBRAv
5uh7QfHnsCDyCgEBAQZ2A/9/OMeWK4YC+PnEzBTmgpF4WAOsVXfzRD3zAbzfNWY9
MEGo4gRF8Mr1lPHdK+0JOHp327mj9ZvYqQb1bV5fwc5dJa8/Z34VLPYlVg2rV7vJ
Hd0YnrgkoaIerbRmtP8dmZGeygeFtrk8aDCdcnMm27+tTJACl5hv2yjFO9rxBq+R
MLQpRXhwaXJlcyBmb3IgbmV3IHNpZ3MvbXNncyBvbiBEZWMgMzEsIDE5OTc=
=pOyw
- -----END PGP PUBLIC KEY BLOCK-----


-----BEGIN PGP SIGNATURE-----
Version: 2.6.2

iQCVAwUBNDy68UHx57Ag8goBAQGP1QP9H6Z9Infv1z1swBzpEsvn+VZyweMj20to
EQNRFcfLvNFu140kWokWfgIcSXh1CBrsz93/CMoZgIb8l1cpGIU51kFgz/DTXGvj
5XQCFcUzBRAEraxeF7xFnEH+Ss35lcCvzAXaWaVLB6apBvXP5ZkZtFr/vUYLhrtF
Y34E8AAXFrg=
=AlX3
-----END PGP SIGNATURE-----


   --John Kelsey, Counterpane Systems, kelsey@counterpane.com
 PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36

John Kelsey <kelsey@plnet.net> writes:
> Adam Back <aba@dcs.ex.ac.uk> writes:
> [computationally infeasible jobs for MITMs]
> I prefer to work on the more immediately useful problem: How can I
> secure my use of the (very nicely done) Comsec secure phones using
> existing infrastructure?  I am concerned with the MITM voice
> impersonation attack, since that's the easiest attack on the
> system.

We were discussing this problem before turning to talking about
automated methods.  I think Eric Blossom suggested this earlier on:

> 1.	Exchange PGP-encrypted e-mail establishing a set of
> sixteen different words, labeled for 0..f in each direction.
> Thus:
> 
> 0. Dilbert 1. Alpha 2. Cable 3. Swordsman ... f. Marxist
> 
> Now, the checksum reading is very hard to spoof.  Suppose I
> get 0x33f. I say ``My checksum is Swordsman Swordsman
> Marxist, or 33f.''

It seems like a good solution.  An interesting question might be how
many times can you use the same table without starting to leak values.
Perhaps it doesn't matter that much because the MITM can't exactly use
brute force on the problem otherwise you will know he's there.  He has
to act non-passively to extract information.  (Presuming the protocol
exchanges part of the information hashed for the challenge is
encrypted with the negotiated key).

> Now, the problem with this is that it's too cumbersome.

What would be nice would be able to have information on one sheet of
paper which you could continue to use for lots of communications,
without need for calculator, or computer, or more emailed tables.

> The simplest way to do this seems to be to just exchange a
> six-digit hex value as a one-time password for a given
> secure phone call.  This is done using PGP or some other
> mail encryption package, and can legitimately be used to
> exchange a long list of one-time passwords at once. Then,
> use Windows' calculator application to add your one-time
> password to the checksum.  Thus:
> 
> 1. I pull up Alice's latest encrypted e-mail, and get
> today's phone password.
> 
> 2. I open the Windows calculator, set it to View/Scientific
> and hex mode, and type in the password (a six-digit hex
> number) and ``+.''
> 
> 3. I call Alice, say hello, and push the ``SECURE'' button.
> 
> 4. I type the six digit hex checksum into my calculator.
> 
> 5. I read the first three digits of the result to her.  She
> reads the next three to me.

I considered this approach (XOR and + function) earlier in this
thread.  I don't think it works because the functions are commutative.
(Unless I'm missing some aspect of the system, perhaps the
interlock... it's a while since I've read the protocols.)

Here's why I think it doesn't work: We have Alice, Mallet and Bob.

Alice & Bob exchange via email password 123456.  The displayed digits
of the hash of Alice/Mallet's DH parameters are: 222222.  The
displayed digits of Mallet/Bob's DH parameters are: 333333.

Alice computes 123456 + 222222 = 345678; Alice says to Mallet: "345"
Bob computes 123546 + 333333 = 456789; Bob says to Mallet: "789"

Mallet recovers the first 3 digits of the passphrase from what Alice
said:	345 - 222 = 123

Mallet recovers the last 3 digits of the passphrase from what Bob
said:	789 - 333 = 456

Mallet has recovered the passphrase and can now spoof Alice to Bob and
Bob to Alice, he says: 456+222 = 678 to Alice, and 456+333 = 789 to
Bob.

Same story with XOR, only it's harder to compute.

I think you need an encryption function.  It depends on how many times
you wanted to re-use the passphrase.  The "encryption" function could
be very weak for one use.  For lots of uses you'd need a real
encryption function.  Problem is encryption functions aren't typically
very easy to perform as mental arithmetic exercises; and
non-programmable calculators don't help much.

The table solution gets around this problem nicely, because it is a
secure way of using a one time password.  Possibly a relatively secure
way of re-using that password even, if mallet has to become active to
obtain information, and gets detected on occasions when he doesn't
yet have sufficient information.

Adam
-- 
Now officially an EAR violation...
Have *you* exported RSA today? --> http://www.dcs.ex.ac.uk/~aba/rsa/

print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`

Adam Back wrote:
> John Kelsey <kelsey@plnet.net> writes:
> > Adam Back <aba@dcs.ex.ac.uk> writes:
> > [computationally infeasible jobs for MITMs]
> > I prefer to work on the more immediately useful problem: How can I
> > secure my use of the (very nicely done) Comsec secure phones using
> > existing infrastructure?  I am concerned with the MITM voice
> > impersonation attack, since that's the easiest attack on the
> > system.
 
> We were discussing this problem before turning to talking about
> automated methods.  I think Eric Blossom suggested this earlier on:
> 
> > 1.    Exchange PGP-encrypted e-mail establishing a set of
> > sixteen different words, labeled for 0..f in each direction.
 
> It seems like a good solution.  An interesting question might be how
> many times can you use the same table without starting to leak values.
> Perhaps it doesn't matter that much because the MITM can't exactly use
> brute force on the problem otherwise you will know he's there.  He has
> to act non-passively to extract information.  (Presuming the protocol
> exchanges part of the information hashed for the challenge is
> encrypted with the negotiated key).
 
> I think you need an encryption function.  It depends on how many times
> you wanted to re-use the passphrase.  The "encryption" function could
> be very weak for one use.  For lots of uses you'd need a real
> encryption function.  Problem is encryption functions aren't typically
> very easy to perform as mental arithmetic exercises; and
> non-programmable calculators don't help much.

Plus - A table can be based on a previously agreed upon one-time pad,
  such as the old-school spook classic, first three words, second
  column, page 3, New York Times. 

PlusPlus - On the InformEnergy Highway, this method can be further 
  obscured by use of data on an obscure website, text or source, 
  binary or hex, etc.

The point being, that one can use complex or obscure methodologies
to obtain the one-time pad table of the day, which can be simple 
enough to calculate on-the-fly in one's head.

there Are Some Similar metHOds peopLe can useE
which can even be used by children, such as myself.

Kill Flags - When WE' RElying on FeatUres of suCh Kinds, Everyone
  shoulD be using prearranged kill flags to signal danger.

Keep in mind that I may just be telling you these things because
I am a cop and trying to gain your confidence.

OTOH, how many cops have a:
Human Gus-Peter

>>> 1.	Exchange PGP-encrypted e-mail establishing a set of
>>> sixteen different words, labeled for 0..f in each direction.....
>>>  ``My checksum is Swordsman Swordsman Marxist, or 33f.''
That really does seem easier than all this checksum business;
if you're exchanging secrets anyway you could also type your
half-keys into some friendly application program, but this is fun.
On the other hand, for Alice's Fax Machine calling Bob's Fax Machine,
it's tougher to automate this stuff.  Does the phone have some way
to output the checksums to a data port for checking later?
(stuffing it into the fax header field would be a nice touch.)

> Either Mallory is in the middle or he isn't.  If he isn't, no problem.
> The word list remains secure.
>
>If he is in the middle, he has 15 chances in 16 of being caught on the
>first exchange.  He only survives if the first digit of the Alice-Mallory
>connection is the same as the first digit of the Mallory-Bob connection.

If there's a failure, you're going to burn this list anyway;
if Alice and Bob each read all their codewords, Mallory can trick them
about 1/16**6 times (1/16Million), which is pretty low -
Mallory learns up to six codewords, but they're only useful if
he doesn't get caught or if Alice and Bob decide to reuse the list
because they don't have a chance to exchange more email.
So if you're not worried about denial of service, catch him.
You do have to make sure Alice and Bob _notice_ they've been hosed;
you can get a bit fancier by using two lists, one for use 
in case of errors or other interruptions
Alice: Swordsman Swordsman Marxist  ->
Mallory: Marxist COUGH COUGH ->
		<- Bob: Dilbert Marxist Aardvark, and repeat please
		<- Mallory: Swordsman Dilbert COUGH, and repeat please
Alice: Swordsman Swordsman Marxist, sounds like you have a cold? ->
Mallory: Marxist Dilbert Aardvark, and I've got a cold too. ->

As opposed to 
		<- Bob: Bogus Suspicious Fnord, and repeat please
Alice: Swordsman Swordsman Marxist, and I've got a bad feeling about this....		

Even just using one list for Alice and one for Bob helps this attack.

>If Alice and Bob catch Mallory, they talk about the weather and exchange a
>new list by email.  If they don't, there is a very high probability that
>the word list has not been compromised, and they can safely continue to use
>it for the next call.

				Thanks!
					Bill
Bill Stewart, stewarts@ix.netcom.com
Regular Key PGP Fingerprint D454 E202 CBC8 40BF  3C85 B884 0ABE 4639

At 12:08 PM -0700 10/9/97, Adam Back wrote:
>John Kelsey <kelsey@plnet.net> writes:
>> Adam Back <aba@dcs.ex.ac.uk> writes:
>> [computationally infeasible jobs for MITMs]
>> I prefer to work on the more immediately useful problem: How can I
>> secure my use of the (very nicely done) Comsec secure phones using
>> existing infrastructure?  I am concerned with the MITM voice
>> impersonation attack, since that's the easiest attack on the
>> system.
>
>We were discussing this problem before turning to talking about
>automated methods.  I think Eric Blossom suggested this earlier on:
>
>> 1.	Exchange PGP-encrypted e-mail establishing a set of
>> sixteen different words, labeled for 0..f in each direction.
>> Thus:
>>
>> 0. Dilbert 1. Alpha 2. Cable 3. Swordsman ... f. Marxist
>>
>> Now, the checksum reading is very hard to spoof.  Suppose I
>> get 0x33f. I say ``My checksum is Swordsman Swordsman
>> Marxist, or 33f.''
>
>It seems like a good solution.  An interesting question might be how
>many times can you use the same table without starting to leak values.
>Perhaps it doesn't matter that much because the MITM can't exactly use
>brute force on the problem otherwise you will know he's there.  He has
>to act non-passively to extract information.  (Presuming the protocol
>exchanges part of the information hashed for the challenge is
>encrypted with the negotiated key).
>
>> Now, the problem with this is that it's too cumbersome.
>
>What would be nice would be able to have information on one sheet of
>paper which you could continue to use for lots of communications,
>without need for calculator, or computer, or more emailed tables.

When I suggested using code words to exchange the checksum, I thought you
would have to use them in one-time-pad mode to be secure.  The following
argument makes me think you can reuse them several times, changing them at
about the same rate as you would change a symmetric crypto key.

Assume that the contents of the paper are secret between Alice and Bob.
When Alice calls Bob, she reads the word coresponding to the first digit of
the checksum.  Either Mallory is in the middle or he isn't.  If he isn't,
no problem.  The word list remains secure.

If he is in the middle, he has 15 chances in 16 of being caught on the
first exchange.  He only survives if the first digit of the Alice-Mallory
connection is the same as the first digit of the Mallory-Bob connection.
He now knows the word for one value and can continue to play 1 out of 16
times.

The probability he can survive the next word that Bob reads to Alice is
harder to calculate.  He can survive if the second digit of the Mallory-Bob
connection is the same as the second digit of the Alice-Mallory connection,
or the second digit of the Alice-Mallory connection is the same as the
first digit on that connection.  Without doing the math, Mallory's survival
probability becomes very small as the exchange continues.

If Alice and Bob catch Mallory, they talk about the weather and exchange a
new list by email.  If they don't, there is a very high probability that
the word list has not been compromised, and they can safely continue to use
it for the next call.


BTW - I really like John's idea of doing another exchange later in the
conversation.  Perhaps something like, "You know, I was dancing the Foxtrot
with my wife 9 days ago at 5AM."


-------------------------------------------------------------------------
Bill Frantz       | Internal surveillance      | Periwinkle -- Consulting
(408)356-8506     | helped make the USSR the   | 16345 Englewood Ave.
frantz@netcom.com | nation it is today.        | Los Gatos, CA 95032, USA