Analysis and detail from Greg Hudson (in a separate comment so we can redact this if need be or for a time when we make this public):

In the initial impact analysis, I wrote "It may be difficult to get the 
KDC to do anything worse than crash" because the read and write overruns 
are necessarily long.  I need to revise this analysis, because 
krb5_parse_pac() will stop and return an error (after freeing the 
nascent PAC) if it encounters a buffer with an invalid offset or length.

This checking makes the read overrun fairly innocuous by itself.  In the 
necessarily long foray into KDC memory beyond the PAC encoding, we will 
(probably quickly) run into an invalid buffer specification and stop. 
In rare circumstances we might get far enough to crash.

However, the potential heap write overrun on 32-bit platforms is more 
potent than I had initially thought.  The crafted PAC would presumably 
contain some valid buffers containing the data the attacker wants to 
deposit into the heap, and then an invalid buffer to terminate parsing 
before the process crashes.  Execution would then continue with a 
corrupted heap.

On 10/13/22 01:26, Greg Hudson wrote:
> A fuzzer discovered that MIT libkrb5's krb5_pac_parse() will do a read
> overrun on the following input:
> 
>      00 00 00 10 00 00 00 00 06 FF FF FF 00 00 F5
> 
> That information has been made public (due to an apparent bug in the
> fuzzer, which erroneously determined that the bug had been fixed).  My
> analysis below has not been made public.
> 
> The first four bytes are the number of PAC buffers (little-endian).
> krb5_pac_parse() performs a bounds check on this value as follows:
> 
>      header_len = PACTYPE_LENGTH + (cbuffers * PAC_INFO_BUFFER_LENGTH);
>      if (len < header_len)
>          return ERANGE;
> 
> where cbuffers is a uint32_t value read from the first four bytes and
> len is the PAC encoding length.  This check is subject to an integer
> overflow attack.  Heimdal libkrb5 appears to have a similar bug:
> 
>      header_end = PACTYPE_SIZE + (PAC_INFO_BUFFER_SIZE * p->pac->numbuffers);
>      if (header_end > len) {
>       ret = EINVAL;
>       goto out;
>      }
> 
> where the numbuffers field also also has type uint32_t.
> 
> Both implementations also appear to have an integer overflow
> vulnerability where they allocate memory, on 32-bit platforms (MIT krb5
> and Heimdal respectively):
> 
>      pac->pac = (PACTYPE *)realloc(pac->pac,
>                                    sizeof(PACTYPE) + ((cbuffers - 1) * sizeof(PAC_INFO_BUFFER)));
> 
>      p->pac = calloc(1,
>                   sizeof(*p->pac) + (sizeof(p->pac->buffers[0]) * (tmp - 1)));
> 
> On 64-bit platforms there shouldn't be any possibility of overflow
> during allocation because the use of sizeof() will coerce the
> addition and multiplication operands to uint64_t.
> 
> I believe all of these lines of code have been present in their current
> form for a long time (since MIT krb5 1.7, and since 2006 in Heimdal).
> 
> Impact analysis:
> 
> PACs are typically only parsed after extraction from a decrypted ticket,
> so the attacker needs to produce a ticket that the victim can decrypt.
> This protects services to some extent (the attacker must possess the
> service key, so has the privileges of either the local KDC or the
> service).  But the KDC is an easier target; likely any authenticated
> attacker can print a ticket encrypted with their own long-term key and
> get the KDC to parse the PAC contained within.  (The MIT krb5 KDC prior
> to 1.20 and without Samba/FreeIPA integration won't try to parse PACs,
> and is therefore not vulnerable.)
> 
> It may be difficult to get the KDC to do anything worse than crash.  If
> the bounds check is defeated and (on a 32-bit platform) insufficient
> space is allocated for the buffers, there will be a heap write overrun
> with data partly of the attacker's choosing, but since the buffer count
> must be very large, it seems likely that the KDC process will crash on
> either a read or a write before returning from krb5_parse_pac().

Created attachment 17565 [details]
proposed patch for master v1

Joseph showed me though the code in Samba, and our initial view is that Samba and Heimdal master (eg 8.0pre) is not impacted as we can't find a code-path to krb5_parse_pac() not already encoded in a krbtgt-encrypted ticket.

It would of course be possible to attack the DC from an RODC, but for 64-bit installs, we can't see major harm from the only multiplication overflow. 

So we are left with an attack from an RODC of a 32 bit full DC.

CVSS:3.1/AV:N/AC:H/PR:H/UI:N/S:U/C:L/I:H/A:L

We have not checked Heimdal 0.7 and Samba 4.15 yet, but will update this if we find anything else.

Upstream Heimdal does not support RODCs and so would not be impacted, meaning we should be free to coordinate only with MIT, allowing Heimdal to just patch in master after the embargo is lifted. 

Does anybody have a counter-analysis?

Andrew,

> Joseph showed me though the code in Samba, and our initial view is that Samba and Heimdal master (eg 8.0pre) is not impacted as we can't find a code-path to krb5_parse_pac() not already encoded in a krbtgt-encrypted ticket.

What about the evidence ticket in an S4U2Proxy request?  It should be encrypted in a service's key, not a krbtgt key, and its PAC should be important enough to parse.

It is also possible to submit a service ticket for renewal.  I don't think Samba considers that an interesting case but I don't know if anything prevents it in Samba, or if upstream Heimdal allows it and parses the PAC.

Further reading of course brings up the enc_authorization_data path that is the reason why a PAC must be signed.  

Thankfully in Samba we add a new PAC in front at all times (and multiple PACs are rejected at parse time), but upstream Heimdal would not get the forced-in 'real' PAC so this could be an issue.

However yes, S4U2Proxy (as attacked with the so-called Bronze Bit) looks like a valid path in, without needing an RODC:

CVSS:3.1/AV:N/AC:H/PR:L/UI:N/S:U/C:L/I:H/A:L (6.4)  (on a 32bit DC)

It looks again like this will require a coordinated release across Heimdal / Samba / MIT / FreeIPA.

Heimdal appears to respect AS-REQ KRB5_PADATA_PA_PAC_REQUEST options when deciding whether to put a PAC in a TGT. Therefore a malicious PAC in the 'enc-authorization-data' field of a TGT renewal request could end up as the only one in the ticket, which Heimdal would parse in subsequent requests.

(In reply to Joseph Sutton from comment #6)
> Heimdal appears to respect AS-REQ KRB5_PADATA_PA_PAC_REQUEST options when
> deciding whether to put a PAC in a TGT.

However, it will add a PAC regardless if the server principal is the krbtgt, so the enc-authorization-data path is made more difficult to exploit in Heimdal's master branch.

Created attachment 17567 [details]
proposed patch for master v2

Addressed a few more potential overflows.

Created attachment 17597 [details]
proposed patch for Heimdal master v2

Created attachment 17600 [details]
Nico's version of Joseph's patch for Heimdal

My version of Joseph's patch.  Heavily edited to add more checks, fix a bug in the original (not Joseph's patch), simplify some code by adding an `addend` argument to `pac_aligned_size()`, add commentary, and add tests.

Created attachment 17617 [details]
MIT krb5 fix

I am attaching the MIT krb5 patch for the benefit of vendors when they are added to this bug.

Created attachment 17618 [details]
patch for Samba master v3

Created attachment 17619 [details]
patch for Samba 4.17 v3

Created attachment 17620 [details]
patch for Samba 4.16 v3

Created attachment 17621 [details]
patch for Samba 4.15 v3

Nico, I made a couple of minor changes to your patch. I zero-initialised header_size in krb5_pac_parse() to avoid a maybe-uninitialized error, and I added a 'ret == 0' condition prior to the 'p->pac == NULL' check in the same function.

Created attachment 17622 [details]
Samba advisory v1

Created attachment 17623 [details]
Critical fixes to be in Heimdal 7.7.1 and 7.8

These are the critical fixes that will be in Heimdal 7.7.1 and 7.8.

These are not all the commits that will be in 7.7.1 and 7.8.  I will post a tarball of all the commits in 7.7.1 separately.

Please review my CVSS scoring of CVE-2022-44640 Heimdal KDC: invalid free in ASN.1 codec.  Maybe I'm being much to severe in my analysis?

Created attachment 17624 [details]
All the commits from heimdal-7.7.0 to heimdal-7-7.1

These are all the commits that will be in heimdal 7.7.1.

(In reply to Joseph Sutton from comment #16)

Which attachment is that in?  Can you post just a diff to my patch (and then I'll update the attachments I just added.)?

(In reply to nico from comment #21)
I've included the changes in the patches for Samba on this bug. The diff is just this:

diff --git a/lib/krb5/pac.c b/lib/krb5/pac.c
index e39ab3fd88..e6dfe2aef3 100644
--- a/lib/krb5/pac.c
+++ b/lib/krb5/pac.c
@@ -256,7 +256,7 @@ krb5_pac_parse(krb5_context context, const void *ptr, size_t len,
     krb5_error_code ret = 0;
     krb5_pac p;
     krb5_storage *sp = NULL;
-    uint32_t i, num_buffers, version, header_size;
+    uint32_t i, num_buffers, version, header_size = 0;
     uint32_t prev_start = 0;
     uint32_t prev_end = 0;
 
@@ -289,7 +289,7 @@ krb5_pac_parse(krb5_context context, const void *ptr, size_t len,
                                N_("PAC encoding invalid, would overflow buffers", ""));
     if (ret == 0)
         p->pac = calloc(1, header_size);
-    if (p->pac == NULL)
+    if (ret == 0 && p->pac == NULL)
 	ret = krb5_enomem(context);
 
     if (ret == 0) {

(In reply to Joseph Sutton from comment #22)

Thanks.  That only affects what will be master, and eventually 8.0.

(In reply to nico from comment #20)
I see the overflow fix you've posted for Heimdal 7.7.1 is quite different from the one to be applied to Heimdal master. For Samba 4.15, which uses a much older version of Heimdal, I've backported the fix for modern Heimdal versions. Should I have taken the patch for Heimdal 7.7.1 instead?

(In reply to Joseph Sutton from comment #24)
I didn't put that much effort into my backport, admittedly.  If you have a better patch I'd use it.  The delta from 7.7 to master was quite large for that file.

(In reply to nico from comment #25)
The backport I did is in the attachment 'patch for Samba 4.15 v3'. It would take a bit of effort to port it back to Heimdal 7.7.0, which is somewhat newer than Samba 4.15's Heimdal version.

(In reply to Joseph Sutton from comment #26)
I'm running out of time since I have to take half of tomorrow off, unless we don't have to have the final patches tomorrow.

Also, you'll want to backport some of the other CVE fixes I attached.

(In reply to nico from comment #27)
I guess you can go with the backported patch you already have, if the differences between it and the master patch are inconsequential.

I checked the patchset you uploaded containing the other CVE fixes, and I think all of the CVEs that would apply to Samba should have already been fixed.

Created attachment 17625 [details]
Advisory v2

I've trimmed down the advisory and made it more useful to our administrators.  I've added a credit to Greg, who I understand provided the initial text this is based on.

Looking over this, I would also like our pre-announcement to specify this is only a concern to 32bit systems, to avoid scaring most folks.

Assigning to Jule to schedule for a Samba security release.  

I've asked for some additional review as the Heimdal changes are complex, but I think these are ready.

Keep in mind that our patches include the fix for the ASN.1 issue.

I can probably trim the 7.7.1 release commits more, but I'm a pumpkin today.

Created attachment 17627 [details]
Just the CVE patches for Heimdal 7.7.1

This is just the CVE patches and two more for Heimdal 7.7.0 -> 7.7.1.

(In reply to Andrew Bartlett from comment #30)
I've added a smaller set of patches for 7.7.1.

Comment on attachment 17618 [details]
patch for Samba master v3

Some thoughts from overnight: 

We should have an additional restriction that the number of buffers (the primary input to the multiplication) is restricted such that len / packed_buffer_size > numbuffers.

That way, the attacker has to supply as many buffers as they wish to allocate, and so the maximum packet that can be ingested restricts the size that they can force to allocate on the server. 

We should also just clamp the number of buffers to 1000.

(In reply to nico from comment #31)
Thankfully Samba 4.15 and older's snapshot is so old the ASN.1 use-after-free can't be accessed per our previous analysis, but we will re-check.  Samba 4.16 and later uses the new ASN.1 template mode that doesn't suffer from this issues as we understand it.

(In reply to Andrew Bartlett from comment #34)
> We should have an additional restriction that the number of buffers (the primary input to the multiplication) is restricted such that len / packed_buffer_size > numbuffers.

The existing header_len(MIT)/header_end(Heimdal) checks should address this once overflows in those computations are prevented.

> We should also just clamp the number of buffers to 1000.

I saw this in Nico's Heimdal v2 patch, but maybe not the smaller one he plans to put in the release?  (That is, I don't see it in 0014-krb5-CVE-2022-42898-PAC-parse-integer-overflows.patch from the tarball.)  It shouldn't be strictly necessary.

The MIT patch requires the buffer count to be in [1,4096].

(In reply to Greg Hudson from comment #36)
I'll update the pac bug fix this weekend, and I'll apply the 1000 buffers limit to it.  Unless someone does a crazy 1-SID-per-buffer extension, 1000 will be enough.

(In reply to Andrew Bartlett from comment #35)
Oh, hmm, the bug in the compiler goes back to 2005, but indeed, not every version of Heimdal has any support for FAST, so I should update the NEWS and announcement (which I've not yet written, and which will have to go out tomorrow).

Opening bug to Samba vendors (and one Heimdal Vendor I'm aware of)

This bug was referenced in samba v4-17-stable (Release samba-4.17.3):

5d845feca47822677c9a0e856191b0117f8bb9e4

This bug was referenced in samba v4-16-stable (Release samba-4.16.7):

a8ef840d4362d3ffeab13c1d5fea417511b727c2

This bug was referenced in samba v4-15-stable (Release samba-4.15.12):

8369aee33a0b3de10485dc72223f4653585e3a79
f792d3e3906414d836d186ec279586c13a83ba8d
9c909c57ce7abacd96ba18173a9dc4ba9a7c0230
a3816433ae971830c2b16b366b10283aeb5a87b5

Removing vendor CC (so that any public comments don't need to be broadcast so widely) and opening these bug to the public.
If you wish to continue to be informed about any changes here please CC individually.

This bug was referenced in samba v4-15-test:

8369aee33a0b3de10485dc72223f4653585e3a79
f792d3e3906414d836d186ec279586c13a83ba8d
9c909c57ce7abacd96ba18173a9dc4ba9a7c0230
a3816433ae971830c2b16b366b10283aeb5a87b5

This bug was referenced in samba v4-16-test:

a8ef840d4362d3ffeab13c1d5fea417511b727c2

This bug was referenced in samba v4-17-test:

5d845feca47822677c9a0e856191b0117f8bb9e4

This bug was referenced in samba master:

434f461e9e5a914d4e5a9141324f1705e5e50cf9

There's a regression on 32-bit builds!

The error message contains something like this:
PAC offset inside header: 0 120

Where offset is 0 because krb5_ret_uint64() doesn't work
on 32-bit.

The fix is most likely something like this:

--- a/third_party/heimdal/lib/krb5/store-int.c
+++ b/third_party/heimdal/lib/krb5/store-int.c
@@ -49,7 +49,7 @@ KRB5_LIB_FUNCTION krb5_ssize_t KRB5_LIB_CALL
 _krb5_get_int64(void *buffer, uint64_t *value, size_t size)
 {
     unsigned char *p = buffer;
-    unsigned long v = 0;
+    uint64_t v = 0;
     size_t i;
     for (i = 0; i < size; i++)
        v = (v << 8) + p[i];

I agree with the change to _krb5_get_int64().  I'm curious, what is the value of the 'size' parameter passed from krb5_ret_int()?  

Is the return value expected to be greater than MAX_UINT64?

(In reply to Jeffrey Altman from comment #48)

It's 8 and the bytes are these:

0x78 0x00 0x00 0x00 0x00 0x00 0x00 0x00

When i becomes 4 'v' will be 0 again. As 'unsigned long' is only
able to hold 4 bytes.

Do you wish to submit a pull request to Heimdal or should I submit a change in your name?

(In reply to Stefan Metzmacher from comment #47)

I just tested new packages with that simple fix and everything works again...

Created attachment 17657 [details]
32-bit regression fix for 4.15

Created attachment 17658 [details]
32-bit regression fix for 4.16

Created attachment 17659 [details]
32-bit regression fix for 4.17

(In reply to Jeffrey Altman from comment #50)

See https://github.com/heimdal/heimdal/pull/1024

I raced with you 

https://github.com/heimdal/heimdal/pull/1025

This bug was referenced in samba v4-16-test:

7edddbc684c8098f15063732b9bf13b089e8fae4

This bug was referenced in samba v4-17-test:

c37b4d797ae4065e84ef52610fc1dcf009948685

This bug was referenced in samba v4-15-test:

f3672577a8e15b7937d0067a262d04df632dade9

This bug was referenced in samba master:

dce639f8bd75ecdca261d1dc8b97ce6a8ebb4eb0

Closing out bug report.

Thanks!

This bug was referenced in samba v4-15-stable (Release samba-4.15.13):

f3672577a8e15b7937d0067a262d04df632dade9

This bug was referenced in samba v4-17-stable (Release samba-4.17.4):

c37b4d797ae4065e84ef52610fc1dcf009948685

This bug was referenced in samba v4-16-stable (Release samba-4.16.8):

7edddbc684c8098f15063732b9bf13b089e8fae4