Brute forcing

[chrisbrown]

By definition, a brute force attack is one where every possible combination is tried until the right one is found. There are undoubtedly advanced algorithms that perform better, but I haven't looked into much of that so I can't say too much on it.

Regardless, Turing is not the language to use, and to be honest, your time would be better spent learning new concepts like efficient data structures, OO, etc...

[Monduman11]

i just wanted to know if it could be done and what im actually aiming for it to try and teach myself as much c++ as i can over the summer

[Tony]

In many cases efficient algorithms and data structures in Turing will significantly outperform naive implementations in C++. The compiler can only do so much for you.

[Monduman11]

Tony @ Tue Jun 22, 2010 4:33 pm wrote:

In many cases efficient algorithms and data structures in Turing will significantly outperform naive implementations in C++. The compiler can only do so much for you.

lol so what your saying is that it doesnt just depend on the program that your using but rather on the programmer as well

[Tony]

Right.

Lets say that we are sorting 1024 (2^10) items.

A bubble sort will compare each item against each other item and is said to have O(n^2) complexity. That's 1024*1024 = 1,048,576 comparisons.

A QuickSort or MergeSort are on the order of O(n*lg(n)). 1024*lg(1024) = 10,240

So you'd need machine code that is ~100 times faster at this size, and the difference grows very very fast, as the size of the list increases.

[DemonWasp]

Incidentally, the speed difference between Turing and C++ (depending on a lot of factors, such as program type, design, compiler used, machine, etc) is that C++ is "around" 100 times as fast as Turing, so you only have to sort a list of 1024 numbers before (smart Turing implementation) outruns (naive C++ implementation).

[Brightguy]

2goto1 @ Mon Jun 21, 2010 7:18 pm wrote:

But the problem is that no website in the real world supports user authentication this way...if they did they definitely wouldn't have any members!

Believe it or not, I belong to a site which uses exactly that method. An odd choice, but it does happen for casual sites.

chrisbrown @ Tue Jun 22, 2010 3:20 pm wrote:

Let's do the math just for fun. Let's assume your password is 4 characters long, using only lowercase english letters. Using permutations, that's more than 350 thousand combinations.

Since passwords can repeat letters, permutations are not proper here. The answer is just 26^4.

Monduman11 @ Tue Jun 22, 2010 3:25 pm wrote:

umm ouch? lol guess thats a waste of time... how could you make it brute force faster though? cause arnt there some that can figure out your pass in like minutes? i think?

That's easy, you just try out more likely passwords first. You can't brute force a strongly chosen password efficiently.

Tony @ Tue Jun 22, 2010 4:52 pm wrote:

A bubble sort will compare each item against each other item and is said to have O(n^2) complexity. That's 1024*1024 = 1,048,576 comparisons.

In the worst case, of course. Also you should say you are abusing the notation. Formally big-oh doesn't tell you anything about a finite problem size.

[Tony]

Right, the Big-O notation is abused. There are no mentions of constants, and comparisons are done at an arbitrary n0, which is not what Big-O is meant for.

(And Bubble-Sort is n^2 in worst case and average case.)

[Srlancelot39]

...what if...the brute forcing program was able to check each character one by one instead of trying everything at once.
eg. insted of trying:
aaaa (wrong)
baaa (wrong)
caaa (wrong)

it tried
a*** (wrong)
b*** (wrong)
c*** (correct)
ca** (wrong)
cb**(correct)
cba*(wrong)
...
etc.

this way, it is not wasting time trying all 4 characters at once. is there a way for the program to only check an individual character...I don't know; maybe there is maybe there isnt
=P

[Brightguy]

Srlancelot39 @ Mon Aug 02, 2010 4:25 pm wrote:

...what if...the brute forcing program was able to check each character one by one instead of trying everything at once.

Then you can determine the password in linear time. (In the real world you can quickly find the combination of an unlocked combination bike lock using this strategy.)

Srlancelot39 @ Mon Aug 02, 2010 4:25 pm wrote:

is there a way for the program to only check an individual character...

Depends on how cryptograpically-savvy the implementator was. For example, a password submission should not be checked with something like memcmp, since the standard implementation of memcmp will check the memory byte-by-byte and return false after the first mismatch. This makes you vulnerable to a timing attack.

Tony wrote:

(And Bubble-Sort is n^2 in worst case and average case.)

Though bubble sort wont always compare each item against each other item. (Nitpick.)

[DtY]

Monduman11 @ Tue Jun 22, 2010 3:25 pm wrote:

umm ouch? lol guess thats a waste of time... how could you make it brute force faster though? cause arnt there some that can figure out your pass in like minutes? i think?

Generally, if it can run in a minute, it's not going to be brute forcing, it will probably be exploiting weaknesses in whatever was used.

[jmarsiglio]

DtY @ Mon Aug 02, 2010 7:16 pm wrote:

Generally, if it can run in a minute, it's not going to be brute forcing, it will probably be exploiting weaknesses in whatever was used.

Brute-forcing takes way too long for it to be efficient, so it is mainly used for website hacking, even then finding an exploit is far easier than bruteforcing the form. Rainbow tables are the way to go nowadays.

[DtY]

jmarsiglio @ Sun Oct 17, 2010 7:15 pm wrote:

DtY @ Mon Aug 02, 2010 7:16 pm wrote:

Generally, if it can run in a minute, it's not going to be brute forcing, it will probably be exploiting weaknesses in whatever was used.

Brute-forcing takes way too long for it to be efficient, so it is mainly used for website hacking, even then finding an exploit is far easier than bruteforcing the form. Rainbow tables are the way to go nowadays.

You need to have obtained the hash of the password though, and then it only works if the system doesn't salt the hashes.

[SNIPERDUDE]

Mmm, salted hashbrowns

[Coldkick]

Bubble sort is (n-1)^2.
Ie. An 8 string check would have to run through
(8-1)^2=7^2=49 checks.
The last value at each run does not have a check.
1->2, 2->3, 3->4, 4->5, 5->6, 6->7, 7->8