[OTR-dev] OTR, keyservers, MITM, etc.

[chris-tuchs at hushmail.com]

Ok, so first off, I apologize that I, a non-cryptographer, am
going to suggest a cryptographic protocol.  It probably stinks,
and I hope you can help me make it better.  In fact I hope you
can say, "Oh yeah, they solved that problem already, go read
Crypto 04 pages xxx-yyy."  I would very much prefer to throw
away my proposal and use something that's had some real review
by qualified cryptographers.

The Problem:

In Second Life it is not uncommon to meet someone for the first
time and want to IM with them.  I am not as familiar with other
IM systems, but I can imagine it could happen that two people
meet on some other IM system.  Since there is no shared history
neither of the SMP based authentication systems seem useful when
given a cursory glance.  But we still want to eliminate the
possibility of a man in the middle, or in fact any third party
to the conversation.  Manual fingerprint verification seems the
only solution.

The real world user:

But my experience with Second Life users of OTR is that of the
few who understand what is expected of them most aren't willing
to actually do the work.  Instead of exchanging key
fingerprints, most users will just mark their buddy
authenticated to make the warning go away.

In actuality, in Second Life, even the question "What color
shirt am I wearing" can be used with SMP to eliminate most
automated man-in-the-middle (MITM) attacks.  On other IM systems
even the laughable "How many letters are in the word 'four'?"
has some value for eliminating automated MITM.

One obvious solution is to use the pgp keyservers along with
some trust computation.  After all, DSA is DSA and there is no
reason we couldn't settle on a canonical notation for usernames
and IM systems.  Then it is just a small matter of writing some
code to get OTR keys and signatures into a format that the PGP
keyservers will be happy with.  But...

Remember the user I am dealing with.  They aren't likely to take
the time to do a SMP based authentication in the first place.
So even if I cleverly put in stuff to generate and post
signatures the quality of the signatures will be very low.

I discussed this with another GreenLife developer and we cooked
up this protocol to lower the probability of undetected MITM
attacks.  I would like feedback about this proposal.  As you
will see there is nothing specific to Second Life in the
proposal and it could be added to all OTR implementations.  It
essentially automatically does fingerprint verification over
multiple untrusted communication channels.  I use the word
"keyserver" below, but I would prefer a better term.  Feel free
to sugest one.

The Proposal:

Imagine a small set of, untrusted, OTR keyservers.  When Alice
establishes an unverified conversation with Bob on protocol P
her software picks a random number R, then posts to the
keyservers a message consisting of <name-hash, key-hash,
random-number> where name-hash is HASH(Alice-user-name |
P-protocol-name | Bob-user-name); key-hash is
HASH(Alice-key-fingerprint | Bob-key-fingerprint); random-number
is a nonce with no special meaning; and | means the
concatenation of utf8 encoded character strings.

I assume there are canonical user names, and a canonical order
to the names.  The first name given to HASH is the earlier in
the sort order.  For example, "Alice Avatar" comes before "Bob
Avatar" so HASH("Alice Avatar" | "SecondLife" | "Bob Avatar")
would be used by both Alice and Bob.  The same order is used for
the key fingerprints.  In this case HASH(Alice-key-fingerprint |
Bob-key-fingerprint).

In response to a message of the form <N, K, R> a keyserver
replies with all the messages <N', K', R'> posted recently that
have N' == N.  If Alice's software finds that her post is
present, all the key hashes match the one her software computed,
and at least one other post is present, then the odds of a MITM
attack are lowered.  The man in the middle attacker would have
to be between Alice and Bob as well as between Alice and all the
keyservers.  (I will consider a keyserver controlled by an
attacker to be the same as an attacker between a user and the
keyserver.)  With a few independently operated keyservers this
becomes impractical.  Naturally Alice's software may beat Bob's
to the keyserver, so not finding a post from Bob just means
Alice's software has to post again after a short pause.  And
since there are actually three parties to this protocol,
including the man in the middle, Alice's software would do well
to check back even if everything looks good on the first check.

I have a few concerns about the proposal.  It can confirm that
Alice had a conversation with Bob, though presumably this
information can be found in the logs of the IM system's servers.
Either Alice or Bob can collude with a keyserver to reveal the
IP address used by the other to post, though using an http proxy
should help mitigate this privacy threat.  It is open to the
obvious denial of service attack of posting messages with valid
name-hashes and multiple different values in the place of
key-hashes.

Most importantly, I am not a 'real cryptographer' and am not
really competent to create and analyze protocols.  I am sure a
real cryptographer can generate a better proposal which takes
advantage of multiple untrusted communication channels.  Never
the less, I feel compelled to do something to help protect the
users in Second Life from their ignorance and apathy.

Chris

Post scripts:

I can make DOS harder by including time in name-hash, and
forcing some property of the posts <n, k, r> such as r ===
HASH(r | k | n) mod 256.  This just makes it expensive to
compute false entries, though still reasonably fast to check if
an entry 'paid the computational tax.'  This would prevent
'blanket' DOS but not a pinpoint DOS on a particular pair of OTR
users.

I considered a number of other things to post to the keyservers,
and turned them down.  This is an abbreviated list.

I considered the pgp keyserver and trust computation, but
rejected it since I don't think our users will invest the time
and effort to properly use and understand such a system.

If Alice posts <Alice-name, Alice-key-fingerprint>, the
keyservers can build lists of <ip, user-name>.  The keyservers
can build lists of who likely talked to whom since Alice's query
must return Bob's post of <Bob-name, Bob-key-fingerprint>.  DOS
attacks would wipe out one user's ability to use the system
rather than just blocking one pair from communicating.

If Alice posts <Bob-name, Bob-key-fingerprint>, the keyservers
can still build weak lists of who talked to whom since Alice's
post includes Bob's name and her query must return his post of
her key.  DOS attacks would wipe out one user's ability to use
the system.

If Alice posts <name-hash, Alice-key-fingerprint> or <name-hash,
bob-key-fingerprint> the servers just have longer identifiers to
use when building lists of who talks to whom, and which IP goes
with which person.

If Alice posts <name-hash, key-hash>, Alice will be unable to
see if Bob is posting or not.  For the protocol to work, at
least two parties must be posting under the same name-hash at
about the same time.

If Alice's post include a signature of anything, the servers can
build even stronger evidence of who talks to whom and/or who
uses which IP.

Philosophy -- is it MITM or not?

If the owner of the IM system wanted to pretend to be Bob and
communicate with Alice, and if Bob were not trying to
communicate with Alice at the time, using this protocol Alice
could only determine that there is no third party to the
conversation.  Since Alice has no way of distinguishing Bob from
any other person, she has no way to detect that "Bob" is an
imposter.  This isn't actually a problem with the MITM
detection; it is inherent in meeting a new person, you don't
know who they are.  Later if Alice did talk to the real Bob she
would detect that Bob's key had changed or that there was a MITM
attack underway.