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

Question

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

Gilles 'SO- stop being evil' said

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?

Answer 1

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."