It's my understanding that the more bits an encryption key has, the longer it takes to break the encryption. What is the down side of having a larger encryption key or why don't we see keys of size 2^100 bits? Someone I worked with said it's the law made by the government encase they ever need to crack it, but this doesn't sound likely.
Speed. While keys can be large, if they are too large you're algorithm will be so slow that it's not workable. Normally multiple key sizes are defined by NIST and their estimate until it will be feasable to crack these.
For instance AES-128 would take:
128-bit Key = (3.4 x 1038) / [(10.51 x 1012) x 31536000] = (0.323 x 1026)/31536000 = 1.02 x 1018 = 1 billion billion years
If you assume:
- Every person on the planet owns 10 computers.
- There are 7 billion people on the planet.
- Each of these computers can test 1 billion key combinations per second (and that's quite high).
- On average, you can crack the key after testing 50% of the possibilities.
- Then the earth's population can crack one encryption key in 77,000,000,000,000,000,000,000,000 years!
So if you take a 2^100 you will not increase your security that much. Infinity is still infinity.
Your friend is not entirely wrong when it comes to requests of government agencies to weaken cryptography. Note that the U.S. still regards cryptography as a weapon. Since World War II, many governments, including the U.S. and its NATO allies, have regulated the export of cryptography for national security considerations, and, as late as 1992, cryptography was on the U.S. Munitions List as an Auxiliary Military Technology.
Recently it was discovered that RSA Laboratories was paid 10 million USD to cripple the random generation of one of their products:
Documents leaked by former NSA contractor Edward Snowden show that the NSA created and promulgated a flawed formula for generating random numbers to create a "back door" in encryption products, the New York Times reported in September. Reuters later reported that RSA became the most important distributor of that formula by rolling it into a software tool called Bsafe that is used to enhance security in personal computers and many other products.
On the other hand they also increased security of DES back in the 70's by helping on the design of the S-boxes of DES. In the early 90's it was discovered that this significantly increased the difficulty of brute forcing DES keys. As Bruce Schneier said:
So, how good is the NSA at cryptography? They're certainly better than the academic world. They have more mathematicians working on the problems, they've been working on them longer, and they have access to everything published in the academic world, while they don't have to make their own results public. But are they a year ahead of the state of the art? Five years? A decade? No one knows. It took the academic community two decades to figure out that the NSA "tweaks" actually improved the security of DES. This means that back in the '70s, the National Security Agency was two decades ahead of the state of the art.
- Mohit Arora, eetimes, How secure is AES against brute force attacks?
- Joseph Menn, Reuters, Secret contract tied NSA and security industry pioneer
- Bruce Schneier, CNET, Saluting the data encryption legacy
The main reason for this would be speed as a trade-off against security. Larger encryption keys usually take longer to process and (assuming that the underlying algorithm and implementation are sound) beyond a certain key length increasing it provides no practical additional security.
For example with 128-bit AES (which is a common standard used in SSL amongst other places) it would take an impractically long time to crack a 128-bit key, so making it any longer provides no practical benefit and does slow things down.
AFAIK the longest symmetric key that has been brute-forced in public was a RC5-64 bit key found by Distributed.net
Keys of size 2^100 bits? Are not commonly used as there are not appropriate algorithms, handling such a large keys is inconvenient and slow. And, 256-bit keys are strong enough.
The answers to this question How much would it cost in U.S. dollars to brute force a 256 bit key in a year? on crypto.SE clearly indicate that 256-bit symmetric keys are strong enough. (Note: There exists some cases, where stronger than 256-bit crypto could be good idea, for instance, if intent is to keep a secret for more than, say, one hundred years.)
Some common asymmetric cryptography algorithms and MACs use larger keys, but that's it. There is little use for very large symmetric encryption key. Very large keys have following disadvantages:
- It is harder to keep large keys secure (there is issue to store the key securely).
- New algorithms would be needed. If keys are very long, it the algorithms to process data with the keys would be very complex.
- Complex is also slow.
- Current generation of cryptographic algorithms has been designed so that their features, including block size, key size, internal structure, key schedule, number of round work well together. To change any of these parameters (like key size, or block size) will mean that each of the other parameters need to be tuned for the new size. Likely design will change in few places.
In AES algorithm supporting 128-bit keys, 192-bit keys, 256-bit keys, change in key size produces following changes: somewhat more processing in key schedule for larger key, and, 10 rounds for 128-bit key, 14 rounds for 256 bit key. Finding good structure for the function and amounts of rounds providing suitable security margin is very hard.
Keys for algorithms like AES can be derived from key materials larger than, say, 256-bits. In some cases it is necessary, such as when the root of the security is a password.
Tidbit: Notable exception is famount unbreakable encryption "OTP". It can use arbitrary large key. In fact it needs to: the key must be the same length than encrypted message. However, OTP is notoriously hard to use securely in most modern use cases for encryption.