Tatebayashi, Matsuzaki, and Newman (TMN) proposed the following protocol, which enables Alice and Bob to establish a shared symmetric key K with the help of a trusted server S. Both Alice and Bob know the server’s public key Ks. Alice randomly generates a temporary secret KA, while Bob randomly generates the new key K to be shared with Alice. The protocol then proceeds as follows:
Alice ? Server Ks{KA}
Bob ? Server Ks{K}
Server ? Alice K⊕KA
Alice recovers key K as KA⊕(K⊕KA)
To summarize, Alice sends her secret to the server encrypted with the server’s public key, while Bob sends the newly generated key, also encrypted with the server’s public key. The server XORs the two values together and sends the result to Alice. As a result, both Alice and Bob know K.
Suppose that evil Charlie eavesdropped on Bob’s message to the server. How can he with the help of his equally evil buddy Don, extract the key K that Alice and Bob are using to protect their communications? Assume that Charlie and Don can engage in the TMN protocol with the server, but they do not know the server’s private key.
