动态密码TOTP

昨天碰到一个有意思的事情,做了一道题,然后提交的时候需要根据定义好的共享密钥的规则来生成一个TOTP动态密码,服务端会对不同的人提交的时候生成的动态密码做校验,于是就学习了一下TOTP算法,并基于GolangJava作出了相应的实现。

生成的这个TOTP动态密码要求是10位的长度,如果只是直接网上搬别人写的代码基本无用,所以就有了这一篇。

HOTPTOTP算法

TOTP是一种基于时间的一次性密码算法,它根据预共享的密钥和当前时间计算一次性密码。该算法已经被互联网任务工作组接纳为RFC 6238标准,成为主动开放认证(OAUTH)的基础。

TOTP基于HOTPRFC 4226),它使用一个时间戳来代替HOTP中的计数器(即HOTP算法中的C)。

HOTP的算法公式如下:

$$HOTP(K,C) = Truncate(HMAC-SHA-1(K,C))$$

主要有两个输入:一个是共享密钥K,另一个是计数器C

  • K:共享密钥,要求每个HOTP的生成器都必须是唯一的;
  • C:计数器,是一个8-byte的值,计数器需要在服务端和客户端之间同步以保持一致;

HOTP算法基于一个动态变化的计数器值和一个静态不变的密钥,使用HMAC-SHA-1是散列算法(RFC 2104)来生成HOTP值。

HMAC-SHA-1的输出是160个字节的,所以最终用户使用的值是在此基于上基于一定规则进行截断处理之后的值。

具体的截断处理分为三步:

  1. 生成散列值:HS = HMAC-SHA-1(K,C),这里的HS为散列算法计算出来的原始值,是一个20-byte的字符串;
  2. 动态截取(DT)生成一个4-byte的字符串;
  3. 计算HOTP值并返回:将第二步的字符串转换为十进制的整数,然后对10^Digit取模,返回结果;

动态截取(DT)的算法如下:

    DT(String) // String = String[0]...String[19]
     Let OffsetBits be the low-order 4 bits of String[19]
     Offset = StToNum(OffsetBits) // 0 <= OffSet <= 15
     Let P = String[OffSet]...String[OffSet+3]
     Return the Last 31 bits of P

实际上就是首先取HS的最后一个字节的低四位,然后将它转成十进制数字,并以它作为偏移值(offset值的大小为0 <= offset <= 15),以得到的offset为起始下标,从HS中取四个字节(从HS[offset]HS[offset+3],定义为P),然后返回P的最后31个字节。

取模操作时的Digit至少要是6位的长度,长度大于等于7位时要考虑生成更长的HOTP值。

对于Digit = 6时计算HOTP的示例:

这里的hmac_resultHMAC-SHA-1的结果。

        int offset   =  hmac_result[19] & 0xf ;
        int bin_code = (hmac_result[offset]  & 0x7f) << 24
           | (hmac_result[offset+1] & 0xff) << 16
           | (hmac_result[offset+2] & 0xff) <<  8
           | (hmac_result[offset+3] & 0xff) ;

这里是示例的散列值:

   -------------------------------------------------------------
   | Byte Number                                               |
   -------------------------------------------------------------
   |00|01|02|03|04|05|06|07|08|09|10|11|12|13|14|15|16|17|18|19|
   -------------------------------------------------------------
   | Byte Value                                                |
   -------------------------------------------------------------
   |1f|86|98|69|0e|02|ca|16|61|85|50|ef|7f|19|da|8e|94|5b|55|5a|
   -------------------------------***********----------------++|
  • 最后的字节(即第19字节)的值为0x5a
  • 该值的低四位的值为0xa(也就是偏移量的值offset
  • 偏移量的十进制值为100xa
  • 以偏移量为起始下标取四个节点,即0x50ef7f19,该值作为DBC1
  • The MSB of DBC1 is 0x50 so DBC2 = DBC1 = 0x50ef7f19(这句没读懂:(
  • HOTP = DBC2 mod 10^6 = 872921

上面的DBC是取的31位、无符合、大端序整数,它的首字节用0x7f屏蔽掉了,最后得到的HOTP值为:872921

HOTP的算法流程图如下:

TOTP引入了一个时间步长(time step)的概念,它是基于一个时间戳减去一个起始计数值,然后除以步长得到的值来作为HOTP中的计数器C,并且,TOTP的实现可以使用HMAC-SHA-256HMAC-SHA-512散列算法来代替HOTP中的HMAC-SHA-1算法。

TOTP的计算公式如下:

$$TOTP = HOTP(K, T)$$

这里用T作为HOTP的计数器,T的计算公式为:T = (Current Unix time - T0) / X,这里的T0为起始计数值,默认为0,这里的X为时间步长,默认为30,也就是说每个生成的密码的默认有效时间为30秒。

TOTP的算法流程图如下:

动手实现TOTP

不多说,直接PO代码。

首先是Golang的实现:

package gtotp

import (
	"crypto/hmac"
	"crypto/sha512"
	"fmt"
	"hash"
	"math"
	"time"
)

type Totp struct {
	secret string           // the K, also the shared secret
	cfg    TotpAlgorithmCfg // totp algorithm config parameters
	hasher *Hasher          // Hmac hash function
}

type TotpAlgorithmCfg struct {
	rtnDigitSize int // the return digit value length
	t0           int // the T0, default is 0
	timeStep     int // the X, default is 30
}

type Hasher struct {
	HashName string           // hash digit name
	Digest   func() hash.Hash // hash function, default is sha512
}

// NewDefaultTotp return Totp reference using default config parameters.
func NewDefaultTotp(sharedSecret string) *Totp {
	return &Totp{
		secret: sharedSecret,
		cfg: TotpAlgorithmCfg{
			rtnDigitSize: 10,
			t0:           0,
			timeStep:     30,
		},
		hasher: &Hasher{
			HashName: "sha512",
			Digest:   sha512.New,
		},
	}
}

// Now return the digit value by current timestamp.
func (t *Totp) Now() string {
	return t.At(int(time.Now().Unix()))
}

// At return the gigit value with the timestamp parameter.
func (t *Totp) At(timestamp int) string {
	currentSteps := t.steps(timestamp)
	byteSecret := []byte(t.secret)
	secretHash := hmac.New(t.hasher.Digest, byteSecret)
	bSteps := Itob(currentSteps)
	secretHash.Write(bSteps)
	hmacHash := secretHash.Sum(nil)

	offset := int(hmacHash[len(hmacHash)-1] & 0xf)

	code := ((int(hmacHash[offset]) & 0x7f) << 24) |
		((int(hmacHash[offset+1] & 0xff)) << 16) |
		((int(hmacHash[offset+2] & 0xff)) << 8) |
		(int(hmacHash[offset+3]) & 0xff)

	code = code % int(math.Pow10(t.cfg.rtnDigitSize))
	return fmt.Sprintf(fmt.Sprintf("%%0%dd", t.cfg.rtnDigitSize), code)
}

// calculate the steps of timestamp.
func (t *Totp) steps(timestamp int) int {
	return int((timestamp - t.cfg.t0) / t.cfg.timeStep)
}

// integer to byte array
func Itob(integer int) []byte {
	byteArr := make([]byte, 8)
	for i := 7; i >= 0; i-- {
		byteArr[i] = byte(integer & 0xff)
		integer = integer >> 8
	}
	return byteArr
}

测试用例:

package gtotp

import (
	"github.com/magiconair/properties/assert"
	"testing"
)

func TestTotp_At(t *testing.T) {
	totp := NewDefaultTotp("ninja@example.comHENNGECHALLENGE003")
	timestamp := 1594352095
	digitVal := totp.At(timestamp)
	assert.Equal(t, "0517636551", digitVal)
}

下面是基于Java的实现:

import javax.crypto.Mac;
import javax.crypto.spec.SecretKeySpec;
import java.lang.reflect.UndeclaredThrowableException;
import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.security.GeneralSecurityException;

/**
 * @author zhaoyang on 2020-07-10.
 */
public class Totp {

    private static final long[] DIGITS_POWER = {
        1L,10L,100L,1000L,10000L,100000L,1000000L,10000000L,100000000L,1000000000L,10000000000L
    };

    private long timeStep = 30L;
    private long t0 = 0L;
    private long rtnDigitSize = 10L;
    private String hmacShaName = "HmacSHA512";

    public Totp() {
        this(30L, 0L, 10L, "HmacSHA512");
    }

    public Totp(long timeStep, long t0, long rtnDigitSize, String hmacShaName) {
        this.timeStep = timeStep;
        this.t0 = t0;
        this.rtnDigitSize = rtnDigitSize;
        this.hmacShaName = hmacShaName;
    }

    public String genTotp(String secret, long time){
        StringBuilder result = null;

        long steps = (time - this.t0) / this.timeStep;

        byte[] secretBytes = secret.getBytes(StandardCharsets.UTF_8);
        byte[] hash = getHmacSha(this.hmacShaName, secretBytes, longToBytes(steps));

        // put selected bytes into result int
        int offset = hash[hash.length - 1] & 0xf;

        long code =
            ((hash[offset] & 0x7f) << 24) |
                ((hash[offset + 1] & 0xff) << 16) |
                ((hash[offset + 2] & 0xff) << 8) |
                (hash[offset + 3] & 0xff);

        code = (code % DIGITS_POWER[(int) this.rtnDigitSize]);

        result = new StringBuilder(Long.toString(code));

        while (result.length() < this.rtnDigitSize) {
            result.insert(0, "0");
        }
        return result.toString();
    }

    public static byte[] longToBytes(long x) {
        ByteBuffer buffer = ByteBuffer.allocate(Long.BYTES);
        buffer.putLong(x);
        return buffer.array();
    }

    private static byte[] getHmacSha(String crypto, byte[] secretBytes, byte[] msgBytes){
        try {
            Mac hmac = Mac.getInstance(crypto);
            SecretKeySpec macKey =
                new SecretKeySpec(secretBytes, "RAW");
            hmac.init(macKey);
            return hmac.doFinal(msgBytes);
        } catch (GeneralSecurityException gse) {
            throw new UndeclaredThrowableException(gse);
        }
    }

    public static void main(String[] args) {
        Totp totp = new Totp();
        System.out.println(totp.genTotp("ninja@example.comHENNGECHALLENGE003", 1594352095));
    }
}

两种实现计算的结果是相同的。

总结

其实认真的把RFC的算法过程看过一遍,看懂之后,这个算法的实现还是蛮简单的,一些比较难搞的位运算的代码都已经直接在协议中给出来了,只要注意一下大于8位的长度时Java中需要修改为long类型来处理就行了。

这个过程中间,在使用Golang实现时,发现了一些没留意的有趣的事情,Golangtime.Unix()方法返回的毫秒值永远是UTC时区的,不管你在输出之前设置的是什么时区,想想,这样其实也蛮好的,至少轻松的把大家的标准给统一了,再也不怕时区不对导致毫秒值的时间问题了。

另外,一定要抽时间看一下Golang中时间的模版设计的源码,据说设计很巧妙。

声明:上面的两张图片引用自HOTP和TOTP算法图解,链接在末尾。

References:
  1. Time based one time password algorithm
  2. RFC 6238
  3. RFC 4226
  4. HOTP和TOTP算法图解
  5. gotopt github repo