5
$\begingroup$

As stated for the question above here's an analogy:

You are a robber looking for a house to rob with two different scenarios that might occur.

1. You have a key that you know belongs to a house and you can use it to let you inside. However, you have no clue for WHICH house it belongs to. At any neighborhood and at any house, the key can be utilized for direct access for one undisclosed location you need direct access to. But because the location of the house is kept secret, you don't know where to look.

2. You are standing right in front of the primary target house. You do not have the key with you but you know there are ways of getting in the home. You can either break the windows, use a crowbar, or slam down the door. It may take a while but you have the necessary tools for the job (tools = BRUTEFORCE)

(For my thought process on this analogy, I'm thinking mostly on the idea of a message that's encrypted and released publicly. However, this is also for the encrypted algorithm as well.)

With these scenarios given, I wanna know why this doesn't apply for Symmetric Cryptography? (I am new to Cryptology, so my apologies if my thinking process for this is not entirely correct. Any help is appreciated.

EDIT: Did some further reading. Is the main reason due to key lengths being the reason why its hard to decrypt a message/algorithm? I just read for a key length being around 128 bits of length results in 340,282,366,920,938,463,463,374,607,431,768,211,456 possible combinations. This is what makes the key itself valuable to hold as it will takes years to even consider brute forcing it. So having the message/algorithm out in public would provide no possible danger if the key itself is difficult to acquire through brute force. Is this the reason why?

$\endgroup$
13
  • 2
    $\begingroup$ See crypto.stackexchange.com/questions/108126/… $\endgroup$ Oct 16, 2023 at 2:27
  • 3
    $\begingroup$ It will not take "years" to brute force it! $2^{128}$ is a lot. That number is so inimaginabley large that we can't brute force it. That is somewhere along the line of the number of atoms on earth. If every single atom was a computer and you could somehow successfully parallelise that and find the right atom that found the key, only then could you brute force that. The orders of magnitude here are important, $2^{128}$ is too large to ever be considered doable. $\endgroup$
    – Kolja
    Oct 16, 2023 at 7:00
  • 3
    $\begingroup$ @kojla There are more than $2^{166}$ atoms forming earth. $2^{128}$ is very little compared to that. I agree with your conclusions about 128-bit keys, but not with your reasoning. $\endgroup$
    – fgrieu
    Oct 16, 2023 at 8:01
  • 3
    $\begingroup$ The analogue to breaking in through a window is not brute-forcing the encryption algorithm, but breaking in through some other software vulnerability. No need to figure out how the lock / encryption algorithm works. And even for the down to earth burglar, not knowing where a particular key fits isn't a hindrance, they can just go find some target that appears feasible in itself (wealthy residents away on holiday), and then break the window. $\endgroup$
    – ilkkachu
    Oct 16, 2023 at 10:04
  • 2
    $\begingroup$ I think 2^256 operations is about the limit that is considered "physically impossible". The total energy in the whole universe wouldn't be enough to make 2^256 state changes, with the Planck constant determining the minimum amount of energy needed to make any change. $\endgroup$
    – gnasher729
    Oct 16, 2023 at 19:29

11 Answers 11

14
$\begingroup$

Some facts for you to consider:

  1. Brutal-force a cryptographic key is much harder than brutal-force breaking into a house - the former can take as long as for a star to explode, while the latter take at most some material for an explosive device.

  2. A cryptographic key is much easier to safe guard, and devising cryptographic algorithms that're secure under Kerckhoff's 2nd Principle is equally easy (by easy I mean easy for experts, not for novices).

$\endgroup$
2
  • 5
    $\begingroup$ Just for an amusing data point: at one point I did the calculations regarding how much energy it would take just to count from 1 to 2^192. I assumed the computer counting was at the background temperature of the universe. Turns out that counting... just the counting... would consume 3/4 of the energy in the galaxy! 2^256 is simply out of reach $\endgroup$
    – Cort Ammon
    Oct 16, 2023 at 22:15
  • 3
    $\begingroup$ One trillion galaxies gives you 40 more bits. That's 2^232. $\endgroup$
    – gnasher729
    Oct 17, 2023 at 9:12
13
$\begingroup$

At least two reasons.

1: security. You want your algorithm to be a good one. One of the best ways we know of ensuring cryptographic algorithms are good is to have as many experts as possible assess them. That is not generally compatible with keeping the algorithm secret.

2: security. Assume you have set of devices which are talking to each other using your algorithm. For each device $D_i$ there is a common algorithm, $A$ say, and a number of keys $k_{ij}$ where $j$ ranges over all the other devices it wishes to talk to. All the $\{k_{ij}\}$ should obviously be distinct. Assume $D_i$ falls into the hands of bad people. They now know $A$ and $k_{ij}$. If knowing $A$ tells them anything useful then you are in big trouble. Therefore you must design $A$ so revealing it does not tell them anything useful.

As a caveat to (2): you could imagine not using a single algorithm but rather some unique algorithm $A_i$ for each device, so when $D_i$ is compromised the baddies only know $A_i$. Well, that means that the part of the algorithm that differs per device is part of the key.

$\endgroup$
1
6
$\begingroup$

I think it most helpful to think of most cryptographic "algorithms" as being not algorithms directly, but rather algorithm factories, which use cryptographic keys as blueprints to produce algorithms. Although all of the algorithms produced via a cryptosystem like AES will always use the same combination of building blocks, the ways in which their effects interact with each other are sufficiently different that the resulting algorithms have no discernible behavioral similarities.

If one wants to prevent someone from stealing a design, guarding the blueprint secret is far more important than guarding the lathes, milling machines, etc. that one might use to fabricate it. Although someone who doesn't have one's collection of tooling bits might not be able to reproduce a shape that would be formed by running bit #57 around a path without knowing what bit #57 was, and someone who did have one's collection of bits might have some clues about the kinds of shapes that could be milled with them, having a standardized set of machinery that can be fed many people's blueprints is much more practical than requiring that every "customer" supply not just a set of blueprints but also all of the tooling needed to use them.

$\endgroup$
5
$\begingroup$

Because anyone can create a good secure key.

Very few people can create create cryptographically secure encryption methods. Most likely, your 'secure encryption' is breakable, possibly by me, because it hasn't hidden the patterns of your message.

I don't need to know how you encrypted something if thru statistical analysis I can determine what meta-character corresponds to what text.

You cannot roll your own Crypto method and expect it to be secure. Most likely the super secure method you just thought of is horrible flawed, and easy to break.

And if you are using a randomly chosen published encryption method... there are not that many well tested cryptographic algorithms in existence, I could brute force your message by hand. However there are 2^256 different cryptographically secure keys for AES-256 1e77.

TLDR: Your analogy is bad. The locked house isn't the algorithm, it is the message. The algorithm is the door, the password is the key.

If you have a bad door, I don't need a key, I don't even need to know how your door works, I can just shimmy the lock using statistics guided by information theory.

$\endgroup$
4
$\begingroup$

Brute force means trying possibilities until one works. If you use a single algorithm with a 128-bit key, there are $2^{128}$ possibilities for the attacker to test. If you choose between 16 different encryption methods, each with a 128-bit key, there are $16\cdot 2^{128} = 2^{132}$ possibilities, which is scarcely any better. And 16 algorithms is a lot—there's a significant chance that in choosing a less common algorithm you'll inadvertently end up with a weakness that will make your scheme much less secure instead of slightly more.

It's better to choose one of the most widely used and studied algorithms, and if you're worried that $2^{128}$ isn't enough, use a 192- or 256-bit key.

$\endgroup$
1
  • $\begingroup$ If you are not worried that 2^128 is enough, use a 192- or 256-bit key :-) $\endgroup$
    – gnasher729
    Oct 16, 2023 at 19:30
4
$\begingroup$

The existing answers are good. Here's a way of looking at it that might fit your intuition better:

I just read for a key length being around 128 bits of length results in 340,282,366,920,938,463,463,374,607,431,768,211,456

And there are about 6 good algorithms to choose from. Which is harder for the attacker - trying all six algorithms, or trying all 2^128 keys?

You might think "surely it's not hard to come up with a new algorithm on my own". Remember that "good" means things like "if I say the same thing twice,the adversary can't tell it repeats". Ie, they can't distinguish this pattern:

Wait
Wait
Wait
Wait
Attack now

There goes 99% of the algorithms you might think of.

Also, good means the adversary can't take your two messages "no, don't" and "attack at dawn" and combine them, to create a new message "no, don't attack at dawn".

You can probably start to see why there are very few algorithms known to be good.

You might think "well I could use different variations of one of those six good algorithms". Yes you could, and all the known GOOD variations could be numbered - variation #1, variation #2, variation #3, etc. You could randomly choose one of several trillion variations. These variation numbers are called "keys". :)

For your house example, a good analogy would be:

A. I don't have the key / combination, but I do know which type of (highly secure) lock they have - a Medeco (AES).

B. I don't know which brand of lock it is, but I have the key.

It's not hard to walk to on the door and see which type of lock, or to try all six types of lock generally used on houses. It's a heck of a lot harder to try all possible keys.

You DO know which person or web site you're attacking, so "I don't know which house" just isn't true. You know which house, and you pretty well know the lock is going to be either Kwikset or Shlage.

$\endgroup$
1
  • $\begingroup$ I once tried to determine how to permute algorithms so the number isn't 6. I never did find a way to find 2^128 algorithms. An algorithm of my devising used for one message would be beyond your reach; but I can't use it repeatedly with known keys without you figuring it out. $\endgroup$
    – Joshua
    Oct 17, 2023 at 21:53
3
$\begingroup$
  1. You are standing right in front of the primary target house. You do not have the key with you but you know there are ways of getting in the home. You can either break the windows, use a crowbar, or slam down the door. It may take a while but you have the necessary tools for the job (tools = BRUTEFORCE)

You have a misconception about cryptography. The very purpose of cryptographic algorithms is to NOT have any known ways of getting in. (Unsafe algorithms have known weaknesses, so we do not use them any more; safe algorithms have no known weaknesses, so we use them).

So your analogy should have been:

  1. You are standing right in front of the primary target house. You do not have the key with you. There are no known ways of getting in the home. Typical approaches like break the windows, use a crowbar, or slam down the door do not work on this house.

Well, is one approach that might work, but it would take millions of years to accomplish. You'd be long dead before any chance of breaking in.

$\endgroup$
6
  • 2
    $\begingroup$ Most cryptographic applications would be amenable to brute-forcing by an adversary given unlimited time and resources. The goal is not to make brute-forcing literally impossible, but to reduce the probability of a brute-force attack being successful within any relevant time frame below that of other bad things whose risk would be considered tolerable. $\endgroup$
    – supercat
    Oct 16, 2023 at 15:36
  • 2
    $\begingroup$ @supercat "given unlimited time and resources" is the equivalant of being impossible. $\endgroup$
    – atk
    Oct 16, 2023 at 16:32
  • 1
    $\begingroup$ For almost any particular cryptosystem, one could compute an upper bound on the worst case time and resource requirements to guarantee success, and one could expect to achieve success with computable (though hopefully very small) level of probability given practical levels of resources. The goal is not to make the probability of successful attack as small as possible, but rather to avoid making the cryptosystem much more expensive than necessary to reduce the risk to an acceptable level. $\endgroup$
    – supercat
    Oct 16, 2023 at 16:43
  • 2
    $\begingroup$ While that comment is technically correct, do you really think that the question is sufficiently nuanced and detailed to have a deep conversation about when 5min is sufficient vs a billion years? Or do you think as I do, that the question is from someone who doesn't really understand things and deserves a very simplified answer? $\endgroup$
    – atk
    Oct 16, 2023 at 16:49
  • 1
    $\begingroup$ @gnasher729 Please reread the original question. The OP was providing a physical analogy to try and understand why algorithms are public. My answer corrects the analogy. It's not about real world cryptographic door keys - it's an analogy where the rest of the house - including the metal that would be cut with bolt cutters - is the algorithm, is not actually physical, and therefore does not have the physical weaknesses you propose. $\endgroup$
    – atk
    Oct 16, 2023 at 19:56
1
$\begingroup$

I think if you consider how symmetric key cryptography is used in the real world, it becomes clear that the idea of keeping algorithms secret is not practical. A useful and ubiquitous example is TLS. TLS is typically thought of as an asymmetric system but one of the things that asymmetric interaction is used for is to exchange a key for symmetric encryption. After that is established, the symmetric key is used between client and server. Importantly, the client and server must negotiate what algorithm is used (among other things.)

Now, if there were secret algorithms, how would you handle this? Would the server transmit binaries to the clients? Source code which the client would then compile? How many algorithms would the server need to have? For your scheme to work properly I think a different algorithm for every client would be needed because you cannot trust the clients to keep them secret. As much as it might drive demand for cryptographers, I don't think that's going to happen. After a few user sessions, all your algorithms would be known.

In contrast, generating new unique keys for well-tested, widely known algorithms is quite straightforward and inexpensive.

$\endgroup$
1
$\begingroup$

Imagine you want to make software and install it on a billion different computers and phones.

For all those device to communicate, say on the Internet, they all need the same code.

If the security is only in the code, then you have a billion copies floating around and if someone reverse engineers one, they get the secrets from all. And since the code must be run by a processor, all code can be reverse engineered with enough time and effort.

This kind of Break Once, Run Anywhere attack is a nightmare scenario for security.

Same thing happens if every device uses the same global key, which has lead to different security vulnerabilities in the past. For example the leaked PS3 root key.

https://www.gameinformer.com/b/news/archive/2011/01/27/the-saga-of-the-hacked-ps3-root-key-continues.aspx

(Modern secure devices are all manufactured with custom keys inside them so they have a unique identity than can be verified. This also allows asymmetric schemes to be used to avoid this single global shared key problem.)

HTH

$\endgroup$
1
  • $\begingroup$ Your example with "every device uses the same global key" part isn't a convincing argument. That key is a digital signature verification key, which can be safely made public. The real reason its private key got recovered is that the implementation of signing code had a "operative" error - IETF RFC-6979 recommended a fix over this. $\endgroup$
    – DannyNiu
    Nov 5, 2023 at 1:13
0
$\begingroup$

Symmetric encryption uses the same key for encryption and decryption.

So if you obtain the key, you can read data from both sender and receiver.

Asymmetric encryption uses key pairs, one private and one public key.

When you want to sent data you encrypt this with the public key of the receiver, the receiver can then decrypt this data with its private key.

A private key can stay in one place, so there is less risk in sending a public key as nobody but the receiver can decrypt the message (in theory). Compared to the first scenario, where both sender and receiver share the same key; this shared key could be much easier to intercept.

$\endgroup$
-3
$\begingroup$

This is kind of an answer and a comment joined together. I think we're underestimating the power of a combination of classical computing as well as massive GPU clusters and new possible algorithms that exist which undermine the time necessary to break even strong encryption like AES 256. There is shores algorithm which is meant to be used in a Quantum environment but I've also seen that we have come up with algorithms which can by orders of magnitude increase the number crunching of a CPU which would then change that brute Force number mentioned above as well as the enormous upgrade and performance with the addition of massive GPU parallel processing clusters and DPUs, so data processing units, for distributed computing along with the fusing of these large GPU clusters and CPU cores with much higher speeds with cross communication buses.

Has anyone taken a serious look at a potential update to The brute force number based on recent papers published on CPU number crunching improvements and I'll see if I can find the reference to the paper but I did mention them on a formum on Linkedin and another one which dealt with the combination of quantum simulations, improvements in computing speed based on new algorithms that have been discovered by deep machine learning and neural networks, and those same neural networks as implemented on extraordinarily faster GPU clusters with new high-speed data buses and DPU which connect them all.

I think they're now exists computers which would be considered somewhat hybrid so no longer classical per se but not Quantum either. So my my answer is both an additional question and a comment to the question asked above as I'm putting this out to all of the people who have commented on the initial question as to the importance of maintaining your private key and it's length as well as exactly how long that brute force number is at this exact current time and or the amount of time that it would now take given the vastly increase processing power. I'm not sure that that's accurate any more and I think processing power should be adjusted to a level somewhere in between a highly capable desktop unit and some of the new supercomputers that have arisen due to the desire for people to implement large language models and other types of neural networks.

I've seen much lower potential numbers mentioned in regard to a AES 128 and even possibly AES 256 down to 2 to the mid to upper 80s. Has the brute Force number been updated to reflect the massive expansion of computing power and not only at the CPU level in terms of number of cores. But also improvements in the number crunching at the CPU level as well as CPU clusters which have been joined together with high-speed buses. Then add in being able to offload large processes to a parallel cluster or GPU cluster which also has absolutely mushroomed in terms of available cores as well as distributed computing across many many other, some almost full single or.doubke U rack sized GPUs that are used at the data centers and supercomputer level?

And then to answer the question directly, I mean a properly implemented AES algorithm is going to be implemented more or less the same way every time if it's properly implemented. That's an important issue and not all programs are properly implementing the algorithm as defined by the standards.

$\endgroup$
2
  • 1
    $\begingroup$ "I think we're underestimating the power of a combination of classical computing as well as massive GPU clusters and new possible algorithms that exist" – One of the most highly optimized brute forcing devices in the world is a Bitcoin miner, and the fastest one of those in the world makes about 250 trillion attempts per second. If we assume that we could build a similar device that makes 250 trillion attempts at cracking an AES-128 key per second, then even if everyone in the world had 1,000 of these, it would still take thousands of years to crack just one key. $\endgroup$ Oct 17, 2023 at 14:50
  • 1
    $\begingroup$ "I've seen much lower potential numbers mentioned in regard to a AES 128 and even possibly AES 256 down to 2 to the mid to upper 80s": no, you haven't. The 2^128/2^256 just tells you the number of guesses you would need to exhaustively try every single possible key in a brute force attack. This number cannot get smaller, it is always the number of possible keys. It doesn't matter what hardware you throw at it, the number of guesses needed is always the same (outside of quantum computing, which is NOT what you seem to think it is). More hardware just lets you make more guesses in less time. $\endgroup$
    – Ben
    Oct 18, 2023 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.