Imagine you took a standard one-way hashing algorithm (like SHA-256), and you implement it in hardware using simple logic gates.

Now, replace each logic gate with an equivalent reversible logic gate (e.g. toffoli gates).

Let's assume we're limiting our messages to 256 bits. We wind up with a circuit that produces the usual 256 bits of the SHA-256 hash, plus an additional 256 very large number of output bits representing the captured entropy of the circuit.

Together, these two sequences of bits can be used to reconstruct the original message (by running an instance of our hardware in reverse), but the actual result is essentially random (or as close to random as you can get with a deterministic hash function).

$$(x,h) \leftarrow \operatorname{Tuffoli-SHA256}(m)$$ where $m$ is the message, $h$ is the result of $h = \operatorname{SHA256}(m)$ and $x$ is the Tuffoli gate information.

Suppose you then have a sequence of messages you want to send securely. You and your friend have a pre-shared key $PSK$ consisting of random bytes, with the same length as $x$ appended to $h$, $h\mathbin\|x$.

For each $m_i$, you generate what you now hope is a private message $p_i$:

$$p_i = PSK \oplus (h_i\mathbin\|x_i)$$

(Where $\oplus$ is XOR.)

The idea I'm getting at here is that even though ($h_i \mathbin\| x_i$) contains all the information necessary to reconstruct $m_i$, it looks like random noise.

My understanding is that if you re-use a random key this way on natural language text, you're vulnerable to crib-dragging attacks.

The difference here is that each $p_i$ itself is appears to be random noise, so it shouldn't be vulnerable to crib-dragging.

So the question is: are there other attacks that could be used to deduce $PSK$ from a sequence $p_n \ldots p_{n+k}$ observed on the open channel?

  • $\begingroup$ Good points, @kelalaka. I edited the question. $\endgroup$ – tangentstorm Aug 4 '20 at 17:22
  • $\begingroup$ "Toffoli gates though reversible, one needs to store lots of states to reverse for each message"; actually, that is not true. One can construct a circuit that computes $(a, b) \rightarrow (a, b + sha256(a))$; such a circuit is rather more complex than a more naïve approach $\endgroup$ – poncho Aug 4 '20 at 18:25
  • $\begingroup$ "Does a third party observer still have the ability to deduce your key?" - actually, SHA256 doesn't have a key; are you stirring in the key somehow in with the message you're hashing? $\endgroup$ – poncho Aug 4 '20 at 18:32
  • $\begingroup$ @poncho I was talking the pure SHA-256. Your construction is not clear for me. Also, It is not about a keyed hash. The OP was thinking about multi-use of OTP now it is PSK. $\endgroup$ – kelalaka Aug 4 '20 at 18:47
  • 1
    $\begingroup$ The only problem that I can think if the message space is known, or an attacker force you to send a message in some way. This doesn't cause a problem with AES since it is KPA secure. $\endgroup$ – kelalaka Aug 4 '20 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.