Score:0

Crypto

Reverse SHA256 Hashed Value from Multiple Instances where Part of Hashed Value is known

Thomas Sylvest

3/30/23, 8:21 AM

I apologize in advance if this question has been answered already. However, I have not been able to find an existing answer - despite the case being pretty simple and common I imagine. Perhaps there is some terminology that I do not know making me miss the obvious.

So here goes:

Assume we repeatedly SHA256-hash a "secret" value concatenated with different numbers and let an adversary know the hashed values and the concatenated number for each hashed value.

For instance:

Let's say the secret is "Pa55word", then we hash the following values and let the adversary know the integer and hashed value for each hash:

Pa55word0,

Pa55word1,

Pa55word2,

Pa55word3...

Then - my question is - if the adversary gains an advantage of finding the secret when knowing part of the hashed value and the hash for several different instances. Is he in a better situation than knowing a single instance where he knows part of the clear-text and the hash.

Or, simply, is the scheme secure?

0 + 0

sha-256

hmac

kelalaka

3/30/23, 8:49 AM

Welcome to Cryptography.SE. What is the size of the secret? The attacker will not execute a pre-image attack. It will search for the secret, therefore if there is [small input space](https://crypto.stackexchange.com/a/81652/18298) they will go for it. What is your actual aim?

Thomas Sylvest

3/30/23, 9:18 AM

Thanks @kelalaka I imagined the secret to be a randomly generated guid (or possibly two guids). The actual use case involves a callback mechanism over the internet. What I am trying to accomplish is verifying that a received callback message corresponds to an outstanding request without performing a lookup in a database for an id. The hope is that this will make the system more resilient to denial-of-service attacks.

poncho

3/30/23, 1:40 PM

@kelalaka: the security of this system does not directly follow from preimage resistance; it's asking about security against a number of related preimages, which we believe SHA-256 is secure against, but it doesn't follow from any of the three standard hash security assumptions.

kelalaka

3/30/23, 5:17 PM

@poncho yes that is way better to formulate.

Score:0

Crypto

Meir Maor

4/1/23, 2:38 PM

Specifically for SHA256 it is easier to argue about the security of this (Not a formal proof). If we discount the finalization and padding of the hash, in the Merkle Damgard construction you can do length extention. take a known hash, and calculate the hash of the same unknonwn plain text with a chosen suffix.

If given H(x) you can calculate H(x||c) without knowning x, it follows that telling the user H(x||c),c in addition to H(x) doesn't noticeably help in extracting x.

Due to padding this doesn't hold directly for SHA256, but I still see this as a strong arguement in favor of the security. i.e knowning SHA256(x||c),c for multiple values of c doesn't make it much easier to find x over only knowning SHA256(x).

For SHA256 we can do extention but not for arbitry suffixes, we need to start with the padding as the next block, but that is pretty close.

0 + 0

poncho

4/1/23, 2:48 PM

That logic does appear to apply (with only one plausible assumption) in the case where $x$ is a multiple of 64 bytes long (with the plausible assumption being that the SHA-256 without padding is preimage resistant for messages a multiple of 64 bytes). Now, it doesn't apply to other lengths (as bytes from $c$ are stirred in with bytes from $x$ in the message scheduling), but it's certainly better than what I thought - thanks

Meir Maor

4/1/23, 2:57 PM

You are of course correct regarding the clock length. For very specific suffixes an attacker can do length extention. And since the proposed scenario in the question doesn't have the attacker, chosing suffixes, unless there is a suffix specific vulenrability an attack would also work on the length extended variants and therefor work also on the raw hash.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Reverse SHA256 Hashed Value from Multiple Instances where Part of Hashed Value is known

TH: ย้อนกลับค่าแฮช SHA256 จากหลายอินสแตนซ์ที่รู้จักส่วนหนึ่งของค่าแฮช

RO: Inversați valoarea hashed SHA256 din mai multe instanțe în care o parte din valoarea hashing este cunoscută

RU: Обратное хэш-значение SHA256 из нескольких экземпляров, где известна часть хеш-значения

VI: Đảo ngược giá trị băm SHA256 từ nhiều trường hợp trong đó một phần của giá trị băm được biết đến

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.