Questions tagged [collision-resistance]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
73 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 ...
2
votes
0answers
90 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 ...
1
vote
0answers
39 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:...
1
vote
1answer
96 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 ...
1
vote
2answers
94 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, ...
-1
votes
1answer
69 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/...
3
votes
1answer
159 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 ...
2
votes
3answers
642 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)$ ...
2
votes
0answers
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 ...
0
votes
3answers
128 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 ...
1
vote
1answer
77 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 ...
0
votes
0answers
42 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) = ...
0
votes
0answers
23 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. ...
1
vote
1answer
213 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 ...
1
vote
3answers
148 views

if i enter a password that's incorrect but that collides with one when hashed, will it let me in?

suppose no salt or pepper is used and passwords are hashed plain, will entering incorrect password that just hashes to the same let me in? i know that one use of salting/peppering techniques is to, ...
2
votes
3answers
160 views

$2^{64}$ versions of the same message

I am reading a textbook and in there they explain the property of hash functions. In particular, they give an example of how unlikely it would be to find a second input value that would match the hash ...
0
votes
2answers
95 views

Is it possible to get the SHA256 hash collision with partial known data

I have a text sentence that consists of 448 digits [0-9] [a-f] (in HEX format). This text sentence is partially cut off, but I know the middle, and the beginning ...
1
vote
0answers
42 views

Hash function producing cycles with expected max length

Is there a known hash function $H_k: X\to X$ such that: $\forall{x\in{X}},\exists{n\in{\mathbb{N}}}, n<k \land H^n(x)=x$ === EDIT === By hash function I mean ...
1
vote
3answers
88 views

Hash function collision importance

Suppose a collision has been found in a certain hash function, such that H(x1) = H(x2) However, x1 and x2 are both a seemingly 'random' collection of bits which do not convey a coherent message, and ...
1
vote
1answer
45 views

Is the collision chance 2^(n/2) of an n-bit tag τ unchanged if reduced to (n/2)-bits using a reduction of τ to some 2^(n/2) order group element?

If $H(k, Μ) = τ$, in the context where $τ$ is an $n$-bit tag produced as a mac on a key, $k$, and a message, $M$, through a keyed-hash function, $H$, is there a function $F(τ) = T$ that transforms $τ$ ...
0
votes
1answer
74 views

Homomorphic hash from prime order group $G$ to $Z_p$

Let $G$ be a cyclic group with the generator $g$ and of prime order $p$ such that the discrete-logarithm problem is hard in $G$. A hash function is homomorphic if $H(a\ast b)=H(a)\cdot H(b)$ (where ...
0
votes
1answer
204 views

Using bcrypt to always produce the same hash like SHA, MD

I want to take advantage of the slow property of bcrypt to hash an input but also want to get the same hash value for the same input every time just like SHA, MD, etc. So in order to do that, instead ...
-1
votes
1answer
45 views

Is it possible to have collision resistance but not pre-image and 2nd pre-image resistance?

I have studied cryptographic hash functions quite a lot, but have not completely understood whether it is possible to have collision resistance but not pre-image and 2nd pre-image resistance at the ...
4
votes
2answers
861 views

Many near collisions but no full collision

I read this question: Cracking $f(x) = Cx \oplus Dx$ Asking about finding collisions in a simple 64 bit hash, and I thought I will give it a go myself just for fun. I quickly wrote code to find ...
0
votes
2answers
53 views

Using hash of data as proof of integrity and preventing collision

Rather than storing user data when interacting with an app, I am storing the SHA3-256 of the data. This is because data storage in this particular environment is very limited. The data can be several ...
3
votes
0answers
132 views

Cracking $f(x) = Cx \oplus Dx$

A program I reverse engineered is using $f(x) = Cx \oplus Dx$ where C = 0x20ef138e415 and D = 0xd3eafc3af14600 as a hash ...
1
vote
1answer
57 views

Preimage attack on sum of two Hash functions modulo 2

If a hash function $H$ is defined as $H(x_1,x_2) = H_1(x_1) \oplus H_2(x_2)$ for two n bit good hash functions $H_1$ and $H_2$ then how can we construct a preimage attack on $H$ that is of $O(2^\frac{...
2
votes
1answer
62 views

How does Authentication-Key Recovery for GCM work?

In his Paper "Authentication weaknesses in GCM" Ferguson describes, how some bits of the error polynomial can be set to zero, thereby increasing significantly the chance of a forgery. Q: ...
0
votes
0answers
33 views

If the source code of SHA256 hashing algorithm is available in public, why can't it be hacked? [duplicate]

If the SHA256 algorithm is public, why can't attackers use it to create more collisions rendering the algorithm useless?
0
votes
0answers
62 views

Merkle-Damgård construction

Let $H^f$ be a hash function designed using Merkle-Damgård construction on $f:\{0,1\}^{2n}\to\{0,1\}^n$. Write an algorithm that makes approximately $2.2^{n/2}$ many queries to $f$ and find four ...
1
vote
1answer
75 views

Is it possible to exploit MD5 weaknesses to create an artificial collision for a password?

If it is possible, could an attacker create a collision for an MD5 password in a database? Could they look at an MD5 hash output and figure out data that creates the same MD5 hash?
2
votes
1answer
68 views

Security of Hash Functions

Given a Hash Function H, how are the properties such as collision resistance, target collision resistance, one wayness, and non-malleability proved? I have read about hash function and stating that it ...
0
votes
1answer
81 views

Two Different Ciphers with Same MD5

I was wondering if someone could help explain md5 collision abit better. I found this resource: https://www.mscs.dal.ca/~selinger/md5collision/ where they provided an example of where two cipher texts ...
1
vote
2answers
168 views

Can there be an injective function that maps a large set of integers to a smaller set while being "collision-aware"

Consider two sets: The "big set" contains all integers between $0$ and $2^{160}$ exactly once. The "small set" contains all integers between $0$ and $2^{32}$ exactly once. Given ...
-2
votes
2answers
83 views

What are the security flaws of SHA? [closed]

I have been researching SHA algorithms extensively, specifically SHA1, SHA2-256, SHA2-512, SHA3-256, and SHA3-512, and have found many instances of successful collision attacks as well as methods. In ...
2
votes
2answers
147 views

Does SHA-256 have (128-time + 128-space = 256-overall)-bit collision resistance?

First, we consider those hash functions that can actually provide 256-bit pre-image security, and not something like SHAKE128<l=256bits> where the sponge ...
1
vote
2answers
913 views

Can SHA512 and SHA3-512 Make Same Collisions?

Does combining those two different cryptographic hash functions in HMAC, when each hashes the same data separately, then saved together, guarantee zero possibily of a collision simultaneously or is ...
0
votes
0answers
137 views

Why do the first two digits of the hash table not collide within CRC32?

In this Python CRC32 table look-up method, the polynomial is 0x104c11db7. I can understand that the generated table does not collide. After all, as long as the ...
1
vote
1answer
80 views

Breaking merkle damgård construction that uses bitwise and?

I'm preparing for a exam in crypto course, and i'm doing some practice problems. I'm now playing with this problem: ...
0
votes
2answers
93 views

Shake256 Infinity Collision

Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?
1
vote
1answer
230 views

Example of a Hash function which is second pre-image resistant but not collision resistant [duplicate]

We know that a collision resistant hash function is also second pre-image resistant. But the converse is not necessarily true. I am looking for the example of a hash function which is second pre-image ...
8
votes
3answers
535 views

What is this AES SBOX triplet property?

While playing around with the AES SBOX, I found out that there are 85 unordered triplets (a, b, c) that have the following characteristics: ...
1
vote
1answer
1k views

Are SHA-256 and SHA-512 collision resistant?

This is my first post on this forum, apologies if this post is naive. I want to learn cryptography and I want to start with this question. Context: Designing a TinyUrl system. The user inputs a ...
3
votes
2answers
267 views

Use slow hashing to reduce digest size?

I have seen this question on MD5 replacement for 128 bit digests. It is said numerous times that having a 128 bit digest is impossible today because finding a collision would only require $2^{64}$ ...
1
vote
3answers
191 views

Using date stamp down to milliseconds / ticks as a salt?

As I understand it, the salt is used to ensure that a hash of two of the same strings results in a different hash. The salt is often stored with the hash, either prepended or as a separate field. As ...
1
vote
1answer
83 views

Depth of the SHA-256 collision search knowing partial input and final hashes

So I have a partial input data (string) PART1+UNKNOWN+PART2, length of UNKNOWN is self-describing. I have a bunch of valid ...
0
votes
1answer
42 views

Finding multiple smaller collisions equal work as finding a bigger collision?

Problem A: I receive two hash digests $H(x), H(y)$ and the corresponding preimages $(x, y)$. $H$ is a 128-bit cryptographic hash function: $H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$ I need to ...
1
vote
3answers
339 views

Is collision resistant hash enough for one-block counter mode?

Let $H:\{0,1\}^*\rightarrow \{0,1\}^\ell$ be a collision resistant hash function (CRH), and let $\Pi = (\mathsf{enc,dec})$ be an encryption scheme with the following properties: $\Pi.\mathsf{enc}: \...
0
votes
0answers
117 views

Hash Function that is Collision Resistant but not Puzzle Friendly

Is there any example of a Hash function that is collision-resistant but may not be puzzle-friendly, similarly example of a hash function that is puzzle-friendly but not collision-resistant? Puzzle ...
1
vote
0answers
52 views

Are the hash functions collosion resistant or not? [closed]

If H is collision resistant then the following are collision resistant or not? H'(x) = H(x) || H(x) H'(x) = 1 || H(x) My thoughts: I am confused in question 1. In case of different hash function(H'(...

1
2 3 4 5
13