aboutsummaryrefslogtreecommitdiffhomepage
path: root/zxcvbn.c
diff options
context:
space:
mode:
Diffstat (limited to 'zxcvbn.c')
-rw-r--r--zxcvbn.c323
1 files changed, 228 insertions, 95 deletions
diff --git a/zxcvbn.c b/zxcvbn.c
index bfb40b3..f9678c5 100644
--- a/zxcvbn.c
+++ b/zxcvbn.c
@@ -50,13 +50,32 @@
#include "stdafx.h"
#endif
+/* Minimum number of characters in a incrementing/decrementing sequence match */
+#define MIN_SEQUENCE_LEN 3
+
+/* Year range for data matching */
+#define MIN_YEAR 1901
+#define MAX_YEAR 2050
+
+/* Minimum number of characters in a spatial matching sequence */
+#define MIN_SPATIAL_LEN 3
+
+/* Minimum number of characters in a repeat sequence match */
+#define MIN_REPEAT_LEN 2
+
+/* Additional entropy to add when password is made of multiple matches. Use different
+ * amounts depending on whether the match is at the end of the password, or in the
+ * middle. If the match is at the begining then there is no additional entropy.
+ */
+#define MULTI_END_ADDITION 1.0
+#define MULTI_MID_ADDITION 1.75
+
/*################################################################################*
*################################################################################*
* Begin utility function code
*################################################################################*
*################################################################################*/
-
/**********************************************************************************
* Binomial coefficient function. Uses method described at
* http://blog.plover.com/math/choose.html
@@ -150,10 +169,23 @@ static ZxcMatch_t *AllocMatch()
/**********************************************************************************
* Add new match struct to linked list of matches. List ordered with shortest at
- * head of list.
+ * head of list. Note: passed new match struct in parameter Nu may be de allocated.
*/
-static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu)
+static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu, int MaxLen)
{
+ /* Adjust the entropy to be used for calculations depending on whether the passed match is
+ * at the begining, middle or end of the password
+ */
+ if (Nu->Begin)
+ {
+ if (Nu->Length >= MaxLen)
+ Nu->MltEnpy = Nu->Entrpy + MULTI_END_ADDITION * log(2.0);
+ else
+ Nu->MltEnpy = Nu->Entrpy + MULTI_MID_ADDITION * log(2.0);
+ }
+ else
+ Nu->MltEnpy = Nu->Entrpy;
+
/* Find the correct insert point */
while(*HeadRef && ((*HeadRef)->Length < Nu->Length))
HeadRef = &((*HeadRef)->Next);
@@ -162,7 +194,7 @@ static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu)
if (*HeadRef && ((*HeadRef)->Length == Nu->Length))
{
/* New entry has same length as existing, so one of them needs discarding */
- if ((*HeadRef)->Entrpy <= Nu->Entrpy)
+ if ((*HeadRef)->MltEnpy <= Nu->MltEnpy)
{
/* Existing entry has lower entropy - keep it, discard new entry */
FreeFn(Nu);
@@ -183,6 +215,34 @@ static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu)
}
}
+/**********************************************************************************
+ * See if the match is repeated. If it is then add a new repeated match to the results.
+ */
+static void AddMatchRepeats(ZxcMatch_t **Result, ZxcMatch_t *Match, const uint8_t *Passwd, int MaxLen)
+{
+ int Len = Match->Length;
+ const uint8_t *Rpt = Passwd + Len;
+ int RepeatCount = 2;
+
+ while(MaxLen >= (Len * RepeatCount))
+ {
+ if (strncmp((const char *)Passwd, (const char *)Rpt, Len) == 0)
+ {
+ /* Found a repeat */
+ ZxcMatch_t *p = AllocMatch();
+ p->Entrpy = Match->Entrpy + log(RepeatCount);
+ p->Type = (ZxcTypeMatch_t)(Match->Type + MULTIPLE_MATCH);
+ p->Length = Len * RepeatCount;
+ p->Begin = Match->Begin;
+ AddResult(Result, p, MaxLen);
+ }
+ else
+ break;
+ ++RepeatCount;
+ Rpt += Len;
+ }
+}
+
/*################################################################################*
*################################################################################*
* Begin dictionary matching code
@@ -239,16 +299,17 @@ static const uint64_t CrcTable[16] =
static const unsigned int MAGIC = 'z' + ('x'<< 8) + ('c' << 16) + ('v' << 24);
-static unsigned int NumNodes, NumChildLocs, NumRanks, NumChildMaps;
+static unsigned int NumNodes, NumChildLocs, NumRanks, NumWordEnd, NumChildMaps;
static unsigned int SizeChildMapEntry, NumLargeCounts, NumSmallCounts, SizeCharSet;
static unsigned int *DictNodes;
-static unsigned short *ChildLocs;
+static uint8_t *WordEndBits;
+static unsigned int *ChildLocs;
static unsigned short *Ranks;
static uint8_t *ChildMap;
static uint8_t *EndCountLge;
static uint8_t *EndCountSml;
-static uint8_t *CharSet;
+static char *CharSet;
/**********************************************************************************
* Calculate the CRC-64 of passed data.
@@ -298,6 +359,8 @@ int ZxcvbnInit(const char *Filename)
i = 0;
if (!MyReadFile(f, &NumRanks, sizeof NumRanks))
i = 0;
+ if (!MyReadFile(f, &NumWordEnd, sizeof NumWordEnd))
+ i = 0;
if (!MyReadFile(f, &NumChildMaps, sizeof NumChildMaps))
i = 0;
if (!MyReadFile(f, &SizeChildMapEntry, sizeof SizeChildMapEntry))
@@ -310,15 +373,15 @@ int ZxcvbnInit(const char *Filename)
i = 0;
/* Validate the header data */
- if (NumNodes >= (1<<16))
+ if (NumNodes >= (1<<17))
i = 1;
- if (NumChildLocs >= (1<<17))
+ if (NumChildLocs >= (1<<BITS_CHILD_MAP_INDEX))
i = 2;
- if (NumChildMaps >= (1<<13))
+ if (NumChildMaps >= (1<<BITS_CHILD_PATT_INDEX))
i = 3;
if ((SizeChildMapEntry*8) < SizeCharSet)
i = 4;
- if (NumLargeCounts >= (1<<8))
+ if (NumLargeCounts >= (1<<9))
i = 5;
if (NumSmallCounts != NumNodes)
i = 6;
@@ -332,15 +395,15 @@ int ZxcvbnInit(const char *Filename)
Crc = CalcCrc64(Crc, &NumNodes, sizeof NumNodes);
Crc = CalcCrc64(Crc, &NumChildLocs, sizeof NumChildLocs);
Crc = CalcCrc64(Crc, &NumRanks, sizeof NumRanks);
+ Crc = CalcCrc64(Crc, &NumWordEnd, sizeof NumWordEnd);
Crc = CalcCrc64(Crc, &NumChildMaps, sizeof NumChildMaps);
Crc = CalcCrc64(Crc, &SizeChildMapEntry, sizeof SizeChildMapEntry);
Crc = CalcCrc64(Crc, &NumLargeCounts, sizeof NumLargeCounts);
Crc = CalcCrc64(Crc, &NumSmallCounts, sizeof NumSmallCounts);
Crc = CalcCrc64(Crc, &SizeCharSet, sizeof SizeCharSet);
- DictSize = NumNodes*sizeof(unsigned int) + NumChildLocs*sizeof(unsigned short) + NumRanks*sizeof(unsigned short) +
- NumChildMaps*SizeChildMapEntry + NumLargeCounts + NumSmallCounts + SizeCharSet;
-
+ DictSize = NumNodes*sizeof(*DictNodes) + NumChildLocs*sizeof(*ChildLocs) + NumRanks*sizeof(*Ranks) +
+ NumWordEnd + NumChildMaps*SizeChildMapEntry + NumLargeCounts + NumSmallCounts + SizeCharSet;
if (DictSize < MAX_DICT_FILE_SIZE)
{
DictNodes = MallocFn(unsigned int, DictSize / sizeof(unsigned int) + 1);
@@ -363,13 +426,15 @@ int ZxcvbnInit(const char *Filename)
DictNodes = 0;
return 0;
}
+ fflush(stdout);
/* Set pointers to the data */
- ChildLocs = (unsigned short *)(DictNodes + NumNodes);
- Ranks = ChildLocs + NumChildLocs;
- ChildMap = (unsigned char*)(Ranks + NumRanks);
+ ChildLocs = DictNodes + NumNodes;
+ Ranks = (unsigned short *)(ChildLocs + NumChildLocs);
+ WordEndBits = (unsigned char *)(Ranks + NumRanks);
+ ChildMap = (unsigned char*)(WordEndBits + NumWordEnd);
EndCountLge = ChildMap + NumChildMaps*SizeChildMapEntry;
EndCountSml = EndCountLge + NumLargeCounts;
- CharSet = EndCountSml + NumSmallCounts;
+ CharSet = (char *)EndCountSml + NumSmallCounts;
CharSet[SizeCharSet] = 0;
return 1;
}
@@ -411,13 +476,12 @@ typedef struct
int NumLeet; /* Total number of leeted characters */
uint8_t Leeted[sizeof L33TChr]; /* Number of leeted chars for each char found in L33TChr */
uint8_t UnLeet[sizeof L33TChr]; /* Number of normal chars for each char found in L33TChr */
-
} DictMatchInfo_t;
/* Struct holding working data for the word match */
typedef struct
{
- int StartLoc;
+ uint32_t StartLoc;
int Ordinal;
int PwdLength;
int Begin;
@@ -496,7 +560,7 @@ static void DictionaryEntropy(ZxcMatch_t *m, DictMatchInfo_t *Extra, const uint8
/* Add allowance for uppercase letters */
if (Extra->Caps)
{
- if (Extra->Caps == m->Length)
+ if (Extra->Caps == m->Length)
{
/* All uppercase, common case so only 1 bit */
e += log(2.0);
@@ -519,7 +583,6 @@ static void DictionaryEntropy(ZxcMatch_t *m, DictMatchInfo_t *Extra, const uint8
if (e > 0.0)
e = log(e);
}
-
}
/* Add allowance for using leet substitution */
if (Extra->NumLeet)
@@ -550,7 +613,6 @@ static void DictionaryEntropy(ZxcMatch_t *m, DictMatchInfo_t *Extra, const uint8
if (d < log(2.0))
d = log(2.0);
e += d;
- /*if(zz)printf(",%f ", d/log(2.0)); */
}
/* Add entropy due to word's rank */
e += log((double)Extra->Rank);
@@ -567,7 +629,7 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
int Ord = Wrk->Ordinal;
int Caps = Wrk->Caps;
int Lower = Wrk->Lower;
- int NodeLoc = Wrk->StartLoc;
+ unsigned int NodeLoc = Wrk->StartLoc;
uint8_t *PossChars = Wrk->PossChars;
int NumPossChrs = Wrk->NumPossChrs;
const uint8_t *Pwd = Passwd;
@@ -588,7 +650,7 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
/* Get char and set of possible chars at current point in word. */
const uint8_t *Bmap;
c = *Passwd;
- Bmap = ChildMap + (NodeData & ((1<<13)-1)) * SizeChildMapEntry;
+ Bmap = ChildMap + (NodeData & ((1<<BITS_CHILD_PATT_INDEX)-1)) * SizeChildMapEntry;
NumPossChrs = ListPossibleChars(PossChars, Bmap);
/* Make it lowercase and update lowercase, uppercase counts */
@@ -642,7 +704,7 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
}
return;
}
- }
+ }
q = CharBinSearch(c, PossChars, NumPossChrs, 1);
if (q)
{
@@ -660,30 +722,34 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
}
/* Add all the end counts of the child nodes before the one that matches */
x = (q - Wrk->PossChars);
- y = (NodeData >> 13) & ((1<<17)-1);
+ y = (NodeData >> BITS_CHILD_PATT_INDEX) & ((1 << BITS_CHILD_MAP_INDEX) - 1);
NodeLoc = ChildLocs[x+y];
for(w=0; w<x; ++w)
{
- int Cloc = ChildLocs[w+y];
+ unsigned int Cloc = ChildLocs[w+y];
z = EndCountSml[Cloc];
- if (DictNodes[Cloc] & (1<<31))
+ if (Cloc < NumLargeCounts)
z += EndCountLge[Cloc]*256;
Ord += z;
}
/* Move to next node */
NodeData = DictNodes[NodeLoc];
- if (NodeData & (1<<30))
+ if (WordEndBits[NodeLoc >> 3] & (1<<(NodeLoc & 7)))
{
/* Word matches, save result */
+ unsigned int v;
ZxcMatch_t *p;
+ v = Ranks[Ord];
+ if (v & (1<<15))
+ v = (v & ((1 << 15) - 1)) * 4 + (1 << 15);
Extra->Caps = Caps;
- Extra->Rank = Ranks[Ord];
+ Extra->Rank = v;
Extra->Lower = Lower;
for(x = 0, y = sizeof Extra->Leeted - 1; y >= 0; --y)
x += Wrk->Leeted[y];
Extra->NumLeet = x;
-
+
memcpy(Extra->UnLeet, Wrk->UnLeet, sizeof Extra->UnLeet);
memcpy(Extra->Leeted, Wrk->Leeted, sizeof Extra->Leeted);
@@ -695,8 +761,8 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
p->Length = Wrk->PwdLength + Len + 1;
p->Begin = Wrk->Begin;
DictionaryEntropy(p, Extra, Pwd);
- AddResult(Result, p);
-
+ AddMatchRepeats(Result, p, Pwd, MaxLen);
+ AddResult(Result, p, MaxLen);
++Ord;
}
}
@@ -745,8 +811,6 @@ static void UserMatch(ZxcMatch_t **Result, const char *Words[], const uint8_t *P
{
++Lowers;
}
-
-
/* See if current char is a leet and can be converted */
q = CharBinSearch(c, L33TCnv, sizeof L33TCnv / LEET_NORM_MAP_SIZE, LEET_NORM_MAP_SIZE);
if (q)
@@ -819,8 +883,8 @@ static void UserMatch(ZxcMatch_t **Result, const char *Words[], const uint8_t *P
Extra.NumLeet = Leets;
Extra.Rank = Rank+1;
DictionaryEntropy(p, &Extra, Passwd);
- AddResult(Result, p);
-
+ AddMatchRepeats(Result, p, Passwd, MaxLen);
+ AddResult(Result, p, MaxLen);
}
}
}
@@ -853,8 +917,6 @@ static void DictionaryMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Star
*################################################################################*
*################################################################################*/
-#define MIN_SPATIAL_LEN 3
-
/* Struct to hold information on a keyboard layout */
typedef struct Keyboard
{
@@ -1129,7 +1191,7 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
/* Math is similar to extra entropy from uppercase letters in dictionary matches. */
int Shift = Extra.Shifts;
int Unshift = Len - Shift;
-
+
Degree = 0.0;
j = Shift;
if (j > Unshift)
@@ -1146,7 +1208,8 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
p->Begin = Start;
p->Entrpy = Entropy;
p->Length = Len;
- AddResult(Result, p);
+ AddMatchRepeats(Result, p, Passwd, MaxLen);
+ AddResult(Result, p, MaxLen);
break;
}
}
@@ -1160,9 +1223,6 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
*################################################################################*
*################################################################################*/
-#define MIN_YEAR 1901
-#define MAX_YEAR 2019
-
/* The possible date formats ordered by length (d for day, m for month, */
/* y for year, ? for separator) */
static const char *Formats[] =
@@ -1290,7 +1350,8 @@ static void DateMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int
p->Type = DATE_MATCH;
p->Length = Len;
p->Begin = Start;
- AddResult(Result, p);
+ AddMatchRepeats(Result, p, Passwd, MaxLen);
+ AddResult(Result, p, MaxLen);
PrevLen = Len;
}
}
@@ -1303,8 +1364,6 @@ static void DateMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int
*################################################################################*
*################################################################################*/
-#define MIN_REPEAT_LEN 3
-
/**********************************************************************************
* Try to match password part as a set of repeated characters.
* Parameters:
@@ -1333,11 +1392,35 @@ static void RepeatMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, i
p->Begin = Start;
p->Length = i;
p->Entrpy = log(Card * i);
- AddResult(Result, p);
+ AddResult(Result, p, MaxLen);
}
}
-}
+ /* Try to match a repeated sequence e.g. qxno6qxno6 */
+ for(Len = MaxLen/2; Len >= MIN_REPEAT_LEN; --Len)
+ {
+ const uint8_t *Rpt = Passwd + Len;
+ int RepeatCount = 2;
+ while(MaxLen >= (Len * RepeatCount))
+ {
+ if (strncmp((const char *)Passwd, (const char *)Rpt, Len) == 0)
+ {
+ /* Found a repeat */
+ int c = Cardinality(Passwd, Len);
+ ZxcMatch_t *p = AllocMatch();
+ p->Entrpy = log((double)c) * Len + log(RepeatCount);
+ p->Type = (ZxcTypeMatch_t)(BRUTE_MATCH + MULTIPLE_MATCH);
+ p->Length = Len * RepeatCount;
+ p->Begin = Start;
+ AddResult(Result, p, MaxLen);
+ }
+ else
+ break;
+ ++RepeatCount;
+ Rpt += Len;
+ }
+ }
+}
/**********************************************************************************
**********************************************************************************
@@ -1345,8 +1428,7 @@ static void RepeatMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, i
**********************************************************************************
*********************************************************************************/
-#define MIN_SEQUENCE_LEN 3
-
+#define MAX_SEQUENCE_STEP 5
/**********************************************************************************
* Try to match password part as a set of incrementing or decrementing characters.
* Parameters:
@@ -1359,12 +1441,14 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
{
int Len=0;
int SetLow, SetHigh, Dir;
- uint8_t First, Next;
-
+ uint8_t First, Next, IsDigits;
+ const uint8_t *Pwd;
Passwd += Start;
+ Pwd = Passwd;
First = Passwd[0];
Dir = Passwd[1] - First;
Len = 0;
+ IsDigits = 0;
/* Decide on min and max character code for sequence */
if (islower(*Passwd))
{
@@ -1380,30 +1464,36 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
{
SetLow = '0';
SetHigh = '9';
- if ((First == '0') && (Dir == 9))
+ if ((First == '0') && isdigit(Passwd[1]) && (Dir > MAX_SEQUENCE_STEP))
{
- /* Special case for decrementing sequence of digits, allow starting with 098 */
- Dir = -1;
- ++Len;
- ++Passwd;
+ /* Special case for decrementing sequence of digits, treat '0 as a 'ten' character */
+ Dir = Passwd[1] - ('9' + 1);
}
+ IsDigits = 1;
}
else
return;
- if ((Dir == 1) || (Dir == -1))
+ /* Only consider it a sequence if the character increment is not too large */
+ if (Dir && (Dir <= MAX_SEQUENCE_STEP) && (Dir >= -MAX_SEQUENCE_STEP))
{
++Len;
while(1)
{
- if ((Passwd[0] == '9') && (Passwd[1] == '0') && (Dir > 0))
+ Next = Passwd[0] + Dir;
+ if (IsDigits && (Dir > 0) && (Next == ('9' + 1)) && (Passwd[1] == '0'))
{
+ /* Incrementing digits, consider '0' to be same as a 'ten' character */
++Len;
++Passwd;
break;
}
- Next = Passwd[0] + Dir;
- if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next))
+ if (IsDigits && (Dir < 0) && (Passwd[0] == '0') && (Passwd[1] == ('9'+1 + Dir)))
+ {
+ ++Len;
+ ++Passwd;
+ }
+ else if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next))
break;
++Len;
++Passwd;
@@ -1416,9 +1506,10 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
/* Enough repeated char, so create results from number found down to min acceptable length */
int i;
double e;
- if ((First == 'a') || (First == '1'))
+ if ((First == 'a') || (First == 'A') || (First == 'z') || (First == 'Z') ||
+ (First == '0') || (First == '1') || (First == '9'))
e = log(2.0);
- else if (isdigit(First))
+ else if (IsDigits)
e = log(10.0);
else if (isupper(First))
e = log(26*2.0);
@@ -1435,19 +1526,18 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
p->Begin = Start;
p->Length = i;
p->Entrpy = e + log((double)i);
- AddResult(Result, p);
+ AddMatchRepeats(Result, p, Pwd, MaxLen);
+ AddResult(Result, p, MaxLen);
}
}
}
-
/**********************************************************************************
**********************************************************************************
* Begin top level zxcvbn code
**********************************************************************************
*********************************************************************************/
-
/**********************************************************************************
* Matching a password is treated as a problem of finding the minimum distance
* between two vertexes in a graph. This is solved using Dijkstra's algorithm.
@@ -1481,12 +1571,13 @@ typedef struct
*/
double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
{
- int i;
+ int i, j;
ZxcMatch_t *Zp;
Node_t *Np;
double e;
int Len = strlen(Pwd);
const uint8_t *Passwd = (const uint8_t *)Pwd;
+ uint8_t *RevPwd;
/* Create the paths */
Node_t *Nodes = MallocFn(Node_t, Len+1);
memset(Nodes, 0, (Len+1) * sizeof *Nodes);
@@ -1505,22 +1596,74 @@ double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
SequenceMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
RepeatMatch(&(Nodes[i].Paths), Passwd, i, MaxLen);
- /* Add a default one character bruteforce path */
- Zp = AllocMatch();
- Zp->Type = BRUTE_MATCH;
- Zp->Begin = i;
- Zp->Length = 1;
- Zp->Entrpy = e;
- AddResult(&(Nodes[i].Paths), Zp);
-
/* Initially set distance to nearly infinite */
Nodes[i].Dist = DBL_MAX;
+ }
+
+ /* Reverse dictionary words check */
+ RevPwd = MallocFn(uint8_t, Len+1);
+ for(i = Len-1, j = 0; i >= 0; --i, ++j)
+ RevPwd[j] = Pwd[i];
+ RevPwd[j] = 0;
+ for(i = 0; i < Len; ++i)
+ {
+ ZxcMatch_t *Path = 0;
+ int MaxLen = Len - i;
+ DictionaryMatch(&Path, RevPwd, i, MaxLen);
+ UserMatch(&Path, UserDict, RevPwd, i, MaxLen);
+
+ /* Now transfer any reverse matches to the normal results */
+ while(Path)
+ {
+ ZxcMatch_t *Nxt = Path->Next;
+ Path->Next = 0;
+ Path->Begin = Len - (Path->Begin + Path->Length);
+ AddResult(&(Nodes[Path->Begin].Paths), Path, MaxLen);
+ Path = Nxt;
+ }
+ }
+
+ /* Add a set of brute force matches. Start by getting all the start points and all */
+ /* points at character position after end of the matches. */
+ memset(RevPwd, 0, Len+1);
+ for(i = 0; i < Len; ++i)
+ {
+ ZxcMatch_t *Path = Nodes[i].Paths;
+ while(Path)
+ {
+ RevPwd[Path->Begin] |= 1;
+ RevPwd[Path->Begin + Path->Length] |= 2;
+ Path = Path->Next;
+ }
+ }
+ RevPwd[0] = 1;
+ RevPwd[Len] = 2;
+ /* Add the brute force matches */
+ for(i = 0; i < Len; ++i)
+ {
+ int MaxLen = Len - i;
+ int j;
+ if (!RevPwd[i])
+ continue;
+ for(j = i+1; j <= Len; ++j)
+ {
+ if (RevPwd[j])
+ {
+ Zp = AllocMatch();
+ Zp->Type = BRUTE_MATCH;
+ Zp->Begin = i;
+ Zp->Length = j - i;
+ Zp->Entrpy = e * (j - i);
+ AddResult(&(Nodes[i].Paths), Zp, MaxLen);
+ }
+ }
}
+ FreeFn(RevPwd);
/* End node has infinite distance/entropy, start node has 0 distance */
Nodes[i].Dist = DBL_MAX;
Nodes[0].Dist = 0.0;
-
+
/* Reduce the paths using Dijkstra's algorithm */
for(i = 0; i < Len; ++i)
{
@@ -1547,7 +1690,7 @@ double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
for(Zp = Np->Paths; Zp; Zp = Zp->Next)
{
Node_t *Ep = Np + Zp->Length;
- double d = e + Zp->Entrpy;
+ double d = e + Zp->MltEnpy;
if (!Ep->Visit && (d < Ep->Dist))
{
/* Update as lower dist, also remember the 'from' node */
@@ -1570,7 +1713,7 @@ double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
{
ZxcMatch_t *Xp;
i = Zp->Begin;
-
+
/* Remove all but required path */
Xp = Nodes[i].Paths;
Nodes[i].Paths = 0;
@@ -1581,20 +1724,11 @@ double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
{
/* Adjust the entropy to log to base 2 */
Xp->Entrpy /= log(2.0);
- if ((*Info) && (Xp->Type == BRUTE_MATCH) && ((*Info)->Type == BRUTE_MATCH))
- {
- /* Previous part and current are bruteforce, merge then into single entry */
- (*Info)->Begin = Xp->Begin;
- (*Info)->Length += Xp->Length;
- (*Info)->Entrpy += Xp->Entrpy;
- FreeFn(Xp);
- }
- else
- {
- /* Put previous part at head of info list */
- Xp->Next = *Info;
- *Info = Xp;
- }
+ Xp->MltEnpy /= log(2.0);
+
+ /* Put previous part at head of info list */
+ Xp->Next = *Info;
+ *Info = Xp;
}
else
{
@@ -1618,7 +1752,6 @@ double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
}
}
FreeFn(Nodes);
-
return e;
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 06:23:57 +0000