Can mt19937 with std::discardblockengine create cryptographically unpredictable sequence?
- User
Can mt19937 with std::discard_block_engine create cryptographically unpredictable sequence?
- Assistant
No, the combination of
std::mt19937, which is an implementation of the Mersenne Twister algorithm, andstd::discard_block_engine, which is a standard adaptor that skips a specified number of values in the output sequence of a given random-number engine, does not create a cryptographically secure sequence.The Mersenne Twister algorithm, while having a very long period and being suitable for Monte Carlo simulations and other statistical applications, is not designed to be cryptographically secure. The output of the Mersenne Twister algorithm can be predicted after observing a sufficient number of outputs because of its deterministic nature.
std::discard_block_enginedoes not alter the predictability of the underlying generator; it only modifies the output by skipping some values. The resulting sequence is still deterministic and, therefore, not secure for cryptographic purposes.For cryptographic applications, you need a cryptographically secure pseudorandom number generator (CSPRNG) that guarantees certain security properties, such as backtracking resistance and forward secrecy. You should use a random number generator that is designed for cryptography, like AES in Counter mode or algorithms provided by cryptographic libraries such as OpenSSL, libsodium, or a platform-specific facility like
/dev/urandomon Unix-like systems or the Cryptography API: Next Generation (CNG) on Windows.Note that while it might be tempting to think that "more random" operations, such as discarding blocks, might enhance the security of a non-cryptographic random number generator, the core issue is that the predictability inherent in these algorithms is a fundamental problem that cannot be mitigated through simple techniques like discarding output. A CSPRNG must be used where unpredictability is required for security purposes.
- User
Give me an example of using this conjunction
- Assistant
Sure, I can provide you with an example of how to use
std::mt19937together withstd::discard_block_engine. Keep in mind, this example is for purely non-cryptographic purposes, as the combination is not suitable for cryptographic security.#include <iostream> #include <random> #include <algorithm> #include <vector> int main() { std::random_device rd; // Non-deterministic seed source std::mt19937 engine(rd()); // Mersenne Twister engine seeded with rd() // Create a discard_block_engine that discards 200 values for every 210 generated std::discard_block_engine<std::mt19937, 210, 200> db_engine(engine); // Generate a sequence of random numbers using db_engine // The distribution and range are up to your application's requirements std::uniform_int_distribution<int> dist(1, 100); std::vector<int> random_numbers; for (size_t i = 0; i < 10; ++i) { int num = dist(db_engine); // Generate random numbers and add them to the vector random_numbers.push_back(num); } // Output the generated numbers std::cout << "Generated random numbers: "; for (int num : random_numbers) { std::cout << num << " "; } std::cout << std::endl; return 0; }In this example:
- We seed a
std::mt19937object with a non-deterministic seed fromstd::random_device. - We create a
std::discard_block_enginethat is using our MT19937 engine, configured to discard 200 out of every 210 generated values. - We set up a
std::uniform_int_distributionto produce numbers in the range [1, 100]. - We generate 10 random numbers from our discard block engine and write them to the vector
random_numbers. - Finally, we print the generated numbers to the console.
Remember that despite discarding values, the end result is still not cryptographically secure; this approach is for illustration and typical non-cryptographic use cases only. If you're developing an application where cryptographic security is needed, you should use a dedicated CSPRNG.
- We seed a
- User
How can I force unpredictability of numberic sequence that std::mt19937 produce? Are there techniques?
- Assistant
Forcing unpredictability in the output sequence of
std::mt19937to achieve cryptographic security is not feasible because the Mersenne Twister algorithm, whichstd::mt19937implements, is inherently deterministic and not designed for cryptographic security.However, if your goal is simply to improve the non-predictability of the sequence for non-security-critical uses, such as simulations or games, you can consider the following techniques to enhance the randomness of the initial state:
-
Use a High-Entropy Seed: Seed
std::mt19937with a more unpredictable source, such asstd::random_device. Whilestd::random_deviceis not cryptographically secure on all implementations, it usually provides better randomness than a fixed or time-based seed.std::random_device rd; std::mt19937 mt(rd()); -
Seed Sequencing: Use
std::seed_seqto combine multiple sources of non-deterministic seeds and improve the quality of the initial seed.std::random_device rd; std::array<std::uint32_t, 10> seed_data; std::generate(seed_data.begin(), seed_data.end(), std::ref(rd)); std::seed_seq seed_seq(std::begin(seed_data), std::end(seed_data)); std::mt19937 mt(seed_seq); -
Frequent Re-Seeding: Periodically re-seed the generator with high-entropy data to avoid long sequences with the same initial state. However, this needs to be done carefully and is not likely to improve security but rather improve the distribution quality and ensure a different sequence on each run.
If your intended usage requires cryptographic strength, such as in encryption, authentication, or any application where the predictability of the number sequence could lead to security vulnerabilities, then these techniques are insufficient. Instead, you should use a cryptographically secure pseudorandom number generator (CSPRNG).
There are several common CSPRNG algorithms used in practice:
- AES-CTR (Advanced Encryption Standard in Counter mode)
- ChaCha20
- Fortuna
Moreover, many software libraries and systems provide interfaces to cryptographic random number generators:
- C++11 and above:
std::random_devicemight be implemented as a CSPRNG in some cases, but this isn't guaranteed. As of writing (knowledge cutoff date in 2023), there's no standard CSPRNG in the C++ standard library. - OpenSSL: Offers functions such as
RAND_bytes()for generating cryptographically secure bytes. - Operating system APIs: In Unix-like systems, the
/dev/urandomand/dev/randomdevices are designed to provide cryptographic randomness. Windows has CryptGenRandom (deprecated) and the CNG API for cryptographic applications. - Third-party libraries: Libraries like libsodium and Crypto++ deliver various cryptographic functions, including secure random number generation.
In conclusion, while some techniques can improve the non-predictability of
std::mt19937, they do not make it suitable for cryptographic applications. If you need secure random numbers, always choose a CSPRNG that is accepted as being suitable for cryptographic use. -
- User
How efficient std::discard_block_engine for increasing random quality for std::mt19937?
- Assistant
std::discard_block_engineis not designed to increase the "quality" of randomness in the underlying random number generator (RNG); rather, its purpose is to create a new RNG that skips a certain number of elements from the original RNG's sequence. Quality in this context is usually measured in terms of statistical properties like uniformity and independence, not in terms of predictability or cryptographic security.The
std::mt19937engine already has excellent statistical properties for most non-cryptographic purposes. It has a very long period (2^19937 − 1) and passes numerous statistical tests for randomness, which makes it suitable for applications like simulations and modeling. Here are some points to consider regardingstd::discard_block_engine:-
Effect on Randomness: Using
std::discard_block_enginewithstd::mt19937will not make the resulting sequence more random in a statistical sense. The statistical properties of the random numbers generated by the Mersenne Twister algorithm are already very good, and skipping values doesn't improve them. -
Impact on Period:
std::discard_block_enginecan be configured to skip a fixed number of generated values regularly (e.g., discard 200 values every 210 generated). This skipping does not change the underlying engine's period; it merely selects a subsequence from the original period. -
Efficiency Considerations: When it comes to efficiency,
std::discard_block_engineadds some overhead because it calculates and discards the specified number of values in every cycle. This means you're doing extra work without getting any output for some of those calculations. Therefore, using this engine could potentially be less efficient compared to usingstd::mt19937directly, depending on how frequently values are discarded. -
Use Cases:
std::discard_block_enginemay be useful in parallel computations where different threads or processes need to use distinct subsequences from a single RNG sequence. With careful planning, you can usestd::discard_block_engineto divide the RNG sequence among workers without overlap.
In summary, while
std::discard_block_enginecan be useful for some specific tasks such as partitioning an RNG sequence for parallel computation, it does not inherently improve the randomness or the statistical properties of the generated numbers fromstd::mt19937. The purpose ofstd::discard_block_engineis mainly to provide a simple method of choosing non-overlapping, predictable subsequences from an RNG, not to enhance the quality of the randomness it produces. -
- User
Is it more efficient than just making unused invocations of std::mt19937 to pass unwanted generations?
- Assistant
std::discard_block_engineis specifically optimized to skip over a block of numbers in the generated sequence efficiently. When you configure astd::discard_block_engineto work with a generator likestd::mt19937, itsdiscardoperation is generally more efficient than manually invoking the generator to discard unwanted values.The efficiency comes from the fact that the adaptor can directly calculate the next state of the underlying
std::mt19937engine after a certain number of steps without generating all intermediate values. This is possible because Mersenne Twister has a mathematically understood transition function enabling the engine state to be advanced by an arbitrary number of steps efficiently.If you were to manually discard values by repeatedly calling the
std::mt19937generator, you would incur the computational cost of producing each value in the sequence, even though those values are immediately thrown away.To illustrate, here's a comparison of manual discarding vs. using
std::discard_block_engine:Manual discarding:
std::mt19937 mt(seed); for (size_t i = 0; i < num_to_discard; ++i) { mt(); // Inefficiently generate and discard the desired number of values } // Continue using mt after discardingUsing
std::discard_block_engine:std::discard_block_engine<std::mt19937, 210, 200> db_engine(mt); db_engine.discard(10); // Efficiently skip ahead 10 *effective* values of mt // Continue using db_engine after discardingIn the second case, the
discardfunction will efficiently compute the resulting state after the equivalent of 10 generated values (as blocks of states are managed internally).Therefore, if your use case involves skipping a substantial number of generated values periodically and performance is a concern, using
std::discard_block_engineis more efficient and is the recommended approach over manually invoking and discarding the outputs ofstd::mt19937. - User
If I have only one true random number that's kept in sectet and I generate other random numbers with std::mt19937 that are kept in secret either, can I produce cryptographical random sequence if I xor my only true random number with first random number from std::mt19937, then this will be my first crypto random number, then I xor the result with second random number from std::mt19937, it will be my second crypto random number, then I xor it with third random number from std::mt19937 and so on?
- Assistant
While at first glance it might seem like the approach you're describing could increase the security of the sequence generated by
std::mt19937, this method does not result in a cryptographically secure random sequence.Here's why the approach fails to achieve cryptographic security:
-
Predictability after Seed Exposure: If someone discovers the initial seed value (the "true random number" you're using), they can replicate the entire sequence generated by
std::mt19937, because it is a deterministic algorithm. From there, they could easily compute all the "crypto random numbers" by performing the same XOR operations that you've described. -
Linearity of the XOR Operation: The XOR operation is linear, meaning that if you know two of the inputs, you can determine the third. In other words, given
A XOR B = C, if you knowAandC, you can obtainB. Sincestd::mt19937generates a deterministic sequence, anyone who can observe or predict part of the sequence has enough information to potentially uncover the "true random number" and subsequently the rest of the sequence. -
Algorithmic Predictability:
std::mt19937has a state that can be entirely predicted after observing 624 outputs (since the state size is 19937 bits and eachstd::mt19937output is 32 bits). With this knowledge, all subsequent outputs (and thus the entire "encrypted" sequence) can be predicted by the attacker.
For a random sequence to be cryptographically secure, it needs to satisfy properties like:
- Unpredictability: An attacker should not be able to predict future outputs based on past outputs (forward secrecy).
- Irreversibility: It should be infeasible to reconstruct previous outputs or internal state from current or future outputs (backward secrecy).
- Lack of Bias: The output should have no discernible patterns or biases that an attacker might exploit.
Therefore, if cryptographic security is essential for your application, you should always use a dedicated cryptographically secure pseudorandom number generator (CSPRNG). These generators are designed to meet the necessary security criteria and withstand attempts to predict future outputs or determine past states. Examples include AES in counter mode (AES-CTR), ChaCha20, and hardware-based random number generators that meet appropriate security standards.
-
- User
Is there Lack of Bias in my example?
- Assistant
In your example, where you XOR a true random number with the outputs of
std::mt19937, you would largely maintain the lack of bias for that particular sequence in a statistical sense, assuming that 'true random number' is indeed uniformly random and independent of the PRNG state. This is because the XOR operation with a uniformly random bit will flip each bit of the output with a 50% probability, which tends to preserve the uniform distribution of the output.However, the lack of bias is not a sufficient condition for achieving cryptographic strength. Although the XOR operation may initially seem to add randomness to each output from the PRNG, the predictability and non-cryptographic nature of
std::mt19937mean that the overall process doesn't meet the criteria required for cryptographic use. Here are a few critical issues:-
Lack of Forward and Backward Secrecy: If an attacker gains knowledge about the internal state of
std::mt19937at any point, they can predict all future and past outputs. This violates the need for forward and backward secrecy in CSPRNGs. -
Lack of An Avalanche Effect: Cryptographically secure algorithms exhibit what's known as an "avalanche effect," where a one-bit change in the input leads to a drastic change in output.
std::mt19937does not have this property. -
Key Reuse: By XORing all outputs with the same true random number, you essentially reuse the key (the true random number) for every output, which is a well-known cryptographic weakness.
Remember, cryptographic strength is not just about having a uniform distribution; it's also about unpredictability and resistance to various forms of attack. To ensure true cryptographic security, you would need to use algorithms specifically designed for this purpose, such as AES in CTR mode for PRNG, which have been thoroughly vetted and tested against cryptographic attacks. These algorithms also use techniques like chaining outputs and feedback mechanisms that are deliberately absent in non-cryptographic PRNGs like the Mersenne Twister.
-