151–160 of 173 posts
Earlier quoted context omitted.
That requires way more hashes to be computed though.
I don't think that's correct? It's probabilistic, yes, but in expectation you would still need ~2^64 hashes to find a collision for a 128-bit hash (birthday paradox).
Earlier quoted context omitted.
I don't think that's correct? It's probabilistic, yes, but in expectation you would still need ~2^64 hashes to find a collision for a 128-bit hash (birthday paradox).
See my above comment. There's a huge difference between having a collision somewhere in a pile of 2^64 hashes, and actually having the colliding hashes ready to present.
Earlier quoted context omitted.
> The security (i.e. the difficulty in finding collisions) decreases with the length of the document for SHA-2 Could you spell this part out for me?
Twenty years ago this paper was considered surprising and, together with a handful of other attacks and with the concrete attacks against MD5 and SHA-1 succeeded by some Chinese researchers prompted the organization of the SHA-3 competition. John Kelsey and Bruce Schneier: "Second Preimages on n-bit Hash Functions for Much Less than 2^n Work" https://eprint.iacr.org/2004/304 The abstract at this link provides the ess…
Earlier quoted context omitted.
See my above comment. There's a huge difference between having a collision somewhere in a pile of 2^64 hashes, and actually having the colliding hashes ready to present.
Are you trying to get at the distinction between second preimage and collision resistance? If all you need is a collision, "try random pairs until you find a collision" method works fine and is arbitrarily parallelizable with no storage.
That requires you to do 2^128 checks on average, not 2^64. Again, the problem is that the birthday problem only exists if you have all the hashes available to compare. If you're just doing two hashes at a time and comparing the two, the chances of you getting a match for each try is 1 in 2^128, and this is independent for each attempt. To get a 50% chance you need 2^128 attempts.
If you can't see why that's the case, you can empirically test this, by using a 16-bit "hash" rather than a 128-bit hash: https://pastebin.com/7xW04Jgg
The average I got during one invocation was 58161, which is 2^15.8, not 2^8 as you'd expect. However, if you modify the code to include a storage/retrieval system: https://pastebin.com/AxF9S0q5, the average drops to near 2^8. For my last invocation, I got 309.7 which is 2^8.2
I've been wondering, is there a term for a type of attack like this: Given a message M, length function L(), and MD5 hash function H(); is there an attack which can generate message M', such that H(M)==H(M') _and_ L(M)==L(M')? In other words: Two different messages, both of the same length, with the same hash? It's almost like a chosen prefix collision attack, but with no prefix (so P is empty) and a given message (M…
I don't know anything about GridFTP - but there's a huge difference between verifying if files were "transferred correctly" and verifying that files were transferred without being tampered with by a malicious party. MD5 is fine for the first task, and totally unacceptable for the second.
I've been wondering, is there a term for a type of attack like this: Given a message M, length function L(), and MD5 hash function H(); is there an attack which can generate message M', such that H(M)==H(M') _and_ L(M)==L(M')? In other words: Two different messages, both of the same length, with the same hash? It's almost like a chosen prefix collision attack, but with no prefix (so P is empty) and a given message (M…
That is still an attack on the second preimage or a collision resistance properties of the hash function. Most collisions do work this way, for example see [1]. [1] https://github.com/corkami/collisions
Earlier quoted context omitted.
> Help us out by describing a time when this happened. Linus Torvalds saying that SHA-1 is okay for git, while it is used for Git signatures as well. Signatures are a classic "you need collission resistance to have safe signatures, but people are often confused about it" case.
I might be mistaken, but wouldn't a git signature already be signing trusted things (i.e. the person making the original signature is trusted), making any attack enabled by the input hash function a second preimage attack (i.e. an attacker onky knows the trusted input, not anything private like the signing key)? Hash collisions mean you can't trust signatures from _untrusted_ sources, but git signatures don't seem to…
If an algorithm is collision resistant a signature guarantees both authenticity and integrity. If it's just second preimage resistant, signing may only guarantee authenticity.
Now, the issue with Git using SHA-1 is that an attacker may submit a new patch to a project, rather than attack an existing commit. In that case they are in control of both halves of the collision, and they just need for the benign half to be useful enough to get merged.
Any future commits with the file untouched would allow the attacker to swap it for their malicious half, while claiming integrity thanks to the maintainers' signatures. They could do this by either breaching the official server or setting up a mirror.
One interesting thing to note though: in the case of human readable input such as source code, this attack breaks down as soon as you verify the repo contents. Therefore it's only feasible longer term when using binary or obfuscated formats.
The article mentions the key detail: MD5 is broken for cryptography (collisions) but not for second preimage attacks. I was hoping there would be some discussion of just how much more difficult the latter is. It is extremely difficult. Let’s ignore that no second preimage attack is currently known for MD5. The software the author links to has a FAQ that links to a paper that lays out the second preimage complexity fo…
Earlier quoted context omitted.
There's a GIF MD5-quine here: https://news.ycombinator.com/item?id=13823704 And a PNG version too: https://news.ycombinator.com/item?id=32956964 But no one has made an exclusively plaintext (ASCII) MD5-quine yet, and I suspect doing so may be impossible given the characteristics of collision blocks.
How is it impossible? I would think an MD5 quine exists with probability approaching 1 as the size of the document grows to infinity. Think about the reduced problem: 1. a document containing "1", whose hash begins with "1" 2. a document containing "12", whose hash begins with "12" 3. a document containing "123", whose hash begins with "123" #1 is certain to exist. #2 exists, but would take 16x as long to brute force…
The problem is that we currently don't know how find it more efficiently than with exhaustive search, AFAIK.
Edit: previously on HN: https://news.ycombinator.com/item?id=614079
Earlier quoted context omitted.
Twenty years ago this paper was considered surprising and, together with a handful of other attacks and with the concrete attacks against MD5 and SHA-1 succeeded by some Chinese researchers prompted the organization of the SHA-3 competition. John Kelsey and Bruce Schneier: "Second Preimages on n-bit Hash Functions for Much Less than 2^n Work" https://eprint.iacr.org/2004/304 The abstract at this link provides the ess…
Thanks! I've added a note about this here: https://github.com/oconnor663/bao/issues/41#issuecomment-119... . Does that sound like an accurate summary to you?
Incorporating somehow a block counter in the block hashing function or using a sponge structure is equivalent to using a different hashing function for each block, which stops the attacks.
Tree hashing where the final branches i.e. the chunks are short, so there are only a small number of blocks hashed in cascade with the same function, behaves differently from linear block chaining, because the hashing function must include additional inputs anyway, so the blocks in a chunk are hashed differently from the blocks that merge tree branches or the root block.
Whether any of the attacks that exist for simple Merkle-Damgaard cascading like SHA-2 are applicable to a tree hash depends on how the blocks are encoded and on the structure of the tree. In any case, the probabilities of success will be different in the case of a tree hash.
I have never analyzed whether the BLAKE2 or BLAKE3 tree hashes could be secure enough without block counters. In any case, the block counters, which are absolutely necessary for linear block chaining, also increase the strength of tree hashing against any attacks and their added overhead is minimal, so there would be no reason to remove them.
A hash computed with a sponge structure, like SHA-3 or KangarooTwelve, is equivalent with a CBC-MAC where the key is updated at each block, instead of being constant. Because each block is hashed with a different key, there is no need for an additional counter input to differentiate the hashing functions. A sponge structure is much simpler than the structure used by BLAKE, but it needs a wider invertible mixing transformation, e.g. for a similar strength BLAKE2b uses an 1024-bit mixing transformation, while SHA-3 uses an 1600-bit mixing transformation. (BLAKE3 trades off strength for speed, so it is not comparable with SHA-3, but only with KangarooTwelve.)