Hacker News Reader

Hacker News

Comment by micaeked | Hacker News Reader

Parent Full thread

micaeked

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

View on HN

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.

Reply on news.ycombinator.com