Looking at the use of Linear Feedback Shift Registers in cryptographic algorithms, I have learned that the Berlekamp-Massey algorithm can be used to find the (shortest) LFSR that generates a given sequence.
But I am not sure if I have really understood things correctly.
Since an LFSR function always returns a copy of its (current) state, one only has to collect enough outputs to be able to construct an LFSR that produces the same binary sequence like the attacked LFSR produces. In a sense this could be interpreted as "collect enough samples/output" to be able to create a function that allows to reconstruct the same binary sequence. (Hope that's correct so far?)
Now, what I am unsure about:
correct LFSR output sampling for Berlekamp-Massey
To be able to successfully apply the Berlekamp-Massey algorithm, does it matter if the collected samples/output are collected "in sequence", or is it enough to do "random sampling"?
Differently asked (to ensure you get what I'm trying to ask), which one of the following is correct:
- Start by fetching a random output and continue collecting several follow-up outputs until enough outputs/samples have been collected. (what I called "in sequence")
- Skipping/missing a few outputs during sampling does not represent a problem, because it does not have to be a series of follow-up outputs; as long as the total number of collected random samples/outputs suffices. (what I called "random sampling")
expected info to be able to calculate the minimum number of needed samples
I've seen some formulas which seemed to point at the calculation, but I do not yet understand them well enough to deduct an answer to the following: Can the minimum number of to-be-collected samples be deducted from a single LFSR sample/output, or would one need more than a single sample/output to calculate the the minimum number of to-be-collected samples/outputs (which would be needed to successfully apply the Berlekamp-Massey algorithm)?
Please don't misinterpret my questions. I'm "doing my research" and I have been reading a whole slew of academic papers that I found in relation to Berlekamp-Massey, but that doesn't mean I'm confident in the fact that I am interpreting those papers correctly. Also, search engines aren't always the best place to find good references. If you know about a specific paper that I should definitely be reading (in relation to Berlekamp-Massey and related LFSR attacks/breaks), I would be grateful if you'ld point me to it.