7 ms·

ELF hash function may overflow

87 points by fcambus 3y ago

userbinator 3y ago
I suspect the author of the hash function thought this wouldn't add more than 4 bits: h = (h << 4) + *name++; But as one should know, two n-bit numbers can create an n+1-bit result when added due to carry.
- dahfizz 3y ago
  I think the issue is that, when written, a `long` was 32 bits. I would guess the author was familiar with the concept of a carry bit, but they didn't care because the carry bit was discarded by their architecture.
- MaskRay 3y ago
  I added this sentence to the article, hopefully making it clearer: > If h is in the range [0x0fffff01,0x0fffffff] in the previous iteration, shifting it by 4 and adding *name may make h larger than UINT32_MAX.
omginternets 3y ago
I have a question: what should I read for an introduction to the implementation/internals/design of hash functions? I would like to to beyond my current understanding, which is basically “they’re effectively one-way functions”, and be able to participate in discussions of articles such as this one.
- jameswryan 3y ago
  For the cryptography & theory? https://toc.cryptobook.us/ https://toc.cryptobook.us/ For the design and internals of hash functions? The finalists for the SHA3 competition have extensive design documentation. There's an archive at https://web.archive.org/web/20170829225940/http://csrc.nist.gov/groups/ST/hash/sha-3/index.html https://web.archive.org/web/20170829225940/http://csrc.nist.... Cryptographic hash functions are designed to resist existing attacks, so you'll want an understanding of differential & linear cryptanalysis, as well as a variety of algebraic attacks. I don't know of a good textbook on the subject, so you might find yourself searching keywords on https://eprint.iacr.org/ https://eprint.iacr.org/
  - omginternets 3y ago
    Thank you!
Toxide 3y ago
Is this a bug? Nowhere in the function is the restriction of being under 32bits provided. Seems more like a problem with the specification.
deleted 3y ago
[deleted]
gumby 3y ago
Back when ELF was designed that architectures larger than 32 bits were extremely uncommon, either obsolete (36 and 40 bit) or expensive and exotic (Cray) so in neither case part of the ELF design space. So not a huge surprise. I remember thinking at the time that it was an oversight but it took more than another decade for that to even matter.
lionkor 3y ago
If someone checked in that code, it would definitely fail my code review. I understand back in the day it was different, but today there should be a lot of named intermediates. Additionally, `long` and any such keywords should not make it into any commit unless the commit explains 1) why its needed and 2) how, with any standard conforming implementation, it couldnt possibly cause a bug. As always in C programming, the bugs arise from people doing stuff that any sane guideline tells them to not do.
- cultureswitch 3y ago
  For all its advantages, C is unfortunately so ripe with stuff that any sane guideline would recommend not to do that it can hard to follow through. Though I agree in this case this would never have passed a modern review.
  - Joker_vD 3y ago
    There is a lovely piece of text in the third version of PNG specification: "PNG four-byte unsigned integers are limited to the range 0 to 2^31-1 to accommodate languages that have difficulty with unsigned four-byte values" [0]. Gee, I wonder what languages those may be? [0] https://www.w3.org/TR/2022/WD-png-3-20221025/#7Integers-and-byte-order https://www.w3.org/TR/2022/WD-png-3-20221025/#7Integers-and-...
    - account42 3y ago
      The answer is Java, not C(++).
    - dahfizz 3y ago
      C has no problem dealing with a uint32_t. Not sure what you are getting at. This is more of an issue with languages like java that abstract away integer widths and signs, which is convenient if you're only doing arithmetic but becomes a huge pain when dealing with binary data.
  - pjmlp 3y ago
    One only needs to compare C programming manuals with the programming manuals from systems programming languages being developed outside Bell Labs. Also note that C author's were naturally aware of these issues and created lint in 1979. Now getting people to use such tooling is another matter, apparently 50 years weren't enough.
JonChesterfield 3y ago
I chased that rabbit hole briefly and it's not very clear that the hashed value is required to be <= UINT32_MAX. Closest is a claim by the same author as this post: > It seems obvious that on 32-bit and 64-bit systems, the function should not give different results and a commit to mask off the low bits in an implementation elsewhere. Well, maybe that would be convenient, but overall it seems unimportant. It's necessary for the tool writing the table and the tool reading it to agree but cross compilation is absolutely full of hazards like this anyway. The code looks fine to me for what that's worth. I can see the assignment in the if being contentious.
- dahfizz 3y ago
  It looks like the ELF standard itself says the hash table uses 32 bit values: > A hash table of Elf32_Word objects supports symbol table access. https://refspecs.linuxfoundation.org/elf/gabi4+/ch5.dynamic.html#hash https://refspecs.linuxfoundation.org/elf/gabi4+/ch5.dynamic....
- sltkr 3y ago
  The behavior is obviously an oversight. I'd bet 1 to 10 that if you chased down the original author he would agree. No sensible engineer would design a hash function that populates the lower 28 bits of the hash code, ALWAYS leaves bits 28 through 31 clear, and then SOMETIMES sets bit 32, but only rarely and only on certain architectures. It makes no sense as a conscious design. The logical conclusion is that the intent was to create a 28-bit hash function, and the fact that the provided code sometimes sets bit 32 is clearly a bug.
sylware 3y ago
ELF is way too complex and not really adapted anymore. We should start to deprecate DT_NEEDED and make dlopen/dlsym/dlclose (maybe, dlvsym) hard symbols in the loader. And game devs should stop using main() as some genius glibc dev did add a new libc_start_main version in 2.34. Namely, any game executable linked with a glibc from 2.34 will refuse to load on system with a previous glibc. Actually, game binaries should be pure ELF64 binaries (not using main()) which "libdl" (dlopen/dlsym/dlclose) everything they need from the system. And of course, as much as possible should be statically linked (I think this is what unity is doing, but unreal/godot have a big issue: the static libstdc++ which, as of late, does not libdl anything from the system).
- ptsneves 3y ago
  There is a huge amount of tooling relying on DT_NEEDED for dependency detection. I am not so sure about general purpose Linux, but in the embedded Linux world this would be a disaster. The Yocto system for example would no longer be able to determine the runtime dependencies of generated binaries. For the static library part, this is such a beaten down argument I just will not argue. I hope you enjoy re-installing your OS every time there is an security update on a library like openssl.
  - sylware 3y ago
    You missed the point: using "shared objects" would have to be explicit with "dlopen/dlsym/dlclose'. Mixing static linking with dynamic linking was not a good idea in the first place, and I mean it. ELF should be "fixed" about this, but to be sincere and honest, I think a lot could be removed from ELF on modern systems. Maybe it is not worth to fix ELF, but to go something like NGELF which would be excrutiatingly simpler and cleaner than ELF, namely real and disruptive innovation.
    - ptsneves 3y ago
      > You missed the point: using "shared objects" would have to be explicit with "dlopen/dlsym/dlclose'. dlopen and friends are function calls that you cannot evaluate build time. Actually not even at runtime as they are by nature dynamic and conditionally dlopen is a thing. Any shared object dependency tracking would be impossible or a new standard would be required. Also dlopen is a POSIX standard. ELFs are used in many other places non POSIX. > Mixing static linking with dynamic linking was not a good idea in the first place, and I mean it. Why was it not a good idea? This happens all the time, especially the code that is at the very first executable address of the elf until some libc prepares things is arguably statically linked. > [...] but to go something like NGELF [...] Sounds interesting. Could you paste a link? I could not find it in google.

87 points by fcambus 3y ago

I suspect the author of the hash function thought this wouldn't add more than 4 bits: h = (h << 4) + *name++; But as one should know, two n-bit numbers can create an n+1-bit result when added due to carry.

dahfizz 3y ago
I think the issue is that, when written, a `long` was 32 bits. I would guess the author was familiar with the concept of a carry bit, but they didn't care because the carry bit was discarded by their architecture.
MaskRay 3y ago
I added this sentence to the article, hopefully making it clearer: > If h is in the range [0x0fffff01,0x0fffffff] in the previous iteration, shifting it by 4 and adding *name may make h larger than UINT32_MAX.

omginternets 3y ago

I have a question: what should I read for an introduction to the implementation/internals/design of hash functions? I would like to to beyond my current understanding, which is basically “they’re effectively one-way functions”, and be able to participate in discussions of articles such as this one.

jameswryan 3y ago
For the cryptography & theory? https://toc.cryptobook.us/ https://toc.cryptobook.us/ For the design and internals of hash functions? The finalists for the SHA3 competition have extensive design documentation. There's an archive at https://web.archive.org/web/20170829225940/http://csrc.nist.gov/groups/ST/hash/sha-3/index.html https://web.archive.org/web/20170829225940/http://csrc.nist.... Cryptographic hash functions are designed to resist existing attacks, so you'll want an understanding of differential & linear cryptanalysis, as well as a variety of algebraic attacks. I don't know of a good textbook on the subject, so you might find yourself searching keywords on https://eprint.iacr.org/ https://eprint.iacr.org/
- omginternets 3y ago
  Thank you!

Toxide 3y ago

Is this a bug? Nowhere in the function is the restriction of being under 32bits provided. Seems more like a problem with the specification.

deleted 3y ago

[deleted]

gumby 3y ago

Back when ELF was designed that architectures larger than 32 bits were extremely uncommon, either obsolete (36 and 40 bit) or expensive and exotic (Cray) so in neither case part of the ELF design space. So not a huge surprise. I remember thinking at the time that it was an oversight but it took more than another decade for that to even matter.

lionkor 3y ago

If someone checked in that code, it would definitely fail my code review. I understand back in the day it was different, but today there should be a lot of named intermediates. Additionally, `long` and any such keywords should not make it into any commit unless the commit explains 1) why its needed and 2) how, with any standard conforming implementation, it couldnt possibly cause a bug. As always in C programming, the bugs arise from people doing stuff that any sane guideline tells them to not do.

cultureswitch 3y ago
For all its advantages, C is unfortunately so ripe with stuff that any sane guideline would recommend not to do that it can hard to follow through. Though I agree in this case this would never have passed a modern review.
- Joker_vD 3y ago
  There is a lovely piece of text in the third version of PNG specification: "PNG four-byte unsigned integers are limited to the range 0 to 2^31-1 to accommodate languages that have difficulty with unsigned four-byte values" [0]. Gee, I wonder what languages those may be? [0] https://www.w3.org/TR/2022/WD-png-3-20221025/#7Integers-and-byte-order https://www.w3.org/TR/2022/WD-png-3-20221025/#7Integers-and-...
  - account42 3y ago
    The answer is Java, not C(++).
  - dahfizz 3y ago
    C has no problem dealing with a uint32_t. Not sure what you are getting at. This is more of an issue with languages like java that abstract away integer widths and signs, which is convenient if you're only doing arithmetic but becomes a huge pain when dealing with binary data.
- pjmlp 3y ago
  One only needs to compare C programming manuals with the programming manuals from systems programming languages being developed outside Bell Labs. Also note that C author's were naturally aware of these issues and created lint in 1979. Now getting people to use such tooling is another matter, apparently 50 years weren't enough.

JonChesterfield 3y ago

I chased that rabbit hole briefly and it's not very clear that the hashed value is required to be <= UINT32_MAX. Closest is a claim by the same author as this post: > It seems obvious that on 32-bit and 64-bit systems, the function should not give different results and a commit to mask off the low bits in an implementation elsewhere. Well, maybe that would be convenient, but overall it seems unimportant. It's necessary for the tool writing the table and the tool reading it to agree but cross compilation is absolutely full of hazards like this anyway. The code looks fine to me for what that's worth. I can see the assignment in the if being contentious.

dahfizz 3y ago
It looks like the ELF standard itself says the hash table uses 32 bit values: > A hash table of Elf32_Word objects supports symbol table access. https://refspecs.linuxfoundation.org/elf/gabi4+/ch5.dynamic.html#hash https://refspecs.linuxfoundation.org/elf/gabi4+/ch5.dynamic....
sltkr 3y ago
The behavior is obviously an oversight. I'd bet 1 to 10 that if you chased down the original author he would agree. No sensible engineer would design a hash function that populates the lower 28 bits of the hash code, ALWAYS leaves bits 28 through 31 clear, and then SOMETIMES sets bit 32, but only rarely and only on certain architectures. It makes no sense as a conscious design. The logical conclusion is that the intent was to create a 28-bit hash function, and the fact that the provided code sometimes sets bit 32 is clearly a bug.

sylware 3y ago

ELF is way too complex and not really adapted anymore. We should start to deprecate DT_NEEDED and make dlopen/dlsym/dlclose (maybe, dlvsym) hard symbols in the loader. And game devs should stop using main() as some genius glibc dev did add a new libc_start_main version in 2.34. Namely, any game executable linked with a glibc from 2.34 will refuse to load on system with a previous glibc. Actually, game binaries should be pure ELF64 binaries (not using main()) which "libdl" (dlopen/dlsym/dlclose) everything they need from the system. And of course, as much as possible should be statically linked (I think this is what unity is doing, but unreal/godot have a big issue: the static libstdc++ which, as of late, does not libdl anything from the system).

ptsneves 3y ago
There is a huge amount of tooling relying on DT_NEEDED for dependency detection. I am not so sure about general purpose Linux, but in the embedded Linux world this would be a disaster. The Yocto system for example would no longer be able to determine the runtime dependencies of generated binaries. For the static library part, this is such a beaten down argument I just will not argue. I hope you enjoy re-installing your OS every time there is an security update on a library like openssl.
- sylware 3y ago
  You missed the point: using "shared objects" would have to be explicit with "dlopen/dlsym/dlclose'. Mixing static linking with dynamic linking was not a good idea in the first place, and I mean it. ELF should be "fixed" about this, but to be sincere and honest, I think a lot could be removed from ELF on modern systems. Maybe it is not worth to fix ELF, but to go something like NGELF which would be excrutiatingly simpler and cleaner than ELF, namely real and disruptive innovation.
  - ptsneves 3y ago
    > You missed the point: using "shared objects" would have to be explicit with "dlopen/dlsym/dlclose'. dlopen and friends are function calls that you cannot evaluate build time. Actually not even at runtime as they are by nature dynamic and conditionally dlopen is a thing. Any shared object dependency tracking would be impossible or a new standard would be required. Also dlopen is a POSIX standard. ELFs are used in many other places non POSIX. > Mixing static linking with dynamic linking was not a good idea in the first place, and I mean it. Why was it not a good idea? This happens all the time, especially the code that is at the very first executable address of the elf until some libc prepares things is arguably statically linked. > [...] but to go something like NGELF [...] Sounds interesting. Could you paste a link? I could not find it in google.