Score:2

Is it possible to reverse GHASH from GCM?

aq flag

How can I create a "reverse" GHASH algorithm for GCM that allows me to compute an input value that generates a specific chosen output, given that I know the authentication key H? If this is possible, what is the process for achieving this?

Score:6
my flag

If this is possible, what is the process for achieving this?

It's actually quite easy, if you know how to do operations in $GF(2^{128})$, specifically, addition, multiplication and computing inverses (note that you already need to know how to do addition and multiplication to perform GHASH in the forward direction).

What GHASH does is take the message [1] and convert it into a series of 128 bit values $a_n, a_{n-1}, ..., a_1$; and it does it in such a way that the bits from $a_n, a_{n-2}, ..., a_2$ come directly from the message. Then, it computes:

$$GHASH_H(\text{Message}) = a_nH^N + a_{n-1}H^{N-1} + ... + a_1H^1$$

So, to find a message that GHASH's to a specific value $T$, you select a message length and a position 16 bytes long which set a specific $a_j$ value (for any $j$). Then, set the bytes on that position to 0 for now, and set the rest of the message bytes arbitrarily, and evaluate the GHASH for that message, it will be a value $T'$.

Then, set those 16 bytes to the value that makes $a_j = H^{-j}(T + T')$, and you're done; when you GHASH that modified message, it'll evaluate to $T$.


[1]: As defined in GCM, GHASH actually takes two messages; one the AAD and one the ciphertext. This doesn't complicate things, and so I'll ignore it

sWong avatar
aq flag
Can you clarify what is meant on the last step, where one takes the inverse of H, and solves for $a_j$? Are you just trying a bunch of values for $T'$, or is there a more elegant way?
poncho avatar
my flag
$H^{-j}$ is that value for which $H^{-j} \times H^j = 1$; this is the multiplicative inverse. One (inefficient) way of computing it is $H^{-j} = (H^j)^{2^{128}-2}$. And, no, we're not trying a bunch of values of $T'$; we're doing one test value and then the final one. I was originally going to write up the equations you need to solve; I then realized that just evaluating it for $a_j=0$ makes the explanation much simpler...
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.