0
$\begingroup$

When we read PRNG requirements of the EPC standard, first rule (page 57 in this link) in the documentation;

Probability of a single RN16: The probability that any RN16 drawn from the RNG has value RN16 = j, for any j, shall be bounded by 0.8/2^16 < P(RN16 = j) < 1.25/2^16.

Does that mean if the PRNG generates 2^16 16-bit numbers, each number should occur once? Basically it wants a perfect 16-bit entropy.

But if it is this way, even C#'s cryptographically secure PRNG cannot meet that requirement. So I'm wondering that I interpreted this requirement right.

$\endgroup$
1
$\begingroup$

All is revealed in the last paragraph of that section, repeated below:-

A cryptographic suite defines RNG requirements and randomness criteria for cryptographic operations. These requirements and criteria may be different, and in particular may be more stringent, than those defined above for inventory and password operations.

Their three randomness tests are an attempt to create a protocol that works in the real world without too much computational effort. By crude analogy, it's like a children's test for randomness. You only have 65536 possible choices anyway (assuming the RNG can reach them all), so there's little point in relying on huge computational effort to generate cryptographic strength Tag codes. An attacker will just brute force them when appropriate tools are developed.

Basically it wants a perfect 16-bit entropy.

Actually no. On this forum, entropy is defined as unpredictability within a certain system's defined scope. There's a EPCglobal test that stipulates that sequential values are only 0.025% certain. That's pretty poor to protect your bank account or nuclear arsenal. For perfect entropy, the next value should only be predictable with a 0.0015% certainly, irrespective of prior RN16s. The first rule is just a lax, perhaps pragmatic interpretation. It allows a ~22% bias in the numbers. And yes, that means you can have consecutive identical RN16's. Prolonged consecutive RN16s might be an issue for the specific protocol implementation (I don't know).

C#'s cryptographically secure PRNG cannot meet that requirement

Unfamiliar with C#, but if it's like a proper *nix language, then the cryptographic generator should be pretty good. My interpretation of these rules is that they are much less stringent than those required for cryptographic purposes. Thus C# might very well fail them in the strict technical sense. It's just that C# is too good for them. True randomness (opposite of bad randomness) is a slippery beast. (It might be useful to flesh out your question illustrating how C# fails the tests).

You don't have these three rules in cryptographic RNDs. Just that each byte is very exactly 1/256ths certain in the long run.

$\endgroup$
  • $\begingroup$ I'm testing an experimental PRNG which passes all NIST STS tests for different seeds, but it will also be used in EPCglobal's protocol, so I think it should be compatible with that rules. I started testing them but it seems I got the first requirement wrong. But I still do not understand how to test it. Is there a tool to test these three requirements, or I have to implement them myself? $\endgroup$ – Cem Aug 7 '17 at 16:35
  • $\begingroup$ No there are no standard tools for RN16 testing. You'd have to implement yourself. However. I would ask: will the EPCglobal's protocol still work with your (very good) PRNG? I suspect it would. I suspect that the rules are for ease of implementation and if you already have a good one, then fine. $\endgroup$ – Paul Uszak Aug 7 '17 at 18:42
  • $\begingroup$ I don't have much knowledge about EPCglobal's protocol, only working on PRNG part. Also, It's mostly an experimental project and I just have to show that EPCglobal's requirements are satisfied. I read that ENT's serial correlation coefficient test is similar to EPCglobal's third test. I have the scores of 0.000069 and 0.000204 for different seeds where totally uncorrelated is 0. $\endgroup$ – Cem Aug 7 '17 at 20:20
  • $\begingroup$ Can your PRNG meet rule 3? The Mersenne Twister can't as it's easy to predict the entire output stream after 624 samples. Is your output unpredictable after noting the last few outputs? This is the differentiator between a PRNG and a CSRNG. – Paul Uszak Aug 7 at 18:48 $\endgroup$ – Paul Uszak Aug 11 '17 at 21:57
  • $\begingroup$ Thanks for your detailed answer, but I still do not understand how the first rule should be implemented. What I understand from the documentation is, if we have 65536 16-bit numbers, each distinct number should appear once. $\endgroup$ – Cem Aug 12 '17 at 21:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.