[cryptography] deniable store and forward with integrity protection?

David-Sarah Hopwood david-sarah at jacaranda.org
Tue Feb 15 19:04:34 EST 2011

On 2011-02-15 03:13, James A. Donald wrote:
> Existing algorithms for off the record messaging between
> entities identified by public keys require an initial round
> trip to set up a shared secret.  Once a shared secret exists,
> obviously routine encryption and MAC authentication will
> create an off the record message - the recipient will know
> that only someone who knows the shared secret could have
> created the message, but cannot prove to someone else which
> of the people holding the shared secret created the message -
> the message is authenticated but deniable, authenticated but
> unsigned.
> It is fairly easy to design a protocol that achieves this
> result without a round trip requirement, (authentication
> without round trips or signature), but has such a protocol
> already been published and examined?

Note that a disadvantage of such protocols relative to
multi-round ones is that, as far as I know, they cannot
achieve forward secrecy.

> The requirement of the protocol if the possessor of the
> secret 'a' corresponding to public key A, sends the message
> to the possessor of the secret key b corresponding to public
> key B, the message can only be decrypted by someone who holds
> one of the two secrets, and only someone who holds one of the
> two secrets could have created the message - but either one
> could have created the message, hence, off the record.

This kind of protocol is called a "public key authenticator".
For this purpose Dan Bernstein suggests using static
Diffie-Hellman to agree a key for a symmetric authenticated-
encryption scheme. For example the 'crypto_box' scheme in his
NaCl library uses static Diffie-Hellman in an elliptic-curve
group: <http://nacl.cace-project.eu/box.html>
I don't know whether it has had any published analysis.

Here's another way to achieve this generically using any
signature and (IND-CCA2-secure) public key encryption schemes:

  Generate a key for a symmetric authenticated-encryption scheme
  (such as encrypt-then-MAC). Encrypt this key to the recipient's
  public encryption key. Sign the result and an identifier for the
  recipient with the sender's private signing key.

Even though a signature is used to authenticate the symmetric
authenticated-encryption key, the protocol has the "off-the-record"
property, because the recipient knows the symmetric key and
therefore could claim any message to have been authenticated by
that key.

Note that this protocol must use encrypt-then-sign in that order.
If it were sign-then-encrypt, the recipient could strip off the
encryption and reuse a signature to forge a message appearing to
be from the original sender. With encrypt-then-sign, this attack
does not work: because the encryption scheme is IND-CCA2-secure,
the message will only be accepted by someone who can decrypt it
using the correct private decryption key (subject to the caveat

Most such schemes, including crypto_box and the generic scheme
above, have a potential vulnerability that needs to be prevented
at a higher protocol level. Suppose that an attacker, Carol,
claims her public key to be the same as that of another user Bob
(depending on the protocol, it may be possible to modify this
attack to work with a key that is different but related to Bob's
key). Now Alice sends Carol a message, which Carol relays to Bob.
Carol cannot change the message since she does not know the
symmetric key, but Bob will believe that Alice intended to send
him that message, when actually Alice intended to send it only
to Carol.

This attack can be countered by including an identifier for
the *intended* recipient in the message. This should be checked
automatically by the recipient's software, and the message not
presented as genuine unless it matches the recipient's expected

Alternatively, each party that claims a public key can be
required to prove knowledge of the corresponding private key.
(Most multi-round protocols essentially do that in a key
confirmation step.)

David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 292 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20110216/8a09bd43/attachment.asc>

More information about the cryptography mailing list