rub-syssec / omen

OMEN: Ordered Markov ENumerator - Password Guesser

OMEN: Ordered Markov ENumerator

OMEN is a Markov model-based password guesser written in C. It generates password candidates according to their occurrence probabilities, i.e., it outputs most likely passwords first. OMEN significantly improves guessing speed over existing proposals. If you are interested in the details on how OMEN improves on existing Markov model-based password guessing approaches, please refer to OMEN: Faster Password Guessing Using an Ordered Markov Enumerator.

User Guide

OMEN consists of two separate program modules: createNG and enumNG. createNG calculates n-gram probabilities based on a given list of passwords and stores them on the hard disk. Based on these probabilities enumNG enumerates new passwords in the correct order (descending).

Installation

Use a recent Linux version make sure you have installed git (Git version control system), gcc (GNU Compiler Collection), and make (GNU Make). You can install it under Ubuntu Linux via:

$ sudo apt-get install build-essential git

Check out the source code via:

$ git clone https://github.com/RUB-SysSec/OMEN.git OMEN

Change into the newly created directory OMEN and run:

$ make

If compilation is successful, you can find createNG and enumNG within the current directory.

.
├── alphabetCreator
├── createNG
├── docs
│   ├── CHANGELOG.md
│   ├── LICENSE
│   └── screenshots
├── enumNG
├── evalPW
├── makefile
├── README.md
└── src
    ├── alphabetCreator.c
    ...

If you like, you can now remove the src folder and the makefile file, they are no longer used.

Windows User?

A short installation guide using Cygwin on Windows 10 can be found here.

Basic Usage

Before one can generate any passwords, the n-gram probabilities have to be estimated using createNG. To calculate the probabilities using the default settings, createNG must be called giving a path to a password list that should be trained:

$ ./createNG --iPwdList password-training-list.txt

Each password of the given list must be in a new line. The module then reads and evaluates the list generating a couple of files. Besides a config file (createConfig) storing the used settings (in this case the default setting), several files are created containing information about the grams and the password length. These files have the extension '.level':

• IP.level (Initial Probability): Stores the probabilities of the first (n-1)-gram of each password.
• CP.level (Conditional Probability): Stores the probabilities of the actual n-grams.
• EP.level (End Probability): Stores the probabilities of the last (n-1)-gram of each password.
• LN.level (Length): Stores the probabilities for the password length.

The probabilities of each n-gram and the lengths are mapped to levels between 0 (most likely) and 10 (least likely). Once those files are created, enumNG can be used to generate a list of passwords ordered by probabilities. Currently, enumNG supports three modes of operation: file, stdout, simulated plaintext attack. In the default mode of enumNG, a list of password guesses based on these levels is created. Using the command

$ ./enumNG

generates 1 billion passwords and stores them in a text file, which can be found in the 'results' folder. The passwords in this file are ordered by level (i.e., by probability). Since common text editors are not able to handle such huge files, it is recommended for testing to reduce the number of passwords created. This can be done using the argument -m.

$ ./enumNG -m 10000

It will create an ordered list with 10,000 passwords only. If you are interested in printing the passwords to the standard output (stdout) stream use the argument -p.

$ ./enumNG -p -m 10000

If you are interested in evaluating the guessing performance against a plaintext password test set use the argument -s. Please note: In this mode OMEN benefits from the adaptive length scheduling algorithm incorporating live feedback, which is not available (due to the missing feedback channel) in file and stdout mode.

$ ./enumNG -s=password-testing-list.txt -m 10000

The result of this evaluation can be found in the 'results' folder.

Both modules provide a help dialog which can be shown using the -h or --help argument.

Password Cracking

How to get from $2a$10$HNYF4KajSTqxIP/KoiB5tOCVeKUgvscTh32hhAmppFk4T/USmI2B. to "GoodOMEN!123"?

Ethics

OMEN was developed for academic use cases like improving probabilistic password modeling, estimating guess numbers or password strength, in general, to improve password security. Do not abuse this software to harm other people's privacy or to break the law.

Preimage Attacks

Popular hash evaluators like Hashcat and John the Ripper support hundreds of hash and cipher formats and could be easily integrated due to their support to read password candidates via their standard input (stdin) stream.

$ ./enumNG -p -m 10000 | ./hashcat64.bin ...

or

$ ./enumNG -p -m 10000 | ./john --stdin ...

For optimal guessing performance, consider to train createNG with a password distribution that is similar to the one you like to crack.

Please note: Using probabilistic password modeling to crack passwords, in general, should only be considered against slow hashes (e.g., bcrypt, PBKDF2, scrypt, or Argon2) were the number of feasible guesses is limited or in very targeted attacks. In contrast, for very fast hashes (MD5, SHA-1, or NTLM), using good dictionaries and mangling rules (e.g., best64.rule) are the way to go.

If you are interested in this topic, consider to read the following papers and their related work (this list is incomplete, you can help by expanding it):

Probabilistic Context-Free Grammars

• Password Cracking Using Probabilistic Context-Free Grammars (SP '09)
• Guess Again (and Again and Again): Measuring Password Strength by Simulating Password-Cracking Algorithms (SP '12)
• On the Semantic Patterns of Passwords and their Security Impact (NDSS '14)
• Next Gen PCFG Password Cracking (TIFS '15)
• ...
• Software A, Software B

Markov Models

• Fast Dictionary Attacks on Passwords Using Time-Space Tradeoff (CCS '05)
• OMEN+: When Privacy meets Security: Leveraging personal information for password cracking (CoRR '13)
• A Study of Probabilistic Password Models (SP '14)
• OMEN: Faster Password Guessing Using an Ordered Markov Enumerator (ESSoS '15)
• ...
• Software A, Software B

Neural Networks

• Fast, Lean, and Accurate: Modeling Password Guessability Using Neural Networks (USENIX '16)
• Using Neural Networks for Password Cracking (Blog post by Sebastian Neef '16)
• Design and Evaluation of a Data-Driven Password Meter (CHI '17)
• ...
• Software A, Software B

Hybrids

• John the Ripper 'Incremental' Mode
• Introducing the PRINCE Attack-Mode (PASSWORDS '14)
• ...
• Software A, Software B

Approach Comparison

• Measuring Real-World Accuracies and Biases in Modeling Password Guessability (USENIX '15)
• A Framework for Comparing Password Guessing Strategies (PASSWORDS '15)
• PARS: A Uniform and Open-source Password Analysis and Research System (ACSAC '15)
• ...
• Software A, Software B

Advanced Usage

Both modules provide several command line arguments to select the various modes available and change the default settings. For instance, the probability distribution created during the createNG process may be manipulated by choosing one of the supported smoothing functions, the n-gram size, or the used alphabet. All available parameters for createNG, a short description, and the default values can be seen by calling the program with -h or --help. The same works for enumNG where for instance, the enumeration mode, the used length scheduling algorithm (only used in -s mode, see 'Basic Usage' section), and the maximum amount of attempts can be selected. If no enumeration mode is given, the default mode is executed, storing all created passwords in a text file in the 'results' folder.

OMEN+

OMEN+ is based on When Privacy Meets Security: Leveraging Personal Information for Password Cracking and is an additional feature of OMEN (implemented in the same binary). Using additional personal information about a user (e.g., a password hint or personal background information scraped from a social network) may help in speeding up the password guessing process (comparable to John the Ripper 'Single crack' mode).

Therefore, a related hint or several hints (tabulator separated) must be provided in a separate file. Furthermore, an alpha file is required containing the respective alpha values (tab separated in one line). Alpha values are used to weight the impact of the provided hints. Important is that for each hint in a line an alpha has to be specified in the alpha file. These alphas have to be in the same order as the hints per line.

Exemplary, we want to guess the password "Mary'sPW2305". The corresponding line in the hint file containing first name, username, date of birth, and email address looks like the following:

mary   mary1   19880523    [email protected]

An alpha file should order the related alpha values for first name, username, date of birth, and email address in the same order as in the hint file. In example:

1   2   1   2

For the usage of OMEN+ enumNG must be called giving a path to a hint and an alpha file:

$ ./enumNG -H hint-file.txt -a alpha-file.txt

Performance

Smoothing Configuration

The smoothing function is selected and configured using a configuration file (createConfig). The file must contain the name of the smoothing function and may contain the values for any variable parameters. The file should be formatted like this:

<name>
-<parameter>_<target> <value>
...

At this time, the only supported smoothing functions are none or additive smoothing.

The allowed parameters (<parameter>) are:

• levelAdjust (level adjustment factor, heavily influence performance, i.e., good are 100-250)
• delta (additive smoothing adds a value δ (delta) to each n-gram, i.e., 0,1,2, ...)

The allowed targets (<target>) are:

• IP (Initial Probability)
• CP (Conditional Probability)
• EP (End Probability)
• all (Parameter is used for all possible targets)

Notice, one value for a single target overwrites the one set for all.

An exemplary for the add1(250) (Additive Smoothing (δ=1), Level Adjustment Factor of 250) smoothing setting:

additive
-delta_all 1
-delta_LN 0
-levelAdjust_all 250
-levelAdjust_CP 2
-levelAdjust_LN 1

Additional Program Modules

Besides the two main modules createNG and enumNG, OMEN provides two other program modules: evalPW and alphabetCreator. evalPW evaluates a given password and alphabetCreator creates an alphabet with the most frequent character in a given password list. Both modules should be considered experimental.

evalPW

It reads a given password and evaluates its strength by returning a password-level. The result is based on the levels generated by createNG. The password-level is the sum of each occurring n-gram level, based on the level lists IP, CP, and EP. The current implementation of evalPW is only a prototype and does not support the whole possible functionality and contains lots of bugs. For example, the actual password length does not influence the password-level. Therefore, only passwords with the same length can be compared to each other.

$ ./evalPW --pw=demo123

alphabetCreator

If you want to limit OMEN to passwords complying to a given alphabet you can specify this in the configuration file (createConfig). To determine the most promising alphabet, the alphabetCreator might be able to help you. The program module creates a new alphabet based on a given password list. The characters of the new alphabet are ordered by their frequency in the password list, beginning with the highest frequency. The length of the alphabet is variable. The created alphabet is based on the 8-bit ASCII table according to ISO 8859-1 (not allowing ’\n’, ’\r’, ’\t’, and ’ ’ (space)). Characters that are not part of this table are ignored. Also, an existing alphabet may be extended with the most frequent characters.

# Based on the frequency statistics of the training file (password-training-list.txt), we generate the new alphabet (new-alphabet-file.alphabet)
$ ./alphabetCreator --pwList password-training-list.txt --size 95 --output new-alphabet-file

# Optional: Verification
$ cat new-alphabet-file.alphabet
ae1ionrls20tm39c8dy54hu6b7kgpjvfwzAxEIOLRNSTMqCDB.YH!U_PKGJ-*VF@WZ#/X$,&+Q?\)=(';%<]~[:^`">{}|

# Now you can train OMEN using the newly generated alphabet
$ ./createNG --iPwdList password-training-list.txt -A new-alphabet-file.alphabet -v

# Optional: Verification
$ ./enumNG -p -m 1000 > top1k.txt
$ grep password top1k.txt
password

FAQ

• Very poor performance and strange looking passwords? Make sure you generated the alphabet file with the alphabetCreator. Manually generating the alphabet is not supported (see Issue#4).

License

The Ordered Markov ENumerator (OMEN) is licensed under the MIT license. Refer to docs/LICENSE for more information.

Third-Party Libraries

• getopt is part of the GNU C Library (glibc) and used to parse command line arguments. The developer, the license, and the source code can be downloaded here.
• uthash is a hash table for C structures developed by Troy D. Hanson. The source code and the license can be downloaded here.

Contact

Visit our website and follow us on Twitter. If you are interested in passwords, consider to contribute and to attend the International Conference on Passwords (PASSWORDS).

omen's Issues

Make CFLAG issue on old version of Ubuntu

I tried to compile OMEN on a very old version of Ubuntu (long story), and ran into the following issues when running Make:

cc1: error: unrecognized command line option ‘-Wpedantic’
cc1: error: unrecognized command line option ‘-std=gnu11’

To fix it, I changed the CFLAG variable in the makefile to -pedantic and -std=gnu99. After that OMEN compiled and worked as expected.

Ubuntu Version: 12.04.5 LTS
gcc version 4.6.3

Note, I ran into a similar problem when I tried that out on a similarly out of date CentoOS release 6.7

feature request: support for utf-8 alphabets

Current alphabet support is limited to ISO 8859-1 8-bit ASCII. Many word corpora are based on other character sets.

16.04 | makefile:41: recipe for target 'evalPW' failed

OS: Xubuntu 16.04

`/RUB-SysSec/OMEN
INSTALL

Cloning into 'OMEN'...
remote: Counting objects: 128, done.
remote: Total 128 (delta 0), reused 0 (delta 0), pack-reused 128
Receiving objects: 100% (128/128), 623.24 KiB | 0 bytes/s, done.
Resolving deltas: 100% (57/57), done.
Checking connectivity... done.
[sudo] password for robotux:
sed s/VERSION/0.3.1/g src/cmdlineCreateNG.h.in > src/cmdlineCreateNG.h
sed s/cmdlineCreateNG.h.in/cmdlineCreateNG.h/g src/cmdlineCreateNG.c.in > src/cmdlineCreateNG.c
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/createNG.c -o createNG.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/common.c -o common.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/errorHandler.c -o errorHandler.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/smoothing.c -o smoothing.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/commonStructs.c -o commonStructs.o
sed s/VERSION/0.3.1/g src/cmdlineEnumNG.h.in > src/cmdlineEnumNG.h
sed s/cmdlineEnumNG.h.in/cmdlineEnumNG.h/g src/cmdlineEnumNG.c.in > src/cmdlineEnumNG.c
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/enumNG.c -o enumNG.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/boosting.c -o boosting.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/nGramReader.c -o nGramReader.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/attackSimulator.c -o attackSimulator.o
sed s/VERSION/0.3.1/g src/cmdlineEvalPW.h.in > src/cmdlineEvalPW.h
sed s/cmdlineEvalPW.h.in/cmdlineEvalPW.h/g src/cmdlineEvalPW.c.in > src/cmdlineEvalPW.c
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/evalPW.c -o evalPW.o
sed s/VERSION/0.3.1/g src/cmdlineAlphabetCreator.h.in > src/cmdlineAlphabetCreator.h
sed s/cmdlineAlphabetCreator.h.in/cmdlineAlphabetCreator.h/g src/cmdlineAlphabetCreator.c.in > src/cmdlineAlphabetCreator.c
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/alphabetCreator.c -o alphabetCreator.o
rm -f *.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/cmdlineCreateNG.c -o cmdlineCreateNG.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/cmdlineEnumNG.c -o cmdlineEnumNG.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/cmdlineEvalPW.c -o cmdlineEvalPW.o
cc -Wall -std=gnu11 -O3 -Wall -Wpedantic -g -flto -c src/cmdlineAlphabetCreator.c -o cmdlineAlphabetCreator.o
cc -o evalPW evalPW.o common.o errorHandler.o smoothing.o cmdlineEvalPW.o commonStructs.o nGramReader.o -g -lm -flto
cc: error: common.o: No such file or directory
cc: error: errorHandler.o: No such file or directory
cc: error: smoothing.o: No such file or directory
cc: error: commonStructs.o: No such file or directory
cc: error: nGramReader.o: No such file or directory
makefile:41: recipe for target 'evalPW' failed
make: *** [evalPW] Error 1
make: *** Waiting for unfinished jobs....`

[createNG] No such file or directory

I've got a weird error for some of my files containing special characters:

./createNG --iPwdList=/data/chercheurs/matlink/bases/elag_expanded_rockyou_learn
ERROR: Could not open /data/chercheurs/matlink/bases/elag_expanded_rockyou_leari, errno: 2 - "No such file or directory"
Status: aborted(1)

Very poor results - is there a bug or did I do it wrong?

Sorry for lengthy post.

I did some quick tests with this because it looked interesting. I was going to post results to john-users mailing list (and consider implementing it natively in JtR) but results were so poor I suspect something is wrong - a bug, or user error on my side?

I used the rockyou list (with dupes but ASCII only) to train OMEN (full ASCII alphabet) as well as JtR's incremental and markov modes. I ran them against a set of real-world NT hashes scraped from pastebin.

1. Create a rockyou file w/ dupes, ASCII only and length 0-16:

$ perl -ne 's/\r//g; print if /^[\x20-\x7e]{0,16}$/' < rockyou.original.dlst > rockyou_ascii_16.dlst

2. For JtR's markov mode (since it's designed to run to end as opposed to produce best candidates early) I adjusted level to produce approx. 100M candidates. At max. length of 16 that was level 190:

$ ./calc_stat -p rockyou_ascii_16.dlst stats
$ ./genmkvpwd stats 0 16
$ rm -f john.pot && ./john scraped.sam -form:nt -v:1 -markov:190 -max-len=16
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press 'q' or Ctrl-C to abort, almost any other key for status
MKV start (stats=$JOHN/stats, lvl=190 len=16 pwd=96840868)
1822g 0:00:00:04 100.00% (ETA: 10:27:53) 380.3g/s 20217Kp/s 20217Kc/s 103475MC/s }|..}

3. The exact number of candidates produced above (96,840,868) was then used with the (brand new) -max-cand option for incremental mode, to get the same number of candidates tried:

$ sed 's/^/:/' < rockyou_ascii_16.dlst > rock.pot
$ ./john -make-charset=custom.chr -pot=rock.pot
$ rm -f john.pot && ./john scraped.sam -form:nt -max-cand=96840868 -v:1 -inc:custom -max-len=16
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press 'q' or Ctrl-C to abort, almost any other key for status
911g 0:00:00:12  73.58g/s 7822Kp/s 7822Kc/s 36739MC/s pwdreg..pwdrik

4. The same number of candidates were generated with OMEN:

$ perl -e 'foreach $i (32..126) { print chr($i) }' > alphabet.txt
$ createNG --iPwdList rockyou_ascii_16.dlst -A alphabet.txt -v
$ rm -f john.pot && enumNG -p -m 96840868 | ./john scraped.sam -form:nt -v:1 -stdin
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press Ctrl-C to abort, or send SIGUSR1 to john process for status
83g 0:00:03:24  0.4063g/s 474059p/s 474059c/s 2488MC/s 121242:7:..192:2:243

Wow :-( Not only was it way slower, the result was also very poor. The low speed was partly due to pipe overhead but mostly not because of that. And anyway the poor result was even more discouraging. Actually, 82 of those 83 cracks were passwords consisting of just digits.

Similar tests with 1G candidates show same poor results. I can't see what I'm doing wrong here?

$ rm -f john.pot && ./john scraped.sam -form:nt -v:1 -markov:213 -max-len=16
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press 'q' or Ctrl-C to abort, almost any other key for status
MKV start (stats=$JOHN/stats, lvl=213 len=16 pwd=1010366652)
2227g 0:00:00:47 100.00% (ETA: 10:49:28) 46.92g/s 21288Kp/s 21288Kc/s 88428MC/s }U..}

$ rm -f john.pot && ./john scraped.sam -form:nt -max-cand=1010366652 -v:1 -inc:custom -max-len=16
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press 'q' or Ctrl-C to abort, almost any other key for status
1311g 0:00:00:52  25.14g/s 19377Kp/s 19377Kc/s 80804MC/s tmd0185..tmd0190

$ rm -f john.pot && enumNG -p -m 1010366652 | ./john scraped.sam -form:nt -v:1 -stdin
Loaded 5294 password hashes with no different salts (NT [MD4 128/128 AVX 4x3])
Press Ctrl-C to abort, or send SIGUSR1 to john process for status
104g 0:00:34:48  0.04980g/s 483884p/s 483884c/s 2516MC/s tifsnjmfouf234..tifsnjpobtu234

Very slow, and again all but one (of the very few) cracks were digits-only. Note that only 104 correct guesses were generated in total over 35 minutes. Compare that to JtR markov's 47 correct guesses per second.

Here's a completely different test. At which point do they find "123456" or "password" which are among the most common RockYou passwords? JtR's markov mode is not tested here since it's not supposed to produce best-early.

$ ../run/john -inc:custom -stdout -max-len=16 | grep -Fxnm1 123456
Press 'q' or Ctrl-C to abort, almost any other key for status
1:123456

$ enumNG -p | grep -Fxnm1 123456
200:123456

$ ../run/john -inc:custom -stdout -max-len=16 -ses:0 | grep -Fxnm1 password
Warning: only 95 characters available
Press 'q' or Ctrl-C to abort, almost any other key for status
409345:password

$ enumNG -p | grep -Fxnm1 password
(I gave up after 25 minutes)

So hundreds of millions of candidates were generated but the 4th most common rockyou password wasn't among them. Something's amiss. I did try a different set of test hashes (subset of LinkedIn) but results were equally sad. I also tried using the -s option to enumNG (which would need it to be incorporated into JtR codebase IRL) and it didn't help noticably.

feature request: allow resuming from a specific point

Long cracking runs sometimes need to resume at a specific point in the wordlist. A way to save state on termination of the process and then resume at that point would be very useful.

This might work similarly to:

https://github.com/hashcat/princeprocessor/blob/master/src/pp.c#L199

Contains an unknown symbol and will be ignored

Where is the error, I have the same error message no matter what options I use ?!

./createNG --iPwdList pw.txt
WARNING: Either errors or warnings occured. Enable print warnings to see these.

./createNG -w --iPwdList pw.txt
WARNING: nGram(s) in line 11743008 contains an unknown symbol and will be ignored.
WARNING: nGram(s) in line 11743141 contains an unknown symbol and will be ignored.
WARNING: nGram(s) in line 11743160 contains an unknown symbol and will be ignored.

Issue with Length data when training

It appears that the length data saved in LN.level has an off by one error when training passwords of length 4 are being saved as length 5, length 5 are being saved as length 6, etc, with junk data being saved for length 4, (using ngrams = 4).

For example, consider the training set. Note this does not have "junk" data for length 4 but I've seen that appear on larger training sets like the RockYou list:

test
test1
test1
test12
test12
test12
test123
test123
test123
test123

So there is 1 of length 4, 2 of length 5, etc. Using the following command for training:

./createNG -F -v -n 4 --iPwdList test.txt

The following is my LN.count file:
...
0 1
0 2
0 3
0 4
1 5
2 6
3 7
4 8
0 9
0 10
0 11
....

feature request: allow running from other directories

When trying to run enumNG from another directory, certain assumptions are made about file locations. This is a very common use case that would be very helpful to add.

$ cd /my/work/dir
$ /usr/local/src/OMEN/enumNG
ERROR: Could not open createConfig, errno: 2 - "No such file or directory"
ERROR: Could not open file (createConfig)

This tool gets stuck and it seems like it will never produce any result

Hello, I am trying to produce a list of candidates of length 8 but it seems to be impossible. First, I use the following word list to train the tool:

bicicleta
estufa
caramelo
marusco
cangrejo
burger
petulante
cimbrel
cinabrio
cucamonga
cerveza

But the problem starts when I execute enumNG like this:
./OMEN/enumNG -m 10000 -l 8 -v -O
I have waited several hours and hasn't produced even a single candidate word. I am also on verbose mode and it says 0 % created and does never move on from there.
Why does this happen? Am I doing something wrong?