# Questions tagged [preimage-resistance]

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

139 questions
Filter by
Sorted by
Tagged with
389 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 ...
82 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 ...
555 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 ...
75 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: ...
709 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? ...
619 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$ ?...
429 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?
575 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 ...
97 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 ...
401 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 ...
11k 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 ...
185 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, ...
316 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?
329 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 ...
6k views

### Could we break MD5 entirely in the future?

Even of today MD5 is (sadly) still heavyly 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 ...
901 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: ...
153 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 ...
404 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....
641 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 ...
408 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 ...
219 views

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

The following implementation, here for illustration: ...
115 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 ...
90 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 ...
465 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....
157 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 ...
695 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 ...
715 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 ...
632 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?
909 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 ...
262 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 ...
263 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 ...
158 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,...
4k 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 ...
824 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 ...