iMessage NSSharedKeyDictionary Decode Out-Of-Bounds Read

iMessage: decoding NSSharedKeyDictionary can lead to out-of-bounds reads

During processing of incoming iMessages, attacker controlled data is deserialized using the
NSUnarchiver API. One of the classes that is allowed to be decoded from the incoming data is
NSDictionary. However, due to the logic of NSUnarchiver, all subclasses of NSDictionary that also
implement secure coding can then be deserialized as well. NSSharedKeyDictionary is an example of
such a subclass. A NSSharedKeyDictionary is a dictionary for which, for performance reasons, the
keys are predefined using a NSSharedKeySet.

A NSSharedKeyDictionary is essentially a linear array of values and a pointer to its
NSSharedKeySet. An NSSharedKeySet on the other hand looks roughly like this (with some fields
omitted for simplicity and translated to pseudo-C):

struct NSSharedKeySet {
    unsigned int _numKeys;   // The number of keys in the _keys array
    id* _keys;              // A pointer to an array containing the key values
    unsigned int _rankTable;    // A table basically mapping the hashes of
                                // the keys to an index into _keys
    unsigned int _M;        // The size of the _rankTable
    unsigned int _factor;   // Used to compute the index into _rankTable from a hash.
    NSSharedKeySet* _subKeySet; // The next KeySet in the chain
};

The value lookup on an NSSharedKeyDictionary then works roughly as follows:
* NSSharedKeyDictionary invokes [NSSharedKeySet indexForKey:] on its associated keySet
* indexForKey: computes the hash of the key, basically computes rti = hash % _factor, bounds-checks
  that against _M, and finally uses it to lookup the index in its rankTable: idx = _rankTable[rti]
* It verifies that idx < _numKeys
* It loads _keys[idx] and invokes [key isEqual:candidate] with it as argument
* If the result is true, the index has been found and is returned to the NSSharedKeyDictionary where
  it is used to index into its values array
* If not, indexForKey: recursively processes the subKeySet in the same way until it either finds the
  key or there is no subKeySet left, in which case it returns -1

There is a bug in the implementation of indexForKey: where, for the bounds check against the
rankTable size, it uses the size (_M) from the original NSSharedKeySet instead of the current one,
as can be seen in the assembly code below (from CoreFoundation.framework):

[NSSharedKeySet indexForKey:]
...
; store first NSSharedKeySet into r12
__text:00000000000ED1EB                 mov     r12, rdi
...
; store current NSSharedKeySet into r15 and start loop
__text:00000000000ED275                 mov     r15, r12

...
; load _M from the first NSSharedKeySet and bounds check against that value
__text:00000000000ED335                 mov     rax, [rbp+var_88]
__text:00000000000ED33C                 mov     r13d, [r12+rax]
__text:00000000000ED340                 cmp     ebx, r13d
__text:00000000000ED343                 jnb     loc_ED418

...
; load the table from the current NSSharedKeySet and index into it
__text:00000000000ED352                 mov     rax, [rbp+var_70]
__text:00000000000ED356                 mov     r8, [r15+rax]
__text:00000000000ED35A                 shr     esi, 2
__text:00000000000ED35D                 and     esi, 1FFFFFFFh
__text:00000000000ED363                 movzx   esi, byte ptr [r8+rsi]

...
; load the next NSSharedKeySet in the chain and repeat if possible
__text:00000000000ED41C                 mov     rax, [rbp+var_80]
__text:00000000000ED420                 mov     r15, [r15+rax]


As such, it is possible to read an index OOB by deserializing a specially crafted
NSSharedKeyDictionary with two NSSharedKeySets chained together. The attached PoC demonstrates this
on the latest macOS 10.14.6 Note that libgmalloc is required to reliably trigger a crash during the
OOB access.

> clang -o tester tester.m -framework Foundation
> ./generator.py
> DYLD_INSERT_LIBRARIES=/usr/lib/libgmalloc.dylib ./tester payload.xml
GuardMalloc[tester-75873]: Allocations will be placed on 16 byte boundaries.
GuardMalloc[tester-75873]:  - Some buffer overruns may not be noticed.
GuardMalloc[tester-75873]:  - Applications using vector instructions (e.g., SSE) should work.
GuardMalloc[tester-75873]: version 109
2019-07-29 16:52:37.736 tester[75873:536654] Let's go
[1]    75873 segmentation fault  DYLD_INSERT_LIBRARIES=/usr/lib/libgmalloc.dylib ./tester payload.xml


As the value that is read out-of-bounds is an index into another table which is correctly
bounds-checked, the security impact of this bug is limited. However, it might be possible to use it
to construct a remote infoleak if a side channel can be constructed that indicates whether a message
was successfully received or not. By then carefully reading indices out-of-bounds on the heap, the
contents of adjacent memory might be inferable. iMessage delivery receipts, which are sent by
default, might be usable for this purpose.

This bug is subject to a 90 day disclosure deadline. After 90 days elapse
or a patch has been made broadly available (whichever is earlier), the bug
report will become visible to the public.


Related CVE Numbers: CVE-2019-8746.



Found by: [email protected]

Copyright ©2024 Exploitalert.