They're stored in a sqlite database on your phone. If you make an unencrypted backup of your device, you can find the db file in the output. The filenames are all mangled, but there's a manifest database at the root of the dump that has a mapping to the source file metadata.

From there, you just need to export the data you want from the messages db. The schema is kind of amazing, but not in a good way.

You don't need to buy a tool - you can write a python/ruby/whatever script.

You can extract them from an iTunes backup using iMazing or Reincubate Backup Extractor, though both are paid.