Wow. That is tough. I don't think a regex would solve it though.

Update: as shown above regex will work :)

This seems to work:

#!/usr/bin/perl

use strict;
my ($pass1,$pass2) = @ARGV;
my $diff = 0;
for(0 .. length($pass1)) {
    $diff ++ unless substr($pass1,$_,1) eq substr($pass2,$_,1);
}

if($diff < 3) {
    print "not okay\n";
}
else {
    print "Okay\n";
}
[download]

Lobster Aliens Are attacking the world!