5 ms·

CTF Writeup: Abusing select() to factor RSA

135 points by moyix 3y ago

jjnoakes 3y ago
select() ought to just fail with EINVAL if nfds is too large. There's probably an argument for the macros as well to fail by default if the file descriptor given is too large.
- moyix 3y ago
  As one safety measure, compiling with -DFORTIFY_SOURCE > 0 will enable checks on the FD_SET etc macros: https://github.com/bminor/glibc/commit/a0f33f996f7986dbf37631a4577f8565b42df29e https://github.com/bminor/glibc/commit/a0f33f996f7986dbf3763... The kernel side interface probably won't change because apparently legitimate apps have been allocating fd_sets on the heap to monitor fds > 1024 and they don't want to break those: https://sourceware.org/bugzilla/show_bug.cgi?id=10352#c7 https://sourceware.org/bugzilla/show_bug.cgi?id=10352#c7 The underlying problem was also discussed in an article by Lennart Poettering (of systemd fame) and posted to HN back in 2021: https://news.ycombinator.com/item?id=27215690 https://news.ycombinator.com/item?id=27215690 https://0pointer.net/blog/file-descriptor-limits.html https://0pointer.net/blog/file-descriptor-limits.html
  - warpspin 3y ago
    > The kernel side interface probably won't change because apparently legitimate apps have been allocating fd_sets on the heap to monitor fds > 1024 and they don't want to break those Rightly so. Before libev, AIO or whatever where a thing, I used to run network servers 10 or 15 years or so ago with a redefined __FD_SETSIZE set to 16384 without any problems on Linux (plus appropriate proc and ulimit settings). The whole stack properly supported it, even if not officially supported. The real problem nowadays is, people can easily receive a fd >= 1024 as you do not control them, and then put them into fd sets only supporting values up to 1023 and then you have a security problem. Plus of course, the later APIs also simply scale better beyond 16k connections.
    - syncsynchalt 3y ago
      I'm guessing you didn't/couldn't use poll(2) because of the performance hit (both user and kernel side) of parsing/checking the less compact data structure? I both miss and don't miss the days before epoll(2) et al.
      - warpspin 3y ago
        Originally, we did not use it because it did not exist. That service existed already in a time before poll(2) was a thing on Linux and when we still had 256 fds only. The increase to 1024 and then to basically unlimited came just in time for us back then, and we were glad a simple recompile with a #define was all we needed to scale it. If my memory serves me right, we did try poll(2) though a while after it became available (and we already ran the 16k selects) but it was simply less performant. Later on, when java.nio came around and Java finally could "compete" for network services therefore, we switched from C to Java completely for that service.
  - dleslie 3y ago
    Hmm, I wonder if there are any Linux distros that are built with this flag enabled?
    - sweetjuly 3y ago
      Fortify source has been enabled in many distros for package builds, including popular ones like Ubuntu [1], for quite a while. [1] https://wiki.ubuntu.com/ToolChain/CompilerFlags#A-D_FORTIFY_SOURCE.3D2 https://wiki.ubuntu.com/ToolChain/CompilerFlags#A-D_FORTIFY_...
chc4 3y ago
I love well designed POSIX APIs, such as "this will silently corrupt memory if you use an FD above FD_SETSIZE, which you have no control over and have no sane way of remapping if it does happen".
- deathanatos 3y ago
  …right? The API design is patently insane, but why can't there be a simple if(nfds > FD_SETSIZE) { errno = EINVAL; return -1; } … or something to prevent "the API is garbage" from escalating all the way into "and now your memory is corrupt and the hackers are in"…?
  - 95014_refugee 3y ago
    Because the code was written before unit tests were a thing, and nobody is willing to take the risk / do the work to fix it, especially when "it's been shipping for years and nobody has ever complained".
    - raldi 3y ago
      It’s been shipping for decades and people have been complaining the whole time.
  - jcalvinowens 3y ago
    That's not really what the problem is. The actual code is fine. The issue is that the definition of `fd_set` has a constant size [1]. If you allocate the memory yourself, the select() system call will work with as many file descriptors as you care to pass to it. You can see that both glibc [2] and the kernel [3] support arbitrarily large arrays (well, in the kernel case you'll run into other limitations... but no memory corruption). [1] https://github.com/bminor/glibc/blob/master/misc/sys/select.h#L59 https://github.com/bminor/glibc/blob/master/misc/sys/select.... [2] https://github.com/bminor/glibc/blob/master/sysdeps/unix/sysv/linux/select.c#L32 https://github.com/bminor/glibc/blob/master/sysdeps/unix/sys... [3] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/select.c#n625 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...
kelsey9876543 3y ago
Excellent writeup. Thank you.
cjbprime 3y ago
CTF writeups are so fun. Here's another I enjoyed, written by a teammate: https://zackorndorff.com/2022/08/06/blazin-etudes-hack-a-sat-3-quals-2022-writeup/ https://zackorndorff.com/2022/08/06/blazin-etudes-hack-a-sat...
saagarjha 3y ago
Memory corruption might die out as we secure our software stacks but I’m glad to see that weebs are eternal.
- deleted 3y ago
  [deleted]
ridiculous_fish 3y ago
Apple's libc has a pretty wild feature (guarded by _DARWIN_UNLIMITED_SELECT, on by default) which allows fds above FD_SETSIZE. It works by checking the address of the fd_set: if it's within the current thread's stack, then the call will fail, under the assumption that it's a stack-allocated fd_set. But if the address is NOT within the current thread's stack, select() assumes you know what you're doing and will allow the call, trusting you have allocated sufficient memory for the high fds in the fd_set. No opinion if this is a good decision or not, I just think it's interesting!
EdSchouten 3y ago
I really think that this is a quality of implementation issue. Even though most implementations do so, there is no requirement to implement fd_set as a bitmap. It could also be an array of integers. Though this still won’t allow you to select() against an infinite number of file descriptors, it at least allows file descriptor numbers to span the full range of int. Furthermore, there’s also no requirement that FD_*() corrupt your memory. I get it that these macros can’t return errors back to the caller, but they can always set some kind of flag in the fd_set to indicate that insertion was unsuccessful. select() could check that flag and bail out if set.
- gpderetta 3y ago
  They could simply abort.
- deleted 3y ago
  [deleted]
- Sesse__ 3y ago
  Windows implements fd_set as an array. https://learn.microsoft.com/en-us/windows/win32/api/winsock/ns-winsock-fd_set https://learn.microsoft.com/en-us/windows/win32/api/winsock/...

135 points by moyix 3y ago

select() ought to just fail with EINVAL if nfds is too large. There's probably an argument for the macros as well to fail by default if the file descriptor given is too large.

moyix 3y ago
As one safety measure, compiling with -DFORTIFY_SOURCE > 0 will enable checks on the FD_SET etc macros: https://github.com/bminor/glibc/commit/a0f33f996f7986dbf37631a4577f8565b42df29e https://github.com/bminor/glibc/commit/a0f33f996f7986dbf3763... The kernel side interface probably won't change because apparently legitimate apps have been allocating fd_sets on the heap to monitor fds > 1024 and they don't want to break those: https://sourceware.org/bugzilla/show_bug.cgi?id=10352#c7 https://sourceware.org/bugzilla/show_bug.cgi?id=10352#c7 The underlying problem was also discussed in an article by Lennart Poettering (of systemd fame) and posted to HN back in 2021: https://news.ycombinator.com/item?id=27215690 https://news.ycombinator.com/item?id=27215690 https://0pointer.net/blog/file-descriptor-limits.html https://0pointer.net/blog/file-descriptor-limits.html
- warpspin 3y ago
  > The kernel side interface probably won't change because apparently legitimate apps have been allocating fd_sets on the heap to monitor fds > 1024 and they don't want to break those Rightly so. Before libev, AIO or whatever where a thing, I used to run network servers 10 or 15 years or so ago with a redefined __FD_SETSIZE set to 16384 without any problems on Linux (plus appropriate proc and ulimit settings). The whole stack properly supported it, even if not officially supported. The real problem nowadays is, people can easily receive a fd >= 1024 as you do not control them, and then put them into fd sets only supporting values up to 1023 and then you have a security problem. Plus of course, the later APIs also simply scale better beyond 16k connections.
  - syncsynchalt 3y ago
    I'm guessing you didn't/couldn't use poll(2) because of the performance hit (both user and kernel side) of parsing/checking the less compact data structure? I both miss and don't miss the days before epoll(2) et al.
    - warpspin 3y ago
      Originally, we did not use it because it did not exist. That service existed already in a time before poll(2) was a thing on Linux and when we still had 256 fds only. The increase to 1024 and then to basically unlimited came just in time for us back then, and we were glad a simple recompile with a #define was all we needed to scale it. If my memory serves me right, we did try poll(2) though a while after it became available (and we already ran the 16k selects) but it was simply less performant. Later on, when java.nio came around and Java finally could "compete" for network services therefore, we switched from C to Java completely for that service.
- dleslie 3y ago
  Hmm, I wonder if there are any Linux distros that are built with this flag enabled?
  - sweetjuly 3y ago
    Fortify source has been enabled in many distros for package builds, including popular ones like Ubuntu [1], for quite a while. [1] https://wiki.ubuntu.com/ToolChain/CompilerFlags#A-D_FORTIFY_SOURCE.3D2 https://wiki.ubuntu.com/ToolChain/CompilerFlags#A-D_FORTIFY_...

chc4 3y ago

I love well designed POSIX APIs, such as "this will silently corrupt memory if you use an FD above FD_SETSIZE, which you have no control over and have no sane way of remapping if it does happen".

deathanatos 3y ago
…right? The API design is patently insane, but why can't there be a simple if(nfds > FD_SETSIZE) { errno = EINVAL; return -1; } … or something to prevent "the API is garbage" from escalating all the way into "and now your memory is corrupt and the hackers are in"…?
- 95014_refugee 3y ago
  Because the code was written before unit tests were a thing, and nobody is willing to take the risk / do the work to fix it, especially when "it's been shipping for years and nobody has ever complained".
  - raldi 3y ago
    It’s been shipping for decades and people have been complaining the whole time.
- jcalvinowens 3y ago
  That's not really what the problem is. The actual code is fine. The issue is that the definition of `fd_set` has a constant size [1]. If you allocate the memory yourself, the select() system call will work with as many file descriptors as you care to pass to it. You can see that both glibc [2] and the kernel [3] support arbitrarily large arrays (well, in the kernel case you'll run into other limitations... but no memory corruption). [1] https://github.com/bminor/glibc/blob/master/misc/sys/select.h#L59 https://github.com/bminor/glibc/blob/master/misc/sys/select.... [2] https://github.com/bminor/glibc/blob/master/sysdeps/unix/sysv/linux/select.c#L32 https://github.com/bminor/glibc/blob/master/sysdeps/unix/sys... [3] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/fs/select.c#n625 https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/lin...

kelsey9876543 3y ago

Excellent writeup. Thank you.

cjbprime 3y ago

CTF writeups are so fun. Here's another I enjoyed, written by a teammate: https://zackorndorff.com/2022/08/06/blazin-etudes-hack-a-sat-3-quals-2022-writeup/ https://zackorndorff.com/2022/08/06/blazin-etudes-hack-a-sat...

saagarjha 3y ago

Memory corruption might die out as we secure our software stacks but I’m glad to see that weebs are eternal.

deleted 3y ago
[deleted]

ridiculous_fish 3y ago

Apple's libc has a pretty wild feature (guarded by _DARWIN_UNLIMITED_SELECT, on by default) which allows fds above FD_SETSIZE. It works by checking the address of the fd_set: if it's within the current thread's stack, then the call will fail, under the assumption that it's a stack-allocated fd_set. But if the address is NOT within the current thread's stack, select() assumes you know what you're doing and will allow the call, trusting you have allocated sufficient memory for the high fds in the fd_set. No opinion if this is a good decision or not, I just think it's interesting!

EdSchouten 3y ago

I really think that this is a quality of implementation issue. Even though most implementations do so, there is no requirement to implement fd_set as a bitmap. It could also be an array of integers. Though this still won’t allow you to select() against an infinite number of file descriptors, it at least allows file descriptor numbers to span the full range of int. Furthermore, there’s also no requirement that FD_*() corrupt your memory. I get it that these macros can’t return errors back to the caller, but they can always set some kind of flag in the fd_set to indicate that insertion was unsuccessful. select() could check that flag and bail out if set.

gpderetta 3y ago
They could simply abort.
deleted 3y ago
[deleted]
Sesse__ 3y ago
Windows implements fd_set as an array. https://learn.microsoft.com/en-us/windows/win32/api/winsock/ns-winsock-fd_set https://learn.microsoft.com/en-us/windows/win32/api/winsock/...