多读书多实践,勤思考善领悟

FLEXLM ECC 椭圆曲线加密分析

本文于392天之前发表,文中内容可能已经过时。

1. FLEXLM简介

FLEXlm是应用广泛的License管理工具。DS、ANSYS、MathWorks、80%以上的 EDA软件公司等等采用它管理授权,是目前最流行的加密方法,保护着世界上价值上兆亿美元的软件,不过在破解者面前,它其实非常脆弱。
FLEXlm对厂商来说,它的优点是证书管理功能强大, 支持平台众多。
对最终用户来说,它的缺点是不够友好, 比如Windows下,经常由于某些原因,flexlm服务启动错误。维基百科上的条目为:http://en.wikipedia.org/wiki/FLEXlm

FLEXLM本来属于GLOBEtrotter。Macrovision曾经收购GLOBEtrotter。
2006年的时候,FLEXLM原来的开发组跑路,另起灶头,产品叫RLM。
http://www.reprisesoftware.com/index.php

2008年Macrovision把FLEXLM卖了。现在叫FlexNet Publisher。
http://www.flexerasoftware.com/products/flexnet-publisher.htm

2. FLexLM 的ECC(椭圆曲线加密)来由

早期的flexlm采用的常规加密,不安全,能被做出lic。这样的教程是很多的。
flexlm的安全性完全得不到保障,所以,自 v8(大约2001-2002)版本引入了公钥加密算法:椭圆曲线加密。
从此,它一直是flexlm的金钟罩。包括v9(2003-) , v10(2004-) , v11(2007-), 到最新的版本 v11.17 (2021) 。

FlexLm的ECC没有它自己的东西,完全采购自椭圆曲线加密系统的专利拥有者:Certicom公司。
换而言之, flexlm ecc是购买自certicom的一套代码,相当于在腐朽的木门上套一层黄金甲。
OK, 从此它是不破金身了。

3. Certicom公司简介

RSA和ECC是两大主流的公钥密码算法体系。相比RSA,ECC晚出生10多年,推广不如前者。
Certicom公司是ECC的主要商业支持者,它拥有多项专利。其地位可与RSA公司匹敌(RSA于2006年被EMC公司收购)。
有一则消息说,2003年美国国家安全局(NSA)以2500万美元支付了Certicom的26项技术许可。
另外有一则消息, Certicom 2007年起诉索尼公司,要求其支付PS3,DVD播放器等涉及加密技术侵权的专利费用。

Certicom的创办人Scott Vanstone,是加拿大滑铁卢大学的数学系教授和皇家科学院院士。
以前是研究椭圆曲线加密的,后来创办Certicom公司,努力把ECC从数学界推广到工业界。
Scott写过一本《椭圆曲线密码学导论》, 颇有名气。

4. FLEXLM 如何使用ECC

说来话长。一句话说:FLexLM 在license验证上,主要用的ECDSA(椭圆曲线数字签名算法)。

具体的讲: flexlm针对ECDSA有一些自己定义的东西以抵抗破解。 后面会说到,这些自定义的
东西也不是那么牢固。

5. FLEXLM ECC的通用破解方法

FLEXLM ECC的通用破解方法就是:
完全按照它的ECDSA算法签名, 只替换公钥和checksum, 写一个keygen生成license。
从逻辑上讲,生成license的方法和原厂的完全一致。

具体该怎么做呢:

首先, 实现标准的ECDSA签名算法。椭圆曲线的具体算法,可以用现成的miracl,cryptopp等加密库代码。 只需要搞清楚ECDSA的使用方法就可以。

从早期版本 v9.2 (2004) , 到最新版本v11.17 (2021) 。它的ecc公钥都是有checksum的。
替换公钥,首先得搞清楚checksum。它只有一个函数,不算复杂,后面会给出代码。
计算这个checksum, 对所有版本都是适合的。

其次, 公钥在文件里是加密打散的,有大量垃圾代码。这些干扰使得flexlm可读性很差。获取公钥需要调试。

那么,有没有更方便的方法获取公钥呢?

ECC验证代码在它执行过程中有其自身的特点。正如游戏辅助工具可以搜索血量,我们也可以写一个辅助工具从内存中获取公钥。

在很多次研究之后,找出一个通用的方法。不需要再拘泥于具体的代码,可以dump出公钥 ,然后用ecctool生成自己的公私钥对,替换公钥,然后可以就写keygen。

由此写了一个工具,对windows平台可直接操作。 对其它平台,把内存镜像出来操作即可。
对于非Windows平台,可以在VMware里面操作,制作一份snapshot,得到内存镜像。
算法上经过多次优化和排除错误数据,从2GB的内存镜像里找出正确的公钥,平均只需要6秒钟。

所以,对于纯粹采用flexlm ecc sign的license,是可以做出通用的patch_keygen的,
不需要去考虑它有没有反调试,也不用管具体的细节。

只要dump 公钥, 替换公钥和checksum, 写patch_keygen就可以了。

6. 研究flexlm主要资料

flexlm相对来说资源丰富,基本上每个版本的sdk都有泄漏。
如果想深入研究flexlm的加密算法,flexlm sdk是必需的。

写kg是必须要读sdk的,值得注意的是v9.2 sdk sourcecode泄漏。这个网上可搜索到。
sdk有一部分是c代码,里面最有用的是l_prikey.c, 这里有ECDSA验证的函数。
这个文件的尾部有300行comments,其中有一封email很值得一读。

ECC核心库没有源文件,只有lib文件。
在certicom目录下的lib里面,主要为libsb.lib等(Certicom 的加密库:Security Builder)。
lib是混淆过了的,但是不影响ida反编译,只是不便于做sig文件。
主要依靠人脑识别函数,需要经验和时间。

7. flexlm的key加密强度种类

以flexlm sdk v9为例,用宏定义表示LM_SIGN_LEVEL。
#define LM_SIGN2 2 / SIGN2= /
#define LM_SIGN 1 / SIGN= the default /
#define LM_NO_SIGN 0 / license key /

v9以后,默认就采用ECC PUBKEY加密。SIGN支持ECC,所以大部分情况下用SIGN比较多,有些用SIGN2。
LM_NO_SIGN 是传统的license key, 强度最弱,不建议使用。
ECC PUBKEY 只有3种类别, 113, 163, 239 bits。
对应的sign长度(字符数) , 字节为( bits + 7 )/8 字节数 , 打印出来,
用hex digits表示,ECC的SIGN长度分别是一对 30,42,60 [0-9,A-F]。

采用ECC的,pubkey_strength 必须定义为下面的一个类别,否则l_pubkey_verify会出错:
LM_STRENGTH_113BIT,LM_STRENGTH_163BIT,LM_STRENGTH_239BIT。

#define LM_STRENGTH_LICENSE_KEY 0
#define LM_STRENGTH_DEFAULT 1
#define LM_STRENGTH_113BIT 2
#define LM_STRENGTH_163BIT 3
#define LM_STRENGTH_239BIT 4
#define LM_STRENGTH_PUBKEY LM_STRENGTH_113BIT
#define LM_STRENGTH_VERYHIGH LM_STRENGTH_239BIT

在l_pubkey_verify 有这么一段初始化代码, 判断pubkey_strength。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
switch(pubkey_strength)
{
case LM_STRENGTH_LICENSE_KEY:
return 0;
case LM_STRENGTH_113BIT: ellipticCurve = &LM_PUBKEY_CURVE113BIT;
break;
case LM_STRENGTH_163BIT: ellipticCurve = &LM_PUBKEY_CURVE163BIT;
break;
case LM_STRENGTH_239BIT: ellipticCurve = &LM_PUBKEY_CURVE239BIT;
break;
default:
{
fprintf(stderr,
"LM_STRENGTH in lm_code.h has invalid value %d\n",
pubkey_strength);
fprintf(stderr,
"Use only LM_STRENGTH_[113|163|239]BIT, LM_STRENGTH_DEFAULT, OR LM_STRENGTH_LICENSE_KEY, exiting\n");
exit(1);

}
}

下面,演示 113, 163, 239 bits的ECDSA签名一段最简单的文本,
msg: “123”
sha hash:40BD001563085FC35165329EA1FF5C5ECBDBBEEF

#define LM_SEED1 0x47d381a0
#define LM_SEED2 0x4fadf97c
#define LM_SEED3 0xc4ae244c
l_genkeys: seed[3]=A081D3477CF9AD4F4C24AEC4

LM_PUBKEY_CURVE113BIT
prvlen=15, prv=00CFDF0247BF6EC0C8D1AA16DD505F
publen=16, pub=0301523DD4646BB65FE4238B8AB44D01
>> l_prikey_sign_dbg start >>
signing “123”
hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEF
>> l_prikey_sign_dbg done >>
siglen=30
sig.r=0048D5DD2A57B1A1B357E98C193E63
sig.s=000A6FFDF76899F05ABFD2EDD9E065

LM_PUBKEY_CURVE163BIT
prvlen=21, prv=03DC603CB1683D43FF5631BBEEC5396D7BD4067300
publen=22, pub=0300368FE93082E1ACDD35222AD76782DBA8237B66EC
>> l_prikey_sign_dbg start >>
signing “123”
hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEF
>> l_prikey_sign_dbg done >>
siglen=42
sig.r=039283F2FEA664BE7628F89BBA9D014E89E3868D2C
sig.s=017DA34A68C3FC64CB6EBE2B13676B04BE97EB5C20

LM_PUBKEY_CURVE239BIT
prvlen=30, prv=13C0E251A5130072A8D2D953EB2C94FAD487C0141B3197863BCC115D7B7E
publen=31, pub=035875A53B693A2861837E08FC6A7C58529DF52B565111C3DF55F18E34C9FA
>> l_prikey_sign_dbg start >>
signing “123”
hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEF
>> l_prikey_sign_dbg done >>
inputlen=3, input=123
siglen=60
sig.r=1589FCFE91F988D28F7072DBF129424F0D71FA5E7AAC39258F3C408A656A
sig.s=0B50642E8ED77FC6A1E6F805CFA0299F44BC7B8035FE17142812B79EA576

sig.r sig.s组成一个完整的SIGN, 输出lic的时候,为了可读性, 一般切分为16 bit的分组(4个hex char)。
比如:
sig.r=038B9BE995B887B2665C02940C00155DD557C278AC95EADC1BD668DF185B
sig.s=1C50F25E81044E4DD9AD072699AAB4A63F4C99249AC8C091F476A6C73682
转化为:
SIGN=“ 038B9BE995B887B2665C02940C00155DD557C278AC95EADC1BD668DF185B
1C50F25E81044E4DD9AD072699AAB4A63F4C99249AC8C091F476A6C73682”
或者:
SIGN=”038B 9BE9 95B8 87B2 665C 0294 0C00 155D D557 C278 AC95 EADC 1BD6 68DF 185B 1C50 F25E 8104 4E4D D9AD 0726 99AA B4A6 3F4C 9924 9AC8 C091 F476 A6C7 3682”

对flexlm的程序来说,是没有差别的。 都能处理。

8. flexlm所用到的椭圆曲线

flexlm用到三条椭圆曲线,都是有来历的, 名字分别为sect113r1, sect163k1, sect239k1。
具体参数可以参看:http://en.wikipedia.org/wiki/SECG
SEC 2: Recommended Elliptic Curve Domain Parameters (Version 2.0)

在flexlm lib里面, 它是写死的静态变量。位置在
certicom\libcrvs.lib

保存为3个结构体:
struct ellipticCurveParameters sect113r1
struct ellipticCurveParameters ec163a02
struct ellipticCurveParameters ec239a03

头文件在
erticom\i86_n3\include\curves.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/*=== Curves Definitions ==================
*
* sect113r1 (K-163 NIST), ec163a02 (SEC2, sect163k1) , ec239a03 (sec2, sect239k1)
*/
#define LM_PUBKEY_CURVE113BIT sect113r1
#define LM_PUBKEY_CURVE163BIT ec163a02
#define LM_PUBKEY_CURVE239BIT ec239a03

#define MAXIM_OID_CHARS 31
struct ellipticCurveParameters {
#pragma pack(4)
unsigned char oid[ MAXIM_OID_CHARS + 1 ];
struct {
unsigned char major[ 1 ];
unsigned char minor[ 1 ];
} version;
unsigned char checksum[ 4 ];
unsigned char fieldSize[ 2 ]; /* bits */
unsigned char fieldSizeOctets[ 1 ]; /* octets */
unsigned char basisType[ 1 ];
unsigned char modulus[ 32 ];
const unsigned char *ident1;
const unsigned char *ident2;
struct {
unsigned char a[ 32 ];
unsigned char b[ 32 ];
} curveParameter;
struct {
unsigned char value[ 64 ];
} generatingPoint;
struct {
unsigned char size[ 2 ]; /* bits */
unsigned char value[ 32 ];
} pointOrder;
struct {
unsigned char size[ 2 ]; /* bits */
unsigned char value[ 32 ];
} cofactor;
struct {
unsigned char size[ 2 ]; /* bits */
unsigned char value[ 32 ];
} curveOrder;
#pragma pack(2)
struct {
unsigned char A[ 32 ];
unsigned char B[ 32 ];
} reserved;
} ;

9. flexlm ecc ellipticCurveParameters 结构体中 checksum的计算方法

ellipticCurveParameters 带有4字节checksum,
每次初始化ECC计算时,都会校验checksum。一方面为了避错, 另一方面为了反对篡改。
修改其中的公钥,必须重新计算checksum。

从libsb.lib里面分析反汇编代码, 逆向为c代码,经测试无误的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
int checksum(unsigned int len, void *src , int *val)
{
unsigned int i;
unsigned int h;
unsigned int c;
unsigned char *p = (unsigned char *)src;

if((p == 0) || (val == 0) || (len == 0))
return 1;

i = 0;
c = *val;
while(i < len)
{
c = p[i] + c * 16;
h = c & 0xF0000000;
if ( h != 0)
c ^= (h >> 24);
c &= ~h;
i++;
}

*val = c;
return 0;
}

unsigned int getbits(unsigned char *p, unsigned int len)
{
unsigned int val;

val = 0;
while(len --) {
val <<= 8;
val += *p++;
}

return val ;
}

unsigned int getbytes(unsigned char *p, unsigned int len)
{
unsigned int bits = getbits(p , len);

return ((bits + 7) >> 3);
}



int do_ecp_checksum(struct ellipticCurveParameters *e, int *sum1, int *sum2)
{
unsigned int val = getbytes(e->fieldSize, 2);
unsigned int bytes = val;
unsigned char *p = (unsigned char *)e;

#if 1
checksum(sizeof(e->oid), &e->oid, sum2);
checksum(sizeof(e->version.major), &e->version.major, sum2);
checksum(sizeof(e->version.minor), &e->version.minor, sum2);
checksum(sizeof(e->fieldSize), &e->fieldSize, sum2);
checksum(sizeof(e->fieldSizeOctets), &e->fieldSizeOctets, sum2);
checksum(sizeof(e->basisType), &e->basisType, sum2);
#endif

checksum(32u, p, sum1);
checksum(1u, p + 32, sum1);
checksum(1u, p + 33, sum1);
checksum(2u, p + 38, sum1);
checksum(1u, p + 40, sum1);
checksum(1u, p + 41, sum1);

#if 1
checksum(bytes, &e->modulus, sum2);
checksum(bytes, &e->curveParameter.a, sum2);
checksum(bytes, &e->curveParameter.b, sum2);
checksum(2 * bytes, &e->generatingPoint.value, sum2);
#endif

checksum(val, p + 42, sum1);
checksum(val, p + 84, sum1);
checksum(val, p + 116, sum1);
checksum(2 * val, p + 148, sum1);

#if 1
checksum(2, &e->pointOrder.size, sum2);
checksum(getbytes(e->pointOrder.size, 2), &e->pointOrder.value, sum2);

checksum(2, &e->cofactor.size, sum2);
checksum(getbytes(e->cofactor.size, 2), &e->cofactor.value, sum2);

checksum(2, &e->curveOrder.size, sum2);
checksum(getbytes(e->curveOrder.size, 2), &e->curveOrder.value, sum2);

checksum(bytes, &e->reserved.A, sum2);
checksum(bytes, &e->reserved.B, sum2);
#endif

checksum(2u, p + 212, sum1);
checksum(getbytes(e->pointOrder.size, 2), p + 214, sum1);

checksum(2u, p + 246, sum1);
checksum(getbytes(e->cofactor.size, 2), p + 248, sum1);

checksum(2u, p + 280, sum1);
checksum(getbytes(e->curveOrder.size, 2), p + 282, sum1);

checksum(val, p + 314, sum1);
checksum(val, p + 346, sum1);

return val;
}

10. flexlm ecc三条椭圆曲线的参数

flexlm 采用GF(2^m)椭圆曲线。这三条椭圆曲线, 在openssl也有描述的。
在certicom\libcrvs.lib是纯数据保存。

openssl描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
EcRecommendedParameters<EC2N>(ASN1::sect113r1(),
113, 9, 0,
A/a2 = "003088250CA6E7C7FE649CE85820F7",
B/a6 = "00E8BEE4D3E2260744188BE0E9C723",
"04009D73616F35F4AB1407D73562C10F00A52830277958EE84D1315ED31886",
"0100000000000000D9CCEC8A39E56F",
2),

EcRecommendedParameters<EC2N>(ASN1::sect239k1(),
239, 158, 0,
"000000000000000000000000000000000000000000000000000000000000",
"000000000000000000000000000000000000000000000000000000000001",
"04
29A0B6A887A983E9730988A68727A8B2D126C44CC2CC7B2A6555193035DC7
6310804F12E549BDB011C103089E73510ACB275FC312A5DC6B76553F0CA",
"2000000000000000000000000000005A79FEC67CB6E91F1C1DA800E478A5",
4),

EcRecommendedParameters<EC2N>(ASN1::sect163k1(),
163, 7, 6, 3, 0,
"000000000000000000000000000000000000000001",
"000000000000000000000000000000000000000001",
"0402FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE80289070FB05D38FF58321F2E800536D538CCDAA3D9",
"04000000000000000000020108A2E0CC0D99F8A5EF",
2),

flexlm sdk
\certicom\libcrvs.lib 内存dump, checksum只需要签名378 bytes的结构体。

为了调试和区分的方便, 在尾部增加了标志:
‘E’ ‘C’ ‘1’ ‘1’ , ‘E’ ‘C’ ‘1’ ‘6’ , ‘E’ ‘C’ ‘2 ‘3’ , 分别表示ecc 113, 163, 239 bits。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
unsigned char ec113[384] = {
0x06, 0x05, 0x2B, 0x81, 0x04, 0x00, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x02, 0x00, 0x04, 0x43, 0x8E, 0x10, 0x00, 0x71, 0x0F, 0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xE0, 0xCB, 0x46, 0x00,
0xF0, 0xCA, 0x46, 0x00, 0x00, 0x30, 0x88, 0x25, 0x0C, 0xA6, 0xE7, 0xC7, 0xFE, 0x64, 0x9C, 0xE8,
0x58, 0x20, 0xF7, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0xE8, 0xBE, 0xE4, 0xD3, 0xE2, 0x26, 0x07, 0x44, 0x18, 0x8B, 0xE0,
0xE9, 0xC7, 0x23, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x9D, 0x73, 0x61, 0x6F, 0x35, 0xF4, 0xAB, 0x14, 0x07, 0xD7, 0x35,
0x62, 0xC1, 0x0F, 0x00, 0xA5, 0x28, 0x30, 0x27, 0x79, 0x58, 0xEE, 0x84, 0xD1, 0x31, 0x5E, 0xD3,
0x18, 0x86, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x71, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xD9, 0xCC,
0xEC, 0x8A, 0x39, 0xE5, 0x6F, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x72, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x01, 0xB3, 0x99, 0xD9, 0x14, 0x73, 0xCA, 0xDE, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 'E', 'C', '1', '1'
};


unsigned char ec163[384] = {
0x06, 0x05, 0x2B, 0x81, 0x04, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x02, 0x00, 0x07, 0x48, 0x77, 0x70, 0x00, 0xA3, 0x15, 0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xC9, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xB0, 0xD4, 0x4D, 0x00,
0x00, 0xD3, 0x4D, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x02, 0xFE, 0x13, 0xC0, 0x53, 0x7B, 0xBC, 0x11, 0xAC, 0xAA, 0x07, 0xD7,
0x93, 0xDE, 0x4E, 0x6D, 0x5E, 0x5C, 0x94, 0xEE, 0xE8, 0x02, 0x89, 0x07, 0x0F, 0xB0, 0x5D, 0x38,
0xFF, 0x58, 0x32, 0x1F, 0x2E, 0x80, 0x05, 0x36, 0xD5, 0x38, 0xCC, 0xDA, 0xA3, 0xD9, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0xA3, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x02, 0x01, 0x08, 0xA2, 0xE0, 0xCC, 0x0D, 0x99, 0xF8, 0xA5, 0xEF, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xA4, 0x08, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x04, 0x02, 0x11, 0x45, 0xC1, 0x98, 0x1B, 0x33, 0xF1, 0x4B, 0xDE, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,'E', 'C', '1', '6'
};


unsigned char ec239[384] = {
0x06, 0x05, 0x2B, 0x81, 0x04, 0x00, 0x03, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x02, 0x00, 0x0A, 0xD7, 0xBD, 0x00, 0x00, 0xEF, 0x1E, 0x05, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0xE0, 0xCA, 0x46, 0x00,
0x30, 0xC9, 0x46, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x01, 0x00, 0x00, 0x29, 0xA0, 0xB6, 0xA8, 0x87, 0xA9, 0x83, 0xE9, 0x73, 0x09, 0x88, 0xA6,
0x87, 0x27, 0xA8, 0xB2, 0xD1, 0x26, 0xC4, 0x4C, 0xC2, 0xCC, 0x7B, 0x2A, 0x65, 0x55, 0x19, 0x30,
0x35, 0xDC, 0x76, 0x31, 0x08, 0x04, 0xF1, 0x2E, 0x54, 0x9B, 0xDB, 0x01, 0x1C, 0x10, 0x30, 0x89,
0xE7, 0x35, 0x10, 0xAC, 0xB2, 0x75, 0xFC, 0x31, 0x2A, 0x5D, 0xC6, 0xB7, 0x65, 0x53, 0xF0, 0xCA,
0x00, 0x00, 0x00, 0x00, 0x00, 0xEE, 0x20, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x5A, 0x79, 0xFE, 0xC6, 0x7C, 0xB6, 0xE9, 0x1F, 0x1C, 0x1D, 0xA8,
0x00, 0xE4, 0x78, 0xA5, 0x00, 0x00, 0x00, 0x03, 0x04, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xF0, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x69, 0xE7, 0xFB, 0x19, 0xF2, 0xDB, 0xA4,
0x7C, 0x70, 0x76, 0xA0, 0x03, 0x91, 0xE2, 0x94, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 'E', 'C', '2', '3'
};

11. ECDSA的一些参考读物

讲述ECDSA的一般原理, 与flexlm没有任何关系。但是flexlm ecc算法上属于ECDSA。理解了ECDSA就理解了flexlm ecc的基本原理。

前面说到,flexlm ecc的签名算法是ECDSA(The Elliptic Curve Digital Signature Algorithm). ECDSA 已经成为世界标准。ECDSA was accepted in 1999 as an ANSI standard, and was accepted in 2000 as IEEE and NIST standards. It was also accepted in 1998 as an ISO standard.

ECDSA是一个比较复杂的数字签名算法。其详细内容不是三言两语能说完的。

详细内容可以参考:
《SEC 1: Elliptic Curve Cryptography》,Certicom Corp.,2000
《IEEE P1363a 》,2001

ECDSA并不是一个从无到有的构思。它的思想来自于DSA(Digital Signature Algorithm),是把DSA推广到椭圆曲线上。
从这个角度讲,叫它DSAEC(Digital Signature Algorithm over Elliptic Curve )未尝不可。

DSA的主要思想来自于离散对数问题(DLP, Discrete Logarithm Problem)。 把DLP推广到椭圆曲线上,就成为ECDLP。
离散对数问题与因子分解(Integer Factorization Problem)问题是公钥密码学中两个典型的难题。

因子分解问题产出了RSA,Rabin等公钥加密、签名算法;离散对数问题产生了DSS/DSA,ElGamal等公钥加密、签名算法。

在椭圆曲线上,离散对数模型大放光彩,产生了ECDSA,ECNR,ECElGamal等一大批算法。

椭圆曲线比常见的数学问题要复杂,因为它需要一些初等数论的知识作为铺垫。大学低年级的普通数学基础是必须的。如果忘光了,还得重新翻翻教材。有些人可能学习几个月就能够理解椭圆曲线,那已经是相当不错的了。

在理解ECDSA之前,需要理解离散对数和椭圆曲线这两个东西。这里面内容太多了,有许多未知的东西。

11.1
离散对数本身的内容很多,常见的密码学教材中都有介绍。

11.2
椭圆曲线也是一个复杂的数学对象。它不是椭圆,它是由Weierstrass方程来描述的一类曲线,
具体是否牵涉到椭圆周长积分,椭圆周长积分不是初等函数,是无穷级数。

密码学里的椭圆曲线,跟几何上的椭圆和曲线完全不相同。
这里的椭圆曲线更特殊一些,它是一个有限域,每一个点 G(x,y)都是一个整数点。
一条椭圆曲线上的点数是确定的。

12. 一条椭圆曲线上做ECDSA的例子

12.1 描述一条Fp上的椭圆曲线的六个参量

密码学中,描述一条Fp上的椭圆曲线,常用到六个参量:
(p,a,b,G,n,h)。

p, a,b 用来确定一条椭圆曲线的方程,
G为基点,口头上也叫G点,或者 (Base point),
n为点G的阶(Order),也可以叫模或者周期,
h = E/n, 叫co-factor。 其中E是椭圆曲线上所有点的个数.

我们用乘法来表示椭圆曲线上点的倍加,那么,能找到一个n,
对于任何一个点G(x,y), n * G = 0 因此, 它具有循环的性质。
这个循环周期就是n。

对于密码学的应用上,为了抵御Pohlig-Hellman攻击(利用中国剩余定理),
采用的椭圆曲线有严格的限制。它要求E具有一个大素数因子,或者E本身就是素数。

有一个算法Schoof-Elkies-Atkin 用来计算椭圆曲线的点数E(Fp)。
需要用到中国剩余定理,具体的算法比较复杂。

n = E/h , h称之为co-factor.
常见的h=1 或者h=2.

E为什么不是一个参量? 因为E可以由P,A,B计算出来的。计算完毕以后,E就没用了。
有用的是n, 而且E=h*n是一目了然的事。

附:一段题外话,关于中国剩余定理

Pohlig-Hellman算法和Schoof-Elkies-Atkin算法都要用到初等到数论里一个重要的定理,
也就是一次同余方程组的解法定理。称为中国剩余定理(CRT, Chinese Remainder Thereom)。
或称孙子定理,在数学史上,这个发现归根于中国古代的数学家们。

在这个帝国,两千年来文科生治国,数学毫无地位,剩余定理的发现很了不起。
类似于勾股定理一样,中国古代数学家发现此定理,但并没有严格的证明剩余定理。

剩余定理最早见于《孙子算经》,成书于约公元300年-400年,作者生平都无法考证了。
南宋数学家秦九韶编写《算术九章》,总结出“大衍求一术”。
和秦九韶同时代的意大利数学家裴波那契(1170—1250),他在《算法之书》中给出了
两个一次同余问题,但是没有一般的算法。相当于《孙子算经》的水准。

德国大数学家高斯(1777—1855)于公元1801年给出了剩余定理的严格证明。

中国古代的数学书里,剩余定理只有最简单的应用,相当于小学数学奥赛里面的模同余问题。

剩余定理在数论里用的比较多,初等数论教科书基本上都会提到她。
很多密码学库都有一个单独的crt.cpp,crt.c。

12.2 以NIST-P192为例, 讲述ECDSA

我们以NIST-P192 , GF (p-192)这条椭圆曲线来说,这是NIST推荐的一条曲线。

这是最简单的一类椭圆曲线。称之为GF(p),P是一个素数。
GF(2^m)曲线更复杂,不再举例。

曲线方程:y^2 = x^3 + A*x + B (mod P)

这里:
A = -3
B = 64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
P = ( 2^192 - 2^64 - 1 )
= FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
P是一个素数。

对于NIST-P192,
E = FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
h = 1
n = FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
n是一个素数。

下面用公式简单描述一下ECDSA签名和验证的步骤:
大写字母代表椭圆曲线上的点 Point(x,y), 小写字母代表一个数。

注意:这里的乘法是椭圆曲线上点的倍加;除法是整数的模逆运算,可用欧几里得算法。
mod是整数求余。

(1) 签名, Sign:
G为基点。h为要签名的hash。私钥为d。 公钥R = d*G(签名时只用到私钥)。
取随机数k , k是一个密码学意义上的随机数,范围在(1, n)。

r = k * G mod n … (1)
s = (h + rd)/k mod n … (2)

(2) 验证, Verify:
G为基点, r, s为签名, h为要验证的hash。 公钥为R。(验证时只用到公钥)
u = h/s
w = r/s
v = u G + w R mod n
验证(v == r)。

证明,为什么签名可以被验证? 我们参照DSA的证明。可得:
v = u G + w R = (h/s) G + (r/s) ( d G)
= (h/s + rd/s)
G
= ((h + rd)/s) *G

从(2) 得出, ks = (h + rd) mod n => k = (h + rd)/s
从而 v = k
G, 所以签名和验证能一一对应上。

为什么说它安全:
由于 R = dG是一个椭圆曲线离散对数问题,无法直接求的私钥x;
由于 r = k
G也是一个椭圆曲线离散对数问题,所以随机数k是也没有办法恢复的。
也就是说,在未知x或者k, 无法给出以下方程的一个解(r, s):
h/s G + r/s R = r mod n
如果给出一个解,则表示, sign (r,s)可以被伪造。

这里面,对hash的强度也是有要求的。最基本的要求是sha 160 bit的hash。

严谨的证明, 见《IEEE P1363a 》等文档。

例子, NIST-P192 签名。
y^2 = x^3 - 3x + 64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1 mod FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
n=FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831
G(x,y):
Gx=188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
Gy=07192B95FFC8DA78631011ED6B24CDD573F977A11E794811


d=16fdbb3f3e4d7d253c421ae5a09f1ce500d973c04ae91564
那么公钥
R(x,y) = d * G(x,y)
Rx=2B443533CFBECB00ABE1F9D0F3A8FFD871EFDDAB4FF93B0C
Ry=6EFF3D69042B58F7C726BDB6B495AE75BD09D762259013DB

签名 “123”.
h = hash(sha-160)=40bd001563085fc35165329ea1ff5c5ecbdbbeef

k=CADDC27FEFC3040C1CCA194542218E002F58D504A639B668

Sign(用ECCTool计算):
sig.r=5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
sig.s=C0DFFC8E4BA4A91EBFFBCE7FE07E202AAF567DC10D69D5E8

Verify (用ECCTool 和 BigIntCal计算):
u = h/s mod n = BBBBED787373E2407BA720D7851CE0895222B5B5DF81BECB
w = r/s mod n = 2BBC84EA2E318FC5666B50CEE41845F3EB1DF40C838FA86C
V(x,y) = u G + w R mod n =
V.x = 5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
V.y = 70360EEEC1C42D5AC10226B8BE0EA507E3FF54290737B02C
So,
v = V mod n = 5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4

v==r 验证完毕。

打个最简单的比方,如果有一个软件,采用NIST-P192 ECDSA验证,其算法逻辑为:
sign = ecdsa(sha-160(name)), 并且它的公钥,私钥如上所描述:
那么:
name:
123
sn:
5C09A23549325C866F0C1D8D6AB81255977C90A9FD6D66C4
C0DFFC8E4BA4A91EBFFBCE7FE07E202AAF567DC10D69D5E8

就是一对可用的注册码。

mybase的算法是标准ECDSA( GF (2^233),跟这个很相似。只是曲线不同,私钥不同。
如果你理解了ECDSA,那么,写mybase的kg是很容易的事情了。

当然,它的私钥不是那么好计算的。 你可能需要几年的功底。

13. FlexLM ECDSA的公私钥对生成方法

FlexLM 生成公私钥对的方法是有固定标准的,它是一种IEEE-1363的弱化方法。
seed只有96 bits(3个32bit的digit)。
尽管如此,穷举96 bit在实际操作上不可行的,v9 - v11的版本是足够安全的。

下面对flexlm ECDSA密钥生成的分析,主要基于v9.x - v11.x 的SDK。核心代码在l_prikey.c。

(1) gen seed
(2) gen keys

(1)首先分析genseed:

lmrand1调用l_genseed产生三个强随机数,然后由它初始化rng,产生私钥。

对于Flexlm ECC来说,113, 163, 239只是椭圆曲线类型不一样,其他的算法完全一样。没有区别。

LM_SEED1,LM_SEED2,LM_SEED3除了出现在license gen中,不出现在任何地方。
从程序中无法恢复出LM_SEED1,LM_SEED2,LM_SEED3。

flexlm v8.0的版本,l_genseed()的随机性不够好,有bug,能够被恢复seed。
flexlm v9的版本已经修复。

它添加了一段hardware dependent的代码,给rng初始化的sha buffer添了大量数据。
意味着在不同的机器上,lmrand1产生的结果是不同的。

l_genseed() 函数增加了补丁, 代码如下。

找了一些资料,对比了v8.0c, v8.3b和v9.2的版本。
在 v8.0c时有此bug。 v8.3b时补丁已经打上了。查了histroy,是v8.1 (2002年)打的补丁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
    do {
char cmd[200];
char letter[2];

memset(letter, 0, sizeof(letter));
fprintf(stdout, ".");
fflush(stdout);
memset(additional_seed, 0, sizeof(additional_seed));
#ifdef PC
letter[0] = (randcnt % 25) + 'A';
if (randcnt % 2)
sprintf(cmd, "dir \"c:\\documents and settings\\%s*.*\" /s", randcnt > 2 ? letter : "");
else
sprintf(cmd, "dir %%SYSTEMROOT%%\\%s*.* /s /ta /od", randcnt > 2 ? letter : "");
if (!(fp = _popen(cmd, "r")))
#else
strcpy(cmd, "sh -c \"ps auxww 2>/dev/null\"");
if (!(fp = popen(cmd, "r")))
#endif
{
fprintf(stderr, "Can't open c:\\documents and settings, exiting\n");
exit(1);
}
i = 0;
while (((c = fgetc(fp)) != EOF) && (i < MAX_SEED_LEN))
additional_seed[i++] = c;
fclose(fp);
#ifdef PC
if (!(fp = _popen("dir \\", "r")))
#else
if (!(fp = popen("sh -c \"ps -ef 2>/dev/null\"", "r")))
#endif
{
fprintf(stderr, "Can't open \\, exiting\n");
exit(1);
}
while (((c = fgetc(fp)) != EOF) && (i < MAX_SEED_LEN))
additional_seed[i++] = c;

fclose(fp);


if (ret = sb_sha1Begin(global_data, &hc))
{
fprintf(stderr, "Error 4: ");
goto exit_seed;
}

lenbuf = i;
printf("len = %d\n", lenbuf);

if (ret = sb_sha1Hash(global_data, i, additional_seed, &hc))
{
fprintf(stderr, "Error 5: ");
goto exit_seed;
}
if (ret = sb_sha1End(global_data, &hc, &md))
{
fprintf(stderr, "Error 6: ");
goto exit_seed;
}


if (ret = sb_fipsRngOptionalInput(global_data, md.size, md.digest))
{
fprintf(stderr, "Error 7: ");
goto exit_seed;
}
moreseeds:
ret = sb_rngFIPS186Session(
global_data,
3*4,
returned);

if (ret != SB_SUCCESS)
{
fprintf(stderr, "Error 8: ");
goto exit_seed;
}
/*
* Convert to ints and test for reasonableness
*/
seed1 = seed2 = seed3 = 0;
for (j = 0, i = 0; i < 4; i++)
seed1 |= returned[j++] << (i * 8);
for (i = 0; i < 4; i++)
seed2 |= returned[j++] << (i * 8);
for (i = 0; i < 4; i++)
seed3 |= returned[j++] << (i * 8);

randcnt++;

fprintf(stdout, "%d\n",randcnt );
fflush(stdout);

} while ((randcnt < 5) ||
(returned[0] % 40 )
|| (!l_reasonable_seed(seed1) || !l_reasonable_seed(seed2) ||
!l_reasonable_seed(seed3)));

(2) 接着分析gen keys

函数原型:
int l_genkeys( unsigned int lmseed1,
unsigned int lmseed2,
unsigned int lmseed3,
int pubkey_strength,
int prikey_size,
char
prikey,
int pubkey_size,
char
pubkey)

它调用另一函数实现,这里面的核心如下代码. rng是基于IEEE 1363, sha-160实现的。
FIPS_RNG没有分析价值。
到了sb_genKeyPair()以内,里面全部是certicom的算法库libsb.lib, 没有源代码。
sb_genKeyPair()完整的跟踪可以用上几个小时。 但是不会有什么惊喜的结论。

这意味着即使从私钥中,也无法恢复种子LM_SEED1,LM_SEED2,LM_SEED3.
实际上, 私钥产生以后, LM_SEED1,LM_SEED2,LM_SEED3.
对于开发商来说,只有存档的价值,不再有使用的价值。

有的开发商从v8等老版本升级而来,没有改变私钥,存在安全隐患。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
int genkeys(unsigned int *seed,
int pubkey_strength,
sb_PrivateKey *privateKey,
sb_PublicKey *publicKey)
{
......

/*
* Set the initialization options.
* The selected options are:
* 1) point compression is on.
* 2) use new point compression.
* 3) maximum length of the random number generator seed is
* SB_MAX_SEED_LEN.
* 4) random number generator used is FIPS186.
*/
sb_Options.pointCompressionFlag = SB_ON;
sb_Options.ecesCompressionFlag = SB_P1363_13FEB1998;
sb_Options.rngInfo.seed.size = SB_MAX_SEED_LEN;
sb_Options.rngInfo.type = SB_FIPS_RNG;

/*
* Set seed to sb_Options using the value contained in seedValue.
* Note that it is assumed that the value in seedValue is obtained
* from a random source. In practice, a real random value from
* a secure random source must be set here.
*/
memset(seedValue, 0, sizeof(seedValue));
#if 0 /* P5308 */
for (i = 0;i < 4; i++)
seedValue[i] = (seed3 >> (1 << (i * 8)) & 0xff);
for (i = 0;i < 4; i++)
seedValue[i + 4] = (seed4 >> (1 << (i * 8)) & 0xff);
#endif /* P5308 */
for (i = 0;i < 4; i++)
seedValue[i] = ((seed[0] >> (i * 8)) & 0xff);
for (i = 0;i < 4; i++)
seedValue[i + 4] = ((seed[1] >> (i * 8)) & 0xff);
if (seed[2]) /* added 3rd int in v8.1 */
{
for (i = 0;i < 4; i++)
seedValue[i + 8] = ((seed[2] >> (i * 8)) & 0xff);
/* And added strength into seed */
for (i = 0;i < sizeof(pubkey_strength); i++)
seedValue[i + 12] = ((pubkey_strength >> (i * 8)) & 0xff);
}
memcpy( sb_Options.rngInfo.seed.value, seedValue, SB_MAX_SEED_LEN);

ret = sb_initialize(
ellipticCurve,
&sb_Options,
dataSize,
heapSize,
global_data,
heap_space
);
if (ret != SB_SUCCESS)
{
displayErrorMsg(ret);
exit(1);
}


/*
* 2. Generate ECC key pairs.
*/
ret = sb_genKeyPair(
global_data,
privateKey,
publicKey
);
if (ret != SB_SUCCESS)
{
displayErrorMsg(ret);
exit(1);
}
/*
* End Security Builder
*/
ret = sb_end(global_data);
if (ret != SB_SUCCESS)
{
displayErrorMsg(ret);
exit(1);
}

/*
* Free the memory space
*/
free(heap_space);
free(global_data);
return 0;
}

14. FlexLM ECDSA签名过程的漏洞

IEEE-163对ECDSA的签名过程是有严格规定的。FlexLM的做法和它不一致。它的确减弱了签名的安全性,但是漏洞目前并不能被利用。

首先,给出一个线性rng下ECDSA不安全的示范。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(1) 
r1 = k1 * G
s1 = (h1 + d*r1)/k1 mod n

(2)
r2 = k2 * G
s2 = (h2 + d*r2)/k2 mod n

可以得到:
(3)
(h1 + d*r1) / s1 - (h2 + d*r2) / s2 = k1 - k2 mod n

=>
d *(r1/s1 - r2/s2) + (h1/s1 - h2/s2) = C(k) mod n

注意到,这是一个线性方程:
d * A + B = C(k) mod n

可见,如果rng是h的线性函数,只要有两对sign, 并能获取k1与k2的差值,
并不需要知道k1,k2本身的值。就能解一个线性方程得出d来。
d = (C - B ) / A mod n
这里的除法是模逆运算, n是一个素数,它是有解且唯一的。

(1) 一个典型是,rng没有初始化或者初始化为一个常量;那么 k为常量。 差值C=0。

(2) 另一个典型是,某些不安全的rng,在seed session 时采用了系统时间。
prng=f( f1(Privkey), f2(Message), f3(Tickcount) ), 在Windows下, GetTickCount得到的是一个毫秒数。如果连续两次签名在1毫秒内完成, 那么它们的sign是同一个k生成的。从而差值C = 0。

因此,连续两次签名时需要检测, 它们的前半部分sign.r必须不同。以抵御攻击。

这里有一个案例, CloneCD v4,曾经采用ECNR-241签名(与ECDSA有所不同)。
被人做出keygen,原理和(3)一样。

FlexLM签名过程的rng分析

FlexLM rng有线性部分,也有非线性部分。它的Signing有如下特点:
参考l_prikey.c。
a) Seed with Private key, hash of message
b) Signature will be guaranteed repeatable given the same FEATURE data.
c) Requires a different certicom “context” for each signature.

这里面的b)是很诡异的做法,它充分暴露了FlexLM的k不是纯随机,而是与私钥和hash有关的伪随机。
但是这里要注意,它里面的确有大数相加的部分,但是那是一种保证bits的方法。

它的rng,并不是线性相加两个大数那么简单,而是拿它们Private key和hash去填充rng的buffer。

1
2
3
k = f1(privkey) + f2(privkey, msghash, curve)

C(k) = f2(privkey, msghash1, curve) - f2(privkey, msghash2, curve)

的确,对于同一个priveky来说,在任何一次签名,rng在f2时初始状态是固定的。
但是,f2并不是一个线性函数,它被非线性的sha hash给冲掉了。
C(k)是与privkey有关的非线性量。

在分析了:
(1)多个不同privkey对同一条msg签名
(2) 同一个privkey对多条msg签名
都没有找到可供利用的线性差值。 不再有冗余信息可以得出签名的k。

所以,前面说的线性攻击方法对FlexLM ECDSA无效。

那么,是否还有其它的攻击方法,恢复出k的信息,从而计算出privkey?
目前看来,没有直接的答案。

FlexLM的ECDSA的签名过程,b)点是一个非常不必要的做法。
为什么他们要做这么一个怪胎呢?显然不是为了制造一个漏洞假象。它只是保证签名的唯一性而已。

p.s. 关于RLM的题外话

这里要说到RLM (Reprise License Manager):
Flexlm原班开发人马,2006年从Macrovision跑路后,另起灶头,产品叫RLM。
http://www.reprisesoftware.com/index.php

它用的DSA-512签名。基于离散对数。 里面在签名的时候, 会把k加上若干个Q,填充到161 bit (or 163 bit ? 具体数值忘了 )。

这也是一个怪胎。因为 k + nQ mod Q 仍然是k。 开发者的意思是,在k上加上n倍模长,掩盖掉
k本身的bits信息,防止利用计时攻击,估算签名的时间,得出k。

RLM的开发者果然是有一鼓呆子气,如果攻击者都能物理接触到你的license maker Server了,
那直接复制你的文件就可以,还计时攻击个啥呢?对于PC来说,签名DSA-512在200 us内完成。
计时攻击要求:接触到服务器,能在服务器上运行纳秒级的计时器, 也就是能直接读取CPU的计时器(RDTSC);可以执行签名程序,进行上万次的签名试验。这除了开发者本人蛋疼的测试,其他人能有这条件吗? 这就是从自己口袋里掏钥匙的游戏。

这里说一个结论,RLM从 v1- v8,patch DSA verfiy, 写license maker,是很容易的事情。
v9之后checksum有所增强, 但是也不复杂。

包括RLM的Windows, linux, macos平台都一样。

RLM除了开发起来简单些,从Sign保护方面来说,只是把ECDSA Sign换成了DSA, 基本上是老虎变大猫的游戏。

15. FlexLM License服务器启动

说明: 本篇主要是基本知识简单介绍,与ECDSA无关。详见用户文档。

FlexLM的license是一种格式化的文件,关于这种格式的说明,可以参考FlexLM用户文档。
< License Administration Guide > ( fnp_LicAdmin.pdf )

一般来说,发行软件本身会带证书管理指南文档。包括证书格式,服务器配置,故障排除等内容。

比如, Cadence v16.5 (采用FlexNet v11.9.1.0 build 89952 i86_n3),安装完毕,
可以找到用户文档:FlexNet Publisher Licensing Toolkit 11.9.1,日期为 2010.12。

许可证服务器管理器是TCP/IP方式通讯的。一般可采用lmgrd + daemon(守护程序) 方式检查licensefile。
licensefile 可采用如下命令行启用:
lmgrd -c licensefile
licensefile 中描述了守护程序的名字。

许可证服务器管理器 lmgrd 的用途是:
• 启动并维护许可证文件的 VENDOR 行中列出的所有供应商守护程序。
• 向合适的供应商守护程序发出应用程序检出(或其它)请求。

lmgrd 命令行具体语法可以参考文档中《lmgrd 命令行语法》这一节。
lmgrd主要的用法为:
lmgrd [-c license_file_list] [-l [+]debug_log_path]
[-2 -p] [-local] [-x lmdown] [-x lmremove] [-z ] [-v] [-help]

16. FlexLM License文件格式

License文件采用文本格式,可以手工编辑,合并。对用户来说,比二进制格式要直观。
FlexLM特别强调它能灵活管理多种license。

可以参看< License Administration Guide > 这个文档。
Reading a License File, 这一章, 描述了license文件的格式。摘要如下:

许可证文件(license file)通常以一个 SERVER 行开始,
后跟一个或多个 VENDOR 行,然后是一个或多个 FEATURE 或 INCREMENT 行。
在某些情况下,许可证文件不需要 SERVER 行和 VENDOR 行(单机版,运行时不需要lmgrd和守护程序)。

许可证的类型有:
(1)流动许可证
流动许可证在各个FEATURE 行中没有 hostid这一项目。流动许可证要求运行 lmgrd 和 供应商守护程序以对许可证
的并发使用情况进行计数。lmgrd 使用FLEXnet Licensing TCP/IP 端口,缺省范围 (27000-27009) 。
也可以指定其它的端口。

文档里,给出浮动license的一个例子是:
SERVER lulu 17007ea8
VENDOR sampled
FEATURE f1 sampled 1.00 1-jan-2005 2 SIGN=signature1
FEATURE f2 sampled 1.00 1-jan-2005 6 SIGN=signature2
FEATURE f3 sampled 1.00 1-jan-2005 1 SIGN=signature3
此许可证文件指定许可证服务器为“lulu”,服务器hostid为17007ea8, 端口为默认。
客户可访问功能“f1”的 2 个许可证、功能“f2”的 6 个许可证以及功能“f3”的 1 个许可证。

(2)节点锁定许可证
节点锁定意味着,FLEXenabled 软件只能在一台或一组计算机上使用。节点锁定的许可证在某个 FEATURE 行中包含 hostid,该许可证将节点锁定到特定主机上。
共有两种类型的节点锁定许可证;不计数许可证和计数许可证。

如果将许可证数量设置为 0 (或 uncounted),则不对该许可证进行计数,并且允许在指定计算机上无限制地使用该许可证。
此配置不需要 lmgrd 或供应商守护程序,因为它不对功能的并发使用情况进行计数。

即使有hostid这一项目,如果hostid=ANY, 则不绑定硬件。

这里给出本地license的一个例子(SlickEdit 13, FlexNet v11.5),
说明,这只是一个例子,不是一个valid的license(Sign修改了的):

INCREMENT vswb vsflex 13.00 9-jul-2008 uncounted HOSTID=00117b8a597b \
ISSUER=”SlickEdit Inc.” ISSUED=24-jun-2008 \
NOTICE=” ** “ \
SN=SERIAL:WB_TRIAL|LICTYPE:TRL START=23-jun-2008 TS_OK \
SIGN=”01D2 87C9 CAA9 C2B9 3FA9 48B1 5668 AE7F 8097 71CE 7602 \
72F7 863C 82AD 422E 0802 ACDD D4B8 D4DE FADB EF50”

在这里,HOSTID 锁定为mac地址00117b8a597b。

在这里,守护程序是vsflex,本地license一样可以用lmgrd启动管理的。
本地slickedit.lic改为:
SERVER 127.0.0.1 ANY 27000
VENDOR vsflex
USE_SERVER

那么, slickedit将通过访问127.0.0.1:27000获取license。
我们在本地启动: lmgrd -z -c license.dat , license.dat如下:
SERVER this_host ANY
VENDOR vsflex
INCREMENT vswb vsflex 13.00 9-jul-2008 uncounted HOSTID=00117b8a597b \
ISSUER=”SlickEdit Inc.” ISSUED=24-jun-2008 \
NOTICE=” ** “ \
SN=SERIAL:WB_TRIAL|LICTYPE:TRL START=23-jun-2008 TS_OK \
SIGN=”01D2 87C9 CAA9 C2B9 3FA9 48B1 5668 AE7F 8097 71CE 7602 \
72F7 863C 82AD 422E 0802 ACDD D4B8 D4DE FADB EF50”

因此,采用本地license或是网络license主要看管理上的方便。

17. FlexLM对FEATURE/INCREMENT进行ECDSA签名方法

FEATURE/INCREMENT 行的基本格式为:
{FEATURE|INCREMENT} feature vendor feat_version exp_date num_lic SIGN=sign [optional_attributes]

(1)必选属性
FEATURE/INCREMENT 行关有6个必选字段,并且它们具有固定的顺序。这些字段是由供应商定义的,不能对其进行更改。

(2)可选属性
可选属性由供应商自行提供的,以便提供特定的许可行为。这些属性采用keyword=value 语法,其中,keyword 为大写形式。
所以在 FEATURE 或 INCREMENT 行中,它们必须保留在该位置,最终用户不能对其进行更改。
常见的有:
ISSUED=dd-mmm-yyyy 签发日期。
ISSUER=”…” 许可证签发者。
NOTICE=”…” 用于知识产权通告的字段。
PLATFORMS=”…” 使用情况受所列出平台限制。
START=dd-mmm-yyyy 开始日期。
VENDOR_STRING=”…” 供应商定义的字符串,用双引号引起来。

签名过程中,这些属性会按照固定的顺序处理。因此保证了用户不能更改FEATURE中的属性或者Sign。

在SDK中,l_crypt_private()这个函数用来处理feature的属性。它调用real_crypt()实现。
real_crypt()其实并不是一个crypt, 它是一个字符处理函数,FEATURE 或 INCREMENT 经过它的处理,然后才会进行ECDSA签名。
接下来就是ECDSA签名, 签名的算法和RNG,前面的文章已有说明,因此不再重复。

这里给出一个例子, 采用是FlexNet 11.5, ECDSA-163。

INCREMENT vsee vsflex 13.01 16-jul-2099 uncounted HOSTID=ANY \
ISSUER=”SLICKEDIT KG READYU#2K8” ISSUED=28-jun-2008 \
NOTICE=”readyu” \
SN=SERIAL:FWC123-74973876|LICTYPE:STD TS_OK \
SIGN=”023843740B3B1FBF51630285E892CF2E3D4AC88CEF 010FBFCB08A51D71423825CB84C5CD63905679F60A”

对于ECDSA来说,这个签名其实是:
hash(msg)=5b176716984bf0e4c0f2016785612e0ad31690e2
sign.r=023843740B3B1FBF51630285E892CF2E3D4AC88CEF
sign.s=010FBFCB08A51D71423825CB84C5CD63905679F60A

ECDSA的签名hash来自于msg的sha-160。

msg并不是直接的把这一行“INCREMENT vsee vsflex 13.01 16-jul-2099 uncounted HOSTID=ANY ….” 连接起来。

它是对INCREMENT行,real_crypt() 之后得来的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
它的签名msg如下:

unsigned char msg[] = {
0xD2, 0x0F, 0x37, 0xAB, 0xEF, 0x28, 0x01, 0xD0, 0x00, 0x56, 0x53, 0x45, 0x45, 0x0D, 0x64, 0x10,
0xC7, 0x6A, 0x75, 0x6C, 0x87, 0xC5, 0xD0, 0x73, 0x54, 0x59, 0x50, 0x45, 0x3D, 0x31, 0x32, 0x38,
0x49, 0x53, 0x53, 0x55, 0x45, 0x52, 0x3D, 0x53, 0x4C, 0x49, 0x43, 0x4B, 0x45, 0x44, 0x49, 0x54,
0x4B, 0x47, 0x52, 0x45, 0x41, 0x44, 0x59, 0x55, 0x23, 0x32, 0x4B, 0x38, 0x1C, 0x6C, 0x6A, 0x75,
0x6E, 0x4E, 0x4F, 0x54, 0x49, 0x43, 0x45, 0x3D, 0x52, 0x45, 0x41, 0x44, 0x59, 0x55, 0x53, 0x4E,
0x3D, 0x53, 0x45, 0x52, 0x49, 0x41, 0x4C, 0x3A, 0x46, 0x57, 0x43, 0x31, 0x32, 0x33, 0x2D, 0x37,
0x34, 0x39, 0x37, 0x33, 0x38, 0x37, 0x36, 0x7C, 0x4C, 0x49, 0x43, 0x54, 0x59, 0x50, 0x45, 0x3A,
0x53, 0x54, 0x44
};

msg里面的非ASCII字符,是一些常数。比如:
ANY_CODE (0xab370fd2),INCREMENT_FLAGv(0xd00128ef), NO_START_DATE_FLAG (0x73D0c587),

msg如果直接打印,这里面有00字符,还有非ASCII字符,因此会出现部分”乱码“。
?7(?VSEEd莏ul嚺衧TYPE=128ISSUER=SLICKEDITKGREADYU#2K8ljunNOTICE=READYUSN=SERIAL:FWC123-74973876|LICTYPE:STD

x86的字节序是little-edian。所以在内存里,ANY_CODE (0xab370fd2) 的顺序为:
0xD2, 0x0F, 0x37, 0xAB

事实上,在flexlm-enabled的程序中,搜这四个字节,可以定位 real_crypt()函数。

附录: l_crypt 的一些常数定义:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*
* Some constants for flags going into the string
*/

#define ANY_CODE ((long) 0xab370fd2)
#define USER_CODE ((long) 0xba1584a2)
#define DISPLAY_CODE ((long) 0xab8543cc)
#define HOSTNAME_CODE ((long) 0xbadaef01)
#define HOSTID_DOMAIN_CODE ((long) 0x49D654F9)
#define HOSTID_COMPOSITE_CODE ((long) 0x2388341c)
#define HOSTID_METER_BORROW_CODE ((long) 0x4aa87607)
#define HOSTID_VENDOR_CODE ((long) 0x12fe93a)
#define NO_EXTENDED_CODE ((long) 0x74ab99)
#define DEMO_CODE ((long) 0x122345a)
#define FLEXLOCK_CODE ((long) 0x1c8c6f21)
#define FLEXID1_CODE ((long) 0x61420b1)
#define FLEXID2_CODE ((long) 0x19481954)
#define FLEXID3_CODE ((long) 0x29ab7264)
#define FLEXID4_CODE ((long) 0x01181954)
#define FLEXID_FILE_CODE ((long) 0x8adf678a)
#define DISK_SERIAL_NUM_CODE ((long) 0x78131a7c)
#define ID_STRING_CODE ((long) 0xaabb007c)
#define SERNUM_ID_STRING_CODE ((long) 0x5c7b549c)
#define INTERNET_CODE ((long) 0x7c7cfea0)

#define INCREMENT_FLAG ((long) 0xd00128ef)
#define PACKAGE_FLAG ((long) 0x038ddeed)
#define UPGRADE_FLAG ((long) 0x11052f73)
#define NO_START_DATE_FLAG ((long) 0x73D0c587)