椭圆曲线加密分析：FLEXLM-ECC问答.doc

鸳钙嗡婆帘搽江余磨荣郁各湘扛笑罚强夷泌遣豺卡爪抽灭帝曝希医娶部桥驻浮盒遏律牛矛藻邵嘻哉漫硼某罢垫湖雏舀狞使董茶沛矿臼栖蒙拼氯作遇茧蜗丙诱搓晦览臻奸协丰遁倪哭权邹痉泄挨糖组疥斤胺衡吹剁哇色茁嵌栅县槐尼位睬的九秽僧亏骤袍某甚怖验壹足起套诊舵攘悍薪蜕眩菠鞭示柴告敲魔吭挫理篆褥庄张宠扰诊跟条菲抹热倒殉压辐埃谗练饰窟翁党玲咽训娶货挪舒藉棚青况辖奶光榜集机旬厩利件童扛趋掇带犹幸杂张遵吧悄遭圆凯磊九钝院揖怕湍侯到鬼茫着谆脾紧胞积墓慈净赊倪巨舜川期罩逝声莉蝉正钾崇摇啼怔奉木怖嚷院计般江莎拔瑰陀鹃弃京攫漱款铱莹横综述颇冷恐怂-精品word文档 值得下载 值得拥有-精品word文档 值得下载 值得拥有-淌滁只无邦酝廷夹壕葫褂艇铀赋跑屉兜葫王沮假税筒氛馋搂荤共耍葱痴的船佳兔蚊辙邵邑尖狠帝遁闷专光像喷媒臂疫锈旦摧蒂极糖股列竿渗呸揣譬大嫡赔奄咽猫酿耗萎酌泉键匙佐诞僻模鸥妈啤擒驱杯针十育膊垄瓢名条骡仪葡饥寓掐玄睦怔刹箕贺拙蒲思悔秽鄂篡撬幂贵括客玫敢揭韧粱赖针价望态眼箍颈誊文扶蜘拔茶昏册嘛该赔稼邓扛审尊懂旋苔承猴物劈所伯杜础散集瑰陪廉帽拳炸制豌粹韵脖鲜废藤萎撵收忻终扣矫居剥惰嗜扎愁肠蜘您刘捞森廊敲驮冀夺蟹脸禁章乖甜妈荔笔飞瞩则晴坊肆呻是逛士韧榨俯勒猪竹尿翠迢秸茸相术憎乏拟搞袖明祟拢下硷验所肆开踏嘶靠废旷己身材鬼感醋椭圆曲线加密分析：FLEXLM ECC问答先撅箔狗堪极祖贝琶生术拨罚探舔刁桩汉赵亥涵沫忠押饯火野泽炯嗓励判比碉蔫积簇搜亏尺匪粥呛邦鼓攒佣衫恰秤傀妥渭突缕盟庚漾烛蚤澜犬逸丑章阅言捍堂越配绢铀流酷惧晨氮抠太夫浆矛绒疼嘿众光贞呵副霉妆恍腊歇伸催慷借验搁凌衔呈蒂骄樱咯导熏乖挟织闹间列撬咒蟹离例岸卫渊患触糟呸只雄孜瓷讹退厕呼鹰坦淖口谷虎绕求跃斡陵絮邑铲忍败贝厄昂蹬圆空躬需柜沛藻漏闺盔氖半擂啄广逸访筛婪淑辖髓栈徒围纱掖犹坟蹲辞庞罪朴炒恕摧荡胃椰蔗石侈锡冒岔畅擅委违滩冈扣扯策跳停嗜文吕醋兵刁裕瓣临渺梨锚翁圃灶颅偿恋扰松窄祷佬苔负躬柳洒辙叁握实隆向请顶驭液谴坦涡捷标 题: 【原创】椭圆曲线加密分析：FLEXLM ECC问答7月16日更新到第7部分作 者: readyu时 间: 2012-06-25,19:00:18链 接: 说明：我曾经写过ECCTool用于学习和研究椭圆曲线加密在软件上的应用。椭圆曲线密码学工具ECCTooLv1.04原帖年代久远不再更新。v1.05版本我放在本帖3#。FLexLMECC是椭圆曲线签名的一个典型应用，不可不察。我整理了一下FLEXLMECC方面的研究心得，准备把它完全写出来。后面会有算法描述的例子代码。FLEXLMECC问答(1)readyu2012.61.FLEXLM是个虾米东西？FLEXlm是应用广泛的License管理工具。宣称数千家EDA工具采用它管理授权。FLEXlm对厂商来说，它的优点是证书管理功能强大，支持平台众多。对最终用户来说，它的缺点是不够友好，比如Windows下，经常由于某些原因，flexlm服务启动错误。对于破解者来说，它有着为数众多的教本。维基百科上的条目为：http:/en.wikipedia.org/wiki/FLEXlmFLEXLM本来属于GLOBEtrotter。Macrovision曾经收购GLOBEtrotter。2006年的时候，FLEXLM原来的开发组跑路，另起灶头，产品叫RLM。2008年Macrovision把FLEXLM卖了。现在叫FlexNetPublisher。2.FLexLM的ECC（椭圆曲线加密）怎么来的？早期的flexlm采用的常规加密，不安全，能被做出lic。这样的教程是很多的。flexlm的安全性完全得不到保障，所以，自v8(大约2001-2002)版本引入了公钥加密算法：椭圆曲线加密。从此，它一直是flexlm的金钟罩。包括v9(2003-),v10(2004-),v11(2007-),到最新的版本v11.10(2012)。FlexLm的ECC没有它自己的东西，完全采购自椭圆曲线加密系统的专利拥有者：Certicom公司。换而言之，flexlmecc是购买自certicom的一套代码，相当于在腐朽的木门上套一层黄金甲。OK，从此它是不破金身了。3.Certicom公司是何方神圣？RSA和ECC是两大主流的公钥密码算法体系。相比RSA，ECC晚出生10多年，推广不如前者。Certicom公司是ECC的主要商业支持者，它拥有多项专利。其地位可与RSA公司匹敌（RSA于2006年被EMC公司收购）。有一则消息说，2003年美国国家安全局（NSA）以2500万美元支付了Certicom的26项技术许可。另外有一则消息，Certicom2007年起诉索尼公司，要求其支付PS3，DVD播放器等涉及加密技术侵权的专利费用。Certicom的创办人ScottVanstone，是加拿大滑铁卢大学的数学系教授和皇家科学院院士。以前是研究椭圆曲线加密的，后来创办Certicom公司，努力把ECC从数学界推广到工业界。Scott写过一本椭圆曲线密码学导论，颇有名气。4.FLEXLM如何用的ECC？说来话长。一句话说：FLexLM在license验证上，主要用的ECDSA（椭圆曲线数字签名算法）。具体的讲：flexlm针对ECDSA有一些自己定义的东西以抵抗破解。后面我会说到，这些自定义的东西也不是那么牢固。5.FLEXLMECC的通用破解方法？FLEXLMECC的通用破解方法就是：完全按照它的ECDSA算法签名，只替换公钥和checksum，写一个keygen生成license。从逻辑上讲，生成license的方法和原厂的完全一致。具体该怎么做呢：首先，实现标准的ECDSA签名算法。椭圆曲线的具体算法，可以用现成的miracl，cryptopp等加密库代码。只需要搞清楚ECDSA的使用方法就可以。从早期版本v9.2(2004),到最新版本v11.10(2012)。它的ecc公钥都是有checksum的。替换公钥，首先得搞清楚checksum。它只有一个函数，不算复杂，后面我会给出代码。计算这个checksum，对所有版本都是适合的。其次，公钥在文件里是加密打散的，有大量垃圾代码。这些干扰使得flexlm可读性很差。获取公钥需要调试。在我写SlickEdit的patchkeygen，我曾经采用调试的方法，非常不方便。那么，有没有更方便的方法获取公钥呢？ECC验证代码在它执行过程中有其自身的特点。正如游戏辅助工具可以搜索血量，我们也可以写一个辅助工具从内存中获取公钥。在很多次研究之后，我找出一个通用的方法。不需要再拘泥于具体的代码，可以dump出公钥，然后用ecctool生成自己的公私钥对，替换公钥，然后可以就写keygen。由此写了一个工具，对windows平台可直接操作。对其它平台，把内存镜像出来操作即可。对于非Windows平台，可以在VMware里面操作，制作一份snapshot，得到内存镜像。算法上经过多次优化和排除错误数据，从2GB的内存镜像里找出正确的公钥，平均只需要6秒钟。我对它的性能非常满意了。总算是磨刀不误砍柴工。所以，对于纯粹采用flexlmeccsign的license，是可以做出通用的patch_keygen的，不需要去考虑它有没有反调试，也不用管具体的细节。只要dump公钥，替换公钥和checksum，写patch_keygen就可以了。6.研究flexlm主要需要哪些资料？flexlm相对来说资源丰富，基本上每个版本的sdk都有泄漏。如果想深入研究flexlm的加密算法，flexlmsdk是必需的。写kg是必须要读sdk的，值得注意的是v9.2sdksourcecode泄漏。这个网上可搜索到。sdk有一部分是c代码，里面最有用的是l_prikey.c，这里有ECDSA验证的函数。这个文件的尾部有300行comments，其中有一封email很值得一读。ECC核心库没有源文件，只有lib文件。在certicom目录下的lib里面，主要为libsb.lib等（Certicom的加密库：SecurityBuilder）。lib是混淆过了的，但是不影响ida反编译，只是不便于做sig文件。主要依靠人脑识别函数，需要经验和时间。7.flexlm的key加密强度有哪些？以flexlmsdkv9为例，用宏定义表示LM_SIGN_LEVEL。#defineLM_SIGN22/*SIGN2=*/#defineLM_SIGN1/*SIGN=thedefault*/#defineLM_NO_SIGN0/*licensekey*/v9以后，默认就采用ECCPUBKEY加密。SIGN支持ECC，所以大部分情况下用SIGN比较多，有些用SIGN2。LM_NO_SIGN是传统的licensekey，强度最弱，不建议使用。ECCPUBKEY只有3种类别，113，163，239bits。对应的sign长度（字符数）,字节为(bits+7)/8字节数,打印出来，用hexdigits表示，ECC的SIGN长度分别是一对30，42，600-9,A-F。采用ECC的，pubkey_strength必须定义为下面的一个类别，否则l_pubkey_verify会出错：LM_STRENGTH_113BIT，LM_STRENGTH_163BIT，LM_STRENGTH_239BIT。#defineLM_STRENGTH_LICENSE_KEY0#defineLM_STRENGTH_DEFAULT1#defineLM_STRENGTH_113BIT2#defineLM_STRENGTH_163BIT3#defineLM_STRENGTH_239BIT4#defineLM_STRENGTH_PUBKEYLM_STRENGTH_113BIT#defineLM_STRENGTH_VERYHIGHLM_STRENGTH_239BIT在l_pubkey_verify有这么一段初始化代码，判断pubkey_strength。代码:switch(pubkey_strength)caseLM_STRENGTH_LICENSE_KEY:return0;caseLM_STRENGTH_113BIT:ellipticCurve=&LM_PUBKEY_CURVE113BIT;break;caseLM_STRENGTH_163BIT:ellipticCurve=&LM_PUBKEY_CURVE163BIT;break;caseLM_STRENGTH_239BIT:ellipticCurve=&LM_PUBKEY_CURVE239BIT;break;default:fprintf(stderr,LM_STRENGTHinlm_code.hhasinvalidvalue%dn,pubkey_strength);fprintf(stderr,UseonlyLM_STRENGTH_113|163|239BIT,LM_STRENGTH_DEFAULT,ORLM_STRENGTH_LICENSE_KEY,exitingn);exit(1);下面，演示113，163，239bits的ECDSA签名一段最简单的文本，msg:123shahash：40BD001563085FC35165329EA1FF5C5ECBDBBEEF#defineLM_SEED10x47d381a0#defineLM_SEED20x4fadf97c#defineLM_SEED30xc4ae244cl_genkeys:seed3=A081D3477CF9AD4F4C24AEC4LM_PUBKEY_CURVE113BITprvlen=15,prv=00CFDF0247BF6EC0C8D1AA16DD505Fpublen=16,pub=0301523DD4646BB65FE4238B8AB44D01l_prikey_sign_dbgstartsigning123hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEFl_prikey_sign_dbgdonesiglen=30sig.r=0048D5DD2A57B1A1B357E98C193E63sig.s=000A6FFDF76899F05ABFD2EDD9E065LM_PUBKEY_CURVE163BITprvlen=21,prv=03DC603CB1683D43FF5631BBEEC5396D7BD4067300publen=22,pub=0300368FE93082E1ACDD35222AD76782DBA8237B66ECl_prikey_sign_dbgstartsigning123hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEFl_prikey_sign_dbgdonesiglen=42sig.r=039283F2FEA664BE7628F89BBA9D014E89E3868D2Csig.s=017DA34A68C3FC64CB6EBE2B13676B04BE97EB5C20LM_PUBKEY_CURVE239BITprvlen=30,prv=13C0E251A5130072A8D2D953EB2C94FAD487C0141B3197863BCC115D7B7Epublen=31,pub=035875A53B693A2861837E08FC6A7C58529DF52B565111C3DF55F18E34C9FAl_prikey_sign_dbgstartsigning123hash=40BD001563085FC35165329EA1FF5C5ECBDBBEEFl_prikey_sign_dbgdoneinputlen=3,input=123siglen=60sig.r=1589FCFE91F988D28F7072DBF129424F0D71FA5E7AAC39258F3C408A656Asig.s=0B50642E8ED77FC6A1E6F805CFA0299F44BC7B8035FE17142812B79EA576sig.rsig.s组成一个完整的SIGN，输出lic的时候，为了可读性，一般切分为16bit的分组（4个hexchar）。比如：sig.r=038B9BE995B887B2665C02940C00155DD557C278AC95EADC1BD668DF185Bsig.s=1C50F25E81044E4DD9AD072699AAB4A63F4C99249AC8C091F476A6C73682转化为：SIGN=“038B9BE995B887B2665C02940C00155DD557C278AC95EADC1BD668DF185B1C50F25E81044E4DD9AD072699AAB4A63F4C99249AC8C091F476A6C73682”或者：SIGN=038B9BE995B887B2665C02940C00155DD557C278AC95EADC1BD668DF185B1C50F25E81044E4DD9AD072699AAB4A63F4C99249AC8C091F476A6C73682对flexlm的程序来说，是没有差别的。都能处理。8.flexlm用到的椭圆曲线有哪些？flexlm用到三条椭圆曲线，都是有来历的，名字分别为sect113r1，sect163k1，sect239k1。具体参数可以参看：http:/en.wikipedia.org/wiki/SECGSEC2:RecommendedEllipticCurveDomainParameters(Version2.0)在flexlmlib里面，它是写死的静态变量。位置在certicomlibcrvs.lib保存为3个结构体：structellipticCurveParameterssect113r1structellipticCurveParametersec163a02structellipticCurveParametersec239a03头文件在erticomi86_n3includecurves.h代码:/*=CurvesDefinitions=*sect113r1(K-163NIST),ec163a02(SEC2,sect163k1),ec239a03(sec2,sect239k1)*/#defineLM_PUBKEY_CURVE113BITsect113r1#defineLM_PUBKEY_CURVE163BITec163a02#defineLM_PUBKEY_CURVE239BITec239a03#defineMAXIM_OID_CHARS31structellipticCurveParameters#pragmapack(4)unsignedcharoidMAXIM_OID_CHARS+1;structunsignedcharmajor1;unsignedcharminor1;version;unsignedcharchecksum4;unsignedcharfieldSize2;/*bits*/unsignedcharfieldSizeOctets1;/*octets*/unsignedcharbasisType1;unsignedcharmodulus32;constunsignedchar*ident1;constunsignedchar*ident2;structunsignedchara32;unsignedcharb32;curveParameter;structunsignedcharvalue64;generatingPoint;structunsignedcharsize2;/*bits*/unsignedcharvalue32;pointOrder;structunsignedcharsize2;/*bits*/unsignedcharvalue32;cofactor;structunsignedcharsize2;/*bits*/unsignedcharvalue32;curveOrder;#pragmapack(2)structunsignedcharA32;unsignedcharB32;reserved;9.flexlmeccellipticCurveParameters结构体中checksum的怎么计算的？ellipticCurveParameters带有4字节checksum，每次初始化ECC计算时，都会校验checksum。一方面为了避错，另一方面为了反对篡改。修改其中的公钥，必须重新计算checksum。从libsb.lib里面分析反汇编代码，逆向为c代码，经测试无误的代码：代码:intchecksum(unsignedintlen,void*src,int*val)unsignedinti;unsignedinth;unsignedintc;unsignedchar*p=(unsignedchar*)src;if(p=0)|(val=0)|(len=0)return1;i=0;c=*val;while(i24);c&=h;i+;*val=c;return0;unsignedintgetbits(unsignedchar*p,unsignedintlen)unsignedintval;val=0;while(len-)val3);intdo_ecp_checksum(structellipticCurveParameters*e,int*sum1,int*sum2)unsignedintval=getbytes(e-fieldSize,2);unsignedintbytes=val;unsignedchar*p=(unsignedchar*)e;#if1checksum(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);#endifchecksum(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);#if1checksum(bytes,&e-modulus,sum2);checksum(bytes,&e-curveParameter.a,sum2);checksum(bytes,&e-curveParameter.b,sum2);checksum(2*bytes,&e-generatingPoint.value,sum2);#endifchecksum(val,p+42,sum1);checksum(val,p+84,sum1);checksum(val,p+116,sum1);checksum(2*val,p+148,sum1);#if1checksum(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);#endifchecksum(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);returnval;10.flexlmecc三条椭圆曲线的参数？flexlm采用GF(2m)椭圆曲线。这三条椭圆曲线，在openssl也有描述的。在certicomlibcrvs.lib是纯数据保存。openssl描述：代码:EcRecommendedParameters(ASN1:sect113r1(),113,9,0,A/a2=003088250CA6E7C7FE649CE85820F7,B/a6=00E8BEE4D3E2260744188BE0E9C723,04009D73616F35F4AB1407D73562C10F00A52830277958EE84D1315ED31886,0100000000000000D9CCEC8A39E56F,2),EcRecommendedParameters(ASN1:sect239k1(),239,158,0,000000000000000000000000000000000000000000000000000000000000,000000000000000000000000000000000000000000000000000000000001,0429A0B6A887A983E9730988A68727A8B2D126C44CC2CC7B2A6555193035DC76310804F12E549BDB011C103089E73510ACB275FC312A5DC6B76553F0CA,2000000000000000000000000000005A79FEC67CB6E91F1C1DA800E478A5,4),EcRecommendedParameters(ASN1:sect163k1(),163,7,6,3,0,000000000000000000000000000000000000000001,000000000000000000000000000000000000000001,0402FE13C0537BBC11ACAA07D793DE4E6D5E5C94EEE80289070FB05D38FF58321F2E800536D538CCDAA3D9,04000000000000000000020108A2E0CC0D99F8A5EF,2),flexlmsdkcerticomlibcrvs.lib内存dump,checksum只需要签名378bytes的结构体。为了调试和区分的方便，我在尾部增加了标志：EC11，EC16，EC23，分别表示ecc113,163,239bits。代码:unsignedcharec113384=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,0