Questions tagged as ['collision-resistance']

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$?

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

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

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

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.

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

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:

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

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.

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

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

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

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

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.

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: https://gist.github.com/meirmaor/b0e59352eb73cacec47d0f95c25a25fc

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

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

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

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

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.

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

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

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

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?

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?

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

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

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

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

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