Are LFSRs enough for this?

Question

Consider the following experiment:

Let there be a machine which runs (ie. continually clocks) an LFSR of size (ie. number of bits) $b$, having a button that, when pressed, extracts the next $t$ bits from the LFSR, prints them onto a paper ticket, deposits the ticket into a sealed, opaque urn, and complements every bit in the LFSR (ignore, for the sake of argument, the case where the LFSR gets reset to all zeroes); the machine continues to run normally afterwards.

Now place this machine in a room, completely isolated from the outside, and have a number (say $n$) of players form a line and, one by one, step into the room and press the button. After all $n$ of them are finished, retrieve the sealed urn.

The LFSR's feedback polynomial, initial state and clocking frequency are public parameters, as are the numbers $b$ and $t$.

Now there's an attacker whose purpose is to match at least one ticket in the urn to one of the players. The attacker has access to all the public parameters, knows the order in which the players are lined up, can measure the time each one enters the room (but cannot, obviously, know exactly when a player pushes a button, since that happens inside the isolated room), and may collude with a fraction q of the players in order to achieve its goal.

The questions, then, are:

1. Which parameters (ie. $b$, $t$, $q$, clocking frequency is a little trickier) can ensure the attacker has no more chance of succeeding than he would by guessing?
2. Would replacing the LFSR by an ASG be any better? any worse?

A note on clocking frequency: for technical reasons, the clocking frequency is forced to be relatively low, say no more than 2kHz (ie. one clock pulse every one two-thousandth of a second).

A note on collusion and what the players can and can't do: the players can be assumed to have at their disposal a timing device of their choosing, with the accuracy they see fit (if this proves to be too powerful an advantage, an analysis with restrictions is greatly appreciated!); a player does not see the number they get (they actually don't get it per se, since the number goes into the urn).

---

The rationale behind all this is that we're trying to generate true-ish random numbers from an LFSR: the random variable to harness is the times at which the button is pressed, the LFSR is there just to provide for confusion of the generated values; if one where to use the number of seconds since the experiment's beginning, the attacker could easily match the tickets to the players; if one where to use the LFSR without complementing, the attacker could compare them according to the order in which the LFSR (all of whose parameters are public) generates them; I believe (with absolutely no basis!) that complementing after each extraction could do the trick.

---

English is not my mother language, I'm sorry if I haven't made myself clear enough, please do ask for clarifications if needed.

This is not homework, tough it may look like it :)

---

---

EDIT: It has been brought up more than once in the answers that knowing so much and being able to do so much, gives the attacker too much power, so i decided to make the LFSR's initial state secret. Now the last paragraph in the explanation above should read:

The LFSR's feedback polynomial and clocking frequency are public parameters, as are the numbers $b$ and $t$. The LFSR's initial state is secret, and unknown to the attacker.

Answer 1

Here is an attack that I think will, with excellent odds, allow certain determination of which value is on the ticket of colluding players; and consequently give an advantage on guessing the tickets of these colluding players, and a (typically lesser) advantage on guessing the tickets of honest players. I'm assuming:

• The adversary knows the value on every ticket (as confirmed by a comment), with no ambiguity about that under orientation of the ticket.
• It is not known the initial state of the LFSR (as now explicit).
• All players press their button haphazardly, which when the exact instant is unknown sorts of partially reseed the LFSR.
• The adversary knows exactly when $m$ consecutive players pressed the button (because these $m$ players collude with the adversary), thus exactly how many steps of the LFSR there has been between theses presses; this allows the adversary to express the state of the LFSR at the key-presses of the colluding players as a linear function of the (assumed unknown) state when the first colluding player pressed the button.
• $n$ is low enough that the adversary can perform some processing for each of the (at most) $n!/(n-m)!$ distinct orders of values for colluding players ($n=15$, $m=10$ means that about $11\cdot10^9$ orders are to be considered, and would be very feasible).
• $t$ is large enough that it is likely that only a single of these ticket order matches the linear functions; there are $b$ unknown bits, $(n-1)\cdot t$ known bits, thus by an entropy argument (based on the vague and unproven hypothesis that the haphazard behavior of players makes the system of linear equations unremarkable), there should typically be a single possible order of values when $$m\cdot t\gg b+\log_2(n!/(n-m)!)$$

It is then easy to check a candidate order, and deduce the $b$ bits of initial state. Just plug $m={2\over3}n$ for $2\over3$ of the players colluding.

Also, if the uncertainty on when the honest players pressed (assumed to have uniform distribution in an interval with $u$ steps, with that the product of time per frequency) is such that $u\ll2^t/(n-m)$, we can often guess the (value on the) tickets of other players immediately before and after the $m$ colluding players; even all of them if $u\ll2^t/(n-m)!$ or something on that tune.

Further (as the saying attributed to the NSA goes, and illustrated by a sizable improvement in version 5 of this answer): attacks only get better; they never get worse. In particular, I have not fully exploited the information that can be gained from the known value on the tickets of the honest players, which is significant if $u\ll2^t$; or speedups possible for many parameters to dramatically cut down on $n!/(n-m)!$ explorations; or what improvements could be achieved when colluding players press at a chosen instant, rather than at a random but known instant.

---

The above does not give a condition that would insure an adversary can't succeed. Here are some thoughts towards that. I'll consider that the LFSR is maximum-length (has period $2^b-1$, or equivalently uses a primitive polynomial and is never all-zero); and that a key-press occurring when the LFSR is all-one prints an all-one ticket, but leaves the LFSR as if no key-press had occurred.

Assume a player stays exactly $u=2^b-1$ clock periods in the room, and consider the 4 variables

• LFSR state $I$ on entrance
• LFSR state $P$ as sampled by key-press (of which $t$ out of $b$ bits are printed)
• LFSR state $O$ on exit
• number of clock periods $w$ between entrance and key-press, with $0\le w<2^w$

It holds that $P=M^w\cdot I$ and $\hat P=M^w\cdot O$, where $\hat P$ is the bitwise complement $\bar P$ of $P$ except that all-ones is unchanged; and $M$ is the $b\times b$ sparse matrix corresponding to advancing the LFSR by one step. When any of $I$ $P$ $O$ $w$ is fixed, these relations defines a one-one mapping from any of the other three variables to either of the two last variables. Note: when $w$ is unknown, finding it (or $P$ if also unknown) seems to be a discrete logarithm problem; I consider an adversary able to solve that.

It follows that when an honest player stays in the room for much longer than $2^b-1$ clock periods, to an adversary knowing only one of the LFSR states on entry or exit,

• the other of these states is indistinguishable from a uniformly random non-zero variable,
• the value printed on the ticket has the same distribution as for a random sampling (all-zero with odds $2^{b-t}-1\over2^b-1$, any of the other $2^t-1$ values with higher odds $2^{b-t}\over2^b-1$).

The above two unknowns are however strongly related.

If we see the LFSR as an entropy pool,

• an honest player staying in the room for much longer than $2^b-1$ clock periods refills that entropy pool to its full capacity $c=\log_2(2^b-1)$ bit
• however knowledge of the value of a ticket reveals at most $r=\log_2(2^b-1)-\log_2(2^{b-t}-1)$ bit of information when $t<b$ (this occurs when the value printed is all-zero), or $r=\log_2(2^b-1)$ bit when $t=b$ (the value printed can't be all-zero).

From this I tentatively conjecture that with all but very small $b$, the adversary has negligible advantage if at least $h$ honest players, who each stay in the room for much longer than $2^b-1$ periods, stand between any two players colluding with the adversary, and $$h\cdot c\ge (h+1)\cdot r \text{ , that is } t<b \text{ and } (h+1)\cdot\log_2(2^{b-t}-1)\ge\log_2(2^b-1)$$

The condition is constructed as: in a sequence of $h+1$ players, at least as much entropy is injected as revealing all the ticket values consumes. My intuition is that this condition is enough that the adversary can't learn more about the state of the LFSR when a player presses a key than knowledge of the corresponding ticket value would reveal, and/thus is unable to tell if an hypothesis on which ticket belongs to who is more or less likely.

Answer 2

If I know the initial state and the time window that the first player pressed the button, I can just run the LFSR up to and through that time window. The first player's token will match one of these states, which means you know the LFSR state after player 1 has gone. You can repeat this to find the token for player 2, since applying the inversion gives you the initial state prior to player 2's turn. You also know the exact time that player 1 pressed the button.

The state inversion "jumps" the LFSR from one location on its cycle to another, so it's possible for the urn to have two tokens that correspond to LFSR states that occur within a player's time window. If the number of players is small and the state is large this is very unlikely. If it does happen we can detect it by clocking the LFSR through the player's whole time window, and we then have to follow two possible initial states to find the next player's token.

None of this analysis uses the fact that the system uses an LFSR. Any deterministic PRNG will have this problem if we know all of its initial state.

If we don't know the initial state, it's a little harder to reconstruct the state at any time. But you can just set the LFSR state to that of a token and run it forwards and backwards. Its state will eventually match another token, at which point you invert and keep going. This way you can chain the tokens together in sequence and match them up with the players.

Note that this only works because the token represents the entirety of the LFSR state. If the token was a an encrypted version of the state this wouldn't be possible, and if it was just part of the state it would be much more difficult.