Hacker News Reader

Hacker News

Comment by valarauca1 | Hacker News Reader

Full thread

valarauca1

How does checking `get_fair_bit(0)' that the next bit isn't the same as the current help fairness?

View on HN

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

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.

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.

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.

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

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.

i.e. an edge detect algorithm.

Assume a fixed bias: A coin flips 90% heads/ 10% tails. To make it 50/50, you can demand either a HT to make a heads, or TH to make a tails. Since HT and TH have the same odds of occurring, you get a 50/50 chance.

Reply on news.ycombinator.com