HKDF methods Expand and DeriveKey may generate corrupt output if 'info' and 'output' spans overlap

[andreimilto]

Description

User may supply overlapping spans as arguments info and output to the method HKDF.Expand. They may do so inadvertently or on purpose (e.g., if info will be no longer needed, they may decide to write the output directly into info to avoid unnecessary memory allocation for the output and reduce memory footprint). The method won't throw ArgumentException.

Expand writes output block-by-block, each block is generated by running the info through HMAC. If spans output and info overlap, writing one of the output blocks will modify the info and cause all the following output blocks (if any) to be invalid (computed for different info).

DeriveKey method uses Expand under the hood, so it is subjected to this problem too.

Illustration

Example 1:

byte[] prk = new byte[32];
byte[] info = new byte[64];
byte[] output = info;

HKDF.Expand(HashAlgorithmName.SHA256, prk, output, info);

// Expected value of 'output':
// 224, 85, 77, 187, 82, 30, 209, 96, 139, 180, 92, 98, 118, 111, 136, 68, 14, 47, 58, 228, 103, 215, 77, 186, 31, 211, 151, 244, 164, 46, 152, 253, 22, 124, 57, 137, 118, 144, 212, 164, 130, 145, 153, 172, 244, 110, 232, 164, 185, 232, 55, 182, 160, 145, 30, 122, 59, 192, 132, 49, 71, 152, 88, 179

// Actual value of 'output':
// 224, 85, 77, 187, 82, 30, 209, 96, 139, 180, 92, 98, 118, 111, 136, 68, 14, 47, 58, 228, 103, 215, 77, 186, 31, 211, 151, 244, 164, 46, 152, 253, 28, 152, 182, 90, 167, 151, 73, 167, 4, 223, 241, 200, 117, 212, 10, 138, 15, 233, 197, 158, 185, 124, 47, 216, 204, 204, 129, 232, 30, 186, 204, 65

Example 2:

var ikm = new byte[32];
var salt = new byte[32];

var buffer = new byte[128];
var info = buffer.AsSpan().Slice(0, 64);
var output = buffer.AsSpan().Slice(60, 64);

HKDF.DeriveKey(HashAlgorithmName.SHA256, ikm, output, salt, info);

// Expected value of 'output':
// 172, 123, 193, 152, 101, 162, 17, 66, 171, 216, 98, 225, 37, 223, 75, 218, 132, 136, 71, 80, 12, 22, 125, 64, 63, 27, 212, 255, 132, 8, 36, 105, 171, 126, 54, 101, 167, 164, 84, 70, 178, 14, 209, 132, 190, 173, 9, 22, 29, 248, 138, 190, 251, 103, 106, 197, 210, 193, 39, 96, 213, 148, 221, 10

// Actual value of 'output':
// 172, 123, 193, 152, 101, 162, 17, 66, 171, 216, 98, 225, 37, 223, 75, 218, 132, 136, 71, 80, 12, 22, 125, 64, 63, 27, 212, 255, 132, 8, 36, 105, 183, 96, 0, 94, 58, 127, 93, 192, 187, 170, 243, 216, 48, 149, 108, 144, 141, 5, 245, 16, 12, 186, 172, 48, 12, 194, 237, 63, 200, 37, 231, 109

Suggested Solution

Suggestion 1:
Check whether the spans info and output overlap, and if they do, throw exception:

if (output.Overlaps(info))
    throw new ArgumentException(...);

Suggestion 2:
Maybe it's a good idea to check all pairs of input and output spans in HKDF and throw exception if there's an overlap in any of them:

• In Extract - ikm and prk, salt and prk
• In Expand - prk and output, info and output
• In DeriveKey - ikm and output, salt and output, info and output

This would make the API style more consistent and potentially safer, than if implementing only the info-output overlap check from the Suggestion 1.
I wasn't able to reproduce this issue with span pairs other than info-output, but I think it may be possible given different HMAC implementation.

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

Tagging subscribers to this area: @bartonjs, @vcsjones, @krwq
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Description

User may supply overlapping spans as arguments info and output to the method HKDF.Expand. They may do so inadvertently or on purpose (e.g., if info will be no longer needed, they may decide to write the output directly into info to avoid unnecessary memory allocation for the output and reduce memory footprint). The method won't throw ArgumentException.

Expand writes output block-by-block, each block is generated by running the info through HMAC. If spans output and info overlap, writing one of the output blocks will modify the info and cause all the following output blocks (if any) to be invalid (computed for different info).

DeriveKey method uses Expand under the hood, so it is subjected to this problem too.

Illustration

Example 1:

byte[] prk = new byte[32];
byte[] info = new byte[64];
byte[] output = info;

HKDF.Expand(HashAlgorithmName.SHA256, prk, output, info);

// Expected value of 'output':
// 224, 85, 77, 187, 82, 30, 209, 96, 139, 180, 92, 98, 118, 111, 136, 68, 14, 47, 58, 228, 103, 215, 77, 186, 31, 211, 151, 244, 164, 46, 152, 253, 22, 124, 57, 137, 118, 144, 212, 164, 130, 145, 153, 172, 244, 110, 232, 164, 185, 232, 55, 182, 160, 145, 30, 122, 59, 192, 132, 49, 71, 152, 88, 179

// Actual value of 'output':
// 224, 85, 77, 187, 82, 30, 209, 96, 139, 180, 92, 98, 118, 111, 136, 68, 14, 47, 58, 228, 103, 215, 77, 186, 31, 211, 151, 244, 164, 46, 152, 253, 28, 152, 182, 90, 167, 151, 73, 167, 4, 223, 241, 200, 117, 212, 10, 138, 15, 233, 197, 158, 185, 124, 47, 216, 204, 204, 129, 232, 30, 186, 204, 65

Example 2:

var ikm = new byte[32];
var salt = new byte[32];

var buffer = new byte[128];
var info = buffer.AsSpan().Slice(0, 64);
var output = buffer.AsSpan().Slice(60, 64);

HKDF.DeriveKey(HashAlgorithmName.SHA256, ikm, output, salt, info);

// Expected value of 'output':
// 172, 123, 193, 152, 101, 162, 17, 66, 171, 216, 98, 225, 37, 223, 75, 218, 132, 136, 71, 80, 12, 22, 125, 64, 63, 27, 212, 255, 132, 8, 36, 105, 171, 126, 54, 101, 167, 164, 84, 70, 178, 14, 209, 132, 190, 173, 9, 22, 29, 248, 138, 190, 251, 103, 106, 197, 210, 193, 39, 96, 213, 148, 221, 10

// Actual value of 'output':
// 172, 123, 193, 152, 101, 162, 17, 66, 171, 216, 98, 225, 37, 223, 75, 218, 132, 136, 71, 80, 12, 22, 125, 64, 63, 27, 212, 255, 132, 8, 36, 105, 183, 96, 0, 94, 58, 127, 93, 192, 187, 170, 243, 216, 48, 149, 108, 144, 141, 5, 245, 16, 12, 186, 172, 48, 12, 194, 237, 63, 200, 37, 231, 109

Suggested Solution

Suggestion 1:
Check whether the spans info and output overlap, and if they do, throw exception:

if (output.Overlaps(info))
    throw new ArgumentException(...);

Suggestion 2:
Maybe it's a good idea to check all pairs of input and output spans in HKDF and throw exception if there's an overlap in any of them:

• In Extract - ikm and prk, salt and prk
• In Expand - prk and output, info and output
• In DeriveKey - ikm and output, salt and output, info and output

This would make the API style more consistent and potentially safer, than if implementing only the info-output overlap check from the Suggestion 1.
I wasn't able to reproduce this issue with span pairs other than info-output, but I think it may be possible given different HMAC implementation.

Author:	andreimilto
Assignees:	-
Labels:	area-System.Security, untriaged
Milestone:	-

[vcsjones]

A 3rd option we could consider: if the buffer we are writing to overlaps any of the other input buffers, allocate/rent a temporary buffer and write to the temporary buffer. When all of the writing is done, copy it to the destination buffer. This is done in a few places that use symmetric encryption.

runtime/src/libraries/System.Security.Cryptography.Algorithms/src/Internal/Cryptography/OpenSslCipher.cs

Line 49 in f3ec6dc

if (input.Overlaps(output, out int overlapOffset) && overlapOffset != 0)

Or the reverse, copy the input buffer, perhaps to the stack if it's safe to do so, to a safe location that won't get overwritten during writing.

HKDF has small enough outputs and inputs that renting or allocating small buffers as needed shouldn't be too much of an issue, I would think.

[bartonjs]

@GrabYourPitchforks Are you in camp "make it throw", camp "make it work", or camp "do nothing, caller beware"? Do we have a solid precedent across the framework at large yet?

[andreimilto]

HKDF has small enough outputs and inputs that renting or allocating small buffers as needed shouldn't be too much of an issue, I would think.

HKDF doesn't impose any upper limit on the size of the inputs, so in theory any of the inputs - ikm, salt, prk or info - or all of them can be very large, although in practice that would be a very rare case - I agree with you. Outputs on the other hand are by design limited to hashOutputSize for Extract and 255 * hashOutputSize for Expand/DeriveKey, which makes them a more universal candidate for copying than inputs, I guess.

A 3rd option we could consider: if the buffer we are writing to overlaps any of the other input buffers, allocate/rent a temporary buffer and write to the temporary buffer.

The only legitimate reason I can think of why a user would direct the output into one of the inputs is to avoid unnecessary allocation of memory. A solution that involves extra allocation of the same amount of memory (only under the hood, hidden from the user's eyes) defeats the whole purpose, moreover it introduces an extra copying operation that a user could avoid if they allocated the memory themselves. Thus, if not informed properly about this behavior, a user might think that they optimize the performance by directing the output into one of the inputs, whereas in reality they would be instead making things slower. And if informed, they will be better off allocating the memory themselves. So, I think throwing an exception is a better option from the performance standpoint and it's also simpler: easier to explain to the user and easier to implement in code.

[vcsjones]

A solution that involves extra allocation

That's fair, but we might be able to be better than allocating either by using stackalloc for small values and CryptoPool.Rent for large values. The latter might allocate, and we can also put this in the documentation.

[GrabYourPitchforks]

@bartonjs I don't think we have FX-wide precedent. Most methods don't check. There have been some bugs in areas like globalization where we added "do these overlap?" checks after the fact. Honestly I'm in camp "caller beware" unless it makes sense for the scenario that overlapping buffers should be special-cased. For instance, when changing case of a Span<char> (globalization), it makes sense that somebody might want to mutate a buffer in-place since the elements are all being treated standalone and you'll end up with the same number of elements in both the source and the destination. (Of course, now that I've written that out, it sounds silly in hindsight that we detect and block this scenario.)

In this particular case, we're starting to deal with multiple combinations of parameters that all have to be checked against one another, and IMO it adds unnecessary complexity to the method. It falls under the same category of that we can't prevent another thread from mutating the contents of an array while our current thread is operating on that data. We just kindly ask people not to do it.

[bartonjs]

The fact that the API is intended to make a cryptographic key makes me a little skeptical of caller beware, since it might cease being reproducible.

Hmm.

[vcsjones]

@bartonjs @GrabYourPitchforks thoughts on what you want to proceed with here? Options:

1. Close this issue as "we don't typically check for this"
2. Make this a documentation note (but when about everything else that has the same behavior)
3. Check for overlap, throw (I don't think we do this anywhere else currently)
4. Check for overlap, use temporary buffers (we have prior art for this)

[bartonjs]

Throwing does have some prior art: https://github.com/dotnet/corefx/pull/38778/files, but I'm guessing that was in the same release.

I believe in the back of my head I was expecting to use temporary buffers for 6. Or maybe throw, since it was introduced in non-LTS and this is its first LTS.

[vcsjones]

I'm guessing that was in the same release.

Yeah. Either way changing is... probably... a breaking change. If someone was relying on stable output for given inputs, the outputs will be fixed (different as far as they are concerned), and throwing will definitely be noticed.

Unless there are objections I will submit a PR to use temp buffers if required.