Steve Weldon - Random Numbers Today and Tomorrow

all right for those of you joining us in track five welcome to track five uh we are going to go ahead and get started with their next talk we have step Welden who will be uh leading this talk um Stephen is currently uh an instructor at August University he instructs in the school of computer and cyber sciences and he also works at Savannah River National Labs um so you guys will get a chance to win a couple prizes so do pay attention make some notes you'll be tested at the end you at the anniversary after all but we will have a couple prizes to give away so let's go ahead and give Stephen A warm round of

welcome Hey thank you all very much I Steve welen and it's my pleasure to present here today at besides zxa and you know just to start off um everybody's tracking on the Zero XA right I just want to make sure you know this is our 10th anniversary but we'll also lead with did y'all ever hear why six was afraid of seven in Canadian heximal because 789 a all right so there we go so we're going to talk you know we talk a bit about just a random topic uh random numbers try to have a good time but let's start off with the important stuff tonight 10:59 p.m. 1.4 billion dollar are on the line if

you go for the cash payout 64 $14 million I mean this is this is good stuff so you know just to kind of recap what's taking place with Powerball uh y'all have probably seen how the game is played you know when they do the drawing there's there's two fish bowls and then in one Fishbowl uh you get a bunch of white balls dumped in there 69 of them five numbers are selected from the white balls and then there's the Power Ball fish bowl and 26 balls are dumped into that one and one of them is picked from that and that's how it goes so at 10:59 p.m. uh eastern time tonight you know somebody down in Tallahasse is going to

tell me that uh you know my uh my retirement plan is set and that I don't have to rely on my speaker fees for besides Augusta to kind of make K me and yes whoever wins on the all chance that it's not me you know what's going to happen is they're going to submit that twom minute notice to their employer peace out I know it's 11:00 at night but here we go so let's look at this a little bit more just to kind of dig in uh on the right you kind of see the chart about what the odds are with Powerball uh so we look at this chart and we see man we're shooting for that

one in 292 million chance that we're going to match all five white balls and the Power Ball and that would be awesome now but then we see those those are big odds if we just match all five white balls where hey one chance in 12 million this is this is progressing nicely this is trending nicely you know then there's all the way down to the $4 ones that we match say a white ball and the power ball or just the Power Ball itself and we made four bucks so what does Powerball ticket cost it cost two bucks we've doubled our money this ain't bad but we see how the odds work here and we see that the overall chance the overall

odds of winning anything any sort of prize is about 1 and 25 and I draw your attention that one in 25 I'm going to talk about uh that in in just a little bit in a different sort of scenario but let's also note that this chart on the right with all those odds that represents 4.0 2% of all the potential numbers in Powerball 4.02% so where are the big numbers they're on the left side of this that there's absolutely no matches you know 65% of the space one white ball no power ball 27% two white balls no Power Ball 3 and 1 12% so we get almost 96% of the possible results combined is the big zip not nothing it

back to work on Monday but so why do we do this why is this so intriguing to us it's because this is the incredibly High payoff for very very low risk and that's what makes Powerball kind of fun and so if we start to look at this and say that Powerball bell curve and this is from powerball's website is we we see the fat part of the bell curve here and we see that 68 Just a Touch over 68% is in that first standard deviation on each side of the mean and then we go out another 13.6 on each side alog together that's about 95% of of where all those numbers uh fall in and again that's the the very

low payoff uh or no payoff really based on what we looked at last time and then we get out on the tail and the tail is where things get fun the tail is what we want is is that we're looking at that big payoff but this is there's some assumptions that are going into this we're assuming a a a standard deviation a gaussian random distribution across all the potential numbers that are in the space that draw those balls that are in that that Fishbowl that this is this is fair it is uh random um and so that kind of leads us in to where we're heading with this discussion so when we play Power all we

are really trusting that that is a fair selection process and we can trust it but what if it's not what if there was a scandal that for some reason when that selection is made Monday Wednesday and Saturday night there was something that was skewing the numbers well if they skew the numbers in my favor so be it uh but if those ain't my numbers I'm a little upset so yeah there could be a problem now you see this this uh this bullet here what if nobody from Augusta wins there's a little bit of a story behind that over 20 years ago uh if you remember the Augusta Entertainment Weekly would come out and say here

here's what to do in austa this weekend and had Rants and Raves and nobody cares about the Raves because they said hey everything was awesome who cares the rants were fun uh when people were just complaining and I read one again this is over 20 years ago and they said the Georgia Lottery is unfair because not enough people from austa win okay that really caused me to think a lot more than I should have thought about that you about that rant but that begs the question what does Randomness really mean what does fair really mean can we Define it and then also what we'll see as we progress is is there such a thing as random enough and how do we Define

random enough enough for particular circumstances so if you start to look at say random number Generations or Randomness you you'll see that the definitions are kind of all over the place there's really smart people who have struggled with how to define random uh so it tends to be it's it's very irregular uh there's no pattern or no discernable pattern or it's unpredictable and it comes down into the probabilities and pure luck or just a coinky dink it's a coin a coincidence that this happened okay uh so maybe that's the way we look at Randomness and then the infinite monkey thing is just a lot of fun if you take infinite monkeys and you put them at a keyboard and they

start banging away you know the overwhelming majority of the stuff that those infinite monkeys are going to produce it's just pure gibberish but when we look at the probabilities although it's a very small probability way out on the tail those infinite monkeys eventually will produce the complete works of Shakespeare now mathematically you know that yes you can you can get there but wo you know are are we really going to wait for that uh probably not so this is uh Robert cabu he's got one of the greatest quotes about random numbers ever generation of random numbers is too important to be left a chance he actually had this as a title of a paper he did in the early 50s

brilliant guy Oakridge National Lab uh he did a lot of simulations did a lot of work in areas that needed good random numbers brilliant guy he was an incredible chess player he's a Tennessee state champion chess player for years and years and years but this is often thrown out when we talk about random numbers is to to kind of frame the argument of what we're really looking for but why are we interested in random numbers well from a cryptographic standpoint we'd like to create strong keys and strong keys are generally key pended uh are linked to having good random numbers to see that algorithm to create keys and because we're talking about the cryptographic process let's

not forget the Crypt analytic process when somebody is trying to bust that and if we're using bad random numbers or we're messing up the implement ation of our algorithms that make that puts us at risk we've already talked a little bit about simulations but anybody that's in modeling and simulations and they want to do Monte Carlos situations you know they're trying to do a lot of different variations of variables to see what the potentials are and running over and over and over Computing just makes Mighty Car Mighty Car simulations the coolest thing in the world and so we're looking at some of those items that can be the inner arrivals the service times service probabilities that is a Wonder ful place

for random numbers and then certainly in the Computing world there's not enough slides that we could put up in 30 minutes that we talk about how we use random numbers in all areas of computing so I just got a few of them here uh carrier sense multiple access back off algorithms whether it's in Collision detection which was super important in the early days of Ethernet or in csma collision avoidance uh that is used in Wi-Fi and lots of of multiple access protocols they rely on random numbers for those back off algorithms um if you're interested in blockchain you know proof of work you've seen a lot of areas where random numbers are used as part of that and and I just

I threw out the burp site sequence or just because it's kind of fun but you know if we're testing the um the randomness of tokens session tokens uh that are created for instance then uh that is one of the things that sequencer looks for are these tokens that are being generated random or is there some discernable pattern that could be used to either make them vulnerable the system vulnerable or to potentially attack it and of course lotteries once again I think that to trust and to have faith in the Powerball system we need to have a good feel for how it is random but we also know that not all random numbers are created equally we like to

think hey we generated a a a random number and it's truly random often times in Computing that is not the case uh so but are can we get Rand truly random numbers oh yeah sure and generally what we're doing is we're measuring that physical process and those measurements are being used to Generate random numbers and we'll talk about that a little bit more as we get into Quantum but really for our purposes we're more in tune with the pseudo random number number generators and so what we're looking at there they are algorithmically generated which makes really nice for us because we can generate a whole bunch of them really fast but we also know that

they're not really random not truly random but we often look for the characteristics of that generator that is going to mimic the statistics of a random distribution equally distributed across the entire space uh and so we we we'll look at at some of the tests that can be done with that and then if you're interested in cryptography uh then we look at the cryptographically secure random numbers and this is really where we get into good old Kirk off's uh principle uh from way back when and you remember that he famously said you assume your enemy has access to the algorithm to the method that you are using to secure your Communications so it's not your algorithm that makes the

difference it is the key and how do we make keys we make keys uh through random numbers that is the secret sauce I don't think the secret sauce thing is a direct quote from kirkoff uh but you know who knows um so in when we do this when we're looking at cryptographically secure random numbers we have additional requirements of those numbers so for instance if I have access to num random numbers that have already been generated with such a system that I'm not able to predict the next number with any certainty greater than 50% so I think about I have a whole string of zeros and ones what's the next number if I can consistently go over 50% then you know

we might not want to use this particular algorithm the opposite also true is if I have access to numbers that are being generated now I should not be able to backtrack in time and recreate the numbers that have been generated in the past that's bad so for a cryptographically secure algorithm we're looking for this forward and backward Security in both directions and from an algorithmic perspective really 10 minutes we are also thinking that um you know we're we're looking at unpredictability in polinomial time if this is outside polinomial time you want to take the the entirity of the remainder of the universe to to to crack it by AOS it's your world uh but you

know polinomial time making it efficient to do so very quick on a toy example of this where you can see some of the issues with random number common random number generators in C if you're doing rock paper scissors lizard Spock very simple all help incast uh Big Bang Theory uh kind of shout out is you you set it up so that you're generating random numbers for both the player and for the computer using the random Cass class and the the code is very simple you instantiate an object from from the class and then you generate a random number quote unquote random number uh for each of the players so you see how uh the next method is called with the

arguments of zero and five so this is inclusive exclusive behavior on this so it's going to generate a number between zero and four because excuse me we have enumerated rock paper scissors lizards Bo in this particular example in order to do this but you do this in uh just a random class and you start to see there's a lot of ties now are ties possible when you're doing rock paper scissors lizard spot and outside of the human element where if you saw the Big Bang Theory stuff with when Raj and Sheldon were doing this they always tied because they always did spot and good for you if you can actually do this you get ahead of the Chick-fil-A line um but

we know just the math is super simple is we got one chance in 25 so it shows up again that both players will select the same thing if the numbers are pretty good so when you start to see a whole bunch of ties you know that something ain't right and so maybe you dig into the random class and you start to see how is the algorithm seated is seated from the system clock and so that creates a challenge and if it's going too fast uh the way that the system clock is feeding those times and they're truncated so what do you do to fix it well you put the thread to sleep for a few th000 milliseconds

we've got 5,000 milliseconds here but you can do it for a lot less time and you start to see those inordinate amounts of ties go away and you if you look at this over a thousand 10,000 a Million numbers you will see that it's much more random that it has been in the past and so now we're talking about pseudo random numbers we showed an example where this goes a little sideways this is a great quote from John Von noyman just a brilliant guy living in a state of sin when you generating random numbers in this deterministic state so he's criticized a lot for for this quote but he did it at a time when

he was then going in to say okay when you have to do it when you have to live in a state of sin here's what you do because that's where we are in a lot of areas in Computing and so we just recognize that some random number generators are better than other mercine twister is is quite good for a general purpose pseudo random number from 1997 with maximoto initi mura uh and that period length is based on a mercen prime which is two to the ra to to raised to a power minus one if that results in a prime that's a mercan prime and this has proven very effective especially with large primes when you results in large

primes uh like this mt19937 so when you have a period from the time that the algorithm starts generating numbers until it starts to repeat that is 2 to the 19,99 37 power minus one um then you've got a really long period and that looks like it's good for general purpose sudo random numbers it is a big big number if your numbers start repeating after 2 to the 32 then you've probably got a system that is susceptible uh so that BS the question of what is random enough when we shift over to cryptographically secure random number generators cryptographically secure Pudo random number generators then we have those extra um requirements of the system and some examples of this in Apple products

have used y yo uh in the past using Fortuna now Microsoft's cryptographic API uses the cryp Gen random there is a version of the mercing Twister uh Crypt Mt which use mercing twister as the internals that can be used as a cryptographic secure pseudo random number generator uh so it's good enough for cryptographic applications and then some standards like fips and nist you see right here just got that sub bullet uh about a klept graphic Back Door story here because just

kpogas and the second revision of this n standard there is one algorithm that is not in second version of the standard because it would dealt with elliptic curve cryptography and there was at least reportedly a back door that was put into that by some governmental entity and there was lots of drama around 2015 on this and so that that algorithm was removed from the standard but then there's Quantum everything's about Quantum right we like to talk about Quantum and it turns out that quantum mechanics is a fantastic source of entropy we can get lots of of good Randomness out it so you see lots in the literature about Quantum random number generators whether it's using

radioactive decay which has been around forever so we see that generating random numbers from quantum mechanics Quantum effects is really one of the more mature uh Quantum technologies that are out there and then in this section about noise where you see the shot and the flicker noise in electronic circuits it's really bizarre it's like the current granularity of the C the the electrical current through creating this noise depending on the the frequency of it it's either shot or flicker but it's really kind of weird and it's hard to determine is this thermal or is it quantum and so you see some reflections of it but other folks just kind of dismiss it one of the big papers that I

used in in the preparation for this they just kind of washed over but Optical is where a lot of this stuff is used when we're doing these particular things like um states of light and we're looking at time of arrival Photon counting vacuum fluctuations those are just cool names but the the optical aspect of quantum uh effects is really really promising uh for Quantum random number generation and it's it's rather affordable too uh so it is really good to look at now with Quantum it's not just a free lunch uh there's a lot of overhead that's associated with this say in the photon detection there is a period of time where the system has to be reset in

order to then detect the next Photon that's coming long so system has to be careful excuse me about that reset value but it can just take in as many photons as many of these detections as possible and then do some Cleanup in order to generate the numbers that we have super super promising uh with even in the realm of using untrusted Hardware to generate trusted numbers I mean that's fantastic and with the protocols that are are there it makes it very um very affordable and very doable and I you know I just got to say I I just just crossed my mind I feel so bad about schinger did y'all hear what happened to him schinger got pulled over for

speeding and the officer part of the stop said hey you mind if I check your car and schroer said yes so officer's looking through his car and then officer came from the Trump and said Hey sir I don't know if you knew this but you've got a dead cat in a box in your Trump and schroer says well I do now so when we generate all these random numbers regardless of whether they're pseudo random they're true random cryptographically secure we often want to test those and so there's a lot of statistical Suites nist has a fantastic statistical test Suite uh written in anzie C uh there's there's also products like test u01 Die Hard Die Harder to but

really what you're looking at regardless of The Suite that you're using is a number of statistical tests to be able to determine how well do these numbers stack up and it's interesting because some some of these that we're very familiar with do great on certain tests and fail other tests uh regardless of whether we're talking about F random or we're talking about even Quantum random numbers but it is certainly felt that Quantum random number numbers that are quantum randomly generated uh are going to be certainly performed at least as good in these statistical test because we want a good feel for all those characteristics of these numbers and how they are used so if you're looking at

well how do we make the choice because there's a lot of environments in Computing that we could go so you just kind of have to we just kind of have to look at what our goal is or if we're falling in on a system you know how was the system designed are we looking at true numbers so pseudo general purpose pseudo random numbers or cryptographically secure uh random numbers and um and then we look at the environment that we in what hardware and software we are how is it performing with statistical analysis do we have any memory issues do we have energy consumption and so if you look at this in particular environments like here I'm

putting some uh info in from a paper on using uh Quantum random generators in constrained iot environments and we know that iot environments are very constrainted you see some recommendations hey let's use can as a general purpose non- cryptographic pseudo random number generator and let's use Shaw 52 spring as the cspring so very specific recommendations given that environment but in general these particular authors said hey if you're going to do general purpose stuff let's let's let's separate general purpose from cryptographically secure let's prefer software over hardware for pseudo random numbers and then then we can certainly use Hardware uh like in thermal noise uh electronic circuit noise uh to add additional entropy to what we're feeding in to our

cryptographic algorithms but if you look at this in constrained iot then it might be completely different if another application that you are Lo are using and so some of those that you've seen in previous years and going into the future lots of us well how can we get entropy how can we Randomness that's coming in from other sources say Get it Over the web and then use it in our systems and nist has the project for entropy as a service uh which is nice because it it it uses Quantum entropy and you can do secure time with it as well but what it's doing it's feeding entropy in and then you can use that entropy in order to feed the

algorithms that you're using locally that's generally the way uh the N project is there's hot nits which is used for many years in radioactive decay they've kind of gotten away from that and if you still want to use it they do an impel CPU based uh effort but uh then commsar uh is interesting because they offer some products for uh cryptographically secure but also cryptographic protocols that are used in the iot world it's it's really interesting to see what they are offering and then they say oh we we also have a product that is post Quantum uh it's going to be really fantastic which is really interesting because then you get into super big science and you have

to say well the postquantum capabilities where do you stand on Quantum non-locality which really goes to Einstein's special theory of relativity and the ability to communicate faster than the speed of light so this is pretty wild stuff this is what sci-fi movies are all made out it's fantastic so that's really what I wanted to do uh as we get ready to break for lunch random numbers are really interesting and they're super important in the world of computing so regardless of where we're developing systems or we are defending systems or we're trying to uh to attack systems one of the things that we can look at is what algorithms are being used and how those numbers that

are feeding those algorithms are generated gives us Keen insights into the security and the reliability uh the feasibility of the system good luck and Powerball tonight all right right right thank Sten he'll be available for a couple minutes to answer your Powerball questions uh but we do have a couple gifts to give away raise your hand if you don't say it out loud if you know any of the quotes the authors of any of the quotes that he put on the board you sir in the Hawaiian shirt there uh John Von Newman living in sin is it correct would you pass that back and we also have a book that we're giving away Stephen do you have a question you like

ask yes the mercing Twister that we called out as being a very common very uh uh uh it it's used what was the meren Prime value that was given it's Mt something something something oh me well this lady had her hand up first did I was going to I don't remember the equation I just remember that the period blank that's called the mercy year Prime but he probably okay two to the 19937 one oh fail I got it I got it congratulations than you all great talk steeve