Hacker News Reader

What happens is you'll write a paper titled "The first SHA-256 collision: SHA-256 is broken in practice", since there are currently no known collisions (despite Bitcoin miners computing exahashes per second). The chances of you finding the first known collision by accident are overwhelming slim, and the benefits of showing that a widely used hash function is broken would greatly exceed the annoyance of a broken system.

No one I know of ever breaks these systems with exhaustive searches. Holding an exhaustive search up as some kind of bedrock of security is foolhardy.

As for cryptography, its all based on primes, and have you been watching what papers are being published regarding more efficient methods and searches for primes?

Ethical people would publish, unethical people would sell it to everyone elses detriment.

Cryptography is not all based on primes.

You are making a lot of over-general assumptions in your posts.

The modern cryptographic functions we were talking about are all based on primes.

Unless you are suddenly trying to shift gears to muddy the water for some other purpose and apply what I said to 'all cryptography', it was pretty clear what we were talking about prior to this response.

Perhaps you should do a bit more research into the origin of those magic constants that get used to initialize those functions.

Where do you think they come from... yes you could change them but then you wouldn't be following the specification, and you can't legitimately call it the same thing.

AFAIK, they are all in some form related to primes, whether that's a truncation of a floating point representation of a prime or some other operation like a square root of a sequence of primes, because evidence has shown that the chaotic nature of primes works best and this is a property we want in cryptographic systems.

> The modern cryptographic functions we were talking about are all based on primes.

No. They aren’t. Not elliptic curves, not any hash functions, not AES, not ChaCha20, and not any of the post-quantum stuff NIST is tossing about.

RSA is. That’s about it. And RSA is being rapidly phased out.

> AFAIK, they are all in some form related to primes

That's plain wrong. Primes are being phased out in crypto, elliptic curves are decades old at this point, and lattices are everywhere in recent research.

> origin of those magic constants that get used to initialize those functions.

For others interested, the magic constants are normally truncated binary of a known constant like e or pi, derived from famous texts, roots of small primes, etc. But the reasoning is that these are common, simple to reproduce numbers that can't be chosen to produce desired results. A.k.a "nothing up my sleeve" https://en.m.wikipedia.org/wiki/Nothing-up-my-sleeve_number

Sha256 is using some prime, but other hashes and systems don't and it doesn't matter at all in this context. They just needed a simple random initial value. I'm half convinced op is trying to use cleverly worded half truths to troll us.

If you think I'm trolling then you are jumping at shadows.

You're not the one taking huge karmic hits for taking an unpopular opinion, and a lot of kids are using bots to try to de-amp that, like that even matters. So many people these days (if they aren't bots) regularly commit acts of true evil without even realizing it.

You know what I find really sad. No one can talk about anything because people use voting as a way to punish people based on their shallow feelings rather than the content, if they are even real people at all. Most of the time their bots controlled by a small group of people.

Its sad because to think and express real intelligent thought one must risk being offensive, and to learn one must risk being offended. If you don't allow that, you're stripping people of voice or the ability to become more intelligent which is a true evil.

When those that don't think outnumber those that do, why should any intelligent person try to solve the unintelligent majority's problems? :: shakes head, so shortsighted::

I hope you have a happy holiday despite all the negativity. I blame HN for switching their banner to red, it always brings out the absolute worst in people.

I don’t think you quite appreciate how remote the possibility of a SHA-256 collision is.

Barring a catastrophic break, there will never be a collision witnessed across the full lifespan of humanity.

I don't think you understand the difference and fluidity of what a distribution is and how it differs from likelihood curves.

You've made some significant assumptions, one of those assumptions is that the brute force way is the most efficient way or put another way there is no optimal way to calculate collisions better than brute force.

That line of thinking is very flawed. Has shown to be flawed many times in the past several decades, and shouldn't even be up for debate given the evidence and deprecation of various cryptographic functions (as vulnerabilities become known publicly). We all know vulnerabilities were known before the deprecation because detection is a lagging process.

Also note, as far as the respondents of the project I've spoken with have said, they do not even check for existing collisions. So if a collision did occur, you wouldn't even know it without specialized knowledge.

What kind of collision are you envisioning? And what's the failure case? Two packages that suddenly have the same hash are still going to differ in the package name and version string, and thus different directories on the nix store.

You can never have something compromised injected onto your computer this way either because nix requires signed builds to download from a remote repository. If you trust a malicious repository... that's on you. By default, only nixpkgs is trusted with the default hydra.

package name and version string are part of what, the metadata manifest provided right?

As a thought experiment, say a collision is found for libc or the standard library, thanks to all that research on primes that's been released recently, assume a more efficient search is found.

What would the failure domains be for those two libraries if, a) the library was non-functional suddenly, or b) the library remained functional but malicious.

Would Nix detect the collision, or would Nix simply recreate the dependency graph overwriting the old but secure with this new malicious software.

Almost all of the security primitives are implemented at domain edges, which means local access, or remote exploitation would have equal effect, and a watering hole/supply chain attack may not even be necessary.

Nothing would happen. Like the other commenter said, you trust your package repo like with any other distro.

So, basically, you're saying that Nix is insecure, because you need hash collision + signature forgery + malicious access to repos; whereas in a standard distro, you only need signature forgery + malicious access to repos?

I really don't get your point.

> thanks to all that research on primes that's been released recently, assume a more efficient search is found.

That's just trolling. Primes have nothing to do with sha256 beyond the initial value. It's just bitwise operations and additions.

> hashes (galois fields)

Huh? What do hashes like Sha256 have to do with Galois fields?

Math, the hash function use magic numbers which in turn initialize and eventually map to a specific Galois Field, they are also called finite fields.

You have a set field size as you go over it, it loops and so output fields are never unique, you have a 1:infinite relationship. That property to determinism, there are problems computers cannot solve but we can. A computer requires determinism to do work, which in effect is that 1:1 state->next state mapping on the state graph. There's a lot of computer science theory and literature on this if you want to dig deeper. MIT has an OCW course in signals and systems.

Anywhere you see modulus math happening, its working with finite fields.

That's flat out wrong. Working modulo 4 is not working in a finite field, because 22 = 0 when you work mod 4. When you work modulo a prime, then you are working in a finite field. Working in the finite field of 4 elements is not* the same as working mod 4. Finite fields of size p^n are not the same as (not isomorphic to!) the ring Z/(p^nZ) whenever n > 1.

Just because there exists a finite field of size 2^n doesn't mean that any length-n-bit-string that is the output of a hash function lives in a finite field of size 2^n.

Adding and multiplying hashes doesn't make any sense. If it does then you have a very weird hash function. Not one of the standard cryptographic hashes. So saying that a hash function maps onto a finite field sounds pretty confused to me.

2 times 2 = 0 mod 4. Sorry for the markdown mess-up.

What are the alternatives which are properly deterministic?

Any of the existing packaging solutions work to a greater or lesser degree so long as the namespaces guarantee uniqueness in the package identity and dependency graphs which is what most packagers do when they put it together for other distros.

As for automating the identity hash generation so it is perfectly deterministic, its not possible so long as you map onto Galois Fields due to their finite field length (and inherent non-unique solutions).

I'm not aware of any mathematical alternative for cryptography, to finite fields, and a hash is a cryptographic function.

Strictly speaking, you have a tradeoff in terms of stability as well as additional cost from the language complexity, and non-deterministic behavior is the fallback when discrete time invariance or determinism is violated.

Many people like Nix, but many people also don't understand how it works, and thus it will work until it doesn't, and then you'll be stuck.

Its not like there is tooling to check determinism, and if time invariance fails because of say a cache (memory property), then you can't even troubleshoot because everything we do to troubleshoot relies on those fundamental system properties with exception to Guess and Check which to be successful requires the highest specialization and understanding of the system.

> Many people like Nix, but many people also don't understand how it works, and thus it will work until it doesn't, and then you'll be stuck.

Until what doesn't work? The base system is verified continuously, so there's no chance some two packages are linked against each other causing a boot problem.

If there's really a problem ever, then you just find the old system and start it on boot to one that doesn't include that package. This is straightforwards because most nix users have multiple nixos versions installed at once. Then, you update the offending package to not hash to the same thing (add a comment to a build script).

Non-deterministic problems don't give you clear signs that they are those class of problems.

The system works so long as its deterministic, this is a requirement for computation to do work.

Then it stops working or doing work when its no longer deterministic. It does this in unknowable ways, unplannable ways, and you often won't know why something failed or even if it did fail. The only concrete characterization non-determinism has is the result was not expected.

Troubleshooting and repeatability doesn't work, you get different results each attempt.

Many things can happen non-deterministically including data corruption.

Its not nearly as simply or safe as you make it out to be.

You are making light and minimizing non-deterministic issues.

> Any of the existing packaging solutions work to a greater or lesser degree

The infantesimal chance that a collision could cause a few hours (at most!) of hassle seems to me to be a far better trade-off in terms of stability and ease of applying and undoing changes compared to pretty much any package managemer that I've used.

Unfortunately, these are famous last words in a professional IT environment.

I've heard the exact same argument almost verbatim from a C-level exec who got fired after an outage. It was regarding backups and the infantesimal chance that we would have a power outage.

It fundamentally assumes a lot of critical things that you can't control. If you follow your own advice, you will eventually be wrong, and pay more for it than you would have otherwise.

As for undoing or applying changes, I've had nothing but praise for rpm, its pretty rock solid with the right setup, and better, because it is maintainable and supportable.

You don't get it. The main issue with a hash collision in sha256 wouldn't be Nix breaking for a few hours; it would be the modern internet breaking down.

I don't see why you get so fixated on Nix rather than preaching about anything else using sha256.

> infantesimal chance that we would have a power outage.

Power outages are experienced every day in every country; sha256 collisions are still to be found. That's not the same magnitude of ‶infinitesimal″ at all.

I'll admit, I don't have a ton of experience with rpm- I've generally avoided it since I had to help a client deploy a website on I think CentOS, and the available packages for imagick, language X, and language-X-imagick bindings were all three incompatible with each other. Not a great excuse, but I since lean towards other distros and tools.

In that sense, I alone have lost more time to rpm than the entire world has with nix sha256 collisions.

Adding support for collision detection to nix, involves a one or two line change to libstore. You should implement such an assert statementt and contribute it to Nix. Nix is open-source and would likely gladly accept it.

You are way overstating the importance of this. This is not a fundamental design flaw in the nix ecosystem. If there's actually no check it's because most people realize this is not a problem worth spending a lot of time on. But the time required here is a few minutes at most.

Just because finite fields are finite doesn't mean that every finite "thing" is a finite field.

Hashes don't really map onto finite fields. They purposefully try to not preserve any algebra.

> so long as the namespaces guarantee uniqueness in the package identity

There are existing issues from this not being the case. Uniqueness of names can only be guaranteed in a single repository and this causes many problems for people pulling from multiple enterprise repos (because everyone packages their own ruby for example). Then they start using omnibus packages instead with their own libraries up to libc, which... it's basically half of poor-mans nix-store.

> Many people like Nix, but many people also don't understand how it works, and thus it will work until it doesn't, and then you'll be stuck.

Considering git still uses sha1 and just about all of web cryptography uses sha1 or sha256 for signatures, block deduplication uses typically 128b hashes, etc., we'll have other problems way before this becomes a problem for nix.

Basically you're worried about a collision in nix, when the whole stack of 10 different things leading to you even reading an article about nix already relies on no collisions.

This will not be an accidental issue within multiples of our lifetimes, and malicious actors will not 0day some nix package in public.

Nix has so many problems with misdesign that this is the last nail.

first: i know some folks who use nix and it works very well for them.

next: but not me tho. the experience:

To be clear, I had a laptop with Nixos as daily driver for about 9 months and it was total hell. The thing that finally forced me to switch to ubuntu (yes, that. at that time i needed working software for 7hours already. studying another five A3 pages of what could have hypothetically go wrong and how to maybe fix it was far beyond the scope what i needed to do.) was some component needed by pyqt4 and pyqt5 and nix could not handle it in any way. i've reported the issue which was subsequently fixed about 8 months later. thanks but not again.

the nix language itself is a hard no. 3 days worth of figuring out stuff instead of having it done in 15 minutes is a usability joke.

then there is guix that has the very same problems you mentioned, because the re-used that hashing nonsense from nix.

looking into /nix/store makes me want to cry every time. i just cant believe the current state (implementation) could be taken seriously by anyone. i have a strong feeling that after 19 years of development nix got into stage when it needs complete redesign and rethink way of doing stuff.

Nope. I stopped using Ubuntu after realizing it offers no benefits over windows. You still have to reinstall the thing every few years when it ends up breaking, and good luck and Godspeed if you ever die in the middle of an upgrade. Oh and it just accumulates cruft and random configuration settings after a while. Thanks, but no thanks. I've had too many ubuntu systems end up in states where something doesn't work with no guide on the internet. In nix, I restart and choose an older generation and I'm left with a clean system. That's the way a computer should work. Are there problems sure? But the class of problem is wholly different.

Ubuntu isnt good at all, compared to windows its far better os, but still crap. Nix? Where not even regular bash script works? What a joke. One big hack. Benchmark of symlinking a dynlinker with no benefit to users, just making things mega complicated, slow, non-configurable or outright not working as (I) used to with no clear workaround.

Yea, tell that Nix is good to admins. They might appreciate. Desktop? No way. Devs? Not even remote. I'd give it 2 out of 10.