Subject: Plausible deniability (a feature to think about)

From: [email-masked] (Daniel A. Nagy)
Date: Thu, 22 Sep 2005 06:29:55 +0200

I just got a message from a human rights activist, who pointed out a
shortcoming of PGP for -- for the lack of a better word -- paranoid
conspirators.

Imagine, that a conspiracy expects to be infiltrated. They send encrypted
messages back and forth but they have a dilemma: to sign or not to sign? If
they do sign, the infiltrator will have damning evidence on his hands and
the bad guys will be able to crack down on the conspirators. If they don't
sign, the infiltrator will be able to forge messages and thus seriously
interfere with the activities of the group (e.g. call off action in the name
of the ringleader, etc.).

Now, there exists a cryptographic solution for this problem, moreover,
RFC2440 even hints that it might be implemented in OpenPGP, though I have never
seen it used: X9.42 Diffie-Hellman key agreement (see also RFC2630, RFC2631
and RFC2633).

In addition to signature and encryption keys, one can have a DH subkey
which may be used to create a (salted) two-party shared secret session key
and send an MDC-protected encnrypted message using that key. Now, the
receiving party can be sure that it was composed by the sender, but has no
means of proving it to a third party. The sender can plausibly deny
authorship, claiming that the receiver has forged it using his private key
and the sender's public key.

Has anybody ever bothered implementing (or even designing an implementation
of) this in an OpenPGP-friendly manner? Seems like it's just a matter of a
third ESK type (tentatively called DH-ESK) and a clear definiton of DH keys
(for which we have reserved identifier 21), which, I guess, should be
identical to ElGamal keys, though it is instrumental that the entie
conspiracy used the same modulus and generator element.

DH-ESK should be very similar to SK-ESK with a salted (but not iterated)
S2K, except for the additional 8-octet IDs of the sender's and the
recipient's public DH keys. The usual traffic-analysis thwarting techniques
of leaving one or both of them blank obviously apply. Allowing for an
ephemeral sender PK to be included is pointless, as that would bring us back
to ElGamal encryption (well, almost), for which there is already a PK-ESK.

If the MDC verification works out on the receiving end, the implementation
should show the message as being "sealed" by the sender on the date from the
literal packet, in addition to decrypting it, much like it handles
signed+encrypted messages.

It's so easy and straightforward that I'd dare to propose it for 2440bis.

-- 
Daniel

---

From: [email-masked] (Peter Gutmann)
Date: Thu, 22 Sep 2005 17:43:57 +1200

[email-masked] (Daniel A. Nagy) writes:

>RFC2440 even hints that it might be implemented in OpenPGP, though I have
>never seen it used: X9.42 Diffie-Hellman key agreement (see also RFC2630,
>RFC2631 and RFC2633).

X9.42 was only added to S/MIME for political reasons.  AFAIK only one
implementation ever supported it, and that was the USG-funded reference
implementation that was required to support it.  In addition, MS supported a
read-only implementation just so they couldn't be accused of not supporting
it.

(I remember having a conversation with a rather baffled security application
 developer who wanted to see X9.42 in an S/MIME toolkit and just couldn't
 understand that although the spec had it as a MUST requirement, all the
 implementors knew that you should ignore it).

>of) this in an OpenPGP-friendly manner?

See above.

Peter.

---

From: "Brian G. Peterson" <[email-masked]>
Date: Thu, 22 Sep 2005 06:28:33 -0500

On Wednesday 21 September 2005 11:29 pm, Daniel A. Nagy wrote:
> interfere with the activities of the group (e.g. call off action in the
> name of the ringleader, etc.).
<...>
>The sender can plausibly deny authorship, claiming that the receiver has
>forged it using his private key and the sender's public key.

Interesting thought experiement.

I led the development team of the solution used by the CryptoRights Foundation
http://www.cryptorights.org/
our solution consisted of management tools, user interfaces, translations, and 
other niceties around a gnupg based engine.

We were most concerned with chain of evidence and verifiability, not plausible 
deniability.  In the real world, most human rights organizations already have 
extensive methods of verifying information that is provided to them, and 
informers have elaborate methods of communicating that information, that only 
rarely involves electronic communication, encrypted or otherwise, becasue of 
the danger of interception.  In a country (like China) where much/most 
private use of encryption is disallowed anyway, sending *any* encrypted 
message is a risk that most human rights workers and informers will not take.

I don't think that OpenPGP needs a new shared-secret method of communication, 
or that the spec needs another wrinkle for implementors to chew on.

Regards,

  - Brian

---

From: [email-masked] (Daniel A. Nagy)
Date: Thu, 22 Sep 2005 15:56:34 +0200

> read-only implementation just so they couldn't be accused of not supporting

What political reasons? And why is there a reserved ID in OpenPGP?

>  implementors knew that you should ignore it).

X9.42 may be flawed (is it?), but DH key agreement is one of the strongest
primitives in asymmetric cryptography.

-- 
Daniel

---

From: [email-masked] (Daniel A. Nagy)
Date: Thu, 22 Sep 2005 16:45:19 +0200

On Thu, Sep 22, 2005 at 06:28:33AM -0500, Brian G. Peterson wrote:

> deniability.

Different people have different concerns, I suppose.

> In the real world, most human rights organizations already have 
> the danger of interception.

The "real world" keeps changing. If you can make something cheaper, more
reliable, simpler, etc., why stop short of doing so?

Also, I am not convinced that what you're stating is universally true.
AFAIK, PGP has been quite popular with activists since its very first public
releases.

> In a country (like China) where much/most 

The world is not black and white. "Countries like that"  are not the only
places where basic human rights are under assault, and not even necessarily
by the government. There's a large number of considerably
less-than-democratic  governments that for one reason or another must
maintain  a democratic facade. And again, the government is not necessarily
the threat you're caring about.

> or that the spec needs another wrinkle for implementors to chew on.

It would be obviously optional, and as outlined in the first email of the
thread, not much of a trouble to design or implement.

Bests,

-- 
Daniel

---

From: [email-masked] (Peter Gutmann)
Date: Sat, 24 Sep 2005 19:31:30 +1200

[email-masked] (Daniel A. Nagy) writes:
>>What political reasons? 

For a brief period during the S/MIME development, RSA was still owned by
RSADSI while DH wasn't.  From "The Crypto Gardening Guide and Planting Tips",
http://www.cs.auckland.ac.nz/~pgut001/pubs/crypto_guide.txt:

  An Internet standard RFC required that implementors support X9.42 DH key
  agreement, and provided RSA as an option (in IETF terms, "MUST X9.42, MAY
  RSA"). However, no existing software supported X9.42, no CAs would issue
  certificates for it, even if they did no-one wanted to renew all of their
  certificates ($$$) for an algorithm that provided no advantages over RSA,
  and no hardware (either crypto accelerators or smart cards) supported it
  (there was some token support after a few years, although even now there are
  problems being found with the X9.42 test vectors which indicate that no-one
  has really looked at them). As a result, even though the standard mandated
  use of X9.42, everyone treated it as if it said "MUST RSA, SHOULD NOT
  X9.42", pretending to do X9.42 while running business as usual with RSA.

>And why is there a reserved ID in OpenPGP?

OpenPGP has reserved IDs for all sorts of weird and wonderful stuff.  I guess
X9.42 is no exception.

Peter.