昨天碰到一个有意思的事情,做了一道题,然后提交的时候需要根据定义好的共享密钥的规则来生成一个TOTP
动态密码,服务端会对不同的人提交的时候生成的动态密码做校验,于是就学习了一下TOTP
算法,并基于Golang
和Java
作出了相应的实现。
生成的这个TOTP
动态密码要求是10
位的长度,如果只是直接网上搬别人写的代码基本无用,所以就有了这一篇。
HOTP
与TOTP
算法
TOTP
是一种基于时间的一次性密码算法,它根据预共享的密钥和当前时间计算一次性密码。该算法已经被互联网任务工作组接纳为RFC 6238
标准,成为主动开放认证(OAUTH
)的基础。
TOTP
基于HOTP
(RFC 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
个字节的,所以最终用户使用的值是在此基于上基于一定规则进行截断处理之后的值。
具体的截断处理分为三步:
- 生成散列值:
HS = HMAC-SHA-1(K,C)
,这里的HS
为散列算法计算出来的原始值,是一个20-byte
的字符串; - 动态截取(
DT
)生成一个4-byte
的字符串; - 计算
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_result
是HMAC-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
) - 偏移量的十进制值为
10
(0xa
) - 以偏移量为起始下标取四个节点,即
0x50ef7f19
,该值作为DBC1
- The
MSB
ofDBC1
is0x50
soDBC2 = DBC1 = 0x50ef7f19
(这句没读懂:(
) HOTP = DBC2 mod 10^6 = 872921
上面的DBC
是取的31
位、无符合、大端序整数,它的首字节用0x7f
屏蔽掉了,最后得到的HOTP
值为:872921
。
HOTP
的算法流程图如下:
TOTP
引入了一个时间步长(time step
)的概念,它是基于一个时间戳减去一个起始计数值,然后除以步长得到的值来作为HOTP
中的计数器C
,并且,TOTP
的实现可以使用HMAC-SHA-256
或HMAC-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
实现时,发现了一些没留意的有趣的事情,Golang
中time.Unix()
方法返回的毫秒值永远是UTC
时区的,不管你在输出之前设置的是什么时区,想想,这样其实也蛮好的,至少轻松的把大家的标准给统一了,再也不怕时区不对导致毫秒值的时间问题了。
另外,一定要抽时间看一下Golang
中时间的模版设计的源码,据说设计很巧妙。
声明:上面的两张图片引用自HOTP和TOTP算法图解
,链接在末尾。