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

[CIYAM]

This is security by obscurity though. Once they know about your implementation it will be easily cracked.

Oh really - then why hasn't this been cracked already?

(the script in the OP is a simplified version of the one I will publish - btw you cannot run the script I will publish without first modifying it in order to hopefully stop someone being silly enough to run it without first modifying it as I modified the one being tested here)

If I can modify one line of a script and use a 4 letter password that no-one here has been able to crack already then I think that speaks for itself.

[Scrat Acorns]

Oh really - then why hasn't this been cracked already?

First of all, you're implying that just because we haven't cracked it in 10 hours then it will never be cracked.

Secondly, we don't know the exact implementation of your key derivation function.

[phr33]

You can send it to 1GAtPwoTGPQ35y9QugJueum5GzaEzLYjiQ

All winnings will be passed on to a followup contest! It might take a while, but there will be one!

On it's way:

http://blockchain.info/tx/003a4b9ee67639a08c28b9c183ab36f3b2fc192aeac84d9bd8cc29684f6f094e

I have a much better bash script that I am including with a custom Open SUSE distro (which I am still putting together) - that will be a hell of a lot more challenging than this to crack (the point being similar to Mike Caldwell's one that you don't need to remember a huge password to get good security).

Thank you very much! You will be in the list of sources of the price for my upcoming challenge!

Could you please direct me to Mike Caldwell's statements? With a (light but still) background in information theory I'm rather skeptical to this statement. Entropy is a b-tch  

[phr33]

Oh really - then why hasn't this been cracked already?

The difference is that in the case we are cracking you haven't yet published the algorithm. One could say that the algorithm is a part of the key and it needs to be kept secret in order to not compromise security.

I recommend reading this: http://en.wikipedia.org/wiki/Security_by_obscurity

[wachtwoord]

Mike's thread: https://bitcointalk.org/index.php?topic=128699.0

[cedivad]

Oh really - then why hasn't this been cracked already?

We have the 15 millions permutations of the possible key, correct? We also have stuff that runs 10k tests per second.

I don't really understand why this wasn't cracked already. I must be missing something.

[CIYAM]

...we don't know the exact implementation of your key derivation function.

Why would you? The idea is that you have to change the script to create your *own* puzzle.

I understand that creating entropy is not easy (and I am certainly not trying to trivialise this problem) but I think it doesn't need to be nearly as hard as trying to remember huge passwords.

If I am wrong then you will be able to steal funds from CIYAM Open - I welcome the challenge!!!

[K1773R]

yes, for opencl u have to change this

Code:

typedef struct {
        uint8_t length;
        uint8_t v[24];
} gpg_password;

change the 24 to 64 in both files (current folder and opencl).
now its working

Looks good!
I would still defiantly try that using a key with known password to make sure it really works

done, works for CPU and GPU implementation

[Scrat Acorns]

Why would you? The idea is that you have to change the script to create your *own* puzzle.

I understand that creating entropy is not easy (and I am certainly not trying to trivialise this problem) but I think it doesn't need to be nearly as hard as trying to remember huge passwords.

If your key derivation is secret then what you are essentially doing is using that as your password as well. Because to decrypt it you dont only have to remember your 4 chars, but you also have to remember the exact formula of the key derivation.

[phr33]

...we don't know the exact implementation of your key derivation function.

Why would you? The idea is that you have to change the script to create your *own* puzzle.

I understand that creating entropy is not easy (and I am certainly not trying to trivialise this problem) but I think it doesn't need to be nearly as hard as trying to remember huge passwords.

Ok, but now you have to also remember the secret derivation function!

Yes - you can store it on your computer. But then you could also just have stored a better password to begin with!

If you make the derivation function public the security of your short password goes down the drain.

[CIYAM]

If your key derivation is secret then what you are essentially doing is using that as your password as well. Because to decrypt it you dont only have to remember your 4 chars, but you also have to remember the exact formula of the key derivation.

Very true - but it's rather easy to hide a mathematical equation (or something else) in some notes that wouldn't seem directly related to your bitcoins isn't it?

[CIYAM]

Ok, but now you have to also remember the secret derivation function!

Yes - you can store it on your computer. But then you could also just have stored a better password to begin with!

If you make the derivation function public the security of your short password goes down the drain.

Of course - that is a very key point to the technique (although I have no need to write things like that down as I have a very good memory) - but so far you guys haven't been able to read my mind and I wasn't even trying with this one.

[BkkCoins]

Python for the win!

Code:

import itertools
import hashlib

group = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789'

for passw in list(itertools.product(group, repeat=4)) :
  pas = ''.join(passw)
  # Modify next line!
  final = "%s+%s=%s%s@L3AsT\n" % (pas, pas, pas, pas)
  m = hashlib.sha256()
  m.update(final)
  print  "%s" %(m.hexdigest())

Code:

$ time python run.py > dict.txt

real    0m37.305s
user    0m35.162s
sys     0m1.200s

F* ME! I wrote it in C and it's taking 1m 57s to generate the full 14776336 pwd set and I didn't even time it to disk as I planned to pipe it. Must be either openssl lib sha256 is pretty slow or I'm just being retarded with too much string copying and mickey mouse code.

[CIYAM]

The difference is that in the case we are cracking you haven't yet published the algorithm. One could say that the algorithm is a part of the key and it needs to be kept secret in order to not compromise security.

I recommend reading this: http://en.wikipedia.org/wiki/Security_by_obscurity

Nice link - and indeed the "salting algorithm" *needs* to be changed by the user (the *real* script literally won't hash a password for you unless you do modify it).

This technique (perhaps unlike Mike's) is only being aimed at those who are capable of using it (i.e. not for Gavin's grandma) although perhaps others can work out some ways to make this even easier for the less computer literate (am willing to set up a task on CIYAM Open and provide some funds if anyone is interested in taking this on).

[phr33]

F* ME! I wrote it in C and it's taking 1m 57s to generate the full 14776336 pwd set and I didn't even time it to disk as I planned to pipe it. Must be either openssl lib sha256 is pretty slow or I'm just being retarded with too much string copying and mickey mouse code.

I'll happely put it in bold:
Python for the win!  

Kidding aside, it's generally a good idea to use as high level library functions as possible, e.g. in my case use itertools to create and iterate the list, rather than doing things manually. If you have a problem, you can bet someone already had a similar one, AND came up with a quicker solution than you would in 15 minutes  

Python just happens to have a sh-t load of such libraries. Not only do you get up and running quickly. It also often runs quite fast. (I realize this is the wrong forum to make such a statement. I know Bitcoin mining is not quick enough on a python ref implementation )

[K1773R]

F* ME! I wrote it in C and it's taking 1m 57s to generate the full 14776336 pwd set and I didn't even time it to disk as I planned to pipe it. Must be either openssl lib sha256 is pretty slow or I'm just being retarded with too much string copying and mickey mouse code.

I'll happely put it in bold:
Python for the win!  

Kidding aside, it's generally a good idea to use as high level library functions as possible, e.g. in my case use itertools to create and iterate the list, rather than doing things manually. If you have a problem, you can bet someone already had a similar one, AND came up with a quicker solution than you would in 15 minutes  

Python just happens to have a sh-t load of such libraries. Not only do you get up and running quickly. It also often runs quite fast. (I realize this is the wrong forum to make such a statement. I know Bitcoin mining is not quick enough on a python ref implementation )

my java + JNI (C) stuff was faster

my rule for levels: work at the API/level where u fully know what happens, never go deeper.

[phr33]

Nice link - and indeed the "salting algorithm" *needs* to be changed by the user (the *real* script literally won't hash a password for you unless you do modify it).

This technique (perhaps unlike Mike's) is only being aimed at those who are capable of using it (i.e. not for Gavin's grandma) although perhaps others can work out some ways to make this even easier for the less computer literate (am willing to set up a task on CIYAM Open and provide some funds if anyone is interested in taking this on).

To be picky the term "secret key derivation function" is probably more correct than "salting algorithm". This might look like salting, but actually isn't. I'm not going to link to wikipedia again, but there is some nice info on slating there as always.

To better illustrate that the derivation function is a part of the password is that you could of course select an "algorithm" that doesn't use any input. such as

Code:

echo "my_secret_123;

Here you add zero bits of entropy to get the key and the entire security lies in the secrecy of the function.

[CIYAM]

To be picky the term "secret key derivation function" is probably more correct than "salting algorithm". This might look like salting, but actually isn't. I'm not going to link to wikipedia again, but there is some nice info on slating there as always.

To better illustrate that the derivation function is a part of the password is that you could of course select an "algorithm" that doesn't use any input. such as

Code:

echo "my_secret_123;

Here you add zero bits of entropy to get the key and the entire security lies in the secrecy of the function.

Sorry for the poor terminology (I am actually far from being an encryption expert) but I am hoping that the point being that "it only takes a bit of creativity" to create a secure password is being made (rather than the "brainwallet - type in a very long and hard to remember password" approach).

[Scrat Acorns]

Sorry for the poor terminology (I am actually far from being an encryption expert) but I am hoping the point being that "it only takes a bit of creativity" to create a secure password is being made (rather than the "brainwallet" approach).

I don't see how this is not a brainwallet too. It would be like creating an electrum 10 word passphrase, remembering only 4 of them and writing 6 of them down on a piece of paper.

You're just adding the entropy either way.

The difference is that you can easily calculate the entropy of a brainwallet. Your function however not so much. So you won't know how secure it is.

[CIYAM]

I don't see how this is not a brainwallet too. It would be like creating an electrum 10 word passphrase, remembering only 4 of them and writing 6 of them down on a piece of paper.

You're just adding the entropy either way.

It is indeed a "brainwallet" of sorts but I think it is a much better one - if I am so wrong then I would have thought that the 10 BTC would have already been moved by now.