Triple Diffie-Hellman (ECC compatible). Any attacks against it?

325 views
Skip to first unread message

C01D B100DED

unread,
Aug 18, 2002, 12:58:47 PM8/18/02
to
Here's the scheme for establishing a secure channel I have
implemented. I've never seen anything like that in literature, that's
why I'm curious if anyone can see some attacks against it that I
don't. The beauty of this protocol is that although it only relies on
good old Diffie-Hellman out of all the asymmetric algorithms, it
assures perfect forward secrecy and more...

First we have two parties that have pre-exchanged their public keys
(for the sake of simplicity let's assume that it's 512-bit Elliptic
Curve Diffie-Hellman):

Side 1 generates a random number Local_Sec, multiplies it by a
randomly chosen point known to both parties, the resulting Local_Pub
is then sent to Side 2, Side 2 calls it Remote_Pub.

Side 2 generates a random number Local_Sec, multiplies it by a
randomly chosen point known to both parties, the resulting Local_Pub
is then sent to Side 1, Side 1 calls it Remote_Pub.

From now on:

Side 1 has its own Local_Sec, Local_Pub and Remote_Pub
Side 2 has its own Local_Sec, Local_Pub and Remote_Pub

On every connection:

Step 1. Both parties send to each other their static public keys,
those keys are saved on the very first connection during the software
installation and verified on every subsequent connection to prevent
unnecessary exponentiations if the keys are unacceptable. Both parties
can also be identified by their static public keys.

Both public keys could be pre-exchanged over a different channel prior
to the first connection and/or their fingerprints could be verified to
ensure that there's no MITM attacking the system that hasn't been
installed yet.

Both parties also include in the packets sent in Step 1 their dynamic
public keys they have generated for that particular session:

Side 1 generates a random number A_sec, multiplies it by a randomly
chosen point known to both parties, the resulting A_pub is then sent
to Side 2, Side 2 calls it B_pub.

Side 2 generates a random number A_sec, multiplies it by a randomly
chosen point known to both parties, the resulting A_pub is then sent
to Side 1, Side 1 calls it B_pub.

At this point:

Side 1 has its own Local_Sec, Remote_Pub, A_Sec, B_Pub
Side 2 has its own Local_Sec, Remote_Pub, A_Sec, B_Pub

Now both sides perform the same calculations:

A_Sec * Remote_Pub -> A
Local_Sec * B_Pub -> B
A_Sec * B_Pub -> x

As the result both sides have the same three A, B and x, only A and B
are swapped. Thus they concatenate those 3 parts into two keys:

AxB and BxA

Side 1's AxB should match Side 2's BxA,
Side 2's AxB should match Side 1's BxA.

Both resulting 1536 bit long trikeys then get hashed into two
different 256-bit AES session keys for traffic encryption.

Step 2. In the second step both sides simply send hashes of their BxA
keys to the other side encrypting them with their AxB keys, the other
side decrypts it with its BxA key and compares the result with the
hash of its AxB key. If they match, both parties immediately know that
both their session keys are correct on both sides.

Both Side 1 and Side 2 send and receive data in both steps
simultaneously, resulting in only 2 subsequent transfers in both
directions. Step 2 can be avoided if the upper layer protocol has its
own data validity verification.

Hashing makes the choice of the way of concatenation and the choice of
positions of the parts A, B and x irrelevant, as long as A and B are
swapped for both keys. Different ways to concatenate all 3 parts can
result in more session keys if necessary.

Summary:

Drawbacks: 3 modular exponentiations or elliptic curve multiplications
on every connection. I use Shamus Standard Curves from
http://indigo.ie/~mscott. For ECC-512 it only takes about 80ms per
point multiplication on 600MHz without any precomputations. Although I
see a quarter of a second per connection as more than acceptable for
my application as connections are kept alive.

Benefits: Part x ensures that even if both secret keys are stolen,
intercepted past or future traffic still cannot be decrypted in either
direction without the MITM attack. Parts A and B ensure that to run
the Man In The Middle attack, both secret keys are required, one will
not suffice.

Does anyone see the above scheme interesting at all? Stupid?
Vulnerable? Patentable? ("Doh!") Patented? Seen it before? Where?

Yarrow Charnot

PS: Please don't shoot me! I have nothing against certificates, PKI,
ASN1, digital signatures, RSA, El-Gamal, SSL, etc, just thought that
Keeping It Simple could be just as secure... :)

David Hopwood

unread,
Aug 18, 2002, 1:51:37 PM8/18/02
to
-----BEGIN PGP SIGNED MESSAGE-----

C01D B100DED wrote:
> Side 1 generates a random number Local_Sec, multiplies it by a
> randomly chosen point known to both parties, the resulting Local_Pub
> is then sent to Side 2, Side 2 calls it Remote_Pub.
>

> Side 2 generates a random number Local_Sec, [rest snipped]

You're reusing variable names. Write it out again without re-using
variable names, and preferably a bit more concisely.

Incidentally, double DH exchanges using both static and ephemeral public
keys are a well-known technique (for example see the "DH2" schemes in [1]),
although I couldn't tell whether what you wrote exactly matches a
published protocol. There seemed not to be any checks against small
subgroup attacks.


[1] <http://P1363:Mars...@grouper.ieee.org/groups/1363/tradPK/P1363/draft.html>
(The final standard, IEEE Std 1363-2000, was not significantly different
from draft D13.)

- --
David Hopwood <david....@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPV/ebzkCAxeYt5gVAQEvJQf7B5cGyG9mAGsO0HVCFqdwrFkN9c7RJrxO
EPcg3wEepnxs3aTowxJ2YTStxwasfyki0mEW3rrW9FVKtD+yf9GOO7u25YGq9SGN
xGacfUKBwR15qV5HonjoZge0unIrHZAvlgwKrL7qOTcnB6t7rTXbPw5xSkP1Bun/
hTP1Y/pfaouBgsPLwECbC4wnD/v1ErmRQ9swZQk75BA3/6D7ZiBZivQ0bg9DJ3YF
QDFI0sYbffk0Zj3v7vST86tMw01Xvx2XL1tM83JmVqdg9VHmE7DnN/FFI9R6Debd
Uyhly0WEBfIr4TnyGk2qh5cX0e9Ukf1Zs48vqAc9P1d7yT1ACDdMeA==
=djer
-----END PGP SIGNATURE-----

C01D B100DED

unread,
Aug 21, 2002, 9:04:42 PM8/21/02
to
Thank you, David, for such a quick response! I appreciate that at
least one person commented on my posting.

> You're reusing variable names. Write it out again without re-using
> variable names, and preferably a bit more concisely.

I specifically described it is the clearest way to see it from the
implementor's point of view. If you see it as confusing, I can only
apologize. I'm surprised that it's the only complaint so far. In the
document you're referring me to, all the protocols are described in
the same way. I simply voided the ' signs on the variables names using
words instead to make it more readable. I'm not going to rewrite my
posting because of that. It's not a standard specification and not a
white paper.

> Incidentally, double DH exchanges using both static and ephemeral public
> keys are a well-known technique (for example see the "DH2" schemes in [1]),
> although I couldn't tell whether what you wrote exactly matches a
> published protocol. There seemed not to be any checks against small
> subgroup attacks.

Okay, I'll be a little more specific about that to clarify something.
I'll also use their language. In DH2 described in IEEE P1363, each
side computes shared secret values z1 from s and w' (9.3.2.6) and z2
from u and v' (9.3.2.7), both are hashed together. In my scheme there
are three shared secrets computed in the following way: z1 from s and
v', z2 from u and w' and z3 from u and v'. Two keys are derived from
those three values hashed together, having z1 and z2 swapped to make
keys K1 and K2 match on both sides. I also didn't mention that in my
implementation the entire key exchange is encrypted using a shared key
z0 derived from s and w' once and stored with w' to avoid unnecessary
exponentiations if either side doesn't possess its static secret key.
It's done to prevent Denial of Service attacks as exponentiations are
slow and can easily consume the entire CPU power. [Yes, of course
decrypted data validity and public key values validity are ensured, no
silly small subgroup attacks.]

Did that make more sense to you? Here's more:

The section D.5.1.3 mentions a more similar protocol to mine, where
the static secret and the ephemeral public keys are combined, but they
are correct that with only two shared secrets derived from two keys
that way, an unknown key share attack can be mounted (See [MQV95]).
There is another protocol similar to mine, called Song-Kim key
agreement. The similarity is "ay + xy + bx", however it's K = g^(ay +
xy + bx) mod N, while in my protocol it's K = H(g^ay mod N, g^xy mod
N, g^bx mod N).

Anyway, in DH2, once the first (static) secret key of either of the
sides is known to the attacker, the attacker can mount the man in the
middle attack. In my scheme possession of both static secret keys is
required to do that. I'd say it's the major and probably the only
major difference.

Thank you for your time! I appreciate your feedback.

Reply all
Reply to author
Forward
0 new messages