Password Generator with random variable length with a certain range and strong random generation

Question

I've designed a Password Generator for review. It takes the minimum length and adds 25% to produce a minimum and maximum length. My thought is to introduce a slight random variance in the length.

I used the Mersenne Twist 19937 64 bit generator, mt19937_64 and the uniform_int_distribution. Instead of creating a new uniform_int_distribution object for each range that I'll be using, my thought was to use a range that will be a multiple of all the ranges I'll be using. This way a modulus operation using the specific range size should still produce evenly distributed numbers.

Header

#include <string>
#include <vector>
#include <random>
using std::string;
using std::vector;
using std::mt19937_64;
using std::uniform_int_distribution;
using std::istream;
class PasswordGenerator
{
 const static size_t MIN_LENGTH = 8;
 const static double MAX_LENGTH_OFFSET;
 vector<string> stringsSets =
 {
 "abccefghijklmnopqrstuvwxyz",
 "ABCDEFJHIJKLMNOPQRSTUVWXYZ",
 "0123456789",
 "`~!@#$%^&*()_+-=[]{}\\|;':\",./<>?"
 };
 enum Options
 {
 NONE = 0,
 UPPER = 1,
 LOWER = 2,
 DIGIT = 4,
 PUNCTUATION = 8
 };
 Options usage = NONE;
 double minLen = MIN_LENGTH;
 double maxLen = MIN_LENGTH * (MAX_LENGTH_OFFSET + 1);
 int numOptions = 0;
 size_t maxRange = 1;
 void CalcMaxRange();
 void AddRange(const size_t);
 string MakeSubstring(string*, size_t, uniform_int_distribution<int>&, mt19937_64&);
public:
 PasswordGenerator(size_t minLength, bool lower, bool upper, bool digit, bool punct);
 PasswordGenerator();
 ~PasswordGenerator();
 string Generate();
};`

Body

#include "PasswordGenerator.h"
#include <cmath>
#include <functional>
#include <sstream>
#include <algorithm>
using std::bind;
using std::stringstream;
using std::random_shuffle;
using std::random_device;
using std::pow;
const double PasswordGenerator::MAX_LENGTH_OFFSET = .25;
void PasswordGenerator::CalcMaxRange()
{
 maxRange = stringsSets.size();
 for (auto s : stringsSets)
 {
 size_t rangeTemp = s.size();
 AddRange(rangeTemp);
 }
 return;
}
void PasswordGenerator::AddRange(const size_t range)
{
 if ( range != 0 && maxRange % range != 0)
 {
 maxRange *= range;
 }
}
PasswordGenerator::PasswordGenerator(size_t minLength = MIN_LENGTH, bool lower = true, bool upper = true, bool digit = true, bool punct = true)
{
 CalcMaxRange();
 if (minLength > MIN_LENGTH)
 {
 minLen = minLength;
 maxLen = minLength * (1 + MAX_LENGTH_OFFSET);
 }
 if (lower)
 {
 usage = (Options)(usage | LOWER);
 numOptions++;
 }
 if (upper)
 {
 usage = (Options)(usage | UPPER);
 numOptions++;
 }
 if (digit)
 {
 usage = (Options)(usage | DIGIT);
 numOptions++;
 }
 if (punct)
 {
 usage = (Options)(usage | PUNCTUATION);
 numOptions++;
 }
}
PasswordGenerator::PasswordGenerator()
{
 CalcMaxRange();
 usage = (Options)(UPPER | LOWER | DIGIT | PUNCTUATION);
 numOptions = 4;
}
PasswordGenerator::~PasswordGenerator()
{
}
string PasswordGenerator::Generate()
{
 int subLimit = ceil(maxLen / numOptions);
 AddRange(subLimit);
 random_device rd;
 mt19937_64 mt64{ rd() };
 uniform_int_distribution<int> dist(0, maxRange);
 auto rnd = bind(dist, mt64);
 stringstream ss;
 size_t stringsSize = stringsSets.size();
 int start = rnd() % stringsSize;
 size_t limit = stringsSize + start;
 for (int i = start; i < limit; i++)
 {
 Options tempOption = (Options)(int)pow(2, i % stringsSize);
 bool allowed = usage & tempOption;
 if (allowed)
 {
 string* temp = &stringsSets[i % stringsSize];
 ss << MakeSubstring(temp, rnd() % subLimit, dist, mt64);
 }
 }
 size_t currSize = ss.str().size();
 if (currSize < minLen)
 {
 size_t limitTemp = (maxLen - currSize) + (rnd() % (int)(maxLen - minLen));
 for (int i = 0; i < limitTemp; i++)
 {
 Options tempOption = NONE;
 bool allowed = false;
 while (!allowed)
 {
 size_t index = rnd() % stringsSize;
 tempOption = (Options)(int)pow(2, index);
 allowed = usage & tempOption;
 if (allowed)
 {
 string* tempString = &stringsSets[index];
 ss << (*tempString)[rnd() % (*tempString).size()];
 }
 }
 }
 }
 string retVal = ss.str();
 random_shuffle(retVal.begin(), retVal.end());
 return retVal;
}
string PasswordGenerator::MakeSubstring(string* chars, size_t length, uniform_int_distribution<int>& dist, mt19937_64& mt64)
{
 auto rnd = bind(dist, mt64);
 string retVal = string(length, '0円');
 size_t stringSize = (*chars).size();
 for (size_t i = 0; i < length; i++)
 {
 retVal[i] = (*chars)[rnd() % stringSize];
 }
 return retVal;
}

• Snowbody: Mersenne twister is a very poor choice for a random password generator. Yes, it's fast, and it has good randomness (as long as it's run enough) but it has a small internal state that is very easy to determine by observing the output. It is absolutely unsuitable for anything involving security or cryptography. For security purposes, you need a cryptographically strong random number generator. It will be slow.
• user33306: When the output has been shuffled, wouldn't that obscure the original output?
• Snowbody: That's not going to stop a skilled cracker for more than a few minutes. You're not adding any entropy by doing that. If they have access to your source code, or the machine code, or can run the password generator many times themselves, they'll easily figure it out.
• user33306: Which generator would you suggest?
• Toby Speight: Are the Options intentionally misaligned with stringsSets (upper/lower interchanged)?

Answer 1

Great usage of math

I actually spent like 30 minutes trying to prove that you're wrong, but then ended up with being wrong myself. To formalize your idea:

Given \$X \sim \mathcal{U}(0, a)\,ドル if \$Y\equiv X \pmod b\,ドル then \$Y \sim \mathcal{U}(0, b)\$ if and only if \$a \equiv 0 \pmod b\$ and \$a \ge b\$.

It might not be both ways, but my intuition tells me it is correct (I know my mathjax sucks).

---

Not so strong random number generator

On Windows, when using mingw, std::random_device always produces the same number. std::random_device is not portable, and it is not even possible to see if it is pseudo-random. Seeding it with current time (in nanoseconds) is still ok option in my opinion.

Use of deprecated random_shuffle

The function is deprecated in C++14, and removed in C++17. As a result, the code is already invalid today.

Hard to comprehend

The logic looks a bit disrupted. It flows nicely and then distorts, then continues to flow nicely again. Were you disrupted during the writing? Also the code seems imperative, e.g. telling how to do each atomic step.

Intended ADL call?

auto rnd = bind(dist, mt64);

The line above makes argument dependent lookup call. Paired with auto, this makes it rather suspicious. It probably will give a compiler error when used improperly, but still, ADL is a very dangerous tool.

Multiple consequent casts

Options tempOption = (Options)(int)pow(2, i % stringsSize);

This doesn't look good. It could just shift bits to the left and leave a comment about that (for those who are not familiar with bit maths, but most people are familiar). That would remove all of those casts. Or better yet, Options could have regular indexing, e.g. 0, 1, 2, 3, 4, .... Then only i % stringSize would be required.

Use references where appropriate

 string* temp = &stringsSets[i % stringsSize];
 ss << MakeSubstring(temp, rnd() % subLimit, dist, mt64);

In the code above, one could just use string& temp = stringsSets[i % stringsSize];. All of the dereferences and brackets would go away.

Answer 2

Don't use using in your headers

Everyone who uses the header will have string, vector, mt19937_64, uniform_int_distribution and istream in the global namespace whether they want them or not. It's not what I expect when I write #include "PasswordGenerator.h", and it's poor practice to inflict that on your (削除) victims (削除ここまで) users.

Avoid floating-point arithmetic.

There's nothing here that can't be done with integers. Using integer types avoids all sorts of precision and rounding issues you'd prefer not to think about. The same goes for (int)pow(2, n) where a simple 1<<n would do.

Don't reduce a uniform range by modulo operator.

This is a biased sampling:

uniform_int_distribution<int> dist(0, maxRange);
auto rnd = bind(dist, mt64);
// ...
int start = rnd() % stringsSize;

Instead, create a distribution of the required range:

std::uniform_int_distribution<int> strings_dist(0, stringsSize);
int start = strings_dist(mt64);

Remember, you can use several distributions with the single generator - that's one of the reasons they are designed to be separable.

• user33306: If the ranges I'm using are all multiples of the range in the distribution, then how is the sampling biased?
• Incomputable: Toby, I can confirm that modulo is ok in this case. Somewhat proof.