10 BTC 4 U 2 STEAL - Protected by a weak 5-letter password - crack & it's yours!

[casascius]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

No I don't think so. This thread had been going 2 or 3 days before anyone cracked it, and that was only after casascius gave enough information to cut the possible solutions in half. Furthermore, the password didn't have any numbers or any other special characters. A random 5 letter password which we know nothing about would take more than a day to crack even with multiple computers.

And this also assumes that you happened to come across a paper wallet (say you stole a purse at the mall) that you knew had money worth stealing, and also assuming the owner didn't snatch back their own coins using a backup copy they kept at home (presumably half the reason for password-protecting a paper wallet) - something they can almost certainly do before you ever get a chance to crack their password.  Password-protected paper wallets are truly do-it-yourself two-factor bitcoins: they're something you have plus something you know.

[1714871965]

1714871965

[1714871965]

1714871965

[picobit]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

No I don't think so. This thread had been going 2 or 3 days before anyone cracked it, and that was only after casascius gave enough information to cut the possible solutions in half. Furthermore, the password didn't have any numbers or any other special characters. A random 5 letter password which we know nothing about would take more than a day to crack even with multiple computers.

Actually, he gave info that cut the search space by a factor of 2^6 = 64 by giving the case of all letters, and that the first was from the second half of the alphabet.  A five-letter random password is clearly not sufficient, but surprisingly robust for this application.

Looks like I would have found the password in a few days.  I permuted the alphabet to search in another order than everybody else (since I started late), and managed to place W last

[johnniewalker]

1 BTC for the password

[SgtSpike]

1 BTC for the password

WuKvR

[kwoody]

https://www.youtube.com/watch?v=D71MTQc3VO4

[prezbo]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

Yeah, this is incorrect. If anything it has proven to be much much more difficult to crack than it was expected.

[wachtwoord]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

No I don't think so. This thread had been going 2 or 3 days before anyone cracked it, and that was only after casascius gave enough information to cut the possible solutions in half. Furthermore, the password didn't have any numbers or any other special characters. A random 5 letter password which we know nothing about would take more than a day to crack even with multiple computers.

Actually, he gave info that cut the search space by a factor of 2^6 = 64 by giving the case of all letters, and that the first was from the second half of the alphabet.  A five-letter random password is clearly not sufficient, but surprisingly robust for this application.

Looks like I would have found the password in a few days.  I permuted the alphabet to search in another order than everybody else (since I started late), and managed to place W last

Lol. I just did it random by using a regex as input with http://research.microsoft.com/en-us/projects/rex/

[spiccioli]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

Yeah, this is incorrect. If anything it has proven to be much much more difficult to crack than it was expected.

prezbo,

this is only because this was the first time that such a feat was accomplished.

if those bills do spread whoever did this has an infrastructure now to do it again and faster.

the only secure thing would be using pass-phrases, IMHO.

spiccioli

[prezbo]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

Yeah, this is incorrect. If anything it has proven to be much much more difficult to crack than it was expected.

prezbo,

this is only because this was the first time that such a feat was accomplished.

if those bills do spread whoever did this has an infrastructure now to do it again and faster.

the only secure thing would be using pass-phrases, IMHO.

spiccioli

Sure there is no replacement for a high entropy. However, if I understand scrypt correctly, it cannot be calculated on gpus and takes a decent amount of time to be computed on a good cpu, thus making it a lot more difficult to bruteforce passwords, even when having multiple computers at your disposal.

Let's say it takes on average 0.2 seconds for one try. That would make a 7-alphanumeric character password safe for about 5 years even if someone would get 100000 decent cpus together.

[Ente]

So what's the lesson? 5 letter passwords are crackable within a day by any sysadmin. 7 letters are probably crackable within a day by a botnet. 8 and more are impossible to memorize. Passwords in general, can't be considered secure anymore.

Yeah, this is incorrect. If anything it has proven to be much much more difficult to crack than it was expected.

prezbo,

this is only because this was the first time that such a feat was accomplished.

if those bills do spread whoever did this has an infrastructure now to do it again and faster.

the only secure thing would be using pass-phrases, IMHO.

spiccioli

Sure there is no replacement for a high entropy. However, if I understand scrypt correctly, it cannot be calculated on gpus and takes a decent amount of time to be computed on a good cpu, thus making it a lot more difficult to bruteforce passwords, even when having multiple computers at your disposal.

Let's say it takes on average 0.2 seconds for one try. That would make a 7-alphanumeric character password safe for about 5 years even if someone would get 100000 decent cpus together.

..as has been stated before:
You need a password strong enough to surely notice your bill was stolen and to transfer the bitcoins from your backup to a new adress..
I, personaly, think 5 (real) chars is enough for this. For me.
Heck, it'll be a dictionary-word with a number or questionmark added or the like! :-)

Thank you, everybody, for this entertaining show!

Ente

[paybitcoin]

In case anyone is interested, I have posted the C code for the bip38 brute forcer here:

https://github.com/notespace/bip38-cracker

It is a bit buggy and only implements the EC-multiply version of BIP-38 (aka only what is required for this contest) but it works. The porting was mostly straightforward, the most difficult part was getting the repeated AES step right and dealing with typos with {un}encryptedpart{1,2} and the related xor operations with the derived array.

IMHO, it would be nice to change:

- the all 0 IV for the AES ops, maybe use ownerhash? I'm not really sure exactly why, but 0 IVs are taboo.
- simplify the AES, use 32 byte data to match the block size of AES-256 (or use AES-128?) I never got into if the 16-byte data was repeated or if it was just padding at the end.
- can seedb come straight out of the AES decrypt operation (esp if it is AES-128) instead of being xor'd with derived?
- does seedb really have to be stretched to 24 bytes, or can it just be 16? maybe 128 bits is not enough key material...?
- also, the documentation needs to be updated on the en.bitcoin.it wiki as well.

Overall though, it looks like a very handy BIP to have and a good implementation. Thanks for a fun contest and congrats to the winner!

[casascius]

In case anyone is interested, I have posted the C code for the bip38 brute forcer here:

https://github.com/notespace/bip38-cracker

It is a bit buggy and only implements the EC-multiply version of BIP-38 (aka only what is required for this contest) but it works. The porting was mostly straightforward, the most difficult part was getting the repeated AES step right and dealing with typos with {un}encryptedpart{1,2} and the related xor operations with the derived array.

I appreciate that - any code that anyone is willing to post is a head start for somebody else to start implementing the ability to accept BIP38-encoded codes as payment on their website or in their client.

IMHO, it would be nice to change:

- the all 0 IV for the AES ops, maybe use ownerhash? I'm not really sure exactly why, but 0 IVs are taboo.
...
- can seedb come straight out of the AES decrypt operation (esp if it is AES-128) instead of being xor'd with derived?

Of these two questions, the latter is the answer to the former.

This is because I have made a distinction between AES and AES+CBC (cipher block chaining).  AES is the block cipher itself, which is a black box that takes 16 bytes of input and a 32-byte key and deterministically creates 16 bytes of output, note an IV isn't part of that.

C# doesn't seem to expose the elementary AES operation without block chaining, so I have effectively defeated the block chaining by giving an IV of zero and then calling the operation twice in a row to clear out the chaining buffer it maintains internally.

AES+CBC is what you do when you want to use AES to encrypt a stream of blocks, and it involves an automatic XORing the plaintext of block n with the ciphertext of block n-1 (or something substantially similar).  This allows entropy to persist throughout the stream, where otherwise, identical plaintext blocks would produce identical ciphertext output and it would be a clear weakness for most typical data streams.  Since the first block doesn't have a block n-1, that's where the IV is used, and also serves as an initial source of entropy.  In this scheme, we can't afford to have an IV in the most traditional sense (as it would make the encrypted keys 16 bytes or 20+ characters longer), but on the other hand we're using a salted key derivation algorithm where most AES applications are not and therefore have the means to fake it and still get the benefit.  So I have made a tradeoff where I am asking scrypt for more bytes and then using them in a manner (XORing) that gives the same net benefit as CBC would in a typical stream.

- simplify the AES, use 32 byte data to match the block size of AES-256 (or use AES-128?) I never got into if the 16-byte data was repeated or if it was just padding at the end.

The elementary AES operation when you're not using CBC is a 16-bit input and 16-bit output, which is the same for both AES-128 and AES-256.

- does seedb really have to be stretched to 24 bytes, or can it just be 16? maybe 128 bits is not enough key material...?

Exactly.  The one day I proposed 22-character minikeys that flirted with the 128 bit range, the devs weren't excited about the security being needlessly weak, they consider 128 bits an absolute floor.

Thanks for trying and thanks for this fantastic contribution of your tool!

[pc]

This is because I have made a distinction between AES and AES+CBC (cipher block chaining).  AES is the block cipher itself, which is a black box that takes 16 bytes of input and a 32-byte key and deterministically creates 16 bytes of output, note an IV isn't part of that.

C# doesn't seem to expose the elementary AES operation without block chaining, so I have effectively defeated the block chaining by giving an IV of zero and then calling the operation twice in a row to clear out the chaining buffer it maintains internally.

AES+CBC is what you do when you want to use AES to encrypt a stream of blocks, and it involves an automatic XORing the plaintext of block n with the ciphertext of block n-1 (or something substantially similar).  This allows entropy to persist throughout the stream, where otherwise, identical plaintext blocks would produce identical ciphertext output and it would be a clear weakness for most typical data streams.  Since the first block doesn't have a block n-1, that's where the IV is used, and also serves as an initial source of entropy.  In this scheme, we can't afford to have an IV in the most traditional sense (as it would make the encrypted keys 16 bytes or 20+ characters longer), but on the other hand we're using a salted key derivation algorithm where most AES applications are not and therefore have the means to fake it and still get the benefit.  So I have made a tradeoff where I am asking scrypt for more bytes and then using them in a manner (XORing) that gives the same net benefit as CBC would in a typical stream.

I'm no crypto expert by any means, but I get a little nervous since this sounds like you're using crypto primitives in some pretty untraditional ways. Is this a documented industry-standard way of using AES in a reasonable fashion? Is there another cipher out there that is more designed for the encrypting-few-bytes use case? It may very well be fine, but I don't have any way of knowing, so it'd be good to know that the crypto community thinks that this is a good use of algorithms before I go throwing all my savings into a BIP38-encrypted key.

[casascius]

I'm no crypto expert by any means, but I get a little nervous since this sounds like you're using crypto primitives in some pretty untraditional ways. Is this a documented industry-standard way of using AES in a reasonable fashion? Is there another cipher out there that is more designed for the encrypting-few-bytes use case? It may very well be fine, but I don't have any way of knowing, so it'd be good to know that the crypto community thinks that this is a good use of algorithms before I go throwing all my savings into a BIP38-encrypted key.

I would totally welcome the comments from anyone with more expertise.

Keep in mind that the AES step isn't what the protection scheme relies upon.  It is extra protection.  The AES step could be removed and the password would have been just as hard to crack.  The operative part of the password protection is scrypt, and the fact that bitcoin key information is missing without being able to supply the correct parameters to scrypt.

I added AES in there just to add protection against the following: attacker has bitcoin private key for paper wallet A (and not the passphrase), and knows paper wallet B is encrypted with the same passphrase and wants to crack it.  The AES step virtually ensures that no information from knowing private key for wallet A can be used to attack B, but even if the attacker had that information, it's not enough to crack it.  Such a scenario is pretty rare on its face, but one I thought to protect against anyway.  As another poster pointed out, it also makes the task of making an ASIC cracker that much more difficult, assuming someone had a reason to do so.

The elementary forms of the AES-128 and AES-256 ciphers were made for encrypting blocks of exactly 16 bytes, no more, no less, which is why they are called block ciphers.  So it is already suited to the task of encrypting this amount of data.  AES+CBC is what is commonly used when "encrypting a file with AES" - a derivative that we don't need here.

Remember the whole point of using IV's and chaining is to protect a stream of non-random data that is many multiples of the cipher's block size from being compromised due to typical properties of streams.  That's not the case here, because we're just protecting a single random integer.  So I think it is very safe to say that this tool does not even apply to this job.  Read more: http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation

Crypto experts, please fire away!

EDIT: I just noticed the Wikipedia article I linked to says (in the section about IV's):

As a special case, if the plaintexts are always small enough to fit into a single block (with no padding), then with some modes (ECB, CBC, PCBC), re-using an IV will leak only whether two plaintexts are equal.

This usage falls into that special case.  Since in this application, the "plaintexts" are themselves large random numbers, the odds of having two identical "plaintexts" are effectively zero.

[fivemileshigh]

Mike, I really like what you've come up with. Any idea when you'll have something that will let a noob like me roll his own encrypted btc bills at home (on a mac pretty please ?

Also, what's the diff between this an a 30-character brainwallet?

[casascius]

Mike, I really like what you've come up with. Any idea when you'll have something that will let a noob like me roll his own encrypted btc bills at home (on a mac pretty please ?

Mono or Parallels.  Sorry, I don't know enough about Mac OS X to make native Mac apps, so it isn't going to get done by me.  But others have told me it will run just fine on a Mac using Mono with only minor limitations.

Also, what's the diff between this an a 30-character brainwallet?

A brainwallet assumes you've memorized all the key material.

This is a two-factor paper storage solution: it's not enough to just know the passphrase, you also have to have the encrypted private key.  This is not a brainwallet.

[kaycyrils]

did anyone get the pass?

[Ente]

Well, click the link in OP?
emptied on 2012-12-03 21:24:43

Ente

[ericaltm]

Has this been cracked yet?