探索 2FA 并尝试实现自己的 OTP 客户端

1. 废话

几年前就听说过 2FA (Two-Factor Authentication) ，但一直没当回事，一是觉得自己的信息没什么价值，应该没人闲的来攻击我，二是觉得自己设计的密码足够复杂，不至于需要额外的认证手段，而且我当时对 2FA 的理解就是设置第二个密码（实际上并不是）。

但最近 Github 说再不弄 2FA 就把你号扬了，虽然我只有在 Github 上倒垃圾的经历，但想到以后还要把我的 Github 写在求职简历上，登陆不上还是有点难受。提起精神弄这个 2FA 发现 Github 推荐了一堆听都没听过的密码管理软件。感觉这要放在我还在用 Windows 的时期可能我会毫不犹豫，随便挑一个装上，但用了几年 Linux 我的开源洁癖越来越严重了，我不想不开源的软件接触我的密码，但搜了一圈发现好像没有纯离线或者可以自己搭建的密码管理软件（实际上是有的，搜索的关键词错了）。然后我就很好奇这个 2FA 到底是什么。

2. 2FA

翻译过来就是双重认证，顾名思义就是账号密码之外再来一层认证机制，可以有很多种形式，比如 Github 提供了：密码管理 APP 、手机短信、物理密钥、 Github 手机 APP 这几种选择。

没错，国内早就开始普及 2FA 了（密码+手机短信验证码），但我觉得大多不是为了安全性，而是另有目的，比如几乎所有国内服务的账号都强制绑定手机，然后隔三差五的要你接短信验证码，到了修改密码之类的敏感操作时反而大多数只需要再输入一边密码就可以，从 2FA 变成了 1FA ；再比如虽然都要手机验证码，但每年都有用户信息泄露， Telegram 上甚至有人靠这些运营盒武器来盈利。

3. OTP

比较主流的第二个 factor 是 OTP (One-Time Password) ，也就是上面提到的密码管理 APP 提供的功能，广义的 OTP 被定义在 RFC2289 ，大概的流程是：

1. 用户设置一个统一的密钥，可以给很多生成端设置同一个，这一步必须保证是私密的（理论上可以只在生成端可见，而对验证端不可见）
2. 验证端和生成端统一一个 seed ，，这个信息不需要保持私密的。通过给多个 OTP 生成端不同的 seed 可以使这些生成端统一使用一个密钥；也可以通过重置这个 seed 来重复使用同一个密钥（不需要冒险修改私密的密钥）
3. 验证端和生成端统一一个序列号，以及认证算法（一个哈希算法），这些信息也不需要保持私密
4. 生成端混合和为（只是简单的字符串拼接），对进行次运算，得到一系列 OTP ，把第次运算得到的 OTP 展示给用户
5. 用户把这个 OTP 传给验证端，验证端需要记录这个 OTP 为

为了方便用户输入，验证端和生成端可以统一一个用户友好的编码方式

到这里，一个 OTP 系统就设置成功了，需要验证时的大概流程是：

1. 验证端展示哈希算法、、序列号（比如上次使用的序列号为，则此次序列号应该为，也就是每次序列号都减一），这些信息也不需要保持私密
2. 生成端把第次运算得到的展示给用户，用户将其发送给验证端
3. 验证端通过判断是否等于来进行验证，这个机制靠重放攻击是破解不了的，因为如果破解成功说明这次破解逆向运算了哈希算法

某个生成端序列号如果用光了可以通过重置 seed 来刷新序列号，此时验证端可以要求验证生成端的第一个 OTP ，来验证生成端完成敏感操作

需要注意的是每次成功验证了一个 OTP ，用户都需要手动将生成端的进行减一操作。

4. HOTP

HOTP (HMAC-Based One-Time Password) 是借助 HMAC 算法的一种升级版 OTP ，被定义在 RFC4226 。

问： HMAC + Hash 比单纯的 Hash 好在哪里？

答：当涉及到拼接时，比如 hash("114" + "514") 的结果与 hash("11" + "4514") 的结果是一致的，而 hmac_hash("114", "514") 与 hmac_hash("11", "4514") 的结果是不一样的。

其实我没太看懂 HOTP 到底是怎么在生成端和验证端使用的，如果按照 RFC4226 的说法：验证端和生成端需要共享一个对称密钥和一个计数器，此时以现代的眼光来看密钥大概率需要在网络上传递，所以这里需要保证这次传递是保密的；生成 OTP 的方法是 trunc(hamc_hash(K, C)) ；而且为了保证验证端和生成端的计数器的同步，验证端还需要被设置 look-ahead 窗口大小，当生成端的 OTP 验证失败时验证端需要最多向前验证个 OTP 。当然每次成功验证一个 OTP 后，用户也需要手动将生成端的进行加一操作。

用 C++ X OpenSSL 来实现的话大概是这样：

#include <string>
#include <vector>

#include <cstddef>
#include <cstdint>

#include "openssl/evp.h"
#include "openssl/hmac.h"

std::vector<std::uint8_t> hmac_sha1(const std::vector<std::uint8_t>& key,
                                    const std::vector<std::uint8_t>& data) {
  std::uint8_t buf[EVP_MAX_MD_SIZE];
  unsigned int len = 0;
  HMAC(EVP_sha1(),
       key.data(),
       static_cast<int>(key.size()),
       data.data(),
       data.size(),
       buf,
       &len);
  return {buf, buf + len};
}

/* uint64 to binary (big endian) */
std::vector<std::uint8_t> u64_2bin_be(const std::uint64_t& u64) {
  std::vector<std::uint8_t> bin_be;
  for (int i = 7; i >= 0; i--) {
    bin_be.emplace_back(static_cast<std::uint8_t>((u64 >> (8 * i)) & 0xff));
  }
  return bin_be;
}

std::string gen_hotp(const std::vector<uint8_t>& secret,
                     const std::uint64_t& counter,
                     const int& digits) {
  std::vector<std::uint8_t> hash = hmac_sha1(secret, u64_2bin_be(counter));
  std::size_t offset = hash[hash.size() - 1] & 0xf;
  /* clang-format off */
  int otp = ((hash[offset]     & 0x7f) << 24)
          | ((hash[offset + 1] & 0xff) << 16)
          | ((hash[offset + 2] & 0xff) << 8)
          |  (hash[offset + 3] & 0xff);
  /* clang-format on */
  char otp_str[digits + 1];
  otp_str[digits] = '\0';
  for (int i = digits; i > 0; i--) {
    otp_str[i - 1] = static_cast<char>((otp % 10) + '0');
    otp /= 10;
  }
  return otp_str;
}

尝试复现 RFC4226 给出的测试用例：

#include <cstdio>

int main(int argc, const char* argv[]) {
  for (int count = 0; count < 10; count++) {
    std::printf(
        "%i: %s\n",
        count,
        gen_hotp({'1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                  '1', '2', '3', '4', '5', '6', '7', '8', '9', '0'},
                 count,
                 6)
            .c_str());
  }
  return 0;
}

输出：

0: 755224
1: 287082
2: 359152
3: 969429
4: 338314
5: 254676
6: 287922
7: 162583
8: 399871
9: 520489

5. TOTP

TOTP (Time-Based One-Time Password) 是 HOTP 的一个扩展，被定义在 RFC6238 ， HOTP 以 counter 作为移动因子， TOTP 可以支持以时间作为移动因子，也就是说把 HOTP 的算法 HOTP = trunc(hmac_sha1(secret, counter) 的 counter 参数换成一个时间相关的参数，这个参数的算法为 T = (curr_unix_time - T0) / period ，其中 T0 为起始计算时间，一般为 0 ， curr_unix_time 为当前 Unix 时间（单位为秒）， period 为时间窗口尺寸，一般为 30 ，也就是说 Unix 时间 xxxxxxxx00 到 xxxxxxxx29 之间计算出来的 T 是相同的，再根据 TOTP 的算法 TOTP = HOTP(secret, T) ，在同一个时间窗口算出的 TOTP 也是相同的，用 C++ 来实现大概是这样的：

#include <ctime>

std::uint64_t get_unix_time_seconds() {
  return static_cast<std::uint64_t>(std::time(nullptr));
}

std::string gen_totp(const std::vector<std::uint8_t>& secret,
                     const std::uint64_t& seconds,
                     const std::uint64_t& period,
                     const int& digits) {
  return gen_hotp(secret, seconds / period, digits);
}

std::string gen_totp_now(const std::vector<std::uint8_t>& secret,
                         const std::uint64_t& period,
                         const int& digits) {
  return gen_totp(secret, get_unix_time_seconds(), period, digits);
}

尝试复现 RFC6238 给出的测试用例的第一行：

int main(int argc, const char* argv[]) {
  std::printf("%lu\n", sizeof(long int));
  return 0;
  for (int count = 0; count < 10; count++) {
    std::printf(
        "%i: %s\n",
        count,
        gen_hotp({'1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                  '1', '2', '3', '4', '5', '6', '7', '8', '9', '0'},
                 count,
                 6)
            .c_str());
  }
  return 0;
}

结果：

94287082

把 HMAC(EVP_sha1(), 一行改成 HMAC(EVP_SHA512(), ，尝试复现第三行：

int main(int argc, const char* argv[]) {
  std::printf("%s\n",
              gen_totp({'1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4', '5', '6', '7', '8', '9', '0',
                        '1', '2', '3', '4'},
                       59,
                       30,
                       8)
                  .c_str());
  return 0;
}

结果：

90693936

RFC 中定义 TOTP 也可以使用 SHA-2 系列算法，但建议 secret 的大小与哈希摘要大小一致，所以 SHA-1 时 secret 为 20 bytes ， SHA-512 为 64 bytes

6. URI 规范

Github 在配置 TOTP 作为 2FA 的第二个 FA 时是要密码管理软件扫描二维码的，这个二维码可以用 zbarimg 进行解码，内容是一个 URI ，我收到的大概是这样的：

otpauth://totp/Github:RayAlto?secret=XXXXXXXXXXXXXXXX&issuer=Github

这个规范不确定最早由谁统一的

去查 IANA 发现被两个无所屌谓的人在 2020 年注册了，提交的文档里甚至连 syntax 都没写，只贴了几个无所屌谓的链接，里面能找到最早的出现地点是 2010 年 Google 开始开发的开源版本 Google Authenticator （已归档，转为专有软件），里面的 ISSUE 确实可以看到一个无所屌谓的人在 2020 提议向 IANA 注册 URI ，然后就莫名其妙的被通过了

但最早使用这个 URI 规范的是 2010 的开源版本 Google Authenticator ，规范的文档可以在 WIKI 页面看到，格式为

otpauth://TYPE/LABEL?PARAMETERS

• TYPE ：只有 hotp 和 totp 两种
• LABEL ：被建议的格式为 issuer:accountname
• PARAMETERS
  • secret ：必有的，是 Base32 编码的二进制数据
  • issuer ：被强烈建议重复一遍 LABEL 里的 issuer
  • algorithm ：可选的，默认为 SHA1
  • digits ：可选的，默认为 6
  • counter ：只有 TYPE 为 hotp 时是有用的且是必须的
  • period ：可选的，默认为 30 只有 TYPE 为 totp 时有用

也就是说 Github 使用 TOTP ，算法为默认的 SHA1 ，生成 OTP 位数为 6 ，时间窗口为 30 。好像 OpenSSL 没有实现 Base32 的编解码，胡乱写一段：

点击展开： Base32 编码

std::string b32enc(const std::vector<std::uint8_t>& data) {
  static const char b32str[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567";
  std::string b32;
  b32.reserve(((data.size() * 8) / 5) + 1);
  std::size_t data_len = data.size();
  std::size_t i = 0;
  int npad = 0;
  // every 5 bytes
  while (data_len > 0) {
    /* 00000000 ???????? ???????? ???????? ????????
     * ^^^^^                                        */
    b32.push_back(b32str[(data[i] >> 3) & 0b00011111]);
    data_len--;

    if (data_len > 0) {
      /* 00000000 00000000 ???????? ???????? ????????
       *      ^^^ ^^                                  */
      b32.push_back(b32str[(((data[i] << 2) & 0b00011100)
                            | ((data[i + 1] >> 6) & 0b00000011))
                           & 0b00011111]);
      /* 00000000 00000000 ???????? ???????? ????????
       *            ^^^^^                             */
      b32.push_back(b32str[(data[i + 1] >> 1) & 0b00011111]);
      data_len--;
    }
    else {
      /* 00000000 -------- -------- -------- --------
       *      ^^^ 00                                  */
      b32.push_back(b32str[((data[i] << 2) & 0b00011100) & 0b00011111]);
      npad = 6;
      break;
    }

    if (data_len > 0) {
      /* 00000000 00000000 00000000 ???????? ????????
       *                 ^ ^^^^                       */
      b32.push_back(b32str[(((data[i + 1] << 4) & 0b00010000)
                            | ((data[i + 2] >> 4) & 0b00001111))
                           & 0b00011111]);
      data_len--;
    }
    else {
      /* 00000000 00000000 -------- -------- --------
       *                 ^ 0000                       */
      b32.push_back(b32str[((data[i + 1] << 4) & 0b00010000) & 0b00011111]);
      npad = 4;
      break;
    }

    if (data_len > 0) {
      /* 00000000 00000000 00000000 00000000 ????????
       *                       ^^^^ ^                 */
      b32.push_back(b32str[(((data[i + 2] << 1) & 0b00011110)
                            | ((data[i + 3] >> 7) & 0b00000001))
                           & 0b00011111]);
      /* 00000000 00000000 00000000 00000000 ????????
       *                             ^^^^^            */
      b32.push_back(b32str[(data[i + 3] >> 2) & 0b00011111]);
      data_len--;
    }
    else {
      /* 00000000 00000000 00000000 -------- --------
       *                       ^^^^ 0                 */
      b32.push_back(b32str[((data[i + 2] << 1) & 0b00011110) & 0b00011111]);
      npad = 3;
      break;
    }

    if (data_len > 0) {
      /* 00000000 00000000 00000000 00000000 00000000
       *                                  ^^ ^^^      */
      b32.push_back(b32str[(((data[i + 3] << 3) & 0b00011000)
                            | ((data[i + 4] >> 5) & 0b00000111))
                           & 0b00011111]);
      /* 00000000 00000000 00000000 00000000 00000000
       *                                        ^^^^^ */
      b32.push_back(b32str[data[i + 4] & 0b00011111]);
      data_len--;
    }
    else {
      /* 00000000 00000000 00000000 00000000 --------
       *                                  ^^ 000      */
      b32.push_back(b32str[((data[i + 3] << 3) & 0b00011000) & 0b00011111]);
      npad = 1;
      break;
    }

    i += 5;
  }

  for (; npad > 0; npad--) {
    b32.push_back('=');
  }

  return b32;
}

点击展开： Base32 解码

// return the binary value of base32 character `c`
constexpr std::uint8_t b32table(const char& c) {
  switch (c) {
  case 'A': return 0; break;
  case 'B': return 1; break;
  case 'C': return 2; break;
  case 'D': return 3; break;
  case 'E': return 4; break;
  case 'F': return 5; break;
  case 'G': return 6; break;
  case 'H': return 7; break;
  case 'I': return 8; break;
  case 'J': return 9; break;
  case 'K': return 10; break;
  case 'L': return 11; break;
  case 'M': return 12; break;
  case 'N': return 13; break;
  case 'O': return 14; break;
  case 'P': return 15; break;
  case 'Q': return 16; break;
  case 'R': return 17; break;
  case 'S': return 18; break;
  case 'T': return 19; break;
  case 'U': return 20; break;
  case 'V': return 21; break;
  case 'W': return 22; break;
  case 'X': return 23; break;
  case 'Y': return 24; break;
  case 'Z': return 25; break;
  case '2': return 26; break;
  case '3': return 27; break;
  case '4': return 28; break;
  case '5': return 29; break;
  case '6': return 30; break;
  case '7': return 31; break;
  case '=': return 32; break;
  default: return 0xff; break;
  }
}

// convert base32 character `c` to binary and save it to `bin5b`
// return false if `c` is '=' or not a valid base32 character
constexpr bool b32bin(const char& c, std::uint8_t& bin5b) {
  bin5b = b32table(c);
  return (bin5b & 0b11100000) == 0;
}

std::vector<std::uint8_t> b32dec(const std::string& b32) {
  std::vector<std::uint8_t> data;
  data.reserve((b32.length() * 5) / 8);
  std::size_t b32len = b32.length();
  std::size_t i = 0;
  std::uint8_t byte = 0;
  // 5 bits from a b32 character
  std::uint8_t bin5b = 0;
  // every 8 b32 characters
  while (b32len > 0 && b32bin(b32[i], bin5b)) {
    /* 00000 ???|?? ????? ?|???? ????|? ????? ??|??? ?????
     * ^^^^^    |          |         |          |          */
    byte |= ((bin5b << 3) & 0b11111000);
    b32len--;

    if (b32len > 0 && b32bin(b32[i + 1], bin5b)) {
      /* 00000 000|00 ????? ?|???? ????|? ????? ??|??? ?????
       *       ^^^|          |         |          |          */
      byte |= ((bin5b >> 2) & 0b00000111);
      data.push_back(byte);
      byte = 0;
      /* 00000 000|00 ????? ?|???? ????|? ????? ??|??? ?????
       *          |^^        |         |          |          */
      byte |= ((bin5b << 6) & 0b11000000);
      b32len--;
    }
    else {
      /* 00000 ---|-- ----- -|---- ----|- ----- --|--- -----
       *       000|          |         |          |          */
      data.push_back(byte);
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 2], bin5b)) {
      /* 00000 000|00 00000 ?|???? ????|? ????? ??|??? ?????
       *          |   ^^^^^  |         |          |          */
      byte |= ((bin5b << 1) & 0b00111110);
      b32len--;
    }
    else {
      /* 00000 000|00 ----- -|---- ----|- ----- --|--- -----
       *          |   00000 0|         |          |          */
      if (byte != 0) {
        // not a pad
        data.push_back(byte);
      }
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 3], bin5b)) {
      /* 00000 000|00 00000 0|0000 ????|? ????? ??|??? ?????
       *          |         ^|         |          |          */
      byte |= ((bin5b >> 4) & 0b00000001);
      data.push_back(byte);
      byte = 0;
      /* 00000 000|00 00000 0|0000 ????|? ????? ??|??? ?????
       *          |          |^^^^     |          |          */
      byte |= ((bin5b << 4) & 0b11110000);
      b32len--;
    }
    else {
      /* 00000 000|00 00000 -|---- ----|- ----- --|--- -----
       *          |         0|         |          |          */
      data.push_back(byte);
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 4], bin5b)) {
      /* 00000 000|00 00000 0|0000 0000|0 ????? ??|??? ?????
       *          |          |     ^^^^|          |          */
      byte |= ((bin5b >> 1) & 0b00001111);
      data.push_back(byte);
      byte = 0;
      /* 00000 000|00 00000 0|0000 0000|0 ????? ??|??? ?????
       *          |          |         |^         |          */
      byte |= ((bin5b << 7) & 0b10000000);
      b32len--;
    }
    else {
      /* 00000 000|00 00000 0|0000 ----|- ----- --|--- -----
       *          |          |     0000|          |          */
      if (byte != 0) {
        data.push_back(byte);
      };
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 5], bin5b)) {
      /* 00000 000|00 00000 0|0000 0000|0 00000 ??|??? ?????
       *          |          |         |  ^^^^^   |          */
      byte |= ((bin5b << 2) & 0b01111100);
      b32len--;
    }
    else {
      /* 00000 000|00 00000 0|0000 0000|0 ----- --|--- -----
       *          |          |         |  00000 00|          */
      if (byte != 0) {
        data.push_back(byte);
      }
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 6], bin5b)) {
      /* 00000 000|00 00000 0|0000 0000|0 00000 00|000 ?????
       *          |          |         |        ^^|          */
      byte |= ((bin5b >> 3) & 0b00000011);
      data.push_back(byte);
      byte = 0;
      /* 00000 000|00 00000 0|0000 0000|0 00000 00|000 ?????
       *          |          |         |          |^^^       */
      byte |= ((bin5b << 5) & 0b11100000);
      b32len--;
    }
    else {
      /* 00000 000|00 00000 0|0000 0000|0 00000 --|--- -----
       *          |          |         |        00|          */
      data.push_back(byte);
      break;
    }

    if (b32len > 0 && b32bin(b32[i + 7], bin5b)) {
      /* 00000 000|00 00000 0|0000 0000|0 00000 00|000 00000
       *          |          |         |          |    ^^^^^ */
      byte |= (bin5b & 0b00011111);
      data.push_back(byte);
      byte = 0;
      b32len--;
    }
    else {
      /* 00000 000|00 00000 0|0000 0000|0 00000 00|000 -----
       *          |          |         |          |    00000 */
      if (byte != 0) {
        data.push_back(byte);
      }
      break;
    }

    i += 8;
  }
  return data;
}

int main(int argc, const char* argv[]) {
  std::string input;
  while (input != "exit") {
    std::cout << "Input: " << std::flush;
    std::cin >> input;
    std::cout << '\n';
    for (const std::uint8_t& b : b32dec(input)) {
      std::printf("%#02x\n", b);
    }
  }
  return 0;
}

7. 尝试实现一个 Github TOTP 生成器

好了，现在可以试着实现一个每秒更新的 Github TOTP 生成器了：

#include <chrono>
#include <iostream>
#include <string>
#include <thread>

int main(int argc, const char* argv[]) {
  std::string secret_b32;
  std::cout << "Paste Github secret (Base32 encoded): " << std::flush;
  std::cin >> secret_b32;
  std::vector<std::uint8_t> secret = b32dec(secret_b32);
  std::cout << "TOTP: " << std::flush;
  while (true) {
    std::cout << gen_totp_now(secret, 30, 6);
    std::this_thread::sleep_for(std::chrono::seconds(1));
    std::cout << "\b\b\b\b\b\b" << std::flush;
  }
  return 0;
}

运行结果：

rayalto@RayAltoNUC ~/program/cpp/test$ ./build/totp
Paste Github secret (Base32 encoded): XXXXXXXXXXXXXXXX
TOTP: 514265

在我的测试下确实可以成功被 Github 录入：

但需要注意的是目前 Github 没有提供删除一个已录入的 TOTP 生成器的方法，也就是说最好把测试用的 secret 记下来，可以考虑对称加密存到电脑里，比如：

# 加密
openssl enc -aes-256-cbc -pbkdf2 -out secret.aes256
# 解密
openssl enc -d -aes-256-cbc -pbkdf2 -in secret.aes256

8. 总结（废话）

令我惊讶的是 OTP 这个概念在 1998 年就有了，而且已经是 IETF 的 draft 了， HOTP 和 TOTP 分别出现在 2005 年和 2011 年，而 Google Authenticator 开源版本最早的一次 commit 可以追溯到 2010 年 5 月 26 日，而且这个时候 Google Authenticator 在设计上就支持了 TOTP 。总之这次探索还是非常有意思的。

这次代码也被我倒进 Github 了： RayAlto/TOTP.Generator