[WITHDRAWN] 10 BTC bounty: A special sentence

[SoobNauce]

I have a sha-512 hash of a special sentence at http://pastebin.com/Use8Cuem (contest details there as well).
The sentence is 12 words long and makes grammatical sense.  It starts with an uppercase letter and uses at least one punctuation symbol.
I need to get the 10btc squared away but I intend to keep the reward up for at least a day.

I'm doing this because of a combination of today's xkcd and something I misinterpreted in the xkcd IRC room today.
Specifically, I want to make sure that my concept of "passwords with a very specific structure are not significantly less secure than randomly-generated passwords" is true before I decide one way or the other.

The sentence will look something like "I didn't know you liked to have egg and bread for breakfast." (although clearly this isn't the sentence.)

edit: No reward anymore, but I'd still like to examine this as a theoretical and/or philosophical question.

Also, question to the mods: Is it ok to cross-post this to the /economy/services/ board once my newbie period is up?

[hsf_context]

I-I can't do it...

[SoobNauce]

I'm interested in finding out whether there's a CS solution -- getting a sorted list of the most common words and making valid 12-word sentences.

I suspect (and this is me being optimistic because I hope to use this for memorable, secure passwords) that even knowing this much about the password, it'll still be easier to crack SHA-512 first-preimage style than to crack the password.

That, or beat me over the head with a wrench until I hand over the password.

Can someone please help me figure out how much entropy is in the sentence from the original post?

Code:

I didn't know you liked to have egg and bread for breakfast.

I'd break it down into words to start, maybe 2 bits for the ending punctuation...  I'd need more space to do a more comprehensive analysis

[nmat]

I may be wrong, but, given that it has 12 words and it is a grammatically correct sentence, I don't think that your password is too hard to brute force with a proper wordlist. The problem here is how to create a proper wordlist. I have a few simple and publicly available tools to generate pass phrases, but non can create sentences with 12 words. If the phrase was 3/4/5 words I would give it a shot

The problem comes down to this: what structure does a 12 word english sentence have? This is a linguistics problem and I am sure there are studies on the subject. It could be for example:

- interjection, determiner, adjective, noun, adverb, verb, preposition (....)
- interjection, determiner, noun, is, comparative, adjective, than, determiner (...)

If we combine these rules with an good english word dictionary, we will get a not so big (I think) wordlist which could contain your phrase.

[jh1523]

It's old news that passphrases are better than passwords; I've been using passphrases for 15 years now, and when (especially lately) I can't use one and instead I have to make up some 8-character nonsense of mixed-case-letters-numbers-and-symbols I use a passphrase anyway, and just run it through my brain-based obfuscator to generate a word out of it. For added security I use phrases that do NOT make gramatical sense yet are easy for me to remember, and using words from different languages together.

[Emrox]

honestly? taking a long enough word you like and writing it in your own 1337speak understanding will be the safest thing you get and can remember.

for example, lets say you choose control and make *[ontr0/ (the * is not part of the 1337speak but you wanna be using at least one freaky sign for security) or something like that out of it, you're done and can be sure that no dictionary will help your attacker.

[Bert]

12 words making sentences, with punctuation. I wouldn't even attempt it.

Circa 250,000 words in the English language, just randomly mixing the words ignoring sentence structure is 250,000^12 or 5.96^64 combinations. So that would be the upper limit.

Limiting that to sentence structure is difficult. Take one word "dog", it is a noun and a verb, this information would need to be known about all words in the English language. Once known the words could be fed through one bad ass lexicon syntax based sentence generator that spewed out valid 12 word sentences. But I suspect that the overhead of the sentence generator may be higher than brute forcing all of the random combinations.

Another approach would be to download all 36K books from Project Gutenberg and filter out all 12 word sentences and use that as your human generated sentence filter for brute force.

Or a webcrawler to scan the Internet for 12 word sentences as the filter for brute force. *ponder* I could say more about this as a targeted approach. But I don't have access to the data collected about you by google, facebook, twitter, amazon, imgur, your ISP ... - but it could be a method for a very focused filter. Using your own digital footprint against you. Googling "SoobNauce" would be the first step for a normal Internet citizen - 875 results (I apologise for the scare tactic, but everyone has a digital footprint).

(While I am typing the above the Beatles lyrics are in my head "There's nothing you can do that can't be done. Nothing you can sing that can't be sung." - there is no sentence you can create that hasn't already been typed.)

I'm not saying it can't be done, just that it isn't worth the herculean effort for 10 BTC. Yea the work could be reused, but not for anything good.

The simple solution is to jumble the sentence that it doesn't make logical sense any more, then you are forcing the 5.96^64 word combination brute force attack. Shifting only one or two words would mess up the above filtering. Or throw in a word or two from a language (or two) other than English, and the difficulty becomes far far larger than 5.96^64 word combinations.

[RandyFolds]

honestly? taking a long enough word you like and writing it in your own 1337speak understanding will be the safest thing you get and can remember.

for example, lets say you choose control and make *[ontr0/ (the * is not part of the 1337speak but you wanna be using at least one freaky sign for security) or something like that out of it, you're done and can be sure that no dictionary will help your attacker.

No way. Even the crappiest of wordlists have got to incorporate 1337 characters. Think who is designing this shit, and think how clever the average user probably thinks it it to swap a 5 for an S in their all-so-clever password "Pa55word" when their company starts making them change their passwords once a month and use two numbers in it.

[SoobNauce]

I'm not saying it can't be done, just that it isn't worth the herculean effort for 10 BTC.

That raises an interesting question.  Is there any number of BTC that would make this legitimately worth it to attempt to break?

[Bert]

Now you are asking a moral question, which I personally choose not to think about *happy thoughts, good thoughts*. Build your fences higher than anyone else's and you are safer than anyone else. If someone wants something and has no morals or regard for any human life ...

[TiagoTiago]

Hm, interesting, i wonder if cracking this will provide a significant advance in the area of natural language interpretation...

[SoobNauce]

I forgot to mention in the original post, but this did have a time limit -- I was going to drop the reward once it cycled out of the topic in the #xkcd IRC room (which would happen in about 2-7 days).  It's cycled out now so I'm going to post the original sentence and withdraw the reward.

The sentence was "When all else fails, a new person can always bring more guns."

The associated hash (for verification) was "c612c2961c582be831486251188f3e86e7d979d865f01ea5e3e9e910a5a7874fad4b5c3e067097d 0a6d7da2bd1c60a5fca0e1e925ea8c95b14bd757c53bb515d".

If you want, and just as a "for kicks" project, I can make another hash but I think I should probably put this topic to rest.

also in case I forgot to mention in the rest of the post, I'm officially withdrawing the 10 BTC bounty.