Some might point out that using a hex digest limits the characters that will be generated too much, do this then.
echo -n "date" | sum | base64
So let's say you have to change your password every month. Pick a day, let's say the second Tuesday of the month. Since your memory sucks write this down "Pipes on second Tuesday @ 5:08!". Sounds like an event reminder right? Here's your actual password algorithm for this month. First you want to has the 'second Tuesday of the month'.
echo -n "2010/07/12" | sha1sum | base64
which outputs
NTFhMTY4NmJkNWQyZmIzNWJlZTlmYmQxYzEwN2FjNGE1MjUyYjI1OCAgLQo=So what was the rest of that reminder for? Now you're going to make it as good as random, take the first 8 characters '
NTFhMTY4' and insert a pipe '|' at the 5th character, resulting in 'NTFh|MTY4'. Now you have a 'good as random, but recoverable' 9 character password.Given if you work with really clever people they might be able to figure it out if they know you use this kind of process. But I'm sure having read this article and my previous one you'll come up with something even better, but just as reproducible.
UPDATE:
I do not believe that anyone can seriously prove (after having read both articles) that you could crack this with anything less than a brute force attack. Because I've suggested inserting 1 or more characters into the final outcome, chances are those are anything in the 94 printable characters of ASCII. Yes you might limit the end possibilities but after seeing passwords that most people have... this makes you a hard enough target that no one is going to bother. Basically all assumptions that using this is bad revolves around someone knowing exactly what you do (so in reality it's probably only bad for me).
I should also note that my personal system encrypts passwords with a salted sha512 and I'm having trouble find a password cracking tool that can even try to brute force that.
UPDATE:
oh and just in case you forgot... no one is trying to brute force your password. Remeber this XKCD
That's not a good password because sha1sum is not random binary it is hex digits and base64 is an encoding of it.
ReplyDeleteWatch this:
perl -e '@a=("a".."z","A".."Z",0..9); for (1..4092) { print $a[rand @a],$/ }' | ent
run that.
Your entropy should be ~ 3.97 so 4 bits per byte. Which is ok for plain text followed by a newline and we know perl is random enough so we'll trust it. This is our base line.
We need entropy as good as that to be a random password.
perl -e 'for my $year (2000..2010) { for my $month (1..12) { for my $day (1..31) { print "echo -n \"$year/$month/$day\" | sha1sum | base64$/" } } }' | sh - | tee /tmp/hashes
So now /tmp/hashes is full of stuff
ent /tmp/hashes says Entropy = 5.139547 bits per byte. which is actually bad, because it says the file isn't that random. So now lets look at each column.
for file in `seq 1 8`; do cut -c $file /tmp/hashes | ent | fgrep Entropy; done
Entropy = 2.142269 bits per byte.
Entropy = 2.466567 bits per byte.
Entropy = 3.099457 bits per byte.
Entropy = 2.998465 bits per byte.
Entropy = 2.138885 bits per byte.
Entropy = 2.469638 bits per byte.
Entropy = 3.097788 bits per byte.
Entropy = 2.998468 bits per byte.
So do you see that? The base64 encoding is not good at all. The entropy per column is very very low.
cut -c 1-8 /tmp/hashes | ent | fgrep Entropy
Entropy = 4.873874 bits per byte.
perl -e '@a=("a".."z","A".."Z",0..9); for (1..4092) { print join("",(map { $a[rand @a] } (1..8))).$/ }' | ent
Entropy = 5.794631 bits per byte.
So what this means is that purely random results have way more information/range than your base64 results.
What I recommend is if you want a one-way hash is to make a hash yourself (perldoc perlguts gives a reasonable hash that they use) or map bits of the sha1sum hashes to characters.
Summary:
* Not random enough
* The entropy (the information) is too low
* Make your own mapping that covers the characters more uniformly.
I tell you what... you show me a password cracker that can crack my passwords significantly faster than a random password. I'm not convinced that just because it's not completely random that it can be cracked faster.
ReplyDeletewell. I know it technically can be if you know the exact algorithm I'm using. But I don't think not knowing what other random characters I throw in and what my input is, that in a real life brute force you would crack it faster than your random password. It certainly won't fall to a dictionary attack.
ReplyDeleteI take offense when you suggest that it is secure.
ReplyDeleteAnyways here's an implementation that gets that 5.7 bits per byte entropy that we demonstrated before was pretty good for a..z,A..Z,0..9
http://pastebin.com/CRFFbVFJ
for file in `seq 1 8`; do cut -c $file /tmp/passwds | ent | fgrep Entropy; done
Entropy = 3.976368 bits per byte.
Entropy = 3.976426 bits per byte.
Entropy = 3.976262 bits per byte.
Entropy = 3.976328 bits per byte.
Entropy = 3.976462 bits per byte.
Entropy = 3.976511 bits per byte.
Entropy = 3.976371 bits per byte.
Entropy = 3.976422 bits per byte.
I take offense when you suggest that it's not secure enough... but I'm going to test both yours and mine and we'll find out whether there's a significant difference between yours and mine against real password crackers.
ReplyDeleteI have pretty good proof that I can brute your password really hard and really fast:
ReplyDeleteHere's the summary, my method, which relies on uniformly random characters is 14 orders of magnitude more secure in terms of size of search space than your method.
Watch:
You don't believe that your passwords are fundamentally insecure?
# Well look at these histograms:
# /tmp/passwds are random passwords of a..zA..Z0..9 (62)
$ cut -c 1 /tmp/passwds | sort | uniq -c
539 0
546 1
535 2
533 3
548 4
570 5
486 6
523 7
556 8
558 9
510 A
545 a
519 B
525 b
558 C
576 c
533 D
549 d
550 E
564 e
551 F
535 f
589 G
509 g
532 H
545 h
547 I
554 i
557 J
520 j
563 K
559 k
585 L
552 l
557 M
550 m
550 N
494 n
537 O
555 o
514 P
534 p
552 Q
513 q
547 R
548 r
528 S
568 s
572 T
531 t
535 U
527 u
563 V
539 v
507 W
526 w
539 X
541 x
565 Y
529 y
546 Z
514 z
# tmp hashes were generated as per above in the previous message
# Now per column of your password:
# Notice a problem here: (5)
$ cut -c 1 /tmp/hashes | sort | uniq -c
1003 M
1019 N
524 O
793 Y
753 Z
#And here notice how the number of characters is so low? (8)
$ cut -c 2 /tmp/hashes | sort | uniq -c
298 2
657 D
378 G
601 j
404 m
814 T
459 W
481 z
#well the range is wider here! (20)
$ cut -c 3 /tmp/hashes | sort | uniq -c
157 A
101 B
151 c
81 d
315 E
182 F
156 g
125 h
309 I
193 J
153 k
110 l
349 M
176 N
329 Q
166 R
332 U
194 V
329 Y
184 Z
# not so hot here (16)
$ cut -c 4 /tmp/hashes | sort | uniq -c
280 0
253 1
263 2
259 3
273 4
241 5
264 h
248 i
245 j
263 k
240 l
252 m
262 w
215 x
248 y
286 z
# oh this is not good (5)
$ cut -c 5 /tmp/hashes | sort | uniq -c
1048 M
975 N
484 O
771 Y
814 Z
# that's a small search space.. (8)
$ cut -c 6 /tmp/hashes | sort | uniq -c
303 2
627 D
393 G
647 j
398 m
782 T
484 W
458 z
# the range here is a little wider (20)
$ cut -c 7 /tmp/hashes | sort | uniq -c
156 A
89 B
156 c
87 d
320 E
201 F
157 g
110 h
310 I
194 J
135 k
89 l
309 M
200 N
346 Q
187 R
332 U
202 V
313 Y
199 Z
# slightly better (17)
$ cut -c 8 /tmp/hashes | sort | uniq -c
271 0
253 1
258 2
296 3
243 4
248 5
277 h
254 i
267 j
268 k
233 l
259 m
254 w
244 x
236 y
231 z
# 5 * 8 * 20 * 16 * 5 * 8 * 20 * 17
# = 174 080 000
# 62^8
# = 218 340 105 584 896
# Do you see now? 14 orders of magnitude difference
Your algorithm is not random enough. It is fundamentally insecure. A purely
ReplyDeleterandom string of 0..9,a..z,A..Z produces a search space 14 magnitudes larger
than your base64 method. Why? Because base64 is an encoding, it is not meant
for randomness! You should use a hash.
You don't believe that your passwords are fundamentally insecure?
# Well look at these histograms:
# /tmp/passwds are random passwords of a..zA..Z0..9 (62)
$ cut -c 1 /tmp/passwds | sort | uniq -c
539 0
546 1
... 58 lines ommitted
546 Z
514 z
# tmp hashes were generated as per above in the previous message
# Now per column of your password:
# Notice a problem here: (5)
$ cut -c 1 /tmp/hashes | sort | uniq -c
1003 M
1019 N
524 O
793 Y
753 Z
#And here notice how the number of characters is so low? (8)
$ cut -c 2 /tmp/hashes | sort | uniq -c
298 2
657 D
378 G
601 j
404 m
814 T
459 W
481 z
#well the range is wider here! (20)
$ cut -c 3 /tmp/hashes | sort | uniq -c
157 A
101 B
151 c
81 d
315 E
182 F
156 g
125 h
309 I
193 J
153 k
110 l
349 M
176 N
329 Q
166 R
332 U
194 V
329 Y
184 Z
# not so hot here (16)
$ cut -c 4 /tmp/hashes | sort | uniq -c
280 0
253 1
263 2
259 3
273 4
241 5
264 h
248 i
245 j
263 k
240 l
252 m
262 w
215 x
248 y
286 z
# oh this is not good (5)
$ cut -c 5 /tmp/hashes | sort | uniq -c
1048 M
975 N
484 O
771 Y
814 Z
# that's a small search space.. (8)
$ cut -c 6 /tmp/hashes | sort | uniq -c
303 2
627 D
393 G
647 j
398 m
782 T
484 W
458 z
# the range here is a little wider (20)
$ cut -c 7 /tmp/hashes | sort | uniq -c
156 A
89 B
156 c
87 d
320 E
201 F
157 g
110 h
310 I
194 J
135 k
89 l
309 M
200 N
346 Q
187 R
332 U
202 V
313 Y
199 Z
# slightly better (17)
$ cut -c 8 /tmp/hashes | sort | uniq -c
271 0
253 1
258 2
296 3
243 4
248 5
277 h
254 i
267 j
268 k
233 l
259 m
254 w
244 x
236 y
231 z
# 5 * 8 * 20 * 16 * 5 * 8 * 20 * 17
# = 174 080 000
# 62^8
# = 218 340 105 584 896
# Do you see now? 14 orders of magnitude difference
Oh jeeze, I'm sorry, google said it ate my post so I reposted.
ReplyDeleteApologies.
time perl cushing.pl test
ReplyDeleteLooking for YTk0YThm at cushing.pl line 14.
M2 at cushing.pl line 17.
MD at cushing.pl line 17.
MG at cushing.pl line 17.
Mj at cushing.pl line 17.
Mm at cushing.pl line 17.
MT at cushing.pl line 17.
MW at cushing.pl line 17.
Mz at cushing.pl line 17.
N2 at cushing.pl line 17.
ND at cushing.pl line 17.
NG at cushing.pl line 17.
Nj at cushing.pl line 17.
Nm at cushing.pl line 17.
NT at cushing.pl line 17.
NW at cushing.pl line 17.
Nz at cushing.pl line 17.
O2 at cushing.pl line 17.
OD at cushing.pl line 17.
OG at cushing.pl line 17.
Oj at cushing.pl line 17.
Om at cushing.pl line 17.
OT at cushing.pl line 17.
OW at cushing.pl line 17.
Oz at cushing.pl line 17.
Y2 at cushing.pl line 17.
YD at cushing.pl line 17.
YG at cushing.pl line 17.
Yj at cushing.pl line 17.
Ym at cushing.pl line 17.
YT at cushing.pl line 17.
Yeah we found it! at cushing.pl line 25.
real 1m38.840s
user 1m38.642s
sys 0m0.036s
http://pastebin.com/7wyc4PNn
ok for starters that code isn't against an actual password file. secondly it assumes only base64 from the looks of it... which means you've ignored some of what I've said... which is add a random character or 2 to what you can remember.
ReplyDeleteSo there are 9 positions where you can put your special character, and assuming it is ASCII, we have 127 characters to choose from. So you increased my search time 1143 times (9 * 127 * X).
ReplyDeleteI can get an easy speed up simply by using C, surely a naive C port can get this done in the same amount of time.
Remember what I said 14 orders of magnitude difference, 1000 is closes the gap by 7 orders of magnitude at most.
Again you have to think about search space.
Effectively base64 is wasting your characters by making your search space so small.
I can tell by reading your responses that you didn't read my first blog which I said was prerequisite. you're assuming that I only use 9 characters, and that I add only one. Also anyone searching for unicode, or really any character that's not on keyboard is probably wasting their time. Also you have to be able to get this password from a salted hash (I use sha512 on my system) (or break into some website not maintained by me)
ReplyDelete"So there are 9 positions where you can put your special character, and assuming it is ASCII, we have 127 characters to choose from. So you increased my search time 1143 times (9 * 127 * X)."
ReplyDeletebtw I use way more than 9 characters... and I use more than 1 special character for important accounts. also you should limit that to the 94 printable characters in ascii. since not all 94 are typeable with just the shift key and another keypress might want to just limit it to the ones on an en_US keyboard (I suspect about 80 though I can't find a reference). but like I said you're talking about the theoretical weakness of my method not the practical weakness. I can't find a wordlist that of even just base64 words. There's always the rainbow tables. Since I can insert other characters anywhere in it, and they don't have to be symbols (and I said to do that in the 2008 post) for all existing options you might as well be dealing with a brute force, and for 9 characters that could take months just for alphanumeric.
oh and one last thing... never forget the lesson of http://xkcd.com/538/ and real world security where the real risk is someone writing there password on a postit on there monitor, or using something stupid like 'pattycake'.
ReplyDeleteI don't appreciate your insults, I understand your problem perfectly well and I repeatedly demonstrated its flaws. I also understand that you previous blog post didn't suffer from as many glaring flaws as this one.
ReplyDeleteYour original blog post which you claimed I didn't read, didn't include this glaring error of using base64.
But sha1sum only produces hex digits you say.
Well guess what, 8 hex digits provide a larger search space than your 8 base64 digits. So assuming you apply your "trick" your magic character to either of them the hex digits one is still going to be more secure and have larger search space than your base64 example here.
You need to stop making these silly assumptions, real cryptographers wouldn't make these assumptions. Imagine I hack a user on your box who used an easy password, but obviously not you. Imagine my goal is to hack Caleb. Then once on the box, I use the CPU available to the user I hacked and a run a brute forcer. I now skip all that awful network latency and now I can try authentications even faster. In easier case I gained access to your database and have a hashed version of your password, in both cases I will brute force your password. I will say, gee Caleb bragged about his secure password system and I'm targetting him so my bruter will use the following regular language to generate passwords to test. Lucky for me Caleb used a system that had a tiny search space. 1 to 10 minutes later I've bruted your password. Maybe 10 hours later if I had to keep talking to some authentication engine.
The point is that real cryptographers assume that you know the technique that they use, and they make systems that are resilient to that. In your case your system tells me that my search space is tiny so go at it.
There are theoretical aspects to what I've talked about here but I thought you would've noticed by now how concrete I have been with you. I have consistently demonstrated the weaknesses and exposed the search space size.
You don't seem to understand that you search space is tiny. This is not secure. You don't seem to understand there are many contexts in which I can brute force your password. You also didn't seem to get that base64ing a sha1sum was a bad idea because the original sha1sum actually had more information per character than your base64ing.
You need to stop defending and start educating.
* Learn about brute force attacks
* Learn about search space size
* Learn about the requirements and properties of cryptographic hashes
* Learn about entropy
Had you really understand any of that, you would've been disgusted at my histogram which showed that base64 was not uniformly distributed across a large alphabet, you would've understood the danger, but instead you acted like your magic character would save you. But it didn't I showed that it did not add much to the search space and naive breakers could handle it.
You need to settle down and go and read something, even unix crypt has be
/MY INSULTS/ Get the HELL OFF MY BLOG! and learn some PRACTICAL SECURITY as opposed to being focussed on purist theory.
ReplyDeleteLOL from the peanut gallery.
ReplyDeleteCan you post a link to information on practical security? I assume, as you say, this is security that you use when you are sure no one will try to attack you.
I do this at home, I leave my windows open, but with screens and curtains. Only a burglar would even try to break through a screen, so I am in fine shape until one shows up.
Hey step away and calm down. Read what I have written it is perfectly rational and I provide concrete implementations, it can't get more practical than that. Do I have to write a C breaker to prove to you the error of your ways. I shouldn't have to. If you claim to know so much about practical security, you should be able to figure out by now that the difference between 1.5 minutes and 1500 minutes isn't much. This is practical.
ReplyDeleteThe only theory I have been using has been multiplication to work out the size of the search space.
ya for real Caleb even though this 'randomness' guy is using big words like 'entropy' it doesn't take much more than a calculator and some thought to see why he's got a point
ReplyDeleteHere's what we're going to do so you can prove me wrong. You're going to show me real life timings of cracked passwords.
ReplyDeletehttp://privatepaste.com/817426dec5
this is an excerpt from my /etc/shadow file. all the accounts were create solely for the purpose of this test. Some of them use My password generation method and some use yours. All the passwords are 9 characters to make it easier for you. I use base64 on all but not necessarily a sha1sum. You must use an existing tool to crack them, and I want the times. I will allow you to write your own (or custom rules for a tool) but only to provide a comparison in times. Because it is unlikely (outside of me) that anyone would have any clue how someone was generating a password. If mine are cracked in an unreasonable period of time then I will concede.
http://www.lockdown.co.uk/?pg=combi
would you say those times are accurate? if so we'll go by them-ish.
According to that it should take 83 days to crack a password of 8 char long and 96 possible characters in that slot worst case scenario (which is expensive). Your argument is that mine are so bad that you should be able to crack them in way less. I don't believe you can do it with an existing tool, and I don't believe anyone is going to write a new tool.
I'm not banking on the fact that mine have a lot less combinations. I'm banking on the fact that the burglars are more interested in my neighbors house because it's an easier target. Mine might be easier than yours but it's harder than other peoples.
To insure I don't cheat here's http://privatepaste.com/40cd9a96d2 the answers. password protected to insure you don't cheat.
Both pastes will autodelete after 1 year. But you should have mine in a couple of days tops right? like I said I want to see the times of a regular password cracker too (because that's what this is supposed to be good against, you couldn't write a specific attack if I hadn't posted this).
Bonus points if you can tell me the source used to generate the password.
I figure this is the most ideal circumstance you could have for cracking passwords outside of getting them in plain text, or unsalted. I mean if you have physical access to my box I'd be more worried about other things than you guessing one of my passwords. Poor programs like pidgin just store them in plain text.
@Cory the theoretical time is irrelevant the actual time is relevant. If you were using my silly little method most crackers wouldn't know that. There only option would be a brute force attack. I speculate that these won't fall any faster to that kind of attack than a pure random password. Now if someone knows and can target you then yeah they'll fall faster.
ReplyDeletehttp://blog.hacker.dk/2010/04/cracking-sha-256-and-sha-512-linuxunix-passwords/ < the only thing I've found that claims to be able to crack sha512 don't know if it can... but it certainly doesn't claim 90 keys a second on my system... (which is a quad core) it doesn't even claim 1.
ReplyDelete@xeno
ReplyDeleteanyone who knows you're password generation algorithm can guess your passwords easily. If you appended a static, long term password to the date, you'd be much better off
i.e.,
echo -n "2010/07/12 longTermPassword" | sha1sum | base64
You still have to remember a password, but it's only one instead of many. This basically what the Password Hahser firefox plugin does.
https://addons.mozilla.org/en-US/firefox/addon/3282/
No I won't. You quoting that page proves you still don't get it. You didn't have 96 possible characters per column. You had at most 26 possible characters per column for 8 characters and then you have 9 positions where you could inject your magic character and then your magic character was 1 of 96.
ReplyDeleteThis means that all positions and all magic characters create a search space of 9 * 96, so 864.
Lets look at 8 character length in the 26 character table on that webpage you linked to.
It says 8 seconds for class F. ok we're going to have repeat this search 864 times, that's 8 * 864, so that's 6912 seconds. Less than 2 hours.
Do you get it yet? Your search space is too small. The number of characters you have per column is too small.
Look at the character count histograms I provided. Look at the analysis.
@Anonymous I never said you couldn't do that. this article is not complete and is meant to be a complimentary addition to the other one. You can input whatever you'd like. It doesn't have to be a date, a date is just one thing you might be able to remember. I can tell you right now that I didn't use dates for every pw I generated for that shadow file, and the dates I did use all had varying formats. The point of this whole thing is that it's repeatable.
ReplyDelete... and random enough to not be easily cracked by someone who doesn't know you're using it.
ReplyDeleteLook your argument is generally viewed as fallacious in the security community:
ReplyDeletehttp://en.wikipedia.org/wiki/Security_through_obscurity
versus the accepted right way to approach the problem:
http://en.wikipedia.org/wiki/Security_by_design
@Randomness if you can crack them in 2 hours prove it. give me the passwords for the shadow files I gave you.
ReplyDelete@Randomness unless you'd like to admit that you can't do it... at least without writing code tuned specifically for this algorithm. Hell I don't think you can do it even with code tuned to this algorithm. But prove me wrong. I'm waiting.
ReplyDeleteI already said no if you had read my comments.
ReplyDeleteAlso your challenge is bogus, it is really a challenge to crack a sha512sum (which is was designed following Security by design, that I linked earlier), rather than your broken generator.
Do you see the difference? sha512 was properly designed and we all know the implementation. Your password generator was not properly designed as I described before and you now claim it relies on security through obscurity.
Summary: You cannot bait someone to fight sha512 when the real issue is your broken generator.
Sorry Random but if you can't crack a real hash you got nothing. I already gave you a break a breaking into the box to get it. On a secure system you would have password timeouts from failed passwords to. I don't store my passwords in plain text or without salts. You've confirmed that you can't actually break into a system that's otherwise locked up tight just because of a smaller number of possible passwords (and that's assuming you knew it was a smaller number, you wouldn't know). Thanks for proving my point.
ReplyDeleteI'm closing this because I can't imagine anyone has anything useful to add (that hasn't been said). If you do pm me on freenode or irc.perl and I'll reopen
ReplyDelete