# Tag Info

5

is $T^{1-1/n}$ Proof: Suppose we have a sample set $M$, with $|M| = m$. We choose a set $N$ with $|N| = n$ among the set $M$, which is $O(m^n)$ (you know $O(m^n)=m\cdot(m-1)\cdot...\cdot(m-n+2)\cdot(m-n+1)$). In particular, we suppose $A_1, A_2, ...., A_n$ make a $n$-collision $H(A_1)=H(A_2) , H(A_2)=H(A_3) , ... , H(A_{n-1})=H(A_n)$ just as you want. ...

1

As indicated, SHA-1 is not broken in the sense that practical attacks apply (as of 2014-12-06). So until practical attacks become feasible it is unclear against what scenarios they can be mounted. Probably the best thing to do is to have a look at what is happening with MD5. It is likely - but not certain - that attacks on SHA-1 would have largely the same ...

5

The question asks how a collision in a hash such as SHA-1 could become a practical concern, with focus on the case of a public-key certificate à la X.509. I'll first give an example involving executable code signing. I'll assume an attacker in a position to write bootstrap code (like, the supplier of a development toolchain, or someone who compromised ...

-1

In many cases it is the hash and not the plaintext that is being compared. For example, in most password systems, the ability to create hash collisions could allow an attacker to forge a password without having to guess the original password. Would this be useful by itself? Perhaps not, but there many examples of crypto systems being broken through a ...

-1

Let me add these paragraphs for clarity, but I still stand behind my below answer, as your question does not specifically address what you already understand Crypto-learner. MD5 as an example of an older uses the Merkle-Damgard construction as do SHA1 and SHA2, however, MD5 have some intrinsic vulnerabilities like the chosen prefix collision attack which ...

2

No, it is not possible. If two inputs with different length produce identical hash outputs, then there would be a collision in the last invocation of the compression function. This is because the last input to the compression function always encodes the length of the original message. If two inputs with identical length produce identical hash outputs, then ...

6

Yes. Let $H$ be a collision resistant hash function and assume that one can find a collision $(x,y)$ for $H\circ H$, that is $x,y$ with $x\neq y$ and $H(H(x))=H(H(y))$. Consider the results $H(x)$ and $H(y)$ of applying $H$ once to both inputs. Then either $H(x)=H(y)$, hence $(x,y)$ is a collision for $H$; or $H(x)\neq H(y)$, hence $(H(x),H(y))$ is a ...

5

If the first application of H results in a collision then, so long as H is deterministic, any subsequent applications will collide. Thus iterated applications of hash functions will increase your collisions and is likely to degrade your security depending on what properties you need. For demonstration purposes only lets pretend we have SHA2-8, that is ...

0

Yes, of course it is possible. Let's consider with below example: Our compression function: $f:\{0,1\}^{(128+512+1)} → \{0,1\}^{128}$ Message $x$ has 1000 bits: ($y$'s are our input blocks and $z$'s are output blocks. Considered a Merkle–Damgård construction.) $y_1$ is first 512 bits of $x$ $y_2$ is last 488 bits of $x||0^{24}$ $y_3$ is ...

3

Ok, here's how it is supposed to work: we take the function (which maps a string of $n$ bits to a string of $n$ bits), and iterate it repeatedly. After some amount of time, we'll run into a loop (that is, we'll evaluate to a value that we visited before, and there after, we'll repeatedly run through the loop). And, we'll run the function iteration twice, ...

Top 50 recent answers are included