A complexidade de senha no Ubuntu é controlada pelo PAM. Infelizmente, o PAM é "tipicamente Unix" como em sua abordagem. Significa que ele espalha sua configuração através de um grande número de arquivos muito confusos.
O arquivo que controla a complexidade da senha é:
/etc/pam.d/common-password
Existe uma linha:
password [success=1 default=ignore] pam_unix.so obscure sha512
Que define as regras básicas para a complexidade da senha. Você pode adicionar uma alteração de tamanho mínimo alterando-a para:
password [success=1 default=ignore] pam_unix.so obscure sha512 minlen=12
ou o mínimo que você quiser. Como você pode ver, o padrão já define algumas regras básicas de obscuridade. Essas regras básicas podem ser vistas em:
man pam_unix
Procure por "obscuro".
Há um grande número de módulos pam que podem ser instalados.
apt-cache search libpam-
Deve mostrar a você.
Você terá que caçar a documentação para eles, eu tenho medo. Mas o "cracklib" é uma adição comum.
UPDATE: Eu deveria ter apontado que o parâmetro "obscuro" padrão inclui testes de complexidade baseados em senhas anteriores e simplicidade (comprimento, número de diferentes tipos de caracteres). O exemplo na manpage mostra o cracklib em ação. Instale o libpam_cracklib para que funcione.
Além disso, depois de saber o que alterar, as alterações são as mesmas em outros arquivos, para que você possa impor as mesmas (ou diferentes) verificações de senhas para SSH e outros aplicativos.