Computational Limits and Applicatoins of Brainwallet Software?

[AsymmetricInformation]

Hello CompSci/Math people,

Part 1

I just went here http://shakespeare.mit.edu/hamlet/full.html to grab the entire text of the play Hamlet, and pasted it into the 'Passphrase' box of brainwallet...and...it worked.

By this I mean: it fit the entire text into the little box, and generated the keys/address in about 1 second.

I did not expect this to happen...does anyone know exactly how much text/what kinds of text this thing can eat before it breaks?

Part 2

Can I achieve secure entropy with:

1) Pick stable website
2) (Optionally) find/replace all 'X' with 'Y'
3) Copy text / html source / whatever into brainwallet passphrase.

Assuming the website/text would not change, this would be secure(?) and memorable (basically only 1 or 2 things to remember)...what's the catch I am missing?

Part 3

Ultimately, why not allow clients to import any file, not just text, to generate keys. Given cloud computing / backups of huge filesystems, I could then choose one tiny pdf/mp3/doc stashed somewhere in my library of files...attacker, even after breaking into my actual file system (which would already be pretty bad), still wouldnt know which file to use, especially in the mp3 case where the files are accessed often (and have emotional/memorable significance to users but not attackers), and can be reproduced from (for example) youtube videos or something.

...sorry if this was discussed before, I did not see it.

[scintill]

I just went here http://shakespeare.mit.edu/hamlet/full.html to grab the entire text of the play Hamlet, and pasted it into the 'Passphrase' box of brainwallet...and...it worked.

By this I mean: it fit the entire text into the little box, and generated the keys/address in about 1 second.

I did not expect this to happen...does anyone know exactly how much text/what kinds of text this thing can eat before it breaks?

I don't know about specific programs, but there is (typically) no limit to the amount of text you can put into a hash function, which is how brainwallets work.  I think it would take the equivalent of thousands of books' worth of text to make it noticeably slow, too.

Part 3

Ultimately, why not allow clients to import any file, not just text, to generate keys. Given cloud computing / backups of huge filesystems, I could then choose one tiny pdf/mp3/doc stashed somewhere in my library of files...attacker, even after breaking into my actual file system (which would already be pretty bad), still wouldnt know which file to use, especially in the mp3 case where the files are accessed often (and have emotional/memorable significance to users but not attackers)

Again I don't know specifics of what clients offer, but I just generated a key from a PDF file like this:

Code:

sha256sum file.pdf

(at Linux command line), then taking the hex string (6e1af4e6324eb27c60c2ce1b1c0411f2bb85115e14ca89de266af3e846b000f5) to brainwallet.org, Convert tab, paste into left box, choose hex on left, base58 on right, and out comes a private key you can import into most clients.

and can be reproduced from (for example) youtube videos or something.

I would be careful with that because you might not get the same byte-for-byte mp3 file.  Ripping a CD track in a lossless format, with the same software/hardware each time, might work though.

Test with small amounts before putting your life savings on a key you generate with one of these methods.

[jim618]

You have to be careful to make the distinction between:

1) The number of things you are choosing between
2) The amount of data/ randomness in the thing you are choosing.

For instance you might think - I have lots of mp3s - but you probably having something of the order of thousands or tens of thousands. This is a small number to bruteforce.

How about the number of people on the planet ? 6,000,000,000. In crypto terms this is still a small number.

How about you choose a single mp3 file from the mp3 collection of a single human being across the whole planet ?

Unfortunately there are lots of repeats of mp3s - how many mp3s do you have that are completely distinct from anyone else's on the planet ? If everyone had 1,000 unique-to-them mp3s (which I doubt) we are talking about:

6,000,000,000,000 distinct mp3s.

This is 6 "tera mp3s". The current network hash rate is 17 terahashes/s so even now without ASICs it would be feasible to hash every mp3 on the planet. (If you think - this is kinda what bittorrent is doing!)

(this ignores the difference in size between a key hash and an mp3 hash and MB and MiBs etc for simplicity)

FUN FACT: To listen to 6 tera mp3s (if each has a length of 3 minutes) will take 40 million years. That is some playlist !

TL;DR You still need to add some randomness in addition to your choice of file to make it secure.

[casascius]

Here is a way I think would be good to make decent brainwallets:

Think of some sort of inside joke, jingle, phrase or song that you made up and remember from your childhood.  It has to be something that nobody but you (and perhaps a couple close friends at best) know.  Take a couple sentences from it.  The more senseless the better, especially if it has words you made up yourself that cannot be found in the dictionary.  Do not use something you heard from somewhere else.  One requirement is that you must be able to remember it word-for-word each time you recall it, but if it's from that long ago, chances are pretty good you're going to remember it the same way, each and every time.

[swissmate]

That's a nice idea, keys generated per favorite books.

[gmaxwell]

By this I mean: it fit the entire text into the little box, and generated the keys/address in about 1 second.
I did not expect this to happen...does anyone know exactly how much text/what kinds of text this thing can eat before it breaks?

Yes, this works. it's unsurprising, and it's not good for security.

You're thinking— But Greg, I gave it like 10 million bits of entropy, it must be secure!

Wrong.  The entropy of your key is

Code:

-log2( The probability that someone would feed it a book, and from your source ) + -log2( 1 / Number of books available from that source )

(assuming you chose uniformly).

So say there is a 1/10000 chance someone would use a whole project gutenberg book as a seed. There are 40,000 project gutenberg ebooks.

-log2(1/10000) + -log2(1/40000) = 28.575 bits of entropy. Crackable in moments, since generating a _great_ many keys per second isn't hard for someone who it's confined to offensively slow javascript sha256 implementations.

Your attacker is not a million monkeys smashing typewriters for eons until by chance one produces your work of Shakespeare; your attacker is someone with a strong model of human behavior and a large amount of computing power.  You're up against a decenteralized consortium of geniuses  each commanding a trillion strong army of faultless robots at typewriters.

Against an attack with good models the strength of your key is only the randomness of how you selected it, and may have little to do with the size of the data itself.  Even if you postulate modifications of the book, the attacker can model those too. Changing all the e's to 3's? Sorry snowflake, nothing is original anymore.  And if you do have a strongly random way of choosing libraries, books, and modifications— you're just as well off using that randomness directly.  "Book Foo from library bar, modified thusly" has the same randomness as the actual data. (± the probability that you'd express it that particular way instead of actually doing it)

Humans are terrible at being random. Even when you think you're being clever and extra random you're often not, in fact being clever often makes you less random— you'll only think of a few possible ideas out of the space of all ideas so you can't choose uniformly between them.

Human generated private keys should simply never be used for applications where the keyed material is generally available for attack. Practically no one is able to do so securely, and a lot of people think they can but they really can't. Must of the common advice about passwords/keys is inapplicable for a case where attackers all over the world can instantly begin testing at enormous rates or apply precomputation attacks without having to compromise something first.

[coretechs]

For a file, just use a picture you took yourself with a digital camera and hash it.

For extra security, take a picture of a lava lamp.  

[DeathAndTaxes]

For a file, just use a picture you took yourself with a digital camera and hash it.

For extra security, take a picture of a lava lamp. 

For extra extra security make sure the lava lamp is holding a sign with it's forum screen name and has a shoe on it's head.

Er wait wrong thread.

[coretechs]

You could then take a picture of a salt shaker and concatenate it with the lava lamp picture, then hash that FTW.  

[scintill]

For a file, just use a picture you took yourself with a digital camera and hash it.

Still, if someone guesses you are doing this and obtains a collection of photos/music from your hard drive, it is not hard to bruteforce a few simple types of hashes.

It all depends on how paranoid you are, how determined you think any attackers will be, etc.

[cbeast]

I like to have several two easy to remember but hard to break brainwallets. If I end up in a prison and I end up using one, I'll want another for when I get out. Yeah, I just made it public knowledge that there may be another one or two. Really, that's all I have, and they are very small. I made sure that I won't need thumbs, kneecaps, or any other breakable body parts to decipher the keys. Actually, I will need all my breakable and unbreakable parts to decipher a brainwallet. I've said too much. Nevermind.

[AsymmetricInformation]

I love the photo idea...they're unique, you could back those up, access them all the time, etc without suspicion (the goal being to keep the method [using a photo] secret). Throw in a randomly selected hash method from some published list. You only need to remember two things now...photo and hash method, one of which was random. If the photo came from a huge, known, pool (instagram, facebook, tumblr) and we cropped the photo at a randomly chosen pixel height and length (remembering four things), are we "secure" yet?

(To bring it back to the book idea, we could screen-capture part of the online book-source and save as jpeg or something).

Given the difficulties of figuring out an eternally unguessable (and unpopular) method, Electrum's 12 words seem a lot easier and safer now.


Unrelatedly, I suddenly want to see a performance of Hamlet where each character speaks a hash of their original line... 

[casascius]

You only need to remember two things now...photo and hash method, one of which was random

The only problem is it's no longer a brainwallet.  It won't do you any good if you don't have possession of the photo.  You may as well just stick to a wallet file and its associated password.

For a brainwallet to be satisfactory, it ought to be useful if you are sitting in prison in your underwear.  Or stuck in another country having been robbed of all your physical possessions and having been left with nothing but the clothes you're wearing.

Here are some more ways I can think of to come up with a hard-to-crack brainwallet.  Each of them has something in common: information personal to you, not necessarily secret, but well-fixed in the average person's brain, not likely to be forgotten, and not typically available to someone engaging in mass cracking.

* A comma-separated list of all your known street addresses in chronological order, in the USPS preferred format (if US), followed by some password:  "1234 12th Street, 5678 Poppy Lane #910, 4858 S 1300 E #16, 2901 Little Cottonwood Rd, foobar123"
* A list of all the girls(guys) you consider yourself to have dated when younger, followed by some password: "Emma Hale, Fanny Alger, Lucinda Harris, Louisa Beaman, Zina Jacobs, foobar123"