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

[casascius]

No joke - see the BTC at http://blockchain.info/address/1BBBvd9G5YThYVVMSGSxJzQvQiQm3WxJC2

Not a gimmick

First person to brute-force this encrypted private key and take the funds gets them, no strings attached.

The password is five letters (no joke, no gimmick, not a riddle, example "AAAAA" and "zzzzz" are the lowest and highest candidates)

Given the obvious weakness of the password, these 10 BTC WILL get taken... it might as well be by you.

Private key is encrypted using methodology in BIP 38: https://en.bitcoin.it/wiki/BIP_0038

Working encryption/decryption code for Windows/.NET (as well as generator of these paper wallets) can be found at:

github: https://github.com/casascius/Bitcoin-Address-Utility
or download binary and source: https://casascius.com/btcaddress-alpha.zip



My interest in running this contest of sorts is to generate discussion and measure interest in password-protected paper wallets, and I am simply curious how long it might take somebody to crack one of these knowing the password is weak.  The password will be revealed to everyone once it is clear the money has been taken.

[1715312885]

1715312885

[1715312885]

1715312885

[casascius]

Did anyone read http://www.wired.com/gadgetlab/2012/11/ff-mat-honan-password-hacker/all/ and what did you think of it?

Yeah, in fact, I am surprised it's 2012 and there isn't a popular standardized hardware security module meant for people to carry and log into websites.

That's part of my purpose of bringing password protected paper wallets to the Bitcoin community.  That constitutes simple two-factor Bitcoin storage usable by anybody: something you have and something you know.

My expectation is that weak passwords, with their obvious shortcomings, will still provide a "bicycle lock" level of security: they're still crackable, but would give the average user enough time to move their coins elsewhere in the event of loss or theft assuming they prepared themselves to do so.

It would be blasphemous for someone to use such a password for their savings wallet, but for protection of a single bitcoin from the casual thief, they have the same level of utility as a four-digit iPhone lock: a measure of protection from 99% of the population likely to steal it.

[hazek]

Well we do have two hardware wallets being developed so I think this problem will soon be reasonably addressed.

[wachtwoord]

Damn nice timing, just as I am heading out ..

Pretty sure this will be gone tomorrow because this is pretty straightforward. Fun contest though

[Meni Rosenfeld]

Modified your software into a script that tries all combinations...

Then realized it will take 36 years to run.

So a much more efficient calculation method would be needed.

[casascius]

Modified your software into a script that tries all combinations...

Then realized it will take 36 years to run.

So a much more efficient calculation method would be needed.

It would take 36 years to run on the slow C# crappy implementation of scrypt that I have bundled with my app.  Simply feeding the same input to a more efficient implementation should chop this figure down by orders of magnitude.

[casascius]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

[Yuhfhrh]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

Tell me the first 4 bits and I'll get it in no time. 

[casascius]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

Tell me the first 4 bits and I'll get it in no time.  

That means if I don't tell you the first 4 bits, you'll get it in 16 * (no time).

But if you know some way where just 4 bits would give you more than a 16x advantage, please share!

[Yuhfhrh]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

Tell me the first 4 bits and I'll get it in no time.  

That means if I don't tell you the first 4 bits, you'll get it in 16 * (no time).

But if you know some way where just 4 bits would give you more than a 16x advantage, please share!

No time≠0, it would be the time it takes to manually guess the password.

[Elxiliath]

Maybe it's just me but I'm having trouble running the application to decrypt any phrase.  Maybe i'm not put the codes in the right fields?

[casascius]

Maybe it's just me but I'm having trouble running the application to decrypt any phrase.  Maybe i'm not put the codes in the right fields?

Here is an example to decrypt.

Run the program, choose Tools - Address Utility.

Here is a test encrypted private key, paste it into the "Private Key (WIF)" box.
6PRJpenX5x4NffBK4dGxXgh1bLqwpSQBwhMXwCdg5k85d7PnPGMCaVdgGk

To decrypt it, fill in the password (which for this test key is "AAAAA") and then click the "down arrow" next to the password box.  The resulting bitcoin address is 1MfxvPTcpnVNU4bi2xs7XcZnsHqFZVKKEn and the corresponding private key should show.

Now on the other hand, to create a batch of encrypted keys, instead of doing Tools - Address Utility, simply do Address - Generate Addresses.  Specify that you want encrypted keys, put in a passphrase, and it will generate a boatload of keys (or rather, the number you asked for).  If you want them printed on paper wallets like the one in the OP, then just choose Selection - Print Banknote Vouchers, pick a color and a printer, voila.  Notably, it's very fast to generate lots of keys with the same password, since the slow step of hashing the password is done once and then the resulting work can be reused for all of the keys.

[kokojie]

I don't think this test can provide any useful information, once your paper bitcoin become wide spread, someone will develop a more efficient cracker. Though right now, it is pretty difficult to crack this 5 letter password because of slow scrypt performance in c#.

[pc]

I decided to see if I could guess the password directly, but the first few words I thought to try haven't worked out…

I had been meaning for a while to see if Casascius's utilities would work under Mono on Mac, and so this contest gave me the incentive to actually try downloading Mono and see if it'd work. So, out of putting this 10 BTC he at least got another user of his program. It does seem to mostly work, though I see boxes where I'm assuming I'm supposed to see arrows, and the menus don't really work when I have it on my left monitor.

If I were to guess the password, is there a button to convert the private key to the standard unencrypted WIF "5" version so that I could import it into a wallet (or maybe generate a raw transaction, if I'm feeling lucky)?

And can you hint if I'm likely to get anywhere with a dictionary attack, or was it made up of 5 random letters? Or will you not say yet?

Thanks!

[casascius]

I had been meaning for a while to see if Casascius's utilities would work under Mono on Mac, and so this contest gave me the incentive to actually try downloading Mono and see if it'd work. So, out of putting this 10 BTC he at least got another user of his program. It does seem to mostly work, though I see boxes where I'm assuming I'm supposed to see arrows, and the menus don't really work when I have it on my left monitor.

Thanks for the helpful info.  I never knew Mono worked on Mac.  I am guessing the font it uses doesn't contain the Unicode arrow code points I'm using.

If I were to guess the password, is there a button to convert the private key to the standard unencrypted WIF "5" version so that I could import it into a wallet (or maybe generate a raw transaction, if I'm feeling lucky)?

The decryption would yield the hex private key.  Then you'd just blank out the password and push the "up arrow" (I guess you see boxes, but it's on the left) and it will convert back to WIF without encryption.

And can you hint if I'm likely to get anywhere with a dictionary attack, or was it made up of 5 random letters? Or will you not say yet?

I will wait a while, and then I will pick a time and the amount of password information I plan to reveal, and then reveal it at the specified time.  Assuming it's not cracked first.  For example I may reveal the casing of the letters, cutting the difficulty by a factor of 32 (assuming they're random - something I'm not revealing at this point).

[Elxiliath]

I have to say your documentation is very good in your application, also, it's quite difficult inserting a loop and array to generate the password properly.  I'll continue my work at trying. 

[Elwar]

password is BBBBB or BBBBTC

on an android tablet or I would try it myself

[runlinux]

I have a loop in place, but ungh... its slow! i'll step this up to a beefier machine...

[hardcore-fs]

K... I think there may be a weakness!!!!, if I understand the code correctly...

HC

[pc]

I did try BBBBB, BBBbb, BBBtc, and BBBTC, figuring that the address starting with 1BBB might not be a coincidence. No luck so far, though.

[Vorksholk]

Got so excited. False positive lol

[thirdchance57]

i wish i could crack it but i'm just a noob.

awesome work creating the bank note generator

[casascius]

K... I think there may be a weakness!!!!, if I understand the code correctly...

HC

If you find one, please share!

[HotDiggityDawg]

I thought I cracked it, and then I realized I hit the "Generate" key on accident lmao.

I'm a total noob with no hope of getting this but it's been fun trying! And obviously I'll continue trying Thanks casascius.

[TTBit]

My 6 character private keys seem secure enough

[finkleshnorts]

hmm, where do I go to write the loops? This is my first application of programming outside school.

[Elxiliath]

You'll need to make the loop conditional on the input of the text field. But you will have to incorporate the checking functions and have the value change after a negative test and adjust the text field there after.

Try Form1.cs

[finkleshnorts]

I give up

[bitfreak!]

Well assuming the password is a word in the dictionary, there are something like 10,000 words which are 5 letters long (that's a very rough guess based on the fact most dictionaries have around 200,000 words).

Some brief testing with the address utility software indicates that it takes about 3.5 seconds to decrypt the private key using my Phenom II X4 810 (also a very rough estimate using only the GUI).

Assuming my calculations so far are remotely correct, to test 10,000 pass phrases when each test takes about 3.5 seconds, will take at least 9 hours. Of course the pass should be found before trying all 10,000.

If the password is a 5 letter English word, it would probably be possible to crack the key using a list of the 5,000 most common 5 letter words or even less. However, the words should be tested in all caps also, so we're back to 10,000.

[Nolo]

I'd like to give it a shot, but have no experience brute forcing a key.  Is there any particular program I could download to try, or is it something I would have to write myself?

[Phinnaeus Gage]

I not going to do this myself, but I will submit one password guess. The first person to try it and it works, please split the bounty with me. Here is my guess: Bruno.

~Bruno K~

[Nolo]

I not going to do this myself, but I will submit one password guess. The first person to try it and it works, please split the bounty with me. Here is my guess: Bruno.

~Bruno K~

Sorry no dice.   

[Elxiliath]

lol, nice.  This is getting more interesting the more I drink.  Haha.  I'm sitting here trying to code in a virtual machine I installed just for this.  I don't think I will guess this or get it, but it's fun and would be nice.

[adamstgBit]

well, i wasted some time on the problem

can't find a C++ version of the SCrypt, so i gave up  

BTW the password is not  "MikeC" 

[Elxiliath]

The coding process is pretty straight forward, it should be easy to compile your own app with both the code or decode process and attempt it. 

[kokojie]

hmm, where do I go to write the loops? This is my first application of programming outside school.

There's no point in writing the loop in C#, as someone already pointed out, using C#, it would take 36 years to crack. You have to rewrite the entire decryption algorithm, in another language, that has a fast scrypt implementation. But if you want to try, the loop should be written in btnPrivWIFToHex_Click method, which is in Form1.cs

[bitfreak!]

Here are some good 5-letter word lists for those who want to take the dictionary approach.

8938 5-letter words:
http://www.poslarchive.com/math/scrabble/lists/common-5.html

5757 5-letter words:
http://homepage.cs.uiowa.edu/~sriram/21/fall07/words.dat

[hardcore-fs]

K... I think there may be a weakness!!!!, if I understand the code correctly...

HC

If you find one, please share!

Well I'd started and my F***** RAID just crashed.

So I may as well share it.... if I understand it correctly.......

It seems that it may have a similar weakness to the zip format.. if I'm not mistaken.


public override bool DecryptWithPassphrase(string passphrase){
.....}


If we look down we see:

byte[] checksum = sha256.ComputeHash(utf8.GetBytes(passphrase + "?"));

            if (hex[2] != 0x80) {
                if ((checksum[0] & 0x7f) != hex[2] || (checksum[1] & 0x7e) != (hex[3] & 0x7e)) {
                    return false;
                }
            }

It seems we can recover a partial solution, because if it is NOT a partial solution the above will fail.

By getting the products up-to this stage, popping them over the serial port to an fpga...... and since Bitcoin is DOUBLE sh256
We can get two engines cycling thrugh the Sha256 keys for the range AAAAA-zzzzz ( actually by splitting the space over two devices we can half the searchtime with a brute it becomes 190102016

Each time we get a 'hit' from the above, we pop it back to the computer to drop it into the code that follows the above code in  "DecryptWithPassphrase"

so even with a XUPV5 I can get over 500MHS through the key address space

52*52*52*52*52=380204032

0.76 seconds  Unless my maths have broken down.

Like I say my development env. crashed so I've nothing to test with.

[adamstgBit]

hmm, where do I go to write the loops? This is my first application of programming outside school.

There's no point in writing the loop in C#, as someone already pointed out, using C#, it would take 36 years to crack. You have to rewrite the entire decryption algorithm, in another language, that has a fast scrypt implementation. But if you want to try, the loop should be written in btnPrivWIFToHex_Click method, which is in Form1.cs

I have a funny feeling scrypt will be slow no matter what the language

The algorithm was specifically designed to make it costly to perform large scale custom hardware attacks by requiring large amounts of memory

good luck

[bitfreak!]

I just read this:

On modern hardware and with default parameters, the cost of cracking the password on a file encrypted by scrypt enc is approximately 100 billion times more than the cost of cracking the same password on a file encrypted by openssl enc; this means that a five-character password using scrypt is stronger than a ten-character password using openssl.

https://www.tarsnap.com/scrypt.html

There's no way anyone is going to crack this via simple brute force. A dictionary attack is the only plausible option. If the password is a random jumble of lowercase and uppercase characters, I doubt anyone will crack it.

[Meni Rosenfeld]

Well I'd started and my F***** RAID just crashed.

So I may as well share it.... if I understand it correctly.......

It seems that it may have a similar weakness to the zip format.. if I'm not mistaken.


public override bool DecryptWithPassphrase(string passphrase){
.....}


If we look down we see:

byte[] checksum = sha256.ComputeHash(utf8.GetBytes(passphrase + "?"));

            if (hex[2] != 0x80) {
                if ((checksum[0] & 0x7f) != hex[2] || (checksum[1] & 0x7e) != (hex[3] & 0x7e)) {
                    return false;
                }
            }

It seems we can recover a partial solution, because if it is NOT a partial solution the above will fail.

By getting the products up-to this stage, popping them over the serial port to an fpga...... and since Bitcoin is DOUBLE sh256
We can get two engines cycling thrugh the Sha256 keys for the range AAAAA-zzzzz ( actually by splitting the space over two devices we can half the searchtime with a brute it becomes 190102016

Each time we get a 'hit' from the above, we pop it back to the computer to drop it into the code that follows the above code in  "DecryptWithPassphrase"

so even with a XUPV5 I can get over 500MHS through the key address space

52*52*52*52*52=380204032

0.76 seconds  Unless my maths have broken down.

Like I say my development env. crashed so I've nothing to test with.

This part of the code doesn't even run when doing the decryption. It has nothing to do with the problem. The code you need is in Bip38KeyPair.cs.

Anyway, doing SHA256 on the entire input range takes about 100 seconds, so that's more or less what you could save (out of decades) by offloading such calculations (if they exist).

I just read this:

On modern hardware and with default parameters, the cost of cracking the password on a file encrypted by scrypt enc is approximately 100 billion times more than the cost of cracking the same password on a file encrypted by openssl enc; this means that a five-character password using scrypt is stronger than a ten-character password using openssl.

https://www.tarsnap.com/scrypt.html

There's no way anyone is going to crack this via simple brute force. A dictionary attack is the only plausible option. If the password is a random jumble of lowercase and uppercase characters, I doubt anyone will crack it.

Perhaps for the first clue casascius will say if the password is random or meaningful.

[casascius]

Well I'd started and my F***** RAID just crashed.

Ouch, hope you manage to get it back up and running.

If we look down we see:

byte[] checksum = sha256.ComputeHash(utf8.GetBytes(passphrase + "?"));

            if (hex[2] != 0x80) {
                if ((checksum[0] & 0x7f) != hex[2] || (checksum[1] & 0x7e) != (hex[3] & 0x7e)) {
                    return false;
                }
            }

It seems we can recover a partial solution, because if it is NOT a partial solution the above will fail.

This isn't it.  I have implemented multiple ways to encrypt keys, the contest key has a prefix of 6Pf and therefore uses the EC Multiply method I detail in BIP 38.  The code you're quoting here is from ShaPassphraseKeyPair.cs, which is for a simpler SHA256-based algorithm that doesn't use scrypt, and the code you've quoted doesn't ever get reached when you attempt to decrypt the note in the OP.  The class you want to be poking at is Bip38KeyPair.cs, specifically the portion that creates a Bip38Intermediate from the passphrase and tries to use it to decrypt the key.

The use of EC Multiply and the Bip38Intermediate code isn't what makes it slow, rather, these are responsible for a couple of features: 1 - it allows one person to know the passphrase and give away only an "intermediate code", and a second person to generate bitcoin addresses with it that only the first person's passphrase can spend (which I intend to use to offer two-factor physical bitcoins).  2 - it happens to allow one passphrase to be expensively hashed once and then used to create thousands of new bitcoin addresses, each with unique per-address salt but the same passphrase, very quickly.

By getting the products up-to this stage, popping them over the serial port to an fpga...... and since Bitcoin is DOUBLE sh256
We can get two engines cycling thrugh the Sha256 keys for the range AAAAA-zzzzz ( actually by splitting the space over two devices we can half the searchtime with a brute it becomes 190102016

The algorithm that needs to be accelerated to make this work is scrypt, rather than sha256, so the FPGA may not be of much use.

[adamstgBit]

The algorithm that needs to be accelerated to make this work is scrypt

I'm thinking scrypt cannot be accelerated enough, its deigned to take time, this is what makes it strong.

I'm no expert, this is the conclusion i came to after a few mins of poking around.

scrypt is no joke.

[casascius]

I imagined there'd be some Litecoin fans who would be experts in knowing what kind of performance to expect on an optimized implementation of scrypt.  By "optimized", I mostly mean an implementation that isn't handicapped by being written in C#.  What I figured would crack this is maybe someone already has a good scrypt that could be compiled into a DLL and called from the C# environment so the better-performing code could be used without rewriting anything in another language.

Taking scrypt a little further, I was thinking it is almost time for a new proposal for a standardized way to do brainwallets in place of the common practice of using SHA256.

In a brainwallet proposal, I would propose that the user would be asked for their postal code and government ID number (however they interpret that) for use as salt, to generate or redeem a brainwallet.  Those two entries would be stripped of all but letters and numbers, forced to uppercase, and concatenated, simply so that the user has a maximum chance of remembering something that produces the same final result, without having to remember how they formatted it.  That personal data would be used as salt, run through scrypt, and then they could choose a strong passphrase without it having to be "to the moon" in length to be secure.

[hardcore-fs]

Well I'd started and my F***** RAID just crashed.

Ouch, hope you manage to get it back up and running.

If we look down we see:

byte[] checksum = sha256.ComputeHash(utf8.GetBytes(passphrase + "?"));

            if (hex[2] != 0x80) {
                if ((checksum[0] & 0x7f) != hex[2] || (checksum[1] & 0x7e) != (hex[3] & 0x7e)) {
                    return false;
                }
            }

It seems we can recover a partial solution, because if it is NOT a partial solution the above will fail.

This isn't it.  I have implemented multiple ways to encrypt keys, the contest key has a prefix of 6Pf and therefore uses the EC Multiply method I detail in BIP 38.  The code you're quoting here is from ShaPassphraseKeyPair.cs, which is for a simpler SHA256-based algorithm that doesn't use scrypt, and the code you've quoted doesn't ever get reached when you attempt to decrypt the note in the OP.  The class you want to be poking at is Bip38KeyPair.cs, specifically the portion that creates a Bip38Intermediate from the passphrase and tries to use it to decrypt the key.

The use of EC Multiply and the Bip38Intermediate code isn't what makes it slow, rather, these are responsible for a couple of features: 1 - it allows one person to know the passphrase and give away only an "intermediate code", and a second person to generate bitcoin addresses with it that only the first person's passphrase can spend (which I intend to use to offer two-factor physical bitcoins).  2 - it happens to allow one passphrase to be expensively hashed once and then used to create thousands of new bitcoin addresses, each with unique per-address salt but the same passphrase, very quickly.

By getting the products up-to this stage, popping them over the serial port to an fpga...... and since Bitcoin is DOUBLE sh256
We can get two engines cycling thrugh the Sha256 keys for the range AAAAA-zzzzz ( actually by splitting the space over two devices we can half the searchtime with a brute it becomes 190102016

The algorithm that needs to be accelerated to make this work is scrypt, rather than sha256, so the FPGA may not be of much use.

Yep my RAID crashed during reading the source... then it crashed during the rebuild
TIP #1 Synology kit is great until something goes wrong.

I thought perhaps it was a little too easy......, but I have seen far more stupid things done with "secure" fingerprint diskdrives.

As regards accelerating scryp, it is unlikely as it was specifically written to ensure it cannot be pipeline easily

[hardcore-fs]

Well I'd started and my F***** RAID just crashed.

Ouch, hope you manage to get it back up and running.

I think I have just found something slower than generating bitcoins... 4 hours later

[enquirer]

It would take 36 years to run on the slow C# crappy implementation of scrypt that I have bundled with my app.  Simply feeding the same input to a more efficient implementation should chop this figure down by orders of magnitude.

C# generates this code for the inner loop:

                    x4 ^= (x0 << 7) | (x12 >> (32 - 7));
000002bc  mov         eax,dword ptr [ebp-28h]
000002bf  shl         eax,7
000002c2  mov         edx,dword ptr [ebp-58h]
000002c5  shr         edx,19h
000002c8  or          eax,edx
000002ca  xor         dword ptr [ebp-38h],eax

I don't think C++ compiler would do any better

[casascius]

It would take 36 years to run on the slow C# crappy implementation of scrypt that I have bundled with my app.  Simply feeding the same input to a more efficient implementation should chop this figure down by orders of magnitude.

C# generates this code for the inner loop:

                    x4 ^= (x0 << 7) | (x12 >> (32 - 7));
000002bc  mov         eax,dword ptr [ebp-28h]
000002bf  shl         eax,7
000002c2  mov         edx,dword ptr [ebp-58h]
000002c5  shr         edx,19h
000002c8  or          eax,edx
000002ca  xor         dword ptr [ebp-38h],eax

I don't think C++ compiler would do any better

Is this really the bottleneck?  I'd have figured that there would be a performance penalty stemming from all the allocation of objects on the heap and have never dug into the inner workings of scrypt this far.  Although I have worked with assembly quite a bit, I have never done so in the context of C#, and have assumed that the JIT compiler does a pretty good job of being efficient at the instruction level other than incurring a ton of overhead moving in and out of objects it so cautiously allocates.

How did you arrive at the above?  If I try to look for the same piece of code in my app, I get this:

Code:

                    x[4] ^= R(x[0] + x[12], 7);
00000113  mov         eax,dword ptr [ebp+8] 
00000116  cmp         dword ptr [eax+4],4 
0000011a  ja          00000121 
0000011c  call        5A95AEC4 
00000121  lea         eax,[eax+18h] 
00000124  mov         dword ptr [ebp-54h],eax 
00000127  mov         eax,dword ptr [ebp-54h] 
0000012a  mov         eax,dword ptr [eax] 
0000012c  mov         dword ptr [ebp-58h],eax 
0000012f  mov         eax,dword ptr [ebp+8] 
00000132  cmp         dword ptr [eax+4],0 
00000136  ja          0000013D 
00000138  call        5A95AEC4 
0000013d  mov         ecx,dword ptr [eax+8] 
00000140  mov         eax,dword ptr [ebp+8] 
00000143  cmp         dword ptr [eax+4],0Ch 
00000147  ja          0000014E 
00000149  call        5A95AEC4 
0000014e  add         ecx,dword ptr [eax+38h] 
00000151  mov         edx,7 
00000156  call        FB56FE08 
0000015b  mov         dword ptr [ebp-5Ch],eax 
0000015e  mov         eax,dword ptr [ebp-58h] 
00000161  xor         eax,dword ptr [ebp-5Ch] 
00000164  mov         edx,dword ptr [ebp-54h] 
00000167  mov         dword ptr [edx],eax 

Looks to me like it's going about it a much longer way than what you've quoted.  Are we looking at the same implementation?  (the code you've quoted isn't even something I could find verbatim in the implementation I used).  All of these instructions look like they are accomplishing nothing more than checking that the array references are in bounds, and the code you're quoting doesn't reference an array.  In fact it is checking very redundantly in spite of obvious possible optimizations (e.g. checking to see that x[0] is a in bounds immediately after having verified that x[4] is).  And it doesn't unroll the call to R(), something I wouldn't have expected anyway.

EDIT: not surprisingly, I get substantially better performance compiling this as a "release" build and then not running it under the debugger, the scrypt operation taking closer to 1 second versus 3 seconds without changing a single line of code, even though the release build still shows all the wasteful bounds checks if I look at the disassembly.

[Remember remember the 5th of November]

Is this going to require a lot of code to implement in C? I can probably do it, but I really don't want to bother if it's going to be a lot of code.

[Vitalik Buterin]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

Tell me the first 4 bits and I'll get it in no time.  

That means if I don't tell you the first 4 bits, you'll get it in 16 * (no time).

But if you know some way where just 4 bits would give you more than a 16x advantage, please share!

Okay, I will.

Possibilities for ASCII code of first letter with no info: 65...90, 97...122 (52 possibilities, 2704 possibilities for first two letters)
Provide the following bits: ???11??? ???11???

This narrows down the possibilities for each letter to only six options: 01011000 01011001 01011010 01111000 01111001 01111010 (88,89,90,120,121,122 = X,Y,Z,x,y,z), so 36 possibilities for the first two letters. 2704/36 = 75.11x advantage.

[Evan]

Isnt there a  trick you can use prehashed tables to dot his in rapid fire?

somewhere i have a CD/DVD/USB with ever possible windows XP password hash  at the time that wintergen would spit out... made cracking brute-force a lot easier...

[prezbo]

Isnt there a  trick you can use prehashed tables to dot his in rapid fire?

somewhere i have a CD/DVD/USB with ever possible windows XP password hash  at the time that wintergen would spit out... made cracking brute-force a lot easier...

Check the BIP 38. It isn't quite that simple.

[Meni Rosenfeld]

By the way, this money is going to get taken one way or another, even if I have to start leaking bits of the password to speed up the process.

Tell me the first 4 bits and I'll get it in no time.  

That means if I don't tell you the first 4 bits, you'll get it in 16 * (no time).

But if you know some way where just 4 bits would give you more than a 16x advantage, please share!

Okay, I will.

Possibilities for ASCII code of first letter with no info: 65...90, 97...122 (52 possibilities, 2704 possibilities for first two letters)
Provide the following bits: ???11??? ???11???

This narrows down the possibilities for each letter to only six options: 01011000 01011001 01011010 01111000 01111001 01111010 (88,89,90,120,121,122 = X,Y,Z,x,y,z), so 36 possibilities for the first two letters. 2704/36 = 75.11x advantage.

Yes, if those are indeed the bit values at these places. If they are other values the advantage will be markedly less than x16.

In general, querying 4 bits can never cut down your search space to less than 1/16 on average.

(I'm guessing you already knew that, this is more a service to those confused about the "magic".)

[casascius]

By "giving bits" I mean giving information that cuts potential search space by half for each bit given, an information theoretical bit, not referring to ASCII. Like, saying whether a letter in a given spot is upper or lower case is to leak one bit.

[enquirer]

Is this really the bottleneck?  I'd have figured that there would be a performance penalty stemming from all the allocation of objects on the heap and have never dug into the inner workings of scrypt this far.  Although I have worked with assembly quite a bit, I have never done so in the context of C#, and have assumed that the JIT compiler does a pretty good job of being efficient at the instruction level other than incurring a ton of overhead moving in and out of objects it so cautiously allocates.

How did you arrive at the above?  If I try to look for the same piece of code in my app, I get this:

Looks to me like it's going about it a much longer way than what you've quoted.  Are we looking at the same implementation?  (the code you've quoted isn't even something I could find verbatim in the implementation I used).  All of these instructions look like they are accomplishing nothing more than checking that the array references are in bounds, and the code you're quoting doesn't reference an array.  In fact it is checking very redundantly in spite of obvious possible optimizations (e.g. checking to see that x[0] is a in bounds immediately after having verified that x[4] is).  And it doesn't unroll the call to R(), something I wouldn't have expected anyway.

EDIT: not surprisingly, I get substantially better performance compiling this as a "release" build and then not running it under the debugger, the scrypt operation taking closer to 1 second versus 3 seconds without changing a single line of code, even though the release build still shows all the wasteful bounds checks if I look at the disassembly.

You are right about the boundary checks. They can be avoided with unsafe pointers though. Also, C# doesn't do inlines well.
So I hand-optimized the inner loop:

Code:

                int i;
                uint x0 = input[0+ inputOffset];
                uint x1 = input[1 + inputOffset];
                uint x2 = input[2 + inputOffset]; 
                uint x3 = input[3 + inputOffset];
                uint x4 = input[4 + inputOffset];
                uint x5 = input[5 + inputOffset];
                uint x6 = input[6 + inputOffset];
                uint x7 = input[7 + inputOffset];
                uint x8 = input[8 + inputOffset];
                uint x9 = input[9 + inputOffset];
                uint x10 = input[10 + inputOffset];
                uint x11 = input[11 + inputOffset];
                uint x12 = input[12 + inputOffset];
                uint x13 = input[13 + inputOffset];
                uint x14 = input[14 + inputOffset];
                uint x15 = input[15 + inputOffset];

                for (i = rounds; i > 0; i -= 2)
                {

                    x4 ^= R(x0 + x12, 7); x8 ^= R(x4 + x0, 9);
                    x12 ^= R(x8 + x4, 13); x0 ^= R(x12 + x8, 18);
                    x9 ^= R(x5 + x1, 7); x13 ^= R(x9 + x5, 9);
                    x1 ^= R(x13 + x9, 13); x5 ^= R(x1 + x13, 18);
                    x14 ^= R(x10 + x6, 7); x2 ^= R(x14 + x10, 9);
                    x6 ^= R(x2 + x14, 13); x10 ^= R(x6 + x2, 18);
                    x3 ^= R(x15 + x11, 7); x7 ^= R(x3 + x15, 9);
                    x11 ^= R(x7 + x3, 13); x15 ^= R(x11 + x7, 18);
                    x1 ^= R(x0 + x3, 7); x2 ^= R(x1 + x0, 9);
                    x3 ^= R(x2 + x1, 13); x0 ^= R(x3 + x2, 18);
                    x6 ^= R(x5 + x4, 7); x7 ^= R(x6 + x5, 9);
                    x4 ^= R(x7 + x6, 13); x5 ^= R(x4 + x7, 18);
                    x11 ^= R(x10 + x9, 7); x8 ^= R(x11 + x10, 9);
                    x9 ^= R(x8 + x11, 13); x10 ^= R(x9 + x8, 18);
                    x12 ^= R(x15 + x14, 7); x13 ^= R(x12 + x15, 9);
                    x14 ^= R(x13 + x12, 13); x15 ^= R(x14 + x13, 18);
                }
                output[0 + outputOffset] = x0 + input[0 + inputOffset];
                output[1 + outputOffset] = x1 + input[1 + inputOffset];
                output[2 + outputOffset] = x2 + input[2 + inputOffset];
                output[3 + outputOffset] = x3 + input[3 + inputOffset];
                output[4 + outputOffset] = x4 + input[4 + inputOffset];
                output[5 + outputOffset] = x5 + input[5 + inputOffset];
                output[6 + outputOffset] = x6 + input[6 + inputOffset];
                output[7 + outputOffset] = x7 + input[7 + inputOffset];
                output[8 + outputOffset] = x8 + input[8 + inputOffset];
                output[9 + outputOffset] = x9 + input[9 + inputOffset];
                output[10 + outputOffset] = x10 + input[10 + inputOffset];
                output[11 + outputOffset] = x11 + input[11 + inputOffset];
                output[12 + outputOffset] = x12 + input[12 + inputOffset];
                output[13 + outputOffset] = x13 + input[13 + inputOffset];
                output[14 + outputOffset] = x14 + input[14 + inputOffset];
                output[15 + outputOffset] = x15 + input[15 + inputOffset];

EDIT: Oops, got it wrong the first time, corrected. Inlining doesn't get you much. Still, x2 faster than original implementation.

[DeathAndTaxes]

The belief that C# (and Java) is god awful slow is simply an urban legend.  Maybe that was true in .NET 0.9b but it hasn't been true for a while now.  

Obviously it is impossible to boil down an entire language (and all compiler implementations, and all possible source codes, and all possible implementation skills down to a single number however)....
http://shootout.alioth.debian.org/u32/which-programs-are-fastest.php

Code:

C++ (g++)                      1.00
C (gcc)                        1.16
Java (Java7)                   1.59
C# (mono)                      2.20
Javascript (chrome V8)         3.04

Execution time's normalized to 1.00 for C++ execution time.   Sure Java, C#, and Javascript are slower but they aren't magnitudes slower and to cut a 36 year brute force search down to say 1 month you are talking about needing MORE than 2 magnitudes in performance increase. 

JIT compilers have come a long way.   C++ compilers have also come along way too.  C++ essnetially adds no overhead to writing native C.  Remember there is a skill factor to consider.  Compilers essentially are a skill normalizer.  Maybe one person in twenty can write better C code than a C++ compiler but then again if that person contributed to C++ compiler enhancement that knowledge is then shared.   




scrypt was simply intended to be very slow.  Even if the C# implementation is poorly written (or compiled) it is unlikely one can expect to gain 100x increase in performance by just switching languages.  There is a reason why fastcash4bitcoins uses bcrypt.  bcrypt is a similar algorithm.  scrypt is even more memory hard however we still use bcrypt simply because it has been around longer.  Anyone taking simple SHA hash of a password is just making the job of an attacker a couple MILLION times easier (no not an exaggeration).

There are two possible vulnerabilities:
a) dictionary attacks (to include dictionary substitution attacks), weak password is still weak even with scrypt. 
b) precomputation attacks (if the algorithm doesn't have some salt value then given enough time a group of hackers could build a distributed database of ALL 1,2,3,4,5,6,7,8,9,10... char passwords).

[Evan]

Isnt there a  trick you can use prehashed tables to dot his in rapid fire?

somewhere i have a CD/DVD/USB with ever possible windows XP password hash  at the time that wintergen would spit out... made cracking brute-force a lot easier...

Check the BIP 38. It isn't quite that simple.

Let me fire up the CRAY..... Wow well so I am looking at a 1TB+ of data for hash tables


Also the Password is Steal

[Raoul Duke]

Also the Password is Steal

LMAO

Mike has a sense of humour.
Too bad this test only showed that people and their predictable way of thinking are security biggest enemy.

[chriswilmer]

Stupid question, but is the encryption/decryption function the exact same one that is used when I open the binary you provided and click on "tools --> address utility" and then type in an "encryption phrase" ?

i.e., in principle, could one steal the BTC from the wallet you provided by trying every AAAAA through zzzzz combination into that box and clicking on "generate"?

[Raoul Duke]

Stupid question, but is the encryption/decryption function the exact same one that is used when I open the binary you provided and click on "tools --> address utility" and then type in an "encryption phrase" ?

i.e., in principle, could one steal the BTC from the wallet you provided by trying every AAAAA through zzzzz combination into that box and clicking on "generate"?

Yes, that's it.
If you wanted to try that 380204032 times.
The dude cracked it by thinking like Mike

[Meni Rosenfeld]

The dude cracked it by thinking like Mike

Presumably it was a joke, the password is neither Steal, STEAL nor steal. And as you can see, the coins are still unclaimed.

[niooron]

 

Code:

if (txtPassphrase.Text != "") {     
                    SetText(txtPrivWIF, new Bip38KeyPair(kp, txtPassphrase.Text).EncryptedPrivateKey); //<-loop this?
                } else {
                    SetText(txtPrivWIF, kp.PrivateKeyBase58);
                }
                SetText(txtPrivHex, kp.PrivateKeyHex);
                SetText(txtPubHex, kp.PublicKeyHex);
                SetText(txtPubHash, kp.Hash160Hex);
                SetText(txtBtcAddr, new Address(kp, AddressTypeByte).AddressBase58);       

I don't understand very much, but we have to search for all combinations looping this piece of code?
How can we arrive at the public key if random keys get encrypted with the password?      

[Meni Rosenfeld]

Code:

if (txtPassphrase.Text != "") {     
                    SetText(txtPrivWIF, new Bip38KeyPair(kp, txtPassphrase.Text).EncryptedPrivateKey); //<-loop this?
                } else {
                    SetText(txtPrivWIF, kp.PrivateKeyBase58);
                }
                SetText(txtPrivHex, kp.PrivateKeyHex);
                SetText(txtPubHex, kp.PublicKeyHex);
                SetText(txtPubHash, kp.Hash160Hex);
                SetText(txtBtcAddr, new Address(kp, AddressTypeByte).AddressBase58);       

I don't understand very much, but we have to search for all combinations looping this piece of code?
How can we arrive at the public key if random keys get encrypted with the password?      

No, this code generates new keypairs unrelated to the one in the note. You want to loop the code in btnPrivWIFToHex_Click (in Form1.cs), with the encrypted key for txtPrivWIF.Text and different password values for txtPassphrase.Text.

[Raoul Duke]

Then Mike has a bug on his software, because Steal did decrypt the private key to a valid one, allebeit a different address.
Let me go to laptop and I'll tell you to which address lol

EDIT: This is strange, but now it says The Passphrase is Incorrect.
But it did give me a valid Private Key and Address, because I've even imported it to my MtGox account.
No, I didn't save it, so I can't say which address or privatekey it was and there's no way on MtGox to see it.
Maybe a glitch from running Mike's tool on Ubuntu. Or a glicth on my fingers and I clicked the wrong button?

[casascius]

Then Mike has a bug on his software, because Steal did decrypt the private key to a valid one, allebeit a different address.
Let me go to laptop and I'll tell you to which address lol

EDIT: This is strange, but now it says The Passphrase is Incorrect.
But it did give me a valid Private Key and Address, because I've even imported it to my MtGox account.
No, I didn't save it, so I can't say which address or privatekey it was and there's no way on MtGox to see it.
Maybe a glitch from running Mike's tool on Ubuntu. Or a glicth on my fingers and I clicked the wrong button?

To me, most likely scenario is you clicked the button to generate a brand new key, and imported it.

Of course it will import, and it will have no money on it.

Successful decryption of the private key means coming up with a private key that evaluates to the same address on the original note.

[casascius]

I will give away the capitalization of the letters of the password sometime between 0:00 UTC and 2:00 UTC December 3, 2012 (that's tonight my local time between 5-7pm Mountain US).  More likely toward the beginning of the time window (I am just giving myself room to be late just in case I'm like driving or something).

I will also give this right now: the capitalization is NOT "aaaaa", nor "Aaaaa", nor "AAAAA".

I will give away one more "bonus bit" of information right now: the first letter falls within the second half of the alphabet (N-Z or n-z).

[adamstgBit]

Is this going to require a lot of code to implement in C? I can probably do it, but I really don't want to bother if it's going to be a lot of code.

ya its not trivial, a days work to rewrite it in C, only to find out it would take 18years

I think Mike will need to give hints

but lets just wait and see.

[Shermo]

My implementation would ONLY take 125 days to attempt all combinations, much faster than the 36 years... but still not doable for the amount of BTC!

[casascius]

Is this going to require a lot of code to implement in C? I can probably do it, but I really don't want to bother if it's going to be a lot of code.

ya its not trivial, a days work to rewrite it in C, only to find out it would take 18years

I think Mike will need to give hints

but lets just wait and see.

Keep in mind that "36 years" became "12 years" just by taking the same code and running it in "release" mode instead of "debug" mode, without making a single change.  (3 seconds per try became 1 second per try)

Unrolling the loop as suggested by Enquirer should make a pretty decent dent

And when I give away the capitalization, 12 years gets chopped by a factor of 32 to under 4.5 months, assuming no code changes (not even the loop unroll).

At some point I'll have given enough bits away that some enterprising person discovers they can throw the problem at some Amazon compute time for five bucks and solve it.

In the end, I think we'll all draw the conclusion that if you print yourself a bunch of 1 BTC notes while keeping a backup copy at home, and put even a simple password on them ("foofoo"), usability is hardly impacted (assuming redeeming them is ubiquitous), but you are pretty much totally protected if the things get lost or stolen.

Meanwhile, I "owe" BTC to a few people (really, what this means is I told them about bitcoins and they asked me to buy some and hold them for them...mostly friends and family).  Passworded paper wallets mean that I can give or mail them their own bitcoins without asking their permission or putting them at a risk of theft, then tell them the password, which I will have chosen as something I know is memorable to them but hard to guess.  I keep a copy of the notes somewhere safe, and the end result: they have the option of spending their money like money at some point in the future without needing to ask me for it, and they can stop thinking of it like a stock.  Meanwhile, I still retain the ability to act on their bitcoins if they need me to, but can also forget that I "owe" them anything.

[Meni Rosenfeld]

My implementation would ONLY take 125 days to attempt all combinations, much faster than the 36 years... but still not doable for the amount of BTC!

Well Mike has already given 1.142 bits of information and will give 4.858 more soon, this already cuts your runtime to 2 days. Go for it.

[casascius]

My implementation would ONLY take 125 days to attempt all combinations, much faster than the 36 years... but still not doable for the amount of BTC!

I am guessing that'll be divided by 32 in a matter of hours, or is this already factored in to your calculation?

The difficulty keeps going down the more I divulge about the password, so the person who has built the most effective cracking solution (and/or gets the luckiest) when I give just enough information to put it within reach will claim it.

[Come-from-Beyond]

I bet the password is "Coinz" but too lazy to check it. 

[Vorksholk]

Yeah, it also decrypts with CaSaS, but to the wrong Address.

[Shermo]

Down to about 21 days now with the hints given and a few tweaks....

[casascius]

Yeah, it also decrypts with CaSaS, but to the wrong Address.

I don't think so.  I tried it and it didn't work.  But if it did, it would be an INCREDIBLE coincidence, given that the "passphrase incorrect" message comes from a mismatch of a 32-bit hash.  Odds of a collision on any given string are 4 billion to 1.

[Elxiliath]

That's funny given those odds compared to the odds of guessing the correct phrase.

[Shermo]

Unrolled a few loops, down to 18 days...

[Vorksholk]

Yeah, it also decrypts with CaSaS, but to the wrong Address.

I don't think so.  I tried it and it didn't work.  But if it did, it would be an INCREDIBLE coincidence, given that the "passphrase incorrect" message comes from a mismatch of a 32-bit hash.  Odds of a collision on any given string are 4 billion to 1.

Ahh, your right, tried it again. Must have hit the up key instead of the down xD

[andrew12]

It would take 36 years to run on the slow C# crappy implementation of scrypt that I have bundled with my app.  Simply feeding the same input to a more efficient implementation should chop this figure down by orders of magnitude.

This pretty much sums up why I'm not motivated to try to find the password.

[picobit]

Found a scrypt implementation for Python written in C, so it should be pretty fast.  100 attempts in 52 sec on my Mac.  Still, that will take 44 days if I had 52 CPUs to run on.  Giving that I still have to implement all the rest of the BIP key decryption in Python (I planned to steal most of it from Armory), I doubt that I will be first to collect the price (and I don't have 52 CPUs to spare).  So I pass.  But it was fun to looking into this.

[kokojie]

Found a scrypt implementation for Python written in C, so it should be pretty fast.  100 attempts in 52 sec on my Mac.  Still, that will take 44 days if I had 52 CPUs to run on.  Giving that I still have to implement all the rest of the BIP key decryption in Python (I planned to steal most of it from Armory), I doubt that I will be first to collect the price (and I don't have 52 CPUs to spare).  So I pass.  But it was fun to looking into this.

Yeah that's still pretty slow, though once casascius reveals more information, your script may be the fastest.

[kokojie]

scrypt sounds like a great encryption algorithm, even 5 letter passwords take so long to crack. Why isn't this in wide spread use for password encryption?

[Come-from-Beyond]

scrypt sounds like a great encryption algorithm, even 5 letter passwords take so long to crack. Why isn't this in wide spread use for password encryption?

It wasn't analyzed so intensively like, say, SHA-256.

[Evan]

Found a scrypt implementation for Python written in C, so it should be pretty fast.  100 attempts in 52 sec on my Mac.  Still, that will take 44 days if I had 52 CPUs to run on.  Giving that I still have to implement all the rest of the BIP key decryption in Python (I planned to steal most of it from Armory), I doubt that I will be first to collect the price (and I don't have 52 CPUs to spare).  So I pass.  But it was fun to looking into this.

I don't have 52 CPUS to crack with but I do have a Server with two E7-8850 so thats 40 CPUs for you.

Also if you could force this to run via a Nvidia Cuda set up  I am sure the 1536+ cores my GPU have could crack that in a few rounds

[casascius]

The capitalization pattern is: AaAaA

[Elxiliath]

Now to figure out what it could be.    I love this app by the way, saves me using photoshop to manually put in all these QR codes when I generate bills.

[Chloride]

I don't know if it helps anyone, but I wrote a quick java program to generate a list dictionary file (plain .txt format) of all possible passwords in the format "AaAaA".

If someone wants to try using it, I'll be happy to give it to them in return for 1 or 2 btc if you managed to crack it.

[Trader Steve]

So who is sending micro-payments to the address? Are these clues from Mike?

[enquirer]

I can only tell you that Amazon Extra-Large High-CPU instances are a rip off!
Not faster than a $500 home computer.
And that password is not in a dictionary.

[Chloride]

I can only tell you that Amazon Extra-Large High-CPU instances are a rip off!
Not faster than a $500 home computer.
And that password is not in a dictionary.

He has stated that the password is 5 letters long, in the format of "AaAaA".
I simply generated a textfile containing every combination of letters in the format, it amounts to ~90mb in a .txt file.
Not so much a dictionary as a list of all possible results.

[runlinux]

im getting about 2 results a second on my 4.5GHz 3960X. We'll how it fairs in the morning. for some reason, its only using 50% of the CPU... time to dig into some code

[Raize]

Mike, I'm interested in more what you're doing with these paper wallets. Is the idea to let us print our own paper currency for exchange between friends and family without having to even own a client?

[casascius]

So who is sending micro-payments to the address? Are these clues from Mike?

I'm not sending the micro-payments.  Amusing though.

[HotDiggityDawg]

So who is sending micro-payments to the address? Are these clues from Mike?

I'm not sending the micro-payments.  Amusing though.

Well damn, and I thought I was onto something!

[casascius]

Mike, I'm interested in more what you're doing with these paper wallets. Is the idea to let us print our own paper currency for exchange between friends and family without having to even own a client?

Yeah, that's one typical use case... there are many others, and quite honestly I expect that there will be many use cases I haven't thought of, that somebody else will.

The password aspect makes it useful for much bigger amounts.  "Here Abby, here's the 165 BTC you bought from me when they were $6 that I've been holding all this time for you.  Now there is a new way I can just give it to you as bills, just in case you'd like to spend a couple of them on the internet without having to ask me for them, since they're money after all.  There are ten BTC10 bills and thirteen BTC5's.  The password is (some phrase based on an inside joke).  Don't worry if you lose these, because as long as you don't lose the password with them, I can always bail you out for whatever you haven't spent, since I made a copy and will remember the password too."  (then shove my copy of her bills in a safe deposit box and then I can stop mentally subtracting her BTC from my own wallet balance as a liability, or worrying I'll ever lose track or ability to give her her money)

[hardcore-fs]

So who is sending micro-payments to the address? Are these clues from Mike?

I'm not sending the micro-payments.  Amusing though.

Well damn, and I thought I was onto something!

LOL, if you dug a little deeper you would be.

[Shermo]

My implementation is down to 30hours with the new information... do-able now

[Shermo]

Crap I just realised I've been reading my time estimates wrong / outputting them not how I thought... actually, I'm at 30 DAYS not hours... bah!

[casascius]

Crap I just realised I've been reading my time estimates wrong / outputting them not how I thought... actually, I'm at 30 DAYS not hours... bah!

I anticipate offering another difficulty drop soon.  But will post a time before providing one of major value.

[Come-from-Beyond]

OMG. Is there any REAL hacker?

[Shermo]

It's not really hacking, its purely brute force thats necessary... you can improve some of the algorithm for speed but aside from that there are about 5 million combinations to try and my system is doing about 2 attempts per second that's still roughly 2500000 seconds, approx 30 days.

[SurReality89]

pretty sure there is exactly 9,765,625 (26^5) possibilities. so more like double 5mil. so the longest it would take is 56.5 days (if you were to guess in alphabetical order and the password turned out being ZzZzZ)

[Shermo]

Given the information that has been released there are exactly 5940688 combinations to try...

[paybitcoin]

Yes, for the parameters of this contest, it is much easier/less time/cheaper to brute force it than investigate weaknesses in any of the elliptic curve math, scrypt, AES, or SHA256.

Right now I have ported BIP 38 to C and threaded it, and it is running on an Amazon EC2 instance at about 10-12 attempts / sec. I am using the standard scrypt library and jgarzik's new libccoin and a clean slate implementation of the BIP. So that's still about 12 days of CPU crunching... At the very least, there should be a (super hacked together, ugly code) version of the BIP in C!

Also, there is still only information enough to get it down to 26 ^ 5 = 11,881,376. Right? Just that the capitalization is AaAaA?

[wachtwoord]

The first letter is N-Z

[paybitcoin]

The first letter is N-Z

Good to know!!!

[picobit]

The first letter is N-Z

Are you just teasing us, or did casascius tell you?

 

[Shermo]

casascius said it a few pages back

[picobit]

Sure, he did.  I am sleeping.  I thought this was the new info he promised.  Sorry, wachtwoord!

[Phinnaeus Gage]

RoBoT (If it works, I desire a 50/50 split)

~Bruno K~

[CIYAM]

Maybe one of the following (got bored after the letter S sorry)?

NeRdY
NiCeR
NiChE
NiFtY
NiNjA
NiMdA
NoIsE
NoTeD
NoVeL
NuKeD
NuTtY
OdDeR
OdDlY
OmEgA
OuTeD
OvErT
PaNdA
PaNiC
PaRsE
PaStE
PaStY
PaYeD
PaYeR
PeAlS
PeEvE
PeRkS
PhOnY
PiCkY
PiNgS
PiVoT
PiXeL
PoStS
PrIcY
PrOoF
PrOmO
QuErY
QuEsT
QuOtA
QuOtE
RaCeR
RaCeS
RaDiI
RaDiO
RaDiX
RaLlY
RaPiD
ReIgN
ReLaX
ReLaY
ReLiC
RePaY
RePlY
RoGuE
RoOkY
RoSeS
RuBlE
RuLeR
RuSeS
SaLeS
SaVeD
SaVeR
SaVeS
ScAmS
ScArY
SeAlS
SeEdS
SeEkS
SeIzE
SeNsE
ShAdY
ShAkY
ShArK
ShInY
ShOwN
ShOwY
SiGnS
SkInT
SlEeK
SlEeP
SlOwS
SlYeR
SmOkE
SnAiL
SnAkY
SnArE
SnOrE
SoLvE
SpAcE
SpAcY
SpOiL
SpOoF
StAkE
StArS
StArT
StAsH
StEaL
StUdY
SwEaT

[casascius]

I'll disclose the first character of the password at or shortly after 20:00 UTC.

[nevafuse]

I'll disclose the first character of the password at or shortly after 20:00 UTC.

Don't do that.  You've already given away too much information.  I'm genuinely interested in how long it would take someone to realisticly crack a 5 character brainwallet generated private key.  Start a new thread with less characters if you want more action.  That way we can all see how long it takes for different character lengths.  This is definitely a neat experiment to either strengthen or weaken people's piece of mind on using brainwallet.

[casascius]

I will avoid disclosing the first character if I am presented with credible evidence that someone is highly likely to crack it within the next 48 hours without the help.  PM if needed.  I don't want it to be a 2-week contest where everyone gives up because they're bored.

[CIYAM]

One last crack at the 5 letter words after S:

TaKeR
TaKeS
TaLeS
TaLkS
TaRdY
TaSkS
TaStE
TaStY
TaXeD
TaXeS
TeAmS
TeArS
TeArY
TeAsE
TeChS
TeChY
TeLlS
TeMpT
TeNtH
TeNtS
TeStS
TeStY
ThEfT
ThEiR
ThEmE
ThErE
ThEsE
ThIcK
ThIeF
ThInG
ThOsE
ThRoW
ThUmB
TiGeR
TiGhT
TiMeD
TiMeR
TiMiD
TiNnY
ToAsT
ToDaY
ToIlS
ToKeN
ToNaL
ToOlS
ToPiC
ToRsE
ToTaL
ToWeL
ToXiC
TrApS
TrAsH
TrEnD
TrIaL
TrIcK
TrIeD
TrIeS
TrIpE
TrItE
TrOlL
TrOvE
TrUeR
TrUlY
TuNeD
TwEaK
TwIsT
UlTrA
UnDeR
UnDiD
UnDuE
UnFiT
UnTiL
UnZiP
UrGeD
UrGeR
UrGeS
UrInE
UsAgE
UsErS
UsHeR
UsInG
UsUaL
UsUrP
UsUrY
VaLuE
VaLvE
VaPoR
VaUlT
VeNoM
ViDeO
ViNeS
ViNyL
ViRaL
ViSiT
ViViD
VoDkA
VoIcE
VoIlA
VoLtS
VoTeD
VoTeR
VoTeS
VoUcH
WaCkY
WaGeD
WaGeS
WaGeR
WaIvE
WaNnA
WaNtS
WaRtS
WaStE
WeArY
WeAvE
WeEpS
WeIrD
WhAcK
WhAmS
WhEeL
WhErE
WhIcH
WhIlE
WhImS
WhIsK
WhOlE
WiDeR
WiElD
WiNeS
WiNkS
WiReD
WiTcH
WiZeN
WoRdS
WoRdY
WoRkS
WoRmY
WoRrY
WoRsE
WoRsT
WoUlD
WrAtH
WrEaK
WrEcK
WrEsT
WrItE
WrOtE
YaChT
YaCkS
YaKkA
YaRdS
YaRnS
YaWnS
YeArN
YeLlS
YeSeD
YiElD
YiKeS
YiPeS
YoUrS
YoUtH
ZeBrA
ZeRoS
ZeStY
ZoMbI
ZoNeD
ZoNeS
ZoNkS
ZoOmS

[casascius]

The correct password isn't a recognizable word.  It's essentially five random letters.

[CIYAM]

So I guess the dictionary hackers should reverse their algos (i.e. do not try anything that is in a word dictionary).




BTW - this has been a very interesting experiment and quite a valuable lesson about the value of scrypt.

[casascius]

So I guess the dictionary hackers should reverse their algos (i.e. do not try anything that is in a word dictionary).

Or at least try all the dictionary entries last... pretty safe bet.  This might give a couple percent speedup.  The password isn't "maybe not a word": it's more like "totally not a word".  I am pretty sure it won't accidentally appear in a dictionary.

If I google the password, I get no meaningful results, just websites dedicated to listing every possible 5-character combination.

[CIYAM]

Actually I've always wondered how good an encryption algo that I wrote years ago actually is (only went as far as verifying that no zip type software could shrink an encrypted file) and now this has given me an idea about how to test that (i.e. encrypt a Bitcoin private key with my algo and publish it for all to try).

[casascius]

Having the output of an encryptor be poorly compressible is a common property of pretty much all encryptors, good or bad.  It is not a useful indicator of strength (although the opposite is true: if the output is compressible by anything more than a token percentage point or two, due to compressibility of non-encrypted metadata or slack space in the file, it's pretty much a given that the encryption should be easy to crack, and probably isn't "encryption" in the first place).

[CIYAM]

Point well taken - so let's say I wanted to do this (if this is getting too OT I'll leave it at this) - how much BTC would motivate someone to crack it if I

(a) just put an encrypted private key with no source code for the encryption
(b) pasted the encrypted private key along with the encryption source code

Would probably consider a private key that has around 100 BTC balance if there are any takers (for option (a) and maybe at least 10 BTC for option (b)).

[scribe]

So I guess the dictionary hackers should reverse their algos (i.e. do not try anything that is in a word dictionary).

Or at least try all the dictionary entries last... pretty safe bet.  This might give a couple percent speedup.  The password isn't "maybe not a word": it's more like "totally not a word".  I am pretty sure it won't accidentally appear in a dictionary.

If I google the password, I get no meaningful results, just websites dedicated to listing every possible 5-character combination.

So all we need to do is hack your google account and check the search history? Sounds easier, anyway...

Also for reference, it's not "VfHkP".

Also less likely to be a string based on keyboard layout (such as ZaQwE. Which it's not.).

[SgtSpike]

So how are people automatically checking password combinations?  2 results per second and whatnot?  Have you each written/modified code on your own for this?

[runlinux]

I modified the code with 5 nested loops.

I place the current combo in the text box, then have it check the value. On the chance it comes back a match, I exit the loops and continue on with the code to display the private / public key.

[Shermo]

I just wrote a little console application that makes use of the classes, easier to debug that way no faffing with all the other code. Added a few statistics and output every 100 combinations so I have an idea of how its doing... its still too slow to consider actually running though.

[wachtwoord]

I'll disclose the first character of the password at or shortly after 20:00 UTC.

Don't do that.  You've already given away too much information.  I'm genuinely interested in how long it would take someone to realisticly crack a 5 character brainwallet generated private key.  Start a new thread with less characters if you want more action.  That way we can all see how long it takes for different character lengths.  This is definitely a neat experiment to either strengthen or weaken people's piece of mind on using brainwallet.

Even with that info it will take my computer a fortnight to try all possibilities

[wtfvanity]

Who would like the snippet code to run the loop? Let's break the key space up and share the prize haha. Or maybe I can sell the snippet. I'll let you chose which range in which spot and you can try luck of the draw and see if you can pick the right key space. First letter given should finish the race in a few hours. I'll take it if you're still handing it out at 20:00 UTC

[SgtSpike]

Who would like the snippet code to run the loop? Let's break the key space up and share the prize haha. Or maybe I can sell the snippet. I'll let you chose which range in which spot and you can try luck of the draw and see if you can pick the right key space. First letter given should finish the race in a few hours. I'll take it if you're still handing it out at 20:00 UTC

If you give me the code, I'll run it and share half the prize with you if I find it.

[andrew12]

If you give me the code, I'll run it and share half the prize with you if I find it.

Why should he believe you? What if I said that if I was given the code, and I found it, I'd give him 2/3 of the prize? Why should he believe me?

[wtfvanity]

What if I compile the exe and have it email me the result and I split it with you?

[pc]

I have been wondering if there's some way to pool this in a verifiable manner, where work gets sent out kind of like a mining pool, and something like I assume P2Pool does where everybody's verifying that the payment transaction they're working on is "fair" and sending the reward to those participating. I'm not sure how it'd be possible to let somebody know when they'd decrypted the key without them having the key to be able to claim the whole amount themselves, though.

[maaku]

If you give me the code, I'll run it and share half the prize with you if I find it.

Why should he believe you? What if I said that if I was given the code, and I found it, I'd give him 2/3 of the prize? Why should he believe me?

SgtSpike has a long-time presence here, 5452 posts to his name, and a reputation that is probably worth more than 5 btc. You do not.

If I google the password, I get no meaningful results, just websites dedicated to listing every possible 5-character combination.

If only I worked at Google search, I could look for 5-letter random sequences searched in the last few days. Easier if I knew your IP

[cheesemunger]

According to my calculations, once the new info is released I should be able to get it within 5 hours
If I were you, I wouldn't trust anyone to share after. There are way too many scammers around

[wachtwoord]

Who would like the snippet code to run the loop? Let's break the key space up and share the prize haha. Or maybe I can sell the snippet. I'll let you chose which range in which spot and you can try luck of the draw and see if you can pick the right key space. First letter given should finish the race in a few hours. I'll take it if you're still handing it out at 20:00 UTC

If you give me the code, I'll run it and share half the prize with you if I find it.

I'll agree to that deal if you are interested. Want the code or a compiled exe? (and we'll wait for the starting letter to be revealed right?

[Dansker]

I bet the ones that are most likely to win are not even posting in the thread, just waiting to break the code and claim the prize.

[casascius]

I am persuaded that the key will be cracked soon (a few days at the most, but possibly much sooner) without me needing to divulge the first character.  If that's true, then me giving away a character would cut that to a guaranteed crack in hours at most.  There are skilled lurkers on this thread who aren't posting, but they're cracking away.

Pooling and agreeing to share the reward is totally a good idea I'd recommend, and totally acceptable to me (not that I have any say once the money gets taken).  It is no different than pooled mining, other than perhaps without the benefit of having any way to keep anybody honest.

[SgtSpike]

Who would like the snippet code to run the loop? Let's break the key space up and share the prize haha. Or maybe I can sell the snippet. I'll let you chose which range in which spot and you can try luck of the draw and see if you can pick the right key space. First letter given should finish the race in a few hours. I'll take it if you're still handing it out at 20:00 UTC

If you give me the code, I'll run it and share half the prize with you if I find it.

I'll agree to that deal if you are interested. Want the code or a compiled exe? (and we'll wait for the starting letter to be revealed right?

Compiled exe would be great - I've tried compiling things in C before and it just doesn't go well.  I'd rather not go through it again if I can avoid it.

And yes, to anyone who questions whether I would share the prize as I have said I would, I'm not selling out my reputation here (and a multitude of other online presences, since I use this screen name almost exclusively) ever, for any dollar amount.  Keeping my integrity intact and a clear conscience is worth far more than anything money could buy.

I'll start whenever I can (whenever you send me the exe), but certainly, having the starting letter would help expedite the process of finding it.

[wtfvanity]

I'm picking one starting letter and trying my luck. 1 in 13 chance I picked the right first letter. If it's not claimed by the time I finish I'll guess another one.

[tacotime]

if you're aiming for high security for the key, you should uses a high r value (4096, 8192) for salsa20/chacha20 and skein for the block cipher as they're both really slow and expensive.  there's only a tiny amount of data to be decrypted here, and even a 5 character password that is random should be a nightmare to solve.

[CoinDiver]

Who would like the snippet code to run the loop? Let's break the key space up and share the prize haha. Or maybe I can sell the snippet. I'll let you chose which range in which spot and you can try luck of the draw and see if you can pick the right key space. First letter given should finish the race in a few hours. I'll take it if you're still handing it out at 20:00 UTC

If you give me the code, I'll run it and share half the prize with you if I find it.

I'll agree to that deal if you are interested. Want the code or a compiled exe? (and we'll wait for the starting letter to be revealed right?

I'll help. I've got a few fast servers I can let crank away it.

[casascius]

if you're aiming for high security for the key, you should uses a high r value (4096, 8192) for salsa20/chacha20 and skein for the block cipher as they're both really slow and expensive.  there's only a tiny amount of data to be decrypted here, and even a 5 character password that is random should be a nightmare to solve.

I don't want it too slow: I want it to be possible to implement in javascript so that somebody could use it to decrypt a key when they know the correct password.  It doesn't have to be convenient, making them wait between 0-60 seconds is totally acceptable.  If this weren't possible, server implementers would be afraid to enable the algorithm, fearing it's a resource-consumption DoS vector.  Allowing server operators to offload this work to the client browser would allow them to offer the redemption of password protected private keys without having to burden their server at all (the client browser would just decrypt it and submit a non-protected key).

[tacotime]

n=1024, r=8192, and p=1 should be a second or too in C, probably a little longer in js (200-300%).

c implementations are here: https://github.com/floodyberry/scrypt-jane

i posted a lot of results in this thread: https://bitcointalk.org/index.php?topic=122256.0

[casascius]

n=1024, r=8192, and p=1 should be a second or too in C, probably a little longer in js (200-300%).

c implementations are here: https://github.com/floodyberry/scrypt-jane

i posted a lot of results in this thread: https://bitcointalk.org/index.php?topic=122256.0

I'm listening, but am afraid I am less familiar with these algorithms than I ought to be for proposing a BIP that uses them.  (That's part of why I've listed the parameters as "preliminary").

Regardless, there's an organizational cost to be incurred to change the parameters, however slight.

It is not clear to me why I should want to bump up r and bump down n, when ultimately it's going to take roughly the same amount of time and memory to run, at least measured in orders of magnitude.  Can you help me understand?

In this application, significantly increasing or decreasing the runtime isn't something I see as very desirable - I think I've picked the sweet spot in terms of balance.  However, one thing I would consider desirable is minimizing the disparity between the amount of time it takes to run in a typical javascript environment (it inconveniences the user) versus what a cracker could achieve (since he's going straight for the speed).  A solution that makes the user's javascript decryption take only 1000 times as long as the cracker's would be better than one where the cracker's crack was more millions of times faster, assuming each is using a single desktop pc and ignoring the fact that any serious cracker would distribute the workload over many machines.  If changing the parameters were to significantly lessen the amount that this could diverge over time, then I'd see that as a valuable improvement.

[tacotime]

N enhances memory consumption with computational enhancement while r simply enhances memory consumption.  You further slow your algorithm down with N as compared to R.  It's really a matter of preference when you get to very large memory consumption (>1 MB), because at that point you're using RAM and you're going to see a severe slowdown.  Additionally, chacha20 should generally be used in place of salsa20 because it's faster and considered exactly as secure.

N becomes a much bigger deal (as far as I can tell) if you use multiple block cipher hash functions because you will be doing many more of these block cipher hashes.  if you are using a lot of block cipher hash algorithms (see below) increasing r would be ideal because you may then actually face significant slowdown.  see theorem 1 for ROMixH computational time from the scrypt paper.

skein is secure, the reason it wasn't considered for SHA3 was because it's really computationally intensive.  the same goes for blake.  sha3 (keccak) has extremely high throughput as compared to either of those algorithms (or SHA256, which is similarly slow), hence its selection as sha3.

if you want something that is a total pain in the ass to crack on a parallel machine (asic, gpu) a high N or r value (resulting in 16-256 MB of memory use) and skein/blake for the block cipher will suffice.  the more block ciphers you add in tandem (eg SHA256(BLAKE512(SKEIN(data, key))) the worse it gets for asic hashing without strongly affecting runtime performance because need an additional 20,000-50,000 circuits per hash algorithm.  but as most of your slowdown is in memory with high N or r values, you can really add as many secondary block ciphers as you like without it making the algorithm a lot slower.

basically all the SHA3 final candidates are reasonably good algorithms, just keccak was the only one that had a ridiculously fast throughput as compared to SHA256.  but in this case speed isn't all that important because the size of the data is so small.

the major advantage to using daisy chained block ciphers in scrypt is also that in the event one block cipher is determined insecure, you still have the others as a failsafe.  the minor advantage is increased asic difficulty.

if you're interested on working on an implementation like this let me know, i would like to make a block chain based on an algorithm such as this along with some other protocol tweaks for economics.

[casascius]

http://blockchain.info/tx/eb758c500d5fa308a8ac2337966d4728d0840b95a1c9cf047ead5ff87f4e7aa2

WuKvR

It's been won guys! Thus far the winner has contacted me privately with the proof...

[runlinux]

Impressive! Congrats!

[wtfvanity]

I chose V as the first letter! So close but so far!

[SgtSpike]

Well then, that didn't take long!

[Uncurlhalo]

So do we get to know the password? 

[SgtSpike]

So do we get to know the password? 

http://blockchain.info/tx/eb758c500d5fa308a8ac2337966d4728d0840b95a1c9cf047ead5ff87f4e7aa2

WuKvR

It's been won guys! Thus far the winner has contacted me privately with the proof...

[wtfvanity]

I checked where I was in the keyspace and even if I had chosen W as the first letter, I was about an hour behind this guy.

[wachtwoord]

A final question though. Decrypting the encrypted private key yields a private key (hex)". Whne I try to import this key into my Armory wallet however it says it is not recognized. How should I do this?

[casascius]

The person who won it says he took libscrypt.so.1.0 from tarsnap and got it to load in the context of C# with a DllImport (something I never thought was possible in the Microsoft toolchain - but I suppose must be possible in Mono?) so he could run my code with the benefit from a native C implementation of scrypt.  Then he just split it across a large number of machines he had access to (he said 20).  This is what he had told me at the point I withdrew my decision to divulge a letter, given that I insisted on evidence that an upcoming win was plausible.

[casascius]

N enhances memory consumption with computational enhancement while r simply enhances memory consumption.  You further slow your algorithm down with N as compared to R.  It's really a matter of preference when you get to very large memory consumption (>1 MB), because at that point you're using RAM and you're going to see a severe slowdown.  Additionally, chacha20 should generally be used in place of salsa20 because it's faster and considered exactly as secure.

N becomes a much bigger deal (as far as I can tell) if you use multiple block cipher hash functions because you will be doing many more of these block cipher hashes.  if you are using a lot of block cipher hash algorithms (see below) increasing r would be ideal because you may then actually face significant slowdown.  see theorem 1 for ROMixH computational time from the scrypt paper.

skein is secure, the reason it wasn't considered for SHA3 was because it's really computationally intensive.  the same goes for blake.  sha3 (keccak) has extremely high throughput as compared to either of those algorithms (or SHA256, which is similarly slow), hence its selection as sha3.

if you want something that is a total pain in the ass to crack on a parallel machine (asic, gpu) a high N or r value (resulting in 16-256 MB of memory use) and skein/blake for the block cipher will suffice.  the more block ciphers you add in tandem (eg SHA256(BLAKE512(SKEIN(data, key))) the worse it gets for asic hashing without strongly affecting runtime performance because need an additional 20,000-50,000 circuits per hash algorithm.  but as most of your slowdown is in memory with high N or r values, you can really add as many secondary block ciphers as you like without it making the algorithm a lot slower.

basically all the SHA3 final candidates are reasonably good algorithms, just keccak was the only one that had a ridiculously fast throughput as compared to SHA256.  but in this case speed isn't all that important because the size of the data is so small.

the major advantage to using daisy chained block ciphers in scrypt is also that in the event one block cipher is determined insecure, you still have the others as a failsafe.  the minor advantage is increased asic difficulty.

if you're interested on working on an implementation like this let me know, i would like to make a block chain based on an algorithm such as this along with some other protocol tweaks for economics.

Here's what I think: perhaps you should consider proposing the next brainwallet algorithm - a problem waiting for an excellent solution and insights like yours.

What you are suggesting here yields the very property that I suggested was desirable, just at the expense of implementation complexity.  Thwarting the possibility of ASIC cracking is valuable... but probably so much more so for brainwallets than for passworded private keys meant to be human-readable.

For someone to want to crack a passworded private key, they have to come across one first and hope it was of high value - something I can't imagine would turn into an endeavor that might involve ASICs.  On the other hand, the idea of using ASICs to grab at low-hanging brainwallets has a lot of appeal for a potential attacker, since those very well could be high value.

Meanwhile, I wish for BIP 38 to achieve ubiquity, to the point that any merchant could offer the ability to redeem BIP 38-encoded private keys directly on their website, the same way I wish they could redeem unencrypted private keys.  Each additional piece of complexity makes it more likely that someone will consider its implementation (or just its code footprint) too burdensome.  I feel it's already pushing the envelope by depending on elliptic curve multiplication for what some might perceive as a pet implementation that favors my physical bitcoin products, and it probably is, except for the fact that I don't plan to hold a monopoly on physical bitcoins and hope they too become ubiquitous.

EDIT: it occurred to me that this encryption, as it is, already benefits from requiring a hodgepodge of algorithms beyond scrypt in order to verify that an answer is correct.  In order to arrive at the bitcoin address and hence confirm the decryption is successful, one must perform two SHA256's, two rounds of AES, another scrypt with much easier parameters, an elliptic curve multiply... it is not enough to look at just the return values of scrypt.

[Raize]

I bet the ones that are most likely to win are not even posting in the thread, just waiting to break the code and claim the prize.

FWIW, I had already burned through two dictionaries of five letter words with the first letter starting with N-Z in the format of AvAvA at the time of my post. I, like others, had almost missed the part about N-Z but I was looking through Mike's post history pulling five-letter words when I spotted that additional info.

I was almost certain "ViReS" was gonna work, too, in case he picked a word that insiders/customers would know. Tested that one manually.

I don't plan to hold a monopoly on physical bitcoins and hope they too become ubiquitous.

If there were a reasonably good way to print Bitcoin check/receipts via custom-coded Raspberry Pis, I'd be in this market, too. I'd create and host my own authentication server and use POS devices to let merchants "banking" with me accept Bitcoins. That's why I think your solution could have legs, it just needs a way for long-standing and known Bitcoiners to position themselves to individuals as trustworthy.

Right now I have a lot of friends and family asking me about Casascius Bitcoins when I show them off. They are perfectly fine to accept them as legit payments from me, but they aren't fine with then *spending* them with other friends and family because they have to say "Well, it's safe because it's created by this guy that Raize trusts." They also have no idea how to turn a Bitcoin into USD. If I could be the actual "banker", then I think they'd be far more comfortable.

It's easy to trade Bitcoin with other Bitcoiners, it's much harder to trade it with people I already know that will never understand cryptography, Bitcoin, the blockchain or why it is safe/secure.

[casascius]

If one could order bitcoins from me that were two factor with pass phrase, and then engrave the paraphrase on the coin upon receipt, it would require trust in nobody.

Simplest case, you engrave the pass phrase on the coin like it was a tag for a pet dog.

Better case, someone resells my coins and offers an added value because he makes up the passphrase and has the means to professionally engrave them on the opposite side of the coins.  The trust footprint is narrowed to whether or not I am colluding with them.

[enquirer]

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.

[Remember remember the 5th of November]

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.

You appear to be right. Though casascius did gives us hints. But generally, as computers get fast, so will the need to find stronger hashing algorithms, or longer passwords.

[nomorecoin]

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.

Passwords of 4 alpha characters, of known case.

The lesson is that this method is reasonably secure for its intended use.

[bitfreak!]

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.

[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.

[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?