An Examination of Visual Basic's Random Number Generation

Introduction

While training and mentoring a new user with a Microsoft Access application I'd written for the client, a quite unexpected condition occurred in my application. This would normally be the kind of condition that prompts me to find an error I'd introduced and not trapped. However, this time the error elicited exclamations of wonder and puzzlement. Surely this could not happen... but I was a witness and couldn't deny my own eyes.

Accepting the possibility that it could happen and creating a do-over (with different key) patch was my highest priority. That patch allowed the application to continue with that day's production run. Disaster had been averted and I left the client's office shaking my head in disbelief. Time to put on my Computer Scientist cap. This is the story of my research and a warning or alert to all VB developers who use the PRNG features of the VB language.

PRNG is not a new Visual Basic statement, feature, referenced class, nor a new kind of potato chip. It is an acronym for Pseudo-Random Number Generator. I'll get to the details about PRNGs and VB PRNG features in a moment. Firstly, I should explain why a Microsoft Access business application needs to use PRNG features.

The Application

Several years ago, we added a feature to this executive survey application that allows the survey taker to answer the survey questions online through their Internet browser. Originally, the surveys were all paper answers that were typed into the database application in typical data-entry fashion. After some setup data entry and Excel data import, the application operator causes survey questions to be sent to a (LAMP) server and an email sent to the survey taker that includes a URL with a key to their survey. After the survey-answering period has expired, we download all completed and partially completed surveys to the Microsoft Access database for extensive profile reporting.

Application Figure 1 (flow)
a. Add row to web survey table
b. Use newly inserted row's primary key value to seed VB PRNG
c. Iterate Rnd() to pick out 30 characters from string
d. Update newly inserted row with random string
e. Secure copy MySQL table data to LAMP server
f. Invoke data import PHP script

Application Source Figure 1 (new record)
This is the area where the application failed due to VB's PRNG weakness. The failing statement was the second .Update method when I assigned an rs!Email_ID value. The Email_ID column has a unique index. Am I ever glad I forced uniqueness on that column, since problem analysis is more difficult on the MySQL database.

With rs
                          .AddNew
                              !Source_ID = lngSourceID
                              !Source_Name = strSourcename
                              !Target_ID = Me.cboTarget.Column(0)
                              !Target_Name = Me.cboTarget.Column(2) & " " & _
                                  Me.cboTarget.Column(3)
                              !Survey_Name = Me.cboSurvey.Column(1)
                              !Expire_Date = Format(CDate(Me.txtSurveyExpireDate), _
                                  "YYYYMMDD")
                          .Update
                      End With
                      rs.Bookmark = rs.LastModified
                      rs.Edit
                          rs!Email_ID = EmailID_For_SID(rs!S_ID)
                      rs.Update
                      
                      Export_Survey_For_Person rs!S_ID

Select all Open in new window

Application Source Figure 2 (generate random string)
Using the parameter (=rowID) as the seed for a new PRNG sequence, build a string of random characters.

Public Function EmailID_For_SID(parmS_ID) As String
                          Dim strTemp As String
                          Dim intLoop As Integer
                          Dim intCharPosn As Integer
                          Dim strCharBase As String
                          strCharBase = "01234ABCDEFGIJKLMNOPQRSTUVWXYZ" & _
                              "abcdefghijklmnopqrstuvwxyz56789"
                          strTemp = String(30, "A")
                      
                          Rnd -1               'resets the random seed
                          Randomize (parmS_ID) 'initialize the seed
                      
                          For intLoop = 1 To Len(strTemp)
                              Mid$(strTemp, intLoop, 1) = _
                                  Mid$(strCharBase, Rnd() * Len(strCharBase) + 1, 1)
                          Next
                      
                          EmailID_For_SID = strTemp
                      End Function

Select all Open in new window

For security reasons, we didn't want to identify the surveys with a long integer value, since a mistyped number would result in the ability to see someone else's survey answers. This is an especially sensitive issue since these executives were often rating their co-workers and senior executives. Since this data has real value to the clients and to the industry, allowing competitors to see or change this data would be very bad for my client. We wrote the PHP application to show an application based on a thirty (30) length string identifier comprised of upper and lower case letters and digit characters.

I seeded the VB PRNG with the (autoincrement) key value of the web-survey table row I'd just inserted and iterated 30 times, picking characters out of an alphabet string. To add to the seed variability, I changed the table default from 'sequential' to 'random' for the autoincrement field. This increased the range of primary key values from 1 -> 2.14 billion to -2.14 billion -> 2.14 billion. When two different rows' autoincrement keys resulted in identical 30 character 'random' strings, the application threw up its hands as I coded it. Identical random strings weren't supposed to happen... or so I thought. What I discovered would make the Lost In Space robot wave his arms and yell "Danger Will Robinson! Collision imminent!"

PRNGs - An Introduction

To fully understand and develop a non-patched work-around for this problem, I needed to better understand PRNGs and how the VB PRNG features work. Although my patch would reduce the chance that a collision would prevent a survey from being generated, I didn't want to be called from a frantic user needing an immediate fix because the patch had failed. I learned three important things in my research about PRNGs:

Where Are PRNGs Used?
The three places you will likely see PRNGs used are Security, Statistics, and Games. Although PRNG applications are not central to this article, it may help you determine likely places to look in your VB code for PRNGs.

PRNG Security Uses
One of the most secure methods of encrypting data is the one-time-pad. If the sender and receiver both use the same random number sequence (same size as the message) to encode their message, then anyone intercepting the message has no clue on how to decrypt the message unless they've also learned of the random number sequence. The problem with this method is the need to use a different random number sequence for each message. PRNGs are also used to generate random data when wiping a hard drive of sensitive data. These two examples only begin to enumerate the uses of PRNGs with security. This is a big list.

PRNG Statistic Uses
The most frequent PRNG use in statistics is with Monte Carlo simulations. However, there are other related scientific fields of study, such as genetic algorithms where PRNGs have been used to select breeding pairs and methods. In this case, I'm using Statistic in an overly broad sense.

PRNG Games Uses
Some of the earliest applications we write as beginner programmers are games. PRNGs are used to select tic-tac-toe squares, shuffle cards, and roll dice. Casinos rely on the PRNGs in their electronic gaming equipment. If you don't think PRNG behavior makes a difference, consider the producers of the TV game show, Press Your Luck.

PRNG Resources For Your Own Study

VB PRNG Language Features

There are two PRNG-related functions/statements in the VB language, Rnd() and Randomize.

The Rnd() Function
The Rnd() function gives sequences of single precision floating point numbers, where 0 <= Rnd() < 1. Rnd() can be use as a function or can appear on a line all by itself, in the form of a VB statement, without any compilation problems. Since Rnd() is a function, the compiler will discard the returned value if it is used as a statement. For the purposes of consistency, Rnd() will be the notation used in this article. You might see the alternate form, Rnd, used in production code and sample/example code.

The Randomize Statement
The Randomize statement initializes the Rnd() sequence with a new seed. The default seed value is the current Timer() function value (see below). When using the Randomize statement to reseed the sequence, you need to invoke Rnd -1 prior to the Randomize statement. Although I've used "Rnd -1" in my examples and documentation of seed resetting, the -1 can be any negative value.

A detailed KB article about resetting the seed is at http://support.microsoft.com/default.aspx?scid=kb;en-us;120587

The Timer() Function
The Timer() function returns values between 0.00 and 86400.00. These are the seconds of the day, starting at midnight with a resolution of 1/100th of a second. Doing the math, there are 8.64 million unique numeric Timer() values.

What Microsoft Tells You

We are at the mercy of Microsoft when it comes to documentation. I think they should be thanked for the overall quality of their help files and product documentation. So this is what Microsoft had to say about the Randomize seed and the use of VB's PRNG features.

VB Classic Randomize Help
From the online help (both VB help file and msdn.microsoft.com), the Randomize statement seed value can be "Any Numeric Expression". That should allow you to supply a HUGE range of seed values.

VB.NET PRNG Help (Rnd and Randomize)
There is new verbiage accompanying VB.NET documentation associated with the Rnd() function and Randomize statement.


Although I didn't consider what I was doing cryptography, I was obscuring the value of the survey key by expressing the row ID as a long string of 'random' characters.

Other than the Security Note, the online documentation about the Randomize statement remains the same as the VB 3 online help: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vblr7/html/vastmrandomize.asp

What Actually Happens

This is an under-the-covers explanation of how the VB PRNG actually works. The VB PRNG is a linear congruential generator, meaning that successive values are mathematically derived from the prior value in a formula of the form:

Rk+1 = (Rk* L + M) Mod N

Rnd() Internals

The Rnd() uses the following formula:

x1 = (x0 * a + c) MOD (2^24)

where a = 1140671485 and c = 12820163

The default value for x0 is 327680 (&h50000). This is why you get repeatable sequences when you do not use the Randomize statement prior to the first Rnd() function invocation.

Please notice the 2^24 division. This results in a 'period' for the PRNG, where a sequence of values from the Rnd() function will repeat after 16.77M invocations. In talks with my local crypto expert, we both agreed that this is a serious flaw in the PRNG. Since I was only using the first 30 items of each sequence, I wasn't too concerned about this.

To get the 0 <= Rnd() < 1 values, the x1 value is divided by 2^24 before it is returned to your Visual Basic program code. It is then up to the VB programmer to transform the returned values into a scale and range that is appropriate for the application.

Randomize Internals
After considerable research, I discovered that there is a weakness in the randomize statement that is much more severe than that in the Rnd() function. Here's what happens inside the Randomize statement:

1. The supplied seed value is cast into a Single datatype. This is understandable, since the Rnd() function returns a Single datatype.
Note: the Timer() value returns a Single datatype which does not require any datatype conversion.

2. The Single (datatype) seed is 'moshed' into 2-byte seed (TwoByteSeed) value with the following XOR operations:

TwoByteSeed = [byte1 XOR byte3] [byte2 XOR byte4]

Select all Open in new window

3. One additional XOR operation is performed on these two bytes, depending on the sign of the originally supplied seed as the following code snippet describes:

If originalseed < 0 Then
                          TwoByteSeed = TwoByteSeed XOR &h06C0
                      Else 
                          TwoByteSeed = TwoByteSeed XOR &h0240
                      End If

Select all Open in new window

The seed value produced by the Randomize statement is a Single (floating point) datatype, but only two of the bytes are used as the seed.

VB PRNG Internals References

What This Means to Developers

This is a summary of the weaknesses and problems with the VB PRNG.

Using the Timer() value, the default seed for the Randomize statement, doesn't help as I've illustrated in the following section. Using a (guaranteed) unique seed value doesn't help as I experience in my application.

To help you estimate your chance of collision, take the total number of supplied seed values and divide by 64K. This would be an approximation of the average collisions. A 'collision' is the occurrence of a repeated sequence.

Timer Seed Collision Stats
These figures are the result of generating the actual seed values based on possible Timer() function values and counting identical values produced by the Randomize statement.

What Can/Should We Do?

Duplicate VB PRNG sequences WILL happen in our applications. Does anyone reading this article doubt it?

So what should you do and what can you do to protect yourself?

What's Ahead? (Next Article)

In a future article, I will present details of minor tweaking, such as

I will also cover details about replacing Rnd() and Randomize (major tweaks), such as

Prior Publication Notice

This article was original published at:
http://www.15seconds.com/issue/051110.htm

Unfortunately, 15seconds.com is no longer a web site so that URL will not navigate you to the article.  I did find a copy of the article on the great Internet Archive (the Wayback Machine) having this URL:
http://web.archive.org/web/20051124213610/http://www.15seconds.com/issue/051110.htm

Since the original article has been URL-referenced widely, I decided to republish it on Experts-Exchange.com to make it easier for people to find.

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
If you liked this article and want to see more from this author,  please click here.

If you found this article helpful, please click the Yes button near the:

      Was this article helpful?

label that is just below and to the right of this text.   Thanks!
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=