13

We have decided to start work on Multi-factor authentication, by way of releasing an iPhone, Android and Blackberry app for our customers.

Think Google Authenticator's one-time password system.

I can get how I could generate a unique string by hashing using a SALT based on the account secret key plus the device serial number (or other unique identifier).

But does anyone have any idea how you could generate a unique, short number, in the way that google does? And/or does anyone have any good links to articles on achieving this kind of thing?

Many thanks

isNaN1247
  • 17,793
  • 12
  • 71
  • 118

2 Answers2

10

In the end I found that this was very well documented in RFC 4226 and regarding the integer conversion, this can be done using the bitwise operation shown on page 7, essentially it is the same as that shown in the answer below.

There was another post on stackoverflow regarding this in a C# context, which may be worth a read if you are in a similar position.

In C# I basically, hashed a time identifier (i.e. the current time in seconds divided by 30 - to get a long which is valid for the current 30-second interval). Then hashed this using my secret key as the SALT.

And then...

// Use a bitwise operation to get a representative binary code from the hash
// Refer section 5.4 at https://www.rfc-editor.org/rfc/rfc4226#page-7            
int offset = hashBytes[19] & 0xf;
int binaryCode = (hashBytes[offset] & 0x7f) << 24
    | (hashBytes[offset + 1] & 0xff) << 16
    | (hashBytes[offset + 2] & 0xff) << 8
    | (hashBytes[offset + 3] & 0xff);

// Generate the OTP using the binary code. As per RFC 4426 [link above] "Implementations MUST extract a 6-digit code at a minimum 
// and possibly 7 and 8-digit code"
int otp = binaryCode % (int)Math.Pow(10, 6); // where 6 is the password length

return otp.ToString().PadLeft(6, '0');

For those of you who didn't know, Google Authenticator is an open source project - you can browse the source code here.

Community
  • 1
  • 1
isNaN1247
  • 17,793
  • 12
  • 71
  • 118
  • 3
    can you please add the code you used for hashing the time identifier? – Chris Kooken Jan 05 '12 at 20:54
  • @Mrchief they've moved the repo, I've updated the link in the post now – isNaN1247 Feb 15 '13 at 05:42
  • @isNaN1247: Can you please explain this a little bit that how is `binaryCode` obtained? I read `https://www.rfc-editor.org/rfc/rfc4226#page-7` but I didn't understand `& 0x7f` , `& 0x7f) << 24`, `& 0xff) << 16`,... Can you please explain with an example? Thanks alot – Arian Aug 28 '22 at 07:45
6

Well, it doesn't have to be unique. It just has to have a fair bit of entropy. Meaning that the chances of getting the same string are fairly low.

One way of doing this is taking your hash and cutting off a certain number of integers:

var hash = sha1(salt + device + secretKey);
var numbers = base_convert(hash, 16, 10); // Convert hex string to a integer
var key = numbers % 100000; // Limit to 5 digits (you can change this on need)

Just remember to left pad the number out so that it starts with literal 0 if it's too short.

ircmaxell
  • 163,128
  • 34
  • 264
  • 314
  • If you want 'a fair bit of entropy' why would you cut down the hash? Use the whole thing, it's not like it's gonna stress the system extra, but it will enhance your entropy. The Birthday Paradox cuts a lot of these seemingly long odds into something much more likely to be hacked. – Marcin Mar 04 '11 at 13:52
  • 4
    @Marcin: simple. Because who wants to give someone a 40 character hex string to enter from their mobile phone? That's a quick way to get your users to hate you. Sure, in some very secure environments it may be acceptable, but like always you need to balance security with usability. You want a system that's reasonably easy to use... – ircmaxell Mar 04 '11 at 14:00
  • That is very true, you always gotta be aware of what you're protecting. On the other hand, not all hashes, and parts of hashes are created equal. In the end you want to calculate your entropy and pair it with 'X many tries to log in, then lock out' and figure out the probability of someone getting in with a key of N bits of entropy in X tries. – Marcin Mar 04 '11 at 14:04