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'