1
$\begingroup$

New to cryptographic, weak in math.

I have designed a PRG which consist of 33 LFSR's, each 32 bits wide.

I use one of the LFSR's as "selector", using the 5 LSB from this register to select one of the other 32 registers, from which I grab one byte and use as output. So each requested byte will thus come from one of 32 "randomly" selected registers.

My gut-feeling is that such a scheme will:

  1. Hide the selector register from the outside world (rendering Berlekamp-Massey useless)
  2. Expose an attacker to a very fast growing tree of possible combinations. (If trying to sort out from which LFSR the last byte might emerge)

As it seems to me as this is an obvious way of creating a truly messy output, it surprises me that I haven't seen it described somewhere (with a name like "Rose-Morris-Nyqvist-Yang-Goldstein-scrambler"), so my conclusion is that it must be a bad solution. (Even beside the obvious hassle of seeding 33 registers and select feedback masks).

So my question is: Why not?

/Hans

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ The alternating step generator is close-enough that I doubt there's a name for your generalization. $\hspace{.59 in}$ $\endgroup$
    – user991
    Mar 28, 2015 at 11:32
  • 1
    $\begingroup$ I think LFSR's are primarily used on constrained environments, so requiring a very large state (and at least 1.25 times the processing power) is quite a big thing to ask. $\endgroup$
    – Maarten Bodewes ♦
    Mar 28, 2015 at 15:49
  • $\begingroup$ OK, sorry Ricky, the name part was a joke - a try, at least - but my question remains; is my scheme flaky or stupid in some some way that I fail to recognize, or will it provide decent security? $\endgroup$
    – H. Circlebeach
    Mar 28, 2015 at 19:30
  • 2
    $\begingroup$ @H. Circlebeach: you have not defined your scheme fully: it is unclear if at each step, 2 or 33 LFSRs are stepped, and by how many bit steps; what are the polynomials; and how the initial state is chosen. $\;$ Whatever these details, once they are known, there's a trivial attack: enumerate the possible states of the selector LFSR (that's only $2^{32}$ possibilities), and check that hypothesis against known keystream, focusing on the most-often selected of the 32 other LFSRs. Finding state and predicting future output from 1024 bytes of past output would require minutes. $\endgroup$
    – fgrieu ♦
    Mar 29, 2015 at 9:48
  • $\begingroup$ @fgrieu: Ah, ok, sorry, the 32 registers used for output are stepped 8 or 9 bits - when called - and the initial states are created by another 32 bit lfsr (seeded with a password) and the polynomes are selected likewise (from a list of 100 different (good 2giga-ticks) polynomes). But I maybe should stick to the standards. It seems easy to make huge mistakes in this disipline... $\endgroup$
    – H. Circlebeach
    Apr 2, 2015 at 13:18

1 Answer 1

Reset to default
4
$\begingroup$

Your design seems to be a byte-wise generalization of Jennings' multiplexed generator rather than the alternating step generator.

S. M. Jennings, “Multiplexed Sequences: Some Properties of the Minimum Polynomial,” Lecture Notes in Computer Science, vol. 149, 1983.

I believe designs like hers [may even be byte based for efficiency] have been used in satellite TV encryption in the 1980s-1990s, but can't find the reference now.

There has been cryptanalysis showing such schemes may not be as strong as first thought.

Jovan Dj. Goliv, Mahmoud Salmasizadeh, Ed Dawson: Statistical Weakness of Multiplexed Sequences, Finite Fields and Their Applications 8(4):420-433, 2002.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! "Multiplexed" is the search term I have been missing... $\endgroup$
    – H. Circlebeach
    Mar 29, 2015 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.