Bitcoin Forum
December 03, 2016, 03:51:49 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: [WITHDRAWN] 10 BTC bounty: A special sentence  (Read 1030 times)
SoobNauce
Newbie
*
Offline Offline

Activity: 8


View Profile
August 10, 2011, 12:47:12 PM
 #1

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?
1480780309
Hero Member
*
Offline Offline

Posts: 1480780309

View Profile Personal Message (Offline)

Ignore
1480780309
Reply with quote  #2

1480780309
Report to moderator
1480780309
Hero Member
*
Offline Offline

Posts: 1480780309

View Profile Personal Message (Offline)

Ignore
1480780309
Reply with quote  #2

1480780309
Report to moderator
1480780309
Hero Member
*
Offline Offline

Posts: 1480780309

View Profile Personal Message (Offline)

Ignore
1480780309
Reply with quote  #2

1480780309
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1480780309
Hero Member
*
Offline Offline

Posts: 1480780309

View Profile Personal Message (Offline)

Ignore
1480780309
Reply with quote  #2

1480780309
Report to moderator
hsf_context
Jr. Member
*
Offline Offline

Activity: 54



View Profile WWW
August 10, 2011, 01:40:45 PM
 #2

I-I can't do it...

Digital artist for hire! Sketches anyone?
Want a custom Photoshop artwork? PM me! GIF banners available too!
SoobNauce
Newbie
*
Offline Offline

Activity: 8


View Profile
August 10, 2011, 02:08:05 PM
 #3

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
Hero Member
*****
Offline Offline

Activity: 602


View Profile
August 10, 2011, 03:29:53 PM
 #4

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 Wink

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
Jr. Member
*
Offline Offline

Activity: 56


View Profile
August 10, 2011, 03:52:30 PM
 #5

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.

If you feel I have helped you, consider donating to 1BFLDATk4iE6R2hYTfqNjxBZYctU9eshCM
Emrox
Newbie
*
Offline Offline

Activity: 4


View Profile
August 10, 2011, 05:58:00 PM
 #6

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.

2x 5850, 1x 5870, 1x 5970 @Win7x64  // ~2 GH/s
Bert
Full Member
***
Offline Offline

Activity: 126



View Profile
August 10, 2011, 09:15:55 PM
 #7

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.

Tip jar: 1BW6kXgUjGrFTqEpyP8LpVEPQDLTkbATZ6
RandyFolds
Sr. Member
****
Offline Offline

Activity: 434



View Profile
August 10, 2011, 11:20:45 PM
 #8

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.

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
▓▓ ONEDICE.ME ▓▓▓▓▓ BEST DICE EXPERIENCE ▓▓▓▓ PLAY OR INVEST ▓▓▓▓▓▓
▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓
SoobNauce
Newbie
*
Offline Offline

Activity: 8


View Profile
August 11, 2011, 01:33:24 AM
 #9

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
Full Member
***
Offline Offline

Activity: 126



View Profile
August 11, 2011, 01:51:10 AM
 #10

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

Tip jar: 1BW6kXgUjGrFTqEpyP8LpVEPQDLTkbATZ6
TiagoTiago
Hero Member
*****
Offline Offline

Activity: 616


Firstbits.com/1fg4i                :Ƀ


View Profile
August 11, 2011, 02:01:39 AM
 #11

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

(I dont always get new reply notifications, pls send a pm when you think it has happened)

Wanna gimme some BTC for any or no reason? 1FmvtS66LFh6ycrXDwKRQTexGJw4UWiqDX Smiley

The more you believe in Bitcoin, and the more you show you do to other people, the faster the real value will soar!

Do you like mmmBananas?!
SoobNauce
Newbie
*
Offline Offline

Activity: 8


View Profile
August 12, 2011, 07:37:06 AM
 #12

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.
Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!