Subject: [TLS] where IVs come from (and other mysteries ...)

From: Stephen Kent <[email-masked]>
Date: Thu, 06 Mar 2014 11:56:06 -0500

Folks,

My message about IV generation certainly triggered a lot of responses. 
Some of these appear to result from the "I didn't read the slides" 
phenomenon. Some others appear to result from not understanding how the 
NIST Cryptography Module Validation Program (CMVP) operates and why. And 
then the discussion expanded well beyond the focus of my 
comments/slides. Only one response was a valid rebuttal to my assertion 
that the CMVP requires generation of a counter mode IV inside the 
evaluation boundary. That well-written message surprised me, and caused 
me to do some homework, the results of which are provided below.

With regard to reading the slides:

Slide 6 noted that ChaCha is not a FIPS approved algorithm, and thus is 
not eligible for CMVP evaluation. It also noted that some folks asked 
Tim Polk (NIST) if it might be evaluated, and Tim didn't say no. So, I 
observed that IF folks want ChaCha to be a viable candidate, THEN it 
makes sense to not propose using it in a way that runs counter to the 
evaluation criteria.

Some folks believed that I was arguing that ChaCha needed to use 
pseudorandom IVs, generated within the cryptography module boundary. The 
slides do not say this. It would be fine to use a counter or a LFSR to 
generate a unique sequence of IVs for ChaCha. The requirement, I stated, 
was that this be performed within the evaluation (module) boundary. So, 
one might use a counter for IVs in a module, and yes, that might 
duplicate the sequence numbers already used by a protocol like TLS or 
ESP. This wastes space in each packet, but we already live with it in 
ESP and in other cryptography algorithm / mode combinations in DTLS.

With regard to how CMVP evaluation works:

Arguments that TLS/DTLS (orESP) won't work if the sequence number it 
generates is managed correctly, and thus they are guarantee to be 
unique, are generally irrelevant to such evaluation. The evaluation of 
an algorithm / mode is with respect to the declared boundary for the 
module being evaluated.

Now, with respect to the one message that really caught my attention. 
Wan-The Chang noted that a number of evaluated modules carry an 
indication that they make use of externally generated IVs with AES GCM. 
He provided very precise references in his well written, even handed 
message. I was surprizsd by what I found, so  I checked with NIST and 
received the following response:

..., these are saying external to the "algorithm" not "external to the 
"module".  I agree that the information is confusing and misleading and 
would work with CMVP and CAVP to clarify the statement.

So, in fact, the evaluations are being performed as specified by the 
relevant NIST documents, from which I quite below:

AES-CGM is defined in NIST 800-38D. Section 8 of this document discusses 
IV construction, with both deterministic and RBG-based approaches. 
Section 9 is entitled "Practical Considerations for Validating 
Implementations*"*and it**notes (red highlighting is mine):

*/9.1 Design Considerations /*

In order to inhibit an unauthorized party from controlling or 
influencing the generation of IVs, GCM shall be implemented only within 
a cryptographic module that meets the requirements of FIPS Pub. 140-2. 
*In particular, the cryptographic boundary of the module shall contain a 
"generation unit" that produces IVs according to one of the 
constructions in Sec. 8.2 above. *

This text clearly states that, for this algorithm and mode, the IV needs 
to be generated within the evaluated cryptography module boundary. So, 
what went wrong? I don't know, but I did find a very recent NITS 
publication: Implementation Guidance for FIPS 140-2 and the 
Cryptographic Module Validation program (1/17/2014).Documents providing 
guidance to folks performing module validation are issued periodically, 
e.g., to resolve areas where there has been ambiguity, confusion, etc. 
In this document the relevant text is in Section A.5, which discusses 
Key/IV pair Uniqueness requirements from SP 800-38D (the document quoted 
above). It states:

One difficulty of testing the modules compliance with this requirement 
comes from the fact that each module is tested independently while *SP 
800-38D *demands that the probability of the (Key, IV) pair collision 
between all modules at all times should be sufficiently low to ensure 
cryptographic strength.

*Question/Problem *

How shall a cryptographic module satisfy the requirements of Section 8 
of *SP 800-38D? *

*Resolution *

There are several scenarios that may take place. First, the AES GCM key 
may be generated internally in a cryptographic module. Second, the key 
can be entered into the module.

The IV is generated internally, according to Section 9.1 of *SP 800-38D. 
*It may be either generated randomly or set deterministically, possibly 
by being incremented by 1 every time a new value is needed.

Here is the summary of the requirements that the cryptographic module 
*shall *satisfy.

*1.**The external generation of the IVs is not allowed. *

There are more details in A.5, but the first one applies irrespective of 
the latter ones. This rather strong statement is clear, and consistent 
with the highlighted text from 800-38D, noted above.

The bottom line is that, contrary to what one might infer from the 
terminology used in the certificates, all IVs for use with AES GCM are 
generated within the evaluation (module) boundary, as called for in the 
standards cited above.

That leaves just David McGrew's comments with respect to supplying an IV 
externally, and having a module verify that it was correct. I'll chat 
with David about this, to get a better sense of what he was thinking. 
But, as far as CMVP is concerned, this does not appear to be an op

---

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Mar 2014 09:18:59 -0800

What is the value of evaluation if it does not include the entire TLS
stack? The bugs are not living in the core crypto modules which are
easily tested: they live at a higher level.

Secondly, I don't see why a module that uses a counter as an IV cannot
output it in the right place to be a TLS sequence number. Yes, this
restricts the module design, but it doesn't prevent compliance with
the NIST requirements.

Sincerely,
Watson Ladd

On Thu, Mar 6, 2014 at 8:56 AM, Stephen Kent <[email-masked]> wrote:
> Folks,
>
>
> My message about IV generation certainly triggered a lot of responses. Some
> of these appear to result from the “I didn’t read the slides” phenomenon.
> Some others appear to result from not understanding how the NIST
> Cryptography Module Validation Program (CMVP) operates and why. And then the
> discussion expanded well beyond the focus of my comments/slides. Only one
> response was a valid rebuttal to my assertion that the CMVP requires
> generation of a counter mode IV inside the evaluation boundary. That
> well-written message surprised me, and caused me to do some homework, the
> results of which are provided below.
>
>
>
>             Slide 6 noted that ChaCha is not a FIPS approved algorithm, and
> thus is not eligible for CMVP evaluation. It also noted that some folks
> asked Tim Polk (NIST) if it might be evaluated, and Tim didn’t say no. So, I
> observed that IF folks want ChaCha to be a viable candidate, THEN it makes
> sense to not propose using it in a way that runs counter to the evaluation
> criteria.
>
>
>
> generate a unique sequence of IVs for ChaCha. The requirement, I stated, was
> that this be performed within the evaluation (module) boundary. So, one
> might use a counter for IVs in a module, and yes, that might duplicate the
> sequence numbers already used by a protocol like TLS or ESP. This wastes
> space in each packet, but we already live with it in ESP and in other
> cryptography algorithm / mode combinations in DTLS.
>
>
>
>             Arguments that TLS/DTLS (or  ESP) won’t work if the sequence
> number it generates is managed correctly, and thus they are guarantee to be
> unique, are generally irrelevant to such evaluation. The evaluation of an
> algorithm / mode is with respect to the declared boundary for the module
> being evaluated.
>
>
>
> Wan-The Chang noted that a number of evaluated modules carry an indication
> that they make use of externally generated IVs with AES GCM. He provided
> very precise references in his well written, even handed message. I was
> surprizsd by what I found, so  I checked with NIST  and received the
> following response:
>
>
>
> …, these are saying external to the “algorithm” not “external to the
> “module”.  I agree that the information is confusing and misleading and
> AES-CGM is defined in NIST 800-38D. Section 8 of this document discusses IV
> construction, with both deterministic and RBG-based approaches. Section 9 is
> entitled “Practical Considerations for Validating Implementations”  and it
> notes (red highlighting is mine):
>
> 9.1 Design Considerations
>
> In order to inhibit an unauthorized party from controlling or influencing
> the generation of IVs, GCM shall be implemented only within a cryptographic
> module that meets the requirements of FIPS Pub. 140-2. In particular, the
> cryptographic boundary of the module shall contain a “generation unit” that
> produces IVs according to one of the constructions in Sec. 8.2 above.
>
> This text clearly states that, for this algorithm and mode, the IV needs to
> be generated within the evaluated cryptography module boundary. So, what
> went wrong? I don’t know, but I did find a very recent NITS publication:
> Implementation Guidance for FIPS 140-2 and the Cryptographic Module
> Validation program (1/17/2014).  Documents providing guidance to folks
> performing module validation are issued periodically, e.g., to resolve areas
> where there has been ambiguity, confusion, etc. In this document the
> relevant text is in Section A.5, which discusses Key/IV pair Uniqueness
> requirements from SP 800-38D (the document quoted above). It states:
>
> One difficulty of testing the modules compliance with this requirement comes
> from the fact that each module is tested independently while SP 800-38D
> demands that the probability of the (Key, IV) pair collision between all
> modules at all times should be sufficiently low to ensure cryptographic
> strength.
>
> Question/Problem
>
> How shall a cryptographic module satisfy the requirements of Section 8 of SP
> 800-38D?
>
> Resolution
>
> There are several scenarios that may take place. First, the AES GCM key may
> be generated internally in a cryptographic module. Second, the key can be
> entered into the module.
>
> The IV is generated internally, according to Section 9.1 of SP 800-38D. It
> may be either generated randomly or set deterministically, possibly by being
> incremented by 1 every time a new value is needed.
>
> Here is the summary of the requirements that the cryptographic module shall
> satisfy.
>
> 1.     The external generation of the IVs is not allowed.
>
> There are more details in A.5, but the first one applies irrespective of the
> latter ones. This rather strong statement is clear, and consistent with the
> highlighted text from 800-38D, noted above.
>
> That leaves just David McGrew’s comments with respect to supplying an IV
> externally, and having a module verify that it was correct. I’ll chat with
> David about this, to get a better sense of what he was thinking. But, as far
> as CMVP is concerned, this does not appear to be an op
>
> _______________________________________________
> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Dr Stephen Henson <[email-masked]>
Date: Thu, 06 Mar 2014 17:20:42 +0000

On 06/03/2014 16:56, Stephen Kent wrote:
> 
> This text clearly states that, for this algorithm and mode, the IV needs to be
> generated within the evaluated cryptography module boundary. So, what went
> wrong? I don’t know, but I did find a very recent NITS publication:
> Implementation Guidance for FIPS 140-2 and the Cryptographic Module Validation
> program (1/17/2014).

[snip]

> Here is the summary of the requirements that the cryptographic module *shall
> *satisfy.
> 
> *1.     **The external generation of the IVs is not allowed. *
> 

Although the date on that document is 2014 I have a copy of an earlier version
of the document dating from March 3rd, 2011 which includes exactly the same
statement.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 6 Mar 2014 12:35:03 -0500

> What is the value of evaluation if it does not include the entire TLS stack?

You ever done an evaluation?  Ever try to sell to an entity that required FIPS-certified crypto?

> The bugs are not living in the core crypto modules which are easily tested: they live at a higher level.

Certainly many embarrassing ones do, yes.  But that doesn't mean that there's not business value in being able to get certified crypto.  Now it might not be something you care about, but there are folks on this list who do.

And evaluation isn't a code review and will not (necessarily) find bugs.
	/r$

--  
Principal Security Engineer
Akamai Technology
Cambridge, MA

---

From: Watson Ladd <[email-masked]>
Date: Thu, 6 Mar 2014 10:08:37 -0800

> You ever done an evaluation?  Ever try to sell to an entity that required FIPS-certified crypto?

So the value is that some customers want it? Okay, I appreciate that
concern. But I don't see why meeting it increases confidence in the
property we actually care about, namely correctness of the entire
implementation. It's particularly a problem when the goal is rendering
the certification meaningless by excluding as much as possible from
the scope. Substance matters.
> Certainly many embarrassing ones do, yes.  But that doesn't mean that there's not business value in being able to get certified crypto.  Now it might not be something you care about, but there are…

Sure, but I don't quite appreciate why the module can't generate the
TLS sequence number itself. Is there some complicated interaction of
specs that I'm neglecting?

> And evaluation isn't a code review and will not (necessarily) find bugs.

So it's a little sticker saying "We did nothing to show this works. Have fun!"?

Sincerely,
Watson Ladd

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 6 Mar 2014 10:29:11 -0800

Stephen Kent <[email-masked]>:

            Some folks believed that I was arguing that ChaCha needed to
> use pseudorandom IVs, generated within the cryptography module boundary.
> The slides do not say this. It would be fine to use a counter or a LFSR to
> was that this be performed within the evaluation (module) boundary. So, one

Thanks for clarifying!

Watson Ladd <[email-masked]>:

> output it in the right place to be a TLS sequence number.

Or rather, if you have a module that generates sequence-number IVs
internally, why do you have to transmit that IV at the particular location
where it was output, instead of (external to that module) "compressing" the
data for TLS usage by checking that the CTR mode IV sequence number agrees
with the TLS record sequence number and then omitting it from the
ciphertext?

(This is logically equivalent to having the counter outside the module and
checking explicitly provided IVs against the expected value within the
module as I proposed earlier, but literally adheres to the restriction that
"The external generation of the IVs is not allowed.")

---

From: Sandeep Kumar <[email-masked]>
Date: Thu, 6 Mar 2014 20:02:49 +0100

> "The external generation of the IVs is not allowed.")

RFC5288 states that
   struct {
                opaque salt[4];
                opaque nonce_explicit[8];
             } GCMNonce;

...the salt is generated as part of the handshake
   process: it is either the client_write_IV (when the client is
   sending) or the server_write_IV (when the server is sending).

Does it mean that the module generates the nonce_explicit or the whole
GCMNonce. If it's the latter then the sequence number checking on the TLS
packet will not help.

Sandeep

---

From: Dr Stephen Henson <[email-masked]>
Date: Thu, 06 Mar 2014 19:13:56 +0000

On 06/03/2014 19:02, Sandeep Kumar wrote:
> Does it mean that the module generates the nonce_explicit or the whole GCMNonce.
> If it's the latter then the sequence number checking on the TLS packet will not
> help.
> 

When I first looked through the specs I thought the module was required to
generate the whole of GCMNonce but that would make TLS 1.2 use of AES GCM with
FIPS140-2 impossible as the salt part comes from the PRF.

Fortunately one of the permissible schemes allows the salt part to be specified
by the API and only requires generation of the nonce_explicit part.

Steve.

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 6 Mar 2014 14:18:45 -0500

> why meeting it increases confidence in the property we actually care about, namely correctness of the entire implementation. It's particularly
> a problem when the goal is rendering the certification meaningless by excluding as much as possible from the scope. Substance matters.

Evaluations are time-consuming and expensive. Go ask on the OpenSSL list how much it cost to get their stack certified.  I wouldn't want to guess the cost if you're starting from scratch with a TLS implementation.

>Sure, but I don't quite appreciate why the module can't generate the TLS sequence number itself.

I don't know if a certified module is allowed to "give out" the IV, or if it's only allowed to give out the plaintext.

> Is there some complicated interaction of specs that I'm neglecting?

Well, as a start, it certainly appears that you are unfamiliar with FIPS evaluation.

> So it's a little sticker saying "We did nothing to show this works. Have fun!"?

I never said that.  And how much do you warrant your software? :)  For a less flip answer, start here: http://csrc.nist.gov/groups/STM/cmvp/documents/140-1/140val-all.htm

	/r$

---

From: Bodo Moeller <[email-masked]>
Date: Thu, 6 Mar 2014 12:19:02 -0800

Salz, Rich <[email-masked]>:

I don't know if a certified module is allowed to "give out" the IV, or if
> it's only allowed to give out the plaintext.
>

I'm not quite sure what you mean here.

When encrypting, if the module generates the IV in an unpredictable way, it
will have to output that IV because we need to provide it to the recipient.

When decrypting, the IV will have to be provided to the module.  There's no
need for the module to output that IV because it's part of the input anyway.

Bodo

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 6 Mar 2014 18:15:32 -0500

> I'm not quite sure what you mean here.

Yeah, I don't know what I meant either.  I'll blame jetlag and ... something else, not sure what.  Sorry 'bout that.

---

From: Stephen Kent <[email-masked]>
Date: Fri, 07 Mar 2014 04:30:47 -0500

Watson,

> easily tested: they live at a higher level.
Eval is performed by NIST for algs and modes, focusing on correctness of
the implementation, protection of keys, etc. There is no eval criteria for
TLS, nor IPsec, etc. So, while it's true that we really want a security 
protocol
to work securely, that's not an option in most cases. The motivation for 
a vendor
to have a product evaluated, relative to NIST criteria, is that this 
makes the
product easier for US Gov folks to purchase. The bigger the collection 
of SW,
firmware, or HW that has to be evaluated, the longer it takes, the more 
it costs,
and the faster the eval becomes invalid, because you made a change to 
the evaluated
stuff (even for reasons largely irrelevant to the core security functions).

> restricts the module design, but it doesn't prevent compliance with
Well, you might be able to do that, but the receiver would have to know that
it has to take the sequence number and use it as the IV, right? That would
have to be negotiated, if one is to allow other IV generation approaches
as well.

Steve

---

From: Stephen Kent <[email-masked]>
Date: Tue, 18 Mar 2014 12:05:14 -0400

Sandeep,

Sorry to be so late in replying.
> ....
> GCMNonce. If it's the latter then the sequence number checking on 
> the TLS packet will not help.
The part of the structure labeled "salt" above is called the "fixed 
field" in NIST 800-38.
The FIPS 140-2 implementation guidance doc says that if one generates 
the explicit nonce
deterministically, e.g., using a counter or LFSR, then the fixed field 
represents the
"name" of the module and the name needs to be long enough to allow for 
at least 2**32
distinct values. The name need not be generated internal to the module; 
according to
Additional Comment #2, page 136, this field may be assigned by a user. 
So, in the context
of interest, TLS could supply the salt to an evaluated module, but the 
module would
generate the explicit nonce internally. There is separate test guidance 
if the whole IV
were to be generated randomly, but we're not discussing that approach 
here, based on
the RFC 5288 description you cited above.

Steve