RSA那些坑

本文涉及的产品
密钥管理服务KMS,1000个密钥,100个凭据,1个月
简介:

1.背景


最近生产上出了两个因为RSA加解密导致的性能问题,一个是加密引起的,一个是解密引起的,都是大量线程在进行RSA操作时等锁,线程被block,请求都被堆在Weblogic队列里不能处理。为此,我就研究了一下RSA加解密在Java里的实现,发现加解密的问题都出现在同一个地方。因为RSA加解密使用的方法都是同一个,就是计算ae mod n,也就是模幂运算,在做这个运算的时候,为了防范攻击,需要加入随机因素,寻找一个blinding parameter,让攻击者无法破解私钥,就是在寻找这个blinding parameter的时候线程出现了堵塞。下面的内容会做详细阐述。


另外,两个问题出现的jdk版本不一样,第一个是1.6,第二个是1.7,都是同一个方法,但是底层实现不太一样。


2.问题描述



2.1 第一个问题:动态菜单签名


客户端的菜单不是写死在客户端的,是服务器下发的。客户端每次启动时,向服务端请求最新的动态菜单,通过向服务端发一个上次更新菜单的时间,来判断服务器是否有新的菜单。为了防止菜单下发后被篡改,对菜单url做了签名。菜单的内容是基本不变的,但是每个人过来都要做一次签名,结果有次对菜单做了较多改动,又赶上做了一次推送,大量用户打开App,把服务器搞挂了。因为Java提供的签名方法内部上锁了,大量线程在等待锁,请求又多,扛不住了。

wKiom1ecfDTAnG8BAAH-uEVxoAo931.png

这个问题没有深入往下研究,用缓存解决了。因为下发的菜单或者其他资源几本是不变的,所以只要按字符串为key做缓存就行了。比如把对url的签名,按url为key缓存。

1
2
3
4
5
6
7
//先查缓存
String signature=memkv.unsafe_hget(“SIGN_LIST”, url);
//查不到则计算签名,放入缓存,缓存1800s
if (signature== null ) {
  signature = SignatureUtil.sign(url);
  memkv.unsafe_hset(“SIGN_LIST”, url,  1800 );
}


2.2 第二个问题:上送报文RSA加密


应用开启了报文全加密,大部分加密都是通过与服务端协商一个对称密钥,然后使用非对称密钥加密后传送,后续的报文都是通过对称加密处理的。但是有部分报文直接用了RSA加密,对性能产生了影响,同样是等锁。一共最多1000个线程,900多个都在等这个锁。


wKioL1ecfcKBbxhsAABE7brk1eE823.png


这个问题没法用缓存解决了,因为每个人上送的信息都是不一样的,需要好好研究一下了。



3.问题分析



通过看代码和查资料,我发现RSA在实际应用中并不是简单的做大数运算,为了提高安全性防范各种攻击,在加解密过程中都需要添加一定的随机因素。随机因素有两方面,一个是为了让同一明文每次加密产生的密文都不一样,加密前先填充一部分随机数,这个不止RSA有,DES等对称加密也都有,称为padding。另一方面是RSA解密(加密与解密用的同一个方法)的时候在做模幂运算时加入随机数,似的做运算的时间不固定,让攻击者无法统计计算时间, 致盲攻击者,称为blinding。 上面出现的问题都是blinding引起的。


3.1 加密随机数(padding)


加密的时候,一般需要在明文上填充一部分随机数,这样每次产生的密文都不一样,这个过程称为padding,而且加密标准里有各种类型的padding标准,比如PCKS1。

比如明文是D,通过一些填充,形成一个0011xxxxxxx11D的待加密串,00是开头,两个11中间是随机数,而且这些随机数不能含有1。这样同一个D,每次产生的待加密串是不一样的,解密后,按照这个格式把D取出来就行了。加密和解密端要使用同样的padding格式。

以下过程依次为

原始明文 -> padding后明文 -> 密文 -> padding后明文 -> 原始明文

对明文D做第一次加密

D -> 00112311D -> 123456 -> 00112311D -> D

对明文D做第二次加密

D -> 00117811D -> 783719 -> 00117811D -> D


为什么要使用padding呢?这个比较容易理解,比如有一种攻击类型叫做短消息攻击,如果我已知加解密双方的明文空间是四个字节的字符串,那我就可以通过观察明文对应的密文把所有的对应关系枚举出来,不需要密钥我就能知道这个密文对应的明文了。如果同样的明文每次密文都不一样,就没法实现这种攻击了。



3.2 解密随机数(blinding)


这个需要先从一种特殊的攻击方式说起。


3.2.1 时序攻击


RSA的破解从理论上来讲是大数质数分解,可是就是有一些人另辟蹊径,搞出乱七八糟的破解方法。有一种攻击方法叫做时序攻击(timing attack),根据你解密的时间长短就能破解你的RSA私钥。这是什么鬼呢?

举一个不恰当但是比较容易理解的例子:

A通过B提供的加密装置把报文加密后发给B,我们不关心加密是怎么搞的,因为时序攻击也不用关系加密端。

AB发的密文是2048位的01串,B有一个私钥,也是2048位的01串,解密的时候把两个串and一下

(以下示例用四位表示)

密文0101

私钥0110

明文0100

问题的关键来了,进行and运算时如果有一个0,那么运算的时间为1ms,如果两个都是1,运算的时间是10ms(只是个假设)。

基于以上假设,A就可以破解B的私钥了。A先构造一个0001的密文,获取B解密的时间,如果是1ms左右,那么对应的位就是0,如果是10ms左右,对应的1,依次类推,就把整个私钥推断出来了。


如何防范这种攻击呢?

一种最简单有效的方法,每次过来一个密文,先用一个随机数与它and一下,然后在与私钥and,只要随机数是真正的随机数,那么是无法破解的。注意,是真正的随机数而不是伪随机数。


现在回到RSA,RSA解密的本质就是幂模运算,也就是x = a ^ b  mod  n ,其中a是明文,b是私钥,n是两个大质数(p-1)(q-1)的积。由于这些数都特别大,比如b可能有2048位,直接计算是不可行的。计算x的最经典的算法是蒙哥马利算法,用代码表示如下:

1
2
3
4
5
6
7
8
9
10
11
12
int  mod( int  a, int  b, int  n){  
     int  result =  1 ;  
     int  base = a;  
     while (b> 0 ){  
      if (b &  1 == 1 ){  
          result = (result*base) % n;  
       }  
      base = (base*base) %n;  
       b>>= 1 ;  
    }  
    return  result;  
}

这个算法从b的最低位循环到最高位,如果是1,需要进行两次模乘运算,如果是0的话则只需要一次。由于这个操作是比较耗时的,所以0和1对应的时间差别较大。攻击者可以通过观察不同输入对应的解密时间,通过分析统计推断出私钥。具体的分析方法也不难,不过我没怎么看懂。。。

而防范RSA时序攻击的方法也是在解密时加入随机因素,让攻击者无法获取准确的解密时间。


3.3 线程阻塞原因


3.3.1 关于随机数


真正意义上的随机数,是很难产生的,因为即使小到原子,它的规律也是有迹可循的。所以我们产生的随机数都是伪随机数,但是伪随机数的随机性也是不一样的,如果产生的随机数规律性很强,那就很容易被预测到,而如果产生的随机数被预测的难度特别大,那么我们就可以认为它是真随机数了,只有强度高的随机数用来加解密等操作上才是安全的。

 

目前大部分操作系统都会提供两种随机数的产生方式,以Linux为例,它提供了/dev/urandom和/dev/random两个特殊设备,可以从里面读取一定长度的随机数。/dev/random是blocking pseudo random number generator (阻塞式伪随机数产生器),它是通过网络事件,键盘敲击事件等物理上随机的事件,收集一些随机bit到熵池来产生随机数。这个随机生成函数可能因为熵池为空而等待,所以需要大量随机数的情况下它会显得很慢,但诸如产生证书之类的操作需要这种强度的随机数。 而/dev/urandom就是unblocking,它不会阻塞,但是产生的随机数不够高,是以时间戳之类的种子来产生随机数。

 

其它操作系统的实现方式可能不同,但是本质都是一样的。总之,要想获得一个真随机数,不管用什么语言,都需要等。在Java里面,可以用SecureRandom产生随机数,而且可以在JVM参数里配置是使用/dev/random还是/dev/urandom,如果安全性要求改,就用/dev/random,但是性能是就会有折扣。


3.3.2 Java的Cipher类


Java的加解密库是通过spi的方式,底层有不同的provider实现,默认的是sun官方的,比较有名的第三方的是bouncy castle。而上层的统一接口就是Cipher。


使用方法:

1
2
3
4
5
6
7
//获取Cipher示例,注意这个并不是单例的,它有线程安全问题
//第一个参数是算法以及填充之类的,第二个是Provider,比如BC就是bouncy castle
Cipher cipher = Cipher.getInstance( "RSA/CBC/PCKS1" "BC" );
//必须初始化
cipher.init(Cipher.DECRYPT_MODE, privateKey);
//传入byte[]数组进行加解密
cipher.doFinal(miwen);

我在看我们应用的代码时,发现全局竟然只有一个Cipher,这个是有问题的,它有线程安全问题,看代码以及多线程做实验都发现了,由于初始化一个Cipher比较慢,所以最好用ThreadLocal来解决它的线程安全问题。


3.3.3 getBlindingParameterPair函数


通过堵塞的线程堆栈来看,两个问题都出现在RsaCore的getBlindingParameterPair上,第一个行数是261,第二个是417,这是因为两个jdk不一样。


在jdk1.6里面,getBlindingParameterPair用的是随机数的方法,堵在了SecureRandom.nextBytes上,这个函数在底层是读的/dev/random,如果产生的随机数不够用,就要堵塞。


在jdk1.7_80这个版本里,getBlingdingParameterPair没有用随机数,而是通过计算得到了一个pair,具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
synchronized  ( this ) {
   if  ((! this .u.equals(BigInteger.ZERO)) && (! this .v.equals(BigInteger.ZERO)))
  {
   localBlindingRandomPair =  new  RSACore.BlindingRandomPair( this .u,  this .v);
   if  (( this .u.compareTo(BigInteger.ONE)<= 0 )||( this .v.compareTo(BigInteger.ONE)<= 0 ))
   {
    this .u = BigInteger.ZERO;
    this .v = BigInteger.ZERO;
   else  {
    this .u =  this .u.modPow(BIG_TWO, paramBigInteger3);
    this .v =  this .v.modPow(BIG_TWO, paramBigInteger3);
   }
  }
}

在同步块里进行大数运算,为什么要上锁我没有深入研究,但是1.7确实比1.6快了。


上面都是用jdk自带的provider实现的,我又试了下把provider换乘bouncy castle,比1.6自带的快很多,但是比1.7的慢,用多个线程解密的时候发现也是堵在SecureRandom.nextBytes上,所以bouncy castle也是用的随机数。

wKiom1ecqinC_hF-AAA7x2YiB_E692.png



问题的原因就是jdk自带的RSA解密方法为了防范时序攻击导致的,但是也没有好的解决办法。在早期的jdk里,代码中有if(ENABLE_BLINDING)这个判断,所以是可以把blinding关掉的,但是新的已经没有选项了,都需要使用blinding,因为时序攻击确实是挺容易实施的。


4.问题解决方案


第一个问题用缓存解决了,每个菜单半个小时只做一次签名,与原来的每个请求都签名相比,性能好太多。


第二个问题除了锁的问题,Cipher类本身有线程安全问题,通过ThreadLocal解决线程安全问题。但是锁的问题不好解决,短期内通过使用计数器对线程进行保护,比如最多允许300个线程同时调用这个函数,多了直接拒绝,因为使用RSA加解密的交易并不多,出现拥堵估计是特殊情况。长期内还是把用RSA加密报文的方式彻底换掉,RSA只加密对称密钥。


总之,RSA作为一种低效的加密方法,用在加密大量数据上面是不合适的,即使是签名之类的地方,能尽量少用也要少用,否则对性能影响很大。



本文转自nxlhero 51CTO博客,原文链接:http://blog.51cto.com/nxlhero/1832127,如需转载请自行联系原作者

相关文章
|
7月前
|
安全 算法 网络安全
RSA2048与RSA3072的闲言碎语
RSA2048与RSA3072的闲言碎语
300 0
如何生成RSA,RSA2密钥
密钥生成或如何使用(创建应用):[url]https://openclub.alipay.com/read.php?tid=1606&fid=72[/url] 1.密钥生成工具下载:[url]https://docs.
1677 13
|
算法
RSA和RSA2签名算法区别
RSA和RSA2签名算法 什么是数字签名? 一个很好的说明文档可以参考:What is a Digital Signature?,中文翻译可以参考:数字签名是什么?. 简单来说,签名主要包含两个过程:摘要和非对称加密,首先对需要签名的数据做摘要(类似于常见的MD5)后得到摘要结果,然后通过签名者的私钥对摘要结果进行非对称加密即可得到签名结果。
5617 12
|
3月前
|
安全 算法 网络安全
浅谈非对称加密(RSA)
浅谈非对称加密(RSA)
141 0
|
3月前
|
算法 JavaScript Java
AES和RSA
AES和RSA
43 0
|
算法 Linux 数据安全/隐私保护
RSA加密算法
RSA加密算法
252 0
RSA加密算法
|
机器学习/深度学习 算法 安全
RSA,RSA2密钥和MD5说明
说明:   现在关于RSA,RSA2,DSA,MD5,AES加密原理这里就不说了,网上已经有很完善的资料可以供我们了解。   下面说说在集成支付宝接口常用的RSA2(强烈推荐使用!!!),RSA,MD5(不推荐使用) 签名方式使用优先级   RSA2>RSA>MD5 支付宝接口签名支持表     注:老板wap支付密钥相关产品已经下架大家无需关注 常见问题:   1.
1980 12
|
Shell
如何生成RSA2密钥
密钥文件说明:    1、rsa_private_key.pem:原始私钥(又称pkcs1私钥),适用于非Java开发语言;  2、rsa_private_key_pkcs8.pem:pkcs8私钥,适用于Java开发语言;  3、rsa_public_key.pem:商户公钥,需上传至应用中加签方式的应用公钥位置。
2058 11
|
JSON 移动开发 Java
RSA 非对称加密【转】
演示代码:https://pan.baidu.com/s/10rfSUUDEEHvCDEYH0oEVCw   Base64工具类,可以让rsa编码的乱码变成一串字符序列 1 package com.
1389 0