What solution would you like?
The current password verification based on pattern marching is not so good as it could be.
To improve it I suggest to use zxcvbn4j which is a port dropbox zxcvbn library which measures
the strength of the password.

To implement it such settings need to be added to the plugin configuration:

• plugins.security.restapi.password_min_length - minimum password length, default and minimum is 8
• plugins.security.restapi.password_score_based_validation_strength - the strength of the valid password
  Possible values:
  • fair - very guessable password: protection from throttled online attacks
  • good - somewhat guessable password: protection from unthrottled online attacks
  • strong - safely unguessable password: moderate protection from offline slow-hash scenario
  • very_strong - very unguessable password: strong protection from offline slow-hash scenario

By default the plugin always checks strength of the password and its minimal length together with the regular expression if its set.
The current implementation of checking username similarity will be changed in favor of zxcvbn similarity by adding username to the user_inputs dictionary which means that usernames and passwords like:

• Andrey_Pleskach Andrey_Pleskach_asdsadas!2e23
• andrey_pleskach asdsadas!2e23-Andrey_Pleskach

Additional notes: as @peternied the performance of the library ~5-20ms which is a good trade off since update and set a new user password is not so common operation compare to get list of roles, roles mapping etc.
The calculation time for passwords around 100 characters is ~100ms as result to avoid of performance degradation for big passwords I suggest to set max length of the password to 100.