Subject: [babel] babel-hmac: key requirements

From: "STARK, BARBARA H" <[email-masked]>
Date: Thu, 10 Jan 2019 23:14:25 +0000

The recent discussion around the HMAC key suggests to me that we need to have some text somewhere that discusses expectations for the authentication key. Or else we're almost guaranteed to achieve non-interoperability across implementations.

As a reminder (from that discussion), OSPF (RFC 5709) has this:
   (1) PREPARATION OF KEY
       In this application, Ko is always L octets long.
       If the Authentication Key (K) is L octets long, then Ko is equal
       to K.  If the Authentication Key (K) is more than L octets long,
       then Ko is set to H(K).  If the Authentication Key (K) is less
       than L octets long, then Ko is set to the Authentication Key (K)
       with zeros appended to the end of the Authentication Key (K),
       such that Ko is L octets long.
where
      H    is the specific hashing algorithm (e.g., SHA-256).
      Ko   is the cryptographic key used with the hash algorithm.
      B    is the block size of H, measured in octets
           rather than bits.  Note well that B is the
           internal block size, not the hash size.
              For SHA-1 and SHA-256: B == 64
              For SHA-384 and SHA-512: B == 128     
      L    is the length of the hash, measured in octets
           rather than bits.

I've also discovered that the HMAC RFC (RFC 2104) says:
   The definition of HMAC requires a cryptographic hash function, which
   we denote by H, and a secret key K. We assume H to be a cryptographic
   hash function where data is hashed by iterating a basic compression
   function on blocks of data.   We denote by B the byte-length of such
   blocks (B=64 for all the above mentioned examples of hash functions),
   and by L the byte-length of hash outputs (L=16 for MD5, L=20 for
   SHA-1).  The authentication key K can be of any length up to B, the
   block length of the hash function.  Applications that use keys longer
   than B bytes will first hash the key using H and then use the
   resultant L byte string as the actual key to HMAC. In any case the
   minimal recommended length for K is L bytes (as the hash output
   length). See section 3 for more information on keys.
and elsewhere it says
   The key for HMAC can be of any length (keys longer than B bytes are
   first hashed using H).  However, less than L bytes is strongly
   discouraged as it would decrease the security strength of the
   function.  Keys longer than L bytes are acceptable but the extra
   length would not significantly increase the function strength. (A
   longer key may be advisable if the randomness of the key is
   considered weak.)

Note that OSPF doesn't quite follow the HMAC RFC -- it hashes the input key when that key length is > L (where HMAC says this is done when key length is < B). 
We also noted that the Bird code applies ASCII (which is the same as UTF-8) encoding to an input authentication key string (and not  hex, base64, or UTF-16). 

My preference is that we have something in the HMAC draft, not too much unlike the OSPF text.
I think, based on the HMAC RFC statement that cryptographic keys with length > L don't add value, it makes sense to restrict the length to L (instead of B). Like OSPF does.
I like UTF-8. It's worked very well for Wi-Fi WPA1 and WPA2 passphrases. But I also recognize that this prevents full use of the available bits. Which is why some Wi-Fi implementations also support direct input of the cryptographic key in hex format. Note that passphrases are used to generate the cryptographic key using PBKDF2 (from RFC 2898) with the SSID as the salt. In order to prevent confusion when a Wi-Fi implementation is provided with a "key", passphrases are required to be between 8 and 63 characters. A string that is exactly 64 characters is the hex cryptographic key (which means it has to be restricted to hex characters, and it requires no PBKDF2 manipulation). This means Wi-Fi WPA1 and WPA2 don't support any length of key other than 256 bit. Which is sort of limiting for anything that wants to be able to easily add support for new future hash algorithms. Wi-Fi deals with support of new hashing algorithms by creating a new WPA (WPA3 coming soon to stores near you and online). Much of this Wi-Fi stuff seems unnecessarily complex for what we need, and I think we should lean towards the HMAC approach.

Here is my suggestion:
--------------------------------------------
Add new section, somewhere between the end of the Conceptual Overview (section 2) and before The Interface Table (section 3.1).

# Preparation of the HMAC Key

All HMAC algorithms require a cryptographic key. Some 
manipulation of an input string may be required, to prepare
it for use as the cryptographic HMAC Key. To allow the
same string to be input to different Babel nodes, 
all Babel nodes will need to do the same string manipulation.

In the description below, the following nomenclature, which
is consistent with [RFC2104], is used:

      H    is the specific hashing algorithm (e.g., SHA-256).
      K    is the entered Authentication Key (input string).
      Ko   is the cryptographic key used with the hash algorithm
            (referred to as the HMAC Key in this document).
      B    is the block size of H, measured in octets rather than bits.  
      L    is the length of the hash, measured in octets rather than bits.

The HMAC Key (Ko) will always be L octets long.

If the entered Authentication Key (K) length is exactly 2L and
uses only the characters 0-9 and a-f or A-F, it MUST be used as
a hex-encoded string, and Ko is equal to K.

Otherwise, the Authentication Key MUST be used as a UTF-8
encoded string. If the Authentication Key (K) is L octets long,
then Ko is equal to K.  If the Authentication Key (K) is more than
L octets long, then Ko is set to H(K).  If the Authentication Key (K) is less
than L octets long, then Ko is set to the Authentication Key (K)
with zeros (bits) appended to the end of the Authentication Key (K),
such that Ko is L octets long.

Barbara

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 12 Jan 2019 13:32:19 +0100

Barbara,

I think we must carefully distinguish between:

  - the key K being used by HMAC;
  - how the key is computed;
  - the user interface (e.g. the config file), which allows the user (or
    the managing software, e.g. HNCP) to express the key computation.

The key K is well defined in all cases -- it's a string of octets the
length of the HMAC bloc size.

Computation of the key should not happen on the router -- the router
should be given the computed key, and any secrets used to compute the key
should not be distributed on the routers.  For example, if the key is
obtained by hashing a passphrase, then the original passphrase should not
be stored on the router.  Similarly, if the key is drawn randomly (e.g. by
an automated key distribution protocol), then the PRNG state should not be
exposed to the routers.

> As a reminder (from that discussion), OSPF (RFC 5709) has this:

[...]

> I've also discovered that the HMAC RFC (RFC 2104) says:

Both of these look extremely naive to my untrained eyes (and 2104 is
confusing).  Better approaches include:

  - drawing the key randomly before distribution (RFC 4086);
  - using a proper KDF to derive a key from a passphrase (see e.g. RFC 5869).

As mentioned above, the key generation should happen offline, and is
therefore out of scope for this draft.

> We also noted that the Bird code applies ASCII (which is the same as
> UTF-8) encoding to an input authentication key string (and not  hex,
> base64, or UTF-16).

Internally, BIRD uses the raw binary string.

The user interface allows entering the key as a quoted string.  BIRD
doesn't interpret the octets entered in the string, so they could be
encoded as UTF-8, ISO 8859-15, Shift-JIS, whatever, depending on your
terminal configuration.  (See the terminal TEXT in cf-lex.l in the BIRD
sources.)

> My preference is that we have something in the HMAC draft, not too much

I disagree.  RFC 5709 is very naive, if a key is generated from user
input, that should be done offline, and using a proper KDF, not the naive
procedure described in 5709.

> I like UTF-8.

So do I -- but this is all out of scope for this draft, since key
generation should happen offline.

If you believe that the key derivation procedure should be described, then
this should happen in a separate draft (that can be used with both
Babel-HMAC and OSPF static keying), or perhaps in an informative appendix
to this draft.  In that case, we'd need to consult a cryptographer in
order to select a safe KDF.

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Sat, 12 Jan 2019 16:05:04 +0200

> therefore out of scope for this draft.

+1.

If one really cares about security, few bytes of ASCII is not really what you want to use as key; ideally, very close to random bits, and plenty of them.

One way of sourcing them is by deriving them from passphrase using some computation which is hard to brute-force though, so even if I use password 'Markus rul3s', someone is unlikely to bother trying to bruteforce it and the clever 3 is sufficient as a security mechanism if it takes (say) minute per attempt on modern CPU.

e.g. RFC5869 is a good starting point (or its SHA-2 application in RFC6234).

> procedure described in 5709.

+1.

All the classic 'let's HMAC and call it done' mechanisms are completely obsolete as security mechanisms, unless the input to HMAC is in and of itself pseudorandom garbage of sufficient length and not passphrase in the first place.

Disclaimer: These are 'old school' recommendations, current KDF state of the art is bit different IIRC but even these are much better than the good old IETF standard (toss MD5 in), or 'modern-ish' IETF standard (toss HMAC-SHA in) way.

Draft should possibly state that if passphrases are used, KDF of SOME SORT should be used, but the actual KDF is IMHO implementation matter and as long as all implementations can be configured with same bytes that come out of KDF they would interoperate.

Cheers,

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 12 Jan 2019 15:27:16 +0100

> Disclaimer: These are 'old school' recommendations, current KDF state of
> the art is bit different IIRC

I'd be interested in a pointer, if you have one handy.

Thanks,

-- Juliusz

---

From: Markus Stenberg <[email-masked]>
Date: Sat, 12 Jan 2019 16:30:42 +0200

> I'd be interested in a pointer, if you have one handy.

https://password-hashing.net

-Markus

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 12 Jan 2019 15:42:31 +0100

> Draft should possibly state that if passphrases are used, KDF of SOME
> SORT should be used, but the actual KDF is IMHO implementation matter
> and as long as all implementations can be configured with same bytes
> that come out of KDF they would interoperate.

So it looks like I should add something to the Security Considerations
section.  What about

  In addition to the above, the mechanism described in this draft relies
  on an attacker being unable to guess the HMAC key, whether by brute
  force or by other means.  Ideally, the HMAC key SHOULD be generated
  randomly using a strong random number generator [RFC4086] and
  distributed to the routers using some sufficiently secure mechanism
  (e.g., ssh [RFC4251]).  If the HMAC key is generated from user input (a
  "passphrase"), then the passphrase SHOULD NOT be stored on the
  individual routers: the key SHOULD be generated on a secure host using
  a sufficiently strong Key Derivation Function (KDF) RFC5869] [RFC6234]
  and, again, the resulting distributed to the routers using some
  sufficiently secure mechanism.  In order to make offline key generation
  practical, implementations SHOULD use the key provided by the user with
  no transformation of any kind.

---

From: Juliusz Chroboczek <[email-masked]>
Date: Sat, 12 Jan 2019 16:30:23 +0100

> https://password-hashing.net

Interesting, thanks.  Roughly speaking, they're concerned about ASIC and
FPGA implementations of brute-force cracking, so they design hashing
algorithms that require absolute shitloads of RAM.

-- Juliusz

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Mon, 14 Jan 2019 17:02:22 +0000

My goal in this discussion is:
1. Getting rid of ambiguity in HMAC key format that is accepted as an input to a babel-hmac implementation on a device.
2. Understand how human beings are expected to interact with getting keys into an implementation, and making sure these expectations are reasonable.
....
> should not be distributed on the routers.  For example, if the key is obtained
> by hashing a passphrase, then the original passphrase should not be stored
> on the router.  Similarly, if the key is drawn randomly (e.g. by an automated
> key distribution protocol), then the PRNG state should not be exposed to the
> routers.

I'm fine with this, if this is the approach everyone agrees on. But the current draft makes no mention of this expectation, which has resulted in Toke's implementation accepting direct entry of a string it interprets as ASCII and will subsequently hash if the string is longer than the length of the hash (which is inconsistent with the above expectation). I don't blame Toke for doing this -- it seems perfectly reasonable given the lack of specification in the draft and the available tools. I'd like the expectations on the HMAC Key to be easily found by someone scanning the table of contents.

Here is a suggestion:
Insert new 2nd level header below 3 (Data Structures)
## The HMAC Key
The HMAC Key is the exact cryptographic key used with the hash algorithm. How the HMAC Key is provided (e.g., a configuration protocol, a user interface, a separate application that includes a computation algorithm, etc.)  is outside the scope of this specification. The provided HMAC Key MUST NOT be modified in any way prior to use with the hash algorithm. 
 
...

> this should happen in a separate draft (that can be used with both Babel-
> HMAC and OSPF static keying), or perhaps in an informative appendix to this
> draft.  In that case, we'd need to consult a cryptographer in order to select a
> safe KDF.

No, I don't think that's needed, and I don't think we have anything to say about OSPF static keying. What I do think is needed is a lack of ambiguity around what the "HMAC Key" is and a statement that no modification of the provided HMAC Key is permitted. If that's the approach being taken.

Barbara

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 15 Jan 2019 20:44:24 +0100

> The provided HMAC Key MUST NOT be modified in any way prior to use with
> the hash algorithm.

Which draft are we speaking about?  The management draft or the HMAC draft?

-- Juliusz

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Tue, 15 Jan 2019 21:17:36 +0000

> > The provided HMAC Key MUST NOT be modified in any way prior to use
> > with the hash algorithm.
> 

The HMAC draft. 

>From your comments, it seems that the "HMAC Key" referenced throughout babel-hmac is the exact set of bits used to compute the HMAC. If this is true, then this is an important fact that is not currently obvious from reading the draft. So the HMAC Key that is an input to an implementation of this spec must not be modified by the implementation prior to use.

An implementation of babel-hmac that hashes a provided HMAC Key value longer than the length of the hash must be considered in violation of the babel-hmac spec. Any user interface that accepts input of ASCII characters to generate an HMAC Key must be separate from the babel-hmac implementation. The existence of OSPF key "preparation" rules and the base HMAC RFC rules key preparation rules means the babel-hmac text needs to unambiguously state that such preparation is *not* done to an "HMAC Key" prior to its use in babel-hmac.

This will impose a requirement on the info-model to treat the HMAC Key as a binary field (like the router-id).

BTW, I'm fine with the text you proposed for the security section. But it doesn't solve the problem of ensuring there is no ambiguity regarding non-"preparation" of the key.
Barbara

---

From: Toke Høiland-Jørgensen <[email-masked]>
Date: Tue, 15 Jan 2019 22:35:53 +0100

"STARK, BARBARA H" <[email-masked]> writes:

>>From your comments, it seems that the "HMAC Key" referenced throughout
>>babel-hmac is the exact set of bits used to compute the HMAC. If this
>>is true, then this is an important fact that is not currently obvious
>>from reading the draft. So the HMAC Key that is an input to an
>>implementation of this spec must not be modified by the implementation
>>prior to use.
>
> An implementation of babel-hmac that hashes a provided HMAC Key value
> longer than the length of the hash must be considered in violation of
> the babel-hmac spec.

So this means you want to specify that a key MUST be exactly (or at
most?) $blocksize bytes long?

> Any user interface that accepts input of ASCII characters to generate
> an HMAC Key must be separate from the babel-hmac implementation.

How do you define "separate from"?

-Toke

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 15 Jan 2019 23:02:23 +0100

> The HMAC draft.

Please consider me utterly confused.

The HMAC draft was carefully written to be agnostic about key distribution
policies.  It assumes that one or more HMAC keys are associated to each
interface (Section 3.1), and takes no stand about how these keys got into
the interface data strcture.

For example, a key might come from a config file, it might come from
a configuration protocol, or it might be the result of a Diffie-Hellman
key exchange.  Babel-HMAC doesn't care, it just consults the interface
data structure and grabs the keys that are there.

So what do you mean by "provided" in the sentence you suggest?  Who's the
mysterious entity doing the providing, and who is she providing the keys to?

(The point I'm making is that you obviously have a particular management
interface in mind -- probably a config file, or perhaps some kind of XML
over HTTP thing --, and that management interfaces are out of scope for
this draft.)

-- Juliusz

---

From: Juliusz Chroboczek <[email-masked]>
Date: Tue, 15 Jan 2019 23:26:40 +0100

Let's be pedantic here -- let's distinguish the objects we manipulate from
the concrete syntax that we use in our config files.

> most?) $blocksize bytes long?

An HMAC key is a string of bytes the length of which is exactly the block
size.  (RFC 2104 confuses matters by distinguishing the "key" and the
"actual key".  Please ignore this nonsense.)

The actual concrete representation that you put in your config file is
a sequence of characters (which happens to be serialised as a sequence of
bytes using some character encoding, but that's irrelevant).  How this
sequence of characters is parsed into a sequence of bytes is outside the
scope of the Babel-HMAC draft.

Babeld requires a hex string in the config file, which to me is the
obviously right thing to do, but makes Dave angry.  Bird does something
different, which I happen to believe is silly.

> How do you define "separate from"?

The algorithm defined in the Babel-HMAC draft assumes that at any time
your interface data structure contains one or more HMAC keys (Section 3.1).
Describing how these bytes got into the interface structure is not the job
of the Babel-HMAC draft, it's the job of the management draft, and of the
documentation of your config file format.

(Although, the be fair, we could add an informative appendix that explains
that hex is the right thing to do, that no post-processing should happen,
and that if you do anything else you need your head examined.)

(The other day, I was implementing in Go an undocumented protocol that has
only been implemented in Javascript before.  They take an SHA-1 hash,
interpret it as a sequence of twenty 8-bit Unicode codepoints, and then
encode the result in UTF-16.  I simply cannot conceive the kind of
intellectual sloppiness that yielded this brain-damage.)

-- Juliusz, feeling grumpy

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Wed, 16 Jan 2019 15:45:59 +0000

I don't seem to be communicating well what I'm looking for. An informative appendix doesn't solve my problem. The advice is nice, but it's not what I'm needing.
Let me try saying this differently.

If it weren't for OSPF defining 2 different keys (the entered key and the cryptographic key) and the HMAC RFC 2104 defining the jey as something of variable length that gets hashed when it's longer than the block size, I/we wouldn't have a problem. But because of those specs (and RFC 2104 is normatively referenced), the term "HMAC key" is ambiguous. A careful reader might not see it as ambiguous and understand what's implied by the text; but all readers aren't careful.

Therefore, I would like for babel-hmac to resolve this ambiguity by providing a prominent (hard to miss) definition of "HMAC key".

Here's another suggestion for how this might be achieved.
Insert a section under Data Structures of:

## The HMAC Key
The HMAC key is a string of bytes the length of which is exactly the block size of the HMAC algorithm being used. Note this is different  from the [RFC2104] definition.

----------------------------
A second problem I have (which doesn't need to be resolved by text in babel-hmac, but can be dealt with in information-model) is the format to use for supplying an input that becomes an HMAC key. I think we're somewhere between binary and hex at this point. I don't care which, but I need to choose one or the other.

Barbara

---

From: Juliusz Chroboczek <[email-masked]>
Date: Wed, 16 Jan 2019 17:53:16 +0100

> The HMAC key is a string of bytes the length of which is exactly the
> block size of the HMAC algorithm being used. Note this is different
> from the [RFC2104] definition.

Good idea.  I'll do that.

-- Juliusz

---

From: "STARK, BARBARA H" <[email-masked]>
Date: Wed, 16 Jan 2019 17:06:45 +0000

> > from the [RFC2104] definition.

Thx. That will resolve my comment. With this, I'm fine with publication of the draft.

I'll start a separate thread to handle my question about the information-model datatype.
Barbara