Solve a riddle, guess a 4 char password and add 10 BTC to your xmas... SOLVED!!

[K1773R]

"Solve a riddle, guess a 4 char password and add 10 BTC to your xmas stocking!" <-- why not "Solve a riddle, bruteforce a 4 char password with an unknown salt and add 10 BTC to your xmas stocking! )"

All will be revealed in time but I will add now that the title of this topic was not inaccurate.

time is of the essence

[K1773R]

For those who dont have enough hashing power, u can send me patterns per PM and il test em, if they match u get a portion of the 10BTC (going to distribute it fair to all who helped, including me).

[CIYAM]

time is of the essence

If you are throwing in the towel then please post a BTC address here (or send me one in a PM) so I can at least throw 1 BTC your way for the time spent on this.

For those who dont have enough hashing power, u can send me patterns per PM and il test em, if they match u get a portion of the 10BTC (going to distribute it fair to all who helped, including me).

Doh - just as I posted - well glad to see you haven't given up!

[K1773R]

If you are throwing in the towel then please post a BTC address here (or send me one in a PM) so I can at least throw 1 BTC your way for the time spent on this.
Doh - just as I posted - well glad to see you haven't given up!

Till date i never gave up on something, i dislike to see this happening

"at first it was for the money, but now I just want it to be solved " -- TechMix <-- same applies for me.

u can find my BTC address in my signature, ty already (again)!

[hazek]

Is anyone interested in an address that contains 230 satoshis? It's in an electrum wallet I'm about to delete and can't be bothered to try and salvage them without paying a fee, so if anyone wants them, they can have the wallet and get them!

sure ty already.
Good opportunity to hack around with electrum.

Yeah I changed my mind cause I didn't want to reveal my tx history which you could see by reconstructing the wallet.. so I retrieved the private key myself. Sorry!

[CIYAM]

btw - I gather you are down to around 10 secs per "sweep" - now if the script were to have the following addition:

Code:

for i in {1..999}
do
 password=`echo "$password 1+1=2 $opassword" | sha256sum`
done

how much slower would that make each pass?

(this is nothing to do with the actual challenge but for inclusion in a distro)

[K1773R]

btw - I gather you are down to around 10 secs per "sweep" - now if the script were to have the following addition:

Code:

for i in {1..999}
do
 password=`echo "$password 1+1=2 $opassword" | sha256sum`
done

how much slower would that make each pass?

(this is nothing to do with the actual challenge but for inclusion in a distro)

whats $opassword? ERROR: Undefined variable T_LOCAL!
it would'nt make it longer since theres no math in it, just simple strings. it would even be faster since the string is shorter.

[CIYAM]

whats $opassword? ERROR: Undefined variable T_LOCAL!
it would'nt make it longer since theres no math in it, just simple strings. it would even be faster since the string is shorter.

Sorry - I should have made it clearer $opassword is the original password (and you can see it is being used along with the hash and some extra salt to rehash so the string is not shorter and of course the number 999 would be changeable).

[K1773R]

whats $opassword? ERROR: Undefined variable T_LOCAL!
it would'nt make it longer since theres no math in it, just simple strings. it would even be faster since the string is shorter.

Sorry - I should have made it clearer $opassword is the original password (and you can see it is being used along with the hash and some extra salt to rehash so the string is not shorter and of course the number 999 would be changeable).

u could do "$password!=$opassword", thats good enough already. "1+1=2" dosnt help much as its static (nonchanging).
that would be 64+2+64+1 (password, !=, password, \n aka newline) - 131 keylength which is much bigger than what we do have right now.

[BkkCoins]

btw - I gather you are down to around 10 secs per "sweep"

Whos's doing 10 second sweeps now? It takes me about 4 minutes each @61,000 c/s.
(By sweep you mean one full set of 4 char inputs, right?)

I ran a bunch more patterns while I slept. We should have a place to post the failed patterns so we don't repeat others work. I mean rather than cluttering up the thread with long lists.

Yes, the problem now is coming up with more variations to test.

[K1773R]

btw - I gather you are down to around 10 secs per "sweep"

Whos's doing 10 second sweeps now? It takes me about 4 minutes each @61,000 c/s.
(By sweep you mean one full set of 4 char inputs, right?)

I ran a bunch more patterns while I slept. We should have a place to post the failed patterns so we don't repeat others work. I mean rather than cluttering up the thread with long lists.

Yes, the problem now is coming up with more variations to test.

its just his guess how long we need, i need around 1 min per sweep (creating wordlist and bruteforcing it).

Code:

OpenCL platform 0: NVIDIA CUDA, 1 device(s).
Using device 0: GeForce GTX 580
Loaded 1 password hash (OpenPGP / GnuPG Secret Key [OpenCL])
guesses: 0  time: 0:00:00:35 DONE (Thu Dec 27 02:35:34 2012)  c/s: 418637  trying: 158b4bcf931ebb9af629643fe653e904ee50733d208b64bc9d3262a96df7e437 - aada9f2c829ce479c03a35c35db77e15e3a8dc7634ccf831875b77b9cbf039af

[CIYAM]

its just his guess how long we need, i need around 1 min per sweep (creating wordlist and bruteforcing it).

Oh - must have got confused by all the stats - so if the script was changed to this:

Code:

password="${password}+${password}=${password}${password}@L3AsT"
opassword=$password
for i in {1..999}
do
 password=`echo "$password $opassword $password" | sha256sum`
done

Could you give me an estimate of the sweep time?

[K1773R]

its just his guess how long we need, i need around 1 min per sweep (creating wordlist and bruteforcing it).

Oh - must have got confused by all the stats - so if the script was changed to this:

Code:

password="${password}+${password}=${password}${password}@L3AsT"
opassword=$password
for i in {1..999}
do
 password=`echo "$password[$opassword]$password" | sha256sum`
done

Could you give me an estimate of the sweep time?

bruteforce time: same since its still a GPG key based on sha256sum (still, this dosnt matter since we want the approx for a full sweep)

creating the wordlist would take 1000-10000 times longer than what we got now. 1k (compared to 1 as we do have it right now) rounds of sha256 and string concatenationg, this takes tons of CPU/GPU cycles.

think about it like this: bitcoin is sha256(sha256($work)), now my GTX580 GPU can hash at 150-170 MH/s. double the hashrate and you got rougly single sha256 round 300MH/s. divide by 1k and u get 300k/s. 300k/s only for the sha256, without the String contatenation and so on. lets be fair and say if everything could be moved to my GPU (hashing, wordlist, bruteforcing) you would be able to get around 10-100k/s (il take 50k/s).
since the password is still 4 char alphanumeric it would be a wordlist with 14776336 hashes, this means it would take around 295526 Seconds or 82 Hours for 1 sweep!
if the salt is unknown too (as now) it would be almost impossible to do in it a matter of time, not even to talk about that it wont be worth it.
these are all just guesses based on my knowledge, good question are always hard to answer. A good question is based on facts, since these are unknown i cant give u a perfect answer and i dont want to wait some days for it to complete and dislike to write such a tool. il hope this is good enough

EDIT: this is only correct if u got the sha256 of the password, otherwise it would be MUCH slower since it would have to do the GPG stuff too. sha256 around 300MH/s for me (aprox), GPG around 400k/s. (factor of 1.1k).
EDIT: for example, pipe 1 concat string into all these hashing tools in a chain:

Code:

sha1sum       sha224sum     sha256sum     sha384sum     sha512sum     md5sum      cksum

this would create a insane password (including ur for loop) which would be mostly uncrackable.

[CIYAM]

Thanks - so if did this:

Code:

opassword=`echo "($password $password $password)" | sha256sum`

# This strips off the trailing space and dash from sha256sum.
opassword=`echo $opassword | awk -F ' ' '{ print $1 }'`

for i in {1..99} # NOTE: Also change the # of iterations here.
do
 password=`echo "$password $opassword $password" | sha256sum`
done

password=`echo $password $opassword | awk -F ' ' '{ print $1 }'`

how would that change things?

[K1773R]

Thanks - so if did this:

Code:

opassword=`echo "($password $password $password)" | sha256sum`

# This strips off the trailing space and dash from sha256sum.
opassword=`echo $opassword | awk -F ' ' '{ print $1 }'`

for i in {1..99} # NOTE: Also change the # of iterations here.
do
 password=`echo "$password $opassword $password" | sha256sum`
done

password=`echo $password $opassword | awk -F ' ' '{ print $1 }'`

how would that change things?

would take atleast twice as long (ignoring the decreased iterations) since u got twice string concat and shasum, your first awk is useless since u can take the full output and reuse it. if u really want to create something secure u shouldnt do it in bash since ur depending on the binarys of the distro, if someone puts malicious binarys in your $PATH every effort would be useless. create your project in python (since every linux distro includes it per default) or C (best way since u can specify much more and its much safer).

EDIT: for performance reasons, use cut instead of awk.

[CIYAM]

Securing the distro is another issue as is securing the computer (will be discussing that in another thread after this) and although I agree a program rather than a bash script would be better if you have a secure computer (the most important thing) and a distro that you trust (not quite as important really as the script is running programs that can be tested).

Turning this into something more "Gavin's grandma" friendly would be quite hard - but I have some ideas about this.

The first being to have a list of meta-password logic templates (such as "math equations", "sewing patterns", etc.) and after you choose the logic template you would then supply the "variables" (let's say at least a couple of numbers) and then it would create a specific password script line (to replace the one in default template).

So from a menu I select: Math Equations
then from a sub-menu I select: x+y=z
and type in values 1, 2 for x and y and it might then spit out:

$password+$password$password=$password$password$password

[K1773R]

Securing the distro is another issue as is securing the computer (will be discussing that in another thread after this) and although I agree a program rather than a bash script would be better if you have a secure computer (the most important thing) and a distro that you trust (not quite as important really as the script is running programs that can be tested).

Turning this into something more "Gavin's grandma" friendly would be quite hard - but I have some ideas about this.

The first being to have a list of meta-password logic templates (such as "math equations", "sewing patterns", etc.) and after you choose the logic template you would then supply the "variables" (let's say at least a couple of numbers) and then it would create a specific password script line (to replace the one in default template).

So from a menu I select: Math Equations
then from a sub-menu I select: x+y=z
and type in values 1, 2 for x and y and it might then spit out:

$password+$password$password=$password$password$password

if u want to create a secure distro u should implement this: http://stackoverflow.com/questions/1732927/signed-executables-under-linux
combine the signed stuff into ur hashing algo, therefore if someone puts in differents binarys and would be able to disable the signed binary enforcement of the kernel, your algo would change and u wouldnt be able to de/encrypt anymore (or atleast not correct, u can always en/de-crypt to garbage).


EDIT: simple rule based on this: the longer it takes to hash 1 round, the longer it takes to bruteforce it (assuming there are no design flaws)

[paybitcoin]

Turning this into something more "Gavin's grandma" friendly would be quite hard - but I have some ideas about this.

The first being to have a list of meta-password logic templates (such as "math equations", "sewing patterns", etc.) and after you choose the logic template you would then supply the "variables" (let's say at least a couple of numbers) and then it would create a specific password script line (to replace the one in default template).

So from a menu I select: Math Equations
then from a sub-menu I select: x+y=z
and type in values 1, 2 for x and y and it might then spit out:

$password+$password$password=$password$password$password

You can get a good idea of the additional complexity by estimating the additional bits of entropy. With a 4 character, alphanumeric, mixed case password [0-9A-Za-z] that's 62^4 = 23.8 bits of entropy. In the same way, 5 chars = 29.8 bits and 6 chars = 35.7 bits.

Adding to your equations and patterns examples, say you have 40 different equations and patterns to choose from which can each take an x,y of 1-10. That would be an additional 40 * 10 * 10 possibilities or 11.9 additional bits of entropy. So in this example, adding the 40 equation and pattern options adds additional 'strength' of 2 extra characters. (23.8 + 11.9 = 35.7)

Personally, I would rather use a standard KDF (like PBKDF2, scrypt, bcrypt) over using a custom key-strengthening method like this. If in the future you ever want someone else to implement your generation method, any of these standard algorithms are already documented, cryptanalyzed, implemented as libraries, and have tuneable levels of strengthening so they can be future-proofed.

[CIYAM]

Adding to your equations and patterns examples, say you have 40 different equations and patterns to choose from which can each take an x,y of 1-10. That would be an additional 40 * 10 * 10 possibilities or 11.9 additional bits of entropy. So in this example, adding the 40 equation and pattern options adds additional 'strength' of 2 extra characters. (23.8 + 11.9 = 35.7)

Personally, I would rather use a standard KDF (like PBKDF2, scrypt, bcrypt) over using a custom key-strengthening method like this. If in the future you ever want someone else to implement your generation method, any of these standard algorithms are already documented, cryptanalyzed, implemented as libraries, and have tuneable levels of strengthening so they can be future-proofed.

Thanks for the info and yes I was going to add a call to one of those to the bash script for good measure (this challenge was mostly as a bit of an experiment).

[btctalk]

after reading 10 pages, I guess I'll keep on reading instead of trying to solve the "riddle"... :-"