Re: bootstrapping a secure channel

From: Arthur J. O'Dwyer (ajo_at_nospam.andrew.cmu.edu)
Date: 08/09/04 

Date: Mon, 9 Aug 2004 14:36:04 -0400 (EDT)

On Mon, 9 Aug 2004, Allen Pulsifer wrote:
>
> Enclosed is a paper discussing a protocol for authenticating the
> exchange of public keys. The primary use for this protocol would be
> to bootstrap a secure channel. Remarkably, we have found no papers or
> documented protocols on how to achieve this.

   As Tom already said, there are plenty. Here's the way I understand
the problem you're trying to solve:

     Alice: Hello, Bob?
     Masked Man: Yes, this is Bob speaking.
     Alice: How do I know?
     [...Problem! Alice cannot verify that Masked Man is really Bob!]

The canonical solution, as I understand it, is

     Masked Man: Here is the message "Hello Alice," signed with Bob's
     private key. Only Bob knows that key.
     Alice: ...You're right! Hello, Bob!
     [Solution! Masked Man knows information that only Bob knows!]

> The protocol has one step involving human intervention, specifically,
> it requires human operators to verify the identity of one another and
> compare two short strings.

   You ought to note that this is /not/ "human intervention" as it
is commonly defined in comp-sci circles. Comparing two bitstrings
for equality is something at which computers are exceptionally good.
"Human intervention" would be more like a CAPTCHA or some such
software, or if your procedure required a special hardware dongle
to be manipulated by a human.

> [...] We are not aware of any method that exceeds this
> performance unless it relies on either a preexisting shared secret
> or a trusted third party to broker the public keys.

[...]
> The described method would most likely be used a single time to
> bootstrap a secure channel. For example, it might be used by two
> peers to bootstrap a secure channel when they have never before
> communicated securely, have no shared secret, and neither has a known
> public key or trusted certificate.
[...]
> The peers who wish to bootstrap a secure channel can be any two
> devices on a network, for example, they could be the personal
> computers of two people who wish to communicate securely.

[...]
> Note also that the requirement of using an authenticated communication
> channel is common to all methods of authentication. Even if the two
> parties do not identify each other and exchange some sort of
> information over an authenticated channel, at some point somebody has
> to identify each person and exchange authenticated information with
> them, and this requires an authenticated channel.

   I'm not /sure/ this is true in general, actually, but I'm willing
to accept it as an axiom for the time being. But now you need to
recognize that "any two devices on a network" rarely have access to
such a secure channel. After all, AIUI the usual method of getting
a secure channel is to encrypt the communications, but in your method
AIUI Alice doesn't want to encrypt anything until she's sure that
Masked Man is really Bob, and not somebody else.

   In fact, you sometimes make it sound as if Alice wants to
distinguish between Bob himself, and Ivan using Bob's keys (which
Ivan would have gotten by stealing them from Bob). This is of
course impossible, so please don't hesitate to correct my
misunderstanding. :)

[...]
> Experience shows that most users are not willing to go through this
> inconvenience.

   This is true of everything computer-related. In other words,
"inconvenience" is a problem for the software designers, not for
the theorists. I hear GPG is pretty easy to use---and not because
the algorithms are easy. It would be because someone designed a
one-click interface for the product. Convenience has nothing at all
to do with security, and phrasing it as if it were some kind of
trade-off is generally a sign of snake oil. I would suggest you
remove this line of argument from your final draft, if you really
mean what you're saying about the algorithm.

[...re: public-key databases]
> secure. If is it compromised, communication between all users is
> compromised.

   Not true, as a database of public keys is by definition /public/.
There is nothing to be "compromised" in a public database. Unless
you're suggesting that someone break in and shuffle all the keys
around? P2P will help the database resist modification, I would
think. Anyway, it works well enough in practice AFAIK. ;)

> Second, a user's public key rarely changes. This
> compromises privacy by making it easy to identify a user from their
> public key.

   Huh? That's obvious, right? Bob's public key is /Bob's/ public
key, and nobody else's. It doesn't matter who knows it: Bob is Bob,
and Bob's key is Bob's key. This is intentional.
   Bob is perfectly free to call himself "l33tdude001" online if
he wants, and then aforementioned key becomes "l33tdude001"'s key
and loses all connection to Bob. So Bob's "real name" doesn't have
anything to do with his digital identity either. What are you trying
to say here?

On to...

> Amishare's Method

> 1. Amy generates a random 37-bit Verification Code, VerA, and a random
> 123-bit salt value, SaltA. Amy "signs" her public key, PubA, by
> computing SigA = HMAC-SHA1(VerA + SaltA, PubA), where "+" represents
> the concatenation of the two binary values. Amy sends SigA to Bob.
>
> 2. Bob also generates a random 37-bit Verification Code, VerB, and a
> random 123-bit salt value, SaltB. He then "signs" his public key,
> PubB, by computing SigB = HMAC-SHA1(VerB + SaltB, PubB), and sends
> SigB to Amy.
>
> 3. Amy sends VerA, SaltA and PubA. Bob checks that the values he
> receives, SigA', VerA', SaltA' and PubA', satisfy SigA' =
> HMAC-SHA1(VerA' + SaltA', PubA').
>
> 4. Bob sends VerB, SaltB and PubB. Amy checks that the values she
> receives, SigB', VerB', SaltB' and PubB', satisfy SigB' =
> HMAC-SHA1(VerB' + SaltB', PubB').

   Up to this point, the algorithm sounds exactly like the canonical
approach to get rid of "man-in-the-middle" attacks: send one part of
the message to make the MITM "commit" to one line, and then send the
other half in such a way that the MITM can't back out of his "prior
commitment" without alerting Alice and Bob to his presence.

> 5. Via an authenticated channel, Amy and Bob compare the Verification
> Codes they sent, VerA and VerB, with the values they received, VerA'
> and VerB'. An "authenticated channel" again means that (a) Amy and
> Bob are able to verify each others' identity; and (b) no one is able
> to alter the contents of their communication without being detected.

   This is (1) generally hard to find; and (2) exactly the thing which
AIUI you are trying to bootstrap! If Alice and Bob /had/ access to
such a secure and authenticated channel, they'd just /use it/, and
not worry about all this "verification" stuff. Furthermore, Alice
and Bob could even use the secure authenticated channel to establish
a shared secret which they'd use to encrypt all their later messages
on the insecure unauthenticated channel.

   Postulating the existence of such a "magic" secure channel takes all
the interest out of the problem. It's like asking how Alice can send
a package to Bob without any tampering if all she has available is an
uncrackable safe to which Bob knows the combination!

> In Amishare, the Verification Codes are interleaved by-bit and
> converted to a single string. These sub-steps in detail, and the
> reasons for each sub-step, are the following:

   (The exact details of the bit-twiddling involved in comparing two
37-bit strings for equality are really unnecessary.)

[...]
> The strings are then displayed for the users in a large, clearly
> legible font. If the resulting verification string on Amy's screen
> matches the resulting verification string on Bob's screen, Amy and Bob
> are assured to a probability of approximately 1 in 2^37 that the keys
> they received are authentic.

   Two comments: (1) How does Alice know what's on Bob's screen, or
vice versa? Obviously in your case they've both got access to the
"magic channel," so it's no big deal. But in practice this will be
tricky and/or impossible.
   (2) Readers who have gotten this far will realize that the magic
number 37 is just that: a magic number. There's no reason to choose
37 over, say, 128 or 1024, except cuteness. Don't force your readers
to figure this out by themselves; state the reason for the magic
number 37 in the introduction. Or, maybe better, generalize the
description of the procedure from 37 bits to 'N', for any 'N' the
implementor cares to provide.

> 6. Finally, if the Verification Codes match, Amy and Bob use their
> public keys to establish a secure communication channel.

> In summary, this is a powerful new method of authenticated key
> exchange without digital certificates. It does not require a
> pre-existing shared secret, or a pre-existing secure channel to
> exchange a shared secret.

   Unless I missed something, that last part is baldly untrue. Alice
needs a "magic channel" which is both authenticated and secure---or
is it only authenticated? Anyway, already having an authenticated
channel takes all the interest out of it: it's a simple key-exchange
then, the sort of thing most people do in their sig blocks every day.

> The techniques described in this paper have been implemented in a new
> peer-to-peer communication program called Amishare. Amishare can be
> downloaded at http://www.amishare.com and provides a good
> demonstration of how this method can be applied to secure
> communications.

>From the EULA:
       You agree not to reverse engineer, decompile, or disassemble
     the Software, or analyze or reverse engineer any information
     transmitted by or to the Software or Services.

Yeah, that's secure enough all right. ;)

-Arthur,
"bleagh, this oil tastes like snake!"

Relevant Pages

  • Re: Almost Chris No More (long)
    ... Bob Rickard ... >> actually have to turn in their guns in early Feb., ... I had just entered the channel, ... >>> houses lining both sides, ...
    (rec.outdoors.fishing.bass)
  • Things that go wrong - First 21 Days on the ICW
    ... Nov 4 - Bob did figure out how to get out without running into the ... We came into Point Comfort Marina ... least he didn't try to polish the anchor :-) He opens the engine hatch ... We came in Shim's Creek instead of going in the Mott Channel ...
    (rec.boats.cruising)
  • Re: Slow Boot and Scratchy Sound
    ... I think you and Bob were helping a lot ... McCarty" wrote: ... optical drives that have difficulty reading a disk than hard drives. ... There the channel shows ULTRA DMA MODE 6. ...
    (microsoft.public.windowsxp.general)
  • Re: Slow Boot and Scratchy Sound
    ... "Bob I" wrote: ... Roger wrote: ... How can i move to a different channel. ... And the windows sounds and sounds from games sounds scratchy. ...
    (microsoft.public.windowsxp.general)
  • Re: Using NTFS security to protect files served via asp/iis
    ... >> authenticating. ... >> the server, then set it to have NTFS read permissions for file. ... I'm not sure I understand why you want ASP ... A local user on the server is called "bob". ...
    (microsoft.public.inetserver.asp.general)
Quantcast