src/club/wpia/gigi/passwords/PasswordHashChecker.java

   1 package club.wpia.gigi.passwords;
   2
   3 import java.io.IOException;
   4 import java.nio.ByteBuffer;
   5 import java.nio.channels.FileChannel;
   6 import java.nio.charset.Charset;
   7 import java.security.MessageDigest;
   8 import java.util.Arrays;
   9
  10 import club.wpia.gigi.GigiApiException;
  11 import club.wpia.gigi.output.template.SprintfCommand;
  12
  13 /**
  14  * A {@link PasswordChecker} which searches for a password
  15  * in a given file containing hashes of known breached passwords.
  16  * If the password is found, it is rejected.
  17  */
  18 public class PasswordHashChecker implements PasswordChecker {
  19
  20     private final FileChannel database;
  21
  22     private final MessageDigest digest;
  23
  24     private final int digestLength;
  25
  26     private final ByteBuffer hashBuffer;
  27
  28     /**
  29      * @param database The database of password hashes.
  30      *                 It should contain the hashes in binary format, with no separating characters,
  31      *                 sorted in ascending order.
  32      * @param digest   The digest function that was used to compile the database.
  33      */
  34     public PasswordHashChecker(FileChannel database, MessageDigest digest) {
  35         this.database = database;
  36         this.digest = digest;
  37         this.digestLength = digest.getDigestLength();
  38         this.hashBuffer = ByteBuffer.allocate(digestLength);
  39     }
  40
  41     @Override
  42     public GigiApiException checkPassword(String password, String[] nameParts, String email) {
  43         byte[] passwordHash = passwordHash(password);
  44         boolean knownPasswordHash;
  45         try {
  46             knownPasswordHash = knownPasswordHash(passwordHash);
  47         } catch (IOException e) {
  48             System.err.printf(
  49                 "Error while reading password hash database, ACCEPTING POTENTIALLY KNOWN PASSWORD for user with email %s.",
  50                 email
  51             );
  52             e.printStackTrace();
  53             knownPasswordHash = false;
  54         }
  55         if (knownPasswordHash) {
  56             return new GigiApiException(new SprintfCommand(
  57                 "The password you submitted was found in a public database of passwords exposed in data breaches. If you use this password anywhere else, you should change it. See our {0}FAQ{1} for more information.",
  58                 Arrays.asList("!(/kb/knownPasswordHash", "!'</a>'")
  59             ));
  60         } else {
  61             return null;
  62         }
  63     }
  64
  65     private byte[] passwordHash(String password) {
  66         byte[] passwordBytes = password.getBytes(Charset.forName("UTF-8"));
  67         byte[] passwordHash;
  68         synchronized (digest) {
  69             digest.reset();
  70             digest.update(passwordBytes);
  71             passwordHash = digest.digest();
  72         }
  73         return passwordHash;
  74     }
  75
  76     private boolean knownPasswordHash(byte[] passwordHash) throws IOException {
  77         long targetEstimate = estimateHashOffset(passwordHash);
  78         long bestGuess = targetEstimate;
  79         bestGuess = clampOffset(bestGuess);
  80
  81         hashBuffer.clear();
  82         database.read(hashBuffer, bestGuess);
  83         // first, guess the location of the hash within the file
  84         for (int i = 0; i < 4; i++) {
  85             long bestGuessEstimate = estimateHashOffset(hashBuffer.array());
  86             if (bestGuessEstimate == targetEstimate) {
  87                 break;
  88             }
  89             bestGuess = bestGuess + targetEstimate - bestGuessEstimate;
  90             bestGuess = clampOffset(bestGuess);
  91             hashBuffer.clear();
  92             database.read(hashBuffer, bestGuess);
  93         }
  94         int searchDirection = compareHashes(passwordHash, hashBuffer.array());
  95         if (searchDirection == 0) {
  96             return true;
  97         }
  98         // then, do a linear search from that location until we’ve either found or moved past the hash
  99         int newSearchDirection = searchDirection;
 100         while (searchDirection == newSearchDirection) {
 101             bestGuess += digestLength * searchDirection;
 102             if (bestGuess < 0 || bestGuess >= database.size()) {
 103                 break;
 104             }
 105             hashBuffer.clear();
 106             database.read(hashBuffer, bestGuess);
 107             newSearchDirection = compareHashes(passwordHash, hashBuffer.array());
 108         }
 109         return newSearchDirection == 0;
 110     }
 111
 112     private int compareHashes(byte[] left, byte[] right) {
 113         for (int i = 0; i < digestLength; i++) {
 114             int leftByte = Byte.toUnsignedInt(left[i]);
 115             int rightByte = Byte.toUnsignedInt(right[i]);
 116             if (leftByte < rightByte) {
 117                 return -1;
 118             }
 119             if (leftByte > rightByte) {
 120                 return 1;
 121             }
 122         }
 123         return 0;
 124     }
 125
 126     private long estimateHashOffset(byte[] hash) throws IOException {
 127         long pos = (database.size()
 128                 * ((hash[0] & 0xFF) << 8 | (hash[1] & 0xFF)))
 129                 / (1L << 16);
 130         pos += (database.size()
 131                 * ((hash[2] & 0xFF) << 8 | (hash[3] & 0xFF)))
 132                 / (1L << 32);
 133         return (pos / digestLength) * digestLength;
 134     }
 135
 136     private long clampOffset(long offset) throws IOException {
 137         if (offset < 0) {
 138             return 0;
 139         }
 140         if (offset >= database.size()) {
 141             return database.size() - 1;
 142         }
 143         return offset;
 144     }
 145 }