3

# how come we cant brute force crack encryptions?

Wed 14 Jan, 2009 10:37 am
isnt it possible to just go

1
11
111
1111

a
aa
aaa

etc?

why woudl it take so long to crack? woudlnt a computer go thru every numeral and letter by the thouands per second?

• Topic Stats
• Top Replies
Type: Question • Score: 3 • Views: 2,558 • Replies: 29
No top replies

Cycloptichorn

1
Wed 14 Jan, 2009 10:44 am
@OGIONIK,
OGIONIK wrote:

isnt it possible to just go

1
11
111
1111

a
aa
aaa

etc?

why woudl it take so long to crack? woudlnt a computer go thru every numeral and letter by the thouands per second?

Sure, with some limiting factors.

Many systems protect against this by only allowing a certain number of attempts in a certain time frame; if you are limited to one attempt/4 seconds, it would take an age to break even a simple key.

Also, the possible number of combination is larger than you think in any modern system - a 4-digit passcode alone has over 5000 possible combinations, and that's just with numbers. With letters involved, it's much, much larger, and most passcodes are longer, so you can see how this might take forever using brute force.

You might want to look into quantum computing as a way of brute forcing attacks - it seems that many codes which were before considered 'unbreakable,' including one-time pads, will have to be revised when this new technology matures.

Cycloptichorn

0 Replies

ebrown p

1
Wed 14 Jan, 2009 11:18 am
@OGIONIK,
Bigger keys take more time to crack using brute force methods-- so as computers get faster, the keys get bigger.

Currently 256-bit keys are considered "good enough" because the computing power that it would take to go through all the possible permutations in a reasonable amount of time (i.e. less then 10 years?) is pretty unrealistic.

When computers get much faster... they will just up the key size to 512, or 1024 bits.
Cycloptichorn

1
Wed 14 Jan, 2009 11:22 am
@ebrown p,
ebrown p wrote:

Bigger keys take more time to crack using brute force methods-- so as computers get faster, the keys get bigger.

Currently 256-bit keys are considered "good enough" because the computing power that it would take to go through all the possible permutations in a reasonable amount of time (i.e. less then 10 years?) is pretty unrealistic.

When computers get much faster... they will just up the key size to 512, or 1024 bits.

I dunno. Quantum computing will change the way we think about keys and encryption, according to some of the research I've done; the theoretical limits to the speed are ridiculous.

From Wikipedia on quantum computing -

Quote:
Potential

Integer factorization is believed to be computationally infeasible with an ordinary computer for large integers that are the product of only a few prime numbers (e.g., products of two 300-digit primes).[7] By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to "break" many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of bits of the integer) algorithm for solving the problem. In particular, most of the popular public key ciphers are based on the difficulty of factoring integers (or the related discrete logarithm problem which can also be solved by Shor's algorithm), including forms of RSA. These are used to protect secure Web pages, encrypted email, and many other types of data. Breaking these would have significant ramifications for electronic privacy and security. The only way to increase the security of an algorithm like RSA would be to increase the key size and hope that an adversary does not have the resources to build and use a powerful enough quantum computer.

A way out of this dilemma would be to use some kind of quantum cryptography. There are also some digital signature schemes that are believed to be secure against quantum computers. See for instance Lamport signatures.

Besides factorization and discrete logarithms, quantum algorithms offering a more than polynomial speedup over the best known classical algorithm have been found for several problems, including the simulation of quantum physical processes from chemistry and solid state physics, the approximation of Jones polynomials, and solving Pell's equation. There is no mathematical proof that an equally fast classical algorithm cannot be discovered, although this is considered unlikely. For some problems, quantum computers offer a polynomial speedup. The most well-known example of this is quantum database search, which can be solved by Grover's algorithm using quadratically fewer queries to the database than are required by classical algorithms. In this case the advantage is provable. Several other examples of provable quantum speedups for query problems have subsequently been discovered, such as for finding collisions in two-to-one functions and evaluating NAND trees.

Consider a problem that has these four properties:

1. The only way to solve it is to guess answers repeatedly and check them,
2. There are n possible answers to check,
3. Every possible answer takes the same amount of time to check, and
4. There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.

An example of this is a password cracker that attempts to guess the password for an encrypted file (assuming that the password has a maximum possible length).

For problems with all four properties, the time for a quantum computer to solve this will be proportional to the square root of n. That can be a very large speedup, reducing some problems from years to seconds. It can be used to attack symmetric ciphers such as Triple DES and AES by attempting to guess the secret key. Regardless of whether any of these problems can be shown to have an advantage on a quantum computer, they nonetheless will always have the advantage of being an excellent tool for studying quantum mechanical interactions, which of itself is an enormous value to the scientific community.

Grover's algorithm can also be used to obtain a quadratic speed-up [over a brute-force search] for a class of problems known as NP-complete.

Cycloptichorn

1
Wed 14 Jan, 2009 11:32 am
@OGIONIK,
There are 2^256 possible keys when you use a 256-bit key.

1.1579208923731619542357098500869 x 10^77 keys.

115,792,089,237,316,195,423,570,985,008,690,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

1
Wed 14 Jan, 2009 11:34 am
@Cycloptichorn,
My understanding is that quantum computing can assist with factoring large numbers, but that it is not applicable to "normal" computing.

So, if you capture the key exchange, and have access to a quantum computer, you might be able to factor the number to get the seed primes in order to decrypt the message, but it does not assist with a brute-force approach to cracking an encrypted message.

1
Wed 14 Jan, 2009 11:35 am
OK, your article has better info than my recollection.
0 Replies

1
Wed 14 Jan, 2009 11:39 am

There are 2^256 possible keys when you use a 256-bit key.

1.1579208923731619542357098500869 x 10^77 keys.

115,792,089,237,316,195,423,570,985,008,690,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000

If you check 1,000/second, it will take 3.6717430630808027468154168254911e+66 years to test every key.

I suppose you might get lucky....
OGIONIK

1
Wed 14 Jan, 2009 11:54 pm
so lets check a million a second haha jk

ok seriously tho, doesnt this mean that even the government is limited by encryptions even a teenager could find on google?

awesome. <3 privacy.
BillRM

1
Thu 15 Jan, 2009 07:26 am
@OGIONIK,
Yes look at truecrypt and pgp to start with and using those programs correctly and you will stop even NSA in it dirty tracks.

An example was a "gentleman" stop at the airport when arriving from abroad and custom agents looking at this computer found what they view as child porn.

After seizing the computer they did a very very dumb thing they shut it off and on reboot found it was protected by whole disk pgp protection.

The courts had refused to order the man to tell them the pass phrase and the government had been stop in it tracks as a result.

He lost the laptop but not his freedoms for a decade or so.

Side note there is a law in England that the police can force you to give up you pass phrase and a case involving animal rights people of all groups is now winding it way in their court system. They might be looking at 2 years in prison for not giving up their keys.
OGIONIK

1
Thu 15 Jan, 2009 08:41 am
@BillRM,
UMM its 1abdgGtYl823638 i think wait wait wait

no no its..

1AbdGgtYl823836

****..
0 Replies

1
Thu 15 Jan, 2009 10:14 am
@OGIONIK,
Let's check a billion a second.

3.6717430630808027468154168254911x10^60 years.

That's 2.4478287087205351645436112169941x10^50 times the current age of the universe.... (Using 15 billion years)

0 Replies

Gargamel

1
Thu 15 Jan, 2009 10:18 am
Holy ****, my nerd alarm just exploded!

1
Thu 15 Jan, 2009 10:24 am
@Gargamel,
Is that what you call that little thing?
Gargamel

1
Thu 15 Jan, 2009 10:26 am
The thing that looks like a Cheeto between two raisins? No. That is my penis.

Carry on.
0 Replies

Robert Gentel

1
Thu 15 Jan, 2009 12:07 pm
You can use brute force to crack encryption. But the longer the encrypted text the harder it is to do.

In recent years, the advent of rainbow tables has made cracking password hashes much more viable. It's basically a huge database of precomputed hashes and many databases will have any string up to a certain length in their database.
BillRM

1
Thu 15 Jan, 2009 01:33 pm
@Robert Gentel,
Yes rainbow tables are a good tool for cracking short and weak passwords/pass phrases, however try using any such tables against a well chosen pass phrase!

Anything longer then 20 characters containing both upper and lower characters with numbers and other such ^ thrown in for good measure and there is not enough computer memory in the world to allow a large enough table to do any good.

Please not one or two dictionary words even with a few numbers thrown in at least if you think you are going to be attack by somone with resources.
0 Replies

BillRM

1
Thu 15 Jan, 2009 01:42 pm
@Robert Gentel,
Gentel with a good pass phrase only 20 characters long I get in the neigberhood of 7x10^35 possible keys!

Of course you need to remember a phrase so it tend to be more non-random then not so for myself I just throw in another five or more characters to make up for that weekness.

Good luck with usng rainbow tables.

1
Thu 15 Jan, 2009 02:06 pm
@BillRM,
No matter how long your password is, it gets stored as a hash.

Rainbow tables allow attackers to look up the hash and find a password that will result in the same hash. It doesn't have to be the same password.
ebrown p

1
Thu 15 Jan, 2009 02:28 pm