findRepeats.js

// use case: password strength checking
// zxcvbn has a "bug" where "passwordpassword" gets a low score, but "password password" gets a really high score
// https://github.com/dropbox/zxcvbn/issues/276

// note: this only searches for repetitions in a 256-character window for repetitions.
// Normally this has no effect because most systems should have a max password length
// less than that anyway. But if we didn't have this, the algorithm would have quadratic
// runtime, so if someone ran this server-side and failed to properly limit password
// length, they'd be vulnerable to a Denial-of-Service attack.

function findRepeats(str) {
    // Outline of the algorithm:
    //   at each location:
    //     start scanning for minimal (2-char) repeats:
    //       if we find one, expand until we know how long of a repeat it is
    //       next, keep scanning to see if we can find a longer one
    //
    // We want to start from minimal repeats and expand, rather than maximal
    // repeats and shrink, because for example, in "thing1 asdf thing2", the fact
    // that we can't find a repeat of "thing1" tells us nothing about whether
    // "thing" repeats; but the fact that we can't find a repeat of "as" guarantees
    // that "asdf" must have no repeats.

    let loopCount = 0

    const repeatByLoc = new Array(str.length)
    function setRepeat(loc, repeat) {
        for (let k = loc; k < loc + repeat.length; k += 1) {
            if (repeat.length > (repeatByLoc[k] || '').length) {
                repeatByLoc[k] = repeat
            }
        }
    }
    for (let i = 0; i <= str.length - 4; i += 1) { // last possible repeat is 6 from the end "...abab"
        let span = 3
        let repeat = ''
        for (let j = i + span; j + span <= str.length && j - i < 256; j += 1) {
            loopCount += 1
            if (str.slice(j, j + span) === str.slice(i, i + span)) {
                // found repeat at least as long as longest so far

                // let's see how long it is:
                while (i + span < j && str.charAt(j + span) === str.charAt(i + span)) {
                    loopCount += 1
                    span += 1
                }

                if (span > repeat.length) {
                    // found new longest repeat
                    repeat = str.slice(i, i + span)
                    setRepeat(i, repeat)
                    setRepeat(j, repeat)
                } else {
                    // found equally long repeat
                    setRepeat(j, repeat)
                }
            }
        }
        //console.log(repeatByLoc)
    }

    const repeats = {}
    for (const loc in repeatByLoc) {
        const repeat = repeatByLoc[loc]
        repeats[repeat] = (repeats[repeat] || 0) + 1
    }

    console.log('inner loop: ' + loopCount)
    return repeats
}