Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The first chosen-prefix collision for SHA-1

sha-mbles.github.io

Post reply on HN
Print view View original

361–369 of 369 posts

Re: The first chosen-prefix collision for SHA-1

#361

Post by espadrine »

cipher_314159 wrote: post #322
tambourine_man wrote: post #76

This kind of thing always brings me down a bit. It's not rational, but it does. I mean I truly admire these folks skills, the math involved is obviously remarkable. But I think the feeling is related to not being able to rely on anything in our field. Hard to justify going to the trouble of encrypting your backup. 10 years from now, it might be as good as plain text. It's not security only, nothing seems to work in t…

> 10 years from now, it might be as good as plain text. I created an account just to chime in on this. In short: horseshit. Look, cryptology is a tricky field, but when it comes to standards development (especially OPEN standards development, without government intervention), it's mostly been hits, not misses. While there are occasional breaks and busts, the fact is, most of the trusted algorithms have remained trust…

I agree with comments.

All ciphers older than 100 years have been broken, except for one.

However, it seems to me that designs improved exponentially, while attacks only improved quadratically. The old days of WWII where Enigma was broken before the end of the war will never happen again.

Conceptually, it makes sense: Science improves quadratically because breakthroughs improve tooling that accelerate breakthroughs. I am simplifying here, but if you have N tools at T1 that make you progress at rate R1=N×K, and that progress yields another tool: at T2 you have N+1 tools, making you progress at rate R2=R1+K. Your progress is P2=P1+R1, which generalizes to Pn+1 = Pn+n×K = P0+K×N×(N-1)÷2, a quadratic progression.

On the other hand, cryptographic security is exponentially better with every bit. If an old cipher uses its bits badly, it will still be good enough if it is long enough. Let's say it reaches a given difficulty level after 10 rounds; a cipher that uses its bits twice as well will reach the same level after 5 rounds, but would have something like 2^K times that level after 6, 2^2K times after 7, … 2^5K times after 10, reaching a level that quadratic improvements won't reach for an increasingly long time.

For instance, it took 5 years for MD4 (1990) to have a practical collision, 12 for MD5 (1992), 22 for SHA1 (1995), therefore roughly doubling every three years. If we extrapolate, SHA2 will have a practical collision in 2080.

Re: The first chosen-prefix collision for SHA-1

#362

Post by klyrs »

thekyle wrote: post #256
jessant wrote: post #244

Earlier quoted context omitted.

What is considered sufficiently far future may change with life extension technology.

Well I would assume that as long as you live you'll keep updating your crypto as new tech comes out. That way the clock only starts ticking when you die.

Your encrypted communications, intercepted today, will be encrypted with today's standards. The clock is ticking now.

Re: The first chosen-prefix collision for SHA-1

#363

Post by tialaramex »

mehrdadn wrote: post #237
saurik wrote: post #229

Earlier quoted context omitted.

1) The premise of a hash function is that you are going to take a large set of inputs and map it to a small set of outputs such that you don't find collisions, with the use case that the result is somehow so unique that the input file can be henceforth named by its hash and looked up in some giant dictionary of everything we have so far ever bothered to hash. The hash is this tiny bit of information, and somehow is e…

1) Oh I see what you mean now. Yeah I guess it depends on your intuition. 2) I mean, I'm not sure how correct your premise that symmetric ciphers are more secure than hash functions is, but it literally is something that is done. You can read more about it in [1], including the possible pitfalls. The transformation should provide more than enough intuition to see why both are equally plausible, which was the point of…

So, the intuition defying part happens in the transformation you're talking about.

The block cipher behaves how we expect, I'm confident that many of the ciphers used inside real hashes like SHA-256 are good block ciphers and either would not be broken if we used them as block ciphers or could be repaired by competent cryptographers to be robust enough so that they didn't get broken over their lifetime after the repairs were done.

But the transformation to get a hash introduces the effect that your parent sees (I think correctly) as unintuitive. Normally if I put a megabyte of plaintext into a cipher I get back a megabytes (or slightly more depending on my mode of operation and rounding up due to block size) of ciphertext, but this transformation ensures we always get one block back, the hash of a Wikipedia dump and of my address book are the same length for a particular hash function. The "block" is bigger than we're used to from popular block ciphers but that's what it is, one block.

And that's where the concern appears. Why is that safe? Surely that shouldn't be safe at all? And yet, it seems, it is successful, more or less, until it isn't.

Re: The first chosen-prefix collision for SHA-1

#364

Post by tialaramex »

espadrine wrote: post #361
cipher_314159 wrote: post #322

Earlier quoted context omitted.

> 10 years from now, it might be as good as plain text. I created an account just to chime in on this. In short: horseshit. Look, cryptology is a tricky field, but when it comes to standards development (especially OPEN standards development, without government intervention), it's mostly been hits, not misses. While there are occasional breaks and busts, the fact is, most of the trusted algorithms have remained trust…

I agree with comments. All ciphers older than 100 years have been broken, except for one. However, it seems to me that designs improved exponentially, while attacks only improved quadratically. The old days of WWII where Enigma was broken before the end of the war will never happen again. Conceptually, it makes sense: Science improves quadratically because breakthroughs improve tooling that accelerate breakthroughs.…

There's a quantum leap in cryptography in WWII and it's a real shame that's so rarely explained even at Bletchley where they'd be well-placed to do it.

Engima (like most systems in use in the 1930s) is thinking about cryptography as being some sort of art in which the idea is to sort of stir letter symbols. Everything else often can't even be encrypted or must be elaborately transformed into letter symbols first. Bletchley has replica "Bombes" which would be used to attack this mechanically, replicating the function of the Enigma machine to defeat it.

Lorenz, which was also attacked at Bletchley using the Colossus, is a modern stream cipher. It XORs a pseudo-random stream against your plaintext bits (albeit in the 1940s these were in 5-bit ITA telegraph code) and so it isn't different in core principles from say RC4 or at a greater distance in time indeed Salsa20 - Lorenz just has about 56-bit keys where these modern ciphers have more and are better designed. Attacking this mechanically was impractical, and that's why a computer like Colossus was needed.

As a result it really isn't fair to compare 100 years ago. If we look back 50 years instead the difference is stark.

Re: The first chosen-prefix collision for SHA-1

#365

Post by MichaelMoser123 »

munificent wrote: post #166
MichaelMoser123 wrote: post #138

Earlier quoted context omitted.

are there any systems that do sha-1 for dedup? I am only aware of sha-256.

Git?

git computes the sha1 checksum over the header that includes the length + the file data; also checks the length in the header as well as the the hash; Linus says that it would be less practical to find a collision that has the same length as the original data; I guess at some stage even that might become possible.

Re: The first chosen-prefix collision for SHA-1

#366

Post by perl4ever »

jodrellblank wrote: post #352
perl4ever wrote: post #348

Earlier quoted context omitted.

"The internet brings a much bigger attack surface than local people who can reach a front door" "Local people", huh. My front door is visible to everyone on the internet, and I have no practical way to prevent that. Some obscure company went by with their mapping vehicle and... Now, some people do live in big buildings where less is exposed to the outside, but millions don't.

> and... and... what? Unless telekinesis has been invented, a photo of your door doesn't increase the amount of people who are able to try opening your door. If you're about to say "someone might choose to come a long way just for my door" then that seems like an argument in favour of what I'm saying - in that case, wouldn't you like to know about any vulnerabilities your door has which you could address, before they…

I'm not really arguing in favor of doing anything in particular; I was just pointing out that people rely on "security by obscurity" in day to day life, despite the fact that everything is connected to the internet. Perhaps there are some subtleties in exactly what "obscurity" is.

I'm saying the ideas I read about how the world is don't seem to be connected to my view of reality. I don't have to argue with your conclusions to find fault with your premises, and I'm feeling too lazy to do it right now.

Re: The first chosen-prefix collision for SHA-1

#367

Post by tatersolid »

LennyWhiteJr wrote: post #270

The root certificate authority for my company's Active Directory is signed using a sha1 hash. What are the practical implications of this chosen collision? How do I convince my IT department to update our CA to sha256?

The signatures on trusted root certs do not matter and are ignored; it’s the public key you’re trusting.

Many public trusted CA certain are self-signed with SHA-1. These keys sign using SHA-256

Re: The first chosen-prefix collision for SHA-1

#368

Post by rakoo »

jessaustin wrote: post #296
rakoo wrote: post #226

Earlier quoted context omitted.

But backups have existed for more than a dozen years. And its replacements today, SHA-256 and SHA-3 will also be broken if you wait long enough.

I can see why backups might be needed for a dozen years, and I can see why encrypted backups might be needed, but outside plainly fake requirements like those of "national security" why would encrypted backups be needed for a dozen years? Aren't we throwing everything sensitive away after seven years? After that isn't it mostly about preserving history? Even things like balance sheets that might be sensitive today wi…

The obvious counter-example is my library, however old my photos or music or videos are I'd like to keep them for as long as possible, and because they're private I'd like to keep them in an encrypted form

Re: The first chosen-prefix collision for SHA-1

#369

Post by newscracker »

onei wrote: post #224
jbverschoor wrote: post #148

Earlier quoted context omitted.

Yep, I'm afraid of that. I have no idea how they are mitigating this, and I doubt they'll ever disclose.

From what I recall when the first collision was proved it was with a PDF which is easier to craft a collision from. I also seem to recall that the collisions were from hashes of the whole file. The dedupe engine written where I work chunks a file and hashes those chunks meaning it's somewhat harder to craft collisions (I forget where the chunking boundaries are, but it's within a range iirc). The hashing algorithm wa…

In my generic question above, I wasn't referring to someone intentionally causing collisions, but about random collisions that could occur because of these data chunks coming from a large pool of data (say a system with tens or hundreds of millions of users with several hundred GB each of varied data among them). AFAIK, chunking methods usually do not use additional metadata (like a file timestamp or size or name) that could help do a more comprehensive comparison instead of relying on a hash alone. Are the chosen chunks very small (which means the number of hashes would be quite large, making deduplication take longer when looking for exact matches)? I'd be interested in writings from real systems online that explore the choices they have taken and how they pre-empt random collisions (as much as they can design it into the system).
Post reply on HN