Review main Merged Breaking

74688[!!!][TASK] Use full md5 hash for `indexed_search`

Florian Schöppe CR +2 V +2 Hard +366 −269 updated 01/29/24, 14:34

Commit message

For `ext:indexed_search` not only a cumbersome md5 to int
conversion has been used. The original md5 length has been
reduced by simply cutting off values from the end, combined
with a `hexdec` conversion, leading to a highly increased
conflict probability (duplicate keys) for several places.

To mitigate this, the raw md5 hash should be used instead
of the reduced integer representation.

This change modifies the database and the user land code
to use the full `md5()` hash without castrating them any
longer.

The following table fields are therefore changed from `int`
to `varchar`:

* index_phash: phash, phash_grouping, contentHash
* index_fulltext: phash
* index_rel: phash, wid
* index_words: wid
* index_section: phash, phash_t3
* index_grlist: phash, phash_x, hash_gr_list
* index_debug: phash

Note: The required table truncation is handled within
the database analyzer schema changes and not as an upgrade
wizard.

Recently added native php types are now changed to string
to cope with this change again. Also removed the now unused
internal `IndexedSearchUtility::md5inthash()` method.

Using `QueryBuilder::quoteArrayBasedValueListToStringList()`
instead of named placeholders for `IN()` conditions to reduce
the risk for exceeded placeholder limit. QuerySize limitation
may still occur, but can be increased by the responsible server
administrator.

Review

  • Code review CR +2 Done
    • Stefan Bürk +2
    • Christian Kuhn +1
    • Simon Schaufelberger +1
  • Verified V +2 Done
    • Stefan Bürk +2
    • Christian Kuhn +1
    • Simon Schaufelberger +1
    • core-ci +1 CI

Issues 5

Files 12

Review log 5978

Show 4053 earlier messages
  1. Florian Schöppe uploaded patch set 1 05/20/22, 08:51

  2. core-ci voted on patch set 1 V -1 05/20/22, 09:00 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27345

  3. Oliver Klee commented on patch set 1 CR -1 05/20/22, 09:21

    CI also is unhappy. You might want to check out what the various checks have to complain about. :-)
    Your commit message is missing a releases line, e.g. "Releases: main" (which I'd propose) or "Releases: main, 11.5". AFAIK, for multiple resolved bugs, you'll need to have each in a separate line: Resolves: #84541 Resolves: #90977 Resolves: #79802 Resolves: #87138
  4. Florian Schöppe updated the commit message in patch set 2 05/20/22, 09:49

  5. core-ci voted on patch set 2 V -1 05/20/22, 09:57 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27346

  6. Sybille Peters commented on patch set 2 V +1 05/20/22, 11:06

    I would be happy to see this solved - has been open for quite a while. BUT; what is most important here is that the patch works. I don't fully understand what you changed and why. I understand that hash collision caused the problem and the hash function truncates the hash string. Perhaps you can explain your approach in the commit message? There will be people reviewing your patch - it is important that they can check your work and understand the change. With the description in the issue https://forge.typo3.org/issues/84541#Reproduce I created a page where I can reproduce this bug. With your patch - this is fixed but it would be good to understand the changes better and make sure nothing else is broken. Having added tests is great! Thank you.

    Reply

    Also, since you listed number 84541 as "Resolves" (twice), there is no need to add the link: > Replaced weak md5 hashes in index_words with database lookups. See https://forge.typo3.org/issues/84541
  7. Florian Schöppe uploaded patch set 3 05/20/22, 11:22

  8. Florian Schöppe updated the commit message in patch set 4 05/20/22, 11:26

  9. Oliver Klee commented on patch set 4 CR -1 05/20/22, 11:29

    IndexSearchRepository.php:648

    For like, you always need to quote the value to avoid SQL injection: https://docs.typo3.org/m/typo3/reference-coreapi/main/en-us/ApiOverview/Database/ExpressionBuilder/Index.html#comparisons Please also add a test that fails without this change to make sure no SQL injection can sneak in here.

    IndexSearchRepository.php:693

    Ditto.

    IndexerTestConfiguration.php:47

    There's some trailing whitespace here that probably is not intentional.
  10. Oliver Klee commented on patch set 4 05/20/22, 11:31

    IndexSearchRepositoryTest.php:27

    For new tests, I recommend directly add an @covers annotation to the test class for the benefit of the reader and for improved code coverage generation: /** * @covers \TYPO3\CMS\IndexedSearch\Domain\Repository\IndexSearchRepository */ Ditto for any other new test class. (This is not a blocker, but a nice-to-have.)
  11. core-ci voted on patch set 3 V +1 05/20/22, 11:33 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27349

  12. core-ci voted on patch set 4 V -1 05/20/22, 11:35 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27350

  13. Florian Schöppe uploaded patch set 5 05/20/22, 14:18

  14. Florian Schöppe uploaded patch set 6 05/20/22, 14:24

  15. core-ci voted on patch set 5 V +1 05/20/22, 14:25 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27354

  16. core-ci voted on patch set 6 V +1 05/20/22, 14:33 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27355

  17. Sybille Peters updated the commit message in patch set 7 05/21/22, 05:46

  18. core-ci voted on patch set 7 V +1 05/21/22, 05:53 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27367

  19. Georg Ringer commented on patch set 7 05/21/22, 06:09

    if there is even an upgrade wizard for something I would like to see a important rst or maybe make a feature out of it?
  20. Oliver Klee commented on patch set 7 05/21/22, 08:44

    ResetIndexWizardTest.php:66

    Generally, in tests please do the strictest checks possible to catch when things are slightly off. Specifically, please always use assertSame instead of assertEquals unless you need the less strict check. (The difference between assertSame and assertEquals is the same as between the === and == comparisons.)
  21. Stefan Bürk commented on patch set 7 CR -2 05/21/22, 10:05

    Thanks for this patch and your work on it, Florian. This put indexed_search again on the table that it really needs some love. I looked through the patch, and the base approach is not bad at all. However, there are some detailes which are not so good at all. Thought quite some time about it, but instead of commenting these details and let you (or someone else) wasting time working them out which does not really make sense in the end, I decided to put a -2 on this change.
  22. Stefan Bürk commented on patch set 7 05/21/22, 10:23

    Reply

    Exidently hit ctrl+return. Let me explain the -2. The castrated md5int was a bad design decision as it have a really higher multitude of collisions. However, we *should* resolve this hash issue general through the whole indexed_search extension and for all tables - and replacing the phash integer columns with corresponding varchar() fields along the way. Benni and I discussed this recently to have this on the table for v12 already. This would solve some more issues with duplicated hashes on several places/tables. Thus given, we should handle these hash changes completly in one patch with only one "upgrade/truncate" call on upgrade to v12. indexed_search generally needs some love for v12 on several ends. Using hashes for search instead of the "basewords" directly avoids some character based issues on database searches, so build towards this is something which needs realy deeply care and proper extended testings with edgecases. So instead of avoiding hashing, it should be done correctly. (Granted, hashing never eliminates potential collisions - maybe can be solved with two steps instead). Furthermore, as far as I know and heared, Oliver Hader had some really usefull and well thought suggestions on that hash problematic - so we should consolidate his suggestion into a general approach as well. I really appreciated your patch, even if it payed not out yet. I loved to see adding tests on it. However, as these kinds of thoughts needs more and complex rework which exceeds a general review / let's change on a change used the -2 card. Not to decline or abandon this, but to do it in a generic way and put more people on the table. If you want to talk about this or my decision you are welcome to contact me in slack #typo3-cms-coredev channel / dm.
  23. Florian Schöppe uploaded patch set 8 05/23/22, 06:16

  24. Florian Schöppe commented on patch set 8 05/23/22, 06:20

    Reply

    The truncation of md5-hashes in the IndexedSearchUtility class is a problem: If the code would use standard md5-hashes collisions would be very unlikely. The code truncates the 128bit hash (32 * 4bit (per hexadecimal character)) to a 28bit hash (7 * 4bit) which drastically increased the probability of collisions. I did the math some time ago (see here for a starter https://stackoverflow.com/questions/201705/how-many-random-elements-before-md5-produces-collisions) and came to the result that these weak hashes should have a 50% probability for the first collision at around 2^14 = 16384 hashes. In general one should avoid customization of hashing functions and I would suggest not to use IndexedSearchUtility::md5inthash anywhere. This patch removes the weak hashes that were used for building the word index. There is no real need for hashing there - I assume the usage was some kind of legacy performance and memory optimization. It could be that this comes with a performance penalty but I think it as a trade off for a search that returns the correct results for every possible search word.

    Reply

    Done

    IndexSearchRepository.php:648 Reply

    Thank you for your valuable feedback! I added a very simple test to make sure the search words are quoted properly. I wasn't able to produce a realworld SQL injection with reasonable efforts because in the first case the injection must be done without using whitespaces (not easy but should be possible) and in the metaphone case the injection has to be immune against the metaphone transformation. :|

    IndexSearchRepository.php:693 Reply

    Done

    IndexerTestConfiguration.php:47 Reply

    Done

    IndexSearchRepositoryTest.php:27 Reply

    Done

    ResetIndexWizardTest.php:66 Reply

    Done
  25. core-ci voted on patch set 8 V +1 05/23/22, 06:24 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27396

  26. Florian Schöppe commented on patch set 8 05/23/22, 06:33

    Reply

    Thank you for the detailed and kind explanation! > The castrated md5int was a bad design decision as it have a really higher multitude of collisions. However, we *should* resolve this hash issue general through the whole indexed_search extension and for all tables - and replacing the phash integer columns with corresponding varchar() fields along the way. Benni and I discussed this recently to have this on the table for v12 already. This would solve some more issues with duplicated hashes on several places/tables. > > Thus given, we should handle these hash changes completly in one patch with only one "upgrade/truncate" call on upgrade to v12. > > indexed_search generally needs some love for v12 on several ends. I totally agree with that. > Using hashes for search instead of the "basewords" directly avoids some character based issues on database searches, so build towards this is something which needs realy deeply care and proper extended testings with edgecases. So instead of avoiding hashing, it should be done correctly. (Granted, hashing never eliminates potential collisions - maybe can be solved with two steps instead). I am not sure I understand what you mean with "character based issues". I don't see the point for hashes when building a word index. I am not deeply into the search topic in general but for me that sounds like a task that could be handled by the database alone. > Furthermore, as far as I know and heared, Oliver Hader had some really usefull and well thought suggestions on that hash problematic - so we should consolidate his suggestion into a general approach as well. > > I really appreciated your patch, even if it payed not out yet. I loved to see adding tests on it. > > However, as these kinds of thoughts needs more and complex rework which exceeds a general review / let's change on a change used the -2 card. Not to decline or abandon this, but to do it in a generic way and put more people on the table. 👍
  27. Markus Klein commented on patch set 8 05/23/22, 19:29

    Just a minor code styles comment.

    AdministrationController.php:306

    This can be simplified to: $metaphone[$row['metaphone']]['metaphone'] = $row['metaphone']; $metaphone[$row['metaphone']]['words'][] = $row['baseword']; No need for the if-condition
  28. Markus Klein commented on patch set 8 05/23/22, 19:31

    ResetIndexWizard.php:138

    If this table is huge, this might run out of memory. Better iterate over the result set than loading things into memory
  29. Markus Klein commented on patch set 8 05/23/22, 19:34

    Indexer.php:1849

    how many words will this be at max? (I don't know the mechanics by heart) If this get too long, the created SQL might exceed the limits of the DBMS, so be cautious with such constructions.

    Indexer.php:1858

    Should be fetchAssociative(), right?
  30. Sybille Peters updated the commit message in patch set 9 05/24/22, 05:27

  31. core-ci voted on patch set 9 V +1 05/24/22, 05:35 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27420

  32. Florian Schöppe commented on patch set 9 05/24/22, 08:49

    Indexer.php:1849 Reply

    An equivalent "in"-expression has been in the code before so I didn't think about using it myself. In general the $wordList should contain all (distinct) words of a single indexed document, so I think your concerns are correct because there is no real upper limit.
  33. Florian Schöppe uploaded patch set 10 05/24/22, 09:22

  34. Florian Schöppe commented on patch set 10 05/24/22, 09:24

    AdministrationController.php:306 Reply

    Done 👍

    Indexer.php:1858 Reply

    Done

    ResetIndexWizard.php:138 Reply

    Done
  35. core-ci voted on patch set 10 V +1 05/24/22, 09:29 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/27428

  36. Florian Schöppe commented on patch set 10 05/25/22, 12:29

    Reply

    While this patch waits for its use or any better solution I provided another patch which just improves the indexing experience without compromising backwards compatibility: https://review.typo3.org/c/Packages/TYPO3.CMS/+/74742
  37. Tymoteusz Motylewski commented on patch set 10 05/25/22, 17:36

    Reply

    maybe the tests you wrote could be extracted into a separate patch and merged?
  38. Florian Schöppe commented on patch set 10 06/02/22, 06:16

    Reply

    Yep, I also think that would be an improvement. I'll work on that.
  39. Florian Schöppe commented on patch set 10 06/03/22, 13:31

  40. Oliver Klee wrote 06/10/22, 21:42

    Removed reviewer Oliver Klee.
  41. Benni Mack uploaded patch set 11 V +1 07/04/23, 20:22

    Copied Votes: * Code-Review-2 (copy condition: "changekind:NO_CHANGE OR is:MIN")
  42. core-ci voted on patch set 11 V -1 07/04/23, 20:37 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/43436

  43. Stefan Bürk voted on patch set 11 CR 0 07/05/23, 07:10

  44. Stefan Bürk uploaded patch set 12 V -1 07/05/23, 14:35

  45. core-ci voted on patch set 12 V -1 07/05/23, 14:58 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/43535

  46. Benni Mack uploaded patch set 13 V -1 07/05/23, 20:40

  47. core-ci voted on patch set 13 V -1 07/05/23, 21:14 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/43622

  48. Sybille Peters commented on patch set 13 07/06/23, 08:36

    ResetIndexWizardTest.php:25

    You shouldn't use annotation @covers - the checks will fail. Run this locally: Build/Scripts/runTests.sh -s checkAnnotations -p 8.1 https://git.typo3.org/typo3/CI/cms/-/jobs/2358745 Will push a fix and see if I can fix the other problems as well.
  49. Sybille Peters uploaded patch set 14 V -1 07/06/23, 08:37

  50. Sybille Peters commented on patch set 14 07/06/23, 08:37

    ResetIndexWizardTest.php:25 Reply

    Done
  51. Sybille Peters commented on patch set 14 07/06/23, 08:41

    Indexer.php:1129

    You specify return type "string" here, but "mixed" in PHPDoc. phpstan will show this, see: https://git.typo3.org/typo3/CI/cms/-/jobs/2359104#L189 You can run this locally: Build/Scripts/runTests.sh -s phpstan -p 8.1 or run this as quick check (but should run full phpstan check as well): Build/Scripts/runTests.sh -s phpstan -p 8.1 typo3/sysext/indexed_search/Classes/Indexer.php see Contribution Guide: https://docs.typo3.org/m/typo3/guide-contributionworkflow/main/en-us/Testing/Index.html
  52. Sybille Peters uploaded patch set 15 07/06/23, 08:53

  53. Sybille Peters commented on patch set 14 07/06/23, 08:54

    Indexer.php:1129 Reply

    Done
  1. Sybille Peters uploaded patch set 16 07/06/23, 08:57

  2. Sybille Peters commented on patch set 15 07/06/23, 08:57

    ResetIndexWizardTest.php:24

    Test classes must be final: Build/Scripts/runTests.sh -s checkTestClassFinal -p 8.1
  3. core-ci voted on patch set 16 V -1 07/06/23, 11:43 Core CI is not happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/43675

  4. Stefan Bürk uploaded patch set 17 V -1 01/29/24, 11:33

  5. Stefan Bürk uploaded patch set 18 01/29/24, 11:40

  6. Stefan Bürk commented on patch set 17 01/29/24, 11:41

    Reply

    Done

    Indexer.php:1849 Reply

    dropped this. Change in behaviour which was not explained anyway, so kept is state for now.
  7. core-ci voted on patch set 17 V +1 01/29/24, 11:41 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/52404

  8. core-ci voted on patch set 18 V +1 01/29/24, 11:51 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/52407

  9. Kevin Appelt voted on patch set 18 CR +1 01/29/24, 12:09

  10. Simon Schaufelberger commented on patch set 18 01/29/24, 12:45

    please use proper English grammar:)

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:14

    an

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:21

    eliminate

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:29

    For the following... bas been changed

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:45

    need

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:52

    installations
  11. Simon Schaufelberger commented on patch set 18 CR -1 01/29/24, 12:49

    ext_tables.sql:7

    why is the length 60? md5 hashes aren't that long.
  12. Stefan Bürk uploaded patch set 19 CR +1 V +1 01/29/24, 13:43

  13. Stefan Bürk commented on patch set 19 01/29/24, 13:45

    Reply

    Changed you other mentioning. Please feel free to grap and change it directly, as this does not help me where I'm wrong - otherwise the grammar would not have been wrong.

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:14 Reply

    Done

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:21 Reply

    Done

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:29 Reply

    Done

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:45 Reply

    Done

    Breaking-102975-UseFullMd5HashesInIndexed_search.rst:52 Reply

    Done

    ext_tables.sql:7 Reply

    Was thinking about switching from md5 to something else and therefore kept some spaces for now. However, reduced it to varchar(32) for now.
  14. Simon Schaufelberger commented on patch set 19 01/29/24, 13:48

    Reply

    Done
  15. core-ci voted on patch set 19 V +1 01/29/24, 13:49 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/52416

  16. Simon Schaufelberger uploaded patch set 20 V +1 01/29/24, 14:02

  17. Simon Schaufelberger voted on patch set 20 CR +1 V +1 01/29/24, 14:03

  18. core-ci voted on patch set 20 V +1 01/29/24, 14:11 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/52421

  19. Kevin Appelt voted on patch set 20 CR +1 01/29/24, 14:17

  20. Christian Kuhn uploaded patch set 21 CR +1 V +1 01/29/24, 14:25

  21. Simon Schaufelberger voted on patch set 21 CR +1 V +1 01/29/24, 14:26

  22. Christian Kuhn voted on patch set 21 CR +1 V +1 01/29/24, 14:28

  23. core-ci voted on patch set 21 V +1 01/29/24, 14:30 Core CI is happy: https://git.typo3.org/typo3/CI/cms/-/pipelines/52424

  24. Stefan Bürk voted on patch set 21 CR +2 V +2 01/29/24, 14:34

  25. Stefan Bürk merged patch set 22 01/29/24, 14:34