8

I am trying to implement a kind of email verification system with a node.js server with no state.

The strategy

  1. User sends his email to the server
  2. Server generates a 4 digits code based on the email address and sends it to the user via email.
  3. User sends back the received code via email + the email address to the server
  4. Server re-generates the 4 digits code based on the email and compares it with the code sent by the user.

My implementation to generate the 4 digits code

  1. Create a HEX digest using HMAC SHA-256 hash function
  2. Take the first 3 characters of the digest
  3. Convert them to an integer
  4. If length < 4, concatenates one or multiples 0 at the end
const crypto = require('crypto')

const get4DigitsCode = (message) => {
  const hash = crypto
    .createHmac('sha256', Buffer.from(SECRET_KEY, 'hex'))
    .update(message)
    .digest('hex')

  const first3HexCharacters = hash.slice(0, 3)

  const int = parseInt(first3HexCharacters, 16)

  let code = int.toString()
  code =
    Array(4 - code.length)
      .fill(0)
      .join("") + code

  return code
}

After generating codes for 8293 email addresses, I noticed that I had 4758 duplicates. Is it normal to have this amount of duplicates for a code as this sort? Is my strategy and my implementation secure (ability to guess the code)?

The service is a mobile app, email based (a "mail to self" app). I want a 4 digit code for UX reasons. The user can read the code from the email client notification, easily memorize it and type it in the app (that he never leaves). No tedious copy and paste, not leaving the app, simply read and type. I know that multiple emails would generate the same code, but it doesn't matter as it is just for validating emails. Also I will protect the APIs against brute-force.

Can someone guess the code with this strategy (what are the risks or possible attacks?) and is my current implementation correct?

UPDATE

A better implementation thanks to @duskwuff's answer :

const crypto = require('crypto')

const get4DigitsCode = (message) => {
    const hash = crypto
        .createHmac('sha256', Buffer.from(SECRET, 'hex'))
        .update(message)
        .digest('hex');
    const first4HexCharacters = hash.slice(0, 4);
    const int = parseInt(first4HexCharacters, 16) % 10000;
    let code = int.toString();
    code =
        Array(4 - code.length)
            .fill(0)
            .join('') + code;
    return code;
};
20

The cryptographical hash function with output size n has √n collision with probability 50% due to the birthday paradox.

You took 3 hexadecimal digits which means you get 12 bits. After 26=64 hash generations, you will see a collision with 50% probability.

Collision in hash functions is inevitable due to the fixed-sized output space but the arbitrary length of input space. Pigeonhole Principle tells us that collision is inevitable.

If you want low collision probability you have to use larger output as 128-bit. For 128-bit we expect at least one collision in 264 hashes with 50% probability.

We are not accepting that the system is secret, we assume it is known. E-Mails are not secret and any attacker can create his code by using your source code. An attacker or a group of attackers can try to attack your system due to short token. The mitigation is increasing the token size.

For most applications using read("/dev/urandom", 16) will be fine or you can use HMAC($email, $key) without trimming. Copy and paste shouldn't be a problem for the user.

If you need higher resistance you may use digital signatures; first hash the e-mail then sign.

  • Why 2^6 ? any attacker can create his code by using your code. Of course I will use a secret key for the Hmac. – Thomas Sep 15 at 9:56
  • Basically, you took 3 of the hex code, so you have 12-bits output which has 2^{12} space take the square root. The secret key residing in code is problematic. – kelalaka Sep 15 at 10:00
  • Note, also a random e-mail can impersonate according to the birthday bound which is too low. – kelalaka Sep 15 at 10:37
  • 1
    I don't understand the last paragraph. How can I create a code using your code? Why would your email not be secret? Why would OP need a signature scheme?! – Luc Sep 16 at 12:00
  • @kelalaka I don't see a Problem, using a secret Key with a hash function should be just as secure as using a digital signature. The key will obviously not reside in the code but will be read from a secure environment (just like a private keyfile would be) - the only real downside is the small search-space, which can not easily be rate-limited, since an attacker could just try on average 2000 random mail-addresses to find one which matches the code "1234" – Falco Sep 16 at 14:12
11

There are a couple of pretty serious problems with this approach which will increase the risk of collisions beyond what would ordinarily be expected for a random 4-digit value.

  1. Take the first 3 characters of the digest
  2. Convert them to an integer

Three hexadecimal digits gives you a range of 0 – 4095 (0x000 - 0xfff). This will give you a lot more collisions than expected for a 4-digit number, because you're only using 40% of the possible values.

Use a larger excerpt of the digest and use a modulus operation (% 10000) to force the result to be four decimal digits long. For numerical reasons, using the first 10 hexadecimal digits (40 bits) is pretty close to ideal. (Multiples of 10 bits give you rough powers of 1000, and 40 bits is large but below the maximum safe integer of 253.)

  1. If length < 4, concatenates one or multiples 0 at the end

This introduces even more collisions. Values from 1 - 4, 10 – 40, and 100 – 400 all get mapped onto the same 1000 – 4000 range, and there's some secondary collisions for sets of values like 5, 50, and 500.

If you need to pad with zeroes, do it on the left side, not the right.

  • 2^53 is only the valid range for integers if the language is using an IEEE double to hold numbers. In C/C++ the limit is only 2^32 for int (technically 2^16, but essentially nobody uses that), you have to use long long to be sure of being able to hold 2^40 - but that holds 2^64. In python of course, there is no limit at all to how big an integer can be. – Martin Bonner Sep 16 at 12:21
  • Note that the number of collisions pretty much exactly matches a perfect low-collision hash function. With ~4000 possible hashes and ~8000 inputs, the best you could achieve with the perfect hash function is ~4000 collisions. sha256 is quite neat ;-) – Falco Sep 16 at 14:16
  • Instead of the modulus operation, would it be simpler to take the first 4 digits of the number ? – Thomas Sep 19 at 7:36
  • Simpler, but horribly wrong in many of the same ways as your first attempt. Consider that the first four digits of a number between 0 and 65535 will usually be between 1000 and 6553. – duskwuff Sep 19 at 8:12
  • Ok, got it! And what do you think about the use of HMAC? It is a good way to generate a personalized (with secret) hash? – Thomas Sep 19 at 8:40

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.