From: Bill Stewart <stewarts@ix.netcom.com>
Date: Sun, 10 Mar 1996 21:57:00 +0800
To: "A. Padgett Peterson P.E. Information Security" <PADGETT@hobbes.orl.mmc.com>
Subject: Re: Square pegs in round holes, matchmaking, corporate mailservers
Message-ID: <199603070738.XAA22980@ix2.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain


At 08:01 PM 3/5/96 -0500, "A. Padgett Peterson P.E. Information Security"
<PADGETT@hobbes.orl.mmc.com> wrote:
[>>Dimitris Tsapakidis <dimitrt@dcs.rhbnc.ac.uk> wrote:]
>  >Bob must find out whether Alice has declared (commited) her interest
>  >in him, if and only if he has declared (commited) his interest in her.
>  >Before he does so, he can at most know that a girl is interested in him.
>  >Another description: Bob and Alice can have a date if they both commit
>  >to each other. If only one commits, nobody will ever find out about it.
>  >- T is the trusted third party.
>  
>  Well if we *must* use D-H that is a way, but why do that ? Instead of
>  using a binary assymetric key, why not a triple ? (Just because I do not
>  know of any does not mean that one does not exist).
>  
>  Consider a function such that Alice has a key such that given a message M,
>  when encrypted by Alice may be manipulated by T such that Bob can decrypt
>  it. Similarly, Bob has a key that when manipulated by T' can be read by
>  Alice. Assymetric but not binary. The advantage here is that while "T"
>  is trusted by both, he/she/it/other is not able to read either message, 
>  rather acts as a catalyst.

Oh, that would work fine.  Let a, b, and t be Alice, Bob, and Trent's secret DH
keys, and g and p be the generator and prime (all math below is mod p.)
If Bob wants to talk to Alice, he sends Trent B = g**b, marked "For Alice",
optionally anonymously.  Trent calculates X = B**t == g**bt, and sends it to
Alice.
Alice calculates K = X**a == g**bat, calculates H = Hash(K) and 
posts it anonymously, or sends it to Trent to post or mail to Bob. 
If Alice wants to talk to Bob, she calculates A = g**a mod p,
sends it to Trent, optionally anonymously, marked "For Bob".
Trent calculates Y = A**t == g**at , and sends it to Bob.  
Bob calculates K' = Y**b == g**abt, calculates H' = Hash(K') and
notices that it's the same as the H he pulled off the net earlier.
Bob says "Oh, wow!  Alice wants to talk to me!", encrypts some lame drivel 
of a message M with key K'==K, and mails it to Alice if he knows her address
or posts it with Subject: H', which Alice receives.

Comments:
1) If Alice doesn't also want to talk to Bob, or Bob doesn't want to talk to
Alice,
they don't both come up with H == H', so they only know that _some_
shy person wanted to talk to them but not who it is.

2) Why does Alice reply to the anonymous message?  Maybe just because
she's free that evening, or maybe because it included a note with it
that made her think the sender is a Nice Guy.

3) Under this method, Alice, Carol, Eve, and Greta can get together and notice
that they've all gotten mail with keys X; they don't know who X is, but
they know he's interested in all of them and he's probably a trolling loser :-)
So they all dump him.  However, even though they know Bob's public key B,
they don't know t, so they can't tell from g**bt mod p that it's Bob,
so they can't send him email saying "Get lost, loser" without revealing their
identity.  So Trent is providing anonymity, and needs to be trusted.

Without Trent, you could do a two-way version of the protocol - if Bob wants to
talk to Alice, he posts Hash(A**b), and vice versa, but Alice can go evaluate
Hash(B**a), Hash(C**a), Hash(D**a), etc., for everyone in the phone book,
and find out that it was Bob.

4) If Bob wants to reduce the level of trust he needs to have in Trent,
he can create a bunch of keys b1, b2, b3, ...., bk in addition to b,
and use a different one for each note.  If I remember correctly,
he can often calculate the inverse of b, b1,... (??????)
So he sends Trent B1=g**b1, Trent sends Alice X1=B1**t == g**b1t,
Alice calculates K1=X1**a == g**b1at, H1=Hash(g**b1at), and posts/sends.
Since she's also interested in Bob, she does the same with key a,
so Trent gives Bob K'g**bat.  Bob calculates Z = K'**binv == g**at(b*binv) mod p
== g**at, and then calculates Hash(Z**b1), Hash(Z**b2), Hash(Z**b3)...,
and notices that H1 = Hash(X**b1) and says "Oh, it's Alice!"

On the other hand, this doesn't appear to work if Alice is also using
multiple identities.

5) If Trent is a really trustable guy, he can offer meeting services
for people who have unusual tastes, such as liking (Exon) and Duct Tape
and Political Party Z and (for bipartite variants) suppliers and consumers
of various substances.  So he could broker a list of (Exon)fans,
as long as the activity is not criminal enough to lead to subpoenas or
warrants for his transactions (if he keeps them) or his key t
(or t1, t2, t3... if he's running multiple lists.)

Dimitris's approach of using
Hash(message) could be used to exchange preference here as well.
If Alice checks the message for Hash("Duct Tape"), she can decide
that she and the unknown sender would be a great match, 
and if she hadn't thought to check Hash((Exon)) she wouldn't
know that Bob enjoyed that also.  So it's at least some privacy for
low-popularity unusual activities :-)

6) Of course, Trent really could be a front for Blacknet :-)  Or Trent's key
could be stolen and published, embarassing all his customers.

>  As to why you would want such a curiosity, consider a corporation with 80,000
>  mailboxes. It would be desirable for each person to be able to send E-Mail
>  to any other person but not desirable for each person to have to hold all
>  80,000 keys.  Given a triple (tertiary ?) function each individual would only
>  need their receive key and a "post office" transmit key.  On sending a
message,
>  it would be encrypted with a session key and the session key encrypted
with the
>  post office key.  The post office would have all 80,000 receive functions but
>  through the assymetic keying would only be able to convert the session
key to something
>  each intended recipient could decode but not be able to decode the message
>  itself.
  
>  This would meet both criteria (not key escrow but that is under "management")
>  D-H is wonderful but has difficulties with scalability.  If such a function
>  existed (has anyone looked ?) it would solve the problem.

Ah.  The method I described above doesn't solve your problem;
it just solves the original Shy-People's-Dating problem.
If your only concern is scalability, and you don't mind doing the
multiple-message handshaking Diffie-Hellman requires (<=SPD...),
you can use either a signed-keypart Diffie-Hellman or just use
PGP with the mailserver signing keys and keyserving.

PGP approach:  Bob has Public/private keys B/b, Alice A/a, Trent T/t, Sam S/s.
Trent is the mail agent at Alice's company, T is well-known.
Sam is the mail agent at Bob's company, S is well-known.
"Well-known" means that all the mail servers know each other's pubkeys.
If Alice and Bob both use the same postoffice, Sam==Trent, so it's simpler.

Bob to Sam:   Fetch Alice's Key
Sam to Trent: Fetch Alice's Key
Trent to Sam: A (signed by T)
Sam verifies  and caches A(signed by T), and already knows T.
Sam to Bob:   A (signed by T), T (signed by S).
Bob verifies  T's signature on A, S's on T. 
Bob to Sam:   To: Alice@trent.aliceco.com, PGPEncrypted(Message,A)
Bob either caches A, or caches T, or doesn't bother.
Sam to Trent:   (ditto)
Trent to Alice: (ditto)
Alice decodes the message.  If she needs Bob's keys, she asks Sam to fetch them.

So there's basically a key-fetching handshake, with Trent and Sam 
acting as CAs as well as keyservers, and then regular PGP.
Clean, simple, and all your regular tools work, except of course
that the keyservers use some database to store keys in instead of
a big hulking PGP keyring.

A Diffie-Hellman relative is a bit messier, because it's Diffie-Hellman.
Assume that the modulus and generator p and g are agreed on (e.g. Photuris's.)
Alice and Bob have their PGP public keys A, B.
Trent and Sam have their PGP public keys T and S, well-known.

Bob generates a random x, calculates X = g**x mod p.
Bob to Sam:     To: alice@trent.aliceco.com, X signed B.
Sam to Trent:   To: alice@trent.aliceco.com, X signed B, B signed S.
Trent to Alice: To: alice, X signed B, B signed S, S signed T.
Alice generates random y, calculates Y = g**y mod p, also K = X**y mod p.
Alice to Trent: To: bob@sam.bobco.com, Y signed A
Trent to Sam:   To: bob@sam.bobco.com, Y signed A, A signed T
Sam to Bob:     To: bob, Y signed A, A signed T, T signed S
Bob verifies Y, A, T, calculates K' = Y**x mod p == K.
Bob to Sam:     To: alice@trent.aliceco.com, Encrypted(Message,K).
Sam to Trent:   (ditto)
Trent to Alice: (ditto)
Alice decodes the message using K.  To make things simpler,
Bob might include Hash(K) or some other message identifier.

In this case, the key-fetching handshake is piggybacked along with the
DH key-exchange halves, and then Bob uses the jointly derived session key
to send a conventionally-encrypted message (which he _could_ use PGP for...)

#--
#			Thanks;  Bill
# Bill Stewart, stewarts@ix.netcom.com, +1-415-442-2215 pager 408-787-1281
#