[tor-bugs] #18162 [Tor]: Potential heap corruption in smartlist_add(), smartlist_insert()

[Tor Bug Tracker & Wiki]

#18162: Potential heap corruption in smartlist_add(), smartlist_insert()
-------------------------------------------------+-------------------------
 Reporter:  asn                                  |          Owner:  nickm
     Type:  defect                               |         Status:
 Priority:  High                                 |  needs_review
Component:  Tor                                  |      Milestone:  Tor:
 Severity:  Normal                               |  0.2.8.x-final
 Keywords:  security 025-backport 026-backport   |        Version:
  027-backport 024-backport                      |     Resolution:
Parent ID:                                       |  Actual Points:
  Sponsor:                                       |         Points:
-------------------------------------------------+-------------------------

Comment (by teor):

 Replying to [ticket:18162 asn]:
 > If `sl->num_used` is 0x7FFFFFFF prior to invoking `smartlist_add`, then
 the next `smartlist_add` is effectively:
 >
 > {{{
 > void
 > smartlist_add(smartlist_t *sl, void *element)
 > {
 >   smartlist_ensure_capacity(sl, -2147483648);
 >   sl->list[2147483647] = element;
 >   sl->num_used = -2147483648
 > }
 > }}}
 >
 > This is the case since we are dealing with a signed 32 bit integer, and
 2147483647 + 1 equals -2147483647.
 >
 > All of the code in `smartlist_ensure_capacity` is wrapped inside the
 following `if` block:
 >
 > {{{
 >   if (size > sl->capacity) {
 >   }
 > }}}
 >
 > The expression -2147483648 > 2147483647 equals false, thus the code
 inside the block is not executed.
 >
 > What actually causes the segmentation fault is that a negative 32 bit
 integer is used to compute a the location of array index on a 64 bit
 memory layout, ie., the next call to smartlist_add is effectively:
 >
 > {{{
 > void
 > smartlist_add(smartlist_t *sl, void *element)
 > {
 >   smartlist_ensure_capacity(sl, -2147483647); // Note that this is
 effective do-nothing code, as explained above
 >   sl->list[-2147483648] = element;
 >   sl->num_used = -2147483647
 > }
 > }}}

 It's worth noting that signed integer overflow is undefined behaviour in
 C, so an optimising compiler could strictly do anything with `2147483647 +
 1`, including assuming that it will never occur, and optimising out the
 check, code after the check, or even code before the check.

 http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

 Whether this undefined behaviour actually occurs in Tor depends on the
 setting of configure's --enable-expensive-hardening. It sets -fwrapv,
 which guarantees wrapping on signed-integer overflow. (Note that in
 #17983, we consider building with -ftrapv instead of -fwrapv. This issue
 would have caused a crash on integer overflow under -ftrapv. It would have
 been a denial of service risk, but not otherwise exploitable.)

 If configure --enable-expensive-hardening is not set, the behaviour is
 undefined, and the outcome depends on the compiler's optimisation of
 undefined behaviour. I don't know what current compilers do with this code
 - has anyone checked?

--
Ticket URL: <https://trac.torproject.org/projects/tor/ticket/18162#comment:6>
Tor Bug Tracker & Wiki <https://trac.torproject.org/>
The Tor Project: anonymity online