Backdooring the Lottery [pdf](media.defcon.org)
media.defcon.org
Backdooring the Lottery [pdf]
https://media.defcon.org/DEF%20CON%2025/DEF%20CON%2025%20presentations/DEFCON-25-Gus-Frischie-and-Evan-Teitelman-Backdooring-the-Lottery.pdf
40 comments
When did Blue Cross become the standard bearer for infosec?
People who haven't worked in infosec think companies like that would naturally be good at security. In reality they're some of the worst. Breaches are just very rare.
Reported breaches
It's just a comparison. Relax.
As an infosec pro, If I was in charge of a lottery RNG, I would require the use of a recent unmodified Linux or OpenBSD distro and simply use getrandom(2). These custom RNG introduce 100% unnecessary complexity and risks. I am baffled none of them seem to do that and they need thirdparty certification procedures (who miss RNG flaws anyway.)
I agree. Customization provides more opportunities for employees to rig the RNGs.
My ideal RNG would be an off-the-shelf computer with a stock image and a < 20 line Python script to display numbers. This could be developed in less than a day and the entire process could be supervised by a third party. There are still trust issues which need to be dealt with (e.g. how are we downloading the image?). These issues could be dealt with with assistance/supervision from a third party or two.
The problem is that lottery RNG vendors are selling a product. Lotteries like to see machines in custom boxes with custom user interfaces. The RNGs have hardcoded game parameters. Some are automated to produce numbers on a schedule without human interaction. Others require an operator to log in and select a game to produce numbers for.
These RNGs contain thousands of lines of code. Some take the form of multiple programs and services. In some cases they even contain multiple machines.
As an example I just ran sloccount on a source directory for one of these RNGs. Here's the (redacted) output:
The systems which this program runs on are set up by a single developer. This setup process is not supervised so even if the developer isn't able to slip something into the source code or the binaries he could in theory place something (e.g. a rootkit or something which simply replaces the RNG program on start) on the system itself.
My ideal RNG would be an off-the-shelf computer with a stock image and a < 20 line Python script to display numbers. This could be developed in less than a day and the entire process could be supervised by a third party. There are still trust issues which need to be dealt with (e.g. how are we downloading the image?). These issues could be dealt with with assistance/supervision from a third party or two.
The problem is that lottery RNG vendors are selling a product. Lotteries like to see machines in custom boxes with custom user interfaces. The RNGs have hardcoded game parameters. Some are automated to produce numbers on a schedule without human interaction. Others require an operator to log in and select a game to produce numbers for.
These RNGs contain thousands of lines of code. Some take the form of multiple programs and services. In some cases they even contain multiple machines.
As an example I just ran sloccount on a source directory for one of these RNGs. Here's the (redacted) output:
62135 XXX cpp=62135
20447 XXX cs=20447
17642 XXX cpp=17642
9308 XXX cpp=5969,ansic=3339
4987 XXX cpp=4987
2414 XXX cs=2414
1926 XXX cpp=1926
1744 XXX cpp=1744
390 XXX cpp=390
150 XXX cpp=150
67 XXX cpp=67
35 XXX cpp=35
32 XXX cpp=32
...
The systems which this program runs on are set up by a single developer. This setup process is not supervised so even if the developer isn't able to slip something into the source code or the binaries he could in theory place something (e.g. a rootkit or something which simply replaces the RNG program on start) on the system itself.
I take it you are in the industry. Interesting :)
I'd take the output of getrandom() and XOR it with something like a quantum RNG.
E.g. these guys claim their hardware is used by Lotteries and Gaming: http://www.idquantique.com/random-number-generation/quantis-...
But, as Agent Mulder knew, "trust no one". So the above is necessary but not sufficient. Above all else, there must be constant vigilance.
E.g. these guys claim their hardware is used by Lotteries and Gaming: http://www.idquantique.com/random-number-generation/quantis-...
But, as Agent Mulder knew, "trust no one". So the above is necessary but not sufficient. Above all else, there must be constant vigilance.
"TRUE RANDOM NUMBER GENERATOR EXPLOITING THE RANDOMNESS OF QUANTUM PHYSICS" not sure what they mean by this. Likely it is just "avalanche noise". This is not very difficult. In fact, I build an hardware RNG that is based on avalanche noise (not my development):
https://emergent.unpythonic.net/01257868826
https://emergent.unpythonic.net/01257868826
Evaluating the veracity of their claims is way above my pay grade.
They do have a PDF on their site: http://marketing.idquantique.com/acton/attachment/11868/f-00...
Basically, emit photons at a semi-transparent mirror. 50% go straight, 50% reflect 90 degrees. Have single-photon detectors at both directions. Quoting from their PDF:
Figure 2 shows the block diagram of the Quantis random number generator. It consists of three subsystems. The first one is the core of the generator and contains the optical elements that are used to implement the random process and produce the random outcomes. It comprises a light emitting diode producing the photons, a transmission element, where the random process takes place, and two single-photon detectors – detectors with single-photon resolution – to record the outcomes. The optical subsystem is controlled by a synchronization and acquisition electronic circuit. This subsystem comprises a clock and triggering electronics for the photon source, as well the acquisition electronics for the single-photon detectors. The processing and interfacing subsystem perform statistical and hardware checks, as well as unbiasing of the sequence.
Edit: the ID Quantique hardware is a bit pricey for hobbyists, starting at about 1000 euros.
If I were building something for myself, I'd look here for inspiration: https://www.fourmilab.ch/hotbits/ That hardware detects beta decay events.
That's preferable to me than "avalanche noise". Not that there's anything fundamentally wrong with thermal noise or shot noise; it's that in real implementations the quality of results is very dependent on things such as quality of power supply. To me it's much simpler to correctly detect intervals between consecutive radioactive decay events.
The downside to a cheap decay detector is that the number of events is much lower than what the commercial hardware provides. A few hundred bits per second versus a few million bits per second.
They do have a PDF on their site: http://marketing.idquantique.com/acton/attachment/11868/f-00...
Basically, emit photons at a semi-transparent mirror. 50% go straight, 50% reflect 90 degrees. Have single-photon detectors at both directions. Quoting from their PDF:
Figure 2 shows the block diagram of the Quantis random number generator. It consists of three subsystems. The first one is the core of the generator and contains the optical elements that are used to implement the random process and produce the random outcomes. It comprises a light emitting diode producing the photons, a transmission element, where the random process takes place, and two single-photon detectors – detectors with single-photon resolution – to record the outcomes. The optical subsystem is controlled by a synchronization and acquisition electronic circuit. This subsystem comprises a clock and triggering electronics for the photon source, as well the acquisition electronics for the single-photon detectors. The processing and interfacing subsystem perform statistical and hardware checks, as well as unbiasing of the sequence.
Edit: the ID Quantique hardware is a bit pricey for hobbyists, starting at about 1000 euros.
If I were building something for myself, I'd look here for inspiration: https://www.fourmilab.ch/hotbits/ That hardware detects beta decay events.
That's preferable to me than "avalanche noise". Not that there's anything fundamentally wrong with thermal noise or shot noise; it's that in real implementations the quality of results is very dependent on things such as quality of power supply. To me it's much simpler to correctly detect intervals between consecutive radioactive decay events.
The downside to a cheap decay detector is that the number of events is much lower than what the commercial hardware provides. A few hundred bits per second versus a few million bits per second.
Pretty good open-hardware TRNGs out there, such as OneRNG. I'd probably attach it and let it mix the rng pool, but not draw from it directly.
I wonder why they didn't go for an easy technique to defend against backdoors: use two independent sources for random numbers that don't know of each other and xor their output together. The increase in cost is small and the win for integrity and security is huge.
Yes, XOR. But what's also needed is simplicity.
As another poster here said, "simply use getrandom()". Whether or not you agree with that exact function, the idea behind "simply" is exactly that, simplicity. It's a lot easier to audit code that does:
As another poster here said, "simply use getrandom()". Whether or not you agree with that exact function, the idea behind "simply" is exactly that, simplicity. It's a lot easier to audit code that does:
getrandom()
read hardware RNG
XOR those two together
done!
btw ... keep a permanent log of these random numbers
>getrandom()
>read hardware RNG
For that matter, getrandom might be able to do something to muck with the hardware RNG, or with the code following. Or any code not part of your RNG scheme could try and muck with the results.
>Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays?
The code was audited and passed because there was no such check. The machine code that made it onto the machine did not match the source code submitted, but instead had an extra function tacked onto the end. How do you defend against this [0]. What if someone sneaks the backdoor in the firmware of the harddrive, that only provides the backdoored code to the CPU occasionally.
At some point, you need to trust the people making the lottery machines.
[0] Hint, reproducible builds and signed code; but this still devolves into a trusting trust situation.
The trusting trust issue is solveable. Also, the deeper you go the more powerful you assume your adversary. If you limit the power of your adversary, you can stop before going fully back to a root of trust you can verify without a computer.
Trusting trust is solveable?
Maybe let's first specify what we are talking about. With trusting trust I mean a chicken and egg problem: To verify a computer you need another computer you trust. But then, how would you verify the other computer?
How would this be possible to solve? Exactly how you bootstrap building complex CPU's from scratch or a big factory in Factorio. You start from first principles and build a very simple computer you can verify without another computer. This guy is the root of the bootstrapping process. Then you build another computer that is too fast to check manually and make the first one check this one. Now, you already have a verified computer that you can only check with other computers.
The basic idea is clear to me, but the specific steps are not. I guess one would need a simple language for the root of the bootstrap process and write a compiler or interpreter for another more complex language in it. Then, use the second compiler/interpreter to build a compiler/interpreter for a yet more powerful language (maybe that's already C), which we run on the next node. Using this process you can end up with a verified computer that can compile stuff, or what not.
Since we would probably not be able to build a machine sufficiently fast for our needs, we need to use commercial and maybe backdoored computers. How do we protect against these? You get at least two different machines (at least different ISA) from different manufactures from different countries. Note, that it would not be a problem if they are backdoored. You must only ensure that they don't have identical backdoors.
Now you create a verified program for each of the possibly backdoored computers and make sure that they know of each other, they must be unconnected. Their output goes into a simple verifieable machine that does only bit for bit checking. If a backdoor is trigged, then the output of the two machines won't be identical anymore.
In this setuo one would need to generate random numbers on some trusted device and feed the same stream into both machines. Also, the operating system must be completely deterministic in it's behaviour. That is surely possible, but no one I know of is.
Then, you have a verified setup that does exactly what is written in the source and any backdoor in the system itself will be detected.
I'm convinced that the process above is doable for individual developers. But creating and engineering all the steps is a lot of work.
I hope some day the community or maybe even governments will have created a manual "Creating trustable trust" where all the steps are worked out.
How would this be possible to solve? Exactly how you bootstrap building complex CPU's from scratch or a big factory in Factorio. You start from first principles and build a very simple computer you can verify without another computer. This guy is the root of the bootstrapping process. Then you build another computer that is too fast to check manually and make the first one check this one. Now, you already have a verified computer that you can only check with other computers.
The basic idea is clear to me, but the specific steps are not. I guess one would need a simple language for the root of the bootstrap process and write a compiler or interpreter for another more complex language in it. Then, use the second compiler/interpreter to build a compiler/interpreter for a yet more powerful language (maybe that's already C), which we run on the next node. Using this process you can end up with a verified computer that can compile stuff, or what not.
Since we would probably not be able to build a machine sufficiently fast for our needs, we need to use commercial and maybe backdoored computers. How do we protect against these? You get at least two different machines (at least different ISA) from different manufactures from different countries. Note, that it would not be a problem if they are backdoored. You must only ensure that they don't have identical backdoors.
Now you create a verified program for each of the possibly backdoored computers and make sure that they know of each other, they must be unconnected. Their output goes into a simple verifieable machine that does only bit for bit checking. If a backdoor is trigged, then the output of the two machines won't be identical anymore.
In this setuo one would need to generate random numbers on some trusted device and feed the same stream into both machines. Also, the operating system must be completely deterministic in it's behaviour. That is surely possible, but no one I know of is.
Then, you have a verified setup that does exactly what is written in the source and any backdoor in the system itself will be detected.
I'm convinced that the process above is doable for individual developers. But creating and engineering all the steps is a lot of work.
I hope some day the community or maybe even governments will have created a manual "Creating trustable trust" where all the steps are worked out.
It seems like you haven't read "Reflections on Trusting Trust"?
http://www.acm.org/classics/sep95/
http://www.acm.org/classics/sep95/
> Who allowed something into production that had an opportunity to check for Wednesdays and Saturdays?
From the analysis in the article it sounds like the function that you're describing was added to the dylib binary after compilation, so it was 'slipped' rather than 'allowed' into production.
That said, auditing the binary and bindiff as suggested could perhaps mitigate the problem, modulo 'Reflections on trusting trust' and its mitigations.
From the analysis in the article it sounds like the function that you're describing was added to the dylib binary after compilation, so it was 'slipped' rather than 'allowed' into production.
That said, auditing the binary and bindiff as suggested could perhaps mitigate the problem, modulo 'Reflections on trusting trust' and its mitigations.
[deleted]
[deleted]
And trying to explain that to a general population will be impossible.
Secure? Yes. Workable? No.
Secure? Yes. Workable? No.
You still need a program to perform the mixing. The intended source of entropy isn't really the issue. The integrity of the program which produces and displays these numbers is.
Instead of xor-ing multiple sources of randomness together,
it's preferable to feed them all into a cryptographically secure hash function, like Keccak or Blake2. One of the sources to be added could be the header of a recently published bitcoin block.
Not quite. That gets you better mixing, but maybe Blake2 has bias in some bits, or bias in some output bits given bias in some input bits.
Xor is nice in that xor of a biased bit and an unbiased bit is an unbiased bit.
Xor is nice in that xor of a biased bit and an unbiased bit is an unbiased bit.
it would be a terrible oversight to put that thing on the internet, either public or private.
I remember reading about the MUSL RNG fraud recently (1-2 years ago). Interesting that they are tying state lottery frauds to that malicious insider from as far back as 2005 (or so the slides suggest).
For anyone else that reads this and thinks the comment is referring to the musl libc fear not. Apparently MUSL is also the "Multi state Lottery":
The idea of a public/random mixing source is always fun. Everybody has a fun pet idea but they all suffer from one issue or another. Here's some of mine:
1. Move the mouse around
2. Force someone to dance and read the output from a webcam
3. Record various RF signals
4. Speak a joke into a microphone.
The best solution is probably just a plain, non-network computer with an open-hardware TRNG to mix the CSPRNG (I believe BSD is switching to Fortuna). Read from the CSPRNG all day loooong.
1. Move the mouse around
2. Force someone to dance and read the output from a webcam
3. Record various RF signals
4. Speak a joke into a microphone.
The best solution is probably just a plain, non-network computer with an open-hardware TRNG to mix the CSPRNG (I believe BSD is switching to Fortuna). Read from the CSPRNG all day loooong.
Anyone getting SSL errors trying to load the slides? Nothing seems to work, including proxying over Tor.
I put a copy in IPFS:
https://ipfs.io/ipfs/QmcgWw89GFo3Z1w9ad1H6Gom4DV4t5VRBu5zhkW...
https://ipfs.io/ipfs/QmcgWw89GFo3Z1w9ad1H6Gom4DV4t5VRBu5zhkW...
Yup. Not working on multiple browsers, curl, etc.
File listing via Google Cache shows it was accessible: https://webcache.googleusercontent.com/search?q=cache:uatZ4u...
Wayback Machine doesn't have it.
Ah... Google cache has it:
https://webcache.googleusercontent.com/search?safe=off&outpu...
File listing via Google Cache shows it was accessible: https://webcache.googleusercontent.com/search?q=cache:uatZ4u...
Wayback Machine doesn't have it.
Ah... Google cache has it:
https://webcache.googleusercontent.com/search?safe=off&outpu...
I was, but it's working now.
Seems to work now.
[deleted]
I also recall one of the compliance guys telling me about the balls used in one of those bingo ball tumbling machines. He said they had to wash, dry and weigh each ball before every draw. Of course it was fun to yell to him saying on draw day "hey it's Friday did you wash and dry your balls?"