diff options
author | Sean Whitton <spwhitton@spwhitton.name> | 2017-06-25 06:48:21 +0100 |
---|---|---|
committer | Sean Whitton <spwhitton@spwhitton.name> | 2017-06-25 06:48:21 +0100 |
commit | 2b482c9ff6dd274154848782e305f08a885c2407 (patch) | |
tree | 1538bd84d38861e020f251a4a014f7c280414396 | |
parent | df90310768e7909582628815f90cf08cd252a6fa (diff) | |
parent | 3a23bf19cb4f685a58b34f5bfaa3b6fcc888896a (diff) | |
download | zxcvbn-c-2b482c9ff6dd274154848782e305f08a885c2407.tar.gz |
Merge tag 'v2.3+dfsg'
version 2.3 DFSG-cleaned
# gpg: Signature made Sun 25 Jun 2017 06:48:08 BST
# gpg: using RSA key 9B917007AE030E36E4FC248B695B7AE4BF066240
# gpg: issuer "spwhitton@spwhitton.name"
# gpg: Good signature from "Sean Whitton <spwhitton@spwhitton.name>" [ultimate]
# Primary key fingerprint: 8DC2 487E 51AB DD90 B5C4 753F 0F56 D055 3B6D 411B
# Subkey fingerprint: 9B91 7007 AE03 0E36 E4FC 248B 695B 7AE4 BF06 6240
-rw-r--r-- | LICENSE.txt | 22 | ||||
-rw-r--r-- | README.md | 6 | ||||
-rw-r--r-- | dict-generate.cpp | 85 | ||||
-rw-r--r-- | test.c | 65 | ||||
-rw-r--r-- | zxcvbn.c | 46 | ||||
-rw-r--r-- | zxcvbn.h | 40 |
6 files changed, 156 insertions, 108 deletions
diff --git a/LICENSE.txt b/LICENSE.txt new file mode 100644 index 0000000..5dd0b43 --- /dev/null +++ b/LICENSE.txt @@ -0,0 +1,22 @@ +The MIT License + +Copyright (c) 2015-2017 Tony Evans + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. + @@ -57,3 +57,9 @@ Dictionary trie encoding (used for by the word lookup code) based on idea from t Word Graph from http://www.pathcom.com/~vadco/cwg.html +## License + +MIT License + +* http://www.opensource.org/licenses/mit-license.php + diff --git a/dict-generate.cpp b/dict-generate.cpp index 410182d..711124d 100644 --- a/dict-generate.cpp +++ b/dict-generate.cpp @@ -1,32 +1,24 @@ /********************************************************************************** * Program to generate the dictionary for the C implementation of the zxcvbn password estimator. - * Copyright (c) 2015, Tony Evans - * All rights reserved. + * Copyright (c) 2015-2017 Tony Evans * - * Redistribution and use in source and binary forms, with or without modification, are - * permitted provided that the following conditions are met: + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: * - * 1. Redistributions of source code must retain the above copyright notice, this list - * of conditions and the following disclaimer. + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. * - * 2. Redistributions in binary form must reproduce the above copyright notice, this - * list of conditions and the following disclaimer in the documentation and/or other - * materials provided with the distribution. - * - * 3. Neither the name of the copyright holder nor the names of its contributors may be - * used to endorse or promote products derived from this software without specific - * prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT - * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED - * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH - * DAMAGE. + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. * **********************************************************************************/ @@ -95,6 +87,7 @@ public: unsigned int GetAddr() const { return mAddr; } NodeMap_t::iterator ChildBegin() { return mChild.begin(); } NodeMap_t::iterator ChildEnd() { return mChild.end(); } + unsigned int GetNumChild() { return mChild.size(); } int GetNumEnds() const { return mEndings; } NodeSPtr FindChild(char); std::string GetChildChars(); @@ -402,6 +395,9 @@ typedef vector<StringInt> StringIntVect_t; // Variables holding 'interesting' information on the data unsigned int MaxLength, MinLength, NumChars, NumInWords, NumDuplicate; +static string PassWithMaxChilds, MaxChildChars; +static unsigned int MaxNumChilds, MaxChildsPosn; + struct FileInfo { FileInfo() : Words(0), BruteIgnore(0), Accented(0), Dups(0), Used(0), Rank(0) { } @@ -686,6 +682,16 @@ static int CheckWord(NodeSPtr Root, const string & Str) if (e) ++i; + if (p->GetNumChild() > MaxNumChilds) + { + NodeMap_t::iterator Itc; + MaxNumChilds = p->GetNumChild(); + MaxChildsPosn = x; + PassWithMaxChilds = Str; + MaxChildChars.clear(); + for(Itc = p->ChildBegin(); Itc != p->ChildEnd(); ++Itc) + MaxChildChars += Itc->first; + } p = It->second; } @@ -1046,7 +1052,7 @@ static int OutputBinary(ostream *Out, const string & ChkFile, const string & Cha Out->write((char *)WordEnds, NumWordEnd); h(WordEnds, NumWordEnd); OutputSize += NumWordEnd; - delete WordEnds; + delete [] WordEnds; StringIntSet_t::iterator Its; string Str; @@ -1063,8 +1069,10 @@ static int OutputBinary(ostream *Out, const string & ChkFile, const string & Cha SetPtrs[p->i] = p; } // Output child bitmap + unsigned int CharSetLen = 0; for(Index = 0; Index < SetPtrs.size(); ++Index) { + unsigned int i, j; string::size_type z, y; StringInt *p; memset(Buf, 0, sizeof Buf); @@ -1078,6 +1086,15 @@ static int OutputBinary(ostream *Out, const string & ChkFile, const string & Cha Buf[y/8] |= 1 << (y & 7); } } + // Find max bits set which indicates max number chars ued at a node + for(i = j = 0; i < 8 * sizeof Buf; ++i) + { + if (Buf[i/8] & (1 << (i & 7))) + ++j; + } + if (j > CharSetLen) + CharSetLen = j; + Out->write((char *)Buf, BytePerEntry); h(Buf, BytePerEntry); } @@ -1127,7 +1144,8 @@ static int OutputBinary(ostream *Out, const string & ChkFile, const string & Cha "#define BITS_CHILD_PATT_INDEX " << BITS_CHILD_PATT_INDEX << "\n" "#define BITS_CHILD_MAP_INDEX " << BITS_CHILD_MAP_INDEX << "\n" "#define SHIFT_CHILD_MAP_INDEX BITS_CHILD_PATT_INDEX\n" - "#define SHIFT_WORD_ENDING_BIT (SHIFT_CHILD_MAP_INDEX + BITS_CHILD_MAP_INDEX)" << endl; + "#define SHIFT_WORD_ENDING_BIT (SHIFT_CHILD_MAP_INDEX + BITS_CHILD_MAP_INDEX)\n" + "#define CHARSET_SIZE " << (CharSetLen + 1) << endl; f.close(); } return OutputSize; @@ -1403,9 +1421,12 @@ int OutputCode(ostream *Out, bool Cmnts, const string & CharSet, StringIntSet_t } SetPtrs[p->i] = p; } + unsigned int CharSetLen = 0; x = 999; + Len = 0; for(Index = 0; Index < SetPtrs.size(); ++Index) { + unsigned int i, j; string::size_type z, y; StringInt *p; memset(Buf, 0, sizeof Buf); @@ -1424,6 +1445,14 @@ int OutputCode(ostream *Out, bool Cmnts, const string & CharSet, StringIntSet_t Buf[y/8] |= 1 << (y & 7); } } + // Find max bits set which indicates max number chars ued at a node + for(i = j = 0; i < 8 * sizeof Buf; ++i) + { + if (Buf[i/8] & (1 << (i & 7))) + ++j; + } + if (j > CharSetLen) + CharSetLen = j; for(z = 0; z < BytePerEntry; ++z) { y = Buf[z] & 0xFF; @@ -1447,7 +1476,7 @@ int OutputCode(ostream *Out, bool Cmnts, const string & CharSet, StringIntSet_t x = 999; } } - *Out << "\n};" << endl; + *Out << "\n};\n#define CHARSET_SIZE " << (CharSetLen+1) << endl; // Output the top 8 bits of the node word endings count. Since node with >255 endings have // been placed at the begining, and ther are not too many of them the array is fairly small. @@ -1714,6 +1743,8 @@ int main(int argc, char *argv[]) { cout << "Node data array size " << NodeData.size() << endl; cout << "Child pointer array size " << ChildAddrs.size() << endl; + cout << "Max node childs " << MaxNumChilds << " (chars " << MaxChildChars << " ) at character index " + << MaxChildsPosn << " using password " << PassWithMaxChilds.c_str() << endl; } shared_ptr<ofstream> fout; ostream *Out = &cout; @@ -1,32 +1,24 @@ /********************************************************************************** * Program to test the C implementation of the zxcvbn password strength estimator. - * Copyright (c) 2015, Tony Evans - * All rights reserved. + * Copyright (c) 2015-2017 Tony Evans * - * Redistribution and use in source and binary forms, with or without modification, are - * permitted provided that the following conditions are met: + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: * - * 1. Redistributions of source code must retain the above copyright notice, this list - * of conditions and the following disclaimer. + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. * - * 2. Redistributions in binary form must reproduce the above copyright notice, this - * list of conditions and the following disclaimer in the documentation and/or other - * materials provided with the distribution. - * - * 3. Neither the name of the copyright holder nor the names of its contributors may be - * used to endorse or promote products derived from this software without specific - * prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT - * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED - * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH - * DAMAGE. + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. * **********************************************************************************/ @@ -124,6 +116,8 @@ int DoChecks(char *file) int y = 0; int w = 0; int r = 0; + int Less = 0; + int More = 0; FILE *f = fopen(file, "r"); if (f == NULL) { @@ -185,17 +179,28 @@ int DoChecks(char *file) e = ZxcvbnMatch(Pwd, UsrDict, 0); x = e / Ent; /* More than 1% difference is a fail. */ - if ((x > 1.01) || (x < 1.0/1.01)) + if (x > 1.01) { - printf("Line %2d Calculated entropy %5.2f, expected %5.2f <%s>\n", y, e, Ent, Pwd); - r = 1; - break; + ++More; + if (r < 10) + { + printf("Line %2d Calculated entropy %5.2f, expected %5.2f <%s>\n", y, e, Ent, Pwd); + ++r; + } + } + else if (x < 1.0/1.01) + { + ++Less; + if (r < 10) + { + printf("Line %2d Calculated entropy %5.2f, expected %5.2f <%s>\n", y, e, Ent, Pwd); + ++r; + } } ++w; } fclose(f); - if (!r) - printf("Tested %d words\n", w); + printf("Tested %d words, %d with low entropy, %d with high\n", w, Less, More); return r; } @@ -1,33 +1,25 @@ /********************************************************************************** * C implementation of the zxcvbn password strength estimation method. - * Copyright (c) 2015, Tony Evans - * All rights reserved. + * Copyright (c) 2015-2017 Tony Evans * - * Redistribution and use in source and binary forms, with or without modification, are - * permitted provided that the following conditions are met: + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: * - * 1. Redistributions of source code must retain the above copyright notice, this list - * of conditions and the following disclaimer. + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. * - * 2. Redistributions in binary form must reproduce the above copyright notice, this - * list of conditions and the following disclaimer in the documentation and/or other - * materials provided with the distribution. + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. * - * 3. Neither the name of the copyright holder nor the names of its contributors may be - * used to endorse or promote products derived from this software without specific - * prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT - * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED - * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH - * DAMAGE. - * **********************************************************************************/ #include <zxcvbn.h> @@ -491,9 +483,8 @@ typedef struct uint8_t Leeted[sizeof L33TChr]; uint8_t UnLeet[sizeof L33TChr]; uint8_t LeetCnv[sizeof L33TCnv / LEET_NORM_MAP_SIZE + 1]; - /* uint8_t LeetChr[3]; */ uint8_t First; - uint8_t PossChars[48]; + uint8_t PossChars[CHARSET_SIZE]; } DictWork_t; /********************************************************************************** @@ -1492,8 +1483,9 @@ static void SequenceMatch(ZxcMatch_t **Result, const uint8_t *Passwd, int Start, { ++Len; ++Passwd; + break; } - else if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next)) + if ((Next > SetHigh) || (Next < SetLow) || (Passwd[1] != Next)) break; ++Len; ++Passwd; @@ -2,34 +2,26 @@ #define ZXCVBN_H_F98183CE2A01_INCLUDED /********************************************************************************** * C implementation of the zxcvbn password strength estimation method. - * Copyright (c) 2015, Tony Evans - * All rights reserved. + * Copyright (c) 2015-2017 Tony Evans * - * Redistribution and use in source and binary forms, with or without modification, are - * permitted provided that the following conditions are met: + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to deal + * in the Software without restriction, including without limitation the rights + * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + * copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: * - * 1. Redistributions of source code must retain the above copyright notice, this list - * of conditions and the following disclaimer. + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. * - * 2. Redistributions in binary form must reproduce the above copyright notice, this - * list of conditions and the following disclaimer in the documentation and/or other - * materials provided with the distribution. + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + * THE SOFTWARE. * - * 3. Neither the name of the copyright holder nor the names of its contributors may be - * used to endorse or promote products derived from this software without specific - * prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY - * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES - * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT - * SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, - * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED - * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR - * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN - * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN - * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH - * DAMAGE. - * **********************************************************************************/ /* If this is defined, the dictiononary data is read from file. When undefined */ |