Hacker News Reader

Thank you for your quick answer.

> I am not sure what you mean by X25519's "collision resistance" vs the file key's "preimage resistance".

There's a significant difference, not only with multi-user attacks (which I see you know of), but with your chances of success with scaled down brute force attacks. If you divide your key search effort by 10 your chances of success are divided by 10 (linear drop off). But if you divide your hash collision (or ECC brute force) efforts by 10 your chances of success are divided by 100 (quadratic drop off). [1]

Those two reasons are why I believe Daniel J. Bernstein when he says that Curve25519 is "high security" even though he has serious concerns with 128-bits AES. [2]

[1]: https://loup-vaillant.fr/tutorials/128-bits-of-security

[2]: https://cr.yp.to/snuffle/bruteforce-20050425.pdf (Understanding Brute Force)

> If you divide your key search effort by 10 your chances of success are divided by 10 (linear drop off).

Right, but if the starting point is 128 bits it doesn't matter how much you can parallelize the attack, you're not going to find a key regardless of how you divide the key space, even if the chances drop off only linearly.

Again, this is about "good enough". 128 bits of collision security are "better" than 128 bits of "preimage security" (I've never heard resistance against encryption key brute force called preimage security, but I think I get it) in the same way that 256 bits of collision security are better than 128 bits of collision security, or any bigger number is better than a smaller number. Cryptography needs to be secure, not as big as possible.

> Right, but if the starting point is 128 bits it doesn't matter how much you can parallelize the attack, you're not going to find a key regardless of how you divide the key space, even if the chances drop off only linearly.

If you combine a parallel attack with a scaled down search, a standard parallel attack can give a state-level attacker chances comparable to the lottery. Very low, just not quite impossible. Enough to protect your wallet, or even your life, perhaps a tad low to protect something like Wikileaks. (Perhaps. the US has shown they have other means.)

> I've never heard resistance against encryption key brute force called preimage security

I'm trying to coin the term, for lack of anything better. As far as I am aware there are two broad classes. One includes key searches and hash preimage attacks. The other includes hash collisions and discrete logarithm problem (without the help of index calculus).

If you have a better term for key search/preimage attack that is more readily understood by readers I would try to use that instead.

> any bigger number is better than a smaller number.

Sure, the choice is what threshold we might use. To do this it might help to get an upper bound. I've read an article stating that a perfect computer operating at space temperature would require the energy of something between a nova and a supernova to explore all the configurations of 256 bits. This is more than the entire output of our sun, so we know that there's no point in ever going higher.

On the lower bound section we have the number of hashes performed by the Bitcoin network. Their peak right now seems to be around 370 Exa-hashes per second, or about 2^93 hashes per year. It thus seems reasonable to never go below 93 bits of security (of any kind).

We can debate the exact numbers. My feeling is that anything above 192 bits is high enough to be utterly boring, and anything below 100 bits is too low for anything high stakes. Between the two however I'm forced to agree with you: any bigger number is better than a smaller number.

I think boring-ness is the crux of it, for me.

From what I've understood, 128-bits is fine-in-practice, unless you're an extremely high-value target who is also feeling unlucky. Even if I was a whistleblower under an authoritarian regime, I'd feel pretty safe using Age in its current form (at the very least, I'd have bigger things to worry about).

However, it's not quite boring enough - the fact that this conversation is happening at all attests to that fact. It would cost almost nothing to increase file key size to 256 bits, and so IMHO it should be considered for an "age v2" - but at the same time, not something people should be alarmed about in the current implementation. (with the caveat that I'm not exactly qualified to make that assertion)

> IMHO it should be considered for an "age v2"

Definitely, though personally I wouldn't go as far as recommend we make a version 2 just for this. The downsides of such a change are not worth the arguably extremely slim security benefit.

(And I agree with Age author it's not worth warning users about either. Not now in 2023.)

Right. I don't think this is a reason alone to make breaking changes, but if a new version is coming out for whatever reason(s), it should be bundled in with the other changes.

>...about 2^93 hashes per year.

128-93=35 bits. 2^35=34 billion years which is significantly longer than the age of the universe. That seems to support the contention that 128 bits is simply not brute forceable at the chances of a lottery or at all.

100-93=7 bits. 2^7=128 years. So 100 might be a bit high for a reasonable lower bound, but is at at least reasonable assuming some sort of breakthrough in computing.

Crap, good catch… I somehow managed to pretend 2^35 = 35. Oops.

That being said, one chance in 34 billion is only 3 orders of magnitude from typical lotteries, and in settings where multi-key attacks are applicable (not Age), we can definitely achieve lottery levels of success (with 1000 keys we get down to 1 in a 34 million chances for 1 year). 100 bits looks too low: in 1 year chances of success on a single key go up to 0.8%. That's pretty high.

We also need to keep in mind the actual algorithm used. When it's SHA-256 and Chacha20 we can say it's pretty comparable to Bitcoin, though there might be a small factor difference between hashing a full block and trying a key in a file. But if the entire path involves more hardware friendly primitives like AES, dedicated silicon could be quite a bit more efficient than the Bitcoin network currently is, and would drive down the costs (or drive up the chances of success) accordingly.

Now, do I actually believe a state level attacker would construct something as powerful as the entire Bitcoin network just so they have an extremely slim chance of cracking one key among many after years of burning energy over the search? No. 128-bit keys are safe, even in the face of multi-user attacks.

But the reasoning required to arrive to this conclusion is more complex than the one needed to assert that 256-bit keys are safe, because "there's still a chance". It's not plausible at all, but it remains humanly possible. With 256-bit keys we know it's flat out impossible. With 256-bit keys we don't even need to think, and that alone has some value.

256 bits is stronger than 128 bits and the extra cost does not matter for a tool designed to encrypt files.

It also saves a lot of time answering questions and justifying the choice.

So, IMHO, go for 256 bits and be done with it.

No, you can't really win here. If you reflexively bring your symmetric constructions to 256 bits, you end up in equally unproductive arguments about parity with your asymmetric constructions.

In my experience, much fewer people object to the use of Curve25519 than they do about 128-bit symmetric keys. I believe one reason is that bigger curves have a significantly higher cost, while limiting symmetric encryption strength to 128 saves zero CPU cycles with Chacha20.

For the few who do object, explaining that there is no such thing such as parity between symmetric and asymmetric primitive can help: https://loup-vaillant.fr/tutorials/128-bits-of-security

I'm responding to a comment suggesting that designers elect for 128 bit primitives to head off unproductive debates. Suggesting that you have a strong preprepared answer for those debates isn't really responsive to what I'm saying.

Sorry, I didn't mean to convey a strong disagreement here. I mostly agree with you on this.

Besides, we know the next step: use Curve448 to stave off criticism about using a small curve, and then people start talking quantum computers.

Yes, everyone will immediately pick on 128 bits for symmetric encryption but I suspect the vast majority of people won't pick on the fact that Curve25519 offers less bits of strength than 256 bits symmetric encryption, or they won't care. So you'll still avoid a lot of questions and have a better marketing box-ticking scorecard, will probably still be more secure.

2560 bits is stronger than 256 bits and the extra cost does not matter for a tool designed to encrypt files. See what I did here? Where do we stop?

This is absurd. I am only comparing the two main options (more or less) for symmetric encryption: 128 or 256.

Edited as not AES but you get the point taking into account that AES256 is the standard.

Age doesn't use AES.

We stop before the key is big enough to requires the energy of our sun to crack, even if you have an ideal computer. 256-bit keys require more energy than a nova.

128 bits however is humanly achievable (35 years worth of peak Bitcoin mining), and as such perhaps a tad low in really high stakes scenarios (say highly classified stuff).

We could chose something between 128 and 256, but they're nice powers of two, and we tend to like powers of two.

I got billions of years when I used the current bitcoin hashing rate for 128 bits. Are you assuming a birthday attack?

No, I just botched it and pretended 2^35 = 35. See these other comments for more details:

https://news.ycombinator.com/item?id=34955855

https://news.ycombinator.com/item?id=34963094

To enumerate 128 bits in 35 years you would need to make 3e29 attempts per second.

Current bitcoin miner can provide efficiency of 19 000 000 MH/J or 19e12 H/J. If we would assume bruteforcer can perform with the same efficiency, we would need 1.6e16 J/s = 16 000 TW.

Current humanity energy output is something like 17 TW.

Yeah, botched my numbers, sorry. I saw that the hash rate of the current Bitcoin network went up to 2^93 hashes per year, and then I managed to pretend 2^128/2^93 = 35, instead of 2^35.

With your numbers if humanity dedicated all its energy to brute forcing a 128/bit key for a year it would have a ~0.1% chance of finding it. I guess that's a pretty good argument that no one is going to even try it in the foreseeable future.

See this cousin comment highlighting my error. that out: https://news.ycombinator.com/item?id=34955855

> age uses a 128-bit per-file nonce fed into HKDF, making the total search space 128 + 128 = 256 bits, safe in every multi-user scenario, too.

If I read the description right (big if), age is using HKDF to derive a 128-bit key. In this case, it does not help at all that there’s a 128-bit nonce: the attacker will do a multi-user attack against the HKDF output, and the attacker wins (with asterisks, etc).

Nope, HKDF outputs are always 256 bits. They are used either as a HMAC-SHA-256 key or as a ChaCha20Poly1305 key, so everything downstream of HKDF is 256 bits.

In "Conventions used in this document" you'll find the sentence "The length of the output keying material is always 32 bytes." making this explicit.

Gotcha. I was looking at the wrong little bit of code and was distracted by all the mentions of AES128.

Actually, I changed my mind. Age uses the file key for at least three things:

1. HKDF with a random 128-bit nonce to derive the actual payload key.

2. HKDF with no nonce to derive the HMAC key for header authentication.

3. As input to every “recipient”.

I’m willing to believe that #1 is not subject to a multi-target attack and that this might even be provable.

I’m less willing to believe, without evidence, that #2 is safe. There isn’t an obvious (to me, on brief consideration) to, for example, tell whether two age files have the same HKDF output for the header key, but that’s only because the headers themselves are likely to differ for age files because the recipient stanzas are (presumably!) unlikely-to-collide functions of the file key.

I don’t like #3 at all. One could easily break multi-target security by having a DH recipient type that is just the identity to the power of file key. And I bet one could design a recipient type that looks reasonable on its own (and even has a security proof!) but breaks the system completely if two instances of the same recipient type are used in the same file.

If I were designing a v2, I would make two changes:

a) Either the file key is never used without a random nonce or the file key is >=256 bits, or both.

b) The recipient stanzas are not functions of the file key. Instead there is a per-stanza wrapping key that wraps the file key separately for each recipient.

The goal would be to enable a security proof that only needs to assume that each recipient stanza is independently secure.