Brute force code cracking question.

[Guv]

Just started reading a novel (Digital Fortress by Dan Brown) which is about NSA, the code cracking agency.

A character in the novel claims that brute force methods can always crack a code based on an encryption key. This claim does not seem close to being correct to me.

It seems to me that a key 100 bits long requires 2100 tries to be certain of finding the key, although you could be lucky and find it in ten tries. On average, it would take 250 tries.

A key several thousand bits long would take many life times of the universe if you could make millions of tries per nanosecond.

Are there any code cracking gurus here with an opinion?

[WorkHorse]

1) Dan Brown is a severely cracked conspiracy theorist novelist with limited knowledge about sciences and arts that he pawns off in novels as "truth".

2) Keys for standard encryption (like for Internet credit card payments) are huge. Way more than 100 bits. Brute force even with multiple super computers would be net to impossible within any person's lifetime.

3) Current accepted standard encryption codes are impossibly complex. I can do some calculus, etc. but I looked at the white paper from the guys that won the Advanced Encryption Standard (AES) a few years back and I couldn't even begin to follow it. I can’t find the paper anymore, but here’s some stuff:

AES is a 128-bit block cipher algorithm based on Rijndael, a mathematic formula developed by Belgian cryptographers Joan Daemen, of Proton World International, and Vincent Rijmen, of Katholieke Universiteit Leuven. Rijndael (pronounced Rhine-doll), named after its creators, was selected by the U.S. government in October 2000 as a new encryption technique for protecting computerized information. The National Institute of Standards and Technology (NIST), an agency of the Commerce Department's Technology Administration, selected the formula after a four-year competition.

4) For passwords to my applications I use a one way encryption. The “key” to the encryption is the password itself. When the user enters the password, it is encrypted and saved to a file. When a user logs on, the password they enter is encrypted and compared to the encrypted password in the file. Passwords are encrypted in such a way that a random guess would be essentially impossible. I have access to the encrypted password and to the encryption code, but it would be next to impossible for me to find out what someone’s password is.

5) Cheap hacking usually involves trying to reverse the encryption to get a sensible answer--that is, something with a recognizable word, name, etc. This is only used for very simple encryptions and having the encryption code helps a lot. For good passwords that are essentially gobbledygook this is worthless. A lot of hacking involves finding a back door to some information.

6) True brute force of a password relies on making many attempts to see if a password succeeds. Most software has guards against this--delays acceptance of passwords, kicks out a user after so many tries, etc. Send Mr. Brown a document encrypted with blowfish and see how long it takes.

7) The only way to brute force something encrypted is to get the whole key. I can make that key, say, 1 to 200,000 characters. Wide characters. Or even ASCII. The combinations are nearly endless (you can calculate them better than I can.) The limit on the length of the key is only dependent on the amount of memory available in your computer (or for VB, 2 billion characters per string).

8) Did I mention that Dan Brown is a psycho conspiracy nut that writes “fiction” based on selective “scientific” facts garnered from people that support his conspiracy theories and who takes every advantage to draw together non-related “evidence” to support his hypotheses which he portrays in “novels” as scientific truth and actual fact?

:eek: :)

[wossname]

Originally posted by Guv
A character in the novel claims that brute force methods can always crack a code based on an encryption key. This claim does not seem close to being correct to me.

It seems to me that a key 100 bits long requires 2100 tries to be certain of finding the key, although you could be lucky and find it in ten tries. On average, it would take 250 tries.

A key several thousand bits long would take many life times of the universe if you could make millions of tries per nanosecond.


I think the author omitted "Given enough time..." from his book. Never the less this doesn't make it untrue that brute force will always yield a result. Several decades ago someone said (paraphrasing) "I cannot envisage a time when we will need to perform more than 40,000 calculations per hour". When quantum computers become viable in about 20 years we'll be cracking 8192 bit RSA as something to pass a boring lunch hour. So if the only limit to brute force effectiveness is time itself, then all we have to do to prove a theory is wait!

[jemidiah]

I think Guv's original argument ("A key several thousand bits long would take many life times of the universe if you could make millions of tries per nanosecond.") is still very true even if/when quantum computers (and up) come along. You said that 8192 bit encryption would take a lunch break to break? Well, what about 8200 bit encryption? That'd take 28 or 256 times longer, and that's only when increasing it by 8 bits. What if they used a megabyte? If processors are that fast, I'm sure storage would also increase at a rate that would make simply upping the encryption key length a negligable effect.

[Guv]

In my original post I said that on average it would take 250 tries to crack a 100 bit key. That is way off: You would have to try 299, or half of the 2100 possible keys. At one million tries per nanosecond, it would take over 20 million years to find the key. I shudder to think about a key 1000 bits long.

WorkHorse: Thanx for the info about Dan Brown. His concepts did not seem sound. You reinforced my opinion of code cracking via brute force. I do not know what NSA can do in this age of computers. An obsolete Laptop (say 800Mhz) can easily encrypt/decrypt using a 1000 bit key. Prior to the modern PC, the time required to encrypt/decrypt was critical. It had to be done using manual methods. A computer with a lot of parallel processors could break such codes, and some methods were crackable via sophisticated analysis rather than brute force methods.

Decrypting a message is a bit different from trying to get an ATM PIN number or a password for logging on to a computer. When attempting to decode an intercepted message, there is no software that will ignore you after 3-10 bad guesses. The brute force methods try every possible key until a sensible message is obtained. The algorithm to decide if the decrypted text is sensible might take more time that the decryption algorithm.

I do not think that sophisticated algorithms are necessary if the key is long enough. The weird complex algorithms are required by the Public Key methods. The mathematics is a bit difficult to understand, but the concept of Trap Door functions is not complicated. They are called Trap Door functions due to an analogy: It is easy to fall through a trap door, but very difficult to climb back out of dungeon you fell into. There are various mathematical processes that are easy to work in one direction, but difficult to reverse. A trivial example is polynomial roots and coefficients. Given the roots, there are easy algorithms which will determine the coefficients. For fifth order and higher polynomials, It is has been proven that there are no analytical methods for determining the roots if you know the coefficients.

The first Public Key method (from about 1975) used the product of two very large prime numbers as an encryption key. To decrypt a message, you had to know the prime factors. Knowing the prime factors, it is easy to find the product, but determining the factors from the product is tuff if the smaller prime has 300 or more digits. Note that classical methods usually (always?) use the same key for both encryption and decryption, while Public Key methods require that the keys be different.

The advantage of such methods is due to what spooks call the down stream loading problem for the standard key methods. Prior to Public Key methods, a courier had to deliver keys, which might not be easy if the spook/soldier who wants to send you a message is under deep cover behind the Iron Curtain or is on a battlefield. With Public Key methods, you can announce the key over public TV or in a radio broadcast. Another interesting advantage of Public Key methods is the ability to verify the sender of a message via processing of an encrypted signature.

WossName: You, like may others, believe that future computers will be fast enough to solve any problem in a reasonable amount of time. This is flat out not a valid belief.

BTW: I will believe in the effectiveness of quantum computers when they build one that can do something more difficult than factoring a 2-digit number, which is not much to show for 20 or so years of effort. I wonder if this technology is being driven by an academic Publish or Perish motivation.

50 years ago, cryogenic computers were prophesied to be the great technology of the future. Much money and resources were invested in this technology. The prototypes could do some significant computations, but practical problems and other developments doomed this technology. I wonder if quantum computers will turn out to be another great concept which did not get out of the laboratory.

I also wonder if quantum effects will put a limit on miniaturization of CPU circuitry and nanotechnology.

[DiGiTaIErRoR]

Network processing.

;)

Or better yet, WAN processing.

[wossname]

Yeah, like Seti@home or Genome@home.

[abcdefg]

The author is wrong with enough bits it cant be cracked.