quality of FPC random

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

quality of FPC random

Xiangrong Fang
Hi All,

I need to generate random numbers to be used as IV of block ciphers.  My question is: is FPC built-in PRNG good enough as comparing to /dev/urandom?

On the other hand, /dev/urandom in my impression is fairly slow, how is the speed of Random() comparing to that?

Thanks!
Xiangrong



_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Jonas Maebe-2

Xiangrong Fang wrote on Fri, 14 Aug 2015:

> I need to generate random numbers to be used as IV of block ciphers.  My
> question is: is FPC built-in PRNG good enough as comparing to /dev/urandom?

No PRNG is suited for that purpose, because every PRNG is by  
definition predictable and you need unpredictable numbers for IVs.

> On the other hand, /dev/urandom in my impression is fairly slow, how is the
> speed of Random() comparing to that?

They are not comparable, they serve completely different purposes.  
Additionally, the speed of /dev/urandom depends on a lot of factors  
(it gets its input from various kinds of activity on the system, so  
the more activity there is, the faster it becomes).


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
On 08/14/2015 03:47 PM, Jonas Maebe wrote:
>
>>   My question is: is FPC built-in PRNG good enough as comparing to
>> /dev/urandom?
>
> No PRNG is suited for that purpose, because every PRNG is by
> definition predictable and you need unpredictable numbers for IVs.
>

How should /dev/urandom not be predictable (as any software random
generator is)  ?

Decent Wifi hubs use hardware of some kind.

-Michael
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Xiangrong Fang
In reply to this post by Jonas Maebe-2
2015-08-14 21:47 GMT+08:00 Jonas Maebe <[hidden email]>:

Xiangrong Fang wrote on Fri, 14 Aug 2015:

I need to generate random numbers to be used as IV of block ciphers.  My
question is: is FPC built-in PRNG good enough as comparing to /dev/urandom?

No PRNG is suited for that purpose, because every PRNG is by definition predictable and you need unpredictable numbers for IVs.

​Well, practically, how can I get totally unpredictable numbers? On stackoverflow, someone suggested using hash value of data as IV, but that's still flawed somehow.

Without introduce hardware source like a dongle or other devices (which is not acceptable for my purpose), I suppose good quality PRNGs​ are the only thing that I can use?

​Also, why FPC random number are not comparable to /dev/urandom?  Despite the difference in their quality and speed (if any), what's the difference between them? especially, what are the typical use cases of these 2 PRNGs when they are designed?​


_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Mark Morgan Lloyd-5
In reply to this post by Michael Schnell
Michael Schnell wrote:

> On 08/14/2015 03:47 PM, Jonas Maebe wrote:
>>
>>>   My question is: is FPC built-in PRNG good enough as comparing to
>>> /dev/urandom?
>>
>> No PRNG is suited for that purpose, because every PRNG is by
>> definition predictable and you need unpredictable numbers for IVs.
>>
>
> How should /dev/urandom not be predictable (as any software random
> generator is)  ?

It seeds itself with "entropy" from the intervals between LAN packets,
intervals between typed characters and so on.

> Decent Wifi hubs use hardware of some kind.

Noise diode, entropy as discussed above, etc. Or they've got broken
security, which probably describes the majority.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Jonas Maebe-2
In reply to this post by Xiangrong Fang

Xiangrong Fang wrote on Fri, 14 Aug 2015:

> 2015-08-14 21:47 GMT+08:00 Jonas Maebe <[hidden email]>:
>
>> No PRNG is suited for that purpose, because every PRNG is by definition
>> predictable and you need unpredictable numbers for IVs.
>
> ​Well, practically, how can I get totally unpredictable numbers?

By using /dev/urandom

> Without introduce hardware source like a dongle or other devices (which is
> not acceptable for my purpose), I suppose good quality PRNGs​ are the only
> thing that I can use?

No, you cannot use PRNGs for this purpose at all.

> ​Also, why FPC random number are not comparable to /dev/urandom?  Despite
> the difference in their quality and speed (if any), what's the difference
> between them? especially, what are the typical use cases of these 2 PRNGs
> when they are designed?​

/dev/urandom is not a PRNG. It returns "real" random numbers and its  
use case is for security-sensitive purposes (how reliable it is at  
generating true random data, is a completely separate issue). The use  
case for a PRNG like FPC's is in games, simulations and the like.

Again: all PRNG's are of the absolutely worst possible quality when  
the goal is security, because no matter how good they are at bit  
swizzling and regardless of how large their state is, they are 100%  
predictable.


Jonas

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
In reply to this post by Mark Morgan Lloyd-5
On 08/14/2015 04:38 PM, Mark Morgan Lloyd wrote:
>
> It seeds itself with "entropy" from the intervals between LAN packets,
> intervals between typed characters and so on.
>
Unfortunately "Randomize" (in Linux in "System") just does

randseed:=longint(Fptime(nil));

if it would use /dev/urandom, the rand() would be as unpredictable as
/dev/urandom unless you fetch more more than some 2 Gig numbers

But I suppose you can set randseed in user code, as well, if you want to.

-Michael
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
In reply to this post by Xiangrong Fang
On 08/14/2015 04:27 PM, Xiangrong Fang wrote:


​ Well, practically, how can I get totally unpredictable numbers?

Nothing is totally unpredictable :-)

I would set randseed via randseed and after this you can just use rand() for at least 2 gig numbers without any perceptible predictability.

On stackoverflow, someone suggested using hash value of data as IV, but that's still flawed somehow.

There are lots of "scientific" articles on creating random numbers (I read some during my work at the university). Most of them are just nonsense.

The common request is "unpredictable" and "equal distribution".

But a "real" random generator can (and according to Murphy will sometimes during Eternity)  happily create an uninterrupted  series of a million of Zeros. To human perception this is neither unpredictable nor equal distribution. In fact random numbers are just a matter of taste.

-Michael

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
On 08/17/2015 10:14 AM, Michael Schnell wrote:
>
> I would set randseed via randseed
Grrr. I would set randseed via /dev/urandom

-Michael
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Mark Morgan Lloyd-5
In reply to this post by Michael Schnell
Michael Schnell wrote:

> On 08/14/2015 04:38 PM, Mark Morgan Lloyd wrote:
>>
>> It seeds itself with "entropy" from the intervals between LAN packets,
>> intervals between typed characters and so on.
>>
> Unfortunately "Randomize" (in Linux in "System") just does
>
> randseed:=longint(Fptime(nil));
>
> if it would use /dev/urandom, the rand() would be as unpredictable as
> /dev/urandom unless you fetch more more than some 2 Gig numbers
>
> But I suppose you can set randseed in user code, as well, if you want to.

I agree, with the caveat that if you read /dev/urandom you can't be sure
that there's enough accumulated entropy to give you a good seed, while
if you read /dev/random it will block for an indeterminate time- neither
of which are desirable behaviours in startup code. A compromise is for a
program to wait until it knows it's generated enough entropy (LAN
accesses or whatever), and at that point to reseed its random number
generator, and that obviously suggests leaving the existing code unchanged.

In the past, I've seen people who should have known better caught by
Turbo Pascal's inadequate random number generator, and there's still
people trying to undo some of the damage caused by RANDU. These days,
there's very little excuse for anybody "skilled in the art" to not
understand that the random number facility in most languages' default
libraries is not crypto grade, and that it is barely adequate for
academic-grade simulations.

--
Mark Morgan Lloyd
markMLl .AT. telemetry.co .DOT. uk

[Opinions above are the author's, not those of his employers or colleagues]
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Peter
In reply to this post by Michael Schnell
On 17/08/15 09:05, Michael Schnell wrote:
> Unfortunately "Randomize" (in Linux in "System") just does
> randseed:=longint(Fptime(nil));
>
> if it would use /dev/urandom,
> ....


Perhaps that is worthy of a bug report?
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Van Canneyt


On Mon, 17 Aug 2015, Peter wrote:

> On 17/08/15 09:05, Michael Schnell wrote:
>> Unfortunately "Randomize" (in Linux in "System") just does
>> randseed:=longint(Fptime(nil));
>>
>> if it would use /dev/urandom,
>> ....
>
>
> Perhaps that is worthy of a bug report?

Don't bother. It's just a default.
You can enter whatever you want in randseed if so desired.

And as Jonas pointed out, you should not use FPC's Builtin random to begin with
if you want really random numbers, because it is perfectly predictable.

In short:
People interested in crypto grade randomness should use specialized routines,
not the built-ins provided by FPC.

Michael.
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
On 08/17/2015 11:15 AM, Michael Van Canneyt wrote:
>
> In short: People interested in crypto grade randomness should use
> specialized routines, not the built-ins provided by FPC.
+1

As said: random numbers are a matter if taste (or of the application)

e.g. :

I once did a project where we such a wide range of integer random
numbers that doing them as int64 was not enough

With "Monecarlo" method to estimate  statistical profitability you
usually need random numbers as real-values to enter them in a simulated
process. here predictability is not a great issue.

Cryptography is a completely different issue. here a decent device uses
hardware to create the random seed.


-Michael
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Adriaan van Os-2
In reply to this post by Michael Van Canneyt
Michael Van Canneyt wrote:
> In short: People interested in crypto grade randomness should use
> specialized routines, not the built-ins provided by FPC.

So, why not provide an FPC CryptoRandom function, calling into /dev/urandom on UNIX and
CryptGenRandom <https://msdn.microsoft.com/en-us/library/aa379942(v=vs.85).aspx> on Windows ?

Regards,

Adriaan van Os
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Jonas Maebe-2

Adriaan van Os wrote on Mon, 17 Aug 2015:

> So, why not provide an FPC CryptoRandom function, calling into  
> /dev/urandom on UNIX and CryptGenRandom  
> <https://msdn.microsoft.com/en-us/library/aa379942(v=vs.85).aspx> on  
> Windows ?

Proper cryptography requires much more than just unpredictable random  
numbers. This is something that belongs in a specialised library, or  
in a set of specialised units written by experts. It has no place in a  
generic RTL unit.


Jonas
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Klaus Hartnegg-3
In reply to this post by Xiangrong Fang
Am 14.08.2015 um 15:38 schrieb Xiangrong Fang:
> I need to generate random numbers to be used as IV of block ciphers.  My
> question is: is FPC built-in PRNG good enough as comparing to /dev/urandom?

NO!!!
For crypto always use /dev/urandom

> On the other hand, /dev/urandom in my impression is fairly slow, how is
> the speed of Random() comparing to that?

Speed is irrelevant, because you do not need many truely random numbers
for crypto.
For crypto always use /dev/urandom

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

David W Noon-2
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Thu, 20 Aug 2015 22:50:05 +0200, Klaus Hartnegg (<[hidden email]>)
wrote about "Re: [fpc-pascal] quality of FPC random" (in
<[hidden email]>):

> Am 14.08.2015 um 15:38 schrieb Xiangrong Fang:
>> I need to generate random numbers to be used as IV of block
>> ciphers.  My question is: is FPC built-in PRNG good enough as
>> comparing to /dev/urandom?
>
> NO!!! For crypto always use /dev/urandom
>
>> On the other hand, /dev/urandom in my impression is fairly slow,
>> how is the speed of Random() comparing to that?
>
> Speed is irrelevant, because you do not need many truely random
> numbers for crypto. For crypto always use /dev/urandom

man 4 random

The /dev/urandom device can resort to a PRNG and can, therefore, be
attacked when used for crypto.  Consequently, /dev/urandom is *not*
universally suitable for cryptographic purposes.

In contrast, /dev/random is based on the system entropy pool.  Its
numbers are genuinely random.  The downside is that if the entropy
pool runs low on bytes, read requests will block until the pool is
refilled.

On this machine, I have a hardware random number generator on the bus
control chipset and a daemon process that uses the hardware to top up
the entropy pool when it gets low.  I highly recommend such a set-up.
 Failing that, you can use the HAVEGE daemon (Google is your friend)
to top up the entropy pool from other sources, if you don't have a
hardware RNG.
- --
Regards,

Dave  [RLU #314465]
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
[hidden email] (David W Noon)
*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAlXWWF4ACgkQogYgcI4W/5RqJQCgsVvdf3ihJrvqs4UQdICQTB7T
epkAoMXQR+Kjai///7EibePEoT6RUoq/
=IGX0
-----END PGP SIGNATURE-----
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Peter
http://www.2uo.de/myths-about-urandom/
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: quality of FPC random

Michael Schnell
In reply to this post by Xiangrong Fang
Thinking more about the issue:

As said, the quality of a random number generator is more a matter of taste than a subject to in-depth discussion (as nearly everything that is influenced by the way infinity word).

Obviously a perfect random number generator (for integer numbers 0...n) needs to be able to create a series of a million zeros. This is (seemingly) neither a nice Equal Distribution nor obviously unpredictable.



IMHO a very decent random generator is just the simple process

r(n) = x(n)   with    x(n) = (a + b*x(n-1) ) mod c 

Here c should be a (big) prime, as you will get "less random" sub-series of the length of any factor of c.

OK let a and b be big primes, as well. That does not harm.


Equal Distribution is granted, as the sequence will completely cover all the numbers 0..c-1 and then start from the beginning.

Of course it is perfectly predictable if you know the numbers a, b, and c. and I suppose you can detect them from watching the series for a rather short time.


You can reduce the predictability by doing a much smaller non-process from the big cyclic process

maybe just

r(n) = x(n) mod d  with    x(n) = (a + b*x(n-1) ) mod c        with d being a prime several orders of magnitude lower than c (and a and b)

could work (I did not try a proof or disproof). Maybe d needs not be a prime but just 2^n if you want an appropriately long key.

But for cryptology all this needs really large integer numbers. That should not be an unsolvable problem. Finding a really large Prime is a standard task, anyway.


Of course x(0) should be created using a nice entropy method.

-Michael

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal