Andy is going to connect to a server Selma over TLS. Later, Andy would like to be able to publish everything (the ciphertexts, the plaintexts, all his keys) and prove to a mediator what data he sent to Selma over TLS; or prove what data Selma sent to him over TLS. Is there any way I can do this?

More specifically: We need some way that a third party could look at the information Andy published and convince themselves that he's not lying. Selma is an existing, unmodified TLS server; it can't be modified. Assume that Selma is trusted: i.e., the third party will be willing to trust that Selma isn't trying to fool them and isn't in collusion with Andy. However, the third party doesn't trust Andy: they'll want a way to verify Andy is not lying about what data was sent/received over the TLS connection. It's OK for Andy to use some clever/sneaky/weird combination of TLS options and features and random values/nonces, if that helps achieve this goal. It's OK to use client certs. Andy is willing to reveal his private key and all session keys when he publishes his data.

Is there a way to achieve these goals and enable Andy to prove what data was sent/received over the TLS connection with Selma?

I do know it might be possible for Andy to later prove that he did open a TLS connection with Selma (because the TLS protocol has Selma sign or decrypt something). But that's not enough for my purposes; I want Andy to be able to demonstrate what data was sent over the TLS connection. It's not enough to merely demonstrate that a TLS connection between Andy and Selma existed at one point in time.

My analysis: I can't see a way to achieve this goal. It seems we'd need a way to make Selma sign something that depends upon the application data. However, in the TLS protocol, what Selma signs seems to be independent of the application data. The Finished message has a running hash of the contents of all of the handshake messages, but it doesn't seem to include any of the application data, and in any event it isn't signed. I looked at multiple key exchanges and at features like session renegotiation and false start, but still couldn't find a way to do it. I've seen Does a trace of SSL packets provide a proof of data authenticity?, which says the answer is no if Andy and Selma don't do anything strange. Does the answer change if Andy has the freedom to abuse the protocol or send whatever he wants?

To rephrase: if the answer to my question is "it can't be done", that means that the data is fully deniable: regardless of what Andy does, Andy can always change his mind and later come up with a fake transcript and lie about what data was sent/received. On the other hand, if the data isn't deniable in some circumstances, then that presumably must imply some kind of "yes" answer to my question.

  • $\begingroup$ Comments are not for extended discussion; this (interesting) conversation has been moved to chat. $\endgroup$
    – e-sushi
    Dec 14, 2015 at 22:59

1 Answer 1


There are only two messages from the client before TLS permits the server to send
Application Data; ClientHello and the other one, in that order. ​ Furthermore, the client does
not keep any secret randomness between ClientHello and that other message from the client.
Thus, the third party can use the following strategy in an attempt at breaking deniability:

Before the connection starts, the third party generates ClientHello, chooses a PRF key, and gives Andy that ClientHello and obfuscated code implementing [apply the PRF to the server's initial response, and use that output and randomness to generate the next client-to-server message].

Andy sends the ClientHello from the third party, applies the obfuscated code to Selma's response, sends that code's output to the server, gets authentincrypted Application Data from Selma,
and then sends both of the Selma-to-Andy messages to the third party.
Since the third party knows the PRF key, the third party can
verify-and-decrypt the alleged authentincrypted Application Data from Selma.
By this answer's first two sentences and the security of the to-be-obfuscated-code's PRF
and the fact that TLS's MACs are stateless, regardless of the Level #, just rewinding isn't
enough, so if the obfuscation was Virtual Black Box then, without Selma's cooperation,
Andy couldn't get the third party to accept any Application Data other than
that actually sent by Selma, even when Andy has oracle access to the third party.
Of course, Virtual Black Box obfuscation is impossible in general, but other than Level 4+ and the +s of higher levels implying a secure signature-with-message-recovery scheme for which TLS's symmetric part is the signing algorithm, I'm not aware of any arguments that there shouldn't be an obfuscation scheme that's good-enough at obfuscating the relevant things from this answer.
(On the other hand, I also have very little idea of what such obfuscation schemes might look like.)

Level 1:
If instead the obfuscated code took a ClientHello message as another input (rather than the third party giving Andy a specific ClientHello message) and used a perfectly invoker-randomizable PRF, then for all obfuscated-programs which it's possible for an honest third-party to generate
(but otherwise chosen by the server), the server would have exactly zero ability to distinguish Andy's first two messages (with the latter generated via the obfuscated-program) from a normal client's first two messages. ​ (weakPRP-based constructions of invoker-randomizable PRFs
result in the perfect invoker-randomizability property holding unconditionally.)

Level 2:
Level-1 code could be extended to authentencrypt Application Data from the client and
decrypt authentincrypted Application Data from the server. ​ In this case, under the same
assumption on the obfuscated-code, the only way for the server to distinguish Andy
from normal clients will be sending invalid allegedly-authentincrypted Application Data.

Level 3:
Level-2 code could be extended to [come close-enough to verifying the
authentincrypted Application Data from the server] that, under the same assumption
on the obfuscated code, it will be hard or [information-theoretically impossible]
for the server to distinguish Andy from a normal client.

Level 4:
Level-3 code could be modified to verify the authentincrypted Application Data from the server
in the same way as a normal client, so that under the same assumption on the obfuscated code,
the server will have zero ability to distinguish Andy from a normal client.

The + of a Level:
There could be [a specific simply-efficient obfuscation scheme achieving the Level] for
which it is infeasible for Andy to have a non-negligible chance of fooling the third party.
(rather than [the scheme just being fast-enough to break deniablility]
or [there just not being an efficient way to reliably simulate])

Level 5:
Level-4 code could be modified to output [signatures from a standard signature scheme] on structs encoding [the relevant parts of the protocol's first three messages] and [the plaintext Application transcript]. ​ In that case, the third party would only be needed to securely generate
the signature verification key and obfuscated code, rather than also to check Andy's claims.

Level 6:
There might even be canonical "obfuscated code" that breaks deniability at Level 5,
in which case there wouldn't even need to be a designated third party
- Everyone could check without needing to trust anyone.

  • $\begingroup$ And then the PRF key turns out to be extracted from mono.snk. $\endgroup$
    – Joshua
    Dec 16, 2015 at 19:29

Your Answer

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

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