1 /**********************************************************************************
2 * C implementation of the zxcvbn password strength estimation method.
3 * Copyright (c) 2015, Tony Evans
6 * Redistribution and use in source and binary forms, with or without modification, are
7 * permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright notice, this list
10 * of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright notice, this
13 * list of conditions and the following disclaimer in the documentation and/or other
14 * materials provided with the distribution.
16 * 3. Neither the name of the copyright holder nor the names of its contributors may be
17 * used to endorse or promote products derived from this software without specific
18 * prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY
21 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
23 * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
25 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
26 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
31 **********************************************************************************/
41 #if defined(USE_FILE_IO) || !defined(__cplusplus)
48 /* For pre-compiled headers under windows */
53 /*################################################################################*
54 *################################################################################*
55 * Begin utility function code
56 *################################################################################*
57 *################################################################################*/
60 /**********************************************************************************
61 * Binomial coefficient function. Uses method described at
62 * http://blog.plover.com/math/choose.html
64 static double nCk(int n
, int k
)
73 for(d
= 1; d
<= k
; ++d
)
81 /**********************************************************************************
82 * Binary search function to find a character in a string.
84 * Ch The character to find
85 * Ents The string to search
86 * NumEnts The number character groups in the string Ents
87 * SizeEnt The size of each character group.
88 * Returns a pointer to the found character, or null if not found.
90 static const uint8_t *CharBinSearch(uint8_t Ch
, const uint8_t *Ents
, unsigned int NumEnts
, unsigned int SizeEnt
)
94 const uint8_t *Mid
= Ents
+ (NumEnts
>> 1) * SizeEnt
;
102 Ents
= Mid
+ SizeEnt
;
110 /**********************************************************************************
111 * Calculate potential number of different characters in the passed string.
113 * Str The string of characters
114 * Len The maximum number of characters to scan
115 * Returns the potential number of different characters in the string.
117 static int Cardinality(const uint8_t *Str
, int Len
)
126 if (islower(c
)) Types
|= 1; /* Lowercase letter */
127 else if (isupper(c
)) Types
|= 2; /* Uppercase letter */
128 else if (isdigit(c
)) Types
|= 4; /* Numeric digit */
129 else if (c
<= 0x7F) Types
|= 8; /* Punctuation character */
130 else Types
|= 16; /* Other (Unicode?) */
133 if (Types
& 1) Card
+= 26;
134 if (Types
& 2) Card
+= 26;
135 if (Types
& 4) Card
+= 10;
136 if (Types
& 8) Card
+= 33;
137 if (Types
& 16) Card
+= 100;
141 /**********************************************************************************
142 * Allocate a ZxcMatch_t struct, clear it to zero
144 static ZxcMatch_t
*AllocMatch()
146 ZxcMatch_t
*p
= MallocFn(ZxcMatch_t
, 1);
147 memset(p
, 0, sizeof *p
);
151 /**********************************************************************************
152 * Add new match struct to linked list of matches. List ordered with shortest at
155 static void AddResult(ZxcMatch_t
**HeadRef
, ZxcMatch_t
*Nu
)
157 /* Find the correct insert point */
158 while(*HeadRef
&& ((*HeadRef
)->Length
< Nu
->Length
))
159 HeadRef
= &((*HeadRef
)->Next
);
161 /* Add new entry or replace existing */
162 if (*HeadRef
&& ((*HeadRef
)->Length
== Nu
->Length
))
164 /* New entry has same length as existing, so one of them needs discarding */
165 if ((*HeadRef
)->Entrpy
<= Nu
->Entrpy
)
167 /* Existing entry has lower entropy - keep it, discard new entry */
172 /* New entry has lower entropy - replace existing entry */
173 Nu
->Next
= (*HeadRef
)->Next
;
180 /* New entry has different length, so add it */
186 /*################################################################################*
187 *################################################################################*
188 * Begin dictionary matching code
189 *################################################################################*
190 *################################################################################*/
193 /* Use dictionary data from file */
195 #if defined(USE_FILE_IO) || !defined(__cplusplus)
196 /* Use the FILE streams from stdio.h */
198 typedef FILE *FileHandle
;
200 #define MyOpenFile(f, name) (f = fopen(name, "rb"))
201 #define MyReadFile(f, buf, bytes) (fread(buf, 1, bytes, f) == (bytes))
202 #define MyCloseFile(f) fclose(f)
206 /* Use the C++ iostreams */
207 typedef std::ifstream FileHandle
;
209 static inline void MyOpenFile(FileHandle
& f
, const char *Name
)
211 f
.open(Name
, std::ifstream::in
| std::ifstream::binary
);
213 static inline bool MyReadFile(FileHandle
& f
, void *Buf
, unsigned int Num
)
215 return f
.read((char *)Buf
, Num
);
217 static inline void MyCloseFile(FileHandle
& f
)
224 /* Include file contains the CRC of the dictionary data file. Used to detect corruption */
226 #include "dict-crc.h"
228 #define MAX_DICT_FILE_SIZE (100+WORD_FILE_SIZE)
229 #define CHK_INIT 0xffffffffffffffffULL
231 /* Static table used for the crc implementation. */
232 static const uint64_t CrcTable
[16] =
234 0x0000000000000000ULL
, 0x7d08ff3b88be6f81ULL
, 0xfa11fe77117cdf02ULL
, 0x8719014c99c2b083ULL
,
235 0xdf7adabd7a6e2d6fULL
, 0xa2722586f2d042eeULL
, 0x256b24ca6b12f26dULL
, 0x5863dbf1e3ac9decULL
,
236 0x95ac9329ac4bc9b5ULL
, 0xe8a46c1224f5a634ULL
, 0x6fbd6d5ebd3716b7ULL
, 0x12b5926535897936ULL
,
237 0x4ad64994d625e4daULL
, 0x37deb6af5e9b8b5bULL
, 0xb0c7b7e3c7593bd8ULL
, 0xcdcf48d84fe75459ULL
240 static const unsigned int MAGIC
= 'z' + ('x'<< 8) + ('c' << 16) + ('v' << 24);
242 static unsigned int NumNodes
, NumChildLocs
, NumRanks
, NumChildMaps
;
243 static unsigned int SizeChildMapEntry
, NumLargeCounts
, NumSmallCounts
, SizeCharSet
;
245 static unsigned int *DictNodes
;
246 static unsigned short *ChildLocs
;
247 static unsigned short *Ranks
;
248 static uint8_t *ChildMap
;
249 static uint8_t *EndCountLge
;
250 static uint8_t *EndCountSml
;
251 static uint8_t *CharSet
;
253 /**********************************************************************************
254 * Calculate the CRC-64 of passed data.
256 * Crc The initial or previous CRC value
257 * v Pointer to the data to add to CRC calculation
258 * Len Length of the passed data
259 * Returns the updated CRC value.
261 static uint64_t CalcCrc64(uint64_t Crc
, const void *v
, unsigned int Len
)
263 const uint8_t *Data
= (const unsigned char *)v
;
266 Crc
= CrcTable
[(Crc
^ (*Data
>> 0)) & 0x0f] ^ (Crc
>> 4);
267 Crc
= CrcTable
[(Crc
^ (*Data
>> 4)) & 0x0f] ^ (Crc
>> 4);
273 /**********************************************************************************
274 * Read the dictionary data from file.
276 * Filename Name of the file to read.
277 * Returns 1 on success, 0 on error
279 int ZxcvbnInit(const char *Filename
)
282 uint64_t Crc
= CHK_INIT
;
285 MyOpenFile(f
, Filename
);
288 unsigned int i
, DictSize
;
290 /* Get magic number */
291 if (!MyReadFile(f
, &i
, sizeof i
))
294 /* Get header data */
295 if (!MyReadFile(f
, &NumNodes
, sizeof NumNodes
))
297 if (!MyReadFile(f
, &NumChildLocs
, sizeof NumChildLocs
))
299 if (!MyReadFile(f
, &NumRanks
, sizeof NumRanks
))
301 if (!MyReadFile(f
, &NumChildMaps
, sizeof NumChildMaps
))
303 if (!MyReadFile(f
, &SizeChildMapEntry
, sizeof SizeChildMapEntry
))
305 if (!MyReadFile(f
, &NumLargeCounts
, sizeof NumLargeCounts
))
307 if (!MyReadFile(f
, &NumSmallCounts
, sizeof NumSmallCounts
))
309 if (!MyReadFile(f
, &SizeCharSet
, sizeof SizeCharSet
))
312 /* Validate the header data */
313 if (NumNodes
>= (1<<16))
315 if (NumChildLocs
>= (1<<17))
317 if (NumChildMaps
>= (1<<13))
319 if ((SizeChildMapEntry
*8) < SizeCharSet
)
321 if (NumLargeCounts
>= (1<<8))
323 if (NumSmallCounts
!= NumNodes
)
331 Crc
= CalcCrc64(Crc
, &i
, sizeof i
);
332 Crc
= CalcCrc64(Crc
, &NumNodes
, sizeof NumNodes
);
333 Crc
= CalcCrc64(Crc
, &NumChildLocs
, sizeof NumChildLocs
);
334 Crc
= CalcCrc64(Crc
, &NumRanks
, sizeof NumRanks
);
335 Crc
= CalcCrc64(Crc
, &NumChildMaps
, sizeof NumChildMaps
);
336 Crc
= CalcCrc64(Crc
, &SizeChildMapEntry
, sizeof SizeChildMapEntry
);
337 Crc
= CalcCrc64(Crc
, &NumLargeCounts
, sizeof NumLargeCounts
);
338 Crc
= CalcCrc64(Crc
, &NumSmallCounts
, sizeof NumSmallCounts
);
339 Crc
= CalcCrc64(Crc
, &SizeCharSet
, sizeof SizeCharSet
);
341 DictSize
= NumNodes
*sizeof(unsigned int) + NumChildLocs
*sizeof(unsigned short) + NumRanks
*sizeof(unsigned short) +
342 NumChildMaps
*SizeChildMapEntry
+ NumLargeCounts
+ NumSmallCounts
+ SizeCharSet
;
344 if (DictSize
< MAX_DICT_FILE_SIZE
)
346 DictNodes
= MallocFn(unsigned int, DictSize
/ sizeof(unsigned int) + 1);
347 if (!MyReadFile(f
, DictNodes
, DictSize
))
358 Crc
= CalcCrc64(Crc
, DictNodes
, DictSize
);
359 if (memcmp(&Crc
, WordCheck
, sizeof Crc
))
366 /* Set pointers to the data */
367 ChildLocs
= (unsigned short *)(DictNodes
+ NumNodes
);
368 Ranks
= ChildLocs
+ NumChildLocs
;
369 ChildMap
= (unsigned char*)(Ranks
+ NumRanks
);
370 EndCountLge
= ChildMap
+ NumChildMaps
*SizeChildMapEntry
;
371 EndCountSml
= EndCountLge
+ NumLargeCounts
;
372 CharSet
= EndCountSml
+ NumSmallCounts
;
373 CharSet
[SizeCharSet
] = 0;
378 /**********************************************************************************
379 * Free the data allocated by ZxcvbnInit().
390 /* Include the source file containing the dictionary data */
391 #include "dict-src.h"
395 /**********************************************************************************
396 * Leet conversion strings
398 /* String of normal chars that could be given as leet chars in the password */
399 static const uint8_t L33TChr
[] = "abcegilostxz";
401 /* String of leet,normal,normal char triples. Used to convert supplied leet char to normal. */
402 static const uint8_t L33TCnv
[] = "!i $s %x (c +t 0o 1il2z 3e 4a 5s 6g 7lt8b 9g <c @a [c {c |il";
403 #define LEET_NORM_MAP_SIZE 3
405 /* Struct holding additional data on the word match */
408 int Rank
; /* Rank of word in dictionary */
409 int Caps
; /* Number of capital letters */
410 int Lower
; /* Number of lower case letters */
411 int NumLeet
; /* Total number of leeted characters */
412 uint8_t Leeted
[sizeof L33TChr
]; /* Number of leeted chars for each char found in L33TChr */
413 uint8_t UnLeet
[sizeof L33TChr
]; /* Number of normal chars for each char found in L33TChr */
417 /* Struct holding working data for the word match */
427 uint8_t Leeted
[sizeof L33TChr
];
428 uint8_t UnLeet
[sizeof L33TChr
];
429 uint8_t LeetCnv
[sizeof L33TCnv
/ LEET_NORM_MAP_SIZE
+ 1];
430 /* uint8_t LeetChr[3]; */
432 uint8_t PossChars
[48];
435 /**********************************************************************************
436 * Given a map entry create a string of all possible characters for following to
439 static int ListPossibleChars(uint8_t *List
, const uint8_t *Map
)
441 unsigned int i
, j
, k
;
443 for(k
= i
= 0; i
< SizeChildMapEntry
; ++i
, ++Map
)
450 for(j
= 0; j
< 8; ++j
)
454 *List
++ = CharSet
[k
];
464 /**********************************************************************************
465 * Increment count of each char that could be leeted.
467 static void AddLeetChr(uint8_t c
, int IsLeet
, uint8_t *Leeted
, uint8_t *UnLeet
)
469 const uint8_t *p
= CharBinSearch(c
, L33TChr
, sizeof L33TChr
- 1, 1);
489 /**********************************************************************************
490 * Given details of a word match, update it with the entropy (as natural log of
491 * number of possiblities)
493 static void DictionaryEntropy(ZxcMatch_t
*m
, DictMatchInfo_t
*Extra
, const uint8_t *Pwd
)
496 /* Add allowance for uppercase letters */
499 if (Extra
->Caps
== m
->Length
)
501 /* All uppercase, common case so only 1 bit */
504 else if ((Extra
->Caps
== 1) && (isupper(*Pwd
) || isupper(Pwd
[m
->Length
- 1])))
506 /* Only first or last uppercase, also common so only 1 bit */
511 /* Get number of combinations of lowercase, uppercase letters */
512 int Up
= Extra
->Caps
;
513 int Lo
= Extra
->Lower
;
517 for(Lo
+= Up
; i
>= 0; --i
)
524 /* Add allowance for using leet substitution */
529 for(i
= sizeof Extra
->Leeted
- 1; i
>= 0; --i
)
531 int Sb
= Extra
->Leeted
[i
];
534 int Un
= Extra
->UnLeet
[i
];
535 int j
= m
->Length
- Extra
->NumLeet
;
536 if ((j
>= 0) && (Un
> j
))
541 for(Un
+= Sb
; j
>= 0; --j
)
543 double z
= nCk(Un
, j
);
553 /*if(zz)printf(",%f ", d/log(2.0)); */
555 /* Add entropy due to word's rank */
556 e
+= log((double)Extra
->Rank
);
560 /**********************************************************************************
561 * Function that does the word matching
563 static void DoDictMatch(const uint8_t *Passwd
, int Start
, int MaxLen
, DictWork_t
*Wrk
, ZxcMatch_t
**Result
, DictMatchInfo_t
*Extra
, int Lev
)
566 uint8_t TempLeet
[LEET_NORM_MAP_SIZE
];
567 int Ord
= Wrk
->Ordinal
;
568 int Caps
= Wrk
->Caps
;
569 int Lower
= Wrk
->Lower
;
570 int NodeLoc
= Wrk
->StartLoc
;
571 uint8_t *PossChars
= Wrk
->PossChars
;
572 int NumPossChrs
= Wrk
->NumPossChrs
;
573 const uint8_t *Pwd
= Passwd
;
574 uint32_t NodeData
= DictNodes
[NodeLoc
];
576 for(Len
= 0; *Passwd
&& (Len
< MaxLen
); ++Len
, ++Passwd
)
582 if (!Len
&& Wrk
->First
)
588 /* Get char and set of possible chars at current point in word. */
591 Bmap
= ChildMap
+ (NodeData
& ((1<<13)-1)) * SizeChildMapEntry
;
592 NumPossChrs
= ListPossibleChars(PossChars
, Bmap
);
594 /* Make it lowercase and update lowercase, uppercase counts */
604 /* See if current char is a leet and can be converted */
605 q
= CharBinSearch(c
, L33TCnv
, sizeof L33TCnv
/ LEET_NORM_MAP_SIZE
, LEET_NORM_MAP_SIZE
);
608 /* Found, see if used before */
610 unsigned int i
= (q
- L33TCnv
) / LEET_NORM_MAP_SIZE
;
613 /* Used before, so limit characters to try */
615 TempLeet
[1] = Wrk
->LeetCnv
[i
];
619 for(j
= 0; (*q
> ' ') && (j
< LEET_NORM_MAP_SIZE
); ++j
, ++q
)
621 const uint8_t *r
= CharBinSearch(*q
, PossChars
, NumPossChrs
, 1);
624 /* valid conversion from leet */
627 w
.StartLoc
= NodeLoc
;
633 w
.NumPossChrs
= NumPossChrs
;
634 memcpy(w
.PossChars
, PossChars
, sizeof w
.PossChars
);
638 AddLeetChr(*r
, -1, w
.Leeted
, w
.UnLeet
);
640 DoDictMatch(Pwd
, Passwd
- Pwd
, MaxLen
- Len
, &w
, Result
, Extra
, Lev
+1);
646 q
= CharBinSearch(c
, PossChars
, NumPossChrs
, 1);
649 /* Found the char as a normal char */
650 if (CharBinSearch(c
, L33TChr
, sizeof L33TChr
- 1, 1))
652 /* Char matches, but also a normal equivalent to a leet char */
653 AddLeetChr(c
, 0, Wrk
->Leeted
, Wrk
->UnLeet
);
658 /* No match for char - return */
661 /* Add all the end counts of the child nodes before the one that matches */
662 x
= (q
- Wrk
->PossChars
);
663 y
= (NodeData
>> 13) & ((1<<17)-1);
664 NodeLoc
= ChildLocs
[x
+y
];
667 int Cloc
= ChildLocs
[w
+y
];
668 z
= EndCountSml
[Cloc
];
669 if (DictNodes
[Cloc
] & (1<<31))
670 z
+= EndCountLge
[Cloc
]*256;
674 /* Move to next node */
675 NodeData
= DictNodes
[NodeLoc
];
676 if (NodeData
& (1<<30))
678 /* Word matches, save result */
681 Extra
->Rank
= Ranks
[Ord
];
682 Extra
->Lower
= Lower
;
683 for(x
= 0, y
= sizeof Extra
->Leeted
- 1; y
>= 0; --y
)
687 memcpy(Extra
->UnLeet
, Wrk
->UnLeet
, sizeof Extra
->UnLeet
);
688 memcpy(Extra
->Leeted
, Wrk
->Leeted
, sizeof Extra
->Leeted
);
692 p
->Type
= DICT_LEET_MATCH
;
694 p
->Type
= DICTIONARY_MATCH
;
695 p
->Length
= Wrk
->PwdLength
+ Len
+ 1;
696 p
->Begin
= Wrk
->Begin
;
697 DictionaryEntropy(p
, Extra
, Pwd
);
698 AddResult(Result
, p
);
705 /**********************************************************************************
706 * Try to match password part with user supplied dictionary words
708 * Result Pointer head of linked list used to store results
709 * Words Array of pointers to dictionary words
710 * Passwd The start of the password
711 * Start Where in the password to start attempting to match
712 * MaxLen Maximum number characters to consider
714 static void UserMatch(ZxcMatch_t
**Result
, const char *Words
[], const uint8_t *Passwd
, int Start
, int MaxLen
)
720 for(Rank
= 0; Words
[Rank
]; ++Rank
)
722 DictMatchInfo_t Extra
;
723 uint8_t LeetChr
[sizeof L33TCnv
/ LEET_NORM_MAP_SIZE
+ 1];
729 const uint8_t *Wrd
= (const uint8_t *)(Words
[Rank
]);
730 const uint8_t *Pwd
= Passwd
;
731 memset(Extra
.Leeted
, 0, sizeof Extra
.Leeted
);
732 memset(Extra
.UnLeet
, 0, sizeof Extra
.UnLeet
);
733 memset(LeetChr
, 0, sizeof LeetChr
);
737 uint8_t d
= tolower(*Wrd
++);
750 /* See if current char is a leet and can be converted */
751 q
= CharBinSearch(c
, L33TCnv
, sizeof L33TCnv
/ LEET_NORM_MAP_SIZE
, LEET_NORM_MAP_SIZE
);
754 /* Found, see if used before */
756 unsigned int i
= (q
- L33TCnv
) / LEET_NORM_MAP_SIZE
;
759 /* Used before, so limit characters to try */
761 TempLeet
[1] = LeetChr
[i
];
766 for(j
= 0; (*q
> ' ') && (j
< LEET_NORM_MAP_SIZE
); ++j
, ++q
)
774 AddLeetChr(c
, 1, Extra
.Leeted
, Extra
.UnLeet
);
788 /* Found the char as a normal char */
789 if (CharBinSearch(c
, L33TChr
, sizeof L33TChr
- 1, 1))
791 /* Char matches, but also a normal equivalent to a leet char */
792 AddLeetChr(c
, 0, Extra
.Leeted
, Extra
.UnLeet
);
809 ZxcMatch_t
*p
= AllocMatch();
811 p
->Type
= USER_MATCH
;
813 p
->Type
= USER_LEET_MATCH
;
818 Extra
.Lower
= Lowers
;
819 Extra
.NumLeet
= Leets
;
821 DictionaryEntropy(p
, &Extra
, Passwd
);
822 AddResult(Result
, p
);
828 /**********************************************************************************
829 * Try to match password part with the dictionary words
831 * Result Pointer head of linked list used to store results
832 * Passwd The start of the password
833 * Start Where in the password to start attempting to match
834 * MaxLen Maximum number characters to consider
836 static void DictionaryMatch(ZxcMatch_t
**Result
, const uint8_t *Passwd
, int Start
, int MaxLen
)
839 DictMatchInfo_t Extra
;
841 memset(&Extra
, 0, sizeof Extra
);
842 memset(&Wrk
, 0, sizeof Wrk
);
844 Wrk
.StartLoc
= ROOT_NODE_LOC
;
846 DoDictMatch(Passwd
+Start
, 0, MaxLen
, &Wrk
, Result
, &Extra
, 0);
850 /*################################################################################*
851 *################################################################################*
852 * Begin keyboard spatial sequence matching code
853 *################################################################################*
854 *################################################################################*/
856 #define MIN_SPATIAL_LEN 3
858 /* Struct to hold information on a keyboard layout */
859 typedef struct Keyboard
862 const uint8_t *Shifts
;
869 /* Struct to hold information on the match */
875 } SpatialMatchInfo_t
;
877 /* Shift mapping, characters in pairs: first is shifted, second un-shifted. */
878 static const uint8_t UK_Shift
[] = "!1\"2$4%5&7(9)0*8:;<,>.?/@'AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~#€4£3¬`";
879 static const uint8_t US_Shift
[] = "!1\"'#3$4%5&7(9)0*8:;<,>.?/@2AaBbCcDdEeFfGgHhIiJjKkLlMmNnOoPpQqRrSsTtUuVvWwXxYyZz^6_-{[|\\}]~`";
882 /* Neighour tables */
883 static const uint8_t UK_Qwerty
[48*7] =
885 /* key, left, up-left, up-right, right, down-right, down-left */
886 '#', '\'',']', 0, 0, 0, 0, '\'',';', '[', ']', '#', 0, '/',
887 ',', 'm', 'k', 'l', '.', 0, 0, '-', '0', 0, 0, '-', 'p', 'o',
888 '.', ',', 'l', ';', '/', 0, 0, '/', '.', ';', '\'', 0, 0, 0,
889 '0', '9', 0, 0, '-', 'p', 'o', '1', '`', 0, 0, '2', 'q', 0,
890 '2', '1', 0, 0, '3', 'w', 'q', '3', '2', 0, 0, '4', 'e', 'w',
891 '4', '3', 0, 0, '5', 'r', 'e', '5', '4', 0, 0, '6', 't', 'r',
892 '6', '5', 0, 0, '7', 'y', 't', '7', '6', 0, 0, '8', 'u', 'y',
893 '8', '7', 0, 0, '9', 'i', 'u', '9', '8', 0, 0, '0', 'o', 'i',
894 ';', 'l', 'o', 'p','\'', '/', '.', '=', '-', 0, 0, 0, ']', '[',
895 '[', 'p', '-', '=', ']', '\'',';', '\\', 0, 0, 'a', 'z', 0, 0,
896 ']', '[', '=', 0, 0, '#','\'', '`', 0, 0, 0, '1', 0, 0,
897 'a', 0, 'q', 'w', 's', 'z','\\', 'b', 'v', 'g', 'h', 'n', 0, 0,
898 'c', 'x', 'd', 'f', 'v', 0, 0, 'd', 's', 'e', 'r', 'f', 'c', 'x',
899 'e', 'w', '3', '4', 'r', 'd', 's', 'f', 'd', 'r', 't', 'g', 'v', 'c',
900 'g', 'f', 't', 'y', 'h', 'b', 'v', 'h', 'g', 'y', 'u', 'j', 'n', 'b',
901 'i', 'u', '8', '9', 'o', 'k', 'j', 'j', 'h', 'u', 'i', 'k', 'm', 'n',
902 'k', 'j', 'i', 'o', 'l', ',', 'm', 'l', 'k', 'o', 'p', ';', '.', ',',
903 'm', 'n', 'j', 'k', ',', 0, 0, 'n', 'b', 'h', 'j', 'm', 0, 0,
904 'o', 'i', '9', '0', 'p', 'l', 'k', 'p', 'o', '0', '-', '[', ';', 'l',
905 'q', 0, '1', '2', 'w', 'a', 0, 'r', 'e', '4', '5', 't', 'f', 'd',
906 's', 'a', 'w', 'e', 'd', 'x', 'z', 't', 'r', '5', '6', 'y', 'g', 'f',
907 'u', 'y', '7', '8', 'i', 'j', 'h', 'v', 'c', 'f', 'g', 'b', 0, 0,
908 'w', 'q', '2', '3', 'e', 's', 'a', 'x', 'z', 's', 'd', 'c', 0, 0,
909 'y', 't', '6', '7', 'u', 'h', 'g', 'z', '\\','a', 's', 'x', 0, 0
912 static const uint8_t US_Qwerty
[47*7] =
914 /* key, left, up-left, up-right, right, down-right, down-left */
915 '\'',';', '[', ']', 0, 0, '/', ',', 'm', 'k', 'l', '.', 0, 0,
916 '-', '0', 0, 0, '=', '[', 'p', '.', ',', 'l', ';', '/', 0, 0,
917 '/', '.', ';','\'', 0, 0, 0, '0', '9', 0, 0, '-', 'p', 'o',
918 '1', '`', 0, 0, '2', 'q', 0, '2', '1', 0, 0, '3', 'w', 'q',
919 '3', '2', 0, 0, '4', 'e', 'w', '4', '3', 0, 0, '5', 'r', 'e',
920 '5', '4', 0, 0, '6', 't', 'r', '6', '5', 0, 0, '7', 'y', 't',
921 '7', '6', 0, 0, '8', 'u', 'y', '8', '7', 0, 0, '9', 'i', 'u',
922 '9', '8', 0, 0, '0', 'o', 'i', ';', 'l', 'p', '[','\'', '/', '.',
923 '=', '-', 0, 0, 0, ']', '[', '[', 'p', '-', '=', ']','\'', ';',
924 '\\',']', 0, 0, 0, 0, 0, ']', '[', '=', 0,'\\', 0,'\'',
925 '`', 0, 0, 0, '1', 0, 0, 'a', 0, 'q', 'w', 's', 'z', 0,
926 'b', 'v', 'g', 'h', 'n', 0, 0, 'c', 'x', 'd', 'f', 'v', 0, 0,
927 'd', 's', 'e', 'r', 'f', 'c', 'x', 'e', 'w', '3', '4', 'r', 'd', 's',
928 'f', 'd', 'r', 't', 'g', 'v', 'c', 'g', 'f', 't', 'y', 'h', 'b', 'v',
929 'h', 'g', 'y', 'u', 'j', 'n', 'b', 'i', 'u', '8', '9', 'o', 'k', 'j',
930 'j', 'h', 'u', 'i', 'k', 'm', 'n', 'k', 'j', 'i', 'o', 'l', ',', 'm',
931 'l', 'k', 'o', 'p', ';', '.', ',', 'm', 'n', 'j', 'k', ',', 0, 0,
932 'n', 'b', 'h', 'j', 'm', 0, 0, 'o', 'i', '9', '0', 'p', 'l', 'k',
933 'p', 'o', '0', '-', '[', ';', 'l', 'q', 0, '1', '2', 'w', 'a', 0,
934 'r', 'e', '4', '5', 't', 'f', 'd', 's', 'a', 'w', 'e', 'd', 'x', 'z',
935 't', 'r', '5', '6', 'y', 'g', 'f', 'u', 'y', '7', '8', 'i', 'j', 'h',
936 'v', 'c', 'f', 'g', 'b', 0, 0, 'w', 'q', '2', '3', 'e', 's', 'a',
937 'x', 'z', 's', 'd', 'c', 0, 0, 'y', 't', '6', '7', 'u', 'h', 'g',
938 'z', 0, 'a', 's', 'x', 0, 0,
940 static const uint8_t Dvorak
[48*7] =
942 '\'', 0, '1', '2', ',', 'a', 0, ',','\'', '2', '3', '.', 'o', 'a',
943 '-', 's', '/', '=', 0, 0, 'z', '.', ',', '3', '4', 'p', 'e', 'o',
944 '/', 'l', '[', ']', '=', '-', 's', '0', '9', 0, 0, '[', 'l', 'r',
945 '1', '`', 0, 0, '2','\'', 0, '2', '1', 0, 0, '3', ',','\'',
946 '3', '2', 0, 0, '4', '.', ',', '4', '3', 0, 0, '5', 'p', '.',
947 '5', '4', 0, 0, '6', 'y', 'p', '6', '5', 0, 0, '7', 'f', 'y',
948 '7', '6', 0, 0, '8', 'g', 'f', '8', '7', 0, 0, '9', 'c', 'g',
949 '9', '8', 0, 0, '0', 'r', 'c', ';', 0, 'a', 'o', 'q', 0, 0,
950 '=', '/', ']', 0,'\\', 0, '-', '[', '0', 0, 0, ']', '/', 'l',
951 '\\','=', 0, 0, 0, 0, 0, ']', '[', 0, 0, 0, '=', '/',
952 '`', 0, 0, 0, '1', 0, 0, 'a', 0,'\'', ',', 'o', ';', 0,
953 'b', 'x', 'd', 'h', 'm', 0, 0, 'c', 'g', '8', '9', 'r', 't', 'h',
954 'd', 'i', 'f', 'g', 'h', 'b', 'x', 'e', 'o', '.', 'p', 'u', 'j', 'q',
955 'f', 'y', '6', '7', 'g', 'd', 'i', 'g', 'f', '7', '8', 'c', 'h', 'd',
956 'h', 'd', 'g', 'c', 't', 'm', 'b', 'i', 'u', 'y', 'f', 'd', 'x', 'k',
957 'j', 'q', 'e', 'u', 'k', 0, 0, 'k', 'j', 'u', 'i', 'x', 0, 0,
958 'l', 'r', '0', '[', '/', 's', 'n', 'm', 'b', 'h', 't', 'w', 0, 0,
959 'n', 't', 'r', 'l', 's', 'v', 'w', 'o', 'a', ',', '.', 'e', 'q', ';',
960 'p', '.', '4', '5', 'y', 'u', 'e', 'q', ';', 'o', 'e', 'j', 0, 0,
961 'r', 'c', '9', '0', 'l', 'n', 't', 's', 'n', 'l', '/', '-', 'z', 'v',
962 't', 'h', 'c', 'r', 'n', 'w', 'm', 'u', 'e', 'p', 'y', 'i', 'k', 'j',
963 'v', 'w', 'n', 's', 'z', 0, 0, 'w', 'm', 't', 'n', 'v', 0, 0,
964 'x', 'k', 'i', 'd', 'b', 0, 0, 'y', 'p', '5', '6', 'f', 'i', 'u',
965 'z', 'v', 's', '-', 0, 0, 0
968 static const uint8_t PC_Keypad
[15*9] =
970 /*Key, left, up-left, up, up-right, right, down-right, down, down-left */
971 '*', '/', 0, 0, 0, '-', '+', '9', '8',
972 '+', '9', '*', '-', 0, 0, 0, 0, '6',
973 '-', '*', 0, 0, 0, 0, 0, '+', '9',
974 '.', '0', '2', '3', 0, 0, 0, 0, 0,
975 '/', 0, 0, 0, 0, '*', '9', '8', '7',
976 '0', 0, '1', '2', '3', '.', 0, 0, 0,
977 '1', 0, 0, '4', '5', '2', '0', 0, 0,
978 '2', '1', '4', '5', '6', '3', '.', '0', 0,
979 '3', '2', '5', '6', 0, 0, 0, '.', '0',
980 '4', 0, 0, '7', '8', '5', '2', '1', 0,
981 '5', '4', '7', '8', '9', '6', '3', '2', '1',
982 '6', '5', '8', '9', '+', 0, 0, '3', '2',
983 '7', 0, 0, 0, '/', '8', '5', '4', 0,
984 '8', '7', 0, '/', '*', '9', '6', '5', '4',
985 '9', '8', '/', '*', '-', '+', 0, '6', '5'
988 static const uint8_t MacKeypad
[16*9] =
990 '*', '/', 0, 0, 0, 0, 0, '-', '9',
991 '+', '6', '9', '-', 0, 0, 0, 0, '3',
992 '-', '9', '/', '*', 0, 0, 0, '+', '6',
993 '.', '0', '2', '3', 0, 0, 0, 0, 0,
994 '/', '=', 0, 0, 0, '*', '-', '9', '8',
995 '0', 0, '1', '2', '3', '.', 0, 0, 0,
996 '1', 0, 0, '4', '5', '2', '0', 0, 0,
997 '2', '1', '4', '5', '6', '3', '.', '0', 0,
998 '3', '2', '5', '6', '+', 0, 0, '.', '0',
999 '4', 0, 0, '7', '8', '5', '2', '1', 0,
1000 '5', '4', '7', '8', '9', '6', '3', '2', '1',
1001 '6', '5', '8', '9', '-', '+', 0, '3', '2',
1002 '7', 0, 0, 0, '=', '8', '5', '4', 0,
1003 '8', '7', 0, '=', '/', '9', '6', '5', '4',
1004 '9', '8', '=', '/', '*', '-', '+', '6', '5',
1005 '=', 0, 0, 0, 0, '/', '9', '8', '7'
1008 static const Keyboard_t Keyboards
[] =
1010 { US_Qwerty
, US_Shift
, sizeof US_Qwerty
/ 7, 7, sizeof US_Shift
/ 2, 66 },
1011 { Dvorak
, US_Shift
, sizeof Dvorak
/ 7, 7, sizeof US_Shift
/ 2, 66 },
1012 { UK_Qwerty
, UK_Shift
, sizeof UK_Qwerty
/ 7, 7, sizeof UK_Shift
/ 2, 66 },
1013 { MacKeypad
, 0, sizeof MacKeypad
/ 9, 9, 0, 44 },
1014 { PC_Keypad
, 0, sizeof PC_Keypad
/ 9, 9, 0, 44 }
1017 /**********************************************************************************
1018 * Match password for the given keyboard layout
1020 static int DoSptlMatch(const uint8_t *Passwd
, int MaxLen
, const Keyboard_t
*Keyb
, SpatialMatchInfo_t
*Extra
)
1027 uint8_t PrevChar
= 0;
1028 for( ; *Passwd
&& (Len
< MaxLen
); ++Passwd
, ++Len
)
1032 uint8_t CurChar
= *Passwd
;
1033 /* Try to unshift the character */
1036 Key
= CharBinSearch(CurChar
, Keyb
->Shifts
, Keyb
->NumShift
, 2);
1046 /* See if the pattern can be extended */
1048 Key
= CharBinSearch(PrevChar
, Keyb
->Keys
, Keyb
->NumKeys
, Keyb
->NumNear
);
1051 for(i
= Keyb
->NumNear
- 1; i
> 0; --i
)
1053 if (Key
[i
] == CurChar
)
1059 Turns
+= (i
!= Dir
);
1070 if (Len
>= MIN_SPATIAL_LEN
)
1072 Extra
->Turns
= Turns
;
1073 Extra
->Shifts
= ShiftCount
;
1079 /**********************************************************************************
1080 * Try to match spatial patterns on the keyboard
1082 * Result Pointer head of linked list used to store results
1083 * Passwd The start of the password
1084 * Start Where in the password to start attempting to match
1085 * MaxLen Maximum number characters to consider
1087 static void SpatialMatch(ZxcMatch_t
**Result
, const uint8_t *Passwd
, int Start
, int MaxLen
)
1091 SpatialMatchInfo_t Extra
;
1092 const Keyboard_t
*k
;
1095 for(CurLen
= MaxLen
; CurLen
>= MIN_SPATIAL_LEN
;CurLen
= Len
- 1)
1098 memset(&Extra
, 0, sizeof Extra
);
1099 for(k
= Keyboards
, Indx
= 0; Indx
< (sizeof Keyboards
/ sizeof Keyboards
[0]); ++Indx
, ++k
)
1101 Len
= DoSptlMatch(Passwd
, CurLen
, k
, &Extra
);
1104 /* Got a sequence of required length so add to result list */
1106 double Degree
, Entropy
;
1108 Degree
= (k
->NumNear
-1) - (double)k
->NumBlank
/ (double)k
->NumKeys
;
1113 /* Estimate the number of possible patterns with length ranging 2 to match length and */
1114 /* with turns ranging from 0 to match turns */
1116 for(i
= 2; i
<= Len
; ++i
)
1118 int PossTurns
= Extra
.Turns
;
1121 for(j
= 1; j
<= PossTurns
; ++j
)
1122 Entropy
+= nCk(i
-1, j
-1) * pow(Degree
, j
) * s
;
1125 Entropy
= log(Entropy
);
1128 /* Add extra entropy for shifted keys. (% instead of 5, A instead of a etc.) */
1129 /* Math is similar to extra entropy from uppercase letters in dictionary matches. */
1130 int Shift
= Extra
.Shifts
;
1131 int Unshift
= Len
- Shift
;
1137 for(i
= 0; i
<= j
; ++i
)
1139 Degree
+= nCk(Len
, i
);
1142 Entropy
+= log(Degree
);
1145 p
->Type
= SPATIAL_MATCH
;
1147 p
->Entrpy
= Entropy
;
1149 AddResult(Result
, p
);
1157 /*################################################################################*
1158 *################################################################################*
1159 * Begin date matching code
1160 *################################################################################*
1161 *################################################################################*/
1163 #define MIN_YEAR 1901
1164 #define MAX_YEAR 2019
1166 /* The possible date formats ordered by length (d for day, m for month, */
1167 /* y for year, ? for separator) */
1168 static const char *Formats
[] =
1193 /* Possible separator characters that could be used */
1194 static const char DateSeperators
[] = "/\\-_. ";
1196 /**********************************************************************************
1197 * Try to match the password with the formats above.
1199 static void DateMatch(ZxcMatch_t
**Result
, const uint8_t *Passwd
, int Start
, int MaxLen
)
1207 for(CurFmt
= 0; Formats
[CurFmt
]; ++CurFmt
)
1214 const uint8_t *p
= Passwd
;
1218 /* Scan along the format, trying to match the password */
1219 for(Fmt
= Formats
[CurFmt
]; *Fmt
&& !Fail
; ++Fmt
)
1223 if (!Sep
&& strchr(DateSeperators
, *p
))
1227 else if (isdigit(*p
))
1231 Day
= 10 * Day
+ *p
- '0';
1233 else if (*Fmt
== 'm')
1235 Mon
= 10 * Mon
+ *p
- '0';
1239 Year
= 10 * Year
+ *p
- '0';
1256 /* Character matching is OK, now check to see if valid date */
1257 if (((YrLen
> 3) || (Len
<= 4)) && ((Year
< MIN_YEAR
) || (Year
> MAX_YEAR
)))
1261 if ((Mon
> 12) && (Day
< 13))
1263 /* Swap day,month to try to make both in range */
1268 /* Check for valid day, month. Currently assumes all months have 31 days. */
1269 if ((Mon
< 1) || (Mon
> 12))
1271 else if ((Day
< 1) || (Day
> 31))
1275 if (!Fail
&& (Len
> PrevLen
))
1277 /* String matched the date, store result */
1279 ZxcMatch_t
*p
= AllocMatch();
1282 e
= log(MAX_YEAR
- MIN_YEAR
+ 1.0);
1284 e
= log(31 * 12 * (MAX_YEAR
- MIN_YEAR
+ 1.0));
1286 e
= log(31 * 12 * 100.0);
1288 e
+= log(4.0); /* Extra 2 bits for separator */
1290 p
->Type
= DATE_MATCH
;
1293 AddResult(Result
, p
);
1300 /*################################################################################*
1301 *################################################################################*
1302 * Begin repeated character matching code
1303 *################################################################################*
1304 *################################################################################*/
1306 #define MIN_REPEAT_LEN 3
1308 /**********************************************************************************
1309 * Try to match password part as a set of repeated characters.
1311 * Result Pointer head of linked list used to store results
1312 * Passwd The start of the password
1313 * Start Where in the password to start attempting to match
1314 * MaxLen Maximum number characters to consider
1316 static void RepeatMatch(ZxcMatch_t
**Result
, const uint8_t *Passwd
, int Start
, int MaxLen
)
1321 /* Remember first char and the count its occurances */
1323 for(Len
= 1; (Len
< MaxLen
) && (c
== Passwd
[Len
]); ++Len
)
1325 if (Len
>= MIN_REPEAT_LEN
)
1327 /* Enough repeated char, so create results from number found down to min acceptable repeats */
1328 double Card
= Cardinality(&c
, 1);
1329 for(i
= Len
; i
>= MIN_REPEAT_LEN
; --i
)
1331 ZxcMatch_t
*p
= AllocMatch();
1332 p
->Type
= REPEATS_MATCH
;
1335 p
->Entrpy
= log(Card
* i
);
1336 AddResult(Result
, p
);
1342 /**********************************************************************************
1343 **********************************************************************************
1344 * Begin character sequence matching code
1345 **********************************************************************************
1346 *********************************************************************************/
1348 #define MIN_SEQUENCE_LEN 3
1350 /**********************************************************************************
1351 * Try to match password part as a set of incrementing or decrementing characters.
1353 * Result Pointer head of linked list used to store results
1354 * Passwd The start of the password
1355 * Start Where in the password to start attempting to match
1356 * MaxLen Maximum number characters to consider
1358 static void SequenceMatch(ZxcMatch_t
**Result
, const uint8_t *Passwd
, int Start
, int MaxLen
)
1361 int SetLow
, SetHigh
, Dir
;
1362 uint8_t First
, Next
;
1366 Dir
= Passwd
[1] - First
;
1368 /* Decide on min and max character code for sequence */
1369 if (islower(*Passwd
))
1374 else if (isupper(*Passwd
))
1379 else if (isdigit(*Passwd
))
1383 if ((First
== '0') && (Dir
== 9))
1385 /* Special case for decrementing sequence of digits, allow starting with 098 */
1394 if ((Dir
== 1) || (Dir
== -1))
1399 if ((Passwd
[0] == '9') && (Passwd
[1] == '0') && (Dir
> 0))
1405 Next
= Passwd
[0] + Dir
;
1406 if ((Next
> SetHigh
) || (Next
< SetLow
) || (Passwd
[1] != Next
))
1414 if (Len
>= MIN_SEQUENCE_LEN
)
1416 /* Enough repeated char, so create results from number found down to min acceptable length */
1419 if ((First
== 'a') || (First
== '1'))
1421 else if (isdigit(First
))
1423 else if (isupper(First
))
1430 for(i
= Len
; i
>= MIN_SEQUENCE_LEN
; --i
)
1432 ZxcMatch_t
*p
= AllocMatch();
1433 /* Add new result to head of list as it has lower entropy */
1434 p
->Type
= SEQUENCE_MATCH
;
1437 p
->Entrpy
= e
+ log((double)i
);
1438 AddResult(Result
, p
);
1444 /**********************************************************************************
1445 **********************************************************************************
1446 * Begin top level zxcvbn code
1447 **********************************************************************************
1448 *********************************************************************************/
1451 /**********************************************************************************
1452 * Matching a password is treated as a problem of finding the minimum distance
1453 * between two vertexes in a graph. This is solved using Dijkstra's algorithm.
1455 * There are a series of nodes (or vertexes in graph terminology) which correspond
1456 * to points between each character of the password. Also there is a start node
1457 * before the first character and an end node after the last character.
1459 * The paths between the nodes (or edges in graph terminology) correspond to the
1460 * matched parts of the password (e.g. dictionary word, repeated characters etc).
1461 * The distance of the path is equal to the entropy of the matched part. A default
1462 * single character bruteforce match path is also added for all nodes except the
1465 * Dijkstra's algorithm finds the combination of these part matches (or paths)
1466 * which gives the lowest entropy (or smallest distance) from begining to end
1470 /* Struct to hold the data of a node (imaginary point between password characters) */
1473 ZxcMatch_t
*Paths
; /* Partial matches that lead to a following node */
1474 double Dist
; /* Distance (or entropy) from start of password to this node */
1475 ZxcMatch_t
*From
; /* Which path was used to get to this node with lowest distance/entropy */
1476 int Visit
; /* Non zero when node has been visited during Dijkstra evaluation */
1479 /**********************************************************************************
1480 * Main function of the zxcvbn password entropy estimation
1482 double ZxcvbnMatch(const char *Pwd
, const char *UserDict
[], ZxcMatch_t
**Info
)
1488 int Len
= strlen(Pwd
);
1489 const uint8_t *Passwd
= (const uint8_t *)Pwd
;
1490 /* Create the paths */
1491 Node_t
*Nodes
= MallocFn(Node_t
, Len
+1);
1492 memset(Nodes
, 0, (Len
+1) * sizeof *Nodes
);
1493 i
= Cardinality(Passwd
, Len
);
1496 /* Do matching for all parts of the password */
1497 for(i
= 0; i
< Len
; ++i
)
1499 int MaxLen
= Len
- i
;
1500 /* Add all the 'paths' between groups of chars in the password, for current starting char */
1501 UserMatch(&(Nodes
[i
].Paths
), UserDict
, Passwd
, i
, MaxLen
);
1502 DictionaryMatch(&(Nodes
[i
].Paths
), Passwd
, i
, MaxLen
);
1503 DateMatch(&(Nodes
[i
].Paths
), Passwd
, i
, MaxLen
);
1504 SpatialMatch(&(Nodes
[i
].Paths
), Passwd
, i
, MaxLen
);
1505 SequenceMatch(&(Nodes
[i
].Paths
), Passwd
, i
, MaxLen
);
1506 RepeatMatch(&(Nodes
[i
].Paths
), Passwd
, i
, MaxLen
);
1508 /* Add a default one character bruteforce path */
1510 Zp
->Type
= BRUTE_MATCH
;
1514 AddResult(&(Nodes
[i
].Paths
), Zp
);
1516 /* Initially set distance to nearly infinite */
1517 Nodes
[i
].Dist
= DBL_MAX
;
1520 /* End node has infinite distance/entropy, start node has 0 distance */
1521 Nodes
[i
].Dist
= DBL_MAX
;
1522 Nodes
[0].Dist
= 0.0;
1524 /* Reduce the paths using Dijkstra's algorithm */
1525 for(i
= 0; i
< Len
; ++i
)
1528 double MinDist
= DBL_MAX
;
1530 /* Find the unvisited node with minimum distance or entropy */
1531 for(Np
= Nodes
, j
= 0; j
< Len
; ++j
, ++Np
)
1533 if (!Np
->Visit
&& (Np
->Dist
< MinDist
))
1539 /* Mark the minimum distance node as visited */
1540 Np
= Nodes
+ MinIdx
;
1543 /* Update all unvisited neighbouring nodes with their new distance. A node is a */
1544 /* neighbour if there is a path/match from current node Np to it. The neighbour */
1545 /* distance is the current node distance plus the path distance/entropy. Only */
1546 /* update if the new distance is smaller. */
1547 for(Zp
= Np
->Paths
; Zp
; Zp
= Zp
->Next
)
1549 Node_t
*Ep
= Np
+ Zp
->Length
;
1550 double d
= e
+ Zp
->Entrpy
;
1551 if (!Ep
->Visit
&& (d
< Ep
->Dist
))
1553 /* Update as lower dist, also remember the 'from' node */
1558 /* If we got to the end node stop early */
1559 /*if (Nodes[Len].Dist < DBL_MAX/2.0) */
1562 /* Make e hold entropy result and adjust to log base 2 */
1563 e
= Nodes
[Len
].Dist
/ log(2.0);
1567 /* Construct info on password parts */
1569 for(Zp
= Nodes
[Len
].From
; Zp
; )
1574 /* Remove all but required path */
1575 Xp
= Nodes
[i
].Paths
;
1579 ZxcMatch_t
*p
= Xp
->Next
;
1582 /* Adjust the entropy to log to base 2 */
1583 Xp
->Entrpy
/= log(2.0);
1584 if ((*Info
) && (Xp
->Type
== BRUTE_MATCH
) && ((*Info
)->Type
== BRUTE_MATCH
))
1586 /* Previous part and current are bruteforce, merge then into single entry */
1587 (*Info
)->Begin
= Xp
->Begin
;
1588 (*Info
)->Length
+= Xp
->Length
;
1589 (*Info
)->Entrpy
+= Xp
->Entrpy
;
1594 /* Put previous part at head of info list */
1601 /* Not going on info list, so free it */
1609 /* Free all paths. Any being returned to caller have already been freed */
1610 for(i
= 0; i
<= Len
; ++i
)
1612 Zp
= Nodes
[i
].Paths
;
1615 ZxcMatch_t
*p
= Zp
->Next
;
1625 /**********************************************************************************
1626 * Free the path info returned by ZxcvbnMatch().
1628 void ZxcvbnFreeInfo(ZxcMatch_t
*Info
)