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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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
-
$\begingroup$ 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? $\endgroup$– sWongFeb 27 at 14:14
-
$\begingroup$ $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... $\endgroup$– ponchoFeb 27 at 14:18