Skip to main content

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
1 vote
0 answers
43 views

I do not understand the result of 'proposition 2' of "MDx-MAC and building fast MACs from hash functions"

I saw the difference between the proof and the statement of "proposition 2" in the paper "MDx-MAC and building fast MACs from hash functions" by Bart Preneel & Paul C. van ...
hellobc's user avatar
  • 31
0 votes
0 answers
40 views

Proving Insecure Hash Function Through Not Collision Resistant

There is a function H : {0, 1}* → {0, 1}^n. On input a message m and two shares of it x, w such that m = x ⊕ w, the function outputs y = H(m) = H(x) ⊕ H(w). How would I find that this NOT a collision ...
sangaCat's user avatar
1 vote
0 answers
23 views

Proof of UOWHF construction from a strongly universal hash family

I am currently trying to rigorously prove Lemma 2.2 of [NY]. More specifically, a UOWHF family can be constructed from a composition of a strongly universal family $G_k = \{g : \{0, 1\}^k \rightarrow \...
Pontakorn Prasertsuk's user avatar
0 votes
1 answer
43 views

Finding security constraints for different input domains of Ajtai functions

I know that the normal construction for Ajtai hash functions is as follows: Pick $n, m, q \in \mathbb{Z}^+$ such that $n \log q < m < \frac{q}{2n^4}$ and $q = O(n^c)$ for some $c>0$, and some ...
the thinker's user avatar
0 votes
0 answers
28 views

Obfuscation scheme wanted

I'd like to know if there's any cryptographic scheme that implements something similar to what I'm summarizing here below. Thanks a lot for reading and for any hint or question. Intro-Scenery: There's ...
Lorenzo's user avatar
  • 101
2 votes
1 answer
59 views

Is it hard to find m, R to make RG^H(m||R)=C?

Assuming the generator of one group $\mathbb G$ is $G$. Given an element $C\in \mathbb G$ and a cryptographic hash function $H(\cdot)$, is it hard for one adversary to find a pair of message $m$ and ...
Twiforest's user avatar
0 votes
0 answers
33 views

Is it possible for a given plaintext and ciphertext to have two different keys? [duplicate]

This has probably been asked before but for a given ciphertext and plaintext pair, is it possible to have two different keys producing said pair? Or there are no collisions in AES, unlike hashing ...
user2338802's user avatar
0 votes
0 answers
103 views

What is the fastest 128-bit non-cryptographic hash function?

I need a 128-bit hash function which is extremely fast since it will be used for generating unique IDs for billions of objects. It doesn't need to be a cryptographic hash function nor does it have to ...
TypicalHog's user avatar
1 vote
3 answers
122 views

Is the composition of a hash function with a block cipher collision resistant?

Assume $H$ is a collision resistant and preimage resistant (unkeyed) hash function and $E(k,y)$ is a block cipher where $k$ is the key. I am interested into the collision resistance of the composed ...
Morz's user avatar
  • 53
0 votes
0 answers
29 views

Calculating maximum plaintexts without birthday collisions given a probability, when the encryption scheme has multiple parts?

I'm sorry if the answer to this is actually simpler than it seems to me. I'm running AES-GCM to encrypt some data keys, but I don't actually know how to go about calculating the probability of ...
RotundChinchilla's user avatar
2 votes
1 answer
96 views

Difficulty of finding a claw for AES-CMAC

Consider the problem of finding two keys K1 and K2, such that for two distinct plaintexts P1 and P2, AES-CMAC(K1, P1) = AES-CMAC(K2, P2). Is this problem any easier than brute-forcing? If so, how much ...
Bogdan Alexandru's user avatar
1 vote
0 answers
33 views

Grow-only set homomorphic hash function from semigroup?

I have been exploring Bellare and Micciancio's "randomize-then-combine" paradigm for deriving set homomorphic hashing functions. I am particularly interested in grow-only sets, such that ...
Carson Farmer's user avatar
1 vote
1 answer
78 views

Security of this MAC scheme

I'm studying for a cryptography exam, I have this question from a past exam: Consider the MAC with key $k$, based on a block cipher $E_{(k)}$ with block size $n$, and a collision-resistant hash ...
cantrell11's user avatar
4 votes
0 answers
146 views

Is the XOR-combiner of independent keyed hash-functions collision resistant?

Assume there are two keyed hash-functions $H_1(k_1, m)$ and $H_2(k_2, m)$, with $k_1$ and $k_2$ being independently randomly sampled public keys. The XOR-combiner is defined as $C_\oplus^{H_1, H_2}:=...
Kristian Koenig's user avatar
3 votes
1 answer
794 views

What is the advantage of using hash function families instead of a single hash function?

My guess would be that families are more secure. In which way though? I have seen claims that hash function families can be collision resistant while single hash functions can not be. Is this true? ...
Wouter's user avatar
  • 31
0 votes
0 answers
170 views

Is the following hash function construction collision resistant?

The problem Let the following function be a collision reisistant hash function $$H=\{H_s:\{0,1\}^{2n} \rightarrow \{0,1\}^{n} \}$$ Let the following function be a PRG $$G:\{0,1\}^{n+1} \rightarrow \{0,...
zBION1C's user avatar
0 votes
1 answer
129 views

Set with probability of SHA-3 collisions lower than for a random oracle?

Can we define one finite set of input strings for a SHA-3 hash (or SHAKE XOF) function so that the collision probability is arguably lower than for a random oracle, with a definition of the set making ...
fgrieu's user avatar
  • 141k
3 votes
2 answers
773 views

How much entropy is lost due to collision?

If entropy is hashed with SHA-256 for example, and the input has exactly 256 entropy bits, how much entropy is reduced after hashing due to collision? Is there any reference that explains how to ...
Daniel Ghattas's user avatar
0 votes
0 answers
137 views

Do "superfast" keyed hash functions exist?

A common family of requirements for (cryptographic) keyed hash functions is that the function $h(k,-)$ should have good collision resistance for all keys $k$, even if the key $k$ is known to the ...
SocraticMathTutor's user avatar
1 vote
1 answer
122 views

Hash-Then-Encrypt or Encrypt-Then-Hash on Keyed Hash Functions

I have seen other answers here on Stack Exchange regarding MAC-Then-Encrypt vs. Encrypt-Then-MAC (and this article regarding MAC-Then-Encrypt padding oracle attacks on SSL) as well as generic Hash-...
Hero's user avatar
  • 11
0 votes
0 answers
74 views

Having trouble providing a distinguisher proving this hash function is not collision-resistant

As suggested by the title, I'm working on an exercise where I'm given a hash function $H$ that takes in an input string $x$. I'm supposed to construct a distinguisher that proves $H$ isn't collision-...
HughJass24's user avatar
1 vote
1 answer
100 views

Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
bd55's user avatar
  • 33
2 votes
2 answers
177 views

A question about "attacks on MAC key space"

At page 336 in "Handbook of Applied Cryptography - Menezes", I see the sentence For $n$-bit MAC with $t$-bit key space this requires $2^t$ MAC operations, after which one expects $1+2^{(t-n)...
hellobc's user avatar
  • 31
1 vote
1 answer
49 views

Collision ISIS Problem

I'm trying to understand the inhomogeneous SIS problem and I'm came across to a scenario that I don't know how to evaluate. Let $A,B \in \mathbb{Z}_q^{n\times m}$ be two random matrixes and $u,v \in \...
Carlos Ribeiro's user avatar
1 vote
0 answers
68 views

Is it possible to get the negative point with −x in that version of the Pedersen hash over the BaybyJubJub curve?

The Pedersen hash is a low constraints friendly hash for Zk-Snarks. Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
user2284570's user avatar
2 votes
0 answers
104 views

Security of Even-Mansour based Merkle-Damgård

Assuming I have single-key Even-Mansour with single $2n$-bit permutation in wide-pipe Merkle-Damgård specifically with Matyas-Meyer-Oseas mode outputting $n$-bit hash. What security can I expect ...
LightBit's user avatar
  • 1,649
2 votes
1 answer
132 views

Recommended output filter for Rumba20 [closed]

Rumba20 is a compression function that maps a 192-byte (1536-bit) string to a 64-byte (512-bit) string. It's designed to provide collision resistance by using Salsa20 (or ChaCha20) with the ...
samuel-lucas6's user avatar
1 vote
1 answer
318 views

Pedersen Hash : when truncating the hash to keep only the X coordinate, is it possible to compute a collision when the Babyjubjub curve is used?

The Pedersen hash is a low constraints friendly hash for Zk-Snarks. Unlike many algorithms, the Pedersen hash returns a point P = (x,y) on a curve as a hash. ...
user2284570's user avatar
0 votes
1 answer
150 views

If we supply a random uuid4 hashed salt to Hashid, will it be considered secure?

Ideally, Hashids -: https://pypi.org/project/hashID/ are considered insecure and it is recommended that we should not use them for any sensitive functions. Though, is a HashId considered secure if we ...
CryptoInfo's user avatar
5 votes
1 answer
127 views

The rigorous proof in the commitment based on CRHF

I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
constantine's user avatar
2 votes
1 answer
231 views

Implementing a Merkle tree using a 128 bit hash function?

I need to implement a Merkle tree using a 128 bit hash function. In general, any hash function that guarantees pre-image, second pre-image and collission resistance should be fine to implement a ...
Lorenzo's user avatar
  • 149
1 vote
1 answer
1k views

What does the 256 in SHA3-256 and SHAKE256 refer to?

I am simply wondering what the bit-length in the algorithm variant in the table below refers to? For the hash functions I assume that this refers to the ouput length in bits. For instance for SHA3-256 ...
Rory's user avatar
  • 335
2 votes
1 answer
159 views

theoretical hash collisions vs random number collisions

I have a theoretical question about the probability of collisions of hashes versus random numbers. I'm not interested in the exact probabilities. The exact hash function is not relevant (we can assume ...
Garret Wilson's user avatar
3 votes
0 answers
111 views

Are there "light" versions of cryptographic hash functions?

After tinkering with cryptographic hash functions, I started wondering if they do have counterpart functions that would imitate their cryptographic properties but with a lower level of strength in ...
Ryan B.'s user avatar
  • 153
3 votes
1 answer
82 views

Analyzing the security of hash approaches

Say that I have a random oracle function $H$. This function outputs a value in $\mathbb{F}_{p}$ where $p \approx 2^{256}$. $H$ can accept either one or two inputs (outputting a single value in both ...
vimwitch's user avatar
  • 139
4 votes
1 answer
260 views

very smooth hash (VSH) Stepwise examples

Can someone please point me to or give me stepwise example of VSH hash function. I couldn't find an example or a reference implementation. I tried to go through original publication but it seems way ...
Shivendra Mishra's user avatar
2 votes
1 answer
101 views

Merkle tree alternating hash and polynomial

I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
vimwitch's user avatar
  • 139
1 vote
1 answer
87 views

Hardening a polynomial checksum scheme

I have a checksum scheme that uses a simple polynomial summation as described here. Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + ...
vimwitch's user avatar
  • 139
1 vote
1 answer
81 views

Hash Flooding a Randomized Modular Hash Table

Assume we have a hash table using the function h(x) = x mod 32. h(x) = x mod 33. Also assume it dynamically resizes by doubling the amount of buckets and rehashing. If I was able to provide inputs for ...
DivideByZero's user avatar
0 votes
1 answer
434 views

Checking encoded strings for a hash collision in Python [closed]

There is a common term used in cryptography called a hash collision. If I am reading the definition correctly on Wikipedia, this can occur if two different data values give rise to the same hash ...
JustBeingHelpful's user avatar
1 vote
1 answer
172 views

Does an increase of message size increase the number of guesses to find a collision?

If I hash a 256-bit message and generate an output digest of the same size with a cryptographic hash function then the number of guesses to find a collision is expected to be 2^128. Does increasing ...
alpominth's user avatar
  • 393
1 vote
0 answers
70 views

How to estimate the collision resistance of a hash function if a secondary key is used (keyed hash function)?

According to the documentation of HighwayHash, for finding a collision are expected $m \over 2$ guesses, being $m$ the message. By contrast, 'strong' hashes such as SipHash or HighwayHash require ...
alpominth's user avatar
  • 393
2 votes
1 answer
246 views

Confusion+Diffusion comparison table? (e.g. with Avalanche Criterion / SAC)

I'm looking for a general comparison of encryption algorithms in regard to Confusion and Diffusion (as defined by Claude Shannon), and if possible, specifically for their SAC and BIC quality. For ...
foo's user avatar
  • 144
1 vote
1 answer
44 views

Is a single 256 bits hash table in which the digests are from mixed cryptographic hashing algorithms still considered collision resistant?

Consider a single hash table containing digests from about 10 different 256 bits cryptographic hashing functions, like SHA256, SHA3, KECCACK256, BLAKE2, BLAKE3, etc... Is such table still considered ...
Rafael Werlang's user avatar
1 vote
0 answers
91 views

What is the proof that the RSA is collision-free?

We have the RSA function: $c = m^e (mod n)$. I would like to know the proof that there is not an $m_1$ and an $m_2$ message that produce the same $c$. My thoughts: We know that $m \le n$, so $m_1 \...
Jakab Martin's user avatar
2 votes
2 answers
2k views

Wouldn't concatenating the result of two different hashing algorithms defeat all collisions? [duplicate]

Let's say I have three messages: A B C And I run each of these through two different ...
Eddie's user avatar
  • 983
2 votes
1 answer
121 views

Is there a CRHF based on integer factorization problem or RSA assumption

We know that in the black-box sense, we cannot use one-way functions to construct Collision Resistant Hash Functions.I feel that in my impression, I have never seen CRHF based on integer factorization ...
constantine's user avatar
3 votes
1 answer
205 views

UOWHF vs CRHF / Relevance of UOWHF

What's the difference between UOWHF and CRHF and why are UOWHF useful? As far as I understand, Universal One-Way Hash Functions are an alternative to CRHF. While for CRHF it is hard, given randomly ...
sbluff's user avatar
  • 113
1 vote
0 answers
43 views

Checksum algorithm using system of multivariate polynomials

I'm working on a protocol that uses zero-knowledge proofs. I'm looking at systems of polynomial equations as cheap solutions for checksumming data. Note, I'm not looking for trapdoor functionality ...
vimwitch's user avatar
  • 139
2 votes
0 answers
70 views

Is there any standard extension of the Merkle-Damgård transform that handles arbitrary-length inputs?

I have seen multiple sources claim that the Merkle-Damgård transform is able to build a collision-resistant Hash-function $H$ for arbitrary-length inputs from a compression function $h : \{0,1\}^n \to ...
Steven's user avatar
  • 131

1
2 3 4 5
15