5
$\begingroup$

Overview

One feature that is often underlooked of the One-Time Pad is its perfect deniability. i.e. If Alice sends a message to Bob that is seen by Eve then if Eve later goes to Alice with the ciphertext and tries to force Alice to disclose her key Alice can "make up" a key and Eve can't prove that the key Alice provided was the real key or not.

One downside of the OTP is its malleability. So a common suggestion is to append a MAC so Bob can see if the message was tampered or not.

I am curious if it was possible to construct a MAC such that if Eve tries to retrieve the key from Alice, Alice can "make up" a key for the MAC and Eve can't prove that that was the real key. i.e. Given a plaintext and MAC Alice can construct a real looking "fake" key in polynomial time. For example HMAC will not satisfy this property because otherwise it would be prone to preimage attacks.

Is this a good definition for perfect deniability of a MAC?

Applications

  • Realistically none since the OTP is impractical.
  • If Alice and Bob are on an anonymous network (example TOR) then Eve cannot prove who sent the message, but Bob can confirm it was sent from Alice and if it was tampered with
  • If Alice posted this in a public place (like a forum, blockchain or public bulletin board) nobody can prove Alice posted it (assuming she posted it anonymously) but Bob can confirm it was sent from Alice and if it was tampered with
  • Can you think of other applications?
Improve this question
$\endgroup$
5
  • $\begingroup$ I think you need to split this up into two questions: 1. is there such a construct (possible) and 2. a question if your construction matches the security requirements of a MAC. Asking questions in answers isn't allowed. $\endgroup$
    – Maarten Bodewes ♦
    Jun 16, 2017 at 11:38
  • $\begingroup$ Moved the protocol idea to crypto.stackexchange.com/questions/48360/… $\endgroup$
    – edggy
    Jun 16, 2017 at 14:23
  • $\begingroup$ Are you assuming Eve can use the real-looking "fake" key to verify the original message sent? The issue I see is that Eve can always check to see whether the key is valid relative to the message and tag pair it already knows. $\endgroup$
    – pg1989
    Jun 19, 2017 at 1:36
  • $\begingroup$ Found this paper on deniable authentication: eprint.iacr.org/2005/046.pdf $\endgroup$
    – pg1989
    Jun 19, 2017 at 1:39
  • $\begingroup$ @pg1989, that is about a different problem: how to get deniability in a public key context. $\endgroup$
    – otus
    Sep 16, 2017 at 11:00

2 Answers 2

Reset to default
1
$\begingroup$

A Carter-Wegman -style MAC gives you easy deniability when you use a one-time pad to encrypt the universal hash. You can compute a hash for your fake message and choose the key accordingly, just like you do with the one-time pad that you use to encrypt the message contents.

This is actually available widely to programmers: NaCl has crypto_onetimeauth which uses Poly1305 (a polynomial evaluation MAC) with the latter half of the single use key used as a one-time pad. To get the same MAC value for another message you can just compute the MAC, then modify the pad part to match your target.

Not all uses of Poly1305 give you perfect deniability, however. The ones where the key or pad comes from AES (Poly1305-AES) or another cipher (e.g. crypto_secretbox) likely do not because you cannot freely choose the value of it without affecting message decryption or the authentication of other messages.

Improve this answer
$\endgroup$
0
$\begingroup$

Any MAC will work if you MAC then encrypt. If the MAC is encrypted with a one time pad by making up a key for the MAC you can replace it for a MAC for the made up message. Yet an attacker trying to mangle the message would need to change two parts of the message in a consistent fashion which is assumed to be hard if the MAC is secure.

Improve this answer
$\endgroup$
3
  • $\begingroup$ But "MAC then Encrypt" is not secure... I guess you could "Encrypt then MAC then Re-encrypt", but that just seems wasteful $\endgroup$
    – edggy
    Sep 19, 2017 at 16:04
  • $\begingroup$ In a OTP setup I suspect using a seprate key for mac part and message part would be sufficient. And this is assuming of course your mac is a simple hash and not keyed itself in anyway. $\endgroup$
    – Meir Maor
    Sep 19, 2017 at 17:03
  • $\begingroup$ crypto.stackexchange.com/questions/202/… If the MAC has no key then anyone can spoof it, so it must have a key. You are correct in saying that we would need 2 independent keys, one for encrypting and the other for MACing. The problem with "MAC then Encrypt" is that you lose integrity, which is bad. $\endgroup$
    – edggy
    Sep 19, 2017 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.