Were I doing this w/Moose (or other Moose-ish package like e.g. Moo) I'd think you'd have maybe a role UserAuthProvider (or maybe User::AuthProvider depending on how you want to structure things) that requires providing whatever methods, and then your individual implementation classes include the role with 'User::AuthProvider' and implement the required methods.

Edit: And aside from role vs subclass this is pretty similar to the subclass-and-factory suggestion above.