1394 is back !

从XP时代开始就一直在用1394 Kernel Debugging,虽然Windows相继增加支持了USB2、USB3或者网络调试,但1394因其方便及更好的适用性一直是我的最爱,这也是为什么没有将我的工作笔记本升级到超级本的原因。

但从Windows 10发布以后,微软不再提供Kernel Debugging over 1394,但好在有相应的Workaround延长了1394的寿命,参见 KD 1394 Work-Around。但此办法无法解决boot debugging的问题,好在我目前都是系统级的内核调试,用不着boot debugging。

只是好景不长,随着Win10版本升级,1394又不行了。曾经为了测试新版Win10的兼容性,装了Windows 10 Pro Insider Preview 16226,结果发现Kernel Debugging over 1394彻底罢工,试过几个版本的Kd1394.dll均不行。

本以为1394就此死翘翘的时候,看到M$发布的一则消息:New WinDbg available in preview!。安装只能通过Windows Store,安装后习惯性的检查了一下文件目录,发现了新版的Kd1394.dll,随即在Win10 Pro 16226系统上做替换测试,然后 bing bing bing ! Windbg host端不断吐出字符来!

后来在Win10 Pro 15063上做了验证,发现此版Kd1394.dll并不适用,但老版的Kd1394.dll还是可以正常适配Win10 15063系统的。作为一个重度1394使用者,又可以欢呼了,但此好景能延续到什么时候呢?

Continue reading » · Rating: · Written on: 09-10-17 · 1 Comment »

Win10升级导致的休眠故障

一切都是因为手贱,看到Win10的升级引入了不少新的特性,心痒就赶了个时髦。升级过程花了不短的时间,但总体顺利,使用上也没有发现异常,也没有发现改进,比如Hyper-V照常和Vmware Workstation冲突。

下班后将电脑休眠从公司带回家,但等到再开机却发现系统重启了,日志中没有看到明显异常。之后就发现休眠时不时就会出问题,不是休眠中当机,就是休眠后无法正常开机。

用驱动大师升级了所有能升级的驱动,问但题还是没有解决,只得回退系统,但回退之后发现还是不能正常休眠。看来只能上Windbg来动动手术了:

开始调试时休眠正常:过程中曾中断系统枚举了所有的进程、IRP及ERESOURCE锁的,只发现dxgkrnl.sys驱动中有明显的锁等待,不少线程都因尝试获取一个已经Exclusively Owned ERESOURCE锁。dxgkrnl是DirectX显示驱动,与此相关的只有intel显卡,等系统恢复后卸载了intel显卡驱动,用Windows来自动安装。

重试几次后windbg端忽然显示出熟悉的输出:

*** Fatal System Error: 0x0000009f
           (0x0000000000000003,0xFFFF980487D7B060,0xFFFFD3810AFB68F0,0xFFFF980490101010)

果然有坑!分析下来发现是蓝牙驱动的问题:

2: kd> !devobj ffff980487d7b060; !irp  ffff980490101010 1
Device object (ffff980487d7b060) is for:
   USBPDO-8 \Driver\usbhub DriverObject ffff980487f6b300
   ...

2: kd> !devnode ffff98048901c010
DevNode 0xffff98048901c010 for PDO 0xffff980487d7b060
  Parent 0xffff980488186d30   Sibling 0xffff98048940f790   Child 0xffff98048929dd30   
  InstancePath is "USB\VID_0A5C&PID_21E6\7CE9D3E86CA0"
  ServiceName is "BTHUSB"
  ...

2: kd> !dh -f bthport
File Type: DLL
FILE HEADER VALUES
    8664 machine (X64)
       C number of sections
CED98754 time date stamp Wed Dec 20 22:34:12 2079
...

bthport的timestamp竟然是2079 !? 什么鬼!先不管这些,重启系统后将蓝牙禁掉后,再测试休眠,试了几次均正常。然后开启蓝牙,什么都不做再次尝试休眠,果然又中招。

问题解决起来倒也简单:将所有的蓝牙设备都删除,重新安装Thinkpad Bluetooth,之后又测试了几次休眠,再没有出问题,世界终于又大同了!

在检查系统加载驱动过程中还有个新发现,国内的公司还有各大银行简直是驱动开发专业户,每家都有几个驱动,就连迅雷,你个下载软件,竟然有两个内核驱动。不由分说,直接咔嚓了此类驱动。从此和谐社会!比新闻联播还鸡血!

Continue reading » · Rating: · Written on: 09-01-17 · 1 Comment »

解析TopLevelIrp

何为TopLevelIrp

TopLevelIrp是当前内核线程结构中的一个指针,可以是一个数值标识(ULONG_PTR),也可以是指向一个内存块的指针(内核IRP结构或用户自定义结构),其目的就是给文件系统驱动记录当前线程其内核栈最早传入且正在处理的I/O请求。因为处理一个I/O请求的过程中可能引入新的I/O,这样就会导致文件系统的重入(嵌套调用),重入问题很有可能会带来对资源依赖的死锁,所以文件系统驱动需要在重入的情况也能甄别出当前正处理的请求是不是最早的,即当前线程内核栈及资源的占用情况,从而采取不同的策略以避免死锁的发生。在时间顺序上最早的请求,从调用栈上来看就是处于最高地址(最高位置)的请求。

TopLevelIrp在内核线程结构中的定义如下:

typedef struct _ETHREAD {
    KTHREAD Tcb;
    ...
    //
    //  File Systems
    //

    ULONG_PTR TopLevelIrp;  // either NULL, an Irp or a flag defined in FsRtl.h
    struct _DEVICE_OBJECT *DeviceToVerify;
    ...
} ETHREAD, *PETHREAD;

TopLevelIrp及DevcieToVerify等域均是留给文件系统驱动专用的,可以作为一个当前线程的环境变量或各层调用栈间的共享变量。

系统操作函数

ETHREAD是内核私有结构,系统内核提供给外部组件(主要是文件系统驱动)两个接口:

函数 功能
VOID IoSetTopLevelIrp(IN PIRP Irp); 设置(改变)当前线程的TopLevelIrp值
PIRP IoGetTopLevelIrp(VOID); 读取当前线程的TopLevelIrp值

TopLevelIrp的操作过程

文件系统驱动与操作系统内核组件:Cache Manager(缓存子系统)、Virtual Memory Manager(虚拟内存管理子系统)及I/O Manager (I/O子系统)间交互相非常紧密且调用关系也非常复杂,调用嵌套及重入的情形非常多,分辨并正确处理不同的重入情景正是文件系统驱动不得不面对的复杂难题。

TopLevelIrp就是为了解决这个问题而设计的。其最直接的操纵及访问者也是文件系统驱动,因为用户层I/O请求最初的响应都是由I/O Manager直接传给文件系统的。文件系统驱动在响应过程中会调用操作系统的其它子系统,在调用前会针对TopLevelIrp做不同的设置。另外还有几种常见情况,如Cache Manager及Virtual Memory Manager会根据内存压力来发起I/O操作,所以内核子系统也需要修改、设置TopLevelIrp域以标识出本次I/O操作的发起者。

IoGetTopLevelIrp()返回值 (当前线程的TopLevelIrp域) 含义
FSRTL_CACHE_TOP_LEVEL_IRP 由缓存管理器触发的i/o请求:延迟写(Lazy-write)或预读(Readahead)
FSRTL_MOD_WRITE_TOP_LEVEL_IRP 由系统脏页回写线程触发的写请求(在MiMappedPageWriter回写映射文件的脏页时)
FSRTL_FAST_IO_TOP_LEVEL_IRP 由I/O Manager及文件系统自身处理Fast i/o请求时设置
FSRTL_FSP_TOP_LEVEL_IRP 通常由文件系统本身触发,用以标识文件系统驱动自身的i/o处理线程(Workitem线程池)。由于此情况下TopLevelIrp完全由文件系统自已管理,IRP或私有结构,通常由文件系统自已构造并使用

操作场景

  1. 用户态切换到内核态 这是最通常的情形,即请求直接来自于用户,用户请求经过syscall之后到达I/O Manager,而后I/O Manager会构造Irp并直接传给文件系统。 文件系统最通常的做法就是将当前的Irp设为TopLevelIrp。文件系统当然也可以用自己私有的结构,因为此线程在Irp没有完成之前将完全由文件系统所控制,TopLevelIrp也只有文件系统驱动会查询。
  2. Fast I/O 用户态的请求通过syscall到达I/O Manager后,I/O Manager发现文件已经被打开过且可以通过文件系统驱动所提供的callback直接来处理这个请求,不必从内存池中分配Irp等结构。 文件系统被调用后又会调用内核所提供的文件系统支持函数(FsRtl...),此操作将有可能涉及Cache Manager、VM,或重入文件系统驱动等,所以文件系统支持函数会设置TopLevelIrp为FSRTL_FAST_IO_TOP_LEVEL_IRP以标示出最初的请求响应是通过Fast I/O来做的。
  3. 文件系统自身的Workitem线程 类似第一种情形(用户态切换到内核态),Workitem线程本身是由文件系统发起并且是文件系统所私有的内核线程,但Workitem中的操作却是有可能重入文件系统的(这个由文件系统的设计决定)。 TopLevelIrp的值可以由文件系统驱动自行决定,如可以设为FSRTL_FSP_TOP_LEVEL_IRP,也可以设为此Workitem当前要处理的请求Irp,也可以设成是文件系统驱动的私有结构。
  4. 缓存管理器:延迟写 Cache Manager的Lazy-write操作(延迟写)是在Cache Manager私有的内核线程中执行的。在调用文件系统进行I/O操作之前会设置TopLevelIrp为FSRTL_CACHE_TOP_LEVEL_IRP,因为Lazy-write操作会通过Cache Manager callback来获取相应的锁资源,并且最终的I/O操作总要由文件系统来完成。
  5. 虚拟内存管理器:MiMappedPageWriter 内存映射文件的I/O不会经过Cache Manager,而是由Virtual Memory Manager直接处理的,并且是在Virtual Memory Manager私有的内核线程中做的,此线程的处理函数就是MiMappedPageWriter。同Cache Manager延迟写的流程类似,最终的I/O操作总要由文件系统来完成,所以移交控制权之前,VM会将当前线程的TopLevelIrp设置为FSRTL_MOD_WRITE_TOP_LEVEL_IRP,以通知文件系统驱动当前请求是由VM发起的。

不同文件系统驱动的处理差异

前面说过TopLevelIrp的读操作及检测只有文件系统驱支在做,虽然其设置可以是多方的。对于文件系统驱动来说,TopLevelIrp的具体值是由文件系统自己来解释的,所以针对 FSRTL_FSP_TOP_LEVEL_IRP,不同的文件驱动对TopLevelIrp的处理也不尽相同:

文件系统驱动 TopLevelIrp所指向的结构
FastFat nt!_IRP
Cdfs cdfs!_THREAD_CONTEXT
Ntfs ntfs!_TOP_LEVEL_CONTEXT

案例分析

TopLevelIrp的设置是一项精巧的手艺活,稍有不慎就会阴沟里翻船,下面就介绍两个开发中曾遇到的案例:

NTFS:Valid Data Length的设置

Ntfs文件系统驱动在其内部维护着每个数据流的Valid Data Length(VDL,有效数据长度),且VDL是管理于Ntfs的私有结构中的。VDL的更新一般是在cached i/o过程中做的。但实际操作中我们有个特殊的需求:要截获所有的cached i/o请求,只会通过paging i/o请求和Ntfs文件系统驱动交与,这样操作的后果就导致VDL不能被正常更新,虽然数据已经写到了磁盘上但是当试图读回数据的时候,Ntfs会根据VDL对数据进行清零化处理。

最后的解决办法也是一个不得已的投巧的办法:将我们的paging writing 请求模拟成mmap i/o (memory mapping i/o),即映射文件的数据刷写方式。mmap i/o操作本身就是个top level操作,并且也是仅有的top level paging i/o的情形。所以针对mmap i/o,Ntfs会更新VDL,这也是唯一的可以更新VDL的机会。

CDFS: 换了光盘但不能正确加载

这个问题比较妖怪,本来以为是文件系统过滤驱动的问题,但仔细分析过滤驱动又没有发现可疑点,最后经过代码对比及对WDK中cdfs的动态调试才定位到问题症结:原来是top level irp的问题。

我们都知道文件系统对于可移动设备及可移除介质设备都会有个检验(即verify)操作,但cdfs的verify操作会检测当前的TopLevelIrp状态,并根据这个状态来决定是否继续verify操作。当我们设置了TopLevelIrp之后,cdfs会认为它不在最高的调用栈上,故直接跳过了verify操作,最终就导致了换光盘后新光盘无法被正常识别的问题。

参考链接

  1. TopLevelIrp是如何设置的 - blog: Oops Kernel
  2. More on Maintaining Valid Data Length - OSR

<本文用时约5小时>

Continue reading » · Rating: · Written on: 02-28-17 · 1 Comment »

AES标准及Rijndael算法解析

AES简介

AES, Advanced Encryption Standard,其实是一套标准:FIPS 197,而我们所说的AES算法其实是Rijndael算法。

NIST (National INstitute of Standards and Technology) 在1997年9月12日公开征集更高效更安全的替代DES加密算法,第一轮共有15种算法入选,其中5种算法入围了决赛,分别是MARS,RC6,Rijndael,Serpent和Twofish。又经过3年的验证、评测及公众讨论之后Rijndael算法最终入选。

思维导图

Rijndael算法

Rijndael算法是由比利时学者Joan Daemen和Vincent Rijmen所提出的,算法的名字就由两位作者的名字组合而成。Rijndael的优势在于集安全性、性能、效率、可实现性及灵活性与一体。

Joan Daemen和Vincent Rijmen

Joan Daemen & Vincent RijmenJoan DaemenVincent Rijmen

AES vs Rijndael

Rijndael算法支持多种分组及密钥长度,介于128-256之间所有32的倍数均可,最小支持128位,最大256位,共25种组合。而AES标准支持的分组大小固定为128位,密钥长度有3种选择:128位、192位及256位。

加密实例

下面针对16字节的简单明文字串“0011223344....eeff”,分别用AES-128/AES-192及AES-256进行加密运算:

AES-128

密钥选用16字节长的简单字串:“00010203....0e0f” 来,上面的明文经过加密变换后成为"69c4e0d8....6089"。

plain :  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
key   :  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
cypher:  69 c4 e0 d8 6a 7b 04 30 d8 cd b7 80 70 b4 c5 5a

AES-192

plain :  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
key   :  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d .. .. .. 17
cypher:  dd a9 7c a4 86 4c df e0 6e af 70 a0 ec 0d 71 91

AES-256

plain :  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
key   :  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d .. .. .. 17 .. .. .. 1f
cypher:  8e a2 b7 ca 51 67 45 bf ea fc 49 90 4b 49 60 89

总体结构

Rijndael算法是基于代换-置换网络(SPN,Substitution-permutation network)的迭代算法。明文数据经过多轮次的转换后方能生成密文,每个轮次的转换操作由轮函数定义。轮函数任务就是根据密钥编排序列(即轮密码)对数据进行不同的代换及置换等操作。

AES & Rijndael Architecture

图左侧为轮函数的流程,主要包含4种主要运算操作:字节代换(SubByte)、行移位(ShiftRow)、列混合(MixColumn)、轮密钥加(AddRoundKey)。图右侧为密钥编排方案,在Rijndael中称为密钥扩展算法(KeyExpansion)。

AES标准算法将128位的明文,以特定次序生成一个4x4的矩阵(每个元素是一个字节,8位),即初始状态(state),经由轮函数的迭代转换之后又将作为下一轮迭代的输入继续参与运算直到迭代结束。

Rijndael算法支持大于128位的明文分组,所以需要列数更多的矩阵来描述。Rijndael轮函数的运算是在特殊定义的有限域GF(256)上进行的。有限域(Finite Field)又名伽罗瓦域(Galois field),简单言之就是一个满足特定规则的集合,集合中的元素可以进行加减乘除运算,且运算结果也是属于此集合。更详细有有关Rijndael算法的数学描述,可以参阅本文最后所罗列的参考资料,在此不做熬述。

轮函数

我们已经得知轮函数主要包含4种运算,但不同的运算轮所做的具体运的算组合并不相同。主要区别是初始轮(Round: 0)和最后一轮(Round: Nr),所有中间轮的运算都是相同的,会依次进行4种运算,即:

  1. 字节代换(SubByte)
  2. 行移位(ShiftRow)
  3. 列混合(MixColumn)
  4. 轮密钥加(AddRoundKey)

根据Rinjdael算法的定义,加密轮数会针对不同的分组及不同的密钥长度选择不同的数值:

AES 迭代轮

AES标准只支持128位分组(Nb = 4)的情况。

轮函数的实现代码如下,直接实现在加密函数内部循环中:

int aes_encrypt(AES_CYPHER_T mode, uint8_t *data, int len, uint8_t *key)
{
    uint8_t w[4 * 4 * 15] = {0}; /* round key */
    uint8_t s[4 * 4] = {0}; /* state */

    int nr, i, j;

    /* key expansion */
    aes_key_expansion(mode, key, w);

    /* start data cypher loop over input buffer */
    for (i = 0; i < len; i += 4 * g_aes_nb[mode]) {

        /* init state from user buffer (plaintext) */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            s[j] = data[i + j];

        /* start AES cypher loop over all AES rounds */
        for (nr = 0; nr <= g_aes_rounds[mode]; nr++) {

            if (nr > 0) {

                /* do SubBytes */
                aes_sub_bytes(mode, s);

                /* do ShiftRows */
                aes_shift_rows(mode, s);

                if (nr < g_aes_rounds[mode]) {
                    /* do MixColumns */
                    aes_mix_columns(mode, s);
                }
            }

            /* do AddRoundKey */
            aes_add_round_key(mode, s, w, nr);
        }

        /* save state (cypher) to user buffer */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            data[i + j] = s[j];
    }

    return 0;
}

动画演示加密过程

Enrique Zabala创建了一个AES-128加密算法的动画演示,清楚、直观地介绍了轮函数执行的过程。点击可直接观看

轮函数拆解:字节代换(Substitute Bytes)

AES:字节替换

字节代换(SubBytes)是对state矩阵中的每一个独立元素于置换盒 (Substitution-box,S盒)中进行查找并以此替换输入状态的操作。字节代换是可逆的非线性变换,也是AES运算组中唯一的非线性变换。字节代换逆操作也是通过逆向置换盒的查找及替换来完成的。

S盒是事先设计好的16x16的查询表,即256个元素。其设计不是随意的,要根据设计原则严格计算求得,不然无法保证算法的安全性。既然是S盒是计算得来,所以字节代换的操作完全可以通过计算来完成,不过通过S盒查表操作更方便快捷,图中所示就是通过S盒查找对应元素进行的替换操作。

AES S-BOX

void aes_sub_bytes(AES_CYPHER_T mode, uint8_t *state)
{
    int i, j;

    for (i = 0; i < g_aes_nb[mode]; i++) {
        for (j = 0; j < 4; j++) {
            state[i * 4 + j] = aes_sub_sbox(state[i * 4 + j]);
        }
    }
}

实例说明:

   input:  00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0
     sub:  63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c

轮函数拆解:行移位(Shift Rows)

AES: 行移位

行移位主要目的是实现字节在每一行的扩散,属于线性变换。

void aes_shift_rows(AES_CYPHER_T mode, uint8_t *state)
{
    uint8_t *s = (uint8_t *)state;
    int i, j, r;

    for (i = 1; i < g_aes_nb[mode]; i++) {
        for (j = 0; j < i; j++) {
            uint8_t tmp = s[i];
            for (r = 0; r < g_aes_nb[mode]; r++) {
                s[i + r * 4] = s[i + (r + 1) * 4];
            }
            s[i + (g_aes_nb[mode] - 1) * 4] = tmp;
        }
    }
}

实例说明:

     sub:  63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
   shift:  63 53 e0 8c 09 60 e1 04 cd 70 b7 51 ba ca d0 e7

轮函数拆解:列混合(Mix Columns)

AES: 列混合

列混合是通过将state矩阵与常矩阵C相乘以达成在列上的扩散,属于代替变换。列混合是Rijndael算法中最复杂的一步,其实质是在有限域GF(256)上的多项式乘法运算。

void aes_mix_columns(AES_CYPHER_T mode, uint8_t *state)
{
    uint8_t y[16] = { 2, 3, 1, 1,  1, 2, 3, 1,  1, 1, 2, 3,  3, 1, 1, 2};
    uint8_t s[4];
    int i, j, r;

    for (i = 0; i < g_aes_nb[mode]; i++) {
        for (r = 0; r < 4; r++) {
            s[r] = 0;
            for (j = 0; j < 4; j++) {
                s[r] = s[r] ^ aes_mul(state[i * 4 + j], y[r * 4 + j]);
            }
        }
        for (r = 0; r < 4; r++) {
            state[i * 4 + r] = s[r];
        }
    }
}

实例说明:

   shift:  63 53 e0 8c 09 60 e1 04 cd 70 b7 51 ba ca d0 e7
     mix:  5f 72 64 15 57 f5 bc 92 f7 be 3b 29 1d b9 f9 1a

轮函数拆解:轮密钥加(Add Round Key)

AES & Rijndael Architecture

密钥加是将轮密钥简单地与状态进行逐比特异或。实现代码如下:

void aes_add_round_key(AES_CYPHER_T mode, uint8_t *state,
                       uint8_t *round, int nr)
{
    uint32_t *w = (uint32_t *)round;
    uint32_t *s = (uint32_t *)state;
    int i;

    for (i = 0; i < g_aes_nb[mode]; i++) {
        s[i] ^= w[nr * g_aes_nb[mode] + i];
    }
}

实例说明:

     mix:  5f 72 64 15 57 f5 bc 92 f7 be 3b 29 1d b9 f9 1a
   round:  d6 aa 74 fd d2 af 72 fa da a6 78 f1 d6 ab 76 fe
   state:  89 d8 10 e8 85 5a ce 68 2d 18 43 d8 cb 12 8f e4

密钥扩展算法(Key Expansion)

密钥扩展算法是Rijndael的密钥编排实现算法,其目的是根据种子密钥(用户密钥)生成多组轮密钥。轮密钥为多组128位密钥,对应不同密钥长度,分别是11,13,15组。

AES: 密钥扩展

实现代码:

/*
 * nr: number of rounds
 * nb: number of columns comprising the state, nb = 4 dwords (16 bytes)
 * nk: number of 32-bit words comprising cipher key, nk = 4, 6, 8 (KeyLength/(4*8))
 */

void aes_key_expansion(AES_CYPHER_T mode, uint8_t *key, uint8_t *round)
{
    uint32_t *w = (uint32_t *)round;
    uint32_t  t;
    int      i = 0;

    do {
        w[i] = *((uint32_t *)&key[i * 4 + 0]);
    } while (++i < g_aes_nk[mode]);

    do {
        if ((i % g_aes_nk[mode]) == 0) {
            t = aes_rot_dword(w[i - 1]);
            t = aes_sub_dword(t);
            t = t ^ aes_swap_dword(g_aes_rcon[i/g_aes_nk[mode] - 1]);
        } else if (g_aes_nk[mode] > 6 && (i % g_aes_nk[mode]) == 4) {
            t = aes_sub_dword(w[i - 1]);
        } else {
            t = w[i - 1];
        }
        w[i] = w[i - g_aes_nk[mode]] ^ t;

    } while (++i < g_aes_nb[mode] * (g_aes_rounds[mode] + 1));

    /* key can be discarded (or zeroed) from memory */
}

以AES-128为例,从128位种子密钥生成11组轮密钥(每组128位):

Input:
    key :  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
Key Expansion:
    00:  rs: 00010203
    01:  rs: 04050607
    02:  rs: 08090a0b
    03:  rs: 0c0d0e0f
    04:  rot: 0d0e0f0c sub: d7ab76fe rcon: 01000000 xor: fe76abd6 rs: d6aa74fd
    05:  equ: d6aa74fd rs: d2af72fa
    06:  equ: d2af72fa rs: daa678f1
    07:  equ: daa678f1 rs: d6ab76fe
    08:  rot: ab76fed6 sub: 6238bbf6 rcon: 02000000 xor: f6bb3860 rs: b692cf0b
    09:  equ: b692cf0b rs: 643dbdf1
    10:  equ: 643dbdf1 rs: be9bc500
    11:  equ: be9bc500 rs: 6830b3fe
    12:  rot: 30b3fe68 sub: 046dbb45 rcon: 04000000 xor: 45bb6d00 rs: b6ff744e
    13:  equ: b6ff744e rs: d2c2c9bf
    14:  equ: d2c2c9bf rs: 6c590cbf
    15:  equ: 6c590cbf rs: 0469bf41
    16:  rot: 69bf4104 sub: f90883f2 rcon: 08000000 xor: f28308f1 rs: 47f7f7bc
    17:  equ: 47f7f7bc rs: 95353e03
    18:  equ: 95353e03 rs: f96c32bc
    19:  equ: f96c32bc rs: fd058dfd
    20:  rot: 058dfdfd sub: 6b5d5454 rcon: 10000000 xor: 54545d7b rs: 3caaa3e8
    21:  equ: 3caaa3e8 rs: a99f9deb
    22:  equ: a99f9deb rs: 50f3af57
    23:  equ: 50f3af57 rs: adf622aa
    24:  rot: f622aaad sub: 4293ac95 rcon: 20000000 xor: 95ac9362 rs: 5e390f7d
    25:  equ: 5e390f7d rs: f7a69296
    26:  equ: f7a69296 rs: a7553dc1
    27:  equ: a7553dc1 rs: 0aa31f6b
    28:  rot: a31f6b0a sub: 0ac07f67 rcon: 40000000 xor: 677fc04a rs: 14f9701a
    29:  equ: 14f9701a rs: e35fe28c
    30:  equ: e35fe28c rs: 440adf4d
    31:  equ: 440adf4d rs: 4ea9c026
    32:  rot: a9c0264e sub: d3baf72f rcon: 80000000 xor: 2ff7ba53 rs: 47438735
    33:  equ: 47438735 rs: a41c65b9
    34:  equ: a41c65b9 rs: e016baf4
    35:  equ: e016baf4 rs: aebf7ad2
    36:  rot: bf7ad2ae sub: 08dab5e4 rcon: 1b000000 xor: e4b5da13 rs: 549932d1
    37:  equ: 549932d1 rs: f0855768
    38:  equ: f0855768 rs: 1093ed9c
    39:  equ: 1093ed9c rs: be2c974e
    40:  rot: 2c974ebe sub: 71882fae rcon: 36000000 xor: ae2f8847 rs: 13111d7f
    41:  equ: 13111d7f rs: e3944a17
    42:  equ: e3944a17 rs: f307a78b
    43:  equ: f307a78b rs: 4d2b30c5

加密过程实例

Encrypting block ...
 Round 0:
   input:  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
   round:  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
   state:  00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0
 Round 1:
   input:  00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0
     sub:  63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
   shift:  63 53 e0 8c 09 60 e1 04 cd 70 b7 51 ba ca d0 e7
     mix:  5f 72 64 15 57 f5 bc 92 f7 be 3b 29 1d b9 f9 1a
   round:  d6 aa 74 fd d2 af 72 fa da a6 78 f1 d6 ab 76 fe
   state:  89 d8 10 e8 85 5a ce 68 2d 18 43 d8 cb 12 8f e4
 Round 2:
   input:  89 d8 10 e8 85 5a ce 68 2d 18 43 d8 cb 12 8f e4
     sub:  a7 61 ca 9b 97 be 8b 45 d8 ad 1a 61 1f c9 73 69
   shift:  a7 be 1a 69 97 ad 73 9b d8 c9 ca 45 1f 61 8b 61
     mix:  ff 87 96 84 31 d8 6a 51 64 51 51 fa 77 3a d0 09
   round:  b6 92 cf 0b 64 3d bd f1 be 9b c5 00 68 30 b3 fe
   state:  49 15 59 8f 55 e5 d7 a0 da ca 94 fa 1f 0a 63 f7
 Round 3:
   input:  49 15 59 8f 55 e5 d7 a0 da ca 94 fa 1f 0a 63 f7
     sub:  3b 59 cb 73 fc d9 0e e0 57 74 22 2d c0 67 fb 68
   shift:  3b d9 22 68 fc 74 fb 73 57 67 cb e0 c0 59 0e 2d
     mix:  4c 9c 1e 66 f7 71 f0 76 2c 3f 86 8e 53 4d f2 56
   round:  b6 ff 74 4e d2 c2 c9 bf 6c 59 0c bf 04 69 bf 41
   state:  fa 63 6a 28 25 b3 39 c9 40 66 8a 31 57 24 4d 17
 Round 4:
   input:  fa 63 6a 28 25 b3 39 c9 40 66 8a 31 57 24 4d 17
     sub:  2d fb 02 34 3f 6d 12 dd 09 33 7e c7 5b 36 e3 f0
   shift:  2d 6d 7e f0 3f 33 e3 34 09 36 02 dd 5b fb 12 c7
     mix:  63 85 b7 9f fc 53 8d f9 97 be 47 8e 75 47 d6 91
   round:  47 f7 f7 bc 95 35 3e 03 f9 6c 32 bc fd 05 8d fd
   state:  24 72 40 23 69 66 b3 fa 6e d2 75 32 88 42 5b 6c
 Round 5:
   input:  24 72 40 23 69 66 b3 fa 6e d2 75 32 88 42 5b 6c
     sub:  36 40 09 26 f9 33 6d 2d 9f b5 9d 23 c4 2c 39 50
   shift:  36 33 9d 50 f9 b5 39 26 9f 2c 09 2d c4 40 6d 23
     mix:  f4 bc d4 54 32 e5 54 d0 75 f1 d6 c5 1d d0 3b 3c
   round:  3c aa a3 e8 a9 9f 9d eb 50 f3 af 57 ad f6 22 aa
   state:  c8 16 77 bc 9b 7a c9 3b 25 02 79 92 b0 26 19 96
 Round 6:
   input:  c8 16 77 bc 9b 7a c9 3b 25 02 79 92 b0 26 19 96
     sub:  e8 47 f5 65 14 da dd e2 3f 77 b6 4f e7 f7 d4 90
   shift:  e8 da b6 90 14 77 d4 65 3f f7 f5 e2 e7 47 dd 4f
     mix:  98 16 ee 74 00 f8 7f 55 6b 2c 04 9c 8e 5a d0 36
   round:  5e 39 0f 7d f7 a6 92 96 a7 55 3d c1 0a a3 1f 6b
   state:  c6 2f e1 09 f7 5e ed c3 cc 79 39 5d 84 f9 cf 5d
 Round 7:
   input:  c6 2f e1 09 f7 5e ed c3 cc 79 39 5d 84 f9 cf 5d
     sub:  b4 15 f8 01 68 58 55 2e 4b b6 12 4c 5f 99 8a 4c
   shift:  b4 58 12 4c 68 b6 8a 01 4b 99 f8 2e 5f 15 55 4c
     mix:  c5 7e 1c 15 9a 9b d2 86 f0 5f 4b e0 98 c6 34 39
   round:  14 f9 70 1a e3 5f e2 8c 44 0a df 4d 4e a9 c0 26
   state:  d1 87 6c 0f 79 c4 30 0a b4 55 94 ad d6 6f f4 1f
 Round 8:
   input:  d1 87 6c 0f 79 c4 30 0a b4 55 94 ad d6 6f f4 1f
     sub:  3e 17 50 76 b6 1c 04 67 8d fc 22 95 f6 a8 bf c0
   shift:  3e 1c 22 c0 b6 fc bf 76 8d a8 50 67 f6 17 04 95
     mix:  ba a0 3d e7 a1 f9 b5 6e d5 51 2c ba 5f 41 4d 23
   round:  47 43 87 35 a4 1c 65 b9 e0 16 ba f4 ae bf 7a d2
   state:  fd e3 ba d2 05 e5 d0 d7 35 47 96 4e f1 fe 37 f1
 Round 9:
   input:  fd e3 ba d2 05 e5 d0 d7 35 47 96 4e f1 fe 37 f1
     sub:  54 11 f4 b5 6b d9 70 0e 96 a0 90 2f a1 bb 9a a1
   shift:  54 d9 90 a1 6b a0 9a b5 96 bb f4 0e a1 11 70 2f
     mix:  e9 f7 4e ec 02 30 20 f6 1b f2 cc f2 35 3c 21 c7
   round:  54 99 32 d1 f0 85 57 68 10 93 ed 9c be 2c 97 4e
   state:  bd 6e 7c 3d f2 b5 77 9e 0b 61 21 6e 8b 10 b6 89
 Round 10:
   input:  bd 6e 7c 3d f2 b5 77 9e 0b 61 21 6e 8b 10 b6 89
     sub:  7a 9f 10 27 89 d5 f5 0b 2b ef fd 9f 3d ca 4e a7
   shift:  7a d5 fd a7 89 ef 4e 27 2b ca 10 0b 3d 9f f5 9f
   round:  13 11 1d 7f e3 94 4a 17 f3 07 a7 8b 4d 2b 30 c5
   state:  69 c4 e0 d8 6a 7b 04 30 d8 cd b7 80 70 b4 c5 5a
Output:
  cypher:  69 c4 e0 d8 6a 7b 04 30 d8 cd b7 80 70 b4 c5 5a

解密轮函数

对Rijndael算法来说解密过程就是加密过程的逆向过程,其解密轮函数实现如下:

int aes_decrypt(AES_CYPHER_T mode, uint8_t *data, int len, uint8_t *key)
{
    uint8_t w[4 * 4 * 15] = {0}; /* round key */
    uint8_t s[4 * 4] = {0}; /* state */

    int nr, i, j;

    /* key expansion */
    aes_key_expansion(mode, key, w);

    /* start data cypher loop over input buffer */
    for (i = 0; i < len; i += 4 * g_aes_nb[mode]) {

        /* init state from user buffer (cyphertext) */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            s[j] = data[i + j];

        /* start AES cypher loop over all AES rounds */
        for (nr = g_aes_rounds[mode]; nr >= 0; nr--) {

            /* do AddRoundKey */
            aes_add_round_key(mode, s, w, nr);

            if (nr > 0) {
                if (nr < g_aes_rounds[mode]) {
                    /* do MixColumns */
                    inv_mix_columns(mode, s);
                }

                /* do ShiftRows */
                inv_shift_rows(mode, s);

                /* do SubBytes */
                inv_sub_bytes(mode, s);
            }
        }

        /* save state (cypher) to user buffer */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            data[i + j] = s[j];
    }

    return 0;
}

解密过程实例

Decrypting block ...
 Round 10:
   input:  69 c4 e0 d8 6a 7b 04 30 d8 cd b7 80 70 b4 c5 5a
   round:  13 11 1d 7f e3 94 4a 17 f3 07 a7 8b 4d 2b 30 c5
   shift:  7a d5 fd a7 89 ef 4e 27 2b ca 10 0b 3d 9f f5 9f
     sub:  7a 9f 10 27 89 d5 f5 0b 2b ef fd 9f 3d ca 4e a7
   state:  bd 6e 7c 3d f2 b5 77 9e 0b 61 21 6e 8b 10 b6 89
 Round 9:
   input:  bd 6e 7c 3d f2 b5 77 9e 0b 61 21 6e 8b 10 b6 89
   round:  54 99 32 d1 f0 85 57 68 10 93 ed 9c be 2c 97 4e
     mix:  e9 f7 4e ec 02 30 20 f6 1b f2 cc f2 35 3c 21 c7
   shift:  54 d9 90 a1 6b a0 9a b5 96 bb f4 0e a1 11 70 2f
     sub:  54 11 f4 b5 6b d9 70 0e 96 a0 90 2f a1 bb 9a a1
   state:  fd e3 ba d2 05 e5 d0 d7 35 47 96 4e f1 fe 37 f1
 Round 8:
   input:  fd e3 ba d2 05 e5 d0 d7 35 47 96 4e f1 fe 37 f1
   round:  47 43 87 35 a4 1c 65 b9 e0 16 ba f4 ae bf 7a d2
     mix:  ba a0 3d e7 a1 f9 b5 6e d5 51 2c ba 5f 41 4d 23
   shift:  3e 1c 22 c0 b6 fc bf 76 8d a8 50 67 f6 17 04 95
     sub:  3e 17 50 76 b6 1c 04 67 8d fc 22 95 f6 a8 bf c0
   state:  d1 87 6c 0f 79 c4 30 0a b4 55 94 ad d6 6f f4 1f
 Round 7:
   input:  d1 87 6c 0f 79 c4 30 0a b4 55 94 ad d6 6f f4 1f
   round:  14 f9 70 1a e3 5f e2 8c 44 0a df 4d 4e a9 c0 26
     mix:  c5 7e 1c 15 9a 9b d2 86 f0 5f 4b e0 98 c6 34 39
   shift:  b4 58 12 4c 68 b6 8a 01 4b 99 f8 2e 5f 15 55 4c
     sub:  b4 15 f8 01 68 58 55 2e 4b b6 12 4c 5f 99 8a 4c
   state:  c6 2f e1 09 f7 5e ed c3 cc 79 39 5d 84 f9 cf 5d
 Round 6:
   input:  c6 2f e1 09 f7 5e ed c3 cc 79 39 5d 84 f9 cf 5d
   round:  5e 39 0f 7d f7 a6 92 96 a7 55 3d c1 0a a3 1f 6b
     mix:  98 16 ee 74 00 f8 7f 55 6b 2c 04 9c 8e 5a d0 36
   shift:  e8 da b6 90 14 77 d4 65 3f f7 f5 e2 e7 47 dd 4f
     sub:  e8 47 f5 65 14 da dd e2 3f 77 b6 4f e7 f7 d4 90
   state:  c8 16 77 bc 9b 7a c9 3b 25 02 79 92 b0 26 19 96
 Round 5:
   input:  c8 16 77 bc 9b 7a c9 3b 25 02 79 92 b0 26 19 96
   round:  3c aa a3 e8 a9 9f 9d eb 50 f3 af 57 ad f6 22 aa
     mix:  f4 bc d4 54 32 e5 54 d0 75 f1 d6 c5 1d d0 3b 3c
   shift:  36 33 9d 50 f9 b5 39 26 9f 2c 09 2d c4 40 6d 23
     sub:  36 40 09 26 f9 33 6d 2d 9f b5 9d 23 c4 2c 39 50
   state:  24 72 40 23 69 66 b3 fa 6e d2 75 32 88 42 5b 6c
 Round 4:
   input:  24 72 40 23 69 66 b3 fa 6e d2 75 32 88 42 5b 6c
   round:  47 f7 f7 bc 95 35 3e 03 f9 6c 32 bc fd 05 8d fd
     mix:  63 85 b7 9f fc 53 8d f9 97 be 47 8e 75 47 d6 91
   shift:  2d 6d 7e f0 3f 33 e3 34 09 36 02 dd 5b fb 12 c7
     sub:  2d fb 02 34 3f 6d 12 dd 09 33 7e c7 5b 36 e3 f0
   state:  fa 63 6a 28 25 b3 39 c9 40 66 8a 31 57 24 4d 17
 Round 3:
   input:  fa 63 6a 28 25 b3 39 c9 40 66 8a 31 57 24 4d 17
   round:  b6 ff 74 4e d2 c2 c9 bf 6c 59 0c bf 04 69 bf 41
     mix:  4c 9c 1e 66 f7 71 f0 76 2c 3f 86 8e 53 4d f2 56
   shift:  3b d9 22 68 fc 74 fb 73 57 67 cb e0 c0 59 0e 2d
     sub:  3b 59 cb 73 fc d9 0e e0 57 74 22 2d c0 67 fb 68
   state:  49 15 59 8f 55 e5 d7 a0 da ca 94 fa 1f 0a 63 f7
 Round 2:
   input:  49 15 59 8f 55 e5 d7 a0 da ca 94 fa 1f 0a 63 f7
   round:  b6 92 cf 0b 64 3d bd f1 be 9b c5 00 68 30 b3 fe
     mix:  ff 87 96 84 31 d8 6a 51 64 51 51 fa 77 3a d0 09
   shift:  a7 be 1a 69 97 ad 73 9b d8 c9 ca 45 1f 61 8b 61
     sub:  a7 61 ca 9b 97 be 8b 45 d8 ad 1a 61 1f c9 73 69
   state:  89 d8 10 e8 85 5a ce 68 2d 18 43 d8 cb 12 8f e4
 Round 1:
   input:  89 d8 10 e8 85 5a ce 68 2d 18 43 d8 cb 12 8f e4
   round:  d6 aa 74 fd d2 af 72 fa da a6 78 f1 d6 ab 76 fe
     mix:  5f 72 64 15 57 f5 bc 92 f7 be 3b 29 1d b9 f9 1a
   shift:  63 53 e0 8c 09 60 e1 04 cd 70 b7 51 ba ca d0 e7
     sub:  63 ca b7 04 09 53 d0 51 cd 60 e0 e7 ba 70 e1 8c
   state:  00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0
 Round 0:
   input:  00 10 20 30 40 50 60 70 80 90 a0 b0 c0 d0 e0 f0
   round:  00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
   state:  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff
Output:
   plain:  00 11 22 33 44 55 66 77 88 99 aa bb cc dd ee ff

算法设计思想

加密算法的一般设计准则

  • 混淆 (Confusion) 最大限度地复杂化密文、明文与密钥之间的关系,通常用非线性变换算法达到最大化的混淆。
  • 扩散 (Diffusion) 明文或密钥每变动一位将最大化地影响密文中的位数,通常采用线性变换算法达到最大化的扩散。

AES评判要求

NIST在征集算法的时候就提出了几项硬性要求:

  • 分组加密算法:支持128位分组大小,128/192/256位密钥
  • 安全性不低于3DES,但实施与执行要比3DES的更高效
  • 优化过的ANSI C的实现代码
  • KAT(Known-Answer tests)及MCT(Monte Carlo Tests)测试及验证
  • 软件及硬件实现的便捷
  • 可抵御已知攻击

Rijndael设计思想

  1. 安全性(Security) 算法足够强,抗攻击
  2. 经济性(Efficiency) 算法运算效率高
  3. 密钥捷变(Key Agility) 更改密钥所引入的损失尽量小,即最小消耗的密钥扩展算法
  4. 适应性 (Versatility) 适用于不同的CPU架构,软件或硬件平台的实现
  5. 设计简单(Simplicity) 轮函数的设计精简,只是多轮迭代

S盒设计

S盒是由一个有限域GF(256)上的乘法求逆并串联线性仿射变换所构造出来的,不是一个随意构造的简单查询表。因其运算复杂,众多的AES 软件及硬件实现直接使用了查找表(LUP, Look-up table),但查询表的方式并不适合所有场景,针对特定的硬件最小化面积设计需求,则要采用优化的组合逻辑以得到同价的S盒替换。

工作模式

分组加密算法是按分组大小来进行加解密操作的,如DES算法的分组是64位,而AES是128位,但实际明文的长度一般要远大于分组大小,这样的情况如何处理呢?

这正是"mode of operation"即工作模式要解决的问题:明文数据流怎样按分组大小切分,数据不对齐的情况怎么处理等等。

早在1981年,DES算法公布之后,NIST在标准文献FIPS 81中公布了4种工作模式:

  • 电子密码本:Electronic Code Book Mode (ECB)

  • 密码分组链接:Cipher Block Chaining Mode (CBC)

  • 密文反馈:Cipher Feedback Mode (CFB)

  • 输出反馈:Output Feedback Mode (OFB)

2001年又针对AES加入了新的工作模式:

  • 计数器模式:Counter Mode (CTR)

后来又陆续引入其它新的工作模式。在此仅介绍几种常用的:

ECB:电子密码本模式

ECB模式只是将明文按分组大小切分,然后用同样的密钥正常加密切分好的明文分组。

AES: 电子密码本模式

ECB的理想应用场景是短数据(如加密密钥)的加密。此模式的问题是无法隐藏原明文数据的模式,因为同样的明文分组加密得到的密文也是一样的。

举例来说明,下图为明文图片: AES: Leaf明文

经ECB模式加密的图片: AES: Leaf ECB加密 图中也正好验证了AES的扩散效果:作为局部图案的叶子,其红颜色在加密后扩散到了整张图片上。

经CBC模式加密的图片: AES: Leaf CBC加密

CBC:密码分组链接模式

此模式是1976年由IBM所发明,引入了IV(初始化向量:Initialization Vector)的概念。IV是长度为分组大小的一组随机,通常情况下不用保密,不过在大多数情况下,针对同一密钥不应多次使用同一组IV。 CBC要求第一个分组的明文在加密运算前先与IV进行异或;从第二组开始,所有的明文先与前一分组加密后的密文进行异或。[区块链(blockchain)的鼻祖!]

AES: 密码分组链接模式

CBC模式相比ECB实现了更好的模式隐藏,但因为其将密文引入运算,加解密操作无法并行操作。同时引入的IV向量,还需要加、解密双方共同知晓方可。

实现代码:

int aes_encrypt_cbc(AES_CYPHER_T mode, uint8_t *data, int len,
                    uint8_t *key, uint8_t *iv)
{
    uint8_t w[4 * 4 * 15] = {0}; /* round key */
    uint8_t s[4 * 4] = {0}; /* state */
    uint8_t v[4 * 4] = {0}; /* iv */

    int nr, i, j;

    /* key expansion */
    aes_key_expansion(mode, key, w);
    memcpy(v, iv, sizeof(v));

    /* start data cypher loop over input buffer */
    for (i = 0; i < len; i += 4 * g_aes_nb[mode]) {
        /* init state from user buffer (plaintext) */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            s[j] = data[i + j] ^ v[j];

        /* start AES cypher loop over all AES rounds */
        for (nr = 0; nr <= g_aes_rounds[mode]; nr++) {

            if (nr > 0) {

                /* do SubBytes */
                aes_sub_bytes(mode, s);

                /* do ShiftRows */
                aes_shift_rows(mode, s);

                if (nr < g_aes_rounds[mode]) {
                    /* do MixColumns */
                    aes_mix_columns(mode, s);
                }
            }

            /* do AddRoundKey */
            aes_add_round_key(mode, s, w, nr);
        }

        /* save state (cypher) to user buffer */
        for (j = 0; j < 4 * g_aes_nb[mode]; j++)
            data[i + j] = v[j] = s[j];
    }

    return 0;
}

CFB:密文反馈模式

与CBC模式类似,但不同的地方在于,CFB模式先生成密码流字典,然后用密码字典与明文进行异或操作并最终生成密文。后一分组的密码字典的生成需要前一分组的密文参与运算。

AES: 密文反馈模式

CFB模式是用分组算法实现流算法,明文数据不需要按分组大小对齐。

OFB:输出反馈模式

OFB模式与CFB模式不同的地方是:生成字典的时候会采用明文参与运算,CFB采用的是密文。

AES: 输出反馈模式

CTR:计数器模式模式

CTR模式同样会产生流密码字典,但同是会引入一个计数,以保证任意长时间均不会产生重复输出。

AES: 计数器模式

CTR模式只需要实现加密算法以生成字典,明文数据与之异或后得到密文,反之便是解密过程。CTR模式可以采用并行算法处理以提升吞量,另外加密数据块的访问可以是随机的,与前后上下文无关。

CCM:Counter with CBC-MAC

CCM模式,全称是Counter with Cipher Block Chaining-Message Authentication Code,是CTR工作模式和CMAC认证算法的组合体,可以同时数据加密和鉴别服务。

明文数据通过CTR模式加密成密文,然后在密文后面再附加上认证数据,所以最终的密文会比明文要长。具体的加密流程如下描述:先对明文数据认证并产生一个tag,在后续加密过程中使用此tag和IV生成校验值U。然后用CTR模式来加密原输入明文数据,在密文的后面附上校验码U。

GCM:伽罗瓦计数器模式

类型CCM模式,GCM模式是CTR和GHASH的组合,GHASH操作定义为密文结果与密钥以及消息长度在GF(2^128)域上相乘。GCM比CCM的优势是在于更高并行度及更好的性能。TLS 1.2标准使用的就是AES-GCM算法,并且Intel CPU提供了GHASH的硬件加速功能。

硬件加速

AES作为主导的加密标准,其应用越来越广泛,特别是针对网络数据的加密需求,越来越多的硬件都集成AES 128/192/256位算法及不同的工作模式的硬件加速的实现。

AES_NI: X86架构

Intel于2010发发布了支持AES加速的CPU,实现了高阶的AES加解密指令即AES_NI:AES New Instructions。AES_NI包含6指令:其中4条用于加解密,2条用于密钥扩展。根据AES_NI白皮书中所说,AES_NI可以带来2-3倍的性能提升。

Instruction Description
AESENC Perform one round of an AES encryption flow
AESENCLAST Perform the last round of an AES encryption flow
AESDEC Perform one round of an AES decryption flow
AESDECLAST Perform the last round of an AES decryption flow
AESKEYGENASSIST Assist in AES round key generation
AESIMC Assist in AES Inverse Mix Columns

目前OpenSSL,Linux's Crypto API以及Windows Cryptography API中均已加入对AES_NI的支持。

AES_NI: 测试

测试环境:

Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz 4 Cores with HyperThread (Enabled or Disabled)
Ubuntu 16.04 AMD64, OpenSSL 1.0.2g-fips  1 Mar 2016

测试方法:

关闭硬件加速1/2/4/8线程AES-256/128-CBC:
OPENSSL_ia32cap="~0x200000200000000" openssl speed -multi {1/2/4/8} -elapsed -evp {aes-256/128-cbc}

开启硬件加速1/2/4/8线程AES-256/128-CBC:
openssl speed -multi {1/2/4/8} -elapsed -evp {aes-256/128-cbc}

超线程的开户与关闭只能通过UEFI/BIOS来设置,测试命令同上。

AEAEAES: CPU加速性能对比

从图中可以得到如下结论:

  1. AES_NI加速可以提升性能1倍多,AESNI-128基本上都是AES-128的2.2倍左右。
  2. AES-128与AES-256的性能比基本在1.36左右(15/11,忽略密钥编排用时的情况下)
  3. 比较有趣的一点发现是,超线程所带来的影响比预想的要大得多。针对高并行的情形,在开启AES_NI时超线程可以带来接近1倍的性能提升;但在关闭AES_NI的情况下对性能提升的贡献要小的多。超线程虽然逻辑上让我们觉得一核变成了两核,其实质只是同一物理核上的队列管理机制,关闭AES_NI的情况下的测试数据基本验证了这一点。另一方面AES_NI硬件加速是基于物理核的,不可能是针对超线程的,所以超线程与AES_NI组合所带来的巨大的性能提升让人有些费解,比较可能的解释是AES_NI硬件加速引擎的潜力足够强大以至于一个物理核心不能完全发挥其效能,所以在超线程开启的情况下能有更好的表现。

ARM及其它体系

2011年发布的ARMv8-A处理器架构开始支持AES加速指令,其指令集与AES_NI不兼容但实现了类似的功能。除ARM外,SUN SPARC(T4, T5, M5以后)及IBM Power7+架构的CPU均已支持AES加速。

实现上的安全性考虑

内存与交换

程序如果将密钥存储在可交换内存页中,在内存吃紧的情况下有可能会交换出来并写入磁盘。如辅以代码逆向等,密钥很有可能会泄露。

应用层最好用mlock(Linux)或VirtualLock(Windows)来防止内存页被交换至磁盘。

但因为密钥在内存中,所以任何能访问内存的方式均有可能导致密钥的泄漏。曾流行的一种攻击是通过1394 DMA方式来访问目标机内存,Linux/Windows Login bypass,Windows bitlock等漏洞均由起引起。较新的CPU为硬件虚拟化所引入的IO MMU (Intel VT-d or AMD-Vi)可以有效地限制硬件对内存的访问权限。

传统攻击

AES从产生至今依然是最安全的加密算法,传统攻击手段依然无法撼动其安全性。虽然已有攻击手段显示可以将AES-256的暴力搜索次数从2^256次降至2^119次,但依然没有实际操作价值。

不过随着计算力的提升,特别是量子计算机的发展,AES将不再是安全的。不过可以肯定的是:一定会出现更安全的加密算法。

旁路攻击

旁路攻击(Side-channel attack, SCA)是指绕过对加密算法的正面对抗及分析,利用硬件实现加密算法的逻辑电路在运算中所泄露的信息,如执行时间、功耗、电磁辐射等,并结合统计理论来实现对密码系统攻击的手段。

旁路攻击条件

旁路攻击成功的必要条件:

  1. 在泄漏的物理信号与处理的数据之间建立关联
  2. 在信息泄漏模型中处理的数据与芯片中处理的数据之间建立关联

智能卡CPU的实现逻辑相对比较简单,并且都是单线程处理机制,因此可以很好的建立起密码-时序或密码-功耗之间的关联。

时序攻击

不同的数值及不同的运算所需时间是不同的,在算法(运算逻辑)固定的前提下完全可以根据运行时间反推出具体的操作数。举个简单的例子:

if (strelen(passwd) != sizeof(fixed_passwd))
  return 0;

for (i = 0; i < sizeof(fixed_passwd); i++)
  if (passwd[i] != fixed_passwd[i])
    return 0;

这段代码在密码的判断上就存在时序攻击的漏洞,如果第一个字符不匹配则直接退出,只有在当前字符匹配的情况下才会继续下一个字符的比较。

所以如果实际密码长度为8位且只能用字母及数字,则理论上暴力搜索次数为 (26 2 + 10) ^ 8。但因为算法的实现没有考虑到时序攻击,如果将执行时间加入考量,则搜索次数将降低至(26 2 + 10) * 8。

本文示例代码中aes_mul()的实现也有时序攻击的漏洞,并且实现效率也比较低,当然主要目的是为了算法演示。

功耗攻击

当信号发生0-1跳变时,需要电源对电容进行充电;而在其它三种情况(0-0, 1-1, 1-0)下则不会进行充电操作,因此可以很容易区分出前者来,这就是功耗攻击原理的简单解释。

功耗攻击一般分为简单功耗攻击(Simple Power Analysis,SPA),差分功耗攻击(Differential Power Analysis, DPA),高阶DPA等。SPA可以揭示出执行操作和能耗泄露间的关系,而DPA则能够揭示出处理数据和能耗泄露间的关系。

DPA利用不同数据对应的条件功耗分布的差异进行统计分析以找出数值与功耗的微弱关联性,并利用此关联性极大的降低密钥的搜索空间,进而完成高效且低成本的攻击。

上海交大的教授郁昱就通过功耗攻击成功破解了来自多家手机制造商以及服务供应商的SIM卡的密钥。更详细信息可见于他在Blackhat 2015年的演示稿: Cloning 3G/4G SIM Cards with a PC and an Oscilloscope: Lessons Learned in Physical Security

以色列特拉维夫大学的研究人员利用旁路攻击,成功从Android和iOS设备上窃取到用于加密比特币钱包、Apple Pay账号和其他高价值资产的密钥,详细请参阅论文: ECDSA Key Extraction from Mobile Devices via Nonintrusive Physical Side Channels

参考资料

  1. 密码学原理与实践(第二版),Douglas R. Stinson,冯登国
  2. AES Proposal: Rijndael by Joan Daemen and Vincent Rijmen
  3. FIPS 197: Announcing the AES
  4. Advanced Encryption Standard - Wikipedia
  5. The Design of Rijndael by Joan Daemen & Vincent Rijmen
  6. The Block Cipher Companion, L. Knudsen & M. Robshaw, 2011
  7. 加密芯片的旁道攻击防御对策研究(博士学位论文), 李海军, 2008
  8. 旁路之能量分析攻击总结
  9. AES算法介绍: 万天添,2015/3/23
  10. AES_NI - Wikipedia
  11. AES_NI v3.01 - Intel

相关代码

  1. https://github.com/matt-wu/AES/

<最早的手工计算AES-128的想法源于2016年底读过的一本书《How Software Works: The Magic Behind Encryption ...》,在阅读过程中发现AES一节中的数据全对不上,然后于17年初开始翻阅AES及Rijndael算法标准等资料,等看完所有文档后才发现此书对AES的介绍真是简化得没边了,后来又做了大量的延伸阅读,春节期间根据FIPS 197及《The Design of Rijndael》实现了AES 128/192/256 ECB/CBC的计算过程,之后开始本blog的书写,中间断断续续直至今日才完工,本文估计用时约40小时。学习从来不是容易的事!但越是不容易的事情做起来才更有乐趣!>

Continue reading » · Rating: · Written on: 02-12-17 · No Comments »

Windows内核开发陷阱 – NTSTATUS

STATUS_REPARSE不是“失败”

曾经在过滤驱动中想针对REPARSE的情况做特殊处理,实现代码如下:

if (NT_SUCCESS(status)) {
    /* file created */
} else if (STATUS_REPARSE == status) {
    /* to be repared  */
} else {
    ...
}

结果代码运行没达有预期效果,手工调试时才发现代码进入了NT_SUCCESS(status)分支。STATUS_REPARSE竟然表示是“成功”的!

这件事后才真正注意到status的问题,虽然在学习内核及驱动编程的时候书上都有相关介绍,但这些基础章节并没有引起重视就直接跳过了。但是像STATS_REPARSE这样的特例并不是少数,如STATUS_PENDING、STATUS_TIMEOUT等。

NTSTATUS的定义

再回顾一下NTSTATUS的定义: NTSTATUS是一个32位长的有符号整型数,即LONG型。其格式如下:

  3                   2                   1                   0
1 0|9|8|7 6 5 4 3 2 1 0 9 8 7 6|5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
---+-+-+-----------------------+-------------------------------
S  |C|N|    Facility           |               Code              
---------------------------------------------------------------

各部分的解释如下:

位数 注解
S 2 Severity: 分4个等级(Success, Informational, Warning, Error)
C 1 1:用户自定义的值 0:默认为系统定义(Microsoft)
N 1 保留位,始终为0值
Facility 12 错误类别或子系统的划分
Code 16 具体错误代码

Severity的4个等级的定义如下:

00 - Success
01 - Informational
10 - Warning
11 - Error

NT_XXXX宏分析

引用WDK代码(ntdef.h):

//
// Generic test for success on any status value (non-negative numbers
// indicate success).
//

#define NT_SUCCESS(Status) (((NTSTATUS)(Status)) >= 0)

//
// Generic test for information on any status value.
//

#define NT_INFORMATION(Status) ((((ULONG)(Status)) >> 30) == 1)

//
// Generic test for warning on any status value.
//

#define NT_WARNING(Status) ((((ULONG)(Status)) >> 30) == 2)

//
// Generic test for error on any status value.
//

#define NT_ERROR(Status) ((((ULONG)(Status)) >> 30) == 3)

由定义可以看出至少两点:

  1. NT_SUCCESS的定义和其它三者是有区别的,并不是根据Severity的值来判断的。NT_SUCCESS(status)其实包含了Severity == 0及Severity == 1的情形。

  2. NT_SUCCESS与NT_ERROR不是单纯的非黑即白的关系。新手常犯的错误就是主观上认为NT_SUCCESS()与!NT_ERROR(),或者NT_ERROR()与!NT_SUCCESS()是等价。

如果想确保一个irp确实是“成功”完成了,就要严格用STATUS_SUCCESS来判断,而不是NT_SUCCESS()。类似地,用NT_ERROR()可以保证代码的执行确实出现了错误,但是NT_WARNING()的情况即被漏掉了。

总之,必要的基本功始终是不可少的,像熟悉开发场景相关的返回值并弄懂这些返回值的确切含义等此类的苦活累活是必须要做且要做好的。

参考链接

  1. [MS-ERREF]: Windows Error Codes
  2. Windows Driver Kit (WDK)

<本文用时2小时,字体及表格调整花时较多。>

Continue reading » · Rating: · Written on: 01-19-17 · No Comments »

Windows内核开发陷阱: Nt vs Zw

在Windows平台上做过开发的人对Native API都不会陌生。但以Nt开头与以Zw开头的Native API到底有没有差别以及都有什么使用场景等一直以来都是让人感觉比较困扰的问题。另外内核态也有同样的一组Nt及Zw开头的内核支持函数,这两者间又是怎么一回事呢,这其中会有会有开发上有陷阱呢?!

我们先来解析用户层,然后研究下内核层其各自的实现:

用户层的Nt vs Zw

对用户层程序来说Nt与Zw开头函数实际上是一样的,只是同一个函数的两个名称而已。比如下面是对ntdll!NtCreateFile及ntdll!ZwCreateFile(Win7 X64)的反汇编:

1: kd> u ntdll!ZwCreateFile
ntdll!NtCreateFile:
00000000`77480400 4c8bd1          mov     r10,rcx
00000000`77480403 b852000000      mov     eax,52h
00000000`77480408 0f05            syscall
00000000`7748040a c3              ret

1: kd> u ntdll!ZwClose
ntdll!NtClose:
00000000`7747ffa0 4c8bd1          mov     r10,rcx
00000000`7747ffa3 b80c000000      mov     eax,0Ch
00000000`7747ffa8 0f05            syscall
00000000`7747ffaa c3              ret

syscall

用户层ntdll!ZwCreateFile或NtCreateFile会通过syscall切换到内核,最早的Windows系统是通过软中断0x2e来完成模式切换的。如何切换以及切换至何处是由CPU的MSR寄存器所决定的,由操作系统在启动时完成的初始化设定。

针对Win7 X64测试系统来说,此处的syscall指令将跳转由MSR_LSTAR所指向的固定地址:

0: kd> rdmsr 0xc0000082
msr[c0000082] = fffff800`03082ec0
0: kd> u fffff800`03082ec0
nt!KiSystemCall64:
fffff800`03082ec0 0f01f8          swapgs
fffff800`03082ec3 654889242...000 mov   qword ptr gs:[10h],rsp
fffff800`03082ecc 65488b242...000 mov   rsp,qword ptr  gs:[1A8h]
fffff800`03082ed5 6a2b            push    2Bh
fffff800`03082ed7 65ff34251...000 push    qword ptr gs:[10h]
fffff800`03082edf 4153            push    r11
fffff800`03082ee1 6a33            push    33h
fffff800`03082ee3 51              push    rcx
......
fffff800`02c7bfce 6690            xchg    ax,ax
fffff800`02c7bfd0 fb              sti
fffff800`02c7bfd1 48898be0010000  mov     qword ptr [rbx+1E0h],rcx
fffff800`02c7bfd8 8983f8010000    mov     dword ptr [rbx+1F8h],eax
nt!KiSystemServiceStart:
fffff800`02c7bfde 4889a3d8010000  mov     qword ptr [rbx+1D8h],rsp
......

nt!KiSystemCall64主要的工作是:

  1. 参数及用户栈的保存(内核态处理完打好返回用户层)
  2. 内核栈切换、内核线程的初始化设定等
  3. 准备工作做好后,最重要的是调用相应的内核服务(比如nt!NtXXX)

内核层的Nt vs Zw

对内核层来说,Zw与Nt函数虽然参数及功能上都是一致的,但二者对参数的处理及对调用环境的认同是不一样的。以nt!NtClose及nt!ZwClose的代码为例(Win7 X64):

1: kd> u nt!NtClose
nt!NtClose [d:\w7rtm\minkernel\ntos\ob\obclose.c @ 430]:
fffff800`0338e2a0 48895c2408      mov     qword ptr [rsp+8],rbx
fffff800`0338e2a5 57              push    rdi
fffff800`0338e2a6 4883ec20        sub     rsp,20h
fffff800`0338e2aa 65488....010000 mov   rax,qword ptr gs:[188h]
fffff800`0338e2b3 48833....e9ff00 cmp     qword ptr [fffff800`03227450],0
fffff800`0338e2bb 488bd9          mov     rbx,rcx
fffff800`0338e2be 0fb6b8f6010000  movzx   edi,byte ptr [rax+1F6h]
fffff800`0338e2c5 0f8520a70200    jne     nt!NtClose+0x2a74b (fffff800`033b89eb)
fffff800`0338e2cb 400fb6d7        movzx   edx,dil
fffff800`0338e2cf 488bcb          mov     rcx,rbx
fffff800`0338e2d2 488b5c2430      mov     rbx,qword ptr [rsp+30h]
fffff800`0338e2d7 4883c420        add     rsp,20h
fffff800`0338e2db 5f              pop     rdi
fffff800`0338e2dc e91ffdffff      jmp     nt!ObpCloseHandle (fffff800`0338e000)

看nt!NtClose没有针对栈做任何准备工作而是直接进入了任务的处理:即调用nt!ObpCloseHandel。类似NtCreateFile也是类似的流程。

下面再来看nt!ZwClose:

1: kd> u nt!ZwClose
nt!ZwClose [o:\w7rtm.obj.amd64fre\minkernel\ntos\ke\mp\objfre\amd64\sysstubs.asm @ 267]:
fffff800`03073640 488bc4          mov     rax,rsp
fffff800`03073643 fa              cli
fffff800`03073644 4883ec10        sub     rsp,10h
fffff800`03073648 50              push    rax
fffff800`03073649 9c              pushfq
fffff800`0307364a 6a10            push    10h
fffff800`0307364c 488d059d300000  lea     rax,[nt!KiServiceLinkage (fffff800`030766f0)]
fffff800`03073653 50              push    rax
fffff800`03073654 b80c000000      mov     eax,0Ch
fffff800`03073659 e9e2670000      jmp     nt!KiServiceInternal (fffff800`03079e40)

1: kd> u nt!KiServiceInternal
nt!KiServiceInternal:
fffff800`02c7be40 4883ec08        sub     rsp,8
fffff800`02c7be44 55              push    rbp
fffff800`02c7be45 4881ec58010000  sub     rsp,158h
fffff800`02c7be4c 488da...000000  lea     rbp,[rsp+80h]
fffff800`02c7be54 48899dc0000000  mov     qword ptr [rbp+0C0h],rbx
fffff800`02c7be5b 4889bdc8000000  mov     qword ptr [rbp+0C8h],rdi
fffff800`02c7be62 4889b5d0000000  mov     qword ptr [rbp+0D0h],rsi
fffff800`02c7be69 fb              sti
fffff800`02c7be6a 65488b1c2588010000 mov   rbx,qword ptr gs:[188h]
fffff800`02c7be73 0f0d8bd8010000  prefetchw [rbx+1D8h]
fffff800`02c7be7a 0fb6bbf6010000  movzx   edi,byte ptr [rbx+1F6h]
fffff800`02c7be81 40887da8        mov     byte ptr [rbp-58h],dil
fffff800`02c7be85 c683f601000000  mov     byte ptr [rbx+1F6h],0
fffff800`02c7be8c 4c8b93d8010000  mov     r10,qword ptr [rbx+1D8h]
fffff800`02c7be93 4c8995b8000000  mov     qword ptr [rbp+0B8h],r10
fffff800`02c7be9a 4c8d1d3d010000  lea     r11,[nt!KiSystemServiceStart (fffff800`02c7bfde)]
fffff800`02c7bea1 41ffe3          jmp     r11

从代码上来nt!ZwClose前面做的工作则有些类似syscall,如果将syscall称作是硬模式切换的话,那nt!ZwCreate所做的可以称算是软模式切换。前者 是从用户态切换到内核态,涉及到栈及context的切换,转换成本很高。而后者则是从内核态到内核态的切换,其实仅是调用关系,均在同一个内核栈上。

nt!ZwXXX函数最终都会切换到相应的nt!NtXXX函数上,因为系统设定所有的任务都是由系统服务nt!NtXXX来实际处理。

从上面的对比不难看出,nt!ZwXXX函数做了一些看似没必要的切换工作,针对 内核驱动来说貌似完全没有必要。比如打开一个文件用nt!NtCreateFile或nt!IoCreateFile等函数更能节省稀缺的内核栈资源的使用,从这点上来看确实如此。

但二者细微的差别却可能导致严重的资源泄露问题。比如一个内核句柄,即在打开文件时指定了OBJ_KERNEL_HANDLE标志,在使用完毕要释放的时候,如果正巧是在用户context(进程上下文),比如IRP_MJ_CREATE或IRP_MJ_CLEANUP等irp的处理程序中,如果调用nt!NtClose的话,则会导致此句柄的泄露,然后此文件会一直处于打开(被占用)的状态。

其原因是nt!NtClose在处理句柄关闭时默认此句柄属于前一个模式空间(PreviousMode)。相反nt!ZwClose正因为多做了“软模式切换”,其切换过程中会修改PreviousMode为KernelMode,因为nt!ZwClose被调用时的线程已经处于内核线程模式(由用户线程通过syscall切换过来的),此时内核句柄用nt!ZwClose就能够正确关闭。

那么我们这里又有了一个新问题:如果反过来用nt!ZwClose来关闭一个本属于用户进程空间的句柄,会不会出错?

答案是不会的。因为nt!ObpCloseHandle在释放句柄前会针对内核句柄做检查,只有在满足全部条件的情况才会当作内核句柄来处理:

#define KERNEL_HANDLE_MASK ((ULONG_PTR)((LONG)0x80000000))

#define IsKernelHandle(H,M)                           \
    (((KERNEL_HANDLE_MASK & (ULONG_PTR)(H)) ==        \
       KERNEL_HANDLE_MASK) &&                         \
     ((M) == KernelMode) &&                           \
     ((H) != NtCurrentThread()) &&                    \
     ((H) != NtCurrentProcess()))

Object Manager通过句柄的第31位来区分是不是内核句柄,所以即使PreviousMode是KernelMode的情形也只会操作当前用户进程的句柄表(CurrentProcess->ObjectTable)而不是内核句柄表(nt!ObpKernelHandleTable)。

小结

不妨简单一点,用这样几个“简单粗暴”的公式来理解它们之间的关系,以NtClose/ZwClose为例:

  • ntdll!ZwClose(用户层) = ntdll!NtClose (用户层)
  • ntdll!ZwClose = syscall(硬切换) + nt!ZwClose(内核层)
  • nt!ZwClose = 软切换 + nt!NtClose(内核层)

魔鬼总在细节之中 (Devils in the details) !

<一直认为对这部分掌握得比较熟,但真正动笔的时候才发现很多不确定的地方。理解只有够深度够准确够熟练才是真正的理解!本文用时2.5小时。>

参考链接

  1. Nt vs. Zw - Clearing Confusion On The Native API
  2. MSDN: PreviousMode
  3. MSDN: Using Nt and Zw Versions of the Native System Services Routines
  4. MSDN: What Does the Zw Prefix Mean?
  5. Windows 7 x64 下的 System Call
  6. 看雪学院:windows 7 x64 KiSystemCall64 笔记
Continue reading » · Rating: · Written on: 01-13-17 · No Comments »