Saturday, December 02, 2006

Diffie-Hellman Example

Johannes recent comment hinted at alternatives to Diffie-Hellman in OpenID for situations where the shared-secret nature of DH would be a limitation - specifically mentioning the potential relevance of non-repudiation.

Brian Ellin has previously discussed Diffie-Hellman in the context of OpenID but, for me, real numbers make things real. So, a work through of how an OpenID RP and IDP would use Diffie-Hellman alorythm to generate a secret that could be used for securing OpenID protocol messages.

p = 7 (a small prime number)
p- 1 = 6
g = 2 (OpenID default)

RP chooses x = 5 (smaller than p - 1)

X = g ^ x mod p
X = 2 ^ 5 mod 7
X = 32 mod 7
X = 4 (the remainder when you divide 7 into 35)

IDP chooses y = 4 (smaller than p - 1)

Y = g ^ y mod p
Y = 2 ^ 4 mod 7
Y = 16 mod 7
Y = 2 (the remainder when you divide 7 into 16)

RP and IDP exchange X and Y in the open (no need for secrecy)

RP calculates IDP calculates

s = Y ^ X mod p s' = X ^ Y mod p
s = 2 ^ 4 mod 7 s' = 4 ^ 2 mod 7
s = 16 mod 7 s' = 16 mod 7
s = 2 s' = 2

Both RP and IDP have calculated the same secret, namely the integer 2, based on information publicly shared between them. They can then use this secret to sign and/or encrypt subsequent communications. OpenID refers to the establishment of this secret as 'association'.

Any eavesdropper, armed only with the public info shared between RP and IDP, would be unable to calculate the secret (if the integers were chosen appropriately large) - this because only both RP and IDP have the necessary additional info (the choices they made but not shared). It's Diffie-Hellman's support for establishing secure communication without any existing trust relationship (excepting SSL) that makes it relevant to OpenID's promiscuous providers.

But, because RP and IDP use the same secret, it doesn't allow the provenance of any particular message to be established. Even if 'signed' with the secret, it could have come from either of the two.

It's worth mentioning that nothing precludes a SAML SP and IDP using the same technique, i.e. establishing a shared secret through Diffie-Hellman and then using it to protect SAML protocol messages.

3 comments:

Anonymous said...

Hi Paul,
A couple of errors in ur post I thought i will bring it to your attention.

There are errors in the section
-------------------------------
RP calculates IDP calculates

s = Y ^ X mod p s' = X ^ Y mod p
s = 2 ^ 4 mod 7 s' = 4 ^ 2 mod 7
s = 16 mod 7 s' = 16 mod 7
s = 2 s' = 2
-----------------------------------
You have used only the public keys X & Y to calculate the Shared secret( s or s').That is incorrect.

The correct representation is :
----------------------------------
RP calculates IDP calculates

s = Y ^ x mod p s' = X ^ y mod p
s = 2 ^ 5 mod 7 s' = 4 ^ 4 mod 7
s = 32 mod 7 s' = 256 mod 7
s = 4 s' = 4
----------------------------------


The other error is just a minor typo.

Instead of:
X = 32 mod 7
X = 4 (the remainder when you divide 7 into 35)

it should read:
X = 32 mod 7
X = 4 (the remainder when you divide 7 into 35)

Thanks
Sarvesh

Anonymous said...

oops,it is
X = 4 (the remainder when you divide 7 into 32)

Paul Madsen said...

Thanks Sarvesh - for both catches!

And I can't tell you how many times I scanned between the two lines looking for what was different :-)

Paul