@MaartenBodewes Yeah, that's a weird one!

So, I think it comes down to this: it depends on how the keys are being used and, therefore, combined (duh!)

@ConorMancone I just realized I was missing something. Can each layer of tor encryption be bruteforced individually?

For simplicity let's consider the case of double encryption using 2 keys with 128 bits. Imagine if the encryption layers are independent, meaning that you can decrypt each one individually

@nobody Exactly!

They can?

Well then that means it would take (2^128)*3 to bruteforce it

If you can brute force the first layer and then brute force the second layer, then your overall security is the equivalent of 2 layers with 128 bits, which means that 2*(2^128) = 2^129

yes

If you have to brute force both layers at the same time, then your complexity is 2^128 * 2^128 = 2^256

So... we were just on different pages this entire time

haha lol

As for which scenario applies here... I don't know enough about TOR to say for sure myself.

Me neither. So I guess we have to wait for forest to return

@MaartenBodewes Did you do that on purpose?

I was really just thinking about the general use case of using 2 keys: not the specific TOR example

I was just thinking of double/triple encryption, not tor in particular either :)

In practice, I expect that you can brute force each layer individually, because each layer also needs its own routing information and meta data. Basically, the middle node will receive a blob of encrypted data which it decodes, and in doing so has some routing information and another blob of encrypted data, which it cannot decode, but which it passes along to the next node

Therefore, you should be able to know when you have brute forced the key for the current layer, and in doing so, you should have the next "packet" of data which you can then start brute forcing

Yeah, Makes sense

So I suspect that for Tor it is a simple "addition" of keys, so 3*2^128 is the correct way of calculating it

But yeah, I was on the wrong page - I never considered the doubly-encrypted situation where the only way you can tell if you have a key is by decrypting the whole thing, and therefore 2 keys with 128 bits do give you the equivalent of a 256 bit key (well, in theory: in practice it is probably weaker)

@ConorMancone Strength depends indeed how it is setup and which algorithms are used. 2 key triple DES (128 bits, 112 effective) doesn't achieve a 112 bit security (while 3 key triple DES does achieve 112 bits more or less, for 168 bit effective key bits).

So yeah, it may be weaker, but it can be achieved (you could use the same 112 bits for AES and get 112 bit security).

@ConorMancone Hold on! How you can test that ciphertext is valid? Double encryption without meet-in-the-middle attacks has cost (2^128)^2 = 2^256.

Now, that is better; each layer also needs its own routing information and meta data

@kelalaka It depends on how the particular protocol works, and that is a detail of Tor that I'm unfamiliar with. However, the routing information and metadata needs to be encrypted as well, because each layer needs to only see the routing information and metadata for itself, and not the other layers.

Therefore, my expectation is that you'll know that you've found the right key because you get valid routing information and metadata.

okay, I need to know what this is called, or if it's a thing. Is there a cryptographic construct where there's a majority in agreement allows a thing. I realize this is sorta like a blockchain database, but what I'm looking for is more like passwords. Let's say that there are five people who each have a password, but only 3 are available. A majority is required to allow access. It's like shamir's secret sharing but with a threshold.

I feel like this is a thing, and what would be it called?

threshold secret sharing

Shamir's secret sharing supports thresholds

@bdegnan ^ what Aman said, the point of shamir secret sharing is to literally provide k-out-of-n threshold secret sharing

I had no idea that it support thresholds.

This is what I get for skimming things.

@bdegnan there are contexts where it is only used as a n-out-of-n secret sharing scheme, in what contexts did you encounter it?

I'm reading a protocol for IoT that assumes n of n are required for the system to operate. I thought it would be more prudent for k of n because hardware fails; however, I didn't know that it was already part of the shamir secret sharing. I'll read up. Thanks!

@ConorMancone if that is true, then you are right.