Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [preimage-resistance]

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

2
votes
1answer
52 views

Partial Known Message Pre-Image Attack on SHA-1

If the last 448 bits of a sha1 block input are known (only the first 64 bits are unknown). Is it possible to do a preimage attack using SAT solvers or something else? Or do I have to brute force all $...
4
votes
1answer
472 views

Is there a feasible preimage attack for any hash function (no matter how deprecated) today?

Has there ever been a hash function that was actually used in the field, no matter how long ago, for which there is now a feasible preimage attack? All hashes that are nowadays considered 'broken' (...
-1
votes
1answer
47 views

Add string to create specific MD5?

I have a file that include a long string , I can calc the md5 of this file . Is there any way to know which string I need to add for this file so the md5 of this file will be specific md5 that I want?...
3
votes
2answers
235 views

What do the security definitions of SHA-3 mean, quantitatively?

In the SHA-3 standard (page 31) the security of SHA-3 is defined quantitatively, for example, they are saying SHA3-256 provides 256 bits of preimage resistance. How is this number of bits to be ...
2
votes
1answer
63 views

What is the minimum message length to obtain the full potential of a hash?

Suppose I want to commit to a uniformly picked nonce of fixed length $n$ bits without revealing the nonce, so I use a secure hash function $H$ mapping messages to digests of length $d$ bits. Suppose $...
16
votes
2answers
4k views

What makes SHA256 secure?

For example, RSA relies on a mathematically hard problem, factoring, while ECDSA or similar rely on discrete logarithm problem. What makes SHA256 and similar hash functions, of the same family, ...
1
vote
1answer
27 views

Number of preimages of hash function from bounded domain

Suppose we have an "ideal" cryptographic hash function $H: \{0,1\}^{n+k}\to \{0,1\}^{n}$ and a given bitstring $b\in \{0,1\}^{n}$, Can we estimate how many preimages $H^{-1}(b)$ there are? With ...
0
votes
1answer
38 views

What pieces of information do you need to unhash a key to find out the original message?

I am very new to the hashing world and despite hours of research (AKA Googling) I still don't understand this piece of information. What are the different pieces of information that are needed in ...
2
votes
0answers
64 views

Is the concatenation of one-way compression functions one-way?

Given two independently keyed compression functions $h_1$ and $h_2$: $h_b(x): \{0,1\}^{3n} \to \{0,1\}^{n}$, where $b \in \{1,2\}$. Let $h(x) = h_1(x) \| h_2(x)$. Given at least one of $h_1$ and $...
4
votes
2answers
215 views

If you wrote a reversible SHA-256 algorithm, how many “metadata” bits would be required for reversability?

I was reading about reversible computing while thinking about FPGA circuits. I realized that it would be possible to write a reversible SHA-256 algorithm if you stored some additional information as "...
17
votes
1answer
3k views

What are the consequences of removing a single byte from a sha256 hash?

I'm working on a system (Ethereum) where it is significantly cheaper to store 32 bytes than 33 bytes. I'd like to create a table where data is stored based on its hash. Sha256 would meet this ...
1
vote
1answer
150 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)$ ...
1
vote
0answers
43 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 ...
3
votes
1answer
211 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 ...
0
votes
2answers
125 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 ...
3
votes
1answer
65 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 ...
0
votes
2answers
153 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 ...
3
votes
1answer
64 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
170 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
45 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
158 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
509 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$ ?...
4
votes
1answer
514 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 ...
0
votes
0answers
67 views

How Secure is Hash-based Bit Commitment?

Specifically, I'm following the hash-based schemed from Bruce Schneier's Applied Cryptography. The steps are: Choose a random string R1, a random string R2, and a message M to commit. Send R1 and H(...
2
votes
0answers
67 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
143 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 ...
3
votes
2answers
4k 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
0answers
45 views

collision resistant preimage resistant partial collision resistant

how to compute output from a function lets say SHA3-256 such that the output is less than $2^{215}$ assuming output is of the form $H(m|a|x)$ where $x$ be an arbitrary value which is also 256-bit, $a$ ...
-2
votes
1answer
138 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, ...
-1
votes
0answers
155 views

CBC-MAC with a constant key

What affect does having a constant key have on a CBC-MAC algorithm and how would it make the CBC-MAC not pre-image resistant.
0
votes
2answers
150 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 (...
3
votes
2answers
492 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
282 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 ...
15
votes
1answer
5k 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 ...
1
vote
1answer
423 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
0answers
35 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 ...
3
votes
0answers
80 views

Rabin fingerprint preimage with given length and alphabet

The Rabin fingerprint looks something like this: ...
0
votes
1answer
114 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 ...
10
votes
1answer
476 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
318 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 ...
3
votes
1answer
195 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
46 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 ...
4
votes
1answer
2k 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
74 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 ...
-3
votes
1answer
149 views

Preimage and second preimage resistance for this instance

I'm trying to understand the relationship between preimage resistance and second preimage resistance. Consider the following example. Suppose there exists a hash function H(x). The function produces ...
4
votes
1answer
268 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
100 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
153 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
745 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 ...
4
votes
2answers
383 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 ...