1

I'm trying to implement two-factor authentication on the cheap for a website of mine. My bank uses this sort of grid-based OTP system, so I wanted to emulate it in my application:

Grid-based OTP

Cards are generated using the same functions as passwordmaker.org. A 64 character pseudorandom string is generated for each card as well as a unique card ID number and these are hashed together using HMAC-RIPEMD-160 using the random string as a key and then some sort of mathematical formula is applied to the hash to produce a long string of characters from the list of characters I provide (in this case, the numbers from 0 to 9). I then split this long string up to populate the different values of the card.

The random string and ID are stored in a database in plain text in order to validate a user. Basically everything that is needed to reproduce the entire card is stored in the DB.

Is there anything wrong with this design so far?

Is there any way I can avoid storing the random string in the database but still be able to validate a user given that they only need to provide the values from 3 cells in order to log in?

As I have it, the numbers produced are not (necessarily) unique, so there is nothing that would prevent the value from one particular cell showing up in any other cell. Is this a good or bad thing? My thoughts are that it is good in the sense that if an attacker were to learn the value of some of the cells on the card, this would not make it easier to determine the values from the other cells.

In case anyone is interested, here is the PHP code that creates the card:

/**
 * Gets all cell values for the grid
 * @Return Array
 */
private function _getGridValues()
{
    if (!isset($this->_num_rows)) {
        throw new Exception("Number of rows is not set");
    }
        if (!isset($this->_num_cols)) {
        throw new Exception("Number of cols is not set");
    }
    $hash = $this->_getStringHash($this->_num_rows * $this->_num_cols * 2);

    $rows = str_split($hash, $this->_num_cols * 2);

    foreach ($rows as $index => $row) {
        $cols = str_split($row, 2);

        $this->_values[$index] = $cols;
    }
}

/**
 * Uses HMAC-RIPEMD-160 to create a hash using a key and a salt
 * @Return String
 */
private function _getStringHash($length)
{
    if (!isset($this->_key)) {
        throw new Exception("Key is not set");
    }
    if (!isset($this->_salt)) {
        throw new Exception("Salt is not set");
    }
    $string = '';
    $count = 0;

    while (strlen($string) < $length && $count < 1000) {
        $key = ($count++) ? $this->_key."\n".$count : $this->_key;

        $string .= $this->_rstr2any(hex2bin(hash_hmac('ripemd160',$this->_salt, $key)), $this->_chars);

        if (!$string) {
            throw new Exception("Unknown error");
        }
    }
    return substr($string, 0, $length);
}

/**
* Convert a raw string to an arbitrary string encoding
* @Copyright http://sourceforge.net/projects/passwordmaker/files/PHP%20Edition/
* @License GNU LGPL version 2.1
*/
private function _rstr2any($input, $chars) {
    $divisor = strlen($chars);
    $remainders = Array();

    /* Convert to an array of 16-bit big-endian values, forming the dividend */
    // pad this
    $dividend = array_pad(array(), ceil(strlen($input) / 2), 0);
    $inp = $input; // Because Miquel is a lazy twit and didn't want to do a search and replace
    for($i = 0; $i < count($dividend); $i++) {
        $dividend[$i] = (ord($inp{$i * 2}) << 8) | ord($inp{$i * 2 + 1});
    }

    $full_length = ceil((float)strlen($input) * 8
        / (log(strlen($chars)) / log(2)));
    /*
    * Repeatedly perform a long division. The binary array forms the dividend,
    * the length of the encoding is the divisor. Once computed, the quotient
    * forms the dividend for the next step. We stop when the dividend is zero.
    * All remainders are stored for later use.
    */
    while(count($dividend) > 0) {
        $quotient = Array();
        $x = 0;
        for($i = 0; $i < count($dividend); $i++) {
            $x = ($x << 16) + $dividend[$i];
            $q = floor($x / $divisor);
            $x -= $q * $divisor;
            if(count($quotient) > 0 || $q > 0)
                $quotient[count($quotient)] = $q;
        }
        $remainders[count($remainders)] = $x;
        //$remainders[$j] = $x;
        $dividend = $quotient;
    }

    /* Convert the remainders to the output string */
    $output = "";
    for($i = count($remainders) - 1; $i >= 0; $i--)
        $output .= $chars{(int)$remainders[$i]};

    return $output;
}
  • This is fun but why not just use Google Authenticator or certificates? If you have some of the higher end Intel chips a cert can be stored in the chips hsm. – Andy Boura Aug 9 '14 at 19:33
  • @AndyBoura I may use Google Authenticator as well, but not everybody has a cell phone, which is why I thought of going this way. – Mike Aug 9 '14 at 19:54
1

The main concern I would have with your proposed method of generating card grid data is whether the resulting grid numbers are sufficiently random. Since you are running randomly generated data through a HMAC (which should be fine) but then also a "mathematical formula" it is possible that could bias the resulting numbers. If an attacker knows that certain numbers have a greater chance of showing up in a challenge response then it might aid them in attacking the system.

Otherwise I like the idea of not storing the random string itself as a record. If an attacker gains access to the database they couldn't directly take the record and recreate a user's grid. They would also have to gain access to your code and recreate the conversion process. Of course, your system should not rely on the conversion mechanism remaining secret for its strength, but in reality that does help resist attacks.

It doesn't matter if certain number sequences show up multiple times as long as they were the result of a good random generator, as noted above. While someone may occasionally panic if their grid response is 00000 ("anyone could guess that!") that possibility shouldn't be any likelier than any other.

| improve this answer | |
  • The reason I thought of passing the hash through the "mathematical formula" was to make it so that for the same id and random string, it will always produce the same output and would therefore allow me to verify values from it. I thought of just feeding it through the random number generator again, but according to the docs, it accepts an integer, not a string. However doing a bit more research, I just found this article which seems like a promising way to seed the RNG with a string. – Mike Aug 9 '14 at 21:42
  • I understand the purpose of the formula and I'm not saying it's the wrong approach. I just want to caution you that depending on how you're converting the HMAC value into digits with that formula you may find that certain numbers show up significantly more than others. That may not be a problem, but it's something you would need to test. – PwdRsch Aug 9 '14 at 23:11
  • I understood what you meant too, so in the end I decided to remove the whole _rstr2any() method and replace it with a simple mt_srand(crc32($hash)); and then use mt_rand() to choose the "random" numbers that become the cell values. That way I avoid any of the problems you mention since the values always come from mt_rand(). – Mike Aug 10 '14 at 0:08
1

You seem to be engineering a lot of unnecessary complexity in...unless I've missed something.

If you have 64 cells generate a 64 character sequence of crypto random digits and store it.

Print your card from this. And check responses to challenges against it. It's really very similar to having a 64 character password and asking for a few characters from it to prevent key loggers etc from getting the whole password. Combined with a conventional and correctly stored password it's actually quite neat.

In terms of securing the sequence if you have correctly stored a conventional password the compromise of this wouldn't be a big deal as it won't be reused anywhere and isn't in any way personal. To add protection though have your Web app call a stored procedure in your db to check challenge responses and increment attempt counters, lockout etc etc rather than give the Web db user access to the passwords/secrets tables. This means it would take a full db compromise to get the data rather than just the web server or a SQL Injection or similar.

| improve this answer | |
  • You know, you're probably right. If I'm storing everything needed to generate the characters in the database, I might as well just store the whole character sequence in the database. What matters is the end result, not how to get there. Good point. And of course, this will be combined with a conventional username/password as well as other checks to temporarily lock accounts after too many failed attempts. – Mike Aug 9 '14 at 19:58
  • What's your take on my question about whether it's better to use pseudorandom vs unique values? – Mike Aug 9 '14 at 20:20
  • I'm not quite sure I follow the question. You will be most secure if there are no constraints on the random sequence. The sequence should be generated using a crypto random function (pseudo random). One of the reasons one of the enigma machines was cracked at Bletchley Park was artificial constraints that limited the effective key space. – Andy Boura Aug 9 '14 at 20:33
  • 1
    One further note...it may be worth storing a history of previously asked combinations and not repeat any asked recently. Also make sure the login page can't be refreshed to get a different combination as that would mean I could keep trying until I get a combination I know. (I've seen a bank do this for a 6 digit password! They didn't think it was a concern!) – Andy Boura Aug 10 '14 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.