Visualization of patterns of used passwords

Scientists from the US Air Force Academy have analyzed the possibility of selecting a password using a special dictionary created using graphical keyboard “patterns” used by users to create a reliable, but easily remembered password.

Introduction

Currently, passwords are the most commonly used method for authenticating system users. With the increasing capabilities of parallel computing, the need for strong passwords is growing every day. A 2004 study by comrades J. Jan R. Anderson and A. Grant [1] proved that about a third of users use insecure passwords. In addition, a vulnerable password in one service may compromise in others, since the same passphrase is often used. Usually, accounts are hacked using a brute-force attack ( brute-force aka brute force attacks), since modern computing power of computers makes it possible to achieve a picking speed of millions of passwords per second. To "force" users to invent more complex password combinations, special rules are introduced. Basically, these rules indicate how long the password should be, the need for special characters, and also check for the presence of the typed password in the open dictionaries for brute-force.
')
A typical example of these rules is the following list:

1. Password must be at least 12 characters
2. Must contain 2 special characters
3. Must be 2 digits
4. Must contain 2 uppercase characters
5. Password must not contain words from the dictionary of known passwords

This set of rules is common to all users so that no one creates too simple passwords. On the other hand, it is very difficult to come up with a password that simultaneously meets these rules and which is really remembered.

Due to the tightening of the rules for creating password phrases, many users resort to alternative methods for creating a memorable password based on graphical keyboard patterns. An example of this type of password is 1qaz! QAZ2wsx @ WSX . Although at first glance it looks quite random, contains 16 characters and seems fairly reliable, analysis of the sequence of keystrokes produces a fairly simple pattern.



It is clear that the user chose an easy-to-remember password, but it is obvious that the pattern starts with the number “1”, continues down to the letter “z”, then repeats with pressed Shift , and then repeats the same pressing technique for the column “2” to "x". This article describes the visualization method and the development of heuristic analysis, which allows you to select, at first glance, complex passwords.

Common Passwords Attacks

There are a number of common ways to open passwords. These are mainly methods based on social engineering (SI), phishing, shoulder surfing , keyloggers, dictionary attacks and brute force attacks. The purpose of a strong password is to protect against dictionary brute force attacks, as well as to increase the difficulty of selecting a password using the full brute force method. Modern password cracking systems are becoming more sophisticated and complex, an example of the most well-known utility "John the Ripper". Joni's functional allows you to carry out attacks not only by brute force, but also allows you to automatically create a set of variations of common words used as a password due to advanced generation rules. This practice is often used by users to enhance their passwords by replacing letters with special characters or numbers. For example, the name of your favorite dog Fido is modified to something like F! D0 . Of course, this increases the set for verification, but this way is achieved beyond the scope of the dictionary. Thus, such tools as “John the Ripper” allow you to quickly and easily crack passwords consisting of a composition of words, especially if one of the words is a login.

The consequence of these achievements in password cracking is that users who are interested in their security are motivated to create more complex passwords. In an attempt to create an easy-to-remember, but complex password, users resort to using passwords based on keyboard patterns.

An approach

The study focuses on the ability to recognize keyboard graphic patterns. The following approach was used:

• collection of passwords, including those known to be created using keyboard patterns;
• development of a visualization technique for the subsequent analysis of passwords with the aim of identifying common parts of the patterns;
• developing heuristics based on recognized models;
• creating a password dictionary based on the created heuristics;
• the use of a hacking tool on a real password.

Password collection

The purpose of the collection was a large set of possible password combinations. We could not make a collection, relying on one of the dictionaries, since we needed passwords that meet fairly strict rules. To solve this problem, an online password creation guide has been created. With the help of students, a large database of passwords was collected, which was used for subsequent analysis.

One of the textbook articles explained the concept of passwords based on keyboard patterns and asked them to imagine. To achieve the goal, a real-time visualization system was used.



Using the created tool we collected more than 250 unique passwords based on patterns with the help of 161 users. Additionally, more than 500 "random" passwords were generated.

Pattern visualization

The next step is to analyze a set of passwords based on keyboard graphic patterns to find common features. A simple image containing lines connecting successively pressed keys on a graphic keyboard was not enough. In this case, the lines would be superimposed on each other, if the keys on the keyboard were in the same row, or the lines would not be drawn at all if they pressed one key several times in a row. Thus, the sequence of input characters would be misleading.

It was necessary to create a way to visualize such situations as: pressing the Shift key , repeatedly pressing a single key, repeatedly entering a character set. The first approach was to play the password sequentially, character by character. This approach solves the problem of pattern recognition, but does not solve the problem of visualizing and scanning a large number of passwords.

To improve pattern recognition when comparing multiple passwords, the following rules are used:

1. Successively pressed keys are connected by arcs.
2. With the Shift key pressed, increase the arc thickness.
3. Multiple presses on one key are depicted by arcs, the ends of which are one node, so that a “flower” is formed
4. Multiple entry of a sequence of characters is displayed by offsetting arcs.
5. Multiple consecutive pressing of one key is depicted in the form of petals with an offset.
6. Arcs are always drawn clockwise to follow the order of keystrokes.

A picture showing all these rules is shown below.



With thick lines everything is clear - the Shift key was pressed. In addition, the "d" and "t" keys were pressed several times. Eight keystrokes of the "t" key arc to the key, as well as the four leaf and the trefoil enclosed in it. In the same way, it is possible to analyze the repeated (fourfold) pressing of the “d” key. Repeating combination of characters "qwqwqw" display with the help of offset arcs. Due to the fact that arcs are always drawn clockwise, it is possible to define a sequence of keystrokes without pointing arrows on arcs.

The following figure shows examples of visualization of keyboard patterns contained in the analyzed database. If the password is not created on the basis of graphical keyboard patterns, as in the 4 example in the figure, then this is immediately visible.






The main task was to determine the main structural elements of the patterns from the database, for quick recognition of passwords. The following is an example of finding such unique elements from which you can make a pattern, based on a 4x4 table generated by a special tool.

Password cracking tool prototype using patterns

On the basis of the research conducted, a set of elementary patterns was created, divided into several categories: double tap, triple tap, snake, pair, triple, etc.



Using the obtained elementary patterns, various combinations of passwords with a length of 8 to 12 characters were generated. The range of password lengths was chosen arbitrarily, but with a strong desire it can be increased, which will lead to a strong increase in the volume of the dictionary.

The password generator created passwords using the following structure (sorted by priority):

1. Compliance with the rule of password complexity.
2. Parts of the password are directed to one side.
3. Parts of the password have the same length.
4. All parts of the password are entered with Shift or not.
5. Parts of the password are directed from left to right, or from top to bottom.
6. Parts of the password have only one break on the keyboard.

Examples of generated passwords by these rules are shown in the figure below.



The resulting dictionary contains about 500.000 variants. However, it contains not all combinations, since the standard 94 character keyboard offers a much larger number of options, namely:

4.8 * 10 ²³ = (94 ⁸ + 94 ⁹ + 94 ¹⁰ + 94 ¹¹ + 94 ¹² )

possible password combinations.

results

Password cracking tests have shown that even a generated database allows you to choose a password based on a graphic pattern in more than 20% of cases in a short period of time. For example, “John the Ripper”, using the brute force method, could not pick up a single password in more than 18 hours, and using the created pattern dictionary, Johnny picked up 11 passwords (18%) in less than one second.

Links used in the article:
[1] J. Yan, A. Blackwell, R. Anderson, and A. Grant. Password memorability and security: empirical results. IEEE Security & Privacy 2, 25-31 (2004)

---

Link to the article itself here .