The Rationale behind NIST's counter/LFSR recommendation on deterministic IV constructions on SP 800-38D

The NIST has a "SP 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC". This guideline is a base for AES-GCM from definition to security considerations. ( all bolds are mine)

In section 8.2.1 Deterministic Construction IV

In the deterministic construction, the IV is the concatenation of two fields, called the fixed field and the invocation field. The fixed field shall identify the device, or, more generally, the context for the instance of the authenticated encryption function. The invocation field shall identify the sets of inputs to the authenticated encryption function in that particular device.

and later in the same section

The invocation field typically is either 1) an integer counter or 2) a linear feedback shift register that is driven by a primitive polynomial to ensure a maximal cycle length. In either case, the invocation field increments upon each invocation of the authenticated encryption function.

The distinction of a counter and Linear Feedback Shift Register (LFSR) is clear. A counter can be simply implemented in the CPU registers in construct an LFSR that requires a primitive polynomial and extra code. Selecting/finding a primitive polynomial is not hard today. As listed in this SO answer there is a report from HP list the binary primitive polynomial of low-degree. One can also use Maple, Mathematica, and SageMath to find one.

If everything works correctly, the counter and LFSR can produce unique IV's that are crucial for the security of the AES-GCM. Any (IV,Key) pair use can remove the confidentiality and can cause forgery.

There is one problem that I'm aware of; during the system failures, the last incremented/advanced counter/LFSR value can be lost. If the administrators continue from the last known values this can result in (key,IV) pair reuse. To mitigate either exchange a new key or use random in some part of the IV.

In the comment of the answer of What are the rules for using AES-GCM correctly?

Maarten Bodewes said

Sorry, but I don't understand why you'd need a LFSR specifically rather than a generic DRBG.

and also

This is good advice except for the LFSR. A non-cryptographic RNG has no place in crypto code.

and

I wonder why they suggest an LFSR. It's a pity that they don't give a rationale.

So the questions for the AES-GCM are;

1. What is the rationale of the NIST to suggest counter and LFSR for IV.

2. Why using an LFSR is not good advice?

3. In section 8.2.2 RGB-based construction talk about RGB(Random Bit Generator) in two ways

1. an output string of r(i) bits from an approved RBG with a sufficient security strength, or
2. the result of applying the r(i)–bit incrementing function to the random field of the preceding IV for the given key

Is there any advantage of RGB against counter/LFSR?

• I had a hunch that didn't quite work out but yielded a relevant bit of information: NIST SP 800-38A ("Recommendation for Block Cipher Modes of Operation") mentions LFSRs in an appendix as one example of an allowed incrementing function for CTR mode. The GCM spec might just be carrying this over. (p. 19) Commented Oct 5, 2020 at 20:27
• My issue is that using a LFSR by itself still requires you to maintain state. If you can maintain state you might as well use a counter. I think you need a well seeded DRBG otherwise. And yes, if you can seed that LFSR then it may provide some performance benefits, as security of the stream is not really an issue for GCM / CTR. It's just about being as unique as possible. Commented Oct 8, 2020 at 13:03
• @MaartenBodewes that is the problem as I stated in the Q. DRBG is randomized that feard some people for the (IV,key) reuse only if you use the same key too much around. If you change the key as per record in TLS it is clean. Dou you know which one is more used in practice? Deterministic or Randomized? Commented Oct 8, 2020 at 13:07

I can't tell whether this is what motivated NIST, but I found a paper that has an argument for LFSR counters in some applications:

• Mukhopadhyay, Sourav and Palash Sarkar. 2006. "Application of LFSRs for Parallel Sequence Generation in Cryptologic Algorithms." Cryptology ePrint Archive: Report 2006/042.

Abstract. We consider the problem of efficiently generating sequences in hardware for use in certain cryptographic algorithms. The conventional method of doing this is to use a counter. We show that sequences generated by linear feedback shift registers (LFSRs) can be tailored to suit the appropriate algorithms. For hardware implementation, this reduces both time and chip area. As a result, we are able to suggest improvements to the design of DES Cracker built by the Electronic Frontier Foundation in 1998; provide an efficient strategy for generating start points in time-memory trade/off attacks; and present an improved parallel hardware implementation of a variant of the counter mode of operation of a block cipher.

As I mention in one of the comments to the question, NIST SP 800-38a ("Recommendation for Block Cipher Modes of Operation," 2001 Edition) also mentions LFSRs as an example of an allowable incrementing function for counter blocks (p. 18), so the technique predates both GCM and this paper.

RFC 3686 ("Using Advanced Encryption Standard (AES) Counter Mode With IPsec Encapsulating Security Payload (ESP)," January 2004) also allows the use of LFSR counter blocks. It says LFSR are a common IV generation method (p. 5) and obliquely appeal to similar motivations as Mukhopadhyay & Sarkar for allowing them:

[p. 14] Allows adders, LFSRs, and any other technique that meets the time budget of the encryptor, so long as the technique results in a unique value for each packet. Adders are simple and straightforward to implement, but due to carries, they do not execute in constant time. LFSRs offer an alternative that executes in constant time.

Saying that LFSRs execute in constant time does counterintuitive to us software folks, who are biased into thinking more generally that addition is "simple" but LFSRs "complex."

• For historical, there was an advertisement for a product that uses 5 LFSRs to and called the device is secure in Cryptologia. And then Decrypting a Class of Stream Ciphers Using Ciphertext Only ... T. Siegenthaler, in 1984. Commented Oct 5, 2020 at 21:33
• Hardware LFSRs are basically a bunch of wires and some XOR gates, with flip-flops to store the bits. Surprisingly cheap and fast. Adders tend to be a lot bigger and/or slower. Especially expensive to make as fast as LFSRs via carry-lookahead. Commented Oct 6, 2020 at 1:55
• Oh, so the point is that it's optimizing for hardware implementations? Because if you're going to have a dedicated circuit for counter incrementation, an LFSR is cheaper than an adder? Seems a bit weird to me, considering that counter incrementation not often done in hardware. And it wouldn't apply to incrementing nonces between messages. Commented Oct 6, 2020 at 18:15
• For the last question Squeamish Ossifrage here provides a little answer, as expected. The random IV generation is prone to collisions therefore the upper limit of IV generation is much lower than deterinisitic. Commented Oct 9, 2020 at 13:22