Algorithm for User-friendly Password Policy Jorge Hernández Liang Master in Computer Science Dr. Alfredo Cruz Electrical & Computer Engineering and Computer Science Department Polytechnic University of Puerto Rico Abstract  Password based security has become the new scheme hopes to undo certain forms of prevalent as the de facto measure against intrusion. conditioning present in many current passwords. Computer systems rarely focus on usability, and The new system borrows some strategies found little research has been done to change the current, in previous NIST publications [1] in using entropy near universal method of implementation. This as a metric for the value of characters, but changing paper explores the weaknesses found in password the way the value of characters and bonuses is based systems and how they can be mitigated. This calculated, as well as adding a way to calculate will conclude with a new set of algorithms for minimum levels of uncertainty required to accept a validating passwords and creating baselines for password. This allows the user to negotiate the setting minimum required strengths for password contents of their password, including length and defense. This new metric allows for a wider diversity in character categories. The new scheme diversity of possible passwords while maintaining also allows users to generate passwords that far security by assigning value to certain surpass requirements to allow for longer duration of characteristics and requiring a minimum amount of use, achieved by requiring complexity gains beyond security be achieved before accepting the password the additionally granted lifetime. instead of relying on static requirements in minimum length and presence of character types. COMMON PASSWORD CRACKING The new approach embraces password diversity WEAKNESSES and allows for trade-offs of different password In order to understand what improvements elements in order to allow users to use a wider need to be performed when creating our new array of strategies at the moment of generating password scheme, it was important to understand their passwords. the common vulnerabilities that are exploited in Key Terms  Computer Security, Passwords, password attacks? The primary issues that are Privacy, Usability. exploited are length and predictability of characters, both of which are easily addressed by changes to INTRODUCTION password requirements. Passwords are a scheme in which users are The clear example of where length is an issue granted authorization to access specific information with passwords is observable in bruteforce or systems by providing a specific string of password guessing attacks. These attacks characters. They have become ubiquitous in our exhaustively attempt to verify the password lives, but are also frequently exploited for common keyspace (every possible combination of characters weaknesses. This paper explores a new approach to that can legally form a password). Due to the password security by presenting a new scheme for exponential growth nature of password space, password requirements. This new system adopts a increasing either length or characterspace (all variable password strength minimum based on possible characters usable in the password) even expected threats as well as multiple ways to reach small increases will have a significant effect on the those strength requirements. By not forcing the user complexity of the password. This can be seen in to implement specific rules within their passwords, Table 1, where we display a chart of keyspaces based on what characters are present and the length of the password. This table shows the rapidly Predictability proves to be an issue for growing nature of passwords. The left column, password systems due to it reducing the representing the base number of the exponential randomness that is inherently critical to password growth, has a significant impact as it grows. Even based security. It is harder to address, but we can the smallest growths in the amount of available attempt to understand how it came to be and avoid characters has an impact of orders of magnitude repeating those mistakes. In a previous study [2], it when looking at the rate of growth for password was learned that the characteristics of user keyspaces. The middle block of the column builds passwords is reflective of common password off of the left characterset size column by requirements and manifest in similar ways across explaining how each size is constructed, using the many users. The same study also presents evidence different character types as groups (Digits in that user diversity could lead to password diversity decimal or hexadecimal form, singlecase or mixed when freedom is allowed at the time of password case letters, standard keyboard special characters, generation. and ASCII characters) which are then summed up Passwords are often presented as requiring at to provide the characterset size. Finally, the least 8 characters, both upper and lower-case rightmost block serves the primary purpose of the characters, and the presence of either numbers or table by displaying the password keyspace created non-alphanumeric characters. This is shown by by those different charactersets using different passwords consisting of at least 8 characters in password lengths. These are all presented in most users and frequently meeting the requirements scientific notation as the order of magnitude proves through the presence of an uppercase character in to be critical component, since many of these the first character of a password and the insertion of charactersets grow very quickly. It is also important a special character at the end of the string of text. to note that their rate of growth increases faster on For example, replacing “password” with the lower rows due to having a much larger “Password1”. This conditioning can be referred to characterset, and therefore a larger base number for as “Pavlovian Passwords” due to similarities to the exponential growth. classical conditioning [3]. Table 1 NIST Keyspace Cardinality Calculations Reprinted courtesy of the National Institute of Standards and Technology, U.S. Department of Commerce. Not copyrightable in the United States. Figure 1 Submitted Password Lengths From here, strict password rules have led to the that demographic information plays on the provided issue of predictability and therefore we must avoid password characteristics. repeating the mistake in future attempts to craft Several conclusions were found such as gender password rules. influencing length of the password, employment and education background influencing the overall PREVIOUS WORK strength, and other factors such as primary language being less significant. As mentioned, the author had performed a Another finding was that the average password related previous study on password based security length of the participants was higher than [2] that demonstrates some useful information for previously recorded averages found, which seems this topic. The study consisted of an experiment to be consistently increasing as time goes on. This were users provided sample passwords through a effect might be amplified within this study as survey that was answered by university students. participants were relatively young, being composed The survey consisted of requests for non-personally of university students. The distribution of their identifying demographic information, such as age password lengths can be seen in Figure 1. The range, primary language, gender, and if they had a significant points of information in this graph are work/study background in technology. They were the low frequency of short passwords. The shortest also asked to provide a mock password, but were instance of password length was 6 characters long, not given any restrictions as to the contents of the and was not very common as a password length. password. (The results of the survey can be It’s mode of 9, with 10 characters being a close observed in Figure 1.) The passwords were second also brings positive information, as these checked for several characteristics. The passwords appear close to the leftmost edge of the values and were then placed in to categories based on their are also very close to the average of password relative strength levels using traditional criteria. lengths. The average itself also gives information, The users themselves were also grouped based as the length of over 14 characters on average on provided demographic information. This continues the trend of increasing password lengths allowed for the verification of the level of influence as time goes on [2]. PREVIOUS ATTEMPTS AT STANDARDS PASSWORD RESILIENCE TESTS There have been two significant attempts to In order to demonstrate how the passwords standardize the realm of password generation, one execution times grow quickly when the keyspace is by the Department of Defense [4] and again by the altered and how quickly even minor changes have National Institute of Standards and Technology [1]. an impact on execution time, it becomes necessary The first mentioned was the Department of Defense to demonstrate the runtime with concrete examples. Password Management Guideline (also known as A series of tests were run to calculate CSC-STD-002-85 or simply as “The Green Book”) execution time of brute force attacks on a computer [4]. This text contains many of the with hardware and software representative of what recommendations observed today for password might be used by a common password cracker at management, such as the recommendation of the time of execution. The specifications for the passwords being replaceable by the user and that computer were as follows: they should not be written down or re-used. The  Intel Core i5 6600K CPU. rule for minimum length of 8 may also have  MSI Z170A Motherboard. originated from one of the examples presented in  16GB Dual Channel DDR4 RAM at 3,000 the text and was simply never updated as MHz speed. technology grew. This highlights the issue of non-  NVIDIA GeForce GTX 1070 GPU (999 MHz evolving standards for passwords, which is clock, 8192 MB GDDR5 memory, 1920 particularly critical in the constantly evolving CUDA cores, Driver ver. 376.33). environment of computers, were hardware is  Windows 10. constantly changing and the speed to compute these  Hashcat V3.2 Password Cracker (MD5 passwords is quickly being reduced. Algorithm). The NIST attempt came in their special publication 800-63-2: Electronic Authentication The tests were computed on passwords Guideline. Here they try to use as a base the representative of real world scenarios such as concept of Shanon Entropy (a measurement for Amazon password requirements (6 character, both unpredictability) to create a variable scheme for upper and lowercase), Facebook requirements (6 password approval. According to this document’s characters), common password requirements such strategy, characters would add a certain number of as minimum 8 characters (both any capitalization bits of entropy (unpredictability or randomness) and mixed) as well as for other reasons such as based on their position, with bonus bits being being resilient to specific methods of attack and awarded to the password based on fulfilling more. The primary distinction for character sets is addition criteria such as having a mix of upper and seen in the name of each group. Categories lowercase characters. This scheme is conceptually identified as Basic# require only 1 letter case, solid, helping to solve some of the presented issues, Complex# requires both uppercase and lowercase, but it does present some shortcomings. There is no and a special character or number. This is in presented way to calculate a minimum acceptable addition to length requirements, which is the level of randomness for a password, the calculation number in the category name. for level of randomness based on position of The results of these tests can be seen in Table characters is not currently supported by established 2. Where the estimated execution time for an research, and there is no incentive for users to exhaustive attack on those spaces is shown. create a password beyond the minimum required to The result of these is showing that there are be considered acceptable by the system. clear breakpoints where there are significant gains, enough to add a margin of safety beyond the successfully finding the password is the primary minimum requirement. goal of this scheme. Many of the simple requirements have short The first issue that can be addressed is length, execution times on current hardware, whereas the setting a minimum length that prevents the more complex requirements presented a rapid practicality of a brute force attack or its variants increase in length. allows the password to perform its most basic The results show that both the inclusion of function. For this reason, the password must adhere diverse character sets and length add significant to a minimum length even in a worst-case scenario amounts of security. Their combined effects where the character complexity is at a minimum. produce a rapid growth that helps greatly with Lowercase character only passwords, however, difficulty at guessing the chosen string. With are not necessarily a given. Many users can simple character sets such as only lowercase implement passwords that have a wider range of characters, there is an acceptable strength, taking characters and that should be rewarded as it approximately 414 days to exhaustively search the provides significant additional security. For this password space in our tests, but increasing from 16 reason, passwords with lesser length but more to 21 characters drastically improves the search complexity should also be allowed. These tradeoffs time to approximately 1156. Similarly, when using must be offered to prevent the case of Pavlovian a complex character set such as all uppercase, passwords mentioned previously. The added lowercase, numbers and non-alphanumeric leads to security can manifest as both mixed character execution times of a few seconds at 8 characters in capitalization and the presence of numbers and non- length, but provides similar security to the Basic21 alphanumeric characters, all of which should be results at approximately 1166 days for the treated as separate cases. Although, it is important exhaustive search. to always maintain that the increase in security should be comparable or greater than the loss in Table 2 Runtime Estimates security from predictability. To avoid abuse in Complexity Runtime (in days) extreme cases, it becomes beneficial to treat these Amazon 0 benefits with diminishing returns to maintain a minimum length expectation. Facebook 0 Users should also be encouraged to go beyond Basic8 .0001 a minimum requirement expectation for safety, Complex8 1.3 unfortunately previous attempts to force this have Basic11 2.3 resulted in the mentioned predictability [2] and Basic16 414 therefore an optional reward system can be Complex10 1166 embraced to replace the approach. As part of the Basic21 1156 system, providing a significant security increase beyond the minimum required can be rewarded with increased password lifespan before it expires. GOALS FOR GUIDELINES Commonly accepted wisdom is that a 3-month The basis for password security is expiration time is acceptable. Increments can be unknowability and unpredictability. By requiring placed at 3 month intervals for additional time, but information accessible only to legitimate users, it this added time should be maxed out to around 1 becomes impossible for attackers to gain access year total length to avoid abuse in extreme cases. without coming across the password by chance. Once again, the added security should outweigh the Restoring this state of unpredictability and loss of safety, which is simplified by the minimizing the possibility of an attacker exponential growth of the password keyspace and linear growth of time, but it should still be following set {`~!@#$%^&*()- monitored and implemented on a case-by-case _=+[{]}\|:;"'/?.>,<} minus any characters basis. that could be dangerous to include in the It is also important to verify that the password character space. has not been discovered in a previous attack. Many  Inclusion of numericals in addition to leaked password lists have been published online, alphabetic characters adds 2 points of entropy and while it may not be ethical to view them in  The bonuses for the inclusion of mixed cases, detail, it should be embraced to check the lists for numerals and non-alphanumerics is reduced by the presence of the submitted password. This 2 for each bonus added after the first. knowledge could be detrimental for any attempted o For example: Including mixed cases and attacks since the leaked information is often used to non-alphanumerics is 8 points. (6 (Cases) execute the tactic. Another common tactic is to + 4 (Non-Alphanumerics) - 2 (multiple attempt dictionary words as passwords, along with bonuses) ) minor variations and simple substitutions such as  Passing a comprehensive dictionary check adds capitalizing the first letter or replacing the letter ‘e’ a value of 6 points of entropy. with a ‘3’. A simple dictionary check can be o The password should be checked with a performed at the moment of submission and sufficiently large dictionary, at least passwords should be given preference for not 50,000 words. Replacing the uppercase failing the comparison check. Those checks should characters with lowercase equivalents for also be performed with the simple substitutions in consistency and it should not contain any mind. Where possible, they should be reverted, of those words as a substring. Passwords such as placing all the letters in their lowercase found to be consisting of permutations of form so that the scan is case-insensitive for easy of the username are also considered to fail verification. this test. From these criteria, the rules for password  Password tests to find currently acceptable acceptance can be built, the explicit rules for which entropy thresholds should: can be stated as follows:  Be performed on current high-performance All passwords begin with a base value of 0 consumer accessible hardware. points of entropy.  Be performed periodically and in accordance  Each Character adds 2 points of Entropy. with changes to hardware landscape.  Inclusion of both uppercase and lowercase  Be performed using all valid characters. characters adds 6 points of entropy.  A baseline minimum entropy threshold should  Inclusion of numericals in addition to be calculated based on a length that takes at alphabetic characters adds 2 points of entropy. least 6 months to complete exhaustively.  Inclusion of non-alphanumeric characters adds  Password lifetimes should default to three 4 points of entropy. months, with an additional three months o Non-alphanumeric characters are allotted per 6 points of entropy exceeded when recommended to be limited to printed compared to the minimum. keyboard characters consisting of the o Absolute maximum allotment of a year. Table 3 Entropy Calculation Example Table 4 Password Examples EXAMPLE OF USE FOR CALCULATION OF This allows for a wide variety of passwords to B V be implemented. Table 4 shows a list of example ASE ALUES passwords generated in assorted styles and Test should be performed using whatever strategies. Each of the provided examples shows algorithm will be used for hashing the passwords, possible password that can be generated, all of them in this example it will be performed using SHA258 entropy equivalent, in several different styles. This on the computer used in the previous example. For includes traditional password/phrases, Acronym tradition and convenience, the example will begin passwords (representing a phrase using specific with an initial value of 8 characters. The rules are characters to replace words), pronounceable set for the ‘?a’ rules present in Hashcat, which passwords (That seek to emulate traditional words includes all valid character types (uppercase, for memorability), and true randomly generated lowercase, numbers, non-alphanumeric). This passwords. Each of these can be constructed as part causes an estimated time of approximately 35 days of all the mentioned character sets and would all be to calculate all possible passwords. Therefore, the approvable by this scheme in the case that the password length is changed to 10 and the test is entropy requirements permit. performed again which then produces an estimated All the presented examples are performed result of 3 years and 91 days. This produces an using the assumption that all inserted passwords acceptable threshold for a basic 3-month lifespan. will pass a dictionary check. This is done so that in The test is then repeated using entropy equivalents the case that when they do not pass a check, they to confirm that the other entropy structures will be forced to produce a stronger password, and produced also have strong execution times, which continue to provide strong security for the password can be seen in Table 3. This table demonstrates system. how a complexity requirement can be adjusted to find entropy equivalents in this system. Using a PRODUCT base of 10 characters with all available characters The product of this project was a series of for our set, it becomes possible to calculate how algorithms that implemented the lessons learned many characters would be needed to reach an and mitigated the weaknesses exploited in equivalent score using simpler character sets. For password based attacks. They follow all the example, reducing the character set to only outlined rules and were generated in such a way lowercase characters reduces the entropy by 8 that all the observed weaknesses in password points, which must then be made up using an structure were at least mitigated. The primary additional 4 characters as part of the password. The benefit of the algorithms is versatility and table also demonstrates password groups that are scalability. The criteria for password acceptance is entropy equivalent for our guidelines. They present not tied to specific values, but to expected threats. equivalent levels of unpredictability, using several The system can grow naturally without need to different methods to achieve it, such as using less change values as hardware improves and should characters, with a wider character set, or very small remain viable while attack trends hold. character set with a larger character total. The algorithms also embrace usability, users in to the system, as part of the approval process for are no longer forced to adhere to the password the use of the password. rules, instead their passwords are evaluated on One of the core features of this approach is various criteria and if their combined result is stated as scalability, and for this reason, there is satisfactory, the password is accepted. The user is also a secondary algorithm that handles calculating given various avenues to produce additional forms baseline value requirements for the passwords to be of password safety and they are all beneficial. In approved. This is performed by selecting an initial addition to this, they are encouraged to provide test value, and calculating an estimated time to passwords stronger than the average by the reward exhaustively test all possible passwords in a key scheme of giving additional password usability space of that length and a full character set of lifetime. uppercase characters, lowercase characters, It is important to note, however, that the numbers and non-alphanumeric characters. These algorithm presented is a template and not a hard set tests should be performed on current hardware, of rules. Implementation should be treated as an which should be representative of expected threats instance with changing details. Rigid adherence to to the system. Multiple GPU clusters for large those rules goes against the nature of this project corporations and single enthusiast grade GPU and could have significant detrimental effects to its systems for smaller organizations and companies efficiency. Simple implementations can work as is, for example. This produces realistic values that but experimentation should be encouraged for give users the most flexibility that can be better results. practically offered without sacrificing safety. The The algorithms all follow a similar structural goal should be to achieve at least double the desired core of calculating the strength of a given time for password lifespan at the base value. password, or a category of passwords. The Using the test machine and settings presented calculation begins with counting the total length of in the previous sections, this proved to happen at a the password, this number is then multiplied by 2 length of 10 characters. This should then be and becomes the base value of the tested password. confirmed to be usable by performing the same test From there, additional value is added based on using the chosen lengths entropy equivalents in fulfilling certain criteria. Those include: other character sets, all of which should have an  +6 for inclusion of both uppercase and execution time of a minimum satisfactory length. lowercase characters. Examples of these entropy equivalence  +2 for inclusion of numbers. calculations can seen in Table 3. These entropy  +4 for inclusion of non-alphanumeric equivalents shown in the table are values calculated characters. by the author, using the rules and algorithms created for this document. The columns of which To prevent scaling issues, a penalty of -2 is contain the possible lengths of passwords, and what applied to for each bonus given by this point past requirements it must meet in order to achieve its the first. This prevents a significant part of the required example value of 34. The point values of value being added exclusively from bonuses. these sources can be seen in the entries of each row, After this point, a dictionary check is with values of 0 meaning that it was not awarded a performed on the password to confirm that it is not bonus for that field. a commonly found password or dictionary word. In The final calculation that must be performed as the case that it does not fail the check, a final bonus part of the algorithm happens at the time of of +6 is given to the password. This check is potential password submission. If the submitted performed each time a potential password is input password surpasses the base value required, then additional time can be given to the passwords usable lifespan as a usability tradeoff. This allows requirement also impacts the character space users to change their password less frequently. It greatly, as seen in Table 1, where rapidly grows as also encourages stronger passwords past the those lengths are increased, even by small margins. minimum requirement, which provides a net gain in Even minor increases show orders of magnitude in security, despite the increased lifespan. This is due change for password length intervals. to the exponential growth rate of password hash This leads directly to additional burden to calculation versus the minor linear growth rate that attackers attempting automated methods of can be given to password. As provided, the rate is infiltration. Conventional methods of password that for every 2-value added to the password past requirements, such as the typical minimum length the requirement, an additional 3 months be allowed of 8 with mixed cases and special character for the password, to a maximum of 1 year to inclusion, lead to short execution times for attacks. prevent abuse cases. As can be seen in Figure 2, while following the The results of implementing this system would guidelines presented here result in guaranteed remove many pass words that would be accepted by average execution times, such as can be seen in currently used schemes such as “password” which Figure 3. Both Figures 2 and 3 present execution carries a life expectancy in the order of seconds, times for attacks in the popular program known as while also allowing new creative approaches such Hashcat which breaks password hashes, with Figure as “ihavemuch<3forchickentacos” which would be 2 presenting the aforementioned complex 8 ruleset rejected as a weak password by some schemes for mentioned before and Figure 3 presenting an not containing a capital letter. Maintaining the acceptable runtime discovered using this algorithm. length of characters to a currently relevant Figure 2 Complex 8 Runtimes Figure 3 Complex 10 Runtimes CONCLUSION significant weaknesses across a variety of password attacks. This includes further delving in to how a After going through the weaknesses found in person’s demographic information influences their current password schemes, new guidelines are password contents and structure. The previously recommended. The new structure is less rigid: it performed study by the author [2] showed that there embraces potential sources of strength and user are unexplored elements that can influence the variances as a source of unpredictability, which password creating process. allows for varied password styles and encourages In addition, the algorithm itself can be refined users to produce stronger passwords. This can lead on a case basis, the implementation can vary and be to a better relationship between users and their further developed as seen fit by the developer that password based systems, meaning that the plans on using it; the needs of the implementer will password validation system might not be vary on a case-by-case basis. antagonistic and complicated, but instead as a system working with the user to keep their systems REFERENCES secure. Brute Force style attacks rely on the certainty [1] Scarfone and S. Murugiah, "Guide to Enterprise Password Management," in National Institute of that the password will eventually be discovered, but Standards and Technology, 2009. by introducing varied password length that certainty is reduced. A variety of lengths in the [2] J. Hernandez, "A Study on the Password Habits of used passwords space, means that a wider span of College Students: Length and Complexity Based on Demographics," in Richard Tapia Celebration of possible passwords must be tested. This may bring Diversity in Computing, Austin, 2016. testing of passwords outside of practical reach for password crackers. [3] MedicineNet. (2016, June 9). Medical Definition of Pavlovian Conditioning [Online]. Available: The adoption of a variable set of password http://www.medicinenet.com/script/main/art.asp?articl rules also embraces many styles of secure ekey=4801. [Accessed 2 6 2017]. passwords that are not permissible in several [4] S. L. &. M. J. D. Brand, "Department of Defense current schemes. Allowing users to use measures password management guideline," in Department of such as sufficiently long passwords that contain Defense, Fort George G. Meade, 1985. only lowercase letter allows them to secure their accounts without forsaking comfort and usability for the user. The password negotiation aspect also lends itself to both security and usability. Allowing for more secure passwords to have longer usable timespans encourages the users to actively participate in the betterment of the security process instead of merely requiring them to give a minimum effort. Combined these elements lead to an improved security system that help to cover many of the current issues found in password security. FUTURE WORK Further study into the characteristics of human generated passwords is critical to improving security. This element has proven to be a source of