Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
112 views

Looking for a lightweight hashing algorithm

I'm looking for a hashing algorithm with some unique properties: Most important: It has to be small. Ideally ~400 bytes of x86 assembly Resistant to preimage & collision attacks with no known ...
Mark Nelson's user avatar
0 votes
2 answers
89 views

Adding 2 hash values

hash(a) + hash(b) = hash(c) When adding 2 hashes values can it be equal to another hash value? Is it unlikely for this to happen? If so why?
randomdude's user avatar
1 vote
1 answer
62 views

Necessity of all three MD-Compliant padding conditions

For Merkle-Damgård hashing, MD-compliant padding is defined as any padding scheme satisfying: $M$ is a prefix of $\text{Pad}(M)$ $|M_1|=|M_2|\Rightarrow |\text{Pad}(M_1)|=|\text{Pad}(M_2)|$ $|M_1|\...
hegash's user avatar
  • 113
0 votes
0 answers
12 views

How many extra bits of security can I get from an intermediate finalisation of SipHash-2-4?

I'm currently using SipHash-2-4 to hash 4096-byte blocks into 64-bit hashes. The key is secret, as that is required by SipHash. I have 128 bits of space available for hashes, but I don't want to use ...
fadedbee's user avatar
  • 928
1 vote
0 answers
46 views

Are saltless PoW's ok?

So, I'm building a system loosely based on the S/Kademlia principles and I have a question. I generate IDs from hashing a public key such that $ID = H(PK)$. Further, I say that for an ID to be valid ...
Lullen's user avatar
  • 11
3 votes
0 answers
57 views

Security impact of weakened collision resistance for 128-bit Fiat-Shamir challenges

As I understand, to achieve a security level of $\lambda$, a hash function's output should be at least $2\lambda$ in length, since the search space is halved for collision resistance. However, I am ...
Taka's user avatar
  • 31
2 votes
0 answers
59 views

Inequalities in collision search on the separation between the classical and quantum random oracle (ROM vs QROM)

I'm trying to read the separation between the classical and quantum random oracle through a paper "Random Oracles in a Quantum World" by Dan Boneh, Ozgur Dagdelen, Marc Fischlin, Anja ...
Dai Chi DO's user avatar
1 vote
0 answers
44 views

Suffix-free padding scheme for hash function

I would like an easy to read proof that shows that it is sufficient for a padding scheme to be suffix-free for it to be collision resistant. Whenever I have come across such a proof it always seems to ...
revision's user avatar
2 votes
1 answer
66 views

How to design a reversible shifted XOR with an S-box?

According to this post, S-boxes are invertible. Inverting S-boxes can be very easy: you simply create a lookup table that reverse all the possible substitutions of the S-box. E.g. if the S-box maps ...
nalzok's user avatar
  • 123
1 vote
0 answers
65 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
26 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
47 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
157 views

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

I need a stable 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 ...
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
  • 55
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
99 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
37 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
81 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
149 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
803 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
173 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
  • 142k
3 votes
2 answers
781 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
139 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
125 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
78 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
179 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
50 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
72 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
105 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
133 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
359 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
160 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
147 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
273 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
2k 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
165 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
84 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
261 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
104 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
85 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
466 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
174 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
2 3 4 5
15