From abc62c2b6b9d7106eb9f53f4994f086835602e57 Mon Sep 17 00:00:00 2001 From: Aditya Wasan Date: Thu, 13 Jan 2022 22:13:53 +0530 Subject: Refactor randomized password generator into a separate module (#1663) --- passgen/random/.gitignore | 1 + passgen/random/build.gradle.kts | 4 + .../aps/passgen/random/PasswordGenerator.kt | 100 ++++++++++++ .../passgen/random/PasswordGeneratorException.kt | 10 ++ .../msfjarvis/aps/passgen/random/PasswordOption.kt | 10 ++ .../aps/passgen/random/RandomNumberGenerator.kt | 31 ++++ .../aps/passgen/random/RandomPasswordGenerator.kt | 48 ++++++ .../aps/passgen/random/RandomPhonemesGenerator.kt | 180 +++++++++++++++++++++ .../aps/passgen/random/util/Extensions.kt | 11 ++ 9 files changed, 395 insertions(+) create mode 100644 passgen/random/.gitignore create mode 100644 passgen/random/build.gradle.kts create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGenerator.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordGeneratorException.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/PasswordOption.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomNumberGenerator.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPasswordGenerator.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/RandomPhonemesGenerator.kt create mode 100644 passgen/random/src/main/kotlin/dev/msfjarvis/aps/passgen/random/util/Extensions.kt (limited to 'passgen') diff --git a/passgen/random/.gitignore b/passgen/random/.gitignore new file mode 100644 index 00000000..42afabfd --- /dev/null +++ b/passgen/random/.gitignore @@ -0,0 +1 @@ +/build \ No newline at end of file diff --git a/passgen/random/build.gradle.kts b/passgen/random/build.gradle.kts new file mode 100644 index 00000000..f91458dd --- /dev/null +++ b/passgen/random/build.gradle.kts @@ -0,0 +1,4 @@ +plugins { + kotlin("jvm") + id("com.github.android-password-store.kotlin-library") +} 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, 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 Array.secureRandomElement() = this[secureRandomNumber(size)] + +internal fun List.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 +} -- cgit v1.2.3