4 ms·

This is a known method for a simple way of getting an unbiased bit from a series of (possibly biased) coin flips. Stated another way, the algorithm for getting

This is a known method for a simple way of getting an unbiased bit from a series of (possibly biased) coin flips. Stated another way, the algorithm for getting an unbiased bit from a biased coin is: 1. Flip the coin twice. 2. If it's both heads or both tails, discard result and go back to 1. 3. If it's heads then tails, result = 0 4. If it's tails then heads, result = 1

infogulch 10y ago
This assumes the bias can't change over time. This works for a coin because you're using the same coin for all flips, you just don't know the bias. This falls apart in this library because in the computer the source can be affected differently over time -- an attacker can effectively switch out your coin on every flip, rendering this whole process useless.
- micaeked 10y ago
  Yep, I agree. I do think the claims made in the readme are way too strong for what they are. This is only an explanation for what that small part of it does. EDIT: And you're right about the bias changing making this useless. I hadn't thought of that.
- dakami 10y ago
  I'm not convinced Von Neumann debiasing is vulnerable like you think. You're dropping runs (00's and 11's) so you don't care if it's 90% 0 or 90% 1, you care if there's an even number of a run or an odd number of a run. In other words: 0000000000000001 000000001 001 ...are all interchangeable. So biases can change all day. There are _other_ issues I've seen in real world data, but not this one.
  - infogulch 10y ago
    So I have the ability to arbitrarily change the bias on every flip, and you don't think debiasing is affected? How about this: for the next string of generated bits, for every even bit the bias is 90% towards 1, and every odd bit the bias is 90% towards 0. raw: 0101010101010111010101010001010101010101 'debiased': 1111111111111111
    - dakami 10y ago
      Ah, there you go. Repro code: #/usr/bin/python from random import * count=0 def get_bit(): global count count+=1 if (count%2)==0: return random()<0.9 else: return False def get_fair_bit(): while 1: a=get_bit() b=get_bit() if a!=b: return a while 1: print get_fair_bit() I'm wondering how often this one shows up the field -- my interest here comes from the ~1% failure rate of RSA keys in the field because manufacturers actually will not install hardware RNG or externally inject key material. Field vulnerability trumps religion. It looks like you need a really stateful vuln -- something akin to "a 1 is always followed by a 0 due to power drain" wouldn't be enough because the number of 0's is still acceptably unbound. I know there are debiasers that look at statistics across a group. Wonder what else is out there.
TickleSteve 10y ago
i.e. an edge detect algorithm.

infogulch 10y ago

This assumes the bias can't change over time. This works for a coin because you're using the same coin for all flips, you just don't know the bias. This falls apart in this library because in the computer the source can be affected differently over time -- an attacker can effectively switch out your coin on every flip, rendering this whole process useless.

micaeked 10y ago
Yep, I agree. I do think the claims made in the readme are way too strong for what they are. This is only an explanation for what that small part of it does. EDIT: And you're right about the bias changing making this useless. I hadn't thought of that.
dakami 10y ago
I'm not convinced Von Neumann debiasing is vulnerable like you think. You're dropping runs (00's and 11's) so you don't care if it's 90% 0 or 90% 1, you care if there's an even number of a run or an odd number of a run. In other words: 0000000000000001 000000001 001 ...are all interchangeable. So biases can change all day. There are _other_ issues I've seen in real world data, but not this one.
- infogulch 10y ago
  So I have the ability to arbitrarily change the bias on every flip, and you don't think debiasing is affected? How about this: for the next string of generated bits, for every even bit the bias is 90% towards 1, and every odd bit the bias is 90% towards 0. raw: 0101010101010111010101010001010101010101 'debiased': 1111111111111111
  - dakami 10y ago
    Ah, there you go. Repro code: #/usr/bin/python from random import * count=0 def get_bit(): global count count+=1 if (count%2)==0: return random()<0.9 else: return False def get_fair_bit(): while 1: a=get_bit() b=get_bit() if a!=b: return a while 1: print get_fair_bit() I'm wondering how often this one shows up the field -- my interest here comes from the ~1% failure rate of RSA keys in the field because manufacturers actually will not install hardware RNG or externally inject key material. Field vulnerability trumps religion. It looks like you need a really stateful vuln -- something akin to "a 1 is always followed by a 0 due to power drain" wouldn't be enough because the number of 0's is still acceptably unbound. I know there are debiasers that look at statistics across a group. Wonder what else is out there.

TickleSteve 10y ago

i.e. an edge detect algorithm.