bootstrapping a secure channel

From: Allen Pulsifer (amicrypt_at_amishare.com)
Date: 08/09/04


Date: 9 Aug 2004 07:27:38 -0700

Greetings,

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.

We posted this last week looking for feedback. Unfortunately, the
thread was immediately hijacked for a discussion of PKI.

Enclosed again for public review and comments is a copy of the paper.
In specific, we would like comments in these areas:

1) A critique of the protocol, perhaps pointing out a flaw, agreeing
with the security analysis, calling attention to missing factors that
should have been considered, etc.

2) References to other papers that document or analyze techniques for
bootstrapping a secure channel.

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. The main goal is to minimize the amount of
work the human operators have to do while still achieving an
acceptable level of security. In the method discussed, if the human
operators compare a total of N bits of data, the chance of an attack
succeeding is 1 in 2^(N/2). Thus the method is able to achieve a high
level of security (1 in 2^37) with only 74 total bits of data
authenticated. 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.

Thank you,

Allen Pulsifer
amicrypt@amishare.com

---------------------------------------------------------------------------

        Authenticated Public Key Exchange without Digital Certificates

This paper describes a new method of authenticated public key exchange
that does not use digital certificates.

The protocol described involves human intervention. In particular, it
requires human operators to verify the identity of one another and
compare two short strings. This ensures that the public keys received
were actually sent by the desired parties and were not altered in
transit.

Since the protocol involves human intervention, it has a unique
concern: to achieve an acceptable level of security while being as
convenient as possible for the human operators. On the security side,
the method is concerned with not only the numeric probability of a
successful attack, but also the likelihood the human operators will be
willing and able to accurately perform their part of the protocol. On
the convenience side, the protocol is concerned with minimizing the
amount of work the human operators must do, and making the overall
workflow and the individual steps as easy to understand and perform as
possible.

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. If either party has a known public
key or trusted certificate, there are likely more efficient protocols.
 However, this protocol could be still used in instances where the
parties wish to personally verify the information in the certificate,
or if they do not wish to use a certificate or identifiable public key
for privacy reasons.

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. They could
also be two firewalls that want to establish a VPN connection, or two
wireless devices that want to exchange data.

Although the need to bootstrap a secure channel arises all the time,
remarkably, this seems to be a little studied area. The author was
unable to find any prior publication or documented techniques on this
topic. Even RSA Security's PKCS #10 v1.7, which addresses certificate
requests, simply states: "A certification authority fulfills the
request by authenticating the requesting entity and verifying the
entity's signature." It makes no mention how the certificate
authority might verify the request was actually sent by the requesting
entity, and verify that the request was not altered in transit, for
example, by substituting public keys.

In the technique described, the devices "sign" their public keys with
random 37-bit Verification Codes prior to the key exchange. The
Verification Codes are then compared by the human operators. If the
codes match, the probability of a successful attack is 1 in 2^37.

In general, if N bits are ultimately compared by the human operators,
the chance of a successful attack is 1 in 2^(N/2). This is a
significantly higher level of security than any current method of
bootstrapping a secure channel that does not rely on a trusted third
party, and may equal the maximum theoretical limit. Further study
would be needed to determine if this is the case.

The techniques described have been implemented in a new peer-to-peer
communication application called Amishare. This program can be
downloaded at http://www.amishare.com and provides a good
demonstration of how these techniques can be used in practice.

Introduction

Public/private key cryptography such as RSA or Diffie-Hellman is often
used to establish a secure channel between two peers. One method is
for both peers to send public keys to the other. With RSA, the public
keys can then be used to encrypt and transmit two secrets that are
combined into one shared secret. With D-H, the public parameters can
be directly used to generate a shared secret.

The protocol might look something like this:

        Amy and Bob exchange public keys.

        Amy and Bob authenticate the keys to ensure they came from each
other.

        Amy and Bob use the keys to exchange secrets and establish a secure
channel.

The keys can be either long-term (semi-permanent) or temporary
(ephemeral) keys. Authentication is critical to the exchange of
public keys, since it (a) prevents an attacker from impersonating one
of the peers; and (b) prevents an attacker from substituting his keys
for the parties' keys and carrying out a man-in-the-middle attack.

Existing Methods of Authenticated Public Key Exchange

These are some methods currently used to exchange and authenticate
public keys:

M1. The parties directly exchange keys using an authenticated channel.
 In this case, authenticated means the parties can identify one
another, and what they send cannot be altered without being detected.
The parties might read their public keys to each other over the
telephone, or they might exchange diskettes containing their keys.

Note that email does not qualify as authenticated because it can be
intercepted and altered or forged, allowing an attacker to impersonate
one of the parties or carry out a man-in-the-middle attack.

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.

The disadvantage of this method M1 is that the public key is very
large, making it difficult to communicate over the telephone. With a
2048-bit public key, the parties would have to read and type
approximately 512 hexadecimal digits each. If even one digit were
transcribed incorrectly, they would be unable to communicate. Key
exchange by diskette is more palatable, but takes time and requires
either meeting in person or using a trusted delivery service.
Experience shows that most users are not willing to go through this
inconvenience.

M2. Another technique is for the peers to exchange public keys via an
unauthenticated communication channel (such as email), and then use an
authenticated channel to verify some attribute of the keys. This
attribute could be the key value itself, or it could be the size and
hash of the key.

If the entire key is verified, this method requires a great deal of
data to be compared. If the hash of each key is verified, this method
still requires a fair amount of data to be compared. In addition, it
is now vulnerable to collision attacks. If an attacker can generate a
public key with the same hash as another person's public key, he can
impersonate that person or do a key substitution. The more time he
has to work on this problem, the more likely he will succeed.

The solution is to use a long enough hash that it is resistant to
collision attacks. The SHA1 hash is 160 bits long and considered to
be sufficiently resistant. However, in order to authenticate a key
using an SHA1 hash, each person would have to check approximately 40
hexadecimal digits. It is unlikely in practice that users would make
a full comparison of the hashes. An attacker might therefore be
successful if he can match only the first N digits of the hash, where
N is in the neighborhood of 10-20. This makes a collision attack much
more possible.

In summary, this method has many tradeoffs in the size of the
attribute compared, the likelihood users will be willing and able to
make an accurate comparison, and the potential for collision attacks.

M3. Another method is to store every user's public key in a central
database indexed by User ID. This database might allow a user to
create their own entry as long as the User ID is unique, so the user's
identity would not need to be verified before creating the entry.

To exchange keys, the peers first exchange User ID's over an
authenticated channel. They enter these User ID's into their
computers, and the computers fetch the public keys from the central
database, also using an authenticated channel such as SSL.

For many applications, this is possibly one of the best methods.
However, it has several disadvantages. First, the server must be
secure. If is it compromised, communication between all users is
compromised. Second, a user's public key rarely changes. This
compromises privacy by making it easy to identify a user from their
public key. Finally, there are numerous key management and service
reliability issues. How does a user change or revoke their public
key? What happens if someone executes a denial of service attack on
the central database?

M4. Another method is for a central authority to issue digital
certificates to each user containing their User ID and public key.
The users could again order their own certificates as long as the User
ID is unique, so an authenticated channel is not required.

This method has almost all of the same problems as method M3. The
users can send each other certificates via email or some other
unauthenticated channel, but they still need to use an authenticated
channel to verify the certificates' User ID's. A major disadvantage
is that an attacker could obtain a certificate with a User ID very
similar to another person's, then attempt to impersonate that person.
A person verifying the certificate might not notice the subtle
difference and end up using the imposter's public key instead of the
intended peer's. The only advantage of this method is that it will
continue to operate even if the central database is offline.

M5. A related method is for a central authority could issue digital
certificates to each user containing their full identity along with
their public key. For example, the full identity might include their
name, age, address, etc. The information included would need to be
sufficient to allow users to associate the certificate with the actual
person.

In this method, the central authority assumes the responsibility of
verifying each user's identity. This verification would have to take
place over an authenticated channel.

For some applications, the advantage of this method is that users have
to be verified only once by the central authority and not by each user
with whom they communicate. This can especially be an advantage when
the users do not know each other well enough to confirm identities.

However, in other applications, this is a drawback. Often it is the
central authority who does not know the users and has little basis on
which to verify their identities. Furthermore, the certificates
continue to be a privacy concern, even more so because they contain
personally identifiable information. Finally, this method also
suffers from the problem that if the security of the central authority
is compromised, communication between all users is no longer secure.

M6. A final method is for the two parties to have a pre-existing
shared secret, and to use this secret as an HMAC key or in a protocol
such as SPEKE. There are several problems with this method. First,
the pre-existing secret has to be shared over a secure channel in
order to keep it secret. This defeats the purpose of the protocol: to
create a secure channel where none exists. Second, as long as the
shared secret exists, it is a potential security vulnerability. If
the shared secret is compromised, so is the security of the key
exchange.

 
Amishare's Method

In Amishare, the parties "sign" their public keys using random 37-bit
Verification Codes, and later verify the identity of one another and
compare Verification Codes over an authenticated channel. The
probability of a sucessful attack is 1 in 2^37.

The detailed steps in this protocol are as follows:

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').

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.
The telephone or in person are two good methods of verification, or
the parties can use an existing authenticated electronic communication
channel such as digitally signed email.

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:

5a. The Verification Code are interleaved by bit with Amy's first bit
coming first, Bob's first bit coming second, etc. Stated another way,
Amy constructs:

        Va = VerA(0) + VerB'(0) + VerA(1) + VerB'(1) + ... + VerA(36) +
VerB'(36)

and Bob constructs:

        Vb = VerA'(0) + VerB(0) + VerA'(1) + VerB(1) + ... + VerA'(36) +
VerB(36)

where "+" represents concatenation.

The next steps are to convert the values to strings and compare the
strings. Interleaving bits combines the codes into one string and
makes the comparison easier for the users. The values are interleaved
by bit so neither verification code "comes first", giving both equal
weight in the comparison. Even if the users don't do a full
comparison (for example, they compare only the first 5 characters),
they will have compared a (more or less) equal number of bits in each
Verification Code. Finally, interleaving bits prior to conversion
magnifies the discrepancies in a single Verification Code, making it
more likely tampering will be detected.

5b. The interleaved values are converted to a string by encoding them
with a 32 character alphabet consisting of the uppercase letters A-Z
along with the digits 3-4 and 6-9. At five bits per character, this
results in a 15 character string. The string is separated by dashes
in the format:

        ABC-DEF-GHI-JKL-MNO

This encoding and format were chosen to provide a compact
representation that would minimize the potential for human comparison
errors.

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.

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

Perhaps the easiest way to analyze this protocol is to attempt a few
attacks.

Impersonation Attack

If Mallory attempts to impersonate either party, this will be
trivially detected when Amy calls Bob on the phone (or vice-versa),
and Bob responds, "Verification Code? What are you talking about?"

Online Man-in-the-Middle Attack

In this attack, Mallory attempts to intercept the exchange and
substitute his keys for the parties' keys:

1. Amy sends SigA = HMAC-SHA1(VerA + SaltA, PubA).

        Mallory intercepts and substitutes his key PubA* for Amy's key, PubA.
        Mallory doesn't know Amy's VerA or SaltA,
     so he has to generate his own VerA* and SaltA*.
        Mallory sends Bob SigA* = HMAC-SHA1(VerA* + SaltA*, PubA*).

2. Bob sends SigB = HMAC-SHA1(VerB + SaltB, PubB).

        Mallory sends Amy SigB* = HMAC-SHA1(VerB* + SaltB*, PubB*).

3. Amy sends VerA, SaltA and PubA.

        Mallory sends VerA*, SaltA* and PubA*. Bob checks that the values he
receives, SigA*, VerA*, SaltA* and PubA*, satisfy SigA* =
HMAC-SHA1(VerA* + SaltA*, PubA*), which they do.

4. Bob sends VerB, SaltB and PubB.

        Mallory sends VerB*, SaltB* and PubB*. Amy checks that the values
she receives, SigB*, VerB*, SaltB* and PubB*, satisfy SigB* =
HMAC-SHA1(VerB* + SaltB*, PubB*), which they do.

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*.

Since Mallory did not know the Verification Codes Amy and Bob used to
"sign" their keys, he had to guess, and he gets only one try. He has
only a 1 in 2*2^37 chance of correctly guessing both Verification
Codes. Most likely, the codes on Amy and Bob's computers will not
match, and Mallory's tampering will be detected.

The size of the Verification Codes, 37 bits, was chosen to achieve an
acceptable level of security while limiting the amount of manual work
Amy and Bob have to do. If a higher level of security is required,
the size of the Verification Codes can be increased. Alternatively,
if the Amy and Bob want to reduce their workload, they can simply
compare the beginning of the string, and ignore the end. Comparing
just the first N bits of the string has the same effect as truncating
each Verification Codes to N/2 bits, and has same effect on security
as setting the size of the Verification Codes to N/2 bits. The method
is therefore scalable: even though the string is 15 characters, Amy
and Bob can simply decide for themselves to compare fewer characters
if they do not require that level of security.

There as an additional avenue of attack that explains the need for the
salt values. It is possible that Amy and Bob have used these public
keys before, and Mallory knows their values. For example, if Amy and
Bob reuse their public keys, Mallory could simply run the protocol
with each person and then abort after they reveal their public key.

If Mallory knows the values of the public keys PubA and PubB in
advance, he might attempt to reverse HMAC-SHA1(VerA + SaltA, PubA) to
obtain VerA, and reverse HMAC-SHA1(VerB + SaltB, PubB) to obtain VerB.
 In order to fool the parties, Mallory only needs to get the 37 bit
Verification Codes correct. However, in a brute force attack, he will
not know he has a solution until he gets both the Verification Codes
and the salt values correct, a total of 160 bits. Including the salt
thwarts what would otherwise be an easy attack.

Despite the salt, Mallory still has a non-zero probability of
successfully executing a brute force attack. Assuming for a moment
that Amy will only wait 40 seconds to get a response back from Bob,
Mallory must reverse the HMAC within this time. Generously assuming
he can compute 10 Giga-HMAC's per second, his odds of successfully
determining Amy's VerA is on the order of 1 in 2^121. This is so much
less than his odds of simply guessing the correct value for the 37-bit
Verification Code that it can be safely be ignored.

That notwithstanding, the protocol can be made immune from this attack
by never reusing the same value for the public keys, in which case
Mallory has no information to attempt a brute force reversal of the
HMAC. The protocol can also be further hardened against this attack
by increasing the size of the salt, appending additional salt to the
public key, or iterating the HMAC.

Offline Man-in-the-Middle Attack

In this attack, Mallory runs all the way through the protocol with one
person, then attempts to replay the values with the other person. In
this particular example, Mallory exchanges keys with Amy while playing
the role of Bob, then exchanges keys with Bob while playing the role
of Amy.

1. Amy sends SigA = HMAC-SHA1(VerA + SaltA, PubA).

        2. Mallory responds with SigB* = HMAC-SHA1(VerB* + SaltB*, PubB*).

3. Amy sends VerA, SaltA and PubA.
 
4. Mallory responds with VerB*, SaltB* and PubB*. Amy checks that the
values she receives, SigB*, VerB*, SaltB* and PubB*, satisfy SigB* =
HMAC-SHA1(VerB* + SaltB*, PubB*), which they do.

Immediately thereafter:

        1. Mallory sends Bob SigA* = HMAC-SHA1(VerA + SaltA, PubA*). Since
Mallory now knows Amy's VerA, he can use it to compute SigA*.

2. Bob sends SigB = HMAC-SHA1(VerB + SaltB, PubB).

3. Mallory responds with VerA, SaltA and PubA*. Bob checks that the
values he received, SigA*, VerA, SaltA and PubA*, satisfy SigA* =
HMAC-SHA1(VerA + SaltA, PubA*), which they do.

4. Bob sends VerB, SaltB and PubB.

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*.

Mallory's problem is that when interacting with Amy, he had no idea
what VerB Bob would eventually generate, so he had to send VerB*. He
had only a 1 in 2^37 chance of correctly guessing Bob's VerB. Most
likely, Mallory's tampering will be detected when Amy and Bob compare
the Verification Codes on their computers.

A similar analysis would show it does not matter what role Mallory
attempts to play, Amy with Bob then Bob with Amy, or Amy with Amy then
Amy with Bob, or Bob with Amy then Bob with Bob. Mallory will be able
to get one of the two Verification Codes correct, but he will be
unable to get both.

Just in case, the protocol is strengthened by making the comparison of
Verification Codes depend on the roles. When constructing their
comparison strings, Amy and Bob position their bits based on the role
they were playing and the role their peer should have been playing.
This further thwarts Mallory's efforts to play the same role (Amy or
Bob) in both exchanges.

Conclusion

Amishare's technique for authenticated key exchange relies
fundamentally on "signing" the public keys with randomly-generated
single-use Verification Codes. The security comes from having both
parties provide "signatures" before they provide the codes used to
create the signatures. Their computers check the signatures, which is
trivial for a computer, but not by itself secure. To make the
protocol secure, the users identify each other and compare the
Verification Codes via an authenticated channel. The security value
of this human-compared data is maximized by using it to "pre-sign" the
computer verified data.

In comparison to the protocols above (in particular M1 and M2),
Amishare's protocol achieves a high level of security while requiring
only a minimum amount of data to be manually verified.

The protocol has many applications. In the examples above, "Amy" and
"Bob" were two people and their computers. They could however be any
two devices. For example, they could be two firewalls that want to
exchange keys for a VPN, or two wireless devices that want to securely
exchange data. In these cases, the devices would perform the
protocol, then their human operators would manually compare
Verification Codes.

The protocol is also scalable. If more security is required, a larger
number of bits can be compared. If less security is required, the
users themselves can decide to compare only part of each Verification
Code, for example, the first 25 bits.

Finally, the protocol is flexible. It allows an unlimited amount of
data to be exchanged and authenticated. In the examples, public keys
were exchanged. However, the data could be anything. In addition, if
only one-way authenticated transmission is required, one of the
parties could simply "sign" a small amount of arbitrary data that is
immediately discarded.

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. The only requirement is that the users have
some method of identifying each other and comparing two short strings
over a channel that an attacker cannot tamper with without being
detect.

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.



Relevant Pages

  • Re: bootstrapping a secure channel
    ... > Enclosed is a paper discussing a protocol for authenticating the ... > exchange of public keys. ... The primary use for this protocol would be ...
    (sci.crypt)
  • New Method for Authenticated Public Key Exchange without Digital Certificates
    ... exchange of public keys without using digital certificates. ... The primary use for this protocol would be to bootstrap a secure ... bootstrap a secure channel. ... These are some methods currently used to exchange and authenticate ...
    (sci.crypt)
  • Re: bootstrapping a secure channel
    ... compare Verification Codes over an authenticated channel." ... > a trusted third party to broker the public keys. ... > wireless devices that want to exchange data. ... > information over an authenticated channel, ...
    (sci.crypt)
  • Re: Certificates
    ... >Certificate Authority? ... Yes, the CA's sign the public keys they choose to trust with their own, ... of confidnetiality in exchanging information over an untrusted channel, ...
    (comp.security.misc)
  • Re: Certificates
    ... >Certificate Authority? ... Yes, the CA's sign the public keys they choose to trust with their own, ... of confidnetiality in exchanging information over an untrusted channel, ...
    (comp.security.ssh)