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: saelo@google.com