src/zxcvbn.c

   1 /**********************************************************************************
   2  * C implementation of the zxcvbn password strength estimation method.
   3  * Copyright (c) 2015, Tony Evans
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without modification, are
   7  * permitted provided that the following conditions are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright notice, this list
  10  *    of conditions and the following disclaimer.
  11  *
  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.
  15  *
  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.
  19  *
  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
  29  * DAMAGE.
  30  *
  31  **********************************************************************************/
  32
  33 #include "zxcvbn.h"
  34 #include <ctype.h>
  35 #include <string.h>
  36 #include <stdint.h>
  37 #include <math.h>
  38 #include <float.h>
  39
  40 #ifdef USE_DICT_FILE
  41 #if defined(USE_FILE_IO) || !defined(__cplusplus)
  42 #include <stdio.h>
  43 #else
  44 #include <fstream>
  45 #endif
  46 #endif
  47
  48 /* For pre-compiled headers under windows */
  49 #ifdef _WIN32
  50 #include "stdafx.h"
  51 #endif
  52
  53 /*################################################################################*
  54  *################################################################################*
  55  * Begin utility function code
  56  *################################################################################*
  57  *################################################################################*/
  58
  59
  60 /**********************************************************************************
  61  * Binomial coefficient function. Uses method described at
  62  *      http://blog.plover.com/math/choose.html
  63  */
  64 static double nCk(int n, int k)
  65 {
  66     int d;
  67     double r;
  68     if (k > n)
  69         return 0.0;
  70     if (!k)
  71         return 1.0;
  72     r = 1.0;
  73     for(d = 1; d <= k; ++d)
  74     {
  75         r *= n--;
  76         r /= d;
  77     }
  78     return r;
  79 }
  80
  81 /**********************************************************************************
  82  * Binary search function to find a character in a string.
  83  * Parameters:
  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.
  89  */
  90 static const uint8_t *CharBinSearch(uint8_t Ch, const uint8_t *Ents, unsigned int NumEnts, unsigned int SizeEnt)
  91 {
  92     while(NumEnts > 0)
  93     {
  94         const uint8_t *Mid = Ents + (NumEnts >> 1) * SizeEnt;
  95         int Dif = Ch - *Mid;
  96         if (!Dif)
  97         {
  98             return Mid;
  99         }
 100         if (Dif > 0)
 101         {
 102             Ents = Mid + SizeEnt;
 103             --NumEnts;
 104         }
 105         NumEnts /= 2;
 106     }
 107     return 0;
 108 }
 109
 110 /**********************************************************************************
 111  * Calculate potential number of different characters in the passed string.
 112  * Parameters:
 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.
 116  */
 117 static int Cardinality(const uint8_t *Str, int Len)
 118 {
 119     int Card=0, Types=0;
 120     int c;
 121     while(Len > 0)
 122     {
 123         c = *Str++ & 0xFF;
 124         if (!c)
 125             break;
 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?) */
 131         --Len;
 132     }
 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;
 138     return Card;
 139 }
 140
 141 /**********************************************************************************
 142  * Allocate a ZxcMatch_t struct, clear it to zero
 143  */
 144 static ZxcMatch_t *AllocMatch()
 145 {
 146     ZxcMatch_t *p = MallocFn(ZxcMatch_t, 1);
 147     memset(p, 0, sizeof *p);
 148     return p;
 149 }
 150
 151 /**********************************************************************************
 152  * Add new match struct to linked list of matches. List ordered with shortest at
 153  * head of list.
 154  */
 155 static void AddResult(ZxcMatch_t **HeadRef, ZxcMatch_t *Nu)
 156 {
 157     /* Find the correct insert point */
 158     while(*HeadRef && ((*HeadRef)->Length < Nu->Length))
 159         HeadRef = &((*HeadRef)->Next);
 160
 161     /* Add new entry or replace existing */
 162     if (*HeadRef && ((*HeadRef)->Length == Nu->Length))
 163     {
 164         /* New entry has same length as existing, so one of them needs discarding */
 165         if ((*HeadRef)->Entrpy <= Nu->Entrpy)
 166         {
 167             /* Existing entry has lower entropy - keep it, discard new entry */
 168             FreeFn(Nu);
 169         }
 170         else
 171         {
 172             /* New entry has lower entropy - replace existing entry */
 173             Nu->Next = (*HeadRef)->Next;
 174             FreeFn(*HeadRef);
 175             *HeadRef = Nu;
 176         }
 177     }
 178     else
 179     {
 180         /* New entry has different length, so add it */
 181         Nu->Next = *HeadRef;
 182         *HeadRef = Nu;
 183     }
 184 }
 185
 186 /*################################################################################*
 187  *################################################################################*
 188  * Begin dictionary matching code
 189  *################################################################################*
 190  *################################################################################*/
 191
 192 #ifdef USE_DICT_FILE
 193 /* Use dictionary data from file */
 194
 195 #if defined(USE_FILE_IO) || !defined(__cplusplus)
 196 /* Use the FILE streams from stdio.h */
 197
 198 typedef FILE *FileHandle;
 199
 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)
 203
 204 #else
 205
 206 /* Use the C++ iostreams */
 207 typedef std::ifstream FileHandle;
 208
 209 static inline void MyOpenFile(FileHandle & f, const char *Name)
 210 {
 211     f.open(Name, std::ifstream::in | std::ifstream::binary);
 212 }
 213 static inline bool MyReadFile(FileHandle & f, void *Buf, unsigned int Num)
 214 {
 215     return f.read((char *)Buf, Num);
 216 }
 217 static inline void MyCloseFile(FileHandle & f)
 218 {
 219     f.close();
 220 }
 221
 222 #endif
 223
 224 /* Include file contains the CRC of the dictionary data file. Used to detect corruption */
 225 /* of the file. */
 226 #include "dict-crc.h"
 227
 228 #define MAX_DICT_FILE_SIZE  (100+WORD_FILE_SIZE)
 229 #define CHK_INIT 0xffffffffffffffffULL
 230
 231 /* Static table used for the crc implementation. */
 232 static const uint64_t CrcTable[16] =
 233 {
 234     0x0000000000000000ULL, 0x7d08ff3b88be6f81ULL, 0xfa11fe77117cdf02ULL, 0x8719014c99c2b083ULL,
 235     0xdf7adabd7a6e2d6fULL, 0xa2722586f2d042eeULL, 0x256b24ca6b12f26dULL, 0x5863dbf1e3ac9decULL,
 236     0x95ac9329ac4bc9b5ULL, 0xe8a46c1224f5a634ULL, 0x6fbd6d5ebd3716b7ULL, 0x12b5926535897936ULL,
 237     0x4ad64994d625e4daULL, 0x37deb6af5e9b8b5bULL, 0xb0c7b7e3c7593bd8ULL, 0xcdcf48d84fe75459ULL
 238 };
 239
 240 static const unsigned int MAGIC = 'z' + ('x'<< 8) + ('c' << 16) + ('v' << 24);
 241
 242 static unsigned int NumNodes, NumChildLocs, NumRanks, NumChildMaps;
 243 static unsigned int SizeChildMapEntry, NumLargeCounts, NumSmallCounts, SizeCharSet;
 244
 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;
 252
 253 /**********************************************************************************
 254  * Calculate the CRC-64 of passed data.
 255  * Parameters:
 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.
 260  */
 261 static uint64_t CalcCrc64(uint64_t Crc, const void *v, unsigned int Len)
 262 {
 263     const uint8_t *Data = (const unsigned char *)v;
 264     while(Len--)
 265     {
 266         Crc = CrcTable[(Crc ^ (*Data >> 0)) & 0x0f] ^ (Crc >> 4);
 267         Crc = CrcTable[(Crc ^ (*Data >> 4)) & 0x0f] ^ (Crc >> 4);
 268         ++Data;
 269     }
 270     return Crc;
 271 }
 272
 273 /**********************************************************************************
 274  * Read the dictionary data from file.
 275  * Parameters:
 276  *  Filename    Name of the file to read.
 277  * Returns 1 on success, 0 on error
 278  */
 279 int ZxcvbnInit(const char *Filename)
 280 {
 281     FileHandle f;
 282     uint64_t Crc = CHK_INIT;
 283     if (DictNodes)
 284         return 1;
 285     MyOpenFile(f, Filename);
 286     if (f)
 287     {
 288         unsigned int i, DictSize;
 289
 290         /* Get magic number */
 291         if (!MyReadFile(f, &i, sizeof i))
 292             i = 0;
 293
 294         /* Get header data */
 295         if (!MyReadFile(f, &NumNodes, sizeof NumNodes))
 296             i = 0;
 297         if (!MyReadFile(f, &NumChildLocs, sizeof NumChildLocs))
 298             i = 0;
 299         if (!MyReadFile(f, &NumRanks, sizeof NumRanks))
 300             i = 0;
 301         if (!MyReadFile(f, &NumChildMaps, sizeof NumChildMaps))
 302             i = 0;
 303         if (!MyReadFile(f, &SizeChildMapEntry, sizeof SizeChildMapEntry))
 304             i = 0;
 305         if (!MyReadFile(f, &NumLargeCounts, sizeof NumLargeCounts))
 306             i = 0;
 307         if (!MyReadFile(f, &NumSmallCounts, sizeof NumSmallCounts))
 308             i = 0;
 309         if (!MyReadFile(f, &SizeCharSet, sizeof SizeCharSet))
 310             i = 0;
 311
 312         /* Validate the header data */
 313         if (NumNodes >= (1<<16))
 314             i = 1;
 315         if (NumChildLocs >= (1<<17))
 316             i = 2;
 317         if (NumChildMaps >= (1<<13))
 318             i = 3;
 319         if ((SizeChildMapEntry*8) < SizeCharSet)
 320             i = 4;
 321         if (NumLargeCounts >= (1<<8))
 322             i = 5;
 323         if (NumSmallCounts != NumNodes)
 324             i = 6;
 325
 326         if (i != MAGIC)
 327         {
 328             MyCloseFile(f);
 329             return 0;
 330         }
 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);
 340
 341         DictSize = NumNodes*sizeof(unsigned int) + NumChildLocs*sizeof(unsigned short) + NumRanks*sizeof(unsigned short) +
 342                         NumChildMaps*SizeChildMapEntry + NumLargeCounts + NumSmallCounts + SizeCharSet;
 343
 344         if (DictSize < MAX_DICT_FILE_SIZE)
 345         {
 346             DictNodes = MallocFn(unsigned int, DictSize / sizeof(unsigned int) + 1);
 347             if (!MyReadFile(f, DictNodes, DictSize))
 348             {
 349                 FreeFn(DictNodes);
 350                 DictNodes = 0;
 351             }
 352         }
 353         MyCloseFile(f);
 354
 355         if (!DictNodes)
 356             return 0;
 357         /* Check crc */
 358         Crc = CalcCrc64(Crc, DictNodes, DictSize);
 359         if (memcmp(&Crc, WordCheck, sizeof Crc))
 360         {
 361             /* File corrupted */
 362             FreeFn(DictNodes);
 363             DictNodes = 0;
 364             return 0;
 365         }
 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;
 374         return 1;
 375     }
 376     return 0;
 377 }
 378 /**********************************************************************************
 379  * Free the data allocated by ZxcvbnInit().
 380  */
 381 void ZxcvbnUnInit()
 382 {
 383     if (DictNodes)
 384         FreeFn(DictNodes);
 385     DictNodes = 0;
 386 }
 387
 388 #else
 389
 390 /* Include the source file containing the dictionary data */
 391 #include "dict-src.h"
 392
 393 #endif
 394
 395 /**********************************************************************************
 396  * Leet conversion strings
 397  */
 398 /* String of normal chars that could be given as leet chars in the password */
 399 static const uint8_t L33TChr[] = "abcegilostxz";
 400
 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
 404
 405 /* Struct holding additional data on the word match */
 406 typedef struct
 407 {
 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 */
 414
 415 } DictMatchInfo_t;
 416
 417 /* Struct holding working data for the word match */
 418 typedef struct
 419 {
 420     int     StartLoc;
 421     int     Ordinal;
 422     int     PwdLength;
 423     int     Begin;
 424     int     Caps;
 425     int     Lower;
 426     int     NumPossChrs;
 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]; */
 431     uint8_t First;
 432     uint8_t PossChars[48];
 433 } DictWork_t;
 434
 435 /**********************************************************************************
 436  * Given a map entry create a string of all possible characters for following to
 437  * a child node
 438  */
 439 static int ListPossibleChars(uint8_t *List, const uint8_t *Map)
 440 {
 441     unsigned int i, j, k;
 442     int Len = 0;
 443     for(k = i = 0; i < SizeChildMapEntry; ++i, ++Map)
 444     {
 445         if (!*Map)
 446         {
 447             k += 8;
 448             continue;
 449         }
 450         for(j = 0; j < 8; ++j)
 451         {
 452             if (*Map & (1<<j))
 453             {
 454                 *List++ = CharSet[k];
 455                 ++Len;
 456             }
 457             ++k;
 458         }
 459     }
 460     *List=0;
 461     return Len;
 462 }
 463
 464 /**********************************************************************************
 465  * Increment count of each char that could be leeted.
 466  */
 467 static void AddLeetChr(uint8_t c, int IsLeet, uint8_t *Leeted, uint8_t *UnLeet)
 468 {
 469     const uint8_t *p = CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1);
 470     if (p)
 471     {
 472         int i = p - L33TChr;
 473         if (IsLeet > 0)
 474         {
 475             Leeted[i] += 1;
 476         }
 477         else if (IsLeet < 0)
 478         {
 479             Leeted[i] += 1;
 480             UnLeet[i] -= 1;
 481         }
 482         else
 483         {
 484             UnLeet[i] += 1;
 485         }
 486     }
 487 }
 488
 489 /**********************************************************************************
 490  * Given details of a word match, update it with the entropy (as natural log of
 491  * number of possiblities)
 492  */
 493 static void DictionaryEntropy(ZxcMatch_t *m, DictMatchInfo_t *Extra, const uint8_t *Pwd)
 494 {
 495     double e = 0.0;
 496     /* Add allowance for uppercase letters */
 497     if (Extra->Caps)
 498     {
 499        if (Extra->Caps == m->Length)
 500         {
 501             /* All uppercase, common case so only 1 bit */
 502             e += log(2.0);
 503         }
 504         else if ((Extra->Caps == 1) && (isupper(*Pwd) || isupper(Pwd[m->Length - 1])))
 505         {
 506             /* Only first or last uppercase, also common so only 1 bit */
 507             e += log(2.0);
 508         }
 509         else
 510         {
 511             /* Get number of combinations of lowercase, uppercase letters */
 512             int Up = Extra->Caps;
 513             int Lo = Extra->Lower;
 514             int i = Up;
 515             if (i > Lo)
 516                 i = Lo;
 517             for(Lo += Up; i >= 0; --i)
 518                 e += nCk(Lo, i);
 519             if (e > 0.0)
 520                 e = log(e);
 521         }
 522
 523     }
 524     /* Add allowance for using leet substitution */
 525     if (Extra->NumLeet)
 526     {
 527         int i;
 528         double d = 0.0;
 529         for(i = sizeof Extra->Leeted - 1; i >= 0; --i)
 530         {
 531             int Sb = Extra->Leeted[i];
 532             if (Sb)
 533             {
 534                 int Un = Extra->UnLeet[i];
 535                 int j = m->Length - Extra->NumLeet;
 536                 if ((j >= 0) && (Un > j))
 537                     Un = j;
 538                 j = Sb;
 539                 if (j > Un)
 540                     j = Un;
 541                 for(Un += Sb; j >= 0; --j)
 542                 {
 543                     double z = nCk(Un, j);
 544                     d += z;
 545                 }
 546             }
 547         }
 548         if (d > 0.0)
 549             d = log(d);
 550         if (d < log(2.0))
 551             d = log(2.0);
 552         e += d;
 553         /*if(zz)printf(",%f ", d/log(2.0)); */
 554     }
 555     /* Add entropy due to word's rank */
 556     e += log((double)Extra->Rank);
 557     m->Entrpy = e;
 558 }
 559
 560 /**********************************************************************************
 561  * Function that does the word matching
 562  */
 563 static void DoDictMatch(const uint8_t *Passwd, int Start, int MaxLen, DictWork_t *Wrk, ZxcMatch_t **Result, DictMatchInfo_t *Extra, int Lev)
 564 {
 565     int Len;
 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];
 575     Passwd += Start;
 576     for(Len = 0; *Passwd && (Len < MaxLen); ++Len, ++Passwd)
 577     {
 578         uint8_t c;
 579         int w, x, y, z;
 580         const uint8_t *q;
 581         z = 0;
 582         if (!Len && Wrk->First)
 583         {
 584             c = Wrk->First;
 585         }
 586         else
 587         {
 588             /* Get char and set of possible chars at current point in word. */
 589             const uint8_t *Bmap;
 590             c = *Passwd;
 591             Bmap = ChildMap + (NodeData & ((1<<13)-1)) * SizeChildMapEntry;
 592             NumPossChrs = ListPossibleChars(PossChars, Bmap);
 593
 594             /* Make it lowercase and update lowercase, uppercase counts */
 595             if (isupper(c))
 596             {
 597                 c = tolower(c);
 598                 ++Caps;
 599             }
 600             else if (islower(c))
 601             {
 602                 ++Lower;
 603             }
 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);
 606             if (q)
 607             {
 608                 /* Found, see if used before */
 609                 unsigned int j;
 610                 unsigned int i = (q - L33TCnv ) / LEET_NORM_MAP_SIZE;
 611                 if (Wrk->LeetCnv[i])
 612                 {
 613                     /* Used before, so limit characters to try */
 614                     TempLeet[0] = c;
 615                     TempLeet[1] = Wrk->LeetCnv[i];
 616                     TempLeet[2] = 0;
 617                     q = TempLeet;
 618                 }
 619                 for(j = 0; (*q > ' ') && (j < LEET_NORM_MAP_SIZE); ++j, ++q)
 620                 {
 621                     const uint8_t *r = CharBinSearch(*q, PossChars, NumPossChrs, 1);
 622                     if (r)
 623                     {
 624                         /* valid conversion from leet */
 625                         DictWork_t w;
 626                         w = *Wrk;
 627                         w.StartLoc = NodeLoc;
 628                         w.Ordinal = Ord;
 629                         w.PwdLength += Len;
 630                         w.Caps = Caps;
 631                         w.Lower = Lower;
 632                         w.First = *r;
 633                         w.NumPossChrs = NumPossChrs;
 634                         memcpy(w.PossChars, PossChars, sizeof w.PossChars);
 635                         if (j)
 636                         {
 637                             w.LeetCnv[i] = *r;
 638                             AddLeetChr(*r, -1, w.Leeted, w.UnLeet);
 639                         }
 640                         DoDictMatch(Pwd, Passwd - Pwd, MaxLen - Len, &w, Result, Extra, Lev+1);
 641                     }
 642                 }
 643                 return;
 644             }
 645         }
 646         q = CharBinSearch(c, PossChars, NumPossChrs, 1);
 647         if (q)
 648         {
 649             /* Found the char as a normal char */
 650             if (CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1))
 651             {
 652                 /* Char matches, but also a normal equivalent to a leet char */
 653                 AddLeetChr(c, 0,  Wrk->Leeted, Wrk->UnLeet);
 654             }
 655         }
 656         if (!q)
 657         {
 658             /* No match for char - return */
 659             return;
 660         }
 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];
 665         for(w=0; w<x; ++w)
 666         {
 667             int Cloc = ChildLocs[w+y];
 668             z = EndCountSml[Cloc];
 669             if (DictNodes[Cloc] & (1<<31))
 670                 z += EndCountLge[Cloc]*256;
 671             Ord += z;
 672         }
 673
 674         /* Move to next node */
 675         NodeData = DictNodes[NodeLoc];
 676         if (NodeData & (1<<30))
 677         {
 678             /* Word matches, save result */
 679             ZxcMatch_t *p;
 680             Extra->Caps = Caps;
 681             Extra->Rank = Ranks[Ord];
 682             Extra->Lower = Lower;
 683             for(x = 0, y = sizeof Extra->Leeted - 1; y >= 0; --y)
 684                 x += Wrk->Leeted[y];
 685             Extra->NumLeet = x;
 686
 687             memcpy(Extra->UnLeet, Wrk->UnLeet, sizeof Extra->UnLeet);
 688             memcpy(Extra->Leeted, Wrk->Leeted, sizeof Extra->Leeted);
 689
 690             p = AllocMatch();
 691             if (x)
 692                 p->Type = DICT_LEET_MATCH;
 693             else
 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);
 699
 700             ++Ord;
 701         }
 702     }
 703 }
 704
 705 /**********************************************************************************
 706  * Try to match password part with user supplied dictionary words
 707  * Parameters:
 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
 713  */
 714 static void UserMatch(ZxcMatch_t **Result, const char *Words[], const uint8_t *Passwd, int Start, int MaxLen)
 715 {
 716     int Rank;
 717     if (!Words)
 718         return;
 719     Passwd += Start;
 720     for(Rank = 0; Words[Rank]; ++Rank)
 721     {
 722         DictMatchInfo_t Extra;
 723         uint8_t LeetChr[sizeof L33TCnv / LEET_NORM_MAP_SIZE + 1];
 724         uint8_t TempLeet[3];
 725         int Len = 0;
 726         int Caps = 0;
 727         int Lowers = 0;
 728         int Leets = 0;
 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);
 734         while(*Wrd)
 735         {
 736             const uint8_t *q;
 737             uint8_t d = tolower(*Wrd++);
 738             uint8_t c = *Pwd++;
 739             if (isupper(c))
 740             {
 741                 c = tolower(c);
 742                 ++Caps;
 743             }
 744             else if (islower(c))
 745             {
 746                 ++Lowers;
 747             }
 748
 749
 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);
 752             if (q)
 753             {
 754                 /* Found, see if used before */
 755                 unsigned int j;
 756                 unsigned int i = (q - L33TCnv ) / LEET_NORM_MAP_SIZE;
 757                 if (LeetChr[i])
 758                 {
 759                     /* Used before, so limit characters to try */
 760                     TempLeet[0] = c;
 761                     TempLeet[1] = LeetChr[i];
 762                     TempLeet[2] = 0;
 763                     q = TempLeet;
 764                 }
 765                 c = d+1;
 766                 for(j = 0; (*q > ' ') && (j < LEET_NORM_MAP_SIZE); ++j, ++q)
 767                 {
 768                     if (d == *q)
 769                     {
 770                         c = d;
 771                         if (i)
 772                         {
 773                             LeetChr[i] = c;
 774                             AddLeetChr(c, 1, Extra.Leeted, Extra.UnLeet);
 775                             ++Leets;
 776                         }
 777                         break;
 778                     }
 779                 }
 780                 if (c != d)
 781                 {
 782                     Len = 0;
 783                     break;
 784                 }
 785             }
 786             else if (c == d)
 787             {
 788                 /* Found the char as a normal char */
 789                 if (CharBinSearch(c, L33TChr, sizeof L33TChr - 1, 1))
 790                 {
 791                     /* Char matches, but also a normal equivalent to a leet char */
 792                     AddLeetChr(c, 0,  Extra.Leeted, Extra.UnLeet);
 793                 }
 794             }
 795             else
 796             {
 797                 /* No Match */
 798                 Len = 0;
 799                 break;
 800             }
 801             if (++Len > MaxLen)
 802             {
 803                 Len = 0;
 804                 break;
 805             }
 806         }
 807         if (Len)
 808         {
 809             ZxcMatch_t *p = AllocMatch();
 810             if (!Leets)
 811                 p->Type = USER_MATCH;
 812             else
 813                 p->Type = USER_LEET_MATCH;
 814             p->Length = Len;
 815             p->Begin = Start;
 816             /* Add Entrpy */
 817             Extra.Caps = Caps;
 818             Extra.Lower = Lowers;
 819             Extra.NumLeet = Leets;
 820             Extra.Rank = Rank+1;
 821             DictionaryEntropy(p, &Extra, Passwd);
 822             AddResult(Result, p);
 823
 824         }
 825     }
 826 }
 827
 828 /**********************************************************************************
 829  * Try to match password part with the dictionary words
 830  * Parameters:
 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
 835  */
 836 static void DictionaryMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
 837 {
 838     DictWork_t Wrk;
 839     DictMatchInfo_t Extra;
 840
 841     memset(&Extra, 0, sizeof Extra);
 842     memset(&Wrk, 0, sizeof Wrk);
 843     Wrk.Ordinal = 1;
 844     Wrk.StartLoc = ROOT_NODE_LOC;
 845     Wrk.Begin = Start;
 846     DoDictMatch(Passwd+Start, 0, MaxLen, &Wrk, Result, &Extra, 0);
 847 }
 848
 849
 850 /*################################################################################*
 851  *################################################################################*
 852  * Begin keyboard spatial sequence matching code
 853  *################################################################################*
 854  *################################################################################*/
 855
 856 #define MIN_SPATIAL_LEN 3
 857
 858 /* Struct to hold information on a keyboard layout */
 859 typedef struct Keyboard
 860 {
 861     const uint8_t *Keys;
 862     const uint8_t *Shifts;
 863     int NumKeys;
 864     int NumNear;
 865     int NumShift;
 866     int NumBlank;
 867 } Keyboard_t;
 868
 869 /* Struct to hold information on the match */
 870 typedef struct
 871 {
 872     int Keyb;
 873     int Turns;
 874     int Shifts;
 875 } SpatialMatchInfo_t;
 876
 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_-{[|\\}]~`";
 880
 881
 882 /* Neighour tables */
 883 static const uint8_t UK_Qwerty[48*7] =
 884 {
 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
 910 };
 911
 912 static const uint8_t US_Qwerty[47*7] =
 913 {
 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,
 939 };
 940 static const uint8_t Dvorak[48*7] =
 941 {
 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
 966 };
 967
 968 static const uint8_t PC_Keypad[15*9] =
 969 {
 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'
 986 };
 987
 988 static const uint8_t MacKeypad[16*9] =
 989 {
 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'
1006 };
1007
1008 static const Keyboard_t Keyboards[] =
1009 {
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 }
1015 };
1016
1017 /**********************************************************************************
1018  * Match password for the given keyboard layout
1019  */
1020 static int DoSptlMatch(const uint8_t *Passwd, int MaxLen, const Keyboard_t *Keyb, SpatialMatchInfo_t *Extra)
1021 {
1022     int i;
1023     int ShiftCount = 0;
1024     int Turns = 0;
1025     int Dir = -1;
1026     int Len = 0;
1027     uint8_t PrevChar = 0;
1028     for( ; *Passwd && (Len < MaxLen); ++Passwd, ++Len)
1029     {
1030         const uint8_t *Key;
1031         int s = 0;
1032         uint8_t CurChar = *Passwd;
1033         /* Try to unshift the character */
1034         if (Keyb->Shifts)
1035         {
1036             Key = CharBinSearch(CurChar, Keyb->Shifts, Keyb->NumShift, 2);
1037             if (Key)
1038             {
1039                 /* Shifted char */
1040                 CurChar = Key[1];
1041                 s = 1;
1042             }
1043         }
1044         if (PrevChar)
1045         {
1046             /* See if the pattern can be extended */
1047             i = 0;
1048             Key = CharBinSearch(PrevChar, Keyb->Keys, Keyb->NumKeys, Keyb->NumNear);
1049             if (Key)
1050             {
1051                 for(i = Keyb->NumNear - 1; i > 0; --i)
1052                 {
1053                     if (Key[i] == CurChar)
1054                         break;
1055                 }
1056             }
1057             if (i)
1058             {
1059                 Turns += (i != Dir);
1060                 Dir = i;
1061                 ShiftCount += s;
1062             }
1063             else
1064             {
1065                 break;
1066             }
1067         }
1068         PrevChar = CurChar;
1069     }
1070     if (Len >= MIN_SPATIAL_LEN)
1071     {
1072         Extra->Turns = Turns;
1073         Extra->Shifts = ShiftCount;
1074         return Len;
1075     }
1076     return 0;
1077 }
1078
1079 /**********************************************************************************
1080  *  Try to match spatial patterns on the keyboard
1081  * Parameters:
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
1086  */
1087 static void SpatialMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1088 {
1089     unsigned int Indx;
1090     int Len, CurLen;
1091     SpatialMatchInfo_t Extra;
1092     const Keyboard_t *k;
1093     Passwd += Start;
1094
1095     for(CurLen = MaxLen; CurLen >= MIN_SPATIAL_LEN;CurLen = Len - 1)
1096     {
1097         Len = 0;
1098         memset(&Extra, 0, sizeof Extra);
1099         for(k = Keyboards, Indx = 0; Indx < (sizeof Keyboards / sizeof Keyboards[0]); ++Indx, ++k)
1100         {
1101             Len = DoSptlMatch(Passwd, CurLen, k, &Extra);
1102             if (Len > 0)
1103             {
1104                 /* Got a sequence of required length so add to result list */
1105                 int i, j, s;
1106                 double Degree, Entropy;
1107                 ZxcMatch_t *p;
1108                 Degree = (k->NumNear-1) - (double)k->NumBlank / (double)k->NumKeys;
1109                 s = k->NumKeys;
1110                 if (k->Shifts)
1111                     s *= 2;
1112
1113                 /* Estimate the number of possible patterns with length ranging 2 to match length and */
1114                 /* with turns ranging from 0 to match turns */
1115                 Entropy = 0.0;
1116                 for(i = 2; i <= Len; ++i)
1117                 {
1118                     int PossTurns = Extra.Turns;
1119                     if (PossTurns >= i)
1120                         PossTurns = i-1;
1121                     for(j = 1; j <= PossTurns; ++j)
1122                         Entropy += nCk(i-1, j-1) * pow(Degree, j) * s;
1123                 }
1124                 if (Entropy > 0.0)
1125                     Entropy = log(Entropy);
1126                 if (Extra.Shifts)
1127                 {
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;
1132
1133                     Degree = 0.0;
1134                     j = Shift;
1135                     if (j > Unshift)
1136                         j = Unshift;
1137                     for(i = 0; i <= j; ++i)
1138                     {
1139                         Degree += nCk(Len, i);
1140                     }
1141                     if (Degree > 0.0)
1142                         Entropy += log(Degree);
1143                 }
1144                 p = AllocMatch();
1145                 p->Type = SPATIAL_MATCH;
1146                 p->Begin = Start;
1147                 p->Entrpy = Entropy;
1148                 p->Length = Len;
1149                 AddResult(Result, p);
1150                 break;
1151             }
1152         }
1153     }
1154 }
1155
1156
1157 /*################################################################################*
1158  *################################################################################*
1159  * Begin date matching code
1160  *################################################################################*
1161  *################################################################################*/
1162
1163 #define MIN_YEAR 1901
1164 #define MAX_YEAR 2019
1165
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[] =
1169 {
1170     "yyyy",
1171     "d?m?yy",
1172     "ddmmyy",
1173     "dmyyyy",
1174     "dd?m?yy",
1175     "d?mm?yy",
1176     "ddmyyyy",
1177     "dmmyyyy",
1178     "yyyymmd",
1179     "yyyymdd",
1180     "d?m?yyyy",
1181     "dd?mm?yy",
1182     "ddmmyyyy",
1183     "yyyy?m?d",
1184     "yyyymmdd",
1185     "dd?m?yyyy",
1186     "d?mm?yyyy",
1187     "yyyy?mm?d",
1188     "yyyy?m?dd",
1189     "dd?mm?yyyy",
1190     "yyyy?mm?dd",
1191     0
1192 };
1193 /* Possible separator characters that could be used */
1194 static const char DateSeperators[] = "/\\-_. ";
1195
1196 /**********************************************************************************
1197  * Try to match the password with the formats above.
1198  */
1199 static void DateMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1200 {
1201     int CurFmt;
1202     int YrLen = 0;
1203     int PrevLen = 0;
1204     uint8_t Sep = 0;
1205     Passwd += Start;
1206
1207     for(CurFmt = 0; Formats[CurFmt]; ++CurFmt)
1208     {
1209         int Len = 0;
1210         int Year = 0;
1211         int Mon  = 0;
1212         int Day  = 0;
1213         int Fail = 0;
1214         const uint8_t *p = Passwd;
1215         const char *Fmt;
1216         YrLen = 0;
1217         Sep = 0;
1218         /* Scan along the format, trying to match the password */
1219         for(Fmt = Formats[CurFmt]; *Fmt && !Fail; ++Fmt)
1220         {
1221             if (*Fmt == '?')
1222             {
1223                 if (!Sep && strchr(DateSeperators, *p))
1224                         Sep = *p;
1225                 Fail = (*p != Sep);
1226             }
1227             else if (isdigit(*p))
1228             {
1229                 if (*Fmt == 'd')
1230                 {
1231                     Day = 10 * Day + *p - '0';
1232                 }
1233                 else if (*Fmt == 'm')
1234                 {
1235                     Mon = 10 * Mon + *p - '0';
1236                 }
1237                 else
1238                 {
1239                     Year = 10 * Year + *p - '0';
1240                     ++YrLen;
1241                 }
1242             }
1243             else
1244             {
1245                 Fail = 1;
1246             }
1247             ++p;
1248             ++Len;
1249             if (Len >= MaxLen)
1250                 break;
1251         }
1252         if (Len < 4)
1253             Fail = 1;
1254         if (!Fail)
1255         {
1256             /* Character matching is OK, now check to see if valid date */
1257             if (((YrLen > 3) || (Len <= 4)) && ((Year < MIN_YEAR) || (Year > MAX_YEAR)))
1258                 Fail = 1;
1259             else if (Len > 4)
1260             {
1261                 if ((Mon > 12) && (Day < 13))
1262                 {
1263                     /* Swap day,month to try to make both in range */
1264                     int i = Mon;
1265                     Mon = Day;
1266                     Day = i;
1267                 }
1268                 /* Check for valid day, month. Currently assumes all months have 31 days. */
1269                 if ((Mon < 1) || (Mon > 12))
1270                     Fail = 1;
1271                 else if ((Day < 1) || (Day > 31))
1272                     Fail = 1;
1273             }
1274         }
1275         if (!Fail && (Len > PrevLen))
1276         {
1277             /* String matched the date, store result */
1278             double e;
1279             ZxcMatch_t *p = AllocMatch();
1280
1281             if (Len <= 4)
1282                 e = log(MAX_YEAR - MIN_YEAR + 1.0);
1283             else if (YrLen > 3)
1284                 e = log(31 * 12 * (MAX_YEAR - MIN_YEAR + 1.0));
1285             else
1286                 e = log(31 * 12 * 100.0);
1287             if (Sep)
1288                 e += log(4.0);  /* Extra 2 bits for separator */
1289             p->Entrpy = e;
1290             p->Type = DATE_MATCH;
1291             p->Length = Len;
1292             p->Begin = Start;
1293             AddResult(Result, p);
1294             PrevLen = Len;
1295         }
1296     }
1297 }
1298
1299
1300 /*################################################################################*
1301  *################################################################################*
1302  * Begin repeated character matching code
1303  *################################################################################*
1304  *################################################################################*/
1305
1306 #define MIN_REPEAT_LEN 3
1307
1308 /**********************************************************************************
1309  * Try to match password part as a set of repeated characters.
1310  * Parameters:
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
1315  */
1316 static void RepeatMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1317 {
1318     int Len, i;
1319     uint8_t c;
1320     Passwd += Start;
1321     /* Remember first char and the count its occurances */
1322     c = *Passwd;
1323     for(Len = 1; (Len < MaxLen) && (c == Passwd[Len]); ++Len)
1324     { }
1325     if (Len >= MIN_REPEAT_LEN)
1326     {
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)
1330         {
1331             ZxcMatch_t *p = AllocMatch();
1332             p->Type = REPEATS_MATCH;
1333             p->Begin = Start;
1334             p->Length = i;
1335             p->Entrpy = log(Card * i);
1336             AddResult(Result, p);
1337         }
1338     }
1339 }
1340
1341
1342 /**********************************************************************************
1343  **********************************************************************************
1344  * Begin character sequence matching code
1345  **********************************************************************************
1346  *********************************************************************************/
1347
1348 #define MIN_SEQUENCE_LEN 3
1349
1350 /**********************************************************************************
1351  * Try to match password part as a set of incrementing or decrementing characters.
1352  * Parameters:
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
1357  */
1358 static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, int MaxLen)
1359 {
1360     int Len=0;
1361     int SetLow, SetHigh, Dir;
1362     uint8_t First, Next;
1363
1364     Passwd += Start;
1365     First = Passwd[0];
1366     Dir = Passwd[1] - First;
1367     Len = 0;
1368     /* Decide on min and max character code for sequence */
1369     if (islower(*Passwd))
1370     {
1371         SetLow = 'a';
1372         SetHigh = 'z';
1373     }
1374     else if (isupper(*Passwd))
1375     {
1376         SetLow = 'A';
1377         SetHigh = 'Z';
1378     }
1379     else if (isdigit(*Passwd))
1380     {
1381         SetLow = '0';
1382         SetHigh = '9';
1383         if ((First == '0') && (Dir == 9))
1384         {
1385             /* Special case for decrementing sequence of digits, allow starting with 098 */
1386             Dir = -1;
1387             ++Len;
1388             ++Passwd;
1389         }
1390     }
1391     else
1392         return;
1393
1394     if ((Dir == 1) || (Dir == -1))
1395     {
1396         ++Len;
1397         while(1)
1398         {
1399             if ((Passwd[0] == '9') && (Passwd[1] == '0') && (Dir > 0))
1400             {
1401                 ++Len;
1402                 ++Passwd;
1403                 break;
1404             }
1405             Next = Passwd[0] + Dir;
1406             if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next))
1407                 break;
1408             ++Len;
1409             ++Passwd;
1410             if (Len >= MaxLen)
1411                 break;
1412         }
1413     }
1414     if (Len >= MIN_SEQUENCE_LEN)
1415     {
1416         /* Enough repeated char, so create results from number found down to min acceptable length */
1417         int i;
1418         double e;
1419         if ((First == 'a') || (First == '1'))
1420             e = log(2.0);
1421         else if (isdigit(First))
1422             e = log(10.0);
1423         else if (isupper(First))
1424             e = log(26*2.0);
1425         else
1426             e = log(26.0);
1427         if (Dir < 0)
1428             e += log(2.0);
1429
1430         for(i = Len; i >= MIN_SEQUENCE_LEN; --i)
1431         {
1432             ZxcMatch_t *p = AllocMatch();
1433             /* Add new result to head of list as it has lower entropy */
1434             p->Type = SEQUENCE_MATCH;
1435             p->Begin = Start;
1436             p->Length = i;
1437             p->Entrpy = e + log((double)i);
1438             AddResult(Result, p);
1439         }
1440     }
1441 }
1442
1443
1444 /**********************************************************************************
1445  **********************************************************************************
1446  * Begin top level zxcvbn code
1447  **********************************************************************************
1448  *********************************************************************************/
1449
1450
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.
1454  *
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.
1458  *
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
1463  * end node.
1464  *
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
1467  * of the password.
1468  */
1469
1470 /* Struct to hold the data of a node (imaginary point between password characters) */
1471 typedef struct
1472 {
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 */
1477 } Node_t;
1478
1479 /**********************************************************************************
1480  * Main function of the zxcvbn password entropy estimation
1481  */
1482 double ZxcvbnMatch(const char *Pwd, const char *UserDict[], ZxcMatch_t **Info)
1483 {
1484     int i;
1485     ZxcMatch_t *Zp;
1486     Node_t *Np;
1487     double e;
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);
1494     e = log((double)i);
1495
1496     /* Do matching for all parts of the password */
1497     for(i = 0; i < Len; ++i)
1498     {
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);
1507
1508         /* Add a default one character bruteforce path */
1509         Zp = AllocMatch();
1510         Zp->Type = BRUTE_MATCH;
1511         Zp->Begin = i;
1512         Zp->Length = 1;
1513         Zp->Entrpy = e;
1514         AddResult(&(Nodes[i].Paths), Zp);
1515
1516         /* Initially set distance to nearly infinite */
1517         Nodes[i].Dist = DBL_MAX;
1518
1519     }
1520     /* End node has infinite distance/entropy, start node has 0 distance */
1521     Nodes[i].Dist = DBL_MAX;
1522     Nodes[0].Dist = 0.0;
1523
1524     /* Reduce the paths using Dijkstra's algorithm */
1525     for(i = 0; i < Len; ++i)
1526     {
1527         int j;
1528         double MinDist = DBL_MAX;
1529         int MinIdx = 0;
1530         /* Find the unvisited node with minimum distance or entropy */
1531         for(Np = Nodes, j = 0; j < Len; ++j, ++Np)
1532         {
1533             if (!Np->Visit && (Np->Dist < MinDist))
1534             {
1535                 MinIdx = j;
1536                 MinDist = Np->Dist;
1537             }
1538         }
1539         /* Mark the minimum distance node as visited */
1540         Np = Nodes + MinIdx;
1541         Np->Visit = 1;
1542         e = Np->Dist;
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)
1548         {
1549             Node_t *Ep = Np + Zp->Length;
1550             double d = e + Zp->Entrpy;
1551             if (!Ep->Visit &&  (d < Ep->Dist))
1552             {
1553                 /* Update as lower dist, also remember the 'from' node */
1554                 Ep->Dist = d;
1555                 Ep->From = Zp;
1556             }
1557         }
1558         /* If we got to the end node stop early */
1559         /*if (Nodes[Len].Dist < DBL_MAX/2.0) */
1560           /*  break; */
1561     }
1562     /* Make e hold entropy result and adjust to log base 2 */
1563     e = Nodes[Len].Dist / log(2.0);
1564
1565     if (Info)
1566     {
1567         /* Construct info on password parts */
1568         *Info = 0;
1569         for(Zp = Nodes[Len].From; Zp; )
1570         {
1571             ZxcMatch_t *Xp;
1572             i = Zp->Begin;
1573
1574             /* Remove all but required path */
1575             Xp = Nodes[i].Paths;
1576             Nodes[i].Paths = 0;
1577             while(Xp)
1578             {
1579                 ZxcMatch_t *p = Xp->Next;
1580                 if (Xp == Zp)
1581                 {
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))
1585                     {
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;
1590                         FreeFn(Xp);
1591                     }
1592                     else
1593                     {
1594                         /* Put previous part at head of info list */
1595                         Xp->Next = *Info;
1596                         *Info = Xp;
1597                     }
1598                 }
1599                 else
1600                 {
1601                     /* Not going on info list, so free it */
1602                     FreeFn(Xp);
1603                 }
1604                 Xp = p;
1605             }
1606             Zp = Nodes[i].From;
1607         }
1608     }
1609     /* Free all paths. Any being returned to caller have already been freed */
1610     for(i = 0; i <= Len; ++i)
1611     {
1612         Zp = Nodes[i].Paths;
1613         while(Zp)
1614         {
1615             ZxcMatch_t *p = Zp->Next;
1616             FreeFn(Zp);
1617             Zp = p;
1618         }
1619     }
1620     FreeFn(Nodes);
1621
1622     return e;
1623 }
1624
1625 /**********************************************************************************
1626  * Free the path info returned by ZxcvbnMatch().
1627  */
1628 void ZxcvbnFreeInfo(ZxcMatch_t *Info)
1629 {
1630     ZxcMatch_t *p;
1631     while(Info)
1632     {
1633         p = Info->Next;
1634         FreeFn(Info);
1635         Info = p;
1636     }
1637 }