Questions tagged [preimage-resistance]

Difficulty of finding an input string that hashes to a given value

144 questions
Filter by
Sorted by
Tagged with
443 views

Hashing based on the discrete logarithm problem

At a first look, one could use the elliptic curve discrete logarithm problem to grant for the onewayness of $H(x)=x*G$ (where $G$ is the generator point of the cyclic subgroup). Additionally, $H(x)$ ...
49 views

Hash Function SHA-3 [duplicate]

I would like to discuss the minimum input of hash function to consider strong (e.g Shack128 (SHA-3)). I have a mechanism based on SHA-3, but the input is just 40-bit, some friends told me 40-bit input ...
670 views

How is pre-image resistance defined, formally?

Earlier today, forest asked in our chat, The Side Channel whether the definition of first pre-image security actually requires that an input that evaluates to the challenge hash result must be known ...
194 views

Security of password hash with known prefix and appendix

Assume I have a password that is exactly 32 characters long. I hash it the following way: Prepend 1524 bytes (known to an attacker) Append 3356 bytes (known to an attacker) Do the checksum It is ...
91 views

Security implications of slow-by-design hashes on relative security vs. hash size

Would it be true to say that that one can get away with much smaller cryptographic hashes if the hashing algorithm is slow and expensive by design? Example: let's say you want 128-bit hashes. This is ...
433 views

Keyed reversible hash function?

Is there such thing as a keyed reversible hash function? This would be a hash function where computing H(x) is easy and requires no key, but computing x from H(x) is only feasible with the key. Is ...
84 views

Robust combiner for preimage resistance

My question is about chaining two hash functions to create a robust combiner for preimage resistance. @Zooko already gave a detailed answer here: $$H_{\circ}(x) = H_0(H_1(x))$$ is as strong as ...
642 views

How can I determine if a hash function is secure?

I'm doing an exam in computer security and I encountered this problem which I'm unsure of how to attack properly. Should I get down and dirty with the Hash function on paper or is there a more general ...
84 views

How to perform Black box testing of a key exchange protocol?

Though obviously not an alternative for proper cryptanalysis, I was wondering about statistical/black box analysis. Should I produce a new key exchange protocol. With the same shape as Diffie-Hellman: ...
879 views

collision and pre-image difference

I'm doing an online free course about cryptography and there's a very confusing question: Can anyone explain the answer please? ...
676 views

Does preimage resistance and/or collision resistance imply the infeasiblility of finding fixed points in hash functions?

For example, if $H$ is a secure cryptographic hash function, is it infeasible to find $x$ such that $H(x)=x$ or such that $H(H(x))=x$ ? What about finding $x, y$, and $z$ such that $H(y||H(z||x))=x$ ?...
452 views

Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

Are the quantum secure hash based signatures (XMSS/LMS) susceptible to preimage/second preimage attack?
604 views

Do well-known hash functions have any “impossible” output values?

What I'm wondering is whether the codomain and image of common hash functions are strictly equal… or whether there are any known values which have no possible preimage. For example, SHA-1 outputs a ...
101 views

*feasible* pre-image attacks against reduced SHA-1

(tldr: see last paragraph) Although SHA-1 is vulnerable to collision attacks, it is still resistant to pre-image attacks. SHA-1 was designed to be resistant until a brute-force attack of $2^{160}$ is ...
427 views

Would this hash functionality fall under pre-image resistance or collision resistance?

I understand that there are three main security requirements for hash functions, pre-image resistance, second pre-image resistance and collision resistance. I need to write about a hash function that ...
14k views

Computational requirements for breaking SHA-256?

Let's define "breaking" a hash function $H$ as being threefold (corresponding to the main properties of a cryptographic hash function): preimage attacks to get $m$ knowing $H(m)$ second-preimage ...
189 views

How many hash functions must Bob compute to find a solution?

Alice proposes the following puzzle to be completed. Let m be the body of the email message, let a be the recipient’s email address, let H( )be the hash function SHA3-256, ...
350 views

Can rainbow tables find the preimage of a hash? [closed]

Given a hash value, how are you supposed to find its preimage? What steps can I take to solve find the preimage of a hash such as this 2d202cb6a781edf6ac01d14e1dd6367497db90ba9e8ad721fd17239228a213f9 (...
2k views

How do you find the preimage of a hash?

What is a preimage and how do you find a preimage of a hash?
342 views

Would finding a Merkle-Damgård preimage that doesn't change the initial state allow an attacker to prepend it to any hashed message?

Suppose, a message M was found so that MD5(M) = S, where S is the initial state of the MD5 function (0x01234567, ...). Given a hash MD5(m), would this allow computing MD5(M∥m∥padding), where padding ...
7k views

Could we break MD5 entirely in the future?

Even of today MD5 is (sadly) still heavily used in some applications. Even big tools like ApacheMD5. But even today there are more then enough MD5 hashes which are still not cracked. According to ...
970 views

Difficulty of collision vs preimage vs second-preimage attacks

It seems at first glance that brute-forcing a collision would be exactly as difficult for all of them. They all (I would expect) work like this: select a hash value, and then try messages to get an ...
83 views

What are best known attacks for finding partial target pre-image?

Just a follow up on this question since I don't have enough point to comment: Does a partial preimage attack imply a preimage attack? Partial target preimage attack: Given $M$ and t-bit partial ...
101 views

Rabin fingerprint preimage with given length and alphabet

The Rabin fingerprint looks something like this: ...
155 views

Are there any known values for common hashes known to have no preimage

In a system which requires a user to have a password, as a quick workaround I wrote random junk as the bcrypt hash so that no one will be able to login to that user. However theoretically there ...
406 views

Hash Function Properties

What I am trying to understand is shown in all three properties of a secure hash function, I will focus on Preimage attack resistance. Preimage resistance: given a hash h, it's difficult to find m s.t....
664 views

How does a preimage attack on MD5 break the security of HMAC-MD5?

It was mentioned in an answer to a different question that it's possible that, any day now, someone might figure out a way to turn those into a preimage attack, which would compromise the ...
419 views

Preimage attack given half of the preimage

512 bit X has been hashed using SHA256(X) = Y Given Y and half of X (the first 256bits) to attacker, how hard is to reveal whole X Can SHA256 or any real world function be cracked to allow this ...
221 views

Given a 128-trit state space, is a 3-symbol block cellular automaton secure against preimage attacks?

The following implementation, here for illustration: ...
137 views

Why does second pre-image resistance imply pre-image resistance? [duplicate]

Definitions here: Pre-image resistance Given a hash value h it should be difficult to find any message m such that ...
4k views

Pre-image attack on MD5 hash

I read somewhere MD5 is broken in terms of collision, but I am wondering if it is broken in terms of pre-image resistance? Given a hash of Md5, is it possible to find the original message of it? If ...
92 views

How to formalize a partial preimage task?

Part of the bitcoin mining proof of work is associated with solving a partial preimage problem. For example, output a preimage message $M′$ which computes to a hash value $Y$ with $|Y| = n$ bits ...
507 views

What if using a block cipher as compression function in Merkle–Damgård?

The Merkle–Damgård construction builds a hash by iterating a compression function $F$, with $S_{j+1}=F(B_j,S_j)$ where $B_j$ is one of $n$ padded message blocks, $S_0$ is the IV, and $S_n$ is the hash....
173 views

Does this proof sketch show that finding a SHA-1 preimage is NP-hard?

Jutla & Patthak wrote "Is SHA-1 conceptually sound?" back in 2005, in which they provide a proof sketch (Appendix A) to show that finding a preimage for SHA-1 is NP-hard. Now, there are some ...
161 views

Why does this SHA-1 relation hold?

In De Canniere & Rechberger's 2008 paper "Preimages for Reduced SHA-0 and SHA-1", the following statement appears on page 6: Suppose that we restrict ourselves to the first $j$ + 1 bits of each ...
1k views

What gives SHA-256 its preimage resistance?

I was reading some guy's description of the SHA-256 algorithm and I noticed that the basic operations it uses appear trivial to reverse: addition, rotate bits, etc. When I say "reverse" I don't mean ...
802 views

Proving a function is one way hash function

I am working on a project which computes the hash of the given input, I have to prove that the function is pre-image resistant that is given an output we cannot get back to the input. While proving ...
773 views

Why do different applications of hash functions demand different properties of the hash function?

A strong cryptographic hash function in general must guarantee several properties, including: Preimage resistance, second preimage resistance and collision resistance. It turns out, however, that ...
650 views

If we know a sha256 hashed value and its message length can we find the message?

Is it possible to find the original message if we know a sha256 hashed value and its message length?
975 views

Does a partial preimage attack imply a preimage attack?

Let's assume we have an $n$-bit hash function and a $b$-bit partial preimage attack that is faster than brute force. Does this imply a faster than brute force preimage attack on the whole hash? It ...
304 views

First preimage resistance check

So I have $H: \{0,1\}^* \rightarrow\{0,1\}^n$ a hash function resistant to the second preimage and to collisions. Let there be a function $H' : \{0,1\}^* \rightarrow \{0,1\}^{n+1}$ with the following ...
280 views

How feasible is a preimage attack or speedups to brute force a substring of MD5?

Beyond the birthday problem analysis how feasible is a preimage attack or speed up brute force on a substring of MD5. For instance let's say from the 128 bits I decide to strip 24 bits, the first four ...
164 views

Is it safe to use fast/small hash for key identity?

I have to roll database access keys often, but it's important to know which key each system is using in order to avoid unavailability. I want the systems to report that without exposing the key itself,...
5k views

Is it possible to brute-force a hash algorithm of 32 bits

I have a 30000 user passwords and usernames stored in a table on a database in which the passwords are stored as hash where ,I need to guess the passwords for all users and I have the hash function ...
833 views

How to reverse this hash function?

I have a function that takes an $m$ byte inputs $x_i$ and maps it a 32 byte outputs $y_j$. The hash function is defined as: $$y_j = \sum_{i=1}^{m} (x_i)^{i-1} \pmod {127}$$ The input is restricted ...
1k views

358 views

Create a potential input for sha-256 hash given a substring of input?

Let's say I'm given a specific SHA-256 hash. Further assume that the SHA-256 input, that yielded this hash contained a known sub-string. Is there a way to find the input (containing the specific ...