Add extra entropy if a password is made from multiple matches, also move some controlling #defines to beginning of zxcvbn.c

3 files changed, 117 insertions, 46 deletions

diff --git a/test.c b/test.c
index 6d763a5..b15cbe3 100644
--- a/test.c
+++ b/test.c
@@ -33,6 +33,7 @@
 #include <stdio.h>
 #include <string.h>
 #include <stdlib.h>
+#include <math.h>
 #include <sys/time.h>
 #include <zxcvbn.h>
 
@@ -56,13 +57,17 @@ static void CalcPass(const char *Pwd, int Quiet)
         int Len, ChkLen;
         struct timeval t1, t2;
         ZxcMatch_t *Info, *p;
+        double m = 0.0;
 
         gettimeofday(&t1, 0);
         e = ZxcvbnMatch(Pwd, UsrDict, &Info);
         gettimeofday(&t2, 0);
+        for(p = Info; p; p = p->Next)
+            m += p->Entrpy;
 
         Len = strlen(Pwd);
-        printf("Pass %s \tLength %d\tEntropy bits=%.3f  log10=%.3f\n", Pwd, Len, e, e * 0.301029996);
+        m = e - m;
+        printf("Pass %s \tLength %d\tEntropy bits=%.3f log10=%.3f\tMulti-word extra bits=%.1f factor=%.1f\n", Pwd, Len, e, e * 0.301029996, m, pow(2.0,m));
         p = Info;
         ChkLen = 0;
         while(p)
diff --git a/zxcvbn.c b/zxcvbn.c
index f77e88d..71334a4 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
@@ -152,8 +171,21 @@ static ZxcMatch_t *AllocMatch()
  * Add new match struct to linked list of matches. List ordered with shortest at
  * 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);
@@ -202,7 +234,7 @@ static void AddMatchRepeats(ZxcMatch_t **Result, ZxcMatch_t *Match, const uint8_
             p->Type = (ZxcTypeMatch_t)(Match->Type + MULTIPLE_MATCH);
             p->Length = Len * RepeatCount;
             p->Begin = Match->Begin;
-            AddResult(Result, p);
+            AddResult(Result, p, MaxLen);
         }
         else
             break;
@@ -444,7 +476,6 @@ 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 */
@@ -582,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);
@@ -732,7 +762,7 @@ static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t
             p->Begin = Wrk->Begin;
             DictionaryEntropy(p, Extra, Pwd);
             AddMatchRepeats(Result, p, Pwd, MaxLen);
-            AddResult(Result, p);
+            AddResult(Result, p, MaxLen);
             ++Ord;
         }
     }
@@ -854,7 +884,7 @@ static void UserMatch(ZxcMatch_t **Result, const char *Words[], const uint8_t *P
             Extra.Rank = Rank+1;
             DictionaryEntropy(p, &Extra, Passwd);
             AddMatchRepeats(Result, p, Passwd, MaxLen);
-            AddResult(Result, p);
+            AddResult(Result, p, MaxLen);
         }
     }
 }
@@ -887,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
 {
@@ -1181,7 +1209,7 @@ static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
                 p->Entrpy = Entropy;
                 p->Length = Len;
                 AddMatchRepeats(Result, p, Passwd, MaxLen);
-                AddResult(Result, p);
+                AddResult(Result, p, MaxLen);
                 break;
             }
         }
@@ -1195,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[] =
@@ -1326,7 +1351,7 @@ static void DateMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int
             p->Length = Len;
             p->Begin = Start;
             AddMatchRepeats(Result, p, Passwd, MaxLen);
-            AddResult(Result, p);
+            AddResult(Result, p, MaxLen);
             PrevLen = Len;
         }
     }
@@ -1339,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:
@@ -1369,7 +1392,7 @@ 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);
         }
     }
 
@@ -1389,7 +1412,7 @@ static void RepeatMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, i
                 p->Type = (ZxcTypeMatch_t)(BRUTE_MATCH + MULTIPLE_MATCH);
                 p->Length = Len * RepeatCount;
                 p->Begin = Start;
-                AddResult(Result, p);
+                AddResult(Result, p, MaxLen);
             }
             else
                 break;
@@ -1405,7 +1428,6 @@ 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.
@@ -1505,7 +1527,7 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start,
             p->Length = i;
             p->Entrpy = e + log((double)i);
             AddMatchRepeats(Result, p, Pwd, MaxLen);
-            AddResult(Result, p);
+            AddResult(Result, p, MaxLen);
         }
     }
 }
@@ -1549,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);
@@ -1573,17 +1596,68 @@ 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);
+            }
+        }
     }
     /* End node has infinite distance/entropy, start node has 0 distance */
     Nodes[i].Dist = DBL_MAX;
@@ -1615,7 +1689,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 */
@@ -1649,20 +1723,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
                 {
diff --git a/zxcvbn.h b/zxcvbn.h
index db08556..796d6b4 100644
--- a/zxcvbn.h
+++ b/zxcvbn.h
@@ -79,6 +79,7 @@ struct ZxcMatch
     int             Begin;   /* Char position of begining of match */
     int             Length;  /* Number of chars in the match */
     double          Entrpy;  /* The entropy of the match */
+    double          MltEnpy; /* Entropy with additional allowance for multipart password */
     ZxcTypeMatch_t  Type;    /* Type of match (Spatial/Dictionary/Order/Repeat) */
     struct ZxcMatch *Next;
 };