Windows进程注入

0 前言

安全软件为了达成进程安全及行为审计的目标经常会采用进程注入的方式,即将自己的DLL注入至用户进程中,以对恶意的注入模块进行对抗。就进程注入方法来说有多种方式,木马及攻击方可使用的手段更多,毕竟攻击者对稳定性及善后部分不用做过多考虑。 本文将对注入方式做一个简单的汇总对比,下面分别从应用层及内核层的不同实现方案进行拆解:

1 应用层注入手段

本章节将主要介绍完全应用层的注入实现。

1.1 远程线程及APC注入、SetThreadContext

这两种方式的实现机制是不同的,但思路是一样的,都需要上传负载(Payload)至要注入的进程空间,一般的操作过程如下:

通过OpenProcess获取进程句柄(HANDLE),然后在目标进程空间申请内存(VirtualAlloc或VirtualAllocEx]),然后调用WriteProcessMemory将shellcode负载写入目标进程空间,最后调用CreateRemoteThread、NtCreateThreadEx、RtlCreateUserThread等创建用户线程,或者添加APC(QueueUserApc)至用户线程以完成shellcode的执行目的。

SetThreadContxt机制是将原线程挂起(SuspendThread),通过修改线程Context中的eip/rip指针至上传的shellcode地址。

Shellcode的设计一般只是简单的LdrLoadDll的调用,复杂的有如DoublePulsar木马所采用的,直接将Payload DLL进行展开并手工加载。

用户层注入的问题是权限受限,另外很容易被检测到,现在的杀软普遍都会特殊关照上述的这些特征函数。

1.2 Win32消息钩子

通过Win32 API SetWindowsHookEx注册系统级消息钩子,以截获同一桌面上所有线程的消息通信,从而实现了DLL模块的注入。当然消息钩子的局限也很明显:

  1. 被注入进程必须接受用户输入,使用了消息队列,如带GUI界面程序;服务进程一般无需用户输入,所以此种注入方法对服务进程无效 64位系统中,64位进程只能设置针对64位程序的消息HOOK,32位进程只针对32位程序,不可交叉混用。和SetWindowsHookEx类似的2. SetWinEventHook 虽然同样可以取到所有进程的消息,但并不能导致DLL注入。
  2. Windows Automation API:Windows Automation API提供给程序访问其它程序窗口及组件(UI elements)的能力,一般用于自动化测试。利用Windows Automation API实现注入的过程,和消息钩子的方式没有本质区别,也有着同样的限制。

    1.3 系统提供机制(注册表选项)

    1) App Init DLLs

    所有加载User32.dll的程序均会自动加载此键值下的DLL,主要针对Win7及之前的Windows版本,从Win8之后此机制不被推荐使用,在UEFI Secure Boot模式下此项被默认关闭。

所在注册表位置:

  • HKEY_LOCAL_MACHINE\Software\Microsoft\Windows NT\CurrentVersion\Windows
  • HKEY_LOCAL_MACHINE\SOFTWARE\Wow6432Node\Microsoft\Windows NT\CurrentVersion\Windows\AppInit_DLLs

使用此方式的木马及病毒:GinwuiCherry PickerT9000

2) App Cert DLLs

所有调用下面Win32 API的程序均会自动加载上述注册表中所列的DLL文件:

  • CreateProcess
  • CreateProcessAsUser
  • CreateProcessWithLoginW
  • CreateProcessWithTokenW
  • WinExec

所在注册表位置:

  • HKEY_LOCAL_MACHINE\System\CurrentControlSet\Control\Session Manager

使用此方式的木马及病毒:HoneybeeFIN8 PUNCHBUGGY

3) Image File Execution Options

这是Windows系统提供的一个调试辅助机制,用以在特定进程启动或退出时启动指定程序(如调试器等)。用户通过更改IFEO键值达成启动不同进程的目的,从而导致原进程加载请求失败。

所在注册表位置:

  • HKLM\SOFTWARE{\Wow6432Node}\Microsoft\Windows NT\CurrentVersion\Image File Execution Options\
  • HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\SilentProcessExit\

4) Shim Database (SDB)攻击

Windows系统通过Shim数据库(SDB文件,位于%windir%\AppPatch\sysmain.sdb)以提升应用程序的向后兼容(backward compatibility)。SDB数据库中包含针对上千个程序的上百种配置,只要有管理员权限就可操纵此数据库,就可以修改任意程序的各种属性,如以下多种属性:

  • InjectDll
  • LoadLibraryRedirectFlag
  • ForceAdminAccess
  • RelaunchElevated
  • WrpMitigation
  • DisableNX
  • ModifyShellLinkPath
  • VirtualRegistry
  • DisableAdvancedRPCClientHardening
  • CorrectFilePaths
  • DisableSeh
  • DisableWindowsDefender
  • ShellExecuteXP

涉及注册表项:

  • HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\AppCompatFlags\Custom
  • HKLM\SOFTWARE\Microsoft\Windows NT\CurrentVersion\AppCompatFlags\InstalledSDB

使用此方式的木马及病毒:BlackEnergy, GooKit, Roaming Tiger,QianSet.exe,VzQqgi.dll木马

1.4 PE程序IAT表静态修改

早期的Win32病毒常采用的就是静态感染方式,会将自身的代码写入被被感染程序,然后修改PE入口函数至病毒的代码段;同样的方式,静态修改PE文件的导入表以增加新的DLL注入亦不是难事。

针对有签名的PE程序,类似的修改会导致签名校验失败。

1.5 DLL替换

创建一个假个但导出一模一样的DLL文件用以替换原系统的,替换办法一般有两种办法:

  1. 系统原DLL文件改名,并替换系统DLL
  2. 更改DLL搜索路径(SetDLLDirectory)

这种方式要处理的问题:

  1. 系统模块签名问题无法处理:PPL进程将无法运行
  2. 不同版本的系统DLL处理堆积

2 内核层注入手段

内核R0层注入要比应用层R3的手段少了很多,实现难度会大一些,但内核实现更加隐蔽,难以被屏蔽。通过创建用户层线程或插入APC以实现注入的方式被普遍使用,原理上同R3的远程线程及APC注入的思路基本一致,均需要向目标进程空间上载参数及shellcode代码,只是R0及R3各自使用的支持函数不同。

2.1 IAT表注入

在进程创建过程中,内核驱动通过PsSetCreateProcessNotifyRoutine或PsSetCreateProcessNotifyRoutineEx得到通知,此时用户进程的创建过程是被阻塞的,在处理通知的回调中,内核驱动可以修改进程的内存镜像中的导入表,将要注入的驱动加入其中。

以wermgr.exe进程(PID: 0x6bc)的创建为例,此进程由services.exe(PID: 0x2bc)创建: Windows注入-IAT表 后续会收到模块加载的通知回调,加载模块的顺序依次为wermgr.exe自身、ntdll.dll、kernel32.dll、KernelBase.dll、msvcrt.dll等,回调时的调用栈为: Windows IAT注入 导入表修改动作是在进程镜像本身的模块加载回调中执行的,即程序本身模块加载的时机。

IAT表注入的主要问题:

  1. .NET程序的兼容性问题
  2. 托管代码与非托管DLL代码的混合
  3. 64位.NET程序没有导入表项
  4. 受保护进程的注入问题,必须要通过NTDLL HOOK来解决,因为创建Section对象时内核会验证DLL签名等,在IAT已注入的情况下签名又无法签证通过时会导致程序加载失败

2.2 Shellcode注入

创建用户线程及插入APC的注入手段均需要上载shellcode代码至目标进程,shellcode可以只是简单的LdrLoadDll调用用以加载HOOK引擎及工作模块,复杂一些的话可以在内核层将DLL手工加载至目标进程空间,正如木马DoublePulsar所实现的加载器【D23】"Generic Relective DLL Loader"或者内核层Turla Driver Loader(TDL)驱动加载器【D18】。

常用shellcode/payload构造(BlackBone的实现):

// shellcode for X64
UCHAR code[] =
{
0x48, 0x83, 0xEC, 0x28,             // sub rsp, 0x28
0x48, 0x31, 0xC9,                   // xor rcx, rcx
0x48, 0x31, 0xD2,                   // xor rdx, rdx
0x49, 0xB8, 0, 0, 0, 0, 0, 0, 0, 0, // mov r8, ModuleFileName   offset+12
0x49, 0xB9, 0, 0, 0, 0, 0, 0, 0, 0, // mov r9, ModuleHandle     offset+28
0x48, 0xB8, 0, 0, 0, 0, 0, 0, 0, 0, // mov rax, LdrLoadDll      offset+32
0xFF, 0xD0,                         // call rax
0x48, 0xBA, 0, 0, 0, 0, 0, 0, 0, 0, // mov rdx, COMPLETE_OFFSET offset+44
0xC7, 0x02, 0x7E, 0x1E, 0x37, 0xC0, // mov [rdx], CALL_COMPLETE
0x48, 0x83, 0xC4, 0x28,             // add rsp, 0x28
0xC3                                // ret
};

// shellcode for X86
UCHAR code[] =
{
0x68, 0, 0, 0, 0,                   // push ModuleHandle        offset+01
0x68, 0, 0, 0, 0,                   // push ModuleFileName      offset+06
0x6A, 0,                            // push Flags
0x6A, 0,                            // push PathToFile
0xE8, 0, 0, 0, 0,                   // call LdrLoadDll          offset+15
0xBA, 0, 0, 0, 0,                   // mov edx, COMPLETE_OFFSET offset+20
0xC7, 0x02, 0x7E, 0x1E, 0x37, 0xC0, // mov [edx], CALL_COMPLETE
0xC2, 0x04, 0x00                    // ret 4
};

1) 创建用户线程

创建用户线程一般通过NtCreateThreadEx(Visata及以后OS)或NtCreateThread(XP),这两个函数在内核中均未导出且是未公开的,其地址获取可以通过SSDT或者ntoskrnl镜像解析完成。

NTKERNELAPI NTSTATUS NTAPI
NtCreateThread(
__out PHANDLE ThreadHandle,
__in ACCESS_MASK DesiredAccess,
__in_opt POBJECT_ATTRIBUTES ObjectAttributes,
__in HANDLE ProcessHandle,
__out PCLIENT_ID ClientId,
__in PCONTEXT ThreadContext,
__in PINITIAL_TEB InitialTeb,
__in BOOLEAN CreateSuspended
);

NTKERNELAPI NTSTATUS NTAPI
NtCreateThreadEx(
OUT PHANDLE hThread,
IN ACCESS_MASK DesiredAccess,
IN PVOID ObjectAttributes,
IN HANDLE ProcessHandle,
IN PVOID lpStartAddress,
IN PVOID lpParameter,
IN ULONG Flags,
IN SIZE_T StackZeroBits,
IN SIZE_T SizeOfStackCommit,
IN SIZE_T SizeOfStackReserve,
OUT PVOID lpBytesBuffer
);

2) APC注入

在内核中构造一个APC结构并添加至用户线程的APC队列,等条件满足时系统会执行APC中设定的callback,从而达成进程DLL注入的目的。

相关函数原型如下:

NTKERNELAPI VOID NTAPI
KeInitializeApc (
__out PRKAPC    Apc,
__in PRKTHREAD  Thread,
__in KAPC_ENVIRONMENT   Environment,
__in PKKERNEL_ROUTINE   KernelRoutine,
__in_opt PKRUNDOWN_ROUTINE  RundownRoutine,
__in_opt PKNORMAL_ROUTINE   NormalRoutine,
__in_opt KPROCESSOR_MODE    ProcessorMode,
__in_opt PVOID  NormalContext
);

NTKERNELAPI BOOLEAN NTAPI
KeInsertQueueApc    (
__inout PRKAPC  Apc,
__in_opt PVOID  SystemArgument1,
__in_opt PVOID  SystemArgument2,
__in KPRIORITY  Increment
);

360安全卫士的驱动360fsflt.sys、木马DoublePulsar【D22】等所采用的方式就是Kernel APC注入,这种方式被普遍使用。但APC注入要注意以下问题:

  1. 时机问题:要求所注入进程已经创建了线程并且已经执行(主线程都是紧随进程创建的)
  2. 依赖线程状态:APC的执行依赖于所注入线程的状态:一般是从内核态切换回用户态时执行
  3. 必须与注入线程做同步,或者在所注入线程环境中插入APC,不然可能会注入至错误进程,另外与第三方驱动同时注入APC存在竞争及一致性问题,当然竞争窗口极小; 每个线程均有两个APC队列,当线程在内核态下调用KeAttachProcess时会做切换,切换过程中没有任何保护

3) HOOK NTDLL方式

内核驱动可以通过内核的回调机制截获用户进程创建及PE加载器加载并初始化DLL链的每个环节,可以监控到指定模块加载时同步进行inline hook,并将关注点的执行流程导向至已上载的shellcode负载。

回调本身是串行在程序的加载流程中的,即回调不返回,进程的创建及DLL的加载过程是被阻塞的,省却了同步与不一致性的问题的处理。

之所以要选择ntdll.dll的原因是,ntdll.dll是所有的Win32程序必须加载的,并且其执行过程比程序本身的入口执行要早;另外选择ntdll.dll而不是Kernel32.dll等模块的原因是,Kernel32.dll等模块并不是必须的,比如Native程序如csrss,exe、autochk.exe等,还有一些程序将Kernel32.dll等模块设置为Delay-Loading-DLL,并不会在程序启动之初就立即加载并执行。

为了尽早地获取控制权,常用的HOOK点一般放在ntdll!LdrInitializeThunk、ntdll!NtOpenDirectoryObject或者ntdll!LdrLoadDLL等关键函数点。Haiheiwang木马【D16】就是通过修改ntdll!NtTestAlert的流程将自己的工作模块加入被感染进程的,当然ntdll!NtTestAlert也存在时机较晚的问题,并不能满足咱们的需求。

这种方式在安全软件中也广泛使用,特别是对针对Win8系统年引入的受保护进程的注入问题,由内核注入Shellcode并通过HOOK ntdll!NtCreateSection来加载非系统模块是最实用且有效方式,目前360安全卫士的注入亦是采用此方式。受保护PPL进程只对用户层的Section对象创建有签名验证,我们通过将内核层创建Section对象映射至用户空间的方式达成向受保护PPL进程注入的目的。

其它的替代方案会导致受保护进行安全性的妥协等,比如短暂取消受保护进行的保护状态以达成注入目的,此种方式有可能会触发KPP/PG检测失效,另外也很容易被第三方恶意利用,比如MalwareFox AntiMalware的一个被曝光的漏洞【D24: MalwareFox AntiMalware 2.74.0.150 LPE】。

Shellcode内存映射可以在HOOK引擎模块加载之后进行销毁,存在窗口时间非常短,被其它安全软件查到或被其它恶意程序所利用的可能比较小。

3 参考资料

3.1 浏览器自身防护资讯

B1: About Google Chrome's incompatible applications warning

B2: Firefox will block DLL Injections

B3: Protecting Microsoft Edge against binary injection

3.2 进程DLL注入资料

D1: DLL Injection with SetThreadContext

D2: R3 DLL Injection: Inject All The Things

D3: COUNTERCEPT: Analyzing the DOUBLEPULSAR Kernel DLL Injection Technique

D4: COUNTERCEPT: Dynamic Shellcode Execution

D5: Ten Process Injection Techniques

D6: DLL Injector via Windows Automation API

D7: Microsoft: AppInit DLLs and Secure Boot

D8: BlackHat: Malicious Application Compatibility Shims

D9: To SDB, Or Not To SDB: FIN7 Leveraging Shim Databases for Persistence

D10: FreeBuf: 走近微软安全技术Shim

D11: ABICC: Windows API/ABI Changes Analysis

D12: MITRE ATT&CK: Application Shimming

D13: FireEye: The Real Shim Shady

D14: iSIGHTPARTNERS: 固守: 微软Fix It补丁机制原理及攻击利用

D15: 腾讯:木马牟利再出新招-恶意利用Windows shim技术锁主页

D16: 腾讯:Haiheiwang木马分析

D17: Windows Vista APC Internals

D18: TDL: Turla Driver Loader

D19: Scylla and API Set Map

D20: Microsoft Docs: Windows API Sets

D21: Windows_7_Kernel_Changes: api-ms-win-core DLLs

D22: DOUBLEPULSAR Kernel DLL Injection Technique

D23: DOUBLEPULSAR: Generic Reflective DLL Loader

D24: MalwareFox AntiMalware 2.74.0.150 - LPE

D25:DLL Injection via SetDLLDirectory

D26: CodeProject: Create your Proxy DLLs automatically

D27: Proxy WS2_32.DLL to create your own firewall

D28: CodeProject: API hooking revealed

3.3 DLL注入商业方案

D30: Shellter Pro: DLL Injection Kit

D31: madCodeHook: DLL Injection Kit

3.4 开源HOOK引擎

H1: Microsoft Detours

H2: Detours NT

H3: minhook

H4: mhook

H5: EasyHook

H6: Deviare Hook Engine

3.5 Instrumentation Callback

I1: 利用KPROCESS结构的InstrumentationCallback域实现Hook

I2: Hooking-via-InstrumentationCallback

I3: Alex Ionescu: Hooking Nirvana

3.6 PPL (Protected Process Light)

P1: Injecting Code into Windows Protected Processes using COM - Part 1

P2: Injecting Code into Windows Protected Processes using COM - Part 2

P3: The Evolution of Protected Processes Part 1: Pass-the-Hash Mitigations in Windows 8.1

P4: The Evolution of Protected Processes Part 2: Exploit/Jailbreak Mitigations, Unkillable Processes and Protected Services

P5: Protected Processes Part 3 : Windows PKI Internals (Signing Levels, Scenarios, Root Keys, EKUs & Runtime Signers)

P6: Protected Processes Light killer

P7: Why Protected Processes Are A Bad Idea

P8: Micorosft: Protecting Anti-Malware Services

P9: Microsoft: Early launch antimalware

P10: Microsoft Virus Initiative

P11: Early Launch Anti-Malware Driver

3.7 WSL (Windows Subsystem for Linux)

W1: The Linux kernel hidden inside Windows 10

W2: Fun with the Windows Subsystem for Linux (WSL/LXSS)

W3: Hunting for Windows Subsystem for Linux

W4: Exploring Windows Subsystem for Linux

W5: Windows 10 and the Anti-malware Ecosystem

W6: Pico Process Overview

W7: WSL System Calls

--- END ---

奔跑在理想之国 — 2018梅里100赛记

“他是两个世界之间的流浪者,注定要永远流浪。”

James Hilton在其所著的《消失的地平线》一书中用来形容主人翁Conway的这句话,同样用来形容每一个跑者也是恰如其分!很多人生活在繁杂拥闹的大城市,所向往的却是野外大自然的宁静悠然。我们在两个世界间不停地穿梭与奔跑,大自然就是我们心中的“香格里拉”。

香格里拉、虎跳、梅里、雨崩、神瀑,2010年7月我曾经来过,不知8年之后的今天,又会变成什么模样?那个与世隔绝的村子是否还保有着仙境般的梦幻?卡瓦格博是否依然还是那个羞涩的小姑娘,始终不肯摘下紧裹的云纱?

万千往事揉着纷杂思绪潮水般涌向心头,而我却无从下笔,就像拿起了一根烟放在嘴里却尴尬地发现没有了火,只能呆呆地望着窗外......

起心

1月11日UTMB抽签结果新鲜出炉,可惜没有带来好消息,几个朋友都没有中签。“不跑个168都不好意思”的小群中4个报了UTMB168的人中,只有过客一人中签,另外天路报了TDS也顺利收获了一张入场券。虽然遗憾,但不中自有不中的好处,就在结果出来后仅几个小时,我和老大便已报名梅里100。

决心一旦下定,旋即就进入了一种亢奋:去赴它个一场与雨崩的8年之约!去跑它个一场高海拔的100公里!连从未体验过高海拔的老大也同样踌躇满志。

只要有了目标,对我们而言,就自会有行动!我们是一群最不缺乏行动力的人。

动念

考虑到老大没有高海拔的经验,我们计划早于比赛几天到达以适应海拔,先去徒步虎跳峡,然后去雨崩村。后来赛事时间变更,结果我们前面可安排的时间更充裕了,多出了一天半的时间,我开始盘算这一天半的时间完全可以去爬个哈巴,毕竟来一趟不容易,即使爬不成雪山,在大本营做个高海拔适应也好。

在香格里拉等老大到来的空,我给哈巴向导武桑打了电话,问询了哈巴山上的情况及近期的天气,得知山上已连着下了三天雨,武桑相信后面会有一个好的天气窗口,另外所需的技术装备如冰镐、冰爪等均有出租。听到这些,我更是按奈不住地兴奋,要玩就不妨玩大的,上次雪山攀登还是2011年的雀儿山。从接触户外之初就对雪山有着一莫名的向往,一连串地爬了几座之后却又对当前的商业登山失望之至,而今又能够亲近雪山了,虽然哈巴只是一座初级山峰,依然莫名兴奋。

等老大到达汇合后,和他说了我的想法,我们一拍即合。眼前,除了兴奋与鸡血。没有别的!

买好了去桥头镇的车票,还有20分钟发车,老大说有点饿,我们遂到车站边上的小饭馆问最快的吃的是什么,老板娘得知我们只有20分钟时她很会意地答曰:米粉。一阵风卷残云,仅过了7分钟,与满脸笑容的老板娘道别,我们俩扬长而去。

28道拐前没有了赌你爬不动的马夫,徒步的小径很多已被宽阔的水泥路面所替代,走到了路上才知道准备的不足,我下载的轨迹虽是2017年的,但已然过时,其中一段腰绕的线路因为修隧道的缘故被破坏了。我和老大在铁丝网上爬了好一阵子,被工地上的人叫了下来,告知路在下面。经过几经探寻之后,终于对上了轨迹走上了正途,但1个小时的时间已飘然而逝。

8年后再走虎跳,已经记不得当时走过的路,反而觉得脚下的路和尼泊尔EBC很像很像。记忆就像一张网,咋一想起便牵动了所有的枝枝叶叶,但一旦仔细回味起来,却只剩下了破碎而又坚硬的梗。

天开始下雨,我们穿好冲锋衣准备好了一场雨战,但高原的天气就是喜欢捉弄你,一会雨又一会晴,湿闷得不行,再加上已好久没有重装徒步,爬起28道拐来相当绝望,远处的玉龙雪山一直藏在云层里,峡谷中蜿蜒着的混浊泥流发出轰鸣的水声却响彻山谷,像是对你的嘲笑。

在茶马客栈补了瓶水之后,我们继续出发,很快到达中途客栈(Half Way G.H.),此时已近8点,天色开始变暗。经过6个小时的行走,我们觉得相当疲惫,毕竟背着近14公斤的包,而且还是几经压缩精简后的。

客栈里已经来了不少客人,我们到达时他们正聊着天。第一眼看去,Half Way还是以前的Half Way,安静的小园子,可以眺望峡谷的天台,但房间内早已升级换代,以前的公共浴室已被各个房间内的沐浴设施取代,不知“天下第一厕”还安否?已然没了去参观它的兴致。

不群

也不知道为什么,反正莫名地就将不群岳兄和中途的老板联系在一起了,为了想明白这个问题,着实费了不少脑细胞但还是没有想明白个缘由。

途经茶马时就得知整个虎跳峡因输电线杆被撞已全部停电,到达中途客栈后问老板洗澡的事,还以为是以前的公共沐浴间,结果老板高逼格说了句:“洗澡是必备的最基本的要求”,结果晚上发电机还没发动就爆了,亏得热水器中存有不少热水,足够我们俩冲个澡;老板还说过早上7点准点有早饭,第二天我们起来后不见人影,我不得不找遍了客栈去逐个敲门,

结完账,我和老大快速撤离,50分钟后在中峡客栈Tina's吃了顿超丰盛的早餐。

行定

和武桑约好11点在山白脸汇合,我想着两个半小时的时间足够我们在中虎跳游玩了。谁知老大竟然这么爱拍照,每过一个点都要正拍10张再反拍10张,然后回过身来再来10张,搞得我好不紧张,毕竟后面的哈巴才是重点。

好在过了一线天之后,走出峡谷,风景不在,我们遂加快了脚步。

外面,武桑和车已经等候多时!到山白脸走了一圈,权算故地重游。

车子发动,沿着金沙江峡谷急驰。

哈巴,我们来了!

在武桑家稍做停留,我们即从彝族村出发去哈巴大本营。路上我叮嘱老大要慢点,慢慢上升慢慢适应海拔,可最后我们还是快过了马,用了3个小时到达海拔约4100的大本营后依然还是一脸的兴奋劲。马儿虽慢,但马儿更会休息,马儿更会保持速度,马儿能够跑得更远,但我们比它更有激情!特别是对于老大来说,高海拔绝对是个正儿八经的新鲜事。

在大本营转了几圈,在营房内烤了几个小时的火,拍照、聊天、烤火、喝水、撒尿,看着山上厚厚的云层被风卷来卷去,山体在云层的包裹中幻生幻灭,木头在火中噼啪作响,火星似流星般向上划出道道弧线,然后湮灭在房间窒息的空气中。我,静静地望着它们,百无聊奈。

是夜,我如期的头痛着入睡,做着各种努力让自己好好睡觉的梦!

是夜,老大如我所叮嘱的一样,躺着一动不动,只是他一丁点儿都没睡着。他说也不头痛也不胸闷,可就是睡不着!连续着三天只睡了两个多小时,超级铁人一个!

凌晨3点半起来吃了碗咸面片粥,觉得超级香,现在想起来还直流口水,看来有必要向武桑索要配方。3:52出发,我们俩是第一队,后面有大部队正在吃饭。

天上滴着小雨,好天气窗口并没有因为前面连续三天的雨而特别眷顾我们,相反而是继续让坏天气来考验我们向上的决心。走过了一小段灌木丛路,我们踏上了光亮的岩石,岩缝中还夹有雪渍,但哈巴的砾岩一点不滑,走起来并不费力。但随着海拔的上升,部分路段覆盖了一层薄薄的冰,这部分走起来要格外小心。

过了雪线后绑上了冰爪,虽然天色渐亮,但我们逐渐走进了浓雾中,天是白的,地上白的,分不清界限,透过雪镜中依稀能看到两侧的山脊的模糊轮廓,山脊两侧就是悬崖,而我们就在悬崖间窄窄的通道上艰难爬行,凭着感觉向上、再向上,只有感觉到确实向上才能明确路线是对的。

前面一段路老大一直很活跃,冲在前面,但到了这一段,开始有点跟不上了,毕竟连续几夜没能休息好再加上连续几天的高强度运动,着实让人吃不消。

从C1营地出发的队伍和我们汇合在一起,一个女生和我们不停地穿插行走交替领先,令我惊讶的是,她和老大一样,也是第一次攀登雪山。

浓雾中两侧山脊渐渐收窄,上山的坡度依然延伸在前面的路上,每慢走50步就要停下来喘口大气,尽我最大的贪婪吸进面前的浓雾,但呼出的热气却更妨碍了前面的视野。

在第N个50步,或者在喘过第N个粗气之后,终于看到了顶峰标志,像是一个刻着字的简陋木板,注意到右侧的山顶更高,我向右上侧挪去,走到一半的时候,向导安牛上来了,安牛叫停了我,说右侧危险,到这里就可以了,这里就是哈巴顶峰。

似乎还不过瘾,似乎是因为天不作美,顶峰上的风景也就4-5米的视野内的一片白茫茫......

时间正好8点半,从大本营出发到现在共4小时38分。后面的女生也上来了,帮她和向导拍照后,我和老大及安牛便开始下撤。

浓浓的大雾中,上来的脚印已经看不出了,天好像还下着雪,小心翼翼地循着山势向下探寻了好长一段,终于遇见了向上攀登的大队伍,一下子热闹了起来,相互间打着招呼,我向他们广播着此地到顶峰的大体所需时间,终于能够放开步子开走。

下至雪线,撤了冰爪,撒欢向下跑,一溜跑到大本营,从凌晨出发到回到大本营共6小时20分。哈巴之行现在可以说是圆满。

发心

和武桑沟通了一下,他说先休息会吃了饭就下山,然后去香格里拉。

老大吵着要好好睡一觉,我却兴奋地没有一点疲倦,在营房里和从广东来哈巴考察做科研的土豪(耗)烤火、聊天。

他们一行几人是考察高海拔上老鼠的种类及分布的,篝火边的木板上全是老鼠的标本,他们准备要将标本烤干,回去还要做肉质分析。问了他不少问题,也聊了不少以前徒步的经历,以至临走时已有几分不舍。

海拔4100的大本营,虽然条件比较艰苦,但这里的人来自全国各地,每个人背后都有着一串串精彩的故事,每个人都有着一颗开放的心。虽然相见短暂,但相聊甚欢,几言几语间已成知己,更多的话不必发出声即能颜传意会,如同《消失的地平线中》所述的康维或亨舍尔与佩劳尔特相逢相知和相互欣赏。

然而时间很快,道别时刻终于还是到来,虽然心里不舍,手上却是轻轻一挥,故作轻松 ...

老大,他 终究 还是 没能 睡着!

随性

重担已卸,警觉亦歇,下山过程全无负担,心意飞悦。我们一行4人(我、老大、武桑、安牛)加上马儿轻松自在,路上比较泥汀,我们不急于赶路,边走边聊,用了2个多小时到达武桑家。

见到了武桑的妈妈,一位慈祥硬朗的彝族老妈妈。我们的哈巴之行就定格在了她满脸的笑容里。

梅里100准备会上古神播放的路线视频让我印象深刻,以至于跑完之后我又看了几遍,但其中几个CP点,纵使我每一个都曾经走过,但怎么也想不起来它的模样了,就好像我压根没看到过似的,难道是因为高海拔缺氧所致!?

30号中午到达飞来寺,入住了老大早早预定好的梅里往事。路过白马雪山时还飘着雪,飞来寺这边则是下着小雨,看到明天将是一场艰苦卓绝的泥战了。

准备会后是丰盛的自助餐,吃得非常非常非常饱,必须对得起赛事组织方的盛情和用心。

下午时分,雨已停,但梅里雪山方向依然密布着云层,白马雪山方向风云幻变,一会亮了半边的天空,一会又升起了浓浓的白雾。

所有人都在祈祷 明天天会变好。

时钟转到了早上8点,发令枪响,人流开始旋转,山在动,地已醒,鞋子上的泥点在飞,雨点也在盘旋着下降,汗一滴滴钻出皮肤而后又钻入土地,等待着变成雨点的轮回。

过了永宗桥后开始上升, 高海拔上升路段已没有了冲下山的那股势气。路上追上了王同伟,30号刚刚认识的北京跑友,同住在梅里往事;晚上在跑神爆的路上又曾碰到他,赛后得知他是30公里的第一名。

过西当村,不时传来加油的吆喝声,我则回应“扎西德勒”,然后就是更多的“扎西德勒”的回声。经过八一茶馆,古神在门口忙碌着,我则只是加满热水即冲向下一站。

去冰湖的路太过漫长,关键回来也要走同样多的路,高海拔的漫长上坡真是让人崩溃,感觉从中午一直到傍晚。至冰川一段和天路同行,冰川上又偶遇古神,顿觉世界真小。

正好在天就要变黑之前,我走到了神瀑脚下,水量比上次来看她的时候要少很多,但现在的她更轻盈活泼,躲在似透非透的薄雾里婀娜着缓缓流下,我凝视许久,天又开始下雨,瀑布迸溅的水滴混着雨点打在我身上,一身清凉。

飞奔而下,走出峡谷的时候碰到了老大,看他状态还不错,他说在上雨崩休息了挺长时间。

从下雨崩出来,志愿者伸出手掌,我们击掌相别,黑夜中我向着白塔跑去,然后就是一路的狂奔,左侧咆哮着的雨崩河无怨无悔地投向澜沧江的怀抱,而我也顺着她无心无肺地奔跑,一路上只有雨崩河的陪伴,好不惬意。直至神秘客栈前才看到志愿者,后又追上了两名选手。

也许是海拔下降之故,晚上的气温相当高,我只得在尼龙村的取水渠里用水浇在头上及身上,顿觉一身的舒服,此时1052号的李灏赶上来,我的号码是1025。从此之后30多公里我们一路偕行,直到终点飞来寺。

从尼龙出发到拥用的机耕路真得要走死人,无语!漫长的路总有尽头,但到了尽头之后又发现黑暗中还有新的尽头在等待着你。

6月1号早上5点48我们从曲登阁出发,向终点发起冲击,天逐渐变亮,然后太阳出来了,直辣辣地照在身上,让我们毫无防备,后果当然不言而喻,左手腕被晒红,鼻子、嘴及下巴区域成了黑三角。

最后关头,冲进24小时的希望越来越大,但是不到终点,你永远不会知道还有什么样的路,我一边快步走着,一边催促着李灏。

在奔跑了近24小时之后,我们俩同时冲线!23小时28分。

情切

6月2号早上,我和老大拖着麻木的双腿走到楼下,正遇到梅里往事的老板,他问我们:你们吃过我们的早饭没?“没有”,我们回答说。接着老板很自豪地说:那你们必须要尝一尝!

于是我们坐下,老板则忙开了,陆续端上来牛奶、奶昔,烤好的面包片及黄油、草莓酱,然后煎蛋和青菜卷,好丰盛的早餐。

临走的时候,正吃饭的老板看到了我们,放下碗筷起身相送。

那一刻,真得不想走,真得想留下来。

素蚁、土豆、老大、我,我们四人将自己塞进了一辆小速腾,任由它飞驰着将我们带离这个世界:这个世界里我们曾挥洒汗水,这个世界里我们曾兴奋而又绝望,这个世界里我们狂奔着叫嚣着狂热着,这个世界里我们又曾无比安静和虔诚地凝视着、祈祷着...

不舍,情切,甚切!

锚点

凡事你曾用心,事必然也会铸造着你。做了但没有一点反响,岂不是等同于从未做过!

8年前的雨崩之行,是我开始独立走长线的锚点;

8年后的梅里之行,是我最惬意的一次高海奔跑体验。

还记得20年前的哈尔滨的一个冬夜,跑过了第一个10000米;

还记得在华政操场上的第一个60圈 ....

太多,太多,早已被抛在了脑后,因为一直有新的锚点在筑起新的高度。

结束即开始

迪庆,是一个奇迹之地,民族的融合,三江并流,山川壮丽,每个人心中的香巴拉圣境,理想之国!每一个跑者的奔跑之地!转梅里,穿三江,跑出自我!

就如在西奈山上上帝对摩西所言:"I AM WHO I AM ..." (From Exodus 3.14)

跑我所跑 !

爱跑而跑 !

无所不能跑 !

WE ARE RUNNING WHAT WE ARE RUNNING !

WE ARE RUNNING WHY (BECAUSE) WE ARE RUNNING !

WE ARE RUNNING WHERE WE ARE RUNNING !

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使用者,又可以欢呼了,但此好景能延续到什么时候呢?

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,之后又测试了几次休眠,再没有出问题,世界终于又大同了!

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

解析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小时>

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 &lt; len; i += 4 * g_aes_nb[mode]) {

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

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

            if (nr &gt; 0) {

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

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

                if (nr &lt; 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 &lt; 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 &lt; g_aes_nb[mode]; i++) {
        for (j = 0; j &lt; 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 &lt; g_aes_nb[mode]; i++) {
        for (j = 0; j &lt; i; j++) {
            uint8_t tmp = s[i];
            for (r = 0; r &lt; 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 &lt; g_aes_nb[mode]; i++) {
        for (r = 0; r &lt; 4; r++) {
            s[r] = 0;
            for (j = 0; j &lt; 4; j++) {
                s[r] = s[r] ^ aes_mul(state[i * 4 + j], y[r * 4 + j]);
            }
        }
        for (r = 0; r &lt; 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 &lt; 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 *)&amp;key[i * 4 + 0]);
    } while (++i &lt; 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] &gt; 6 &amp;&amp; (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 &lt; 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 &lt; len; i += 4 * g_aes_nb[mode]) {

        /* init state from user buffer (cyphertext) */
        for (j = 0; j &lt; 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 &gt;= 0; nr--) {

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

            if (nr &gt; 0) {
                if (nr &lt; 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 &lt; 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加密

经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 &lt; len; i += 4 * g_aes_nb[mode]) {
        /* init state from user buffer (plaintext) */
        for (j = 0; j &lt; 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 &lt;= g_aes_rounds[mode]; nr++) {

            if (nr &gt; 0) {

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

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

                if (nr &lt; 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 &lt; 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=&quot;~0x200000200000000&quot; 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 &lt; 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小时。学习从来不是容易的事!但越是不容易的事情做起来才更有乐趣!>