From: Kent Briggs <72124.3234@compuserve.com>
Date: Sat, 9 Dec 95 12:48:00 PST
To: cypherpunks <cypherpunks@toad.com>
Subject: Diffie-Hellman with Blowfish
Message-ID: <951209204827_72124.3234_EHJ183-1@CompuServe.COM>
MIME-Version: 1.0
Content-Type: text/plain


I am working on a program that will use Diffie-Hellman with Blowfish to create a
public-key encryption system similar to the way PGP uses RSA and IDEA.  This
system would not have the digital signature feature that
PGP has, however.  I invite comments on any security problems that I might have
overlooked.  Bruce Schneier briefly mentions this idea on p. 515 of Applied
Cryptography (2nd ed): Key Exchange Without Exchanging Keys.

Key Generation
--------------
First, users select a private key passphrase.  The passphrase is case sensitive
and from 8 to 50 characters in length.  A random 32-bit salt is generated from
timed keystrokes.  The salt is appended to the passphrase and run through an
SHA-1 hash.  The output is a 160-bit value, x.

The 1024-bit public key "y" is calculated:
y = g^x mod p     (^ denotes exponentiation)

p is a 1024-bit strong prime constant that does not change. g is the generator
for that prime and is always 2.

The KeyID for the public key is the 32-bit salt.  The user publishes the public
key and KeyID values.  The key should be certified to prevent a man in the
middle attack.  The user imports public keys from others and places them on
their public key ring.

Note that there is no private key ring.  I could have used the PGP method and
made the private key a random number and then encrypted that number with a
passphrase.  This would be more secure but I was worried about users deleting
their private key file.  The 32-bit salt will discourage a pre-computed
dictionary attack.  An attacker would have to run over 4 billion SHA's and D-H's
and store the result for every passphrase in their dictionary.  To discourage a
dictionary attack on a specific public key, I will include a tutorial on how to
choose a secure passphrase.

Encryption
----------
The program will generate a 160-bit random private session key "r" based on
timed keystrokes by the user.  A 1024-bit public session key "z" is calculated:
z=g^r mod p

z is stored in the file header.

For each recipient, a "k" value is calculated using the recipient's public key:
k=y^r mod p

The session key r is now encrypted for each recipient by running each k through
an SHA-1 hash and xoring the output with r: k'=SHA(k) xor r

For each recipient the 160-bit k' value is stored with the recipient's 32-bit
KeyID value in the file header.  Each additional recipient adds 24 bytes to the
file header.

The plaintext is then encrypted with Blowfish in CBC mode using the 160-bit r
value as the key.  r is then discarded.

Note that I use the same r key for the Blowfish session key and
the Diffie-Hellman private key.  I could have generated a
separate r1 for Blowfish and an r2 for D-H but I don't think
this is necessary.

Decryption
----------
The public session key z is retrieved from the file header.  Each recipient
matches their KeyID with one of the KeyIDs stored in the file header.  From this
match they get their particular k' value.  They enter their private key
passphrase, append the KeyID salt and run it through an SHA-1 hash to get x.  k
is then calculated: k=z^x mod p

The original private session key r is decrypted: r=SHA(k) xor k'

The ciphertext is decrypted using Blowfish with key r.

=======================================================

Does anyone see any obvious security problems that I might have overlooked?

Kent Briggs
kbriggs@execpc.com
CIS: 72124,3234