Hashing a seed full of entropy with a cryptographic hash function and emiting a key with the same size as input: can a collision attack occurs?

alpominth

3/22/24, 8:30 AM

I read this in the documentation of HighwayHash:

By contrast, 'strong' hashes such as SipHash or HighwayHash require infeasible attacker effort to find a hash collision (an expected 2^32 guesses of m per the birthday paradox) or recover the seed (2^63 requests). These security claims assume the seed is secret. It is reasonable to suppose s is initially unknown to attackers, e.g. generated on startup or even per-connection. A timing attack by Wool/Bar-Yosef recovers 13-bit seeds by testing all 8K possibilities using millions of requests, which takes several days (even assuming unrealistic 150 us round-trip times). It appears infeasible to recover 64-bit seeds in this way.

/\ This is talking about 64-bits output.

Let's suppose I take a 256-bits seed full of entropy from Linux /dev/hwrng and hash with a (cryptographic) hash function.

Based on that said above, can the adversary brute-force the seed space and find a collision with 2^128 guesses (128-bits)? Or will it have to brute-force the entire seed space to find the matching key (256-bits)?

This question could sound obvious, but the documentation of HighwayHash made me confused.

0 + 7

entropy

collision-attack

seed

Paul Uszak

3/22/24, 9:29 AM

Hiya! But what is `/dev/hwrng `? The NSA don't like that kinda stuff.

Maarten Bodewes

3/22/24, 10:17 AM

I answered but I deleted my answer. SipHash is a keyed hash and is used to prevent very specific attacks against hash tables. I'm not entirely sure that you are trying to use it in a way for which it is designed. As I'm unaware of the context I think my answer is void of meaning.

alpominth

3/22/24, 8:33 PM

@PaulUszak I have been reading about conspiracies about the TRNG of Inter processors be backdoored, but I use AMD. I cited /dev/hwrng as an example, here I use CPU jittering as my main entropy source for avoiding any possibility of my hardware has the NSA hands. haha! I'm realy paranoid.

alpominth

3/22/24, 8:35 PM

@Maarten Bodewes I just wanna know if I hash a key with 256-bits of size and entropy I would get another key with the same criptographic strenght.

Maarten Bodewes

3/23/24, 10:26 AM

... with a 64 bit output? Huh? Sorry, by now I'm just confused.

alpominth

3/24/24, 12:40 AM

@MaartenBodewes That was an example, there are variants of HighwayHash that outputs 128 and 256-bits respectively.

Maarten Bodewes

3/24/24, 8:33 AM

@PaulUszak It is a reference to RDRAND in Intel and AMD processors (and probably similar instructions on ARM processors). So it might well be that NSA *does* like that stuff, according to your own reasoning.

Elon Musk

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

EN: Hashing a seed full of entropy with a cryptographic hash function and emiting a key with the same size as input: can a collision attack occurs?

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.