My favourite line in the whole article was about the way he alerted the lottery board:
"The package was sent at 10 am. Two hours later, he received a call from Zufelt. Srivastava had correctly predicted 19 out of the 20 tickets. The next day, the tic-tac-toe game was pulled from stores."
I know that we're supposed to be fascinated by the statistical work done cracking the code, but my real sympathy is for the head of security that received that package. How do you react in such a situation?
As an aside, the statistician seems really cool too - it's a very forthright interview and the article's much better than I expected. Both the statistician and the author seem to be very surprised by the lack of concern shown for the apparent evidence of security breaches. This, of course, has a direct analogue with the way large multi-nationals treat computer security. I was only surprised to get to the end of the article and not find that the statistician had been threatened with prosecution or similar.
"I found it hard to believe that only this tic-tac-toe game was flawed. What were the odds that I just happened to stumble upon the only breakable game the very first time I played the lottery? Of course, I knew it was possible that every other scratch game was totally secure. I just didn’t think it was very likely."
The cynical bastard in me thinks that There Is A Chance To Beat The Lottery is the best headline a lottery PR team could ever hope for. It is like card counting in Vegas: a problem if and only if you can do it well.
Except "counting the cards" in the lottery version is trivial compared to doing it for real. Like the article said, he taught it to his eight year old daughter.
Right: that is the perfect target for the math abilities of the average lottery player. Do a controlled loss on one game, receive PR bonanza and watch as millions of lottery winners learn how to "outsmart" the lottery, introduce Game 2 with the same mechanic and cards which are countable in a fashion which is not exploitable, and watch as ticket sales soar.
This would be evil, of course, but if you're running a lottery your entire business is stealing money from poor people.
or people well assume it's an inside job from the start. That the majority of winning tickets are snatched up before they ever show up at the gas station.
buy a corner store or gas station with other clean(er) money, and become a lottery ticket merchant. place winners on your customers to keep people coming back.
the hunch is that it will pay out, but not how much. what if this woman in texas had 5 marked "winners" from a dirty merchant "placed" on her when she bought it to avoid a misplaced accusation?
I'm very surprised that he wasn't arrested, prosecuted, served with an injunction not to talk about this and have all his computers confiscated.
The lottery commission in BC is on it's Nth major criminal investigation - but the trick here seems to be the simpler method of the shop stealing winning tickets from customers.
Summary: If you are smart enough to crack the scratch off lottery you already make enough income that cracking the scratch off lottery is not justifiable.
Or you could write a Beat The Lottery iPhone app. (OCR plus counting... I somehow think they can make it work.) There are a variety of business models available at that point.
To make matters worse, my understanding is that when the state receives money from the lottery for the schools, that money does in fact go to the schools... and then an equivalent amount of money comes out of the school's budget and goes into the state's general budget.
So, for example: if the school budget for the year is $5 million, and lottery brings in $1 million for the school, the school doesn't get $6 million the way a lot of people seem to think. The school gets $1 million from the lottery and the state only has to pay $4 million out of the general budget.
I find irony in the fact that if the populous were better educated, the state would get less money.
While not strictly true (a better educated populous would probably earn more, and give more taxes to the state, among other reasons), I find the idea on this small scale amusing.
I find it strange that they don't use some true random source in generating the tickets. I'm also surprised the article finds this obvious.
"Of course, it would be really nice if the computer could just spit out random digits. But that’s not possible, since the lottery corporation needs to control the number of winning tickets"
Surely the lottery could quantify uncertainties and set up a system where the probability of them losing money would be arbitrarily small. Interesting interview, btw.
It sounds like ticket design is the problem; an algorithm is needed that:
- produces a set of bingo cards or tic-tac-toe boards such that only one board per card is a winner
- produces cards that contain a number of almost winners
Simply randomly assigning numbers wouldn't work, and it seems the method they've developed for building "fun to play" cards contains weaknesses against statistical analysis.
Hmm... now I'll be stuck mulling over a good algorithm for this all day...
The solution is straightforward: generate truly random boards, evaluate them, and then use the set that fits your payout profile. The problem is that these boards will lack the enticing hooks that keep folks coming back. The complete solution is to also discard boards that are not enticing enough. The result will have fewer artificial patterns like the ones used in the article to determine winners.
That procedure is vulnerable to the same issues mentioned in the article.
Let's say you design a game that has outcomes Lose, Near-Miss, Win, and Invalid (tickets that must be suppressed, e.g. multiple wins). Then, imagine a rare, salient pattern, like 3 singletons in a baited-hook row. That might be an extremely rare occurrence in the overall lot of random boards, but it might still occur disproportionately in, or in the vast majority of, Win boards and Invalid boards.
If you then choose the Lose, Near-Miss, and Win cards randomly, in the desired proportion, from your truly randomly generated set, then the pattern will be statistically correlated -- potentially strongly -- with the Win cards. That's what the article describes.
A single confusing sentence in the article seems to have gotten a lot of people (including me, at first) thinking this had something to do with PRNG; rather, apalmblad's claim that this is a game design issue seems right.
Only if the "game design" purposely used a limited pool of numbers for the visible and hidden boards. If there was no guarantee that a number would appear 1.9 times, then seeing singleton numbers wouldn't be a predictor.
My guess is that the restricted number pool was used as a means of easily mapping a number (the number on the back of the card) onto a playing board. Anyone interested in the why and how of this should look at The Wizard of Odds[1]. If the number on the card was used to seed a PRNG which then produced a lot more data, there could be a more sophisticated board generator that doesn't need to take such compromising shortcuts.
So in a sense, the culprit is game design in that rules were created to allow for certain percentages of Loses, Near Wins, and Wins. But there is no reason to mix output control into game design. My suggestion is to make the game rules with no regard to controlling output. Instead, evaluate the generated boards and keep/drop them to control the output.
If there was no guarantee that a number would appear 1.9 times, then seeing singleton numbers wouldn't be a predictor.
Let's say there's no such demand, and the boards are generated truly randomly and neutrally. If visible-quality X is disproportionately correlated with invisible-quality "Win" then the game is already flawed; this may emerge naturally from the Win conditions and from the game design decision of what is shown in the baited-hook. If the output is controlled post-generation to increase the proportion of Win cards and Near-Win cards vs. Lose and Invalid cards, then the statistical correlation may be greatly increased.
Simplified example: Scratcher with two numbers 0-4: one bait, one hidden, pays if sum is 5 or 6. If everything is fair and truly random, the odds of winning are, 0 showing: 0%, 1 showing: 20%, 2-4 showing: 40%. Already a bad game, but now the game designers want to eliminate cards with sums of 7 or 8 because this confuses people, (not minding that they're changing overall odds of winning), so they block those Invalid cards from shipping without blocking anything else. That gives:
0 1 2 3 4
0 - - - - -
1 - - - - W
2 - - - W W
3 - - W W I
4 - W W I I
The new odds of a given ticket, given the visible number, are: 0: 0%, 1: 20%, 2: 40%, 3: 50%, 4: 67%. The point here is that now a 4-showing-card is >3x as good as a 1-showing card, when it used to be only 2x as good, and it might now have positive expected return.
OK, database geek hat on here. It's not too hard to pregenerate a set of every possible ticket combination, just lots of cross joining of numbers tables and a bit of coding of the play rules. Add in the payout rules and you can produce a total set of all possible cards along with the payout for each given card.
From this set, we can select exactly the number and balance of paying and non-paying cards we want, chosen pseudorandomly from the set of possible cards. Output that set and sort that pseudorandomly, then send to the printers. You've got a (pseudo) random selection of cards with an absolutely controlled payout pattern.
The downside, and what seems to be the critical problem for the suppliers, is that I suspect you'd have less 'near miss' cards this way to entice players. But it's absolutely possible to ensure that you have a defined payout pattern while also giving random ticket distribution.
I don't think you've done the math yet on how many possible ticket combinations there are. I have more reason than most people to spend time thinking about bingo math. Get out a piece of paper and run some calculations: enumerating the whole solution space is not feasible.
Anyhow, the real solution is easier: checking a bingo card or lottery ticket for any feature you want is, essentially, O(1). Generating a lottery ticket is O(1). Generate billions, sort into piles, choose millions from piles in proper proportions, randomize order, done.
This still won't help you if you print sufficient information on the ticket to reverse engineer whether it won or not without actually purchasing it, of course.
I'm a Brit (and not a lottery player) so not fully familiar with US state scratchcard lottery game mechanics :-) The longest odds straight lottery over here is 75m to 1 which is definitely enumerable, but if you say these cards get into the billions and would crash my server then I'll believe you! Agreed that you can still generate a controlled prize distribution with random tickets generated individually rather than pregenerating all combinations - it's a bit more fiddly but perfectly doable.
All this I agree won't help if your card design is as poor as the original article was, but to address the complaint of the poster before me it's perfectly possible to randomly generate tickets while controlling the number of winning tickets - you just have to have a screening function which prevents more than your controlled number of winners making it through.
I've heard of this technique used for games of chance in vegas where they need to tightly control the outcomes both so they don't lose money but also to satisfy the reporting requirements for the regulatory commissions.
They probably have to specify exactly what percentage of income is given out in winnings. Not to protect the lottery company, but to protect lottery buyers.
Your comment reminds me of the great article that was on here some time ago about the guy who used a PDA and barcode scanner to search book stores for cheap books he could sell on Amazon for a profit:
Why do they need a non random code to generate these? If they want to guarantee the number of winners, they can just ensure that they only release so many winners. This would require them "solving" all the tickets they were to release and holding/deleting/regenerating the ticket if they have enough winners already.
This may not be the most efficient system but it guarantees it isn't crackable with a couple of caveats:
1. They weren't always releasing a winner at a fixed time - i.e. they had to have x win per week, and they released a winner at regular intervals to guarantee separation. You don't want all the winners for a month produced in the first hour. Although this would be random and should be a possibility.
2. The random number generator was actually random.
It seems that a large part of the problem (aside from flawed algorithm) is that they allow people to pick the tickets they want to purchase. If they required people to buy the tickets in order they're dispensed from the roll it would bring the abuse down dramatically.
Even if you were able to crack the code you'd have to wait for others to buy the losers before a winning ticket would show up. The flaw in this would be if the store selling the tickets was be in on the scam. They'd be able to sell a bunch of losers and pull any winners as soon as it was their turn to dispense. But as with most crimes, the more people involved in it, the harder it is to keep quiet about it and pull it off.
I wouldn't have been surprised if they had known about the 'flaw', but didn't mind it, because, as Srivastava said "it wasn't worth the time to abuse the flaw". In similar vein, I once randomly generated 2 million out of 40 million possible codes. Consumers would buy products, obtain a code and it would allow them to 'buy one, get one free' for some other product. The code being short and without the usual mixup candidates (I, 1, O, 0, etc.) was much more important than people 'cracking' the system. Even at half the price, the other product still sold at a profit and nobody saw room for mass purchase/reselling.
Of course, later in the article it appeared that people were abusing cracks in the system and reaping the benefits, so it doesn't apply to this case. I just wanted to note that sometimes business concerns trump all actually interesting parts of a problem :/
It wasn't economical for the statistician, since he was making more than he could possibly make doing this. It would likely be economical for many other people, however.
He said he could make $600/day doing this. Even if you only do this 5 days a week and give yourself 2 weeks of vacation, you still end up making $150,000/yr ($600/day * 50 weeks/yr * 5 days/week). That's well above the national average for both the US and Canada.
Another key advantage is tax arbitrage. If you can make $800/day, that's because you have a certain skill set, you can't send a random college student in your place to collect your earnings for one month and pay almost no taxes. You have to pay your taxes on one $150k income.
With progressive taxation, if you get 12 students to redeem 1/12th of your winnings (for say 5%), you're paying taxes at the lowest level (likely even 0%) rather than the 35+% you would be if you had to claim 150k on a single tax return.
Great article, though, I take issue with this tangent:
"James “Whitey” Bulger, a notorious South Boston mob boss currently on the FBI’s 10 Most Wanted Fugitives list—he’s thought to be the inspiration for the Frank Costello character in The Departed"
The inspiration for that character is the original movie, Infernal Affairs, which The Departed is a remake of. They may have bleneded some features of Bulger into that character, but that doesn't make him the inspiration.
I wish the article had talked about the legality of doing this. Assuming I'm not doing this to launder money and that I report all my earnings, is this legal?
I think so. Obviously, the lottery isn't happy if people actually figure out how to break it; but there are quite a few people who think "7 is lucky", and I can't figure out a good way to separate the actual winners from people who only think they are winners. And lotteries make their money from the latter...
Not a lawyer, but I would be very surprised if the law that creates and regulates the lottery doesn't include a clause to make buying tickets by an algorithm illegal or something like it.
Why? The law says that you can buy tickets, and return unused ones. So just buy a bunch, scratch the winning ones, and return the rest.
There's no law which says that "if you can figure out how the lottery works, it is illegal". Their recourse is to only pull the lottery and discontinue it; they can't accuse you of fraud if you somehow figured out how to pick the right tickets.
Can someone describe the statistical analysis that would be required to discover something like this? Is it along the lines of guessing different parts of an algorithm till you find something that agrees with the data (IE He'd have to guess that only "singletons" could form winning entries and go from there)? Or, are there some more general approaches here to draw out correlations between the structure of visible numbers and any hidden structure?
More generally, other than saying "statistics," what specific fields of math are applicable to a problem like this? I'd guess there's some relation here with cryptographic attacks and attacks against pseudo random generators, but what specifically would one study to understand these types of problems?
My guess is the following.
Lets say that the numbers in the game are in the range [1..N]. Lets further assume that there are M slots (or squares where numbers are placed). Suppose M is about 3*N.
So, on average, you'd expect each number to occur 3 times.
If you see that number occur only once in the (visible) column on the right, then you are pretty sure that it'll occur at least once or twice in the (hidden) column on the left. So if you see 3 numbers in a row (or column) that each occur only once in the right hand side, then you can be fairly certain that they'll occur at least once in the left side; so you're pretty sure to win the prize.
All you need is some basic knowledge of statistics, uniform distribution, etc. I don't see a need for high-falutin' cryptographic analysis and higher order math.
If you're dealing with online stuff, then some knowledge of PRNGs can help. I remember (a long time ago) hearing about some online poker algorithm which was just calling rand(), and had been seeded with unix time. That leaves a really small number of possibilities to try, and you can reconstruct the stream of random numbers it would generate.
That makes sense, but theres still the problem that, even if you have 3 in a row that you think have a higher probability of occurring in the hidden part, they can still be X or O, not necessarily winning. Maybe theres a statistical edge in knowing that, but I doubt that would give you an edge of 90%.
Also, that seems to indicate the issue is due to the overall structure of the problem of choosing numbers for a game like this, while I got the sense from the article that the problem was more due to the algorithm the company used to control winners and losers (maybe I'm wrong on that). If it is due to how the company controls wins in some way, I could see how observing 3 in a row of singles more often than expected by a random distribution (whatever the distribution is for choice of number and choice of spot on the board) is a giveaway to some nonrandomness introduced by their algorithm. But if you were to approach it by finding divergences from this distribution, wouldn't you need a lot of tickets before you could infer this?
In any case - any guess on the expected number of tickets you'd have to have to discover a flaw like this?
I excitedly went to the Virginia lottery website, thinking maybe I could find a game or two possibly vulnerable to something like this and then buy a few tickets for the fun of seeing if this can still be done...
But manufacturers appear to have dealt with this by getting rid of "baited hooks"--every number on a card is under a surface that has to be scratched off.
I guess they lose the allure of letting people say "I want to buy a card with lots of 7s because that's my lucky number" but it's a simple and effective fix. Oh well, guess I'll have to get rich through hard work :)
I'll open myself up to scorn by admitting that I buy these things often. You don't get to select your tickets in NY, they are ripped off one at a time on a roll that is in a locked container.
The most obvious vulnerability here is clerks and convenience store owners who unroll the tickets and hand out the loser tickets to customers. That risk is mitigated by the craziness of lotto addicts, who won't accept a ticket that doesn't come off of the roll.
In Canada, are you able to say, "I don't want this one" until you get a potential winner? Here in Texas, you cannot pick your ticket. When you buy a ticket, you get whatever the cashier gives you or whatever the machine spits out. Or is the guy simply not wasting time scratching off the losers? I still don't see how this could be profitable since most games have 1:5 odds, including break even prizes.
“Lots of people buy lottery tickets in bulk to give away as prizes for contests,” he says. He asked several Toronto retailers if they would object to him buying tickets and then exchanging the unused, unscratched tickets. “Everybody said that would be totally fine. Nobody was even a tiny bit suspicious,” he says. “Why not? Because they all assumed the games are unbreakable. So what I would try to do is buy up lots of tickets, run them through my scanning machine, and then try to return the unscratched losers. Of course, you could also just find a retailer willing to cooperate or take a bribe. That might be easier.”
Not in the UK lottery; all the tickets get dispensed from clear containers and have to be the next one on the roll (which comes out at the back so you can't see what the next one will be). They've tried educating their customers* about not buying tickets that aren't on the roll.
This to me seemed to be the core of the problem; not that the cards were crackable, but that it was possible for a user to select what card to purchase rather than just what game to play. Remove that and the problem largely goes away through simple education about valid play procedures as I suggested.
Exactly. Force players to buy the next ticket on the roll (without seeing it) and don't allow unused tickets to be returned. Problem solved.
I grew up in Maine and tickets are dispensed this way. Not sure about returning tickets, but knowing Mainers, I'd be surprised if they would take them back. It doesn't pass the straight-face test.
Problem not solved. A savvy attendant just checks the tickets on the end of each roll. If it's a winner, go ahead and buy it. Otherwise, wait until a customer buys the loser first.
I once bought a brick of scratch tickets, the only way I see this working is buying the brick, going through them and pulling out the winners and then selling the unscratched ones back to your friend convenience store clerk. There should be lots of tickets still attached to eachother, so they can be placed back into the hopper and removed as usual. When a "broken link" is encountered, it'll just look like the end of a brick.
It would not work, except that some lotteries have been trying to get creative with marketing. They want to give people an illusion of control, hence letting them choose between several "different" tickets. This is the "baited hook" they mention.
In theory, the tickets are not actually visibly different. In practice, apparently they are, just not in entirely obvious ways.
I checked my national lottery (Belgium), but sadly none of the 15 scratch card types they sell have 'baited hooks' or other unique numbers, as far as I can see ( http://lotto.be/NL/Spelen_en_Winnen/Krasspelen/default.aspx - in Dutch). I would laugh SO hard if we found some exploitable lottery...
Why the hell didn't he hire people to find tickets for him?
If you are worried about people doing this without you, just make an app to calculate the values. Make the calculations server side, and only after checking if the phone is registered.
Just don't hire too many people, or the clerks may start to get suspicious.
Why not bring the clerks into it? The corner-store I go to near-daily knows me well, and they sell lots of lottery tickets. It'd be trivial for me to go in there and say "listen, I'll give you an X% cut in exchange for your silence and first pick of the tickets."
However, if they're knowingly selling losers, could that be construed as fraud? Then again, the lottery does that already...
Even though he knew the formula, at least where I buy lottery tickets, the person behind the counter gives you the ticket. Assuming there are many more losers then winners, without being able to select the tickets yourself, it would seem as though it'd be a losing proposition. Now, if you were the store owner and had access to the tickets yourself, that would be a different story.
It's not only an issue of rarely having control over which scratch-off card you'd like to pick, there's also the issue of most states having the majority of their games almost entirely hidden. Very few games allow you to see numbers or letters plainly - most require to you to scratch off "your" numbers and then scratch off the "board" as well.
They slide out the little display holding the type you're interested in and you sit and mull over the aura of winnitude of each of them. There would be little tolerance for someone looking at each individual card for a minute, though.
The Ontario lottery corporation has come down hard on retailers because, of course, they're the ones who generally ply these scams.
The lottery system can now confidently continue to extracting money out of idiots who don't know better. Somehow this whole story leaves me feeling that nothing good has happened.
The whole story just feels like a good Samaritan helping a schoolyard bully steal change out of the back pockets of unwitting classmates.
A happy ending would be the lottery system managers getting thrown out after suffering unexpected sustained losses.
These are scratch cards, so they already have a set payout for the number they produce. So unless the cards are getting returned to the lotteries and refunded (this might even happen in some cases, I'm not sure) they aren't losing any money. It's just the other people who play the lottery who will have a far lesser chance of winning (as they are sold all the losing tickets rejected by the cheaters)
"The package was sent at 10 am. Two hours later, he received a call from Zufelt. Srivastava had correctly predicted 19 out of the 20 tickets. The next day, the tic-tac-toe game was pulled from stores."
I know that we're supposed to be fascinated by the statistical work done cracking the code, but my real sympathy is for the head of security that received that package. How do you react in such a situation?
As an aside, the statistician seems really cool too - it's a very forthright interview and the article's much better than I expected. Both the statistician and the author seem to be very surprised by the lack of concern shown for the apparent evidence of security breaches. This, of course, has a direct analogue with the way large multi-nationals treat computer security. I was only surprised to get to the end of the article and not find that the statistician had been threatened with prosecution or similar.