DH Question

From: David Oxley (googlenews2_at_curzon-dax.co.uk)
Date: 06/28/04 

Date: 28 Jun 2004 04:08:21 -0700

Hi...

Alice goes on holiday and intends to send Bob a postcard at various
intervals. Where she is going, there are no 'phones etc., so she
cannot
enjoy an interactive key exchange session. She chooses to use a data
independent stream cipher, such as RC4, to encrypt the message in the
postcard.

Before she leaves to go on holiday, Alice and Bob agree (securely,
perhaps
in person or by means of a system such as SKEME) on a DH parameter,
g^x mod
p

Every time Alice wants to write a postcard, she
1) chooses a random y
2) calculates g^y mod p
3) g^{xy} mod p (ie the usual DH params).

She uses H(g^{xy} mod p) as the key for the RC4 encryption phase where
H is
a secure hash, say MD5. Somewhere on the postcard she writes the value
of
g^y mod p and, for completeness, g^x mod p.

4) y can now be discarded.

When Bob receives the postcard, he can use the g^y mod p shown on the
postcard together with x that only he knows to find H(g^{xy} mod p)
and
generate the correct RC4 keystream to decrypt the message.

==

1) Does significant danger arise from this approach by generating many
keys
of the form
g^{xa}, g^{xb}, g^{xc},..... ? [Alice chooses a, b, c,... each time
she
writes a postcard]
ie, if b is discovered, does it help the attacker decrypt any other
postcards?

(I don't think so, this is the basis of public DH params is it not?)

[Clearly perfect forward secrecy (PFS) is not property of the system,
since
compromising x (known only to Bob) will allow decryption of all
postcards].

2) Is there any benefit from signing each g^y mod p that Alice
includes in
the postcard? We assume that she does not sign the message in its
entirety.

Again, I don't think so. An attacker could replace the g^y that Alice
writes
on the postcard so that the message decrypts to garbage, signing g^y
would
allow Alice to be sure that the message stands a chance of decrypting
correctly.

However, if the attacker just wants to garble the message and g^y has
been
signed then it can just change the ciphertext of the message.

3) If Alice were to sign g^y, does this provide proof that the
decrypted
message is authentic?
Again, probably not: an attacker can change the ciphertext and Bob has
no
knowledge that this has taken place.

==

Hope this is the right ng for this sort of post; apologies for
answering my
own questions, but keen to be sure :) Apologies if this message
appears twice in the ng, had some trouble my end with posting.

Thanks,
Mike

Relevant Pages

  • Re: DH Question
    ... > Alice goes on holiday and intends to send Bob a postcard at various ... > generate the correct RC4 keystream to decrypt the message. ...
    (sci.crypt)
  • Re: DH Question
    ... > Alice goes on holiday and intends to send Bob a postcard at various ... > generate the correct RC4 keystream to decrypt the message. ...
    (sci.crypt)
  • Re: Caribbean Holiday C/D 1.10.05
    ... Is this plain paper or a postcard? ... TIA, ... Alice ... Prev by Date: ...
    (uk.rec.competitions)
  • Re: PGP Lame question
    ... > There are also numbers NB, PubB and PrivB, that Bob knows. ... if the authorities ask Bob to decrypt, ... then they have R, and Bob's public key B, and they have Q to begin ... >> can verify that Alice signed something somehow connected to Bob? ...
    (sci.crypt)
  • Re: PGP Lame question
    ... Bob could have created this R himself. ... if the authorities had intercepted the original message ... while being sent from Alice to Bob, then there's no hope for Alice ... > can decrypt and obtain R, ...
    (sci.crypt)