Алгоритм оценки стойкости пароля от Microsoft (Часть 1)

Искал информацию по алгоритмам оценки стойкости паролей, нашел на Хабре топик со ссылкой на Microsoft Password Checker. Как оказалось, проверка стойкости производится с помощью небольшого JS-скрипта, поэтому появилось желание подробно задокументировать алгоритм проверки. Кому-то может быть нужно прояснить, почему делается тот или иной вывод, а кому-то — улучшить алгоритм.

По следам обсуждения на Хабре, соберу основные тезисы.

1. Проверка реализована в виде passwdcheck.js.
2. Эксперименты показали, что проверка не учитывает некоторых простейших вещей, которые сильно снижают стойкость.
3. Рекомендации от Microsoft для создания запоминающихся сложных паролей.

Итак,

Анализ кода показал, что там содержится не один, а целых два анализатора стойкости пароля — текущий, достаточно упрощенный, и старый более глубокий.

Начнем с текущего, по которому анализатор работает сейчас. Во второй части будет разбор старого.

• Уровень стойкости пароля дается в диапазоне [0; 4] в зависимости от вычисляемой «битовой стойкости» bits
  
  • bits ≥ 128 — 4
  • 128 < bits ≥ 64 — 3
  • 64 < bits ≥ 56 — 2
  • bits < 56 — 1
  • пустой пароль — 0
• Для оценки «битовой стойкости» используется формула

  bits = log(charset)*(length/log(2))

  где
  
  • bits — битовая стойкость
  • log — натуральный логарифм
  • length — длина пароля
  • charset — суммарный размер множеств для каждого из типов ниже, если они присутствуют в строке:
    • малые английские буквы [abcdefghijklmnopqrstuvwxyz];
    • заглавные английские буквы [ABCDEFGHIJKLMNOPQRSTUVWXYZ];
    • специальные символы [~`!@#$%^&*()-_+="];
    • цифры [1234567890];
    • остальные символы

Ниже привожу исходный код этого алгоритма на JS (я убрал лишние отладочные комментарии, которые были в тексте).

var alpha = "abcdefghijklmnopqrstuvwxyz";
var upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
var upper_punct = "~`!@#$%^&*()-_+=";
var digits = "1234567890";

var totalChars = 0x7f - 0x20;
var alphaChars = alpha.length;
var upperChars = upper.length;
var upper_punctChars = upper_punct.length;
var digitChars = digits.length;
var otherChars = totalChars - (alphaChars + upperChars + upper_punctChars + digitChars);

function GEId(sID) {
    return document.getElementById(sID);
}
function calculateBits(passWord) {
    
    if (passWord.length < 0) {
        return 0;
    }

    var fAlpha = false;
    var fUpper = false;
    var fUpperPunct = false;
    var fDigit = false;
    var fOther = false;
    var charset = 0;

    for (var i = 0; i < passWord.length; i++) {
        var char = passWord.charAt(i);

        if (alpha.indexOf(char) != -1)
            fAlpha = true;
        else if (upper.indexOf(char) != -1)
            fUpper = true;
        else if (digits.indexOf(char) != -1)
            fDigit = true;
        else if (upper_punct.indexOf(char) != -1)
            fUpperPunct = true;
        else
            fOther = true;

    }

   
    if (fAlpha)
        charset += alphaChars;
    if (fUpper)
        charset += upperChars;
    if (fDigit)
        charset += digitChars;
    if (fUpperPunct)
        charset += upper_punctChars;
    if (fOther)
        charset += otherChars;

    var bits = Math.log(charset) * (passWord.length / Math.log(2));
    
    return Math.floor(bits);
}

function DispPwdStrength(iN, sHL) {
    if (iN > 4) {
        iN = 4;
    }
    for (var i = 0; i < 5; i++) {
        var sHCR = "pwdChkCon0"; if (i <= iN) {
            sHCR = sHL;
        } if (i > 0) {
            GEId("idSM" + i).className = sHCR;
        }
        GEId("idSMT" + i).style.display = ((i == iN) ? "inline" : "none");
    }
}

function EvalPwdStrength(oF, sP) {
    var bits = calculateBits(sP);
    if (bits >= 128) {
        DispPwdStrength(4, 'pwdChkCon4');
    }
    else if (bits < 128 && bits >= 64) {
        DispPwdStrength(3, 'pwdChkCon3');
    }
    else if (bits<64 && bits>=56) {
        DispPwdStrength(2, 'pwdChkCon2');
    }
    else if (bits<56) {
        DispPwdStrength(1, 'pwdChkCon1');
    }
    else {
        DispPwdStrength(0, 'pwdChkCon0');
    }
}

Вывод: тривиально — не значит хорошо. Этот алгоритм совершенно не учитывает многих аспектов стойкости паролей — к примеру, словарные атаки или повторяющиеся символы.

Продолжение см. Часть 2.