4 ms·
It means exactly what it sounds like: the author tried to attack the generator, failed, and thus concluded that it must be a Very Hard Problem. Note that the f
by pbsd 11y ago
It means exactly what it sounds like: the author tried to attack the generator, failed, and thus concluded that it must be a Very Hard Problem.
Note that the field of pseudorandom number generation for non-cryptographic purposes is much less rigorous than cryptography. Typically, for a new generator to be accepted as "OK" all it needs to do is pass a number of fixed statistical tests, usually one of the TestU01 batteries [1]. This is usually the only falsifiable claim you get, and if you're familiar with diffusion and how to achieve it this is easy to work out. Other falsifiable claims include equidistribution, but that is not a very useful guarantee---simply incrementing by 1 will achieve that. The notion of indistinguishability against computationally-bounded adversaries does not exist. All of this contributes to this being a field where crackpottery abounds, and is hard to distinguish good from bad.
For example, here's a generator that uses 1/4 of an AES round per output word, and that passes the Crush battery of statistical tests (which uses ~2^35 samples). Is it a good generator? I would not bet on it.
#include <stdint.h>
#include <immintrin.h>
struct S {
static const unsigned kAesRounds = 1;
union {
uint32_t state_[4 * 4];
__m128i words_[4];
} u_;
unsigned counter_;
const __m128i key_;
S(uint64_t seed)
: u_{{0}}, key_{_mm_set_epi64x(seed, -seed)}, counter_{0} {
for(unsigned i = 0; i < 16; ++i) (void)next();
}
uint32_t next() {
const uint32_t output = u_.state_[counter_];
__m128i t = u_.words_[counter_ & 3];
counter_ = (counter_ + 1) & 15;
for(unsigned i = 0; i < kAesRounds; ++i)
t = _mm_aesenc_si128(t, key_);
u_.words_[counter_ & 3] = t;
return output;
}
};
[1] http://simul.iro.umontreal.ca/testu01/tu01.html http://simul.iro.umontreal.ca/testu01/tu01.html
- nkurz 11y agoIs there a particular reason you would bet against it, or do you just saying that you wouldn't would bet for any implementation without proven theoretical properties? (As an aside, it's probably just my lack of familiarity, but considering how simple the algorithm is I find the syntax surprisingly hard to follow. Is this modern C++?)
- pbsd 11y agoAlthough this thing is able to fool the 200 or so tests from TestU01, it would take a short time for an expert to devise a test that would distinguish it from random, and even recover the key (read: seed). On the other hand, AES-CTR (conjecturally) fools _all_ statistical tests that take less than 2^128 effort, and on top of that it is still very very fast (0.63 cycles per byte on Haswell). So what really was gained? Cryptographic primitives have gotten so fast that the additional speed from these ad hoc generators seems like an unworthy risk. I concede that it can be very fun to try to make them, though. Additionally, a generator that passes those 200 tests is not guaranteed to be high-quality for a particular usage, which might as well be considered nothing but another statistical test. There is the famous case of the r250 generator---an additive Fibonacci generator that passed all statistical tests of the time---which turned out to have characteristics that rendered costly real-world simulations wrong [1]. That is C++, yes, but I don't think there is much of anything modern about it. Trying to save on space probably contributed to its unreadability a bit. [1] http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.69.3382 http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.69....
- nkurz 11y agoHere's a paper that includes an analysis of a similar approach that uses 5 rounds of AES under the name ARS-5: http://www.thesalmons.org/john/random123/papers/random123sc11.pdf http://www.thesalmons.org/john/random123/papers/random123sc1...
- pbsd 11y agoI know this paper, and like this approach. Reduced-round primitives let you take advantage of existent analysis, and keep some guarantees while improving speed. In the case of AES, we know that the probability of any differential for 4 rounds is at most 2^-113; similar for linear probabilities [1]. I'm curious why ARS-4 fails Crush; I wonder if the custom key schedule is the culprit. [1] https://eprint.iacr.org/2005/321 https://eprint.iacr.org/2005/321
- YAYERKA 11y agoabout the C; https://software.intel.com/sites/landingpage/IntrinsicsGuide/ https://software.intel.com/sites/landingpage/IntrinsicsGuide...
- deleted 11y ago[deleted]
- JoachimSchipper 11y agoNit: you call _mm_aesenc_si128() once per call to next(), right? I don't see how that constitutes "1/4th of an AES round per output word". (You do output 1/4th of an AES block.) You are, of course, right about the actual point you're making. And calling _mm_aesenc_si128() once per 4 calls to next() may well suffice to pass a statistical test. Then again, even an LSFR passes most statistical tests...
- pbsd 11y agoYes, you're right, I am calling the AES round once per `next()` call. But note that this his could be rewritten as if(counter_ >= 4) { counter_ = 0; u_.words_[0] = _mm_aesenc_si128(u_.words_[0], key_); } return u_.state_[counter_++]; Which only uses one AES call every 4 words (and only one block of storage). Instead, I chose to avoid the `if` and compute blocks ahead of time, which makes for more predictable performance.