Questions tagged as ['collision-resistance']

Difficulty of finding two different inputs that hash to the same value
Score: 0
Two Elliptic Curve Points having the Same X coordinate
ua flag

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 does not exist $n' < \lceil{q/2}\rceil$, such that $(x,y_2)=n'P$ is a valid curve point where $y_2 \neq y_1$?

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

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 practically $x_1$,$x_2$ such that $H(x_1)=H(x_2)$?

I argue no with the following reasoning: Let $A$ be an Algorithm which generates $x_1 \neq x_2$ such that $H(x_1)=H(x_2)$ and define $A: \mathbb{N} \rightarro ...

Score: 0
Ramesh Sharma Yadav avatar
What happens when we hash already hashed values, concatenated together?
cn flag

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) = H_0(M) \mathbin\| H_1(M)$ in order to ensure collision resistance as long as either of H0, H1 obeys the property.

Consider H, a secure internal hash function with 256-bit inputs and 128-bit outputs

Score: 0
JSA avatar
Securely and Deterministically select a combination of objects from hash (cryptographic seed)
fr flag

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. Then a client knows that only the authenticated server selected that combination of objects before distribution of the hash the combination derived from. In other words, I need to select a combination  ...

Score: 1
AES-CBC Hash Function Collision Resistance
mp flag

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 get collisions? And if so, how could I find examples?

I expect to find collisions every 2^(n/2) hashes but I don't imagine this would allow me to find any matches in the next 10000000 years.

Score: 1
nimrodel avatar
if i enter a password that's incorrect but that collides with one when hashed, will it let me in?
cz flag

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, aside from making brute force more time consuming, prevent one hash compromise all the users using same pass. but how does it work for preventing colliding passwords being used interchangeably? in other words ...

Score: 2
Slim Shady avatar
$2^{64}$ versions of the same message
cn flag

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 output of the original input. Here's the example:

We show now how Oscar could turn his ability to find collisions (modifying two messages) into an attack. He starts with two messages, for instance:

Score: 0
Dew Debra avatar
Is it possible to get the SHA256 hash collision with partial known data
br flag

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 and end are damaged.

What I know is 322 known digits in the middle of a text sentence.

74 unknown digits at the beginning

52 unknown digits at the end

That is, the entire text Size: 224 bytes and it is hashed using the SHA256 hash algorith ...

Score: 1
Hash function producing cycles with expected max length
nc flag

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 that any other way of finding the preimage of $x \in X$ than iterating $H_k$ is computably unfeasible or at least significantly harder.

My motivation is using such a function as sequential POW.

Score: 1
Arik avatar
Hash function collision importance
ng flag

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 cannot be interperted in a coherent way.

Does this collision make the hash function H not secure? if so how can it be exploited, even if the known collision doesn't convey a coherent message? thanks

Score: 1
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?
in flag

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 $τ$ into a group element, $Τ$, of some group, $G$, of order $2^{\frac{n}{2}}$, such that:

  • The chance of producing any $T$ ( where $F(τ') = F(τ) = T$; and $τ' ≠ τ$ ) is given by $≈2^{\frac{-n ...
Score: 0
Homomorphic hash from prime order group $G$ to $Z_p$
cn flag

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 the operations $\ast$ and $\cdot$ depend on the groups). Here we do not expect the hash function to be compressing, but collision-resistance (CR) and efficiently computeable.

Now the question is, if the ...

Score: 0
Using bcrypt to always produce the same hash like SHA, MD
tr flag

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 of using a static salt, which is less secure I believe, I am thinking to use the input as the salt as well? The output will be the hash value minus the front salt bit (obviously the input itself).

Basic ...

Score: -1
Is it possible to have collision resistance but not pre-image and 2nd pre-image resistance?
in flag

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 same time.

Is it possible?

Please answer this question with a general example.

Score: 4
Meir Maor avatar
Many near collisions but no full collision
in flag

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 collisions:

And yet it finds many near collisions and no full collisions, this baffles me.

Algorithm description: I wanted to solve this using 8GB  ...

Score: 0
Jaime avatar
Using hash of data as proof of integrity and preventing collision
us flag

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 variables, e.g., a, b, and, c, but instead of saving them individually, I save the hash of the concatenation: SHA3(a,b,c).

When the user wants to interact with the system, they should send the variables ...

Score: 3
Alex James avatar
Cracking $f(x) = Cx \oplus Dx$
in flag

A program I reverse engineered is using $f(x) = Cx \oplus Dx$ where C = 0x20ef138e415 and D = 0xd3eafc3af14600 as a hash function. Given a byte array, the hash is is obtained by repeatedly applying $f$ to the current hash xor next byte.

Java code:

    public static long f(long x) {
        return (0x20ef138e415L * x) ^ (0xd3eafc3af14600L * x);

    public static long hash(byte[] bytes) {
        l ...
Score: 1
Preimage attack on sum of two Hash functions modulo 2
cn flag

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{n}{2})$ given some y ?

Here, are we allowed to query $H_1$ and $H_2$ ?

I would really appreciate some hints.

Score: 2
MichaelW avatar
How does Authentication-Key Recovery for GCM work?
in flag

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: What does it mean in detail? That the resulting equations do not solve the problem of obtaining forgery completely, but the solution space is significantly reduced? So we can fix some bits of the error polynomial ...

Score: 0
Yogesh avatar
If the source code of SHA256 hashing algorithm is available in public, why can't it be hacked?
in flag

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

Score: 0
Merkle-Damgård construction
bw flag

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 messages that all hash to same value under $H^f$.

I get an idea to use length extension and 2 birthday attack to get four collision. But I am not able to write the appropriate solution. Can anyone help m ...

Score: 1
Practixal avatar
Is it possible to exploit MD5 weaknesses to create an artificial collision for a password?
sg flag

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?

Score: 2
Novice_researcher avatar
Security of Hash Functions
br flag

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 is collision-resistant but how are they formally proved? If a hash function satisfies all the properties will it act as a random oracle model?

Score: 0
user16198894 avatar
Two Different Ciphers with Same MD5
cn flag

I was wondering if someone could help explain md5 collision abit better. I found this resource: where they provided an example of where two cipher texts have the same md5. I tried to confirm that their example was correct but when I input their examples into a md5 calculator, I get two different md5s for the two different cipher text. What am I doing ...

Score: 1
user10030 avatar
Can there be an injective function that maps a large set of integers to a smaller set while being "collision-aware"
in flag

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 that the number of members in the "big set" is greater than those in the "small set", there can't be an injective function $f(n_b) = n_s$ mapping any input being a member of the "big set" $n_b$ to an output that's a membe ...

Score: -2
Arturo Roman avatar
What are the security flaws of SHA?
in flag

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 my list are the following:

  • Brute Force attacks
    • Birthday attacks
    • Yuval's Birthday attack (improved birthday attack with different conditions)
  • Reduced round attacks
    • Successful on attacks on all SHA al ...
Score: 2
DannyNiu avatar
Does SHA-256 have (128-time + 128-space = 256-overall)-bit collision resistance?
vu flag

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 parameters provides only a security capacity of 128-bit.

We know that cryptanalysis doesn't have just a time dimension - it also has a space dimension, i.e. the amount of working memory needed to execute the cryptanalysis algorithm. So if we expe ...

Score: 0
quxinna avatar
Why do the first two digits of the hash table not collide within CRC32?
mv flag

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 start and end of the polynomial binary are 1, then the hash obtained by different raw data is different.

But why do the first two bits of the hash table not collide?

The first four digits of the polynomial are 0x04c1, and the binary end of