New encryption scheme may use HKDF in a sub-optimal (and cryptographically unproven) way.

[marti4d]

Have you checked borgbackup docs, FAQ, and open GitHub issues?

Yes

Is this a BUG / ISSUE report or a QUESTION?

Issue

Describe the problem you're observing.

Looking at Borg's encryption design document and the discussion in Issue #3814, it seems that Borg may be using HKDF in a way that is unproven by cryptanalysis and makes sub-optimal use of the randomness introduced by SessionId by using it as the salt parameter of HKDF instead of feeding it into the info parameter (called context in the diagram).

In the blog post by @soatok entitled Understanding HKDF, he discusses the formal proofs provided for HKDF, and how many developers accidentally misuse the algorithm in ways that invalidate those proofs. It appears that the algorithm was designed so that the same "(salt, IKM)" would be used across all iterations of HKDF for a given key being used in a given context (in this case, the master keying material in the context of a Borg archive), and the cryptographic proofs do not extend to "same IKM, varying salt". If different keying material is desired for the same IKM within the same context, it should be produced by varying the info parameter, not the salt.

In fact, according to RFC 5869 Section 3.3, if the IKM is already strong and uniformly-random, the HKDF-Extract stage can just be skipped altogether (which is the only step that uses salt). Borg's IKM already meets that requirement, so it would be permissible (and still within the cryptographic proof for HKDF) for Borg to do away with the first stage altogether (including eliminating the salt parameter) and just directly use the 512-bit crypt_key in the HKDF-Expand stage.

So, if we assume that it's okay to get rid of the HKDF-Extract stage (which RFC 5869 supports), and since we're only extracting a single 256-bit output block from HKDF-Expand, the session key derivation becomes a single iteration of HKDF-Expand with crypt_key as the PRK and session_id | flavor_string as the info:

session_key = HMAC(crypt_key, session_id | flavor_string | 0x01)

(Technically, you need to have the 0x01 concatenated in there to comply with the proofs from the paper, although I'd wager that it doesn't add much in terms of security, since it's already being concatenated with a random number).

[ThomasWaldmann]

Thanks for looking at borg2's crypto!

Just to be a bit more specific about what we are discussing, this is (besides our test suite) currently the only usage of hkdf in master branch in borg.crypto.key module:

    def _get_session_key(self, sessionid):
        assert len(sessionid) == 24  # 192bit
        key = hkdf_hmac_sha512(
            ikm=self.crypt_key,
            salt=sessionid,
            info=b"borg-session-key-" + self.CIPHERSUITE.__name__.encode(),
            output_length=32,
        )
        return key

What do we have there?

• self.crypt_key - this is the static key material from the (encrypted) on-disk borg key, at least 512b of random.
• sessionid - 192b of random, initialised freshly for each borg invocation (= for each backup)

[soatok]

Right, and using a static key (self.crypt_key) with a variable salt (sessionid) is the exact antipattern for HKDF that @marti4d reported above.

Key	Salt	Info	Notes
Static	Static	Static	Deterministic key derivation
Static	Variable	Static	Anti-pattern, only PRF security, not KDF security -- Borg2 is here
Variable	Variable	Static	OK
Variable	Static	Static	OK
Static	Static	Variable	Multiple keys derived from input key
Static	Variable	Variable	Anti-pattern, only PRF security, not KDF security
Variable	Variable	Variable	OK
Variable	Static	Variable	OK

[RonnyPfannschmidt]

If I read the rfc correct, then the session id should go to info instead of salt

[RonnyPfannschmidt]

The RFC in confusing in the sense that it recommended the salt to be random and the info to be a context identifier,the whole thing is pretty confusing

[RonnyPfannschmidt]

The Blog post is most instructive

As far as I understand borg with actual keys doesn't need hkdf as presented the input key is already matching the requirements

[marti4d]

The Blog post is most instructive

As far as I understand borg with actual keys doesn't need hkdf as presented the input key is already matching the requirements

Exactly -- HKDF was really designed for deriving keys after Diffie–Hellman exchange, where the IKM is not uniformly random.

Since Borg's master key is already a PseudoRandom Key (PRK), there is no need for the "HKDF-Extract" stage. Only the "HKDF-Expand" stage is needed, with the random sessionid (and the crypto suite "flavor") as the info parameter, and only a single iteration.

Therefore, if you follow RFC 5869 definition for the HKDF-Expand stage, it simplifies to:

Input:
PRK = self.crypt_key
info = sessionid | flavor_string
L = 32 bytes (`session_key` length)

Output:
OKM = Will be the desired `session_key`

Other:
flavor_string = b"borg-session-key-" + self.CIPHERSUITE.__name__.encode()
HashLen = 64 bytes (length of a SHA-512 hash)

The output OKM is calculated as follows:

N = ceil(L/HashLen) = ceil(32/64)  = 1
T = T(1)
OKM = first 32 octets of T

where:
T(0) = empty string (zero length)
T(1) = HMAC-Hash(PRK, T(0) | info | 0x01)

Now, let's simplify:

T = T(1) = HMAC-Hash(PRK, (empty string) | info | 0x01)

OKM = first 32 octets of T

**Finally, substituting our values**

OKM = truncate32(HMAC-SHA-512(self.crypt_key, sessionid | flavor_string | 0x01))

One last note -- I'm pretty sure we can all agree (and the design paper for HKDF seems to second this) that there's really no reason to have the 0x01 byte in there -- They added it as an iterator in case you want to derive more than a single block of keying material.

Since that's not the case here, that simplifies the equation down to:

OKM = truncate32(HMAC-SHA-512(self.crypt_key, sessionid | flavor_string))

Essentially, when you are using HKDF with an already pseudorandom IKM, and you only want to derive a single hash block (or less) from it, it basically simplifies down to a simple truncate(HMAC(key, info), output_size) call.

I think it makes sense for Borg's session id to be derived as follows (in Python):

def _get_session_key(self, sessionid):
    assert len(sessionid) == 24  # 192bit
    key_64 = hmac_sha512(
        key=self.crypt_key,
        message=sessionid + b"borg-session-key-" + self.CIPHERSUITE.__name__.encode(),
    )
    return key_64[:32]

[marti4d]

Perhaps @soatok would know more than me, but since Borg is using HKDF with input key material that is already pseudorandom, I guess technically what it's doing now is sub-optimal, but likely not broken. IE there likely isn't an actual security problem here (although that fact is more difficult to prove than it would be if Borg were just to use the HMAC construction I suggested above). Does that sound right?

[soatok]

From the perspective of "I'm an academic and I want to write a formal model or security proof", only having PRF security when KDF security is desired is a minor nuisance.

From the real world perspective, PRFs are pretty damn good.

[ThomasWaldmann]

@soatok but given our circumstances (crypt_key being fully random), there is no need to require or desire KDF security and we would be totally fine with PRF security, right?

At NIST, they even describe a one-step kdf there:

https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Cr2.pdf in section 4 (that's a newer revision of the document you linked from your blog post)

For our needs, that seems to boil down to just a truncated-hmac (as in #7953 (comment))

Or, as they also allow a hash instead a hmac, even simpler (if I understood correctly):

truncate(sha512(crypt_key + sessionid + b"context-info-constant-string"), 32)
# or, even simpler, this:
sha256(crypt_key + sessionid + b"context-info-constant-string")

Note: we tended to use sha512, considering it is faster on 64bit CPUs when done in software. But, considering that there are more and more CPUs with hw accelerated sha2 and that this computation is only done once per session, we can just use the simpler code. Update: for borg create, the session key is derived once, but for reading existing repo content (e.g. borg extract), the decryption key must be derived per object (with the related sessionid stored with that object).

[ThomasWaldmann]

See #7955 where I implemented the first approach with hmac_sha256 (in the first commit, the 2nd commit is just removing unused code).

[soatok]

@soatok but given our circumstances (crypt_key being fully random), there is no need to require or desire KDF security and we would be totally fine with PRF security, right?

I haven't audited your design, I was just tagged and notified, so I can't say for sure. :)

What I can say is, to most people, "KDF security" vs "PRF security" only matters in rare situations, like "I'm doing fun things with Diffie-Hellman" or "I invented a new kind of commutative algebraic group that aims to be post-quantum secure and want to use its output for a symmetric key".

[marti4d]

Or, as they also allow a hash instead a hmac, even simpler (if I understood correctly):

truncate(sha512(crypt_key + sessionid + b"context-info-constant-string"), 32)
# or, even simpler, this:
sha256(crypt_key + sessionid + b"context-info-constant-string")

Note: we tended to use sha512, considering it is faster on 64bit CPUs when done in software. But, considering that there are more and more CPUs with hw accelerated sha2 and that this computation is only done once per session, we can just use the simpler code. Update: for borg create, the session key is derived once, but for reading existing repo content (e.g. borg extract), the decryption key must be derived per object (with the related sessionid stored with that object).

Hmm... Actually, I guess that makes a lot of sense -- HMAC really is meant for just that - calculating MACs with hash functions. Specifically, it was designed to prevent forced collisions when the attacker controls the plaintext (as is the case when a message is being authenticated). Since Borg controls the entire string that would be hashed, even HMAC is likely overkill.

FYI FIPS 180 defines SHA-512/256 for exactly the reason you discussed above -- on 64-bit machines, it's often faster to just use SHA-512 and truncate it.

So your construction above, but following the minor changes from the FIPS paper to produce sha512_256 seems like a reasonable solution:

session_key = sha512_256(crypt_key + sessionid + b"context-info-constant-string")

[ThomasWaldmann]

I had the impression that hw acceleration accelerates sha256 (but not sha512, or not as fast), so I stopped optimising for sha512 if sha256 gives enough bits.

[marti4d]

I had the impression that hw acceleration accelerates sha256 (but not sha512, or not as fast), so I stopped optimising for sha512 if sha256 gives enough bits.

Ah, you're right. I see they won't be accelerating SHA-512 until Arrow Lake

Either way, as you said -- This isn't so critical that you're going to be performing thousands of hashes per second. Probably best to favour the simple path and just use SHA-256 (like you had suggested previously). It looks like it is both faster and easier.

[marti4d]

WRT #7955, it seems to me also that you have permission from FIPS to just use the SHA-256 hash function without the HMAC construction. Either would be okay -- Obviously the naked hash function would be a bit cheaper. It seems FIPS doesn't really state a preference.

[ThomasWaldmann]

Updated the PR to simply use sha256, also added some comments, flavour -> domain and updated the diagram.