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

211–220 of 369 posts

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

#211

Post by SAI_Peregrinus »

riquito wrote: post #87
LadyCailin wrote: post #82

Earlier quoted context omitted.

If you use SHA-256 to encrypt your backup, then I just need to steal your backup and wait 20 years, until that is cracked, and then I can decrypt your backup, even though today you’re using the “correct” encryption.

The GP was likely hinting at SHA1 being an hashing function, non an encryption function, so just applying sha* wouldn't produce a working backup

To be excessively pedantic you can encrypt securely (but slowly for the SHA series) with a hash function of sufficient capacity by running the hash function in CTR mode. You turn it into a stream cipher. Ideally you also MAC the ciphertext, nonce, and other associated data. That's is pretty easy with such a hash function (either use HMAC or a MAC mode of the hash function if supported).

Salsa20 & ChaCha20 cores are hash functions (though not collision-resistant compression functions since it's not needed for their design goal and would be slower) run in CTR mode.[1]

[1] https://cr.yp.to/salsa20.html

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

#212

Post by fanf2 »

upofadown wrote: post #149
newscracker wrote: post #133

General questions: (edit: these are indeed general questions, not just about SHA1) Has anyone else been worried about data deduplication done by storage and/or backup systems, considering that they usually use hashes to detect data blocks that are "the same" (without additional metadata) and avoid storing those "duplicate data blocks" again? Doesn't this seem far worse when you also consider that systems like Dropbox…

SHA1 isn't broken for hashes.

SHA-1 (and SHA-256 and many other hash functions) are subject to length extension, which is how the 2017 shattered attack works: find a pair of short prefixes that work as PDF headers and that have colliding hashes; then append a common suffix such that the different headers display different parts of the suffixes. Once the collision has been found you can easily make your own colliding PDFs - https://alf.nu/SHA1

This breaks anything that dedups on just the SHA-1 hashes of raw files

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

#213

Post by im3w1l »

gpm wrote: post #119
riquito wrote: post #87

Earlier quoted context omitted.

The GP was likely hinting at SHA1 being an hashing function, non an encryption function, so just applying sha* wouldn't produce a working backup

It probably will if your data is less than 128 bytes, and you're willing to wait a few decades to decrypt it.

As an aside, sha-1 is smaller than 128 bytes.

From my numerical experiments (I hope I didn't mess up...) using the random oracle model, the probability that a given key is collision-free is 99.6% if the input is one byte shorter than hash, 1/e if input is same size as hash and 6.6e-112 if the input is one byte longer than hash.

And this holds basically irrespective of key size.

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

#214

Post by SAI_Peregrinus »

gist wrote: post #204
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…

The way I see it, this is what is bad: > We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all. What the…

We typically assume that organizations like the NSA, FSB, Mossad, MSS, and the like already know of such attacks.

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

#215

Post by tedunangst »

p1mrx wrote: post #182
CiPHPerCoder wrote: post #131

Earlier quoted context omitted.

Truncated hash functions are not vulnerable to length-extension attacks. Length-extension attacks are relevant when you design a MAC by passing a secret and then a message to a hash function, where only the message is known. Truncating the hash (which is what SHA-512/256 and SHA-384 do to SHA-512) removes the ability to grab an existing hash H(k || m) (where k is unknown and m might be known) and append junk because…

Why do SHA-512/160 and SHA-512/128 not exist? They could be useful as drop-in replacements for SHA1 and MD5.

You can truncate a hash anywhere you like. But 128 bits is considered too short now.

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

#216

Post by jodrellblank »

gist wrote: post #204
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…

The way I see it, this is what is bad: > We have tried to contact the authors of affected software before announcing this attack, but due to limited resources, we could not notify everyone. Many in the 'security industrial complex' make as if they are doing god's work by their 'research' but from a common sense, man/woman on the street, and layman point of view that is not what appears to be going on at all. What the…

The idea behind your complaint is "if we tell good people about risks, then bad people will know about them. If we keep them secret from good people, then bad people won't find out about them". Or, "if we don't make a list of open doors, then bad people can't find which doors are open". Which is .. not true. Bad people will already be making their own list of open doors, and sneaking through them without being noticed, over and over again.

> all almost all people would do just fine

Here's an ongoing ransom attack in the UK, started on New Year's Eve: https://www.bbc.com/news/business-51017852 The ransom is in the millions of dollars range, Travelex websites in 30 countries down for a week, Sainsbury's money exchange websites down for the same time, and "Dates of birth, credit card information and social security numbers [of customers] are all in their possession, they say."

Not looking at problems doesn't stop problems from existing.

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

#217

Post by im3w1l »

saurik wrote: post #108
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…

FWIW, a lot of very smart people seem to think that we actually do have symmetric encryption in a state where it "works" and is "understood" and that AES is unlikely to be "broken". What we don't really feel so great about is asymmetric encryption, but at least that feels like something P != NP might imply can be done... hashing algorithms just have this problem where if you glance at the information theory you would…

AES may be fine, but what about the block cipher modes?

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

#218

Post by noja »

femto113 wrote: post #156
noja wrote: post #125

Is a collision impossible with two hashes, each using a different algorithm?

Not impossible, but assuming there's not a mathematical flaw that affect both algorithms the difficulty is roughly the product of the difficulty of finding a collision in each. AFAIK no one has come up with a joint collision for MD5+SHA1 despite collisions in each being practical for several years.

So should we do that, as well as keep finding new algorithms?

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

#220

Post by SAI_Peregrinus »

p1mrx wrote: post #182
CiPHPerCoder wrote: post #131

Earlier quoted context omitted.

Truncated hash functions are not vulnerable to length-extension attacks. Length-extension attacks are relevant when you design a MAC by passing a secret and then a message to a hash function, where only the message is known. Truncating the hash (which is what SHA-512/256 and SHA-384 do to SHA-512) removes the ability to grab an existing hash H(k || m) (where k is unknown and m might be known) and append junk because…

Why do SHA-512/160 and SHA-512/128 not exist? They could be useful as drop-in replacements for SHA1 and MD5.

Because 224 bits is considered the minimum safe output length for a general purpose hash function. So they'd be drop-in replacements but still wouldn't be safe. Safer than MD5/SHA1, but not actually safe.

So rather than push off getting people to make things actually safe by providing a footgun NIST just didn't do that.

Post reply on HN