1
$\begingroup$

Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?

$\endgroup$
  • 2
    $\begingroup$ The claim "Forward security can be achieved using symmetric encryption schemes" is dubious and unsourced Also, "LFSR-based PRNG" is vague. It goes from LFSR (very insecure) to Trivium (unbroken), with ASG, SSG, A5/1 in-between (unbroken for large-enough parameters, with no precise security claim). $\endgroup$ – fgrieu Feb 10 at 8:36
2
$\begingroup$

Once an attacker knows $2L$-bits of an $LFSR$ of length $L$ with unknown taps, they can use the Berlekamp-Massey algorithm to construct your LFSR. If the taps are known, then only $L$ bits are required. Therefore your PRNG based on a single LFSR will fail. They were popular but anymore.

  • LFSR's has no next-bit security. From previous known states, the next bit is exactly can be found.
  • More generally, an attacker that knows the current state, they have more power than predicting the next outputs, they know the next states of your random number generator.
  • LFSR's can be run backward, which will reveal the previously generated random numbers. Once an attacker accesses the system, they will able to decrypt the previously encrypted messages. See the Double ratchet which is used by Signal.
| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ @fgrieu I took the question like it only uses an LFSR. The OP must be clear about the algorithm as you noted on your comment. $\endgroup$ – kelalaka Feb 10 at 8:57

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.