jgreely@cis.ohio-state.edu (J Greely) (11/27/88)
In article <274@aber-cs.UUCP> pcg@cs.aber.ac.uk writes: >In article <13169@ncoast.UUCP> allbery@ncoast.UUCP writes: > A possible enhancement is to use phonemes instead of letters, thus > increasing the chances of a pronounceable password. It could be combined > with a phoneme-to-letter table which could randomly (or maybe not so > randomly, depends on how much time I want to put in it) choose between > alternative representations (f/ph, etc.) of a phoneme. The posted version of this (pwgen, in comp.sources.misc, natch) doesn't quite work. I sent the minor changes to Brandon. The generated words sound nothing like English, but they *are* pronouncable (mostly). >As has been discussed at length and conclusively, generating by algorithm >menmonic passwords is a very bad idea, because: >[1] It restricts unconscionably the key space (usually to a few thousand >or at best dozen thousand entries). Well, after fixing the minor bugs in pwgen, I'm not terribly worried about the key space: % pwgen 9 500000 | sort | uniq | wc -l 482718 The percentage of unique passwords seems to drop at a fairly constant rate as you raise the number generated, but at 500000 it's still over 96%. It would require more testing to see just how many unique strings it's capable of generating, but that's for another day. >[2] If the algorithm used to generate the passwords get known, it can be >used to obtain a complete list of all possibly passwords. Naaah. The patch I sent to him suggested adding a switch to randomly upcase letters, as well as replace letters with numbers ('l' -> '1', 'o' -> '0', etc). If 8-character passwords are chosen, modified by these transformations, the key space is more than sufficient. -- J Greely (jgreely@cis.ohio-state.edu; osu-cis!jgreely) Unseen, in the background, Fate was quietly slipping the lead into the boxing glove.
pcg@aber-cs.UUCP (Piercarlo Grandi) (11/27/88)
In article <28399@tut.cis.ohio-state.edu> jgreely@cis.ohio-state.edu (J Greely) writes: >[1] It restricts unconscionably the key space (usually to a few thousand >or at best dozen thousand entries). Well, after fixing the minor bugs in pwgen, I'm not terribly worried about the key space: % pwgen 9 500000 | sort | uniq | wc -l 482718 The percentage of unique passwords seems to drop at a fairly constant rate as you raise the number generated, but at 500000 it's still over 96%. I used the word unconscionably, and for good reason :-(. Assume that a nice system administrator uses your 500,000 figure. Assume somebody decides to DES all of them, say one every millisecond. In less than 500 seconds (say 15 minutes, including delays etc...) he has broken ALL the passwords on your system. Interesting... :-) :-) Consider also the fact that pwgen must eventually cycle. For all you know, the cycle is exactly 482718 elements long, and after that passwords start repeating. Maybe yes, maybe not. Also, there being a cycle, there must be a point at which the number of duplicates raises linearly. When you have got 50% duplicates, this just means that you have just run thru the second cycle. Note also that duplicates are not the whole story; there may be no duplicates, but the key space is still highly structured, and in a known way. It would require more testing to see just how many unique strings it's capable of generating, but that's for another day. The point is that security is not a something where you test; you PROVE, or you make a convincing mathematical analysis using the best tools of statistics etc... >[2] If the algorithm used to generate the passwords get known, it can be >used to obtain a complete list of all possibly passwords. Naaah. The patch I sent to him suggested adding a switch to randomly upcase letters, as well as replace letters with numbers ('l' -> '1', 'o' -> '0', etc). If 8-character passwords are chosen, modified by these transformations, the key space is more than sufficient. It has been argued forcefully that even the 2^56 keyspace of fully random DES is too small; somebody posted that an exhaustive generation of all possible keys encrypted by login is already a feasible thing to do. All algorithms that do generate "random" passwords lop off a LOT of the 56 bits of the key space. So much the worse if the "random" selection is based on fairly restrictive rules. The resulting key space may be larger than a few dozen thousand entities, but will most likely be small enough to be easily attackable, especially as it is known that it is highly structured, i.e. not random at all. A good codebreaker uses the regularity of natural language as a powerful tool; an algorithm as the source of the signal to decode is just too good to be true, especially if it is highly predictable. Manual password generation may be weak, but at least it is less predictable. My own opinion is that the worse security risk is a false sense of security and a "random" password generator is one of the best tools to achieve this. If a reasonable and articulate and competent person like Mr. Greely still feels like giving an example with a number like 500,000 for a reasonably large key space, and may be prepared to trust a site's security to it, I shudder thinking of what less prepared people might come up with. -- Piercarlo "Peter" Grandi INET: pcg@cs.aber.ac.uk Sw.Eng. Group, Dept. of Computer Science UUCP: ...!mcvax!ukc!aber-cs!pcg UCW, Penglais, Aberystwyth, WALES SY23 3BZ (UK)
smb@ulysses.homer.nj.att.com (Steven M. Bellovin) (11/29/88)
In article <278@aber-cs.UUCP>, pcg@aber-cs.UUCP (Piercarlo Grandi) writes: > somebody posted that an exhaustive generation > of all possible keys encrypted by login is already a feasible thing to > do. Let's look at this quantitatively. There are, more or less, 95 printable characters. We'll subtract 2 for @ and #, which many UNIX systems still use for line kill and erase. If we consider just 8-character passwords, that means there are 93^8 possibilities, or 5,595,818,096,650,401. Each one can be encrypt 4096 different ways, given the salt; this leaves us with 22,920,470,923,880,042,496, but if you're trying to attack one particular password, as opposed to password fishing that number isn't relevant. So we'll look at the smaller number, which I trust you'll let me abbreviate as 5.6e15. Let's assume you can do an encryption in 1 microsecond (which is ~4 orders of magnitude better than any claims I've seen for a VAX 8600). Let's further assume that you're doing this on some small cheap machine, so that you can put 1000 of them to the task. That means that you can try 10^9 passwords/second, so it should take you 5.6e6 seconds to crack my password that way, or ~65 days. More realistically, you're not going to manage that speed any time soon, especially not on that many machines. If your encryptions take even 10 microseconds -- still 1000 times the best speed reported for an 8600 -- my password is safe for 2 years. I change it more frequently than that... Using a more restricted character set helps the cracker a lot. Under the same wildly-optimistic speed assumptions as before, a password of only upper- and lower-case letters would take just .6 days to crack, which is indeed worrisome. A cracker on a lone 8600, using today's technology, would need 6 million days. Clearly, we can't be that optimistic. Assume, for example, a worm that devoted all the power of the penetrated machines to attacking one password. The Internet is estimated to contain 60,000 machines; let's assume that each one could be infected, and each one could check a password in 100 microseconds. That means 6e8 trials a second, for just over a day to check all possibilities. This number isn't that insane; we postulate a 5-fold improvement in the algorithm, and a 20-fold improvement in CPU power, in a widely available form, is almost here now. And if the Internet keeps growing, our next wormer may have something useful to do with all that CPU power! Note that precalculating all these passwords doesn't work. First, you'd need to multiply the number of possibilities by 4K, because of the salt; second, CPUs can calculate data much too rapidly for even optical disks to keep up. Again, 52^8 choices, times 4096 encryptions, times 8 bytes for the output data maximally packed, yields 1,751,768,384,518,750,208 bytes. We'll assume that the salt used and the cleartext password are calculable from the position of the result, which probably isn't true if you organize the file for rapid searching... What can we conclude? First, for 8-character passwords, today's algorithms are good enough for now. Second, that they won't be forever; in 10 years, some of these numbers will start to look worrisome. Third, using a larger input character set expands the search space beyond the forseeable trouble range. --Steve Bellovin
jgreely@cis.ohio-state.edu (J Greely) (11/29/88)
In article <278@aber-cs.UUCP> pcg@cs.aber.ac.uk writes: >In article <28399@tut.cis.ohio-state.edu> jgreely@cis.ohio-state.edu (J Greely) writes: > [quick test showed at least a half-million possible strings from > Brandon's "pronouncable" password generator] >I used the word unconscionably, and for good reason :-(. Assume that a >nice system administrator uses your 500,000 figure. The half-million was quoted simply because it took only a few minutes to generate. The "sort | uniq" was getting a bit unwieldy at that point. I haven't had time to really study the method used, beyond noting that it does attempt to generate random strings with lots of vowels (although "oo" is *far* too popular). As is, I would not attempt to force every user here to use it (fat chance they'd listen to me, anyway), but as soon as I am sufficiently convinced of its efficiency, I have no problem pointing it out as an option. I'd rather have people using a random string from a known algorithm than something from /usr/dict/words. It may not be completely safe, but it has the advantage of not being *online*. Quick example: the infamous worm never got here, but I tested our passwd files against the 432 strings it used. 32 out of 2000 accounts were broken, including 2 staff accounts. So, when I'm convinced that this or some other algorithm generates a reasonably large number of pronouncable, non-English words (and I convince the rest of the staff :-)), I'll be happy to add it as an *option*. If I could convince them to roll a set of Boggle(TM) dice, I'd try that, too. > Assume somebody >decides to DES all of them, say one every millisecond. In less than 500 >seconds (say 15 minutes, including delays etc...) he has broken ALL the >passwords on your system. Interesting... :-) :-) Pretty fast crypt. Remember, password encryption is 25 times slower than normal DES (unless you know something about multiple encryption with the same key that I don't). And for a quick back-of-the-keyboard calculation, 500000 * 11 * 4096 / 1024^3 is almost 21 *giga*bytes, just for the ciphertext. Now that you know you broke it, you still have to have the original text somewhere to find out what the password is. Messy. For those who don't know where the 4096 came from, Unix password encryption changes DES in one of 4096 ways before encrypting (the "salt"), raising the effective key size to 68 bits, at the possible cost of some of the algorithm's strength. >Consider also the fact that pwgen must eventually cycle. Can't avoid this with any password generation system. If you use any one system, you decrease your security drastically, no matter how secure that one system is. However, if, in my list of "ways to make a good password", I include a random string generator (whether it be pwgen, travesty, or dissociated press), some people will try it, find something they like, and use it. Better that than "password", or their username. >It has been argued forcefully that even the 2^56 keyspace of fully >random DES is too small; somebody posted that an exhaustive generation >of all possible keys encrypted by login is already a feasible thing to >do. Feasible? 'scuse me a moment. 2^56 * 4096 * 11 / 1024^3 > 3 * 10^12 gigabytes of storage for the whole thing. Consider that when you're generating these, they have to be compared to your target passwords. If your target list is small enough, you can (encrypt,compare,throw out), otherwise you'll have to store them somewhere (a few pieces at a time). No doubt it can be done, but the effort required is not cost-effective for cracking most systems. >Manual password generation may be weak, but at least it is less >predictable. Well, sort of. Human nature is *very* predictable. When I tested here for people using either their username or part of their full name ("joes"), I was not surprised to find several. When I tested the worm list, I was not surprised to find more (in fact, some of the accounts broken pointed out a much larger security problem, which shall remain nameless :-)). >My own opinion is that the worse security risk is a false sense of >security and a "random" password generator is one of the best tools to >achieve this. I'm not going to argue this one. "Well, Mr. Upperclass Management Person, we've increased our security by requiring all employees to use randomly generated passwords, to prevent them from choosing easy-to-remember words. Now they must use company-assigned passwords, and guard them with their worthless lives." I'd be the first person to raise hell if something like this was tried, particularly in a university environment. >If a reasonable and articulate and competent person like Mr. Greely (mind if I show this part to my boss?) -- J Greely (jgreely@cis.ohio-state.edu; osu-cis!jgreely) Unseen, in the background, Fate was quietly slipping the lead into the boxing glove.
bzs@encore.com (Barry Shein) (11/30/88)
>Let's look at this quantitatively. There are, more or less, 95 >printable characters. We'll subtract 2 for @ and #, which many UNIX >systems still use for line kill and erase. If we consider just >8-character passwords, that means there are 93^8 possibilities, or >5,595,818,096,650,401. Each one can be encrypt 4096 different ways, >given the salt; this leaves us with 22,920,470,923,880,042,496... >...If your encryptions take even 10 microseconds -- still 1000 times the best >speed reported for an 8600 -- my password is safe for 2 years. >What can we conclude? First, for 8-character passwords, today's algorithms >are good enough for now. Second, that they won't be forever; in 10 years, >some of these numbers will start to look worrisome. Third, using a larger >input character set expands the search space beyond the forseeable trouble >range. > > --Steve Bellovin Round of applause! I consider this a good argument to support my claim that shadow password files are basically an idea barking up the wrong tree. Choosing good passwords is both necessary and sufficient for reasonable security. If your users choose good passwords then hiding a passwd file is unnecessary. If your users choose bad ones than you better pray before you go to sleep every night that no one walked out with a copy of your passwd file, protected or not. If people leave their office/home/car keys lying around no one should be shocked if they walk away and later their property is found burglarized. If people resist choosing good passwords then the same can be said. Just as leaving keys around often endangers everyone (eg. outside entrance keys are often present allowing intruders into the building, stolen cars often end up in accidents on joy rides etc) so can passwds left "lying around" (eg. easy to crack.) On a system I managed a while back I would occasionally try to break the passwords by use of a program and, when I broke one, would send a mail message to the owner that went something like: Your password on this system is trival to break, I broke it with a readily available program in (time value.) Please choose a more reasonable password (seven or more characters, not an english word or name, at least one punctuation mark and preferably a mixture of upper/lower case and/or digits.) If you need help with this don't hesitate to ask one of the staff. If you choose to continue to use an easy to break password please do not bother the staff to restore files or undo other damage which might be done to your account. Since it wasn't important to you it will not be important to us. Note also that an intruder can disrupt and destroy others' work, if such an intrusion is traced to your bad choice of password the entire user community will be informed of this. Please excuse the tone of this letter but it is a serious matter. A program to demand a decent password might be an improvement, I'm mixed on the issue of individual responsibility vs trying to cram good behavior down people's throats with software but given the possible ramifications to the entire community it has its merits, besides, what consititutes a "good" password might be confusing to some. -Barry Shein, ||Encore||
dhesi@bsu-cs.UUCP (Rahul Dhesi) (11/30/88)
In article <10896@ulysses.homer.nj.att.com> smb@ulysses.homer.nj.att.com (Steven M. Bellovin) writes: [some calculations] >If your encryptions take even 10 microseconds -- still 1000 times the best >speed reported for an 8600 -- my password is safe for 2 years. I change >it more frequently than that... Not quite. Your password is safe for two years against a certain attack, for one year against an attack with a 50% chance of success...etc. Consider the claim: "Give me a week, and there's a 1% chance that I will break into your account." If the person keeps trying week after week, he will likely break into your account after two or three years of trying. No matter how often you change your password. No matter how often your change your password! I don't like the sound of that. (I do realize that your calculations were too conservative by a large factor.) -- Rahul Dhesi UUCP: <backbones>!{iuvax,pur-ee}!bsu-cs!dhesi
lm@snafu.Sun.COM (Larry McVoy) (11/30/88)
Steve wrote: >>Let's look at this quantitatively. There are, more or less, 95 >>printable characters. We'll subtract 2 for @ and #, which many UNIX Barry said: [wonderful] Jeez. This sounds awful. Try this instead, you'll like it better. Add a field somewhere (/etc/failures?) that records the number of failed attempts. If it reaches some maximum, disallow logins with some message like: ("Possible security risk: %d failed attempts\n", failed) If the failed number is greater than MAXFAIL/2, then warn the user that he ought to reset his password (to anything, including what it was). Resetting would clear the failed field. Now that I think about it, you could print out the number of failed attempts to date at login time. Users would know right away if someone had been beating on their account. Wouldn't this be a much easier and more palatable way to solve the problem? Larry McVoy (lm%snafu@sun.com)
james@tcom.stc.co.uk (James Rouse) (12/01/88)
Larry Mcvoy writes:- >Add a field somewhere (/etc/failures?) that records the number of >failed attempts. If it reaches some maximum, disallow logins with >some message like: > ("Possible security risk: %d failed attempts\n", failed) >If the failed number is greater than MAXFAIL/2, then warn the user that >he ought to reset his password (to anything, including what it was). [stuff deleted] > >Wouldn't this be a much easier and more palatable way to solve the problem? No because (unless you have a shadow password file :-) see below) to try a password you simply get the encrypted version from etc/passwd,encrypt your guess and compare the two. The number of attempted logins to your name has nothing to do with this. If however etc/passwd was unreadable to the world then this method of attack would be ruled out. You wouldn't need a shadow passwd file then either. The one thing that seems to have been assumed in this argument is that de-encrypting passwords is impossible. It may be very difficult, but if people are talking about using a mainframe to encrypt the dictionary (!) and grep the password file why is everyone so sure that a mainframe cannot be used to reverse the encryption routine?
bzs@encore.com (Barry Shein) (12/02/88)
>If the failed number is greater than MAXFAIL/2, then warn the user that >he ought to reset his password (to anything, including what it was). >Resetting would clear the failed field. Now that I think about it, >you could print out the number of failed attempts to date at login time. >Users would know right away if someone had been beating on their >account. > >Wouldn't this be a much easier and more palatable way to solve the problem? > >Larry McVoy (lm%snafu@sun.com) It's not a bad idea and doesn't complicate/change the user interface but I think the concern was folks taking away your password file and running attempts on their own machine. Once, outside the 7-mile limit and many years ago, a friend recoded V7 crypt in tight assembler and broke the root password on the system "upstairs", fixed a few kernel bugs we'd been bitching about and rebooted the system. The reactions were mixed, tho folks seemed to like the improvements to the terminal driver :-) -Barry Shein, ||Encore||
jfh@rpp386.Dallas.TX.US (The Beach Bum) (12/05/88)
In article <711@jura.tcom.stc.co.uk> james@htc2.UUCP (James Rouse) writes: >Larry Mcvoy writes:- >>Add a field somewhere (/etc/failures?) that records the number of >>failed attempts. If it reaches some maximum, disallow logins with >>some message like: >> ("Possible security risk: %d failed attempts\n", failed) >>If the failed number is greater than MAXFAIL/2, then warn the user that >>he ought to reset his password (to anything, including what it was). >> >>Wouldn't this be a much easier and more palatable way to solve the problem? There have been other arcticles explaining why this is such a bad idea. > No because (unless you have a shadow password file :-) see below) to > try a password you simply get the encrypted version from etc/passwd, > encrypt your guess and compare the two. The number of attempted logins > to your name has nothing to do with this. No. This mechanism presumes the Bad Guy doesn't have access to the encrypted password file. Breaking a UNIX system involves having a valid login name. root is a standard account, along with bin, adm, etc. Illegal attempts on those accounts are indicative of someone trying to break into the machine. This is also why you should never have an account `who' which gives a `who' without a password. You will notice that I don't follow my own advice on this point ... > If however etc/passwd was unreadable to the world then this method of > attack would be ruled out. You wouldn't need a shadow passwd file then > either. Making /etc/passwd unreadable more likely than not will break /bin/ls. Not a nice tradeoff. Having /etc/shadow allows the encrypted password to be protected someplace else. It should also alert you to the importance of physical security. If the Bad Guy has access to the dump tapes, he can surely add trojans to the tape, or duplicate the tape with trojan accounts or files included. You can't just chmod 400 /etc/shadow and expect your system to be secure. > The one thing that seems to have been assumed in this argument is that > de-encrypting passwords is impossible. It may be very difficult, but if > people are talking about using a mainframe to encrypt the dictionary (!) > and grep the password file why is everyone so sure that a mainframe > cannot be used to reverse the encryption routine? The former is much simpler than the later. I can encrypt a dictionary on an unused PC running UNIX. Trying to reverse [ brute-force decrypt is more like it ] a password on a PC would take significantly more time than you or I have on this earth. -- John F. Haugh II +-Cat of the Week:--------------_ /|- VoiceNet: (214) 250-3311 Data: -6272 |Aren't you absolutely sick and \'o.O' InterNet: jfh@rpp386.Dallas.TX.US |tired of looking at these damn =(___)= UucpNet : <backbone>!killer!rpp386!jfh +things in everybody's .sig?-------U---
norstar@tnl.UUCP (Daniel Ray) (12/06/88)
In article <9119@rpp386.Dallas.TX.US>, jfh@rpp386.Dallas.TX.US (The Beach Bum) writes: > > and grep the password file why is everyone so sure that a mainframe > > cannot be used to reverse the encryption routine? > > The former is much simpler than the later. I can encrypt a dictionary on > an unused PC running UNIX. Trying to reverse [ brute-force decrypt is > more like it ] a password on a PC would take significantly more time than > you or I have on this earth. > -- > John F. Haugh II +-Cat of the Week:--------------_ /|- Correct me if I'm wrong, but I recall reading one of the old UNIX abstracts (in the back of "UNIX System Security" by Wood & Kochan, Hayden Books) that states that the crypt() routine IRREVERSIBLY encrypts a password. As a trivial example: lets say we encrypt the alphabet..A is mapped to B, B to C, C to D, etc, except that both Y and Z are mapped to Z. The encrypted text of the word "ZOO" would be "ZPP". Easy to do. However, by knowing that the ciphered text is "ZPP", can one reverse it? No, because both "ZOO" and "YOO" encrypt to that. I thought crypt() was like this in a much more sophisticated way, and that there exists the remote but theoretical possibility of password collision (two different passwords encrypting to the same string using the same salt). Is this true, or am I all mixed up :@) !! norstar The Northern Lights, Burlington Vermont | tnl dialins: 802-865-3614 at 300-2400 bps. ` | / ------------------------------------------ --- * --- uucp: uunet!uvm-gen!tnl!norstar or / | . {decvax,linus}!dartvax!uvm-gen!tnl!norstar |
jc@minya.UUCP (John Chambers) (12/06/88)
> If a reasonable and articulate and competent person like Mr. Greely > still feels like giving an example with a number like 500,000 for a > reasonably large key space, and may be prepared to trust a site's > security to it, I shudder thinking of what less prepared people might > come up with. No need to wrack your brain thinking about this; just get an account at any bank with an ATM. I've yet to hear of one that uses a password (i.e., a PIN) that is more than a 4-digit number. Some banks even refuse to use PINs that do things like repeat digits, thus decreasing the search space even further. (Oh, well, it's just money. :-) -- John Chambers <{adelie,ima,maynard,mit-eddie}!minya!{jc,root}> (617/484-6393) [Any errors in the above are due to failures in the logic of the keyboard, not in the fingers that did the typing.]
gwyn@smoke.BRL.MIL (Doug Gwyn ) (12/07/88)
In article <120@tnl.UUCP> norstar@tnl.UUCP (Daniel Ray) writes: >However, by knowing that the ciphered text is "ZPP", can one reverse it? >No, because both "ZOO" and "YOO" encrypt to that. For purposes of obtaining a usable password, either would do.
waters@polya.Stanford.EDU (Jim Waters) (12/11/88)
In article <147@minya.UUCP> jc@minya.UUCP (John Chambers) writes: >No need to wrack your brain thinking about this; just get an account >at any bank with an ATM. I've yet to hear of one that uses a password >(i.e., a PIN) that is more than a 4-digit number. Some banks even >[Any errors in the above are due to failures in the logic of the keyboard, >not in the fingers that did the typing.] Actually, I have a 7 digid "secret number," and I believe that 9 is the limit. We go to the bank to choose them, so no one else ever sees the number. --------------------------------------------------------------------------- Jim Waters internet: waters@umunhum.stanford.edu USPS: P.O. Box 13735 waters@argus.stanford.edu Stanford, CA 94309 uucp: ...decwrl!umunhum.stanford.edu!waters AT+T: (414)326-0229 bitnet: waters%umunhum.stanford.edu@stanford What's that? Don't I have anything really profound to say here . . . Nope.
jik@athena.mit.edu (Jonathan I. Kamens) (12/12/88)
In article <5598@polya.Stanford.EDU> waters@polya.Stanford.EDU (Jim Waters) writes: >Actually, I have a 7 digid "secret number," and I believe that 9 is the limit. >We go to the bank to choose them, so no one else ever sees the number. Ay, there's the rub.... My bank (BayBanks Boston) allowed me to choose a 7-digit security code as well. However, if you watch really closely when typing the 7-digit code into a BayBanks machine, the screen will flash momentarily after the fourth digit is entered. Well, boys and girls, can you guess what that means? Yes, that's right, the BayBanks machine is only listening to the first four digits! In fact, if you press the enter key after only the first four digits, the machine merrily accepts your PIN. Moral of the story: are you *sure* that all seven digits of your PIN matter to the machine? (This really has nothing to do with unix. Sigh.) Jonathan Kamens MIT Project Athena
ok@quintus.uucp (Richard A. O'Keefe) (12/12/88)
In article <147@minya.UUCP> jc@minya.UUCP (John Chambers) writes: >No need to wrack your brain thinking about this; just get an account >at any bank with an ATM. I've yet to hear of one that uses a password >(i.e., a PIN) that is more than a 4-digit number. I had a Versatel card (Bank of America) and my PIN was 10 characters.