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

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