dev-cpp-users Mailing List for Dev-C++

There are already good random number generators with immensely much better
randomnes and immensely much longer sequences making them evilishly hard
to follow.

With a good entrophy to seed them - some of which I discussed in my
previous mail - even a quite simle application can use good cryptographic
strength random numbers.

Why invent an octagonal wheel when there are already true round wheels
available out there on the net?

Let's play a bit with the time() function - even if repeated a large
number of times - doesn't create hardly any entrophy. Let's say you get 10
bits of entrophy for the first call (i.e. a random time within a start
window of 15 minutes). Each following call add an entrophy close to zero.
Let's say that you call time() on average every 60 seconds (2^6
alternatives), which might give you 6 bits of entrophy. To get 256 bits of
entrophy (a very lousy entrophy for encryption seed), you then need 40
calls within a 40 minute interval... For real entrophy, you should
probably have at least 1024 or 2048 bits, which in this case translates to
a smapling interval of 150 to 300 minutes.

Let's then look a bit closer at the above alternative. You have still not
specified how you should manage to make the individual "random" delays
between each time() sample. If this isn't true random (which it can't be
since you haven't even managed to get a real seed yet) and instead
generated by calls to rand() (which is using a known algorithm and have a
very short sequence) then your 6 bits of entrophy for each 60 second
window actually gets multiplied by 0, i.e. you are still at your initial
10 bits of entrophy from the 15-minute uncertainty of when the first call
was made.

A large number of people have tried your approach in a number of variants.
Every one of them who have had their results stressed have fallen through,
i.e. the "randomnes" has been quickly shot to pieces.

We are not talking about world-class cryptographic analysis to pick the
above methods to pieces. More like a suitable programming exercise for
project Euler:
  http://www.mathschallenge.net/index.php?section=project
or maybe a home exercise for some courses at the university.

- There are no ways to just algorithmically create randomnes.
- There are good random number generators available freely.
- For most environments, entrophy can be picked up from the system.

Why then bother to try and do something that can't be done? Instead fix
good random generator from the net. Fix reasonably good entrophy from the
system. Mix together and use. Takes less time than even thinking about
inventing some smart methods for "garbling" the rand() sequence.

time(), srand(), rand() etc are _only_ for selecting which attack a moster
should use, what color a screen saver should display etc. They can not be
used for anything where random quality or preditability (or actually lack
of) is important.

With time() you get a few bits, but you have to look somewhere else to
collect the rest of the bits to use. In an interactive environment, the
user is a great source of entrophy. Else, you really have to dig in and
look under every stone there is. Only remember that repeating the same
operation twice doesn't double the entrophy. Most of the time it doesn't
give a single bit extra...

I don't write this to be difficult. It's just that there must be
absolutely no misconception that rand() and time() may be used for
cryptography or other fields where good random numbers and entrophy
are needed.

Note: more comments inlined below.

/Per W

On Tue, 9 Nov 2004, Aitor Moreno wrote:

> Yes.. I agree with you. Since time() doesn't generate true random
> numbers, with this EASY approach, better results are achieved... do
> you agree with me?

See comments above - no extra entrophy added.

> >
> Yes, of course this can happen.... but this introduces a noise in the
> resulting sequence.

Not noise - as in randomnes. It only adds predictability, i.e. "hooks"
that may be used to figure out what extra code you are using to garble the
rand() function.

> >
> Obviously... it is like trying to encrypt a java applet.... it is
> impossible, but with all the known techniques, you can make the attack
> more difficult, only for those attacks that know how to do it....
>
> With this easy approach, you can add a real noise to the resulting
> sequence that makes the analysis more difficult... or isn't it??

As I mentioned above: A lot of people have tried obfuscation. I don't know
about anyone who have managed to survive a real hack attempt.

> >
> And if it is small set of random numbers, with the proposed function,
> reseeding the sequence, and the interval between successive numbers is
> not trivial....
> do you think that is harder or easier to perform the analysis?

You need a random generator to make this strategy work. Then, you still
receive entrophy in a real slow way. And in the end, rand() in itself is
too bad to be helped by good entrophy

> >
> and if it is used only for choose a random color for my background ?
>
> I know what you are comment... and all it is true... the true random
> numbers are difficult to obtain...  And, like the topic was "true
> random numbers", I have to agree with that, because I think in the
> same way .
>
> But, a good approach for easy applications can be the proposed one in
> the first post or in the second one....
>
> In all cryptographic books it is used to appear a chapter about this ...

A good approach for easy applications that are not limited to selecting
the background color of a window is to pick the code available in these
chapters of the cryptographic books, or to just google for a download
site. Any other design decision either fails or requires extensive
statistics and cryptographics knowledge and may still backfire.

> ...
> Don't forget that it is very easy to check 2^32 seed values to find a
> suitable start seed. By knowing within a reasonable time span when the
> random numbers are generated, few random steps need to be tested with few
> stepped times to continue to follow this "random" chain.

Yes.. I agree with you. Since time() doesn't generate true random
numbers, with this EASY approach, better results are achieved... do
you agree with me?


> ...
> By constantly reseed the rand() function, you may also create local
> sequence loops, where the current time() call will result in a seed value
> already used before.

Yes, of course this can happen.... but this introduces a noise in the
resulting sequence.


> ...
> In short, the concept doesn't hold under cryptographic analysis.

Obviously... it is like trying to encrypt a java applet.... it is
impossible, but with all the known techniques, you can make the attack
more difficult, only for those attacks that know how to do it....

With this easy approach, you can add a real noise to the resulting
sequence that makes the analysis more difficult... or isn't it??

> If you produce huge number of random numbers, the sequence generated with
> the same time will be long - easy to catch. If you produce your numbers
> within a very long time interval, the time steps will affect more but then
> the numbers are so few that is still trivial to follow the sequence.

And if it is small set of random numbers, with the proposed function,
reseeding the sequence, and the interval between successive numbers is
not trivial....
do you think that is harder or easier to perform the analysis? 

and if it is used only for choose a random color for my background ?

I know what you are comment... and all it is true... the true random
numbers are difficult to obtain...  And, like the topic was "true
random numbers", I have to agree with that, because I think in the
same way .

But, a good approach for easy applications can be the proposed one in
the first post or in the second one....

In all cryptographic books it is used to appear a chapter about this ...

Bye!


-- 
Aitor Moreno
   ait...@gm...

Except that it doesn't add any randomnes since time() returns a very well
known value all the calls, and you are using a random number generator
with a well known sequence.

Don't forget that it is very easy to check 2^32 seed values to find a
suitable start seed. By knowing within a reasonable time span when the
random numbers are generated, few random steps need to be tested with few
stepped times to continue to follow this "random" chain.

By constantly reseed the rand() function, you may also create local
sequence loops, where the current time() call will result in a seed value
already used before.

In short, the concept doesn't hold under cryptographic analysis.

This is a reason why for example Intel has added random number generation
to some of their chipsets, and why most operating systems are using their
internal state changes to fill large buffers with entropy data.

You might look into information such as:
- number of tcp packets sent on primary network interface
- the product of all PID of all currently running tasks
- number of available bytes on the user disk partition
- number of microseconds needed for a user to enter a password
- contents of an area of the graphics memory
- ...

and then combine all this information into the seed entrophy of a high-end
random generator - definitely not the one available in the standard RTL.

And unless you are really, really, _really_ sure about the quality of your
entrophy you should be careful about restarting the random generator.

Believe me, the first thing peoples tries when unrolling an encryption is
to check how key generation is affected by current PID or time values. In
your case it is enough to start the application mutliple times from the
same start time to produce identical random sequences. The jitter within
the second will change number of identical random numbers until the system
ticks to the next second. However, this is trivial to catch and compensate
for since it is just a +/- 1 error in the time during transition from one
second to the next.

If you produce huge number of random numbers, the sequence generated with
the same time will be long - easy to catch. If you produce your numbers
within a very long time interval, the time steps will affect more but then
the numbers are so few that is still trivial to follow the sequence.

/Per W

On Tue, 9 Nov 2004, Aitor Moreno wrote:

> > I would assume your first rand() call always produces the same result,
> > i.e. that you seed the random number generator with a constant multiplied
> > with the current time.
>
> Yes, the first rand() always produces the same result... but
> multiplyed by a different value of current time, we can obtain a
> different seed to further random values
>
> Let suppose two different executions E1 and E2:
>
> srand( (unsigned)time( NULL ) *rand()/RAND_MAX );
>
> the first call of rand() is the same in execution 1 and 2. But the
> srand is seeded with different values  N1 and M1. (due to different
> times)
>
> Then we obtain a random number RN1 and RN2 that will be different.
>
> Then we re-seed the sequence again
> srand( (unsigned)time( NULL ) *rand()/RAND_MAX );
> both values in the mulplitication are different so, we are seeding
> again with two different seeds....
>
> And so on... Every time you need a random value.. the sequece is
> re-seeded with current time and the next existing random value..
>
> I think it is a easy way in order to complicate the analysis....
>
>
> > No much differene from the all-time "favorite" of
> > using process PID multiplied with time(). A large number of applications
> > have done this for generating session keys or similar. A short analysis
> > makes this approach obvious and an attacker may then find out a very small
> > range of possible seed values when trying to recreate the random sequence
> > used. Don't forget that most of the programs in the world are built using
> > a small set of runtime libraries. The runtime libraries are created using
> > an even smaller set of standard pseudo-random number generators.
>
> I dont think that this is perfect... but I believe that this can
> minimize the risk, seeing that you only get a single number of a
> sequence (you are reseeding it continously)
>
> > When just generating some semirandomnes for "fun" in an application, this
> > doesn't much matter.
>
> I agree...
>
> > However, as soon as the random sequences are used for
> > some soft of security, the seed becomes very important, and it might also
> > be an idea to think about the sequence, since max 2^32 sequences may be
> > created, which is very easily scanned.
> >
>
> Of course.... the pseudo random algorithms are becoming a proper
> science.... in fact, a way for atack secure systems like RSA is with
> atacks to the builtin pseudo ramdom algorithms... so you can reduce
> dramatically the range of possible keys.. for example.
>
> Bye!
>
> --
> Aitor Moreno
>    ait...@gm...
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Sybase ASE Linux Express Edition - download now for FREE
> LinuxWorld Reader's Choice Award Winner for best database on Linux.
> http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

> I would assume your first rand() call always produces the same result,
> i.e. that you seed the random number generator with a constant multiplied
> with the current time. 

Yes, the first rand() always produces the same result... but
multiplyed by a different value of current time, we can obtain a
different seed to further random values

Let suppose two different executions E1 and E2:

srand( (unsigned)time( NULL ) *rand()/RAND_MAX ); 

the first call of rand() is the same in execution 1 and 2. But the
srand is seeded with different values  N1 and M1. (due to different
times)

Then we obtain a random number RN1 and RN2 that will be different.

Then we re-seed the sequence again
srand( (unsigned)time( NULL ) *rand()/RAND_MAX ); 
both values in the mulplitication are different so, we are seeding
again with two different seeds....

And so on... Every time you need a random value.. the sequece is
re-seeded with current time and the next existing random value..

I think it is a easy way in order to complicate the analysis.... 


> No much differene from the all-time "favorite" of
> using process PID multiplied with time(). A large number of applications
> have done this for generating session keys or similar. A short analysis
> makes this approach obvious and an attacker may then find out a very small
> range of possible seed values when trying to recreate the random sequence
> used. Don't forget that most of the programs in the world are built using
> a small set of runtime libraries. The runtime libraries are created using
> an even smaller set of standard pseudo-random number generators.

I dont think that this is perfect... but I believe that this can
minimize the risk, seeing that you only get a single number of a
sequence (you are reseeding it continously)

> When just generating some semirandomnes for "fun" in an application, this
> doesn't much matter. 

I agree...

> However, as soon as the random sequences are used for
> some soft of security, the seed becomes very important, and it might also
> be an idea to think about the sequence, since max 2^32 sequences may be
> created, which is very easily scanned.
> 

Of course.... the pseudo random algorithms are becoming a proper
science.... in fact, a way for atack secure systems like RSA is with
atacks to the builtin pseudo ramdom algorithms... so you can reduce
dramatically the range of possible keys.. for example.

Bye! 

-- 
Aitor Moreno
   ait...@gm...

As I said, the performance counters (which are extra registers inside
Pentium-class processors) can keep track of the individual clock cycles of
the processor, i.e. better than ns resolution.

/Per W

On Tue, 9 Nov 2004, Rob Lawless wrote:

> sorry but i would like relative time in ms resolution....
> i tried using the getTickCount() but this does not seem to be very accurate
> if i need an ms value <32 ms
> any other suggestions?
> also is nanosecond resolution possible?
> regards
> Rob
> ----- Original Message -----
> From: "Per Westermark" <pw...@ia...>
> To: "Rob Lawless" <rob...@nt...>
> Cc: "DEV-CPP" <dev...@li...>
> Sent: Monday, November 08, 2004 10:55 PM
> Subject: Re: [Dev-C++] Calculating Time in milliseconds
>
>
> > Do you want absolute time or relative time in ms resolution?
> >
> > For Win32, you can use GetTickCount() that gives number of ms since the
> > machine booted. It overflows every 49.7 days.
> >
> > However, it doesn't tick every ms. For a workstation I think it change
> > value every 32 ms.
> >
> > I haven't bothered to test, but I think the tick interval depends on the
> > length of time strata used by the windows installation for task switching,
> > i.e. it will vary between workstation and server installation.
> >
> > For better time intervals you can use the performance counters in windows
> > - they count time in clock cycles of the processor.
> >
> > On a unix machine you can use gettimeofday() to get absolute time down
> > to us resolution, but for this function too, the time is of course not
> > stepped every microsecond. Note that this function - as compared to the
> > Win32 GetTickCount() function - takes some time to call, so a program
> > making large amount of calls will get slowed down.
> >
> > /Per W
> >
> > On Mon, 8 Nov 2004, Rob Lawless wrote:
> >
> > > Hey folks just reading the <ctime> documentation which can only specify
> a mimimun time in seconds...does anyone know how to calulate a time interval
> in milliseconds?
> > > regards
> > > Rob
> >
>
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Sybase ASE Linux Express Edition - download now for FREE
> LinuxWorld Reader's Choice Award Winner for best database on Linux.
> http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

I would assume your first rand() call always produces the same result,
i.e. that you seed the random number generator with a constant multiplied
with the current time. No much differene from the all-time "favorite" of
using process PID multiplied with time(). A large number of applications
have done this for generating session keys or similar. A short analysis
makes this approach obvious and an attacker may then find out a very small
range of possible seed values when trying to recreate the random sequence
used. Don't forget that most of the programs in the world are built using
a small set of runtime libraries. The runtime libraries are created using
an even smaller set of standard pseudo-random number generators.

When just generating some semirandomnes for "fun" in an application, this
doesn't much matter. However, as soon as the random sequences are used for
some soft of security, the seed becomes very important, and it might also
be an idea to think about the sequence, since max 2^32 sequences may be
created, which is very easily scanned.

/Per W

On Tue, 9 Nov 2004, Aitor Moreno wrote:

> > If you test the code, you will get values between 0 and 99, i.e. a lack of
> > samples with value 100.
>
> In fact, like I use real numbers, the achieved numbers are between 0
> and 99.9999999999...
> analytically.. the number is in the range  [0..100)  It can be 0 but no 100.
>
> In this situation, an int truncation must be performed ...
>
> >
> > using the time() of the application start as seed is very dangerous, which
> > Netscape knows about...
>
> I allways use this instruction:
> srand( (unsigned)time( NULL ) *rand()/RAND_MAX );
>
> With this, a random number is used to seed the next random number...
> it is more reliable.
>
> Bye!
>
>
> --
> Aitor Moreno
>    ait...@gm...
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Sybase ASE Linux Express Edition - download now for FREE
> LinuxWorld Reader's Choice Award Winner for best database on Linux.
> http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

sorry but i would like relative time in ms resolution....
i tried using the getTickCount() but this does not seem to be very accurate
if i need an ms value <32 ms
any other suggestions?
also is nanosecond resolution possible?
regards
Rob
----- Original Message -----
From: "Per Westermark" <pw...@ia...>
To: "Rob Lawless" <rob...@nt...>
Cc: "DEV-CPP" <dev...@li...>
Sent: Monday, November 08, 2004 10:55 PM
Subject: Re: [Dev-C++] Calculating Time in milliseconds


> Do you want absolute time or relative time in ms resolution?
>
> For Win32, you can use GetTickCount() that gives number of ms since the
> machine booted. It overflows every 49.7 days.
>
> However, it doesn't tick every ms. For a workstation I think it change
> value every 32 ms.
>
> I haven't bothered to test, but I think the tick interval depends on the
> length of time strata used by the windows installation for task switching,
> i.e. it will vary between workstation and server installation.
>
> For better time intervals you can use the performance counters in windows
> - they count time in clock cycles of the processor.
>
> On a unix machine you can use gettimeofday() to get absolute time down
> to us resolution, but for this function too, the time is of course not
> stepped every microsecond. Note that this function - as compared to the
> Win32 GetTickCount() function - takes some time to call, so a program
> making large amount of calls will get slowed down.
>
> /Per W
>
> On Mon, 8 Nov 2004, Rob Lawless wrote:
>
> > Hey folks just reading the <ctime> documentation which can only specify
a mimimun time in seconds...does anyone know how to calulate a time interval
in milliseconds?
> > regards
> > Rob
>

> If you test the code, you will get values between 0 and 99, i.e. a lack of
> samples with value 100.

In fact, like I use real numbers, the achieved numbers are between 0
and 99.9999999999...
analytically.. the number is in the range  [0..100)  It can be 0 but no 100.

In this situation, an int truncation must be performed ... 

> 
> using the time() of the application start as seed is very dangerous, which
> Netscape knows about...

I allways use this instruction:
srand( (unsigned)time( NULL ) *rand()/RAND_MAX );

With this, a random number is used to seed the next random number...
it is more reliable.

Bye! 


-- 
Aitor Moreno
   ait...@gm...

If you test the code, you will get values between 0 and 99, i.e. a lack of
samples with value 100.

using the time() of the application start as seed is very dangerous, which
Netscape knows about...

/Per W

On Tue, 9 Nov 2004, Aitor Moreno wrote:

> //Initialize....
> srand( (unsigned)time( NULL ) );
>
> //Get a random value between 0 and 1
> unitvalue= (real)rand()/RAND_MAX;
>
> //Now yourvalue will be between 0 and 100
> yourvalue = 100*unitvalue;
>
> --
> Aitor Moreno
>    ait...@gm...
>
>
> -------------------------------------------------------
> This SF.Net email is sponsored by:
> Sybase ASE Linux Express Edition - download now for FREE
> LinuxWorld Reader's Choice Award Winner for best database on Linux.
> http://ads.osdn.com/?ad_id=5588&alloc_id=12065&op=click
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>

//Initialize....
srand( (unsigned)time( NULL ) );

//Get a random value between 0 and 1
unitvalue= (real)rand()/RAND_MAX;

//Now yourvalue will be between 0 and 100
yourvalue = 100*unitvalue;

-- 
Aitor Moreno
   ait...@gm...

 =A0=0A=0A=0AHi All,=0A      I want to have a true random number generator =
program which should use input from soundcard mic. I will try all kind of n=
oises and sounds to generate these numbers which are one from each decade u=
pto 99. E.g, 00,12,21,32,47,50,69,72,84,94; This is an experiment to see th=
e algorithm of randomness of the incidents which are measured everyday for =
every half an hour.=0AIf you have any idea how to adopt this program for ce=
ll phones and try in different computers which don't have compilers in them=
 to use everytime.=0AI am now learning C and not an expert in languages and=
 so the request, =0Aall the best and thanks,=0AMD T