HOTP & TOTP 实现

在这篇文章中，我会粗略的介绍从实现 HOTP 到 TOTP 的主要重点过程。我不会细致的阐述每行代码的作用，相反，这篇文章主要提炼出实现步骤和我在开发过程中遇到的一些需要注意的地方。

如果你想参考详细的 HOTP 和 TOTP 的过程，原理和资料，请查看下列的网站：

• RFC 4226 - HOTP: An HMAC-Based One-Time Password Algorithm
• RFC 6238 - TOTP: Time-Based One-Time Password Algorithm
• Wikipedia - HMAC-based one-time password
• Wikipedia - Time-based one-time password
• Medium - Implementing Your Own Time-Based OTP Generator

为了实现 RFC 6238 (TOTP)，根据标准的 Abstract 部分已经说明 TOTP 是 HOTP 的一个拓展，因此需要对 RFC 4226 (HOTP) 进行实现

This document describes an extension of the One-Time Password (OTP) algorithm, namely the HMAC-based One-Time Password (HOTP) algorithm, as defined in RFC 4226, to support the time-based moving factor.

RFC 4226 (HOTP) 实现

实现 HOTP 有三个重要的，今天我们会用到的参数

• Key
• Counter
• Digit

Symbol  Represents
   -------------------------------------------------------------------
   C       8-byte counter value, the moving factor.  This counter
           MUST be synchronized between the HOTP generator (client)
           and the HOTP validator (server).

   K       shared secret between client and server; each HOTP
           generator has a different and unique secret K.

   T       throttling parameter: the server will refuse connections
           from a user after T unsuccessful authentication attempts.

   s       resynchronization parameter: the server will attempt to
           verify a received authenticator across s consecutive
           counter values.

   Digit   number of digits in an HOTP value; system parameter.

Step 1

利用 HMAC-SHA1 算法生成出散列值 hs。密钥是上文提到的 K (Key) ，消息为 C (Counter in 8-byte)

Step 1: Generate an HMAC-SHA-1 value Let HS = HMAC-SHA-1(K,C)  // HS is a 20-byte string

var hmac = new HMACSHA1(Secret);
var hs = hmac.ComputeHash(Counter);

上面的代码使用 C# 编写，仅保留主要部分作为示例

Step 2

这一步需要使用一个叫做 Dynamic Truncdation 的方法，将 20 字节的 HMAC 哈希结果转成一个较短的固定代码作为一次性密码

   Step 2: Generate a 4-byte string (Dynamic Truncation)
   Let Sbits = DT(HS)   //  DT, defined below,
                        //  returns a 31-bit string

由于 .NET 中的 hmac.ComputeHash 方法将会返回 byte[] 类型，我将直接操作 byte[] 类型的数据

private int DynamicTruncation(byte[] p)
{
    var offset = p.Last() & 0x0F; // Offset value

    return ((p[offset] & 0x7F) << 24) |
        ((p[offset + 1] & 0xFF) << 16) |
        ((p[offset + 2] & 0xFF) << 8) |
        (p[offset + 3] & 0xFF); // Return the Last 31 bits of p
}

这一步已经完成了整个第二步，返回类型为整数，因为我们要带入第三步参与数字运算

Step 3

   Step 3: Compute an HOTP value
   Let Snum  = StToNum(Sbits)   // Convert S to a number in
                                    0...2^{31}-1
   Return D = Snum mod 10^Digit //  D is a number in the range
                                    0...10^{Digit}-1

这一步需要将我们得到的数字进行取模运算，算法为 num % 10^Digit

var code = (DynamicTruncation(hs) % (int)Math.Pow(10, Digit)) // hs is defined in Step 1.

到这一步就完成了 HOTP 的一次性密码生成，我们将它转为字符串类型

var code = (DynamicTruncation(hs) % (int)Math.Pow(10, Digit)).ToString().PadLeft(Digit, '0');

由于在计算 Dynamic Truncation 和对数字进行取模运算时，我们的数据类型为数字。因此，如果一次性密码中包含有 0 出现在数量级最高位，在数学中的 0 将会被舍弃。所以在我们转换成字符串 (或者在任何语言中可以代表任意文本的数据类型) 需要进行相应的 PadLeft 操作，在此，C# 中可以直接使用 string.PadLeft() 方法

为了验证其算法正确性，在标准的附录 D 中携带了测试用例供开发者测试

Appendix D - HOTP Algorithm: Test Values

   The following test data uses the ASCII string
   "12345678901234567890" for the secret:

   Secret = 0x3132333435363738393031323334353637383930

   Table 1 details for each count, the intermediate HMAC value.

   Count    Hexadecimal HMAC-SHA-1(secret, count)
   0        cc93cf18508d94934c64b65d8ba7667fb7cde4b0
   1        75a48a19d4cbe100644e8ac1397eea747a2d33ab
   2        0bacb7fa082fef30782211938bc1c5e70416ff44
   3        66c28227d03a2d5529262ff016a1e6ef76557ece
   4        a904c900a64b35909874b33e61c5938a8e15ed1c
   5        a37e783d7b7233c083d4f62926c7a25f238d0316
   6        bc9cd28561042c83f219324d3c607256c03272ae
   7        a4fb960c0bc06e1eabb804e5b397cdc4b45596fa
   8        1b3c89f65e6c9e883012052823443f048b4332db
   9        1637409809a679dc698207310c8c7fc07290d9e5

   Table 2 details for each count the truncated values (both in
   hexadecimal and decimal) and then the HOTP value.

                     Truncated
   Count    Hexadecimal    Decimal        HOTP
   0        4c93cf18       1284755224     755224
   1        41397eea       1094287082     287082
   2         82fef30        137359152     359152
   3        66ef7655       1726969429     969429
   4        61c5938a       1640338314     338314
   5        33c083d4        868254676     254676
   6        7256c032       1918287922     287922
   7         4e5b397         82162583     162583
   8        2823443f        673399871     399871
   9        2679dc69        645520489     520489

class HOTP
{
    private byte[] Secret { get; set; }
    private byte[] Counter { get; set; }
    private int Digit { get; set; }

    public HOTP(byte[] secret, int counter, int digit)
    {
        Secret = secret;
        Digit = digit;
        var bytes = new byte[8];

        for (var i = 7; i >= 0; i--)
        {
            bytes[i] = (byte)(counter & 0xFF);

            counter >>= 8;
        }

        Counter = bytes;
    }

    public string Code()
    {
        var hmac = new HMACSHA1(Secret);
        var hs = hmac.ComputeHash(Counter);
        var code = (DynamicTruncation(hs) % (int)Math.Pow(10, Digit)).ToString().PadLeft(Digit, '0');

        return code;
    }

    private int DynamicTruncation(byte[] p)
    {
        var offset = p.Last() & 0x0F;

        return ((p[offset] & 0x7F) << 24) |
            ((p[offset + 1] & 0xFF) << 16) |
            ((p[offset + 2] & 0xFF) << 8) |
            (p[offset + 3] & 0xFF);
    }
}

class Program
{
    public static void Main()
    {
        for (int i = 0; i != 10; i++)
        {
            var hotp = new HOTP(Encoding.ASCII.GetBytes("12345678901234567890"), i, 6);

            Console.WriteLine(hotp.Code());
        }
    }
}

755224
287082
359152
969429
338314
254676
287922
162583
399871
520489

C:\Users\xyfbs\source\repos\ConsoleTotp\ConsoleTotp\bin\Debug\net7.0\ConsoleTotp.exe (process 26588) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . .

RFC 6238 (TOTP) 实现

完成了对于 HOTP 的实现，我们就已经做到了整个项目的一大半了。因为 TOTP 是对 HOTP 的一个拓展，因此我们的工作量会大大减少。

前往标准的 Section 4 部分是对整个 TOTP 算法的核心描述

Step 1

   o  X represents the time step in seconds (default value X =
      30 seconds) and is a system parameter.

   o  T0 is the Unix time to start counting time steps (default value is
      0, i.e., the Unix epoch) and is also a system parameter.

   Basically, we define TOTP as TOTP = HOTP(K, T), where T is an integer
   and represents the number of time steps between the initial counter
   time T0 and the current Unix time.

   More specifically, T = (Current Unix time - T0) / X, where the
   default floor function is used in the computation.

   For example, with T0 = 0 and Time Step X = 30, T = 1 if the current
   Unix time is 59 seconds, and T = 2 if the current Unix time is
   60 seconds.

根据上面的描述，我们需要获得时间步长 X 和时间戳参数 T (一般为 UTC 时间戳，单位为秒)。一般情况下，参数 T0 为 0，因此可以不执行减法计算。

var x = 30; // Time step in seconds
var timeestamp = DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1)).TotalSeconds; // Current UTC timestamp
var t = (int)Math.Floor(unixTimestamp / x);

Step 2

最后，将参数 T 作为 HOTP 的 Counter 参数传入，就可以得到 TOTP 的一次性密码

var totp = new HOTP(SECRET, t, DIGIT); // This is pseudocode, please refer to the complete code example provided at the end of the article.
var code = totp.Code(); // Also pseudocode...

Step 3

这一步我们将探讨 TOTP 算法实现完毕后的正确性...首先，这是整个项目完整的代码

class HOTP
{
    private byte[] Secret { get; set; }
    private byte[] Counter { get; set; }
    private int Digit { get; set; }

    public HOTP(byte[] secret, int counter, int digit)
    {
        Secret = secret;
        Digit = digit;
        var bytes = new byte[8];

        for (var i = 7; i >= 0; i--)
        {
            bytes[i] = (byte)(counter & 0xFF);

            counter >>= 8;
        }

        Counter = bytes;
    }

    public string Code()
    {
        var hmac = new HMACSHA1(Secret);
        var hs = hmac.ComputeHash(Counter);
        var code = (DynamicTruncation(hs) % (int)Math.Pow(10, Digit)).ToString().PadLeft(Digit, '0');

        return code;
    }

    private int DynamicTruncation(byte[] p)
    {
        var offset = p.Last() & 0x0F;

        return ((p[offset] & 0x7F) << 24) |
            ((p[offset + 1] & 0xFF) << 16) |
            ((p[offset + 2] & 0xFF) << 8) |
            (p[offset + 3] & 0xFF);
    }
}

public class TOTP
{
    private byte[] Secret;
    private int Timestep = 30;
    private int Digit = 6;

    public TOTP(byte[] secret)
    {
        Secret = secret;
    }

    public TOTP(byte[] secret, int timestep)
    {
        Secret = secret;
        Timestep = timestep;
    }

    public TOTP(byte[] secret, int timestep, int digit)
    {
        Secret = secret;
        Timestep = timestep;
        Digit = digit;
    }

    public string Code()
    {
        var unixTimestamp = DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1)).TotalSeconds;
        var t = (int)Math.Floor(unixTimestamp / Timestep);
        var hotp = new HOTP(Secret, t, Digit);
        var code = hotp.Code();

        return code;
    }
}

在标准的 Appendix B 中同样具有跟 HOTP 一样的测试用例。但请注意，测试用例中的 Digit 参数为 8 位，而不是 6 位。

   The test token shared secret uses the ASCII string value
   "12345678901234567890".  With Time Step X = 30, and the Unix epoch as
   the initial value to count time steps, where T0 = 0, the TOTP
   algorithm will display the following values for specified modes and
   timestamps.

  +-------------+--------------+------------------+----------+--------+
  |  Time (sec) |   UTC Time   | Value of T (hex) |   TOTP   |  Mode  |
  +-------------+--------------+------------------+----------+--------+
  |      59     |  1970-01-01  | 0000000000000001 | 94287082 |  SHA1  |
  |             |   00:00:59   |                  |          |        |
  |      59     |  1970-01-01  | 0000000000000001 | 46119246 | SHA256 |
  |             |   00:00:59   |                  |          |        |
  |      59     |  1970-01-01  | 0000000000000001 | 90693936 | SHA512 |
  |             |   00:00:59   |                  |          |        |
  |  1111111109 |  2005-03-18  | 00000000023523EC | 07081804 |  SHA1  |
  |             |   01:58:29   |                  |          |        |
  |  1111111109 |  2005-03-18  | 00000000023523EC | 68084774 | SHA256 |
  |             |   01:58:29   |                  |          |        |
  |  1111111109 |  2005-03-18  | 00000000023523EC | 25091201 | SHA512 |
  |             |   01:58:29   |                  |          |        |
  |  1111111111 |  2005-03-18  | 00000000023523ED | 14050471 |  SHA1  |
  |             |   01:58:31   |                  |          |        |
  |  1111111111 |  2005-03-18  | 00000000023523ED | 67062674 | SHA256 |
  |             |   01:58:31   |                  |          |        |
  |  1111111111 |  2005-03-18  | 00000000023523ED | 99943326 | SHA512 |
  |             |   01:58:31   |                  |          |        |
  |  1234567890 |  2009-02-13  | 000000000273EF07 | 89005924 |  SHA1  |
  |             |   23:31:30   |                  |          |        |
  |  1234567890 |  2009-02-13  | 000000000273EF07 | 91819424 | SHA256 |
  |             |   23:31:30   |                  |          |        |
  |  1234567890 |  2009-02-13  | 000000000273EF07 | 93441116 | SHA512 |
  |             |   23:31:30   |                  |          |        |
  |  2000000000 |  2033-05-18  | 0000000003F940AA | 69279037 |  SHA1  |
  |             |   03:33:20   |                  |          |        |
  |  2000000000 |  2033-05-18  | 0000000003F940AA | 90698825 | SHA256 |
  |             |   03:33:20   |                  |          |        |
  |  2000000000 |  2033-05-18  | 0000000003F940AA | 38618901 | SHA512 |
  |             |   03:33:20   |                  |          |        |
  | 20000000000 |  2603-10-11  | 0000000027BC86AA | 65353130 |  SHA1  |
  |             |   11:33:20   |                  |          |        |
  | 20000000000 |  2603-10-11  | 0000000027BC86AA | 77737706 | SHA256 |
  |             |   11:33:20   |                  |          |        |
  | 20000000000 |  2603-10-11  | 0000000027BC86AA | 47863826 | SHA512 |
  |             |   11:33:20   |                  |          |        |
  +-------------+--------------+------------------+----------+--------+

为了测试该标准实现的正确性，需要根据测试用例中提供的时间戳和密钥计算出同样的 TOTP 结果。因此我们需要稍作修改，将 TOTP 的 T 参数相关的逻辑代码修改成如下:

  +-------------+--------------+------------------+----------+--------+
  |  Time (sec) |   UTC Time   | Value of T (hex) |   TOTP   |  Mode  |
  +-------------+--------------+------------------+----------+--------+
  |  1234567890 |  2009-02-13  | 000000000273EF07 | 89005924 |  SHA1  |
  +-------------+--------------+------------------+----------+--------+

public string Code()
{
    var unixTimestamp = DateTime.UtcNow.Subtract(new DateTime(1970, 1, 1)).TotalSeconds;
    var testTimestamp = 1234567890;
    var t = (int)Math.Floor((double)testTimestamp / Timestep);
    var hotp = new HOTP(Secret, t, Digit);
    var code = hotp.Code();

    return code;
}

class Program
{
    public static void Main()
    {
        var totp = new TOTP(Encoding.ASCII.GetBytes("12345678901234567890"), 30, 8);

        Console.WriteLine(totp.Code());
    }
}

89005924

C:\Users\xyfbs\source\repos\ConsoleTotp\ConsoleTotp\bin\Debug\net7.0\ConsoleTotp.exe (process 45364) exited with code 0.
To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.
Press any key to close this window . . .

看，我们能计算出标准中的测试用例给的正确结果了

附录

Base32

在一般真实的使用情况下，密钥通常经过了 Base32 编码。为了获得正确的结果，通常开发者需要先对密钥进行 Base32 解码的操作。因此我将在本文章提供我使用的 Base32 解码的实现。

/*
 * Derived from https://github.com/google/google-authenticator-android/blob/master/AuthenticatorApp/src/main/java/com/google/android/apps/authenticator/Base32String.java
 *
 * Copyright (C) 2016 BravoTango86
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

using System;
using System.Text;

public static class Base32
{
    private static readonly char[] _digits = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567".ToCharArray();
    private const int _mask = 31;
    private const int _shift = 5;

    private static int CharToInt(char c)
    {
        switch (c)
        {
            case 'A': return 0;
            case 'B': return 1;
            case 'C': return 2;
            case 'D': return 3;
            case 'E': return 4;
            case 'F': return 5;
            case 'G': return 6;
            case 'H': return 7;
            case 'I': return 8;
            case 'J': return 9;
            case 'K': return 10;
            case 'L': return 11;
            case 'M': return 12;
            case 'N': return 13;
            case 'O': return 14;
            case 'P': return 15;
            case 'Q': return 16;
            case 'R': return 17;
            case 'S': return 18;
            case 'T': return 19;
            case 'U': return 20;
            case 'V': return 21;
            case 'W': return 22;
            case 'X': return 23;
            case 'Y': return 24;
            case 'Z': return 25;
            case '2': return 26;
            case '3': return 27;
            case '4': return 28;
            case '5': return 29;
            case '6': return 30;
            case '7': return 31;
        }
        return -1;
    }

    public static byte[] FromBase32String(string encoded)
    {
        if (encoded == null)
            throw new ArgumentNullException(nameof(encoded));

        // Remove whitespace and padding. Note: the padding is used as hint
        // to determine how many bits to decode from the last incomplete chunk
        // Also, canonicalize to all upper case
        encoded = encoded.Trim().TrimEnd('=').ToUpper();
        if (encoded.Length == 0)
            return new byte[0];

        var outLength = encoded.Length * _shift / 8;
        var result = new byte[outLength];
        var buffer = 0;
        var next = 0;
        var bitsLeft = 0;
        var charValue = 0;
        foreach (var c in encoded)
        {
            charValue = CharToInt(c);
            if (charValue < 0)
                throw new FormatException("Illegal character: `" + c + "`");

            buffer <<= _shift;
            buffer |= charValue & _mask;
            bitsLeft += _shift;
            if (bitsLeft >= 8)
            {
                result[next++] = (byte)(buffer >> (bitsLeft - 8));
                bitsLeft -= 8;
            }
        }

        return result;
    }

    public static string ToBase32String(byte[] data, bool padOutput = false)
    {
        return ToBase32String(data, 0, data.Length, padOutput);
    }

    public static string ToBase32String(byte[] data, int offset, int length, bool padOutput = false)
    {
        if (data == null)
            throw new ArgumentNullException(nameof(data));

        if (offset < 0)
            throw new ArgumentOutOfRangeException(nameof(offset));

        if (length < 0)
            throw new ArgumentOutOfRangeException(nameof(length));

        if ((offset + length) > data.Length)
            throw new ArgumentOutOfRangeException();

        if (length == 0)
            return "";

        // SHIFT is the number of bits per output character, so the length of the
        // output is the length of the input multiplied by 8/SHIFT, rounded up.
        // The computation below will fail, so don't do it.
        if (length >= (1 << 28))
            throw new ArgumentOutOfRangeException(nameof(data));

        var outputLength = (length * 8 + _shift - 1) / _shift;
        var result = new StringBuilder(outputLength);

        var last = offset + length;
        int buffer = data[offset++];
        var bitsLeft = 8;
        while (bitsLeft > 0 || offset < last)
        {
            if (bitsLeft < _shift)
            {
                if (offset < last)
                {
                    buffer <<= 8;
                    buffer |= (data[offset++] & 0xff);
                    bitsLeft += 8;
                }
                else
                {
                    int pad = _shift - bitsLeft;
                    buffer <<= pad;
                    bitsLeft += pad;
                }
            }
            int index = _mask & (buffer >> (bitsLeft - _shift));
            bitsLeft -= _shift;
            result.Append(_digits[index]);
        }
        if (padOutput)
        {
            int padding = 8 - (result.Length % 8);
            if (padding > 0) result.Append('=', padding == 8 ? 0 : padding);
        }
        return result.ToString();
    }
}

为了测试 TOTP 代码在真实密钥情况下的可用性，我推荐 Authentication Test 的 TOTP 测试页面作为测试用例。密钥一般为 I65VU7K5ZQL7WB4E (但请还是根据网站提供的密钥为准)。时间步长 X 参数和 Digit 参数分别为常用的 30 和 6。

class Program
{
    public static void Main()
    {
        var totp = new TOTP(Base32.FromBase32String("I65VU7K5ZQL7WB4E"), 30, 6);

        Console.WriteLine(totp.Code()); // You will obtain a usable TOTP one-time password result.
    }
}

得到结果后，将 TOTP 密码填入，点击登录。并且观察是否能登陆成功即可。