Re: Simple authenticated channel

From: Matthijs van Duin (efh84df_at_yahoo.com)
Date: 10/15/03 

Date: 15 Oct 2003 06:09:03 -0700

Paul Rubin <http://phr.cx@NOSPAM.invalid> wrote:
> efh84df@yahoo.com (Matthijs van Duin) writes:
> > Ehm, no, I was merely mentioning a pre-shared secret key as a
> > theoretical possibility, but in practice public key crypto will
> > ofcourse be used.
>
> Ok. Why don't you want to use SSL?

Several reasons:

1. I'm very much interested in cryptography, and hope to develop some
experience. No money depends on the security of this protocol, so I
can afford to experiment.

2. SSL does much much more than I need at this point, and is
consequently ridiculously heavy and complex for the simple goals I've
set out.

3. There are also some implementation details that make use of a lib
like OpenSSL inconvenient.

> Cooking your own protocols is almost always a recipe for bugs.

I'm very much aware of the dangers of creating a cryptographic
protocol, which is why I've been very careful and conservative in its
design.

I have also continued my efforts to analyze it. Below I've included
an updated description, made a bit more concrete by filling in actual
protocols (in this case, I assume Bob uses a DH keypair), followed by
my updated analysis.

The conclusion of the analysis is that if the cryptographic primitives
used are secure, then the protocol meets the security objectives. If
you can find flaws in the analysis, I'd appreciate to hear about them.

Bob's public key consists (at least) of:
  1. The DH parameters p, q, g such that:
       p and q are prime and q divides p-1
       1 < g < p and g^q = 1 mod p
  2. A public value u = g^v mod p (where v is Bob's secret value)
  3. Identification of the hash algorithm H used (should be SHA-256)

It is assumed Alice already has an authetic copy of Bob's public key.

The protocol is initiated by Alice establishing a TCP connection with
Bob. Alice and Bob then exchange messages N_1, N_2, etc; where N_i is
sent by Alice for odd i, and by Bob for even i.

For all i, N_i = M_i || T_i where M_i is the actual message content
and T_i is the authentication tag. T_i = MAC_k(C_0 || M_1 || C_1 ||
.. || M_i || C_i), where k is the authentication key and C_i is extra
information used to avoid misinterpretation of the M_i. For example,
C_0 should contain an identification of the purpose of the channel, to
ensure Bob has the correct notion of why Alice is talking to him.

Note that the encoding of C_i and M_i should be such that the string
C_0 || M_1 || C_1 || .. || M_i || C_i can be split unambiguously into
the separate M_i and C_i, and also such that the incoming data can be
split into M_i and T_i. A simple tag-length-value encoding with an
end-of-message marker will be used to ensure this.

Alice constructs the authenticated channel without Bob's help (using
his public key though), and will place in M_1 all information needed
to enable Bob to construct his end of the channel.

The steps taken by Alice:
  1. Select x randomly from { 1, .. , q - 1 }
  2. y = g^x mod p
  3. k = H(u^x mod p)

Alice also chooses the MAC, which should however always be
HMAC-SHA-256. The value y and identification of the MAC used are
placed in M_1. The chosen MAC and secret key k are then used for
authentication of all M_i as described above. A "fingerprint" of
Bob's public key should be put into C_1 to ensure Alice and Bob really
are talking about the same key.

Bob can, after receiving M_1, calculate k = H(y^v mod p).

OK, now for some analysis.. (I assume an active attacker that has
Bob's public key, and can see and manipulate all traffic between Alice
and Bob)

Suppose Alice or Bob receives a message M_i with authentication tag
T_i. Now for the message to be accepted as authentic, T_i must equal
MAC_k(C_0 || M_1 || C_1 || .. || M_i || C_i). This means (if the MAC
is secure) that M_i must have been produced by a party who holds k and
intended M_i to be a response to the message chain M_1 .. M_(i-1).
Determining k from the T_i should not be possible if the MAC is
secure.

Now, Alice generates an unpredictable k for each session, and Bob's
secret key is necessary to generate k from y (unless DH is broken
ofcourse). The attacker therefore does not hold k, and hence its only
avenue of attack is to somehow reuse T_j for j <= i. However only T_i
is usable to authenticate a message in response to M_1 .. M_(i-1), and
that tag only authenticates the original M_i sent by Bob. Therefore
Alice will only accept messages that were authenticated by Bob, and
Bob must have seen the same M_1 .. M_(i-1) as Alice has.

The attacker has slightly more room to play on Bob's side: Bob
derives k from M_1, and hence replay of a sequence of messages M_1 ..
M_i of an earlier session is possible. The attacker however still
does not have k and cannot influence M_i where i is even (since these
are generated by Bob), hence the replay of this sequence only works as
long as Bob keeps giving the same replies it did when the message
exchange originally took place.

This 'attack' is quite uninteresting for two reasons:
1. The replayed M_1 through M_i is just a normal communication session
between the attacker and Bob. The attacker is just an unauthenticated
as Alice is, so Bob doesn't even care.
2. Any deviation by Bob from the original M_i (for even i) will cause
the attacker to be unable to send further replies.

If desired, Bob may simply include a nonce in M_2 to guarantee that
the attacker can only replay M_1 of any previous session.

The previous paragraphs should hopefully illustrate that, with the
minor exception given above, an attacker who does not have Bob's
private key and can not break the crypto primitives (DH, SHA-256,
HMAC-SHA-256) is unable to present Alice or Bob with a message that is
not the one intended by the other party, without causing the
authentication to fail. This means that an active attacker can only
deliberately cause authentication to fail or block a message entirely,
either of which causes denial of service.

Note however that an active attack requires either causing Alice to
make the TCP connection to the attacker instead of Bob, or hijacking
the TCP connection between Alice and Bob. In either case, denial of
service is always possible, so this is not a flaw in my protocol.

A final approach would be to attack the interpretation of the
messages, rather than the messages themselves. This should be
prevented by the proper inclusion of context information (C_i). The
M_i and C_i together must leave no ambiguity in the meaning of M_i.

 - Matthijs van Duin

Relevant Pages

  • Re: PGP Lame question
    ... i think that given Q and Bob's public key, ... Q can be linked as encrypted to Bob ... can verify that Alice signed something somehow connected to Bob? ... Alice encrypts M with R and gets an output, ...
    (sci.crypt)
  • Practical improvement of DH-ElGamal scheme
    ... Improving DH-ElGamal public key encryption scheme can be done in ... For person Alice: ... Linking between 2 persons (Alice and Bob): ... Attacking this encryption scheme: ...
    (sci.crypt.research)
  • Re: GPG
    ... In a practical sense, only Bob may decrypt ... Alice on the way to Bob and prevent it from reaching Bob. ... Alice may encrypt the message with Bob's public key, ... the others) before issuing their certificates. ...
    (comp.os.linux.security)
  • Simple authenticated channel
    ... Alice and Bob, where alice already has some key that belongs to bob. ... MAC algorithm used. ... If we assume those are secure, the attacker should not ...
    (sci.crypt)
  • Re: Is SSL/TSL really secure?
    ... computers to record the private and public keys as they pass from my ... So both partners have such a keypair, say Alice has K1, K2 and Bob has ... Now Alice keeps K1 strictly secret - it's her "private key". ... with the public key of Bob, ...
    (comp.security.misc)