[cryptography] deniable store and forward with integrity protection?

James A. Donald jamesd at echeque.com
Tue Feb 15 22:28:12 EST 2011

On 2011-02-16 10:04 AM, David-Sarah Hopwood wrote:
 > Note that a disadvantage of such protocols relative to
 > multi-round ones is that, as far as I know, they cannot
 > achieve forward secrecy.

In that if either party to the protocol described loses
control of his secret key, all messages can be retroactively

I was unaware that any half round protocols had been
described, though you proceed to describe one blow.

 > 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.

This accomplishes the same result (no round trips) with the
minor disadvantage that one cannot deny sending *a* message
(which is a very minor disadvantage since traffic is
generally traceable), and the considerable advantage that it
uses only long established cryptographic primitives.

 > 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 below).
 > 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 ID.
 > 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.)

It would seem that forward secrecy inherently requires at
least one and a half round trips, since the recipient of the
message has to have a transient secret.

This problem can be somewhat mitigated by caching shared
secrets for a moderate period.

More information about the cryptography mailing list