The SNAKE Key Exchange creates a key from multiple (1 or more) DH Key Exchanges which are performed concurrently using a prime modulous based on the shared weak secret.  SNAKE is unpatented and public domain and may be used without restriction.

U         User or client identifier
P         hash of passphrase
X[0..n-1] set of n large random numbers (Client)
Y[0..n-1] set of n large random numbers (Server)
R         a large random number (Client)
S         a large random number (Server)
f(k,P,R)  a function which constructs a large safe
          prime number. k is a small integer 0..n-1
g         the generator, a fixed public value, and a
          primitive root for all f() values
K         shared session key
H()       crypto hash function (SHA1,TIGER,or similar)
E[K](Z)   means 'encrypt Z with key K' using a block
          cipher
^         means 'to the power of'

Message1: Client --> Server (client chooses R, X[0..n-1])
    U, R, g^X[0] mod f(0,P,R), g^X[1] mod f(1,P,R), ...

Message2: Server --> Client (server chooses S, Y[0..n-1])
    S, g^Y[0] mod f(0,P,R), g^Y[1] mod f(1,P,R), ...

Message3: Client --> Server
    E[K](S)
    where K=H(P,Message1,Message2,
              (g^Y[0] mod f(0,P,R))^X[0] mod f(0,P,R),
              (g^Y[1] mod f(1,P,R))^X[1] mod f(1,P,R),
              ...)

Message4: Server --> Client
    E[K](R)
    where K=H(P,Message1,Message2,
              (g^X[0] mod f(0,P,R))^Y[0] mod f(0,P,R),
              (g^X[1] mod f(1,P,R))^Y[1] mod f(1,P,R),
              ...)
NOTES:

n    is the number of SNAKE 'parts', it is a small fixed
     public integer > 0.
g    must be in the range sqrt(max f())+1 .. min f()-1,
     and a primitive root for all f().
X[k] values must be chosen such that g^X[k] mod f(k,P,R)
     is not 0,1 or g, and is < min f(). The Server must
     check that the values sent by the Client are valid.
Y[k] values must be chosen such that g^Y[k] mod f(k,P,R)
     is not 0,1 or g, and is < min f(). The Client must
     check that the values sent by the Server are valid.

When the Server receives Message3 it authenticates the
Client by decrypting and checking S using the shared
session key K. If the decrypted value for S does not
match the vaue sent in Message2, then authentication
fails and Message4 should not be sent.

When the Client receives Message4 it authenticates the
Server by decrypting and checking R using the shared
session key K. If the decrypted value for R does not
match the vaue sent in Message1, then authentication
fails.

After the key exchange is complete the session key can
be used to encrypt all data in both directions, or as
an initializer for some other encryption mechanism, such
as a stream cipher.

SNAKE can be applied to any two entities which wish to
do mutual authentication, they are not required to be
'clients' or 'servers'.

Efficient Creation Of A Safe Prime Modulous

The function f(k,P,R) which constructs the safe prime
modulous for each SNAKE part is obviously key to the
efficient implementation of a SNAKE key exchange.

A simple mechanism to do this would be to seed a
Pseudo Random Number Generator with H(k,P,R) and
find the next higher safe prime number. However,
although this would undoubtedly work and would
have the benefit of allowing effective SNAKE key
exchanges with only one part, even using advanced
probabalistic techniques for finding primes would
result in a very computationaly expensive (and slow)
implementation.

The fastest mechanism would be to simply have a lookup
table which translated H(k,P,R) into a suitable large
safe prime.

Since P is weak, we can assume that it has only a
small number of possible values, say 2^36 (~64 billion).

Therefore if we define f(k,P,R)=m[H(k,P,R)%4096]
where m[] is a table of 4096 suitable safe prime
numbers, we will allow for 4096^3 (==2^36) values
for P.

Similarly we could use more SNAKE parts and a smaller
table, or less SNAKE parts and a larger table.

Also, storing a table of a few thousand large prime
numbers does not require as much space as one might
think.

The table needs to store large safe primes which
share have a common primitive root g (the generator).

One mechanism to find these values is to choose
primes such that p=g+(x^2) where x is a positive
interger >= 4.

This guarantees g is a primitive root of p since...

   1. For a strong prime p=2q+1, Z*_p is of size
      2q and with subgroups of order 2 and q.
   2. The subgroup of order q is the set of quadratic
      residues.
   3. The subgroup of order 2 is {-1,1}.
   4. x^2 mod p is a generator of the subgroup of
      order q (so when x < sqrt(p-1), x^2 itself is
      a generator of the subgroup of order q).
   5. -1 is a generator of the subgroup of order 2.
   6. -1 is not a square mod p (or else you'd have an
      element of order 4, and thus a subgroup of size 4)
   7. -(x^2) generates all the quadratic residues
   8. -(x^2) generates -1
   9. Any element that generates more than q elements,
      must generate all 2q elements.

So, if we need a table of b bit primes, we can simply
choose an arbitrary g=2^(b-1)+C where C is some
positive integer < 2^b, and then populate our table
by finding safe primes p=g+(x^2) for x>=4.

However, we could simply store the table of x values
rather than full primes and the reconstruct the
primes on the fly whenever we need them. For prime
tables <= 4096 elements containg primes <=4096 bits,
this would reduce each table element to 4 bytes or
less.

A simpler approach which is equally effective in
most situations is to store the offsets for each
prime from an arbitrary common base (possibly even g).

Further reductions can be gained by using relative
offsets between table entries and so on.

Consequently it should be easy to create an
implementation of a f(k,P,R) function which can
efficiently construct a suitable safe prime number
and require a very small amout of memory (<16Kb).