Questions tagged [preimage-resistance]

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

Filter by
Sorted by
Tagged with
0
votes
2answers
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 ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
1
vote
0answers
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: ...
1
vote
1answer
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? ...
6
votes
1answer
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$ ?...
2
votes
1answer
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?
4
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
3answers
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 ...
6
votes
2answers
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 ...
-1
votes
1answer
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, ...
0
votes
2answers
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 (...
5
votes
2answers
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?
8
votes
1answer
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 ...
19
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
0answers
101 views

Rabin fingerprint preimage with given length and alphabet

The Rabin fingerprint looks something like this: ...
0
votes
1answer
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 ...
4
votes
0answers
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....
10
votes
1answer
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 ...
3
votes
1answer
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 ...
2
votes
1answer
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: ...
1
vote
0answers
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 ...
5
votes
1answer
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 ...
1
vote
0answers
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 ...
4
votes
1answer
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....
2
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
-3
votes
3answers
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?
15
votes
3answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
1answer
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,...
0
votes
3answers
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 ...
-2
votes
3answers
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 ...
6
votes
1answer
904 views

What is the security strength of an n-bit HMAC?

HMACs depend on preimage resistance, or so I have read. The security strength of hash function with an $n$-bit output against collision attacks is $2^{\frac{n}{2}}$. Against preimage attacks, it is $2^...
-4
votes
2answers
804 views

Decrypting SHA-256 with SHA-256 as input?

Is there a way to somewhat decrypt a SHA-256 hash, provided that the initial string was also a SHA-256 hash? If not, could anyone link me to a rainbow table containing some of the $16^{64}$ possible ...
1
vote
1answer
269 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 ...
1
vote
1answer
230 views

Does absence of second pre-image resistance infer absence of pre-image resistance?

Talking about hash functions, I know the hierarchy is as follows: Pre-image resistance Second pre-image resistance Collision resistance Where each property implies the one before it so 2nd pre-...
1
vote
1answer
209 views

Determining collision resistance of a function?

I am having trouble trying to understand if the function is collision resistant. As I understand it, preimage resistance means that it is hard for an adversary to find two messages that produce the ...
2
votes
1answer
563 views

Why does a fixed key not make MACs like CBC-MAC or GMAC into secure hash functions? [duplicate]

Why does setting the secret key to a fixed, public value not make MACs like CBC-MAC or EMAC into secure unkeyed cryptographic hash functions? In other words, why is the resulting hash function not ...
2
votes
1answer
711 views

Are there any successful preimage attacks?

Are there any successful preimage attacks on any serious cryptographic hash algorithm or at least on serious-looking non-cryptographic hashes (like MurmurHash)?
4
votes
1answer
325 views

Is finding collisions in a part-hash not often enough a bad problem?

My situation: I've been working now for a couple of months on my own unique hash function, I've changed it many times and had two main versions but I won't bore anyone with the details of my work; at ...
2
votes
1answer
117 views

Does including the size of the hashed data improve security over just the hash

Trying to settle a discussion at work. We are mostly concerned with pre-image resistance. Suppose we have a common secure hash function $H$ (e.g. SHA-1/SHA-2) and some message $M$ we want to hash. ...
2
votes
1answer
1k views

What's the perfect chain length : number of chains ratio for rainbow tables?

I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of ...