Questions tagged [collision-resistance]

Difficulty of finding two different inputs that hash to the same value

Filter by
Sorted by
Tagged with
0 votes
0 answers
59 views

Determine if a Hash function is pre-image resistant and collision free

I'm so confused by this kind of exercise. We have that $n = p * q$, where $p$ and $q$ are prime numbers. Let's examine this hash function: $h(x) = x^2 \mod n$. Determine if the hash function is pre-...
user avatar
0 votes
0 answers
37 views

Can we combine two AES (with block size 128) to to a block cipher with a block size 192 which is collision-resistant?

Encrypting values with AES we only need about $2^{64}$ trials until we finding an already used value (some collision). This can be done these days with easy. To make this harder can we combine two AES ...
user avatar
  • 475
0 votes
1 answer
49 views

Proof of computationally binding correct?

I have defined the following commitment scheme and would like to prove that it is statistically hiding and computationally binding, but I'm not sure if my proof is accurate: For $h$, a collision ...
user avatar
  • 189
0 votes
0 answers
14 views

Do L-trees remove the need of collision resistance hashes in XMSS MT?

I read that the bitmasks in XMSS-MT lower the security requirements from a collision resistant undetectable hash to a 2nd preimage resistant undetectable hash (see LMS vs XMSS: Comparion of two Hash-...
user avatar
1 vote
0 answers
23 views

What is an advantage of the Charles--Lauter--Goren hash function?

What is an advantage of the Charles--Lauter--Goren hash function (based on isogenies of elliptic curves) among other provably secure collision-resistance hash functions ? I heard that it is slower.
user avatar
1 vote
1 answer
51 views

Hash of concatenated values (one public, one private)

Assume two end-points $A, B$. $A$ sends to $B$ a $Hash(pv||key)$, where $pv$ is a public value that can be intercepted by attackers. The $key$ is a common secure shared key in both end-points, and $||$...
user avatar
  • 303
0 votes
1 answer
51 views

Randomness and authentication on short value outputs (48 bits)

I want to implement a client that generates random 48-bit values and send them as broadcast messages. We assume also there is a legitimate receiver getting those values (so, there is some sort of pre-...
user avatar
  • 303
0 votes
1 answer
111 views

non-reversible additive cryptographic hash algorithm

I need a lightweight cryptographic hash function which is additive but not reversible, however I'm not sure such a function exists! (it would be better if it works in multisets as well) By additive I ...
user avatar
0 votes
0 answers
19 views

Why we need DSPR or Eq. 14 for the proof of SPHNICS+?

The paper says that We show that preimage resistance (PRE) follows tightly from the conjunction of second-preimage resistance (SPR) and decisional second-preimage resistance (DSPR). As I understand ...
user avatar
  • 73
0 votes
0 answers
29 views

Collision and pre-image resistances of a hash function based on SPRP

Assume we have a secure block cipher $E$ (strong pseudorandom permutation) and a fixed key $k$ which are publicly known. We construct our hash function $H(m)$ as $$ H(m) = E_k(m_1) \oplus \dots \oplus ...
user avatar
1 vote
1 answer
45 views

Clarification on nonce collision calculation

I've been working on a AES256-GCM implementation (in Java). I'm a little bit stuck on the part where i need to decide how often i need to rotate my key. I've got a lot of information from this posts: ...
user avatar
0 votes
0 answers
69 views

1st Preimage, 2nd Preimage, Collision resistance of powers of 2 mod n

Let $n$ be a product of two odd, distinct large primes $p$ and $q$. Define the hash function as $$ H_{F}(x)=2^{x} \bmod n $$ Is this hash function resistant to 1st/2nd preimage and collision attacks? ...
user avatar
0 votes
0 answers
46 views

Checking if a function is collision-resistant

Consider a prime order cyclic group $\Bbb G$ of order $q$ with generator $g$. Then consider the function$$f:\Bbb Z^n_q\to\Bbb G\\(\alpha_1,\alpha_2,...,\alpha_n)\mapsto g^{\alpha_1\cdot\alpha_2...\...
user avatar
1 vote
1 answer
46 views

vary length hash collision on deterministic block cipher

I am trying to learn attack on hash collision. I guess for this scheme, it might be possible to use messages with different lengths to find a pair of same ciphertexts. An attempt is to use the same ...
user avatar
0 votes
0 answers
34 views

How Davies–Meyer does work? [duplicate]

I am here so if I asked something wrong or in the wrong way please let me know. How to hash compression large data into the fixed size of the string. Edit: How Davies–Meyer does work? Take the example ...
user avatar
1 vote
0 answers
63 views

Cryptographic hash function to map interval onto itself

Is there any existing approach to construct perfect hash function that map [0, M) to [0, M)? It should be one to one mapping and ...
user avatar
0 votes
1 answer
132 views

Is a perfect hash function the same concept as a collision-resistant hash function?

About collision-resistant hash functions, in Katz's Introduction to Modern Cryptography, 6.1 Definitions Hash functions are simply functions that take inputs of some length and compress them into ...
user avatar
  • 151
0 votes
1 answer
78 views

can you generate an ID number quickly, with no collisions, and without IDs revealing information?

Is there a standard way to generate ID numbers one after the other such that: You can guarantee, or almost guarantee, that you avoid collisions. (By "almost guarantee", I mean for example ...
user avatar
  • 145
1 vote
0 answers
67 views

Collision-resistant single-pass EdDSA?

Is there any reason why collision resistant variants of ed25519 that use a single-pass aren't used instead? For example: $n = h(noncekey \| m)$ $h(R \| pub \| n)$ instead of $h(R \| pub \| m)$ or ...
user avatar
1 vote
1 answer
60 views

Why do we need both bitmasks and keyed hash in SPHINCS+

I think one of them is related to multitarget attacks and the other is related to collision attacks. But I cannot find how hash based crypto related to hash collisions. 1-) Consider the following ...
user avatar
  • 73
2 votes
2 answers
100 views

Are SHA-1 hash collisions harder to find when files are big?

Was that just a coincidence, or did the 2 "shattered" pdf files whose SHA-1 hashes are identical had to be small in size (412KB) to make the collision attack easier?
user avatar
  • 23
1 vote
1 answer
54 views

Do proof of work hash function arguments have anything in common?

Some proof of work hashes have a lot of initial zeros. Do the arguments to the hash functions giving these zero containing hashes have anything in common, or are they stochastic? What I am looking ...
user avatar
3 votes
1 answer
115 views

Can a collision resistant hash return zero?

Recently, I have been reading the original proof of GCM. It mentioned the properties of "almost universal" and "return zero" for hash function. I wonder if there is a connection ...
user avatar
  • 115
3 votes
2 answers
184 views

Will Hashing Multiple Times Be More, Less, Or Similarly Secure As Hashing Once

Will Hashing Multiple Times Be More, Less, Or Similarly Secure As Hashing Once? Flushing out this question: I saw this claim: List item: ...
user avatar
2 votes
1 answer
326 views

Understanding Hash collisions - why bad?

I read few answers about the question: why are hash collisions so dangerous? But did not get a really satisfying answer. Assume we are the first people who found a SHA256-collision, like sha256($§&...
user avatar
  • 23
2 votes
1 answer
176 views

Is there a quantum algorithm to find SHA256 collisions?

As I understand, the Bitcoin network can be seen as a supercomputer looking for SHA256 collisions. It hasn't found one yet (March 2022). Also, in the post-quantum cryptography era, you would be ...
user avatar
0 votes
0 answers
46 views

Collision resistance analysis

I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the ...
user avatar
2 votes
1 answer
44 views

Why randomness space must be significantly larger than the commitment space |R|>>|C| in order to generate a commitment string?

Why randomness space must be significantly larger than the commitment space |R|>|C|? the picture is from https://youtu.be/IkNZWJFcfcU?t=236
user avatar
  • 205
2 votes
1 answer
141 views

Deterministically produce an array of indexes based on input number

Please see the Reference section below for terms. Is there a known one-way method to produce an array of indexes, based only on two input elements: length of the resulting array number, used as a key ...
user avatar
  • 143
1 vote
2 answers
151 views

Is the composition of collision resistant functions H' = h1(h2()) collision resistant?

Suppose there are two collision-resistant hash functions $h_1$ and $h_2$ with output sizes of $n_1$ and $n_2$ respectively. Is $H'(x) = h_1(h_2(x))$ collision resistant for the different ...
user avatar
  • 11
0 votes
1 answer
66 views

Finding collisions of polynomial rolling hashes

A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$). For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the ...
user avatar
1 vote
2 answers
104 views

Does concept "Collision Resistance" and "Binding Commitment" in cryptography similar?

I found there are two perplexing and related concept "Collision Resistance" and "Computation Binding in Commitment" in cryptography. I found the wikipedia's explanation is ...
user avatar
  • 205
0 votes
0 answers
47 views

Is sha256, when using an input of 32 bytes, a perfect hash function? [duplicate]

As the title says, is sha256 collision-free if the input is 32-byte long (same size as its output)? In case it's not, what is the most efficient and non-reversible collision-free function? (it doesn't ...
user avatar
1 vote
1 answer
64 views

Checking equivalence among distributed sets

I have elements from $\{0, 1\}^{n}$ (range of a hash function) The master $A$ can have any subset of this range. There are clients that each have a subset from the space, too. I want to make sure that ...
user avatar
  • 581
2 votes
2 answers
757 views

Is there collision in encryption like in hash functions?

In hash functions, $h(m) = h(m_1)$ is called collision and is very undesired that they are feasible to find as it undermines hash security. However, is there essentially analogous concern in ...
user avatar
1 vote
0 answers
142 views

How to find the 6 main properties of cryptographic hash functions when implementing a hash function?

According to this there are at least 6 "properties" all cryptographically secure hash functions strive to attain: Deterministic: the same message always results in the same hash; Quick: it ...
user avatar
  • 161
1 vote
1 answer
92 views

Avoiding MD5 collision with secondary partial hashes

I am trying to design a VCS like program that determines if the files are the same by comparing their MD5 hashes. Then I read about MD5 collisions here, and I wonder if I can work around that by doing ...
user avatar
  • 121
2 votes
0 answers
110 views

Why this function isn't second preimage resistant?

Why is $h(k,m)$ not second-preimage resistant? Let $E_k$ be a block cipher where the message space is the same as the key space. $$h(k,m)=E_k(m\oplus k)\oplus k$$ I've been reading about second ...
user avatar
  • 21
1 vote
0 answers
45 views

One way function with fixed point

As part of an exercise in a cryptography course, I want to come up with a one way function for which it is "easy" to find a collision from a given OWF. To achieve this, I tried the following:...
user avatar
  • 21
1 vote
1 answer
144 views

Why a hash function in a manner similar to CBC-MAC is not collision-resistant?

I'm reading the book The Joy of Cryptography by Mike Rosulek. When reading Chapter 11, on the hash function, I found a very interesting exercise. Does anyone have ideas on how to prove this? Please ...
user avatar
1 vote
2 answers
138 views

reversing hash function makes possibilities increase exponentially, yet there is a finite number of inputs. How?

When trying to reverse a hash function, there is loss, e.g. a+b=c given c=5, try to go back to a,b (previous step) (a,b)=(5,0),(4,1),(3,2),(2,3),(1,4),(0,5) but, ...
user avatar
-1 votes
1 answer
89 views

truncated sha3-512

Let's say I need performance on 64-bit machine, then SHA3-512 is the way to go. SHA-512/256(x) is SHA-512(x) with output truncated to 256 bits, according to https://pycryptodome.readthedocs.io/en/...
user avatar
3 votes
1 answer
180 views

Collision finding method

The "birthday paradox" places an upper bound on collision resistance: if a hash function produces $N$ bits of output, an attacker who computes only $2^{N/2}$ (...) hash operations on random ...
user avatar
3 votes
3 answers
911 views

Composition of cryptographic hash functions

I've stumbled upon many opinions, so I ask about them myself. Let $H(x)$ and $F(x)$ be hash functions. is $H(F(x))$ or $F(H(x))$ safer than $H(x)$ or $F(x)$ is $H(F(x))$ or $F(H(x))$ safe when $H(x)$ ...
user avatar
2 votes
0 answers
36 views

Cyclical Redundancy Check and bijections [closed]

Let $F_M(n)=\operatorname{CRC32}(M|n)$, where $M$ is an arbitrary length prefix message, $n$ is a 32 bit integer (whether little or big-endian encoded is unimportant) and "|" is simply ...
user avatar
0 votes
3 answers
154 views

Two Elliptic Curve Points having the Same X coordinate

Suppose in a elliptic curve (say the curve equation is: $y^2 = x^3 -17$) with prime order $q$, we have $(x,y_1) = nP$, where $P$ is a generator and $n<\lceil{q/2}\rceil$. Can we claim that there ...
user avatar
  • 3
1 vote
1 answer
88 views

Is $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ with $p$ prime (strongly) collision-free?

Let $H:\mathbb{Z} \rightarrow \mathbb{Z}_{p}^{*}$ and $a \mapsto g^a\bmod p$ for $g \in \mathbb{Z}_{p}^{*}$ where $p$ is prime. Is this function (strongly) collision-free meaning we cannot find ...
user avatar
  • 121
0 votes
0 answers
45 views

What happens when we hash already hashed values, concatenated together?

I read on the page 16 of On the Security of Hash Function Combiners that the classical combiner for collision-resistance simply concatenates the outputs of both hash functions $Comb_{\mathbin\|}(M) = ...
user avatar
0 votes
0 answers
25 views

Securely and Deterministically select a combination of objects from hash (cryptographic seed)

I am working on a project that is using a bit-commitment concept to authenticate information. I need to select a combination of objects securely from a secure hash, then distribute that hash later. ...
user avatar
  • 1
1 vote
1 answer
283 views

AES-CBC Hash Function Collision Resistance

I am using AES-CBC as a hash function which is encrypting a block of length n. The blocks, m = (m1, m2, ..., mn). The IV is one block long and the encryption key is length 128, 192 or 256 bits. Will I ...
user avatar

1
2 3 4 5
14