Refactor randomized password generator into a separate module (#1663)

7 files changed, 390 insertions, 0 deletions

diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGenerator.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGenerator.kt
new file mode 100644
index 00000000..fcd28311
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGenerator.kt
@@ -0,0 +1,100 @@
+/*
+ * Copyright © 2014-2021 The Android Password Store Authors. All Rights Reserved.
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+package dev.msfjarvis.aps.passgen.random
+
+import dev.msfjarvis.aps.passgen.random.util.clearFlag
+import dev.msfjarvis.aps.passgen.random.util.hasFlag
+
+public object PasswordGenerator {
+
+  public const val DEFAULT_LENGTH: Int = 16
+
+  internal const val DIGITS = 0x0001
+  internal const val UPPERS = 0x0002
+  internal const val SYMBOLS = 0x0004
+  internal const val NO_AMBIGUOUS = 0x0008
+  internal const val LOWERS = 0x0020
+
+  internal const val DIGITS_STR = "0123456789"
+  internal const val UPPERS_STR = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+  internal const val LOWERS_STR = "abcdefghijklmnopqrstuvwxyz"
+  internal const val SYMBOLS_STR = "!\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~"
+  internal const val AMBIGUOUS_STR = "B8G6I1l0OQDS5Z2"
+
+  internal fun isValidPassword(password: String, pwFlags: Int): Boolean {
+    if (pwFlags hasFlag DIGITS && password.none { it in DIGITS_STR }) return false
+    if (pwFlags hasFlag UPPERS && password.none { it in UPPERS_STR }) return false
+    if (pwFlags hasFlag LOWERS && password.none { it in LOWERS_STR }) return false
+    if (pwFlags hasFlag SYMBOLS && password.none { it in SYMBOLS_STR }) return false
+    if (pwFlags hasFlag NO_AMBIGUOUS && password.any { it in AMBIGUOUS_STR }) return false
+    return true
+  }
+
+  /** Generates a password using the given [passwordOptions] and [length]. */
+  @Throws(PasswordGeneratorException::class)
+  public fun generate(passwordOptions: List<PasswordOption>, length: Int = DEFAULT_LENGTH): String {
+    var numCharacterCategories = 0
+    var phonemes = true
+    var pwgenFlags = DIGITS or UPPERS or LOWERS
+
+    for (option in PasswordOption.values()) {
+      if (option in passwordOptions) {
+        when (option) {
+          PasswordOption.NoDigits -> pwgenFlags = pwgenFlags.clearFlag(DIGITS)
+          PasswordOption.NoUppercaseLetters -> pwgenFlags = pwgenFlags.clearFlag(UPPERS)
+          PasswordOption.NoLowercaseLetters -> pwgenFlags = pwgenFlags.clearFlag(LOWERS)
+          PasswordOption.NoAmbiguousCharacters -> pwgenFlags = pwgenFlags or NO_AMBIGUOUS
+          PasswordOption.FullyRandom -> phonemes = false
+          PasswordOption.AtLeastOneSymbol -> {
+            numCharacterCategories++
+            pwgenFlags = pwgenFlags or SYMBOLS
+          }
+        }
+      } else {
+        // The No* options are false, so the respective character category will be included.
+        when (option) {
+          PasswordOption.NoDigits,
+          PasswordOption.NoUppercaseLetters,
+          PasswordOption.NoLowercaseLetters -> {
+            numCharacterCategories++
+          }
+          PasswordOption.NoAmbiguousCharacters,
+          PasswordOption.FullyRandom,
+          // Since AtLeastOneSymbol is not negated, it is counted in the if branch.
+          PasswordOption.AtLeastOneSymbol -> {}
+        }
+      }
+    }
+
+    if (pwgenFlags.clearFlag(NO_AMBIGUOUS) == 0) {
+      throw NoCharactersIncludedException()
+    }
+    if (length < numCharacterCategories) {
+      throw PasswordLengthTooShortException()
+    }
+    if (!(pwgenFlags hasFlag UPPERS) && !(pwgenFlags hasFlag LOWERS)) {
+      phonemes = false
+      pwgenFlags = pwgenFlags.clearFlag(NO_AMBIGUOUS)
+    }
+    // Experiments show that phonemes may require more than 1000 iterations to generate a valid
+    // password if the length is not at least 6.
+    if (length < 6) {
+      phonemes = false
+    }
+
+    var password: String?
+    var iterations = 0
+    do {
+      if (iterations++ > 1000) throw MaxIterationsExceededException()
+      password =
+        if (phonemes) {
+          RandomPhonemesGenerator.generate(length, pwgenFlags)
+        } else {
+          RandomPasswordGenerator.generate(length, pwgenFlags)
+        }
+    } while (password == null)
+    return password
+  }
+}
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGeneratorException.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGeneratorException.kt
new file mode 100644
index 00000000..b7d70c39
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGeneratorException.kt
@@ -0,0 +1,10 @@
+package dev.msfjarvis.aps.passgen.random
+
+public sealed class PasswordGeneratorException(message: String? = null, cause: Throwable? = null) :
+  Throwable(message, cause)
+
+public class MaxIterationsExceededException : PasswordGeneratorException()
+
+public class NoCharactersIncludedException : PasswordGeneratorException()
+
+public class PasswordLengthTooShortException : PasswordGeneratorException()
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordOption.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordOption.kt
new file mode 100644
index 00000000..70d0da22
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordOption.kt
@@ -0,0 +1,10 @@
+package dev.msfjarvis.aps.passgen.random
+
+public enum class PasswordOption(public val key: String) {
+  NoDigits("0"),
+  NoUppercaseLetters("A"),
+  NoAmbiguousCharacters("B"),
+  FullyRandom("s"),
+  AtLeastOneSymbol("y"),
+  NoLowercaseLetters("L")
+}
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomNumberGenerator.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomNumberGenerator.kt
new file mode 100644
index 00000000..3bb34325
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomNumberGenerator.kt
@@ -0,0 +1,31 @@
+/*
+ * Copyright © 2014-2021 The Android Password Store Authors. All Rights Reserved.
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+package dev.msfjarvis.aps.passgen.random
+
+import java.security.SecureRandom
+
+private val secureRandom = SecureRandom()
+
+/** Returns a number between 0 (inclusive) and [exclusiveBound](exclusive). */
+internal fun secureRandomNumber(exclusiveBound: Int) = secureRandom.nextInt(exclusiveBound)
+
+/** Returns `true` and `false` with probablity 50% each. */
+internal fun secureRandomBoolean() = secureRandom.nextBoolean()
+
+/**
+ * Returns `true` with probability [percentTrue]% and `false` with probability `(100 - [percentTrue]
+ * )`%.
+ */
+internal fun secureRandomBiasedBoolean(percentTrue: Int): Boolean {
+  require(1 <= percentTrue) { "Probability for returning `true` must be at least 1%" }
+  require(percentTrue <= 99) { "Probability for returning `true` must be at most 99%" }
+  return secureRandomNumber(100) < percentTrue
+}
+
+internal fun <T> Array<T>.secureRandomElement() = this[secureRandomNumber(size)]
+
+internal fun <T> List<T>.secureRandomElement() = this[secureRandomNumber(size)]
+
+internal fun String.secureRandomCharacter() = this[secureRandomNumber(length)]
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPasswordGenerator.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPasswordGenerator.kt
new file mode 100644
index 00000000..32d3ff49
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPasswordGenerator.kt
@@ -0,0 +1,48 @@
+/*
+ * Copyright © 2014-2021 The Android Password Store Authors. All Rights Reserved.
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+package dev.msfjarvis.aps.passgen.random
+
+import dev.msfjarvis.aps.passgen.random.util.hasFlag
+
+internal object RandomPasswordGenerator {
+
+  /**
+   * Generates a random password of length [targetLength], taking the following flags in [pwFlags]
+   * into account, or fails to do so and returns null:
+   *
+   * - [PasswordGenerator.DIGITS]: If set, the password will contain at least one digit; if not set,
+   * the password will not contain any digits.
+   * - [PasswordGenerator.UPPERS]: If set, the password will contain at least one uppercase letter;
+   * if not set, the password will not contain any uppercase letters.
+   * - [PasswordGenerator.LOWERS]: If set, the password will contain at least one lowercase letter;
+   * if not set, the password will not contain any lowercase letters.
+   * - [PasswordGenerator.SYMBOLS]: If set, the password will contain at least one symbol; if not
+   * set, the password will not contain any symbols.
+   * - [PasswordGenerator.NO_AMBIGUOUS]: If set, the password will not contain any ambiguous
+   * characters.
+   */
+  fun generate(targetLength: Int, pwFlags: Int): String? {
+    val bank =
+      listOfNotNull(
+          PasswordGenerator.DIGITS_STR.takeIf { pwFlags hasFlag PasswordGenerator.DIGITS },
+          PasswordGenerator.UPPERS_STR.takeIf { pwFlags hasFlag PasswordGenerator.UPPERS },
+          PasswordGenerator.LOWERS_STR.takeIf { pwFlags hasFlag PasswordGenerator.LOWERS },
+          PasswordGenerator.SYMBOLS_STR.takeIf { pwFlags hasFlag PasswordGenerator.SYMBOLS },
+        )
+        .joinToString("")
+
+    var password = ""
+    while (password.length < targetLength) {
+      val candidate = bank.secureRandomCharacter()
+      if (pwFlags hasFlag PasswordGenerator.NO_AMBIGUOUS &&
+          candidate in PasswordGenerator.AMBIGUOUS_STR
+      ) {
+        continue
+      }
+      password += candidate
+    }
+    return password.takeIf { PasswordGenerator.isValidPassword(it, pwFlags) }
+  }
+}
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPhonemesGenerator.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPhonemesGenerator.kt
new file mode 100644
index 00000000..b9df4324
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPhonemesGenerator.kt
@@ -0,0 +1,180 @@
+/*
+ * Copyright © 2014-2021 The Android Password Store Authors. All Rights Reserved.
+ * SPDX-License-Identifier: GPL-3.0-only
+ */
+package dev.msfjarvis.aps.passgen.random
+
+import dev.msfjarvis.aps.passgen.random.util.hasFlag
+import java.util.Locale
+
+internal object RandomPhonemesGenerator {
+
+  private const val CONSONANT = 0x0001
+  private const val VOWEL = 0x0002
+  private const val DIPHTHONG = 0x0004
+  private const val NOT_FIRST = 0x0008
+
+  private val elements =
+    arrayOf(
+      Element("a", VOWEL),
+      Element("ae", VOWEL or DIPHTHONG),
+      Element("ah", VOWEL or DIPHTHONG),
+      Element("ai", VOWEL or DIPHTHONG),
+      Element("b", CONSONANT),
+      Element("c", CONSONANT),
+      Element("ch", CONSONANT or DIPHTHONG),
+      Element("d", CONSONANT),
+      Element("e", VOWEL),
+      Element("ee", VOWEL or DIPHTHONG),
+      Element("ei", VOWEL or DIPHTHONG),
+      Element("f", CONSONANT),
+      Element("g", CONSONANT),
+      Element("gh", CONSONANT or DIPHTHONG or NOT_FIRST),
+      Element("h", CONSONANT),
+      Element("i", VOWEL),
+      Element("ie", VOWEL or DIPHTHONG),
+      Element("j", CONSONANT),
+      Element("k", CONSONANT),
+      Element("l", CONSONANT),
+      Element("m", CONSONANT),
+      Element("n", CONSONANT),
+      Element("ng", CONSONANT or DIPHTHONG or NOT_FIRST),
+      Element("o", VOWEL),
+      Element("oh", VOWEL or DIPHTHONG),
+      Element("oo", VOWEL or DIPHTHONG),
+      Element("p", CONSONANT),
+      Element("ph", CONSONANT or DIPHTHONG),
+      Element("qu", CONSONANT or DIPHTHONG),
+      Element("r", CONSONANT),
+      Element("s", CONSONANT),
+      Element("sh", CONSONANT or DIPHTHONG),
+      Element("t", CONSONANT),
+      Element("th", CONSONANT or DIPHTHONG),
+      Element("u", VOWEL),
+      Element("v", CONSONANT),
+      Element("w", CONSONANT),
+      Element("x", CONSONANT),
+      Element("y", CONSONANT),
+      Element("z", CONSONANT)
+    )
+
+  private class Element(str: String, val flags: Int) {
+
+    val upperCase = str.uppercase(Locale.ROOT)
+    val lowerCase = str.lowercase(Locale.ROOT)
+    val length = str.length
+    val isAmbiguous = str.any { it in PasswordGenerator.AMBIGUOUS_STR }
+  }
+
+  /**
+   * Generates a random human-readable password of length [targetLength], taking the following flags
+   * in [pwFlags] into account, or fails to do so and returns null:
+   *
+   * - [PasswordGenerator.DIGITS]: If set, the password will contain at least one digit; if not set,
+   * the password will not contain any digits.
+   * - [PasswordGenerator.UPPERS]: If set, the password will contain at least one uppercase letter;
+   * if not set, the password will not contain any uppercase letters.
+   * - [PasswordGenerator.LOWERS]: If set, the password will contain at least one lowercase letter;
+   * if not set and [PasswordGenerator.UPPERS] is set, the password will not contain any lowercase
+   * characters; if both are not set, an exception is thrown.
+   * - [PasswordGenerator.SYMBOLS]: If set, the password will contain at least one symbol; if not
+   * set, the password will not contain any symbols.
+   * - [PasswordGenerator.NO_AMBIGUOUS]: If set, the password will not contain any ambiguous
+   * characters.
+   */
+  fun generate(targetLength: Int, pwFlags: Int): String? {
+    require(pwFlags hasFlag PasswordGenerator.UPPERS || pwFlags hasFlag PasswordGenerator.LOWERS)
+
+    var password = ""
+
+    var isStartOfPart = true
+    var nextBasicType = if (secureRandomBoolean()) VOWEL else CONSONANT
+    var previousFlags = 0
+
+    while (password.length < targetLength) {
+      // First part: Add a single letter or pronounceable pair of letters in varying case.
+
+      val candidate = elements.secureRandomElement()
+
+      // Reroll if the candidate does not fulfill the current requirements.
+      if (!candidate.flags.hasFlag(nextBasicType) ||
+          (isStartOfPart && candidate.flags hasFlag NOT_FIRST) ||
+          // Don't let a diphthong that starts with a vowel follow a vowel.
+          (previousFlags hasFlag VOWEL &&
+            candidate.flags hasFlag VOWEL &&
+            candidate.flags hasFlag DIPHTHONG) ||
+          // Don't add multi-character candidates if we would go over the targetLength.
+          (password.length + candidate.length > targetLength) ||
+          (pwFlags hasFlag PasswordGenerator.NO_AMBIGUOUS && candidate.isAmbiguous)
+      ) {
+        continue
+      }
+
+      // At this point the candidate could be appended to the password, but we still have
+      // to determine the case. If no upper case characters are required, we don't add
+      // any.
+      val useUpperIfBothCasesAllowed =
+        (isStartOfPart || candidate.flags hasFlag CONSONANT) && secureRandomBiasedBoolean(20)
+      password +=
+        if (pwFlags hasFlag PasswordGenerator.UPPERS &&
+            (!(pwFlags hasFlag PasswordGenerator.LOWERS) || useUpperIfBothCasesAllowed)
+        ) {
+          candidate.upperCase
+        } else {
+          candidate.lowerCase
+        }
+
+      // We ensured above that we will not go above the target length.
+      check(password.length <= targetLength)
+      if (password.length == targetLength) break
+
+      // Second part: Add digits and symbols with a certain probability (if requested) if
+      // they would not directly follow the first character in a pronounceable part.
+
+      if (!isStartOfPart &&
+          pwFlags hasFlag PasswordGenerator.DIGITS &&
+          secureRandomBiasedBoolean(30)
+      ) {
+        var randomDigit: Char
+        do {
+          randomDigit = secureRandomNumber(10).toString(10).first()
+        } while (pwFlags hasFlag PasswordGenerator.NO_AMBIGUOUS &&
+          randomDigit in PasswordGenerator.AMBIGUOUS_STR)
+
+        password += randomDigit
+        // Begin a new pronounceable part after every digit.
+        isStartOfPart = true
+        nextBasicType = if (secureRandomBoolean()) VOWEL else CONSONANT
+        previousFlags = 0
+        continue
+      }
+
+      if (!isStartOfPart &&
+          pwFlags hasFlag PasswordGenerator.SYMBOLS &&
+          secureRandomBiasedBoolean(20)
+      ) {
+        var randomSymbol: Char
+        do {
+          randomSymbol = PasswordGenerator.SYMBOLS_STR.secureRandomCharacter()
+        } while (pwFlags hasFlag PasswordGenerator.NO_AMBIGUOUS &&
+          randomSymbol in PasswordGenerator.AMBIGUOUS_STR)
+        password += randomSymbol
+        // Continue the password generation as if nothing was added.
+      }
+
+      // Third part: Determine the basic type of the next character depending on the letter
+      // we just added.
+      nextBasicType =
+        when {
+          candidate.flags.hasFlag(CONSONANT) -> VOWEL
+          previousFlags.hasFlag(VOWEL) ||
+            candidate.flags.hasFlag(DIPHTHONG) ||
+            secureRandomBiasedBoolean(60) -> CONSONANT
+          else -> VOWEL
+        }
+      previousFlags = candidate.flags
+      isStartOfPart = false
+    }
+    return password.takeIf { PasswordGenerator.isValidPassword(it, pwFlags) }
+  }
+}
diff --git a/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/util/Extensions.kt b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/util/Extensions.kt
new file mode 100644
index 00000000..3b38e22b
--- /dev/null
+++ b/passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/util/Extensions.kt
@@ -0,0 +1,11 @@
+package dev.msfjarvis.aps.passgen.random.util
+
+/** Clears the given [flag] from the value of this [Int] */
+internal infix fun Int.clearFlag(flag: Int): Int {
+  return this and flag.inv()
+}
+
+/** Checks if this [Int] contains the given [flag] */
+internal infix fun Int.hasFlag(flag: Int): Boolean {
+  return this and flag == flag
+}