一年十二月谁主春秋关注：基础系统工程密码学人工智能

经典的复杂性关系
P是多项式时间确定型图灵机可识别的语言类，NP是多项式时间非确定型图灵机可识别的语言类，NPC表示NP完全问题类，coNP表示NP的补，coNPC表示NPC的补。确定型图灵机是一种从不选择移动的特殊的非确定型图灵机，故自然有P属于NP

coNP、coNPC的定义之集合表述

上面顶部的图有个假设前提是：coNPC不属于NP，即我们相信NP完全问题的补都不属于NP。但当P=NP或NP=coNP时，可以发现coNPC属于NP

◆ 为什么coNPC属于coNP？

◆ 为什么NPC 不属于coNP？

◆ 为什么P属于coNP?

◆ 当P=NP时，为什么NP=coNP？

◆ 当NP=coNP时，为什么NPC=coNPC？

前文的关系演变图没考虑多项式空间问题类PS与递归问题类（因为那两个条件不会影响到它们），PS（NPS）是带多项式空间限制的确定型（非确定型）图灵机可接受的语言类，但不限制运行时间可能需超多项式或指数时间，在外围加上PS与递归语言类后如下

◆ 为什么coNP 属于PS？

用于分析加密
无论对称还是公钥加密，统一设加密运算为E，解密为D。对于正常用户，E和D皆为DTM（确定性图灵机）；对于敌手，若攻击对称加密，则E和D为NTM（非确定性图灵机），攻击公钥则解密为NTM。由于E和D输入为密钥和明文或密文，因此DTM和NTM可采用多道/多带结构。DTM代表P类计算，NTM代表NP类计算，故对于公钥加密安全保障要求P!=NP，这是一个必要条件。另根据计算理论定理，必有L(NTM)=L(DTM)，但是它对应的DTM可能要多花费指数时间，这亦说明破解公钥的解密是困难的

零知识复杂性关系

依据Oded Goldreich的《密码学基础》，关系如下

相关原文片段引用如下

BPP是可被概率多项式时间图灵机(即随机化算法)识别的语言类，IP是所有具有交互证明系统的语言构成的类，等于多项式空间语言类即前文经典复杂性关系中的PS，如下图所述

SZK!=CZK是因为计算不可分辨不一定能推出统计不可分辨，BPP!=PZK之原因可理解为BPP是退化的特殊的完备交互证明系统（证明者什么都不做，仅由验证者概率性地决定是否接受或拒绝）。
当（非均匀）单向函数存在时CZK=IP，涉及的命题与定理如下

也就是说PS类中的每种语言都具有零知识证明系统，比如NP有如下构造

posted @ 2024-02-09 22:19 春秋十二月阅读(309) | 评论 (0) | 编辑收藏

一个积分攻击定理的证明

【定理】设多项式，其中q是某个素数的方幂，F_q为有限域，则

若是置换多项式，则

【证明】

posted @ 2023-12-16 21:49 春秋十二月阅读(197) | 评论 (0) | 编辑收藏

浅谈体系结构与内联优化

周知内联是为了消除函数调用的代价，即四大指令序列：调用前序列、被调者起始序列、被调者收尾序列、返回后序列。它们通常对应到体系结构调用者保存/恢复寄存器集合与被调者保存/恢复寄存器集合之约束。这个本质也是内联的前提。试问如果有某体系结构比如S，它任意深度的函数调用代价几乎为零，那么显然内联是没意义没必要的。但是S可能存在吗？我认为不太可能。因为机器的资源比如寄存器集数量与堆栈空间是有限的，且调用需要知晓上下文，所以不能够支持任意深度的调用，但是可以支持有限深度比如4层调用，这4层调用代价几乎为零，假设再来一层，那么第5层调用代价就不为零了，这时如果内联第5层就变成4层调用，代价又几乎为零。综上所述，内联无论在何种体系结构，即使在一定深度内没意义也不会破坏性能。

体系结构直接影响程序性能。主要体现在指令集、寄存器、cache三块。它们对于编译器实现代码优化必须都考虑，尤其cache比如内联优化、循环展开、基本块布局、函数重排，如果不是因为有cache这玩意，内联优化的复杂性会大为降低，因为不用考虑代码膨胀引起的副作用即cache缺失，只要评估函数的指令数与动态执行消耗的关系，指令数很少但执行耗费很多时钟周期的，则不宜内联，尤其函数为非叶子结点；指令数很多但执行耗费较少的，则可仅内联其中的快速路径代码。因现实存在cache这玩意，就必须权衡代码膨胀带来的副作用，是否能接受一定的膨胀，需要精确评估，构建函数调用频率与其静态调用位置的矩阵，计算收益比如平均执行一次的耗时是否减少，若收益为正且明显则可内联，否则不宜内联。

有些编译器为了简单处理，不会内联带静态变量的函数哪怕指令数很少，或者内联不太正确比如LLVM（详见下文）。其实单从技术上可以做到，不过要复杂些，复杂在于链接器的协作。为了保证函数级静态变量的语义，编译时要预留全局唯一标志与构造函数的占位符，在调用者体内插入对全局唯一标志的（位）判断（标志字的一位对应一个静态变量，表明是否已构造或初始化赋值）、构造函数调用/初始化赋值、置位标志，而链接时要确定全局唯一标志及构造函数的地址。静态变量、全局唯一标志放于可执行文件的数据区，全局唯一构造/初始化及析构函数放于代码区，具体布局位置可以灵活，比如. data. static_obj，. text. obj. ctor/dtor。如果这种函数性能影响较大需要内联优化，而编译器不支持，有个替代的办法是用全局变量或文件/类级别的静态变量，辅以对应标志处理一次性构造或初始化赋值（必要时将这处理封装为一个函数以确保目标函数被内联），可达到同样效果不足之处是作用域扩大了。

关于LLVM对于带静态变量的函数之内联的测验结果

posted @ 2023-11-16 23:32 春秋十二月阅读(217) | 评论 (0) | 编辑收藏

浅谈对称加密算法的软件实现

谈两个问题：高性能与安全性

先谈高性能：这里指代码实现层面（非数学优化层面），使用寄存器优化，即主密钥/轮密钥、敏感数据比如中间/临时变量必须存于寄存器，明文/密文放在内存（若有够用的寄存器则放寄存器），主密钥用特权寄存器（为支持长期存储，比如调试寄存器、MSR寄存器），轮密钥和敏感数据用通用寄存器。那么怎么做？稳妥快捷的方法是用汇编或内联汇编，手工编排寄存器即构建密钥与敏感数据到寄存器集合的映射，若用普通的汇编指令，则寄存器的映射比较自由；若用专用的加密指令，则映射相对受限。如果用高级语言比如c/c++开发，问题在于register关键字非强制生效，即使强制的，编译器优化（比如公共子表达式消除）产生的中间变量及寄存器分配策略不完全可控，需要修改编译器比如LLVM强制某些变量必须分配(特定的)寄存器，为通用性要从编程语言语法属性到目标机器代码生成都改动支持，这个方法实现成本有点大。下面是摘自LLVM X86RegisterInfo.td的部分寄存器

1 // 32-bit registers
  2 let SubRegIndices = [sub_16bit, sub_16bit_hi], CoveredBySubRegs = 1 in {
  3 def EAX : X86Reg<"eax", 0, [AX, HAX]>, DwarfRegNum<[-2, 0, 0]>;
  4 def EDX : X86Reg<"edx", 2, [DX, HDX]>, DwarfRegNum<[-2, 2, 2]>;
  5 def ECX : X86Reg<"ecx", 1, [CX, HCX]>, DwarfRegNum<[-2, 1, 1]>;
  6 def EBX : X86Reg<"ebx", 3, [BX, HBX]>, DwarfRegNum<[-2, 3, 3]>;
  7 def ESI : X86Reg<"esi", 6, [SI, HSI]>, DwarfRegNum<[-2, 6, 6]>;
  8 def EDI : X86Reg<"edi", 7, [DI, HDI]>, DwarfRegNum<[-2, 7, 7]>;
  9 def EBP : X86Reg<"ebp", 5, [BP, HBP]>, DwarfRegNum<[-2, 4, 5]>;
10 def ESP : X86Reg<"esp", 4, [SP, HSP]>, DwarfRegNum<[-2, 5, 4]>;
11 def EIP : X86Reg<"eip", 0, [IP, HIP]>, DwarfRegNum<[-2, 8, 8]>;
12 }
13
14 // X86-64 only, requires REX
15 let SubRegIndices = [sub_16bit, sub_16bit_hi], CoveredBySubRegs = 1 in {
16 def R8D  : X86Reg<"r8d",   8, [R8W,R8WH]>;
17 def R9D  : X86Reg<"r9d",   9, [R9W,R9WH]>;
18 def R10D : X86Reg<"r10d", 10, [R10W,R10WH]>;
19 def R11D : X86Reg<"r11d", 11, [R11W,R11WH]>;
20 def R12D : X86Reg<"r12d", 12, [R12W,R12WH]>;
21 def R13D : X86Reg<"r13d", 13, [R13W,R13WH]>;
22 def R14D : X86Reg<"r14d", 14, [R14W,R14WH]>;
23 def R15D : X86Reg<"r15d", 15, [R15W,R15WH]>;
24 }
25
26 // 64-bit registers, X86-64 only
27 let SubRegIndices = [sub_32bit] in {
28 def RAX : X86Reg<"rax", 0, [EAX]>, DwarfRegNum<[0, -2, -2]>;
29 def RDX : X86Reg<"rdx", 2, [EDX]>, DwarfRegNum<[1, -2, -2]>;
30 def RCX : X86Reg<"rcx", 1, [ECX]>, DwarfRegNum<[2, -2, -2]>;
31 def RBX : X86Reg<"rbx", 3, [EBX]>, DwarfRegNum<[3, -2, -2]>;
32 def RSI : X86Reg<"rsi", 6, [ESI]>, DwarfRegNum<[4, -2, -2]>;
33 def RDI : X86Reg<"rdi", 7, [EDI]>, DwarfRegNum<[5, -2, -2]>;
34 def RBP : X86Reg<"rbp", 5, [EBP]>, DwarfRegNum<[6, -2, -2]>;
35 def RSP : X86Reg<"rsp", 4, [ESP]>, DwarfRegNum<[7, -2, -2]>;
36
37 // These also require REX.
38 def R8  : X86Reg<"r8",   8, [R8D]>,  DwarfRegNum<[ 8, -2, -2]>;
39 def R9  : X86Reg<"r9",   9, [R9D]>,  DwarfRegNum<[ 9, -2, -2]>;
40 def R10 : X86Reg<"r10", 10, [R10D]>, DwarfRegNum<[10, -2, -2]>;
41 def R11 : X86Reg<"r11", 11, [R11D]>, DwarfRegNum<[11, -2, -2]>;
42 def R12 : X86Reg<"r12", 12, [R12D]>, DwarfRegNum<[12, -2, -2]>;
43 def R13 : X86Reg<"r13", 13, [R13D]>, DwarfRegNum<[13, -2, -2]>;
44 def R14 : X86Reg<"r14", 14, [R14D]>, DwarfRegNum<[14, -2, -2]>;
45 def R15 : X86Reg<"r15", 15, [R15D]>, DwarfRegNum<[15, -2, -2]>;
46 def RIP : X86Reg<"rip",  0, [EIP]>,  DwarfRegNum<[16, -2, -2]>;
47 }
48

49 // XMM Registers, used by the various SSE instruction set extensions.
50 def XMM0: X86Reg<"xmm0", 0>, DwarfRegNum<[17, 21, 21]>;
51 def XMM1: X86Reg<"xmm1", 1>, DwarfRegNum<[18, 22, 22]>;
52 def XMM2: X86Reg<"xmm2", 2>, DwarfRegNum<[19, 23, 23]>;
53 def XMM3: X86Reg<"xmm3", 3>, DwarfRegNum<[20, 24, 24]>;
54 def XMM4: X86Reg<"xmm4", 4>, DwarfRegNum<[21, 25, 25]>;
55 def XMM5: X86Reg<"xmm5", 5>, DwarfRegNum<[22, 26, 26]>;
56 def XMM6: X86Reg<"xmm6", 6>, DwarfRegNum<[23, 27, 27]>;
57 def XMM7: X86Reg<"xmm7", 7>, DwarfRegNum<[24, 28, 28]>;
58
59 // X86-64 only
60 def XMM8:  X86Reg<"xmm8",   8>, DwarfRegNum<[25, -2, -2]>;
61 def XMM9:  X86Reg<"xmm9",   9>, DwarfRegNum<[26, -2, -2]>;
62 def XMM10: X86Reg<"xmm10", 10>, DwarfRegNum<[27, -2, -2]>;
63 def XMM11: X86Reg<"xmm11", 11>, DwarfRegNum<[28, -2, -2]>;
64 def XMM12: X86Reg<"xmm12", 12>, DwarfRegNum<[29, -2, -2]>;
65 def XMM13: X86Reg<"xmm13", 13>, DwarfRegNum<[30, -2, -2]>;
66 def XMM14: X86Reg<"xmm14", 14>, DwarfRegNum<[31, -2, -2]>;
67 def XMM15: X86Reg<"xmm15", 15>, DwarfRegNum<[32, -2, -2]>;
68
69 def XMM16:  X86Reg<"xmm16", 16>, DwarfRegNum<[67, -2, -2]>;
70 def XMM17:  X86Reg<"xmm17", 17>, DwarfRegNum<[68, -2, -2]>;
71 def XMM18:  X86Reg<"xmm18", 18>, DwarfRegNum<[69, -2, -2]>;
72 def XMM19:  X86Reg<"xmm19", 19>, DwarfRegNum<[70, -2, -2]>;
73 def XMM20:  X86Reg<"xmm20", 20>, DwarfRegNum<[71, -2, -2]>;
74 def XMM21:  X86Reg<"xmm21", 21>, DwarfRegNum<[72, -2, -2]>;
75 def XMM22:  X86Reg<"xmm22", 22>, DwarfRegNum<[73, -2, -2]>;
76 def XMM23:  X86Reg<"xmm23", 23>, DwarfRegNum<[74, -2, -2]>;
77 def XMM24:  X86Reg<"xmm24", 24>, DwarfRegNum<[75, -2, -2]>;
78 def XMM25:  X86Reg<"xmm25", 25>, DwarfRegNum<[76, -2, -2]>;
79 def XMM26:  X86Reg<"xmm26", 26>, DwarfRegNum<[77, -2, -2]>;
80 def XMM27:  X86Reg<"xmm27", 27>, DwarfRegNum<[78, -2, -2]>;
81 def XMM28:  X86Reg<"xmm28", 28>, DwarfRegNum<[79, -2, -2]>;
82 def XMM29:  X86Reg<"xmm29", 29>, DwarfRegNum<[80, -2, -2]>;
83 def XMM30:  X86Reg<"xmm30", 30>, DwarfRegNum<[81, -2, -2]>;
84 def XMM31:  X86Reg<"xmm31", 31>, DwarfRegNum<[82, -2, -2]>;
85
86 // YMM0-15 registers, used by AVX instructions and
87 // YMM16-31 registers, used by AVX-512 instructions.
88 let SubRegIndices = [sub_xmm] in {
89   foreach  Index = 0-31 in {
90     def YMM#Index : X86Reg<"ymm"#Index, Index, [!cast("XMM"#Index)]>,
91                     DwarfRegAlias("XMM"#Index)>;
92   }
93 }
94
95 // ZMM Registers, used by AVX-512 instructions.
96 let SubRegIndices = [sub_ymm] in {
97   foreach  Index = 0-31 in {
98     def ZMM#Index : X86Reg<"zmm"#Index, Index, [!cast("YMM"#Index)]>,
99                     DwarfRegAlias("XMM"#Index)>;
100   }
101 }
102

103 // Debug registers
104 def DR0  : X86Reg<"dr0",   0>;
105 def DR1  : X86Reg<"dr1",   1>;
106 def DR2  : X86Reg<"dr2",   2>;
107 def DR3  : X86Reg<"dr3",   3>;
108 def DR4  : X86Reg<"dr4",   4>;
109 def DR5  : X86Reg<"dr5",   5>;
110 def DR6  : X86Reg<"dr6",   6>;
111 def DR7  : X86Reg<"dr7",   7>;
112 def DR8  : X86Reg<"dr8",   8>;
113 def DR9  : X86Reg<"dr9",   9>;
114 def DR10 : X86Reg<"dr10", 10>;
115 def DR11 : X86Reg<"dr11", 11>;
116 def DR12 : X86Reg<"dr12", 12>;
117 def DR13 : X86Reg<"dr13", 13>;
118 def DR14 : X86Reg<"dr14", 14>;
119 def DR15 : X86Reg<"dr15", 15>;
120

121 def GR32 : RegisterClass<"X86", [i32], 32,
122                          (add EAX, ECX, EDX, ESI, EDI, EBX, EBP, ESP,
123                               R8D, R9D, R10D, R11D, R14D, R15D, R12D, R13D)>;
124
125 // GR64 - 64-bit GPRs. This oddly includes RIP, which isn't accurate, since
126 // RIP isn't really a register and it can't be used anywhere except in an
127 // address, but it doesn't cause trouble.
128 // FIXME: it *does* cause trouble - CheckBaseRegAndIndexReg() has extra
129 // tests because of the inclusion of RIP in this register class.
130 def GR64 : RegisterClass<"X86", [i64], 64,
131                          (add RAX, RCX, RDX, RSI, RDI, R8, R9, R10, R11,
132                               RBX, R14, R15, R12, R13, RBP, RSP, RIP)>;

再谈安全性：为保障安全就复杂了，由于密钥及敏感数据存于寄存器，首先要防止寄存器交换/拷贝到内存（为避免读取内存的冷启动攻击、基于cache的侧信道攻击）的一切可能因素，比如进程调度、由信号或异步中断引起的处理器模式切换、系统休眠，如果在用户态实现加解密，就避免不了被调度或切换，因为单核上不可能只运行加解密进程，所以得实现在内核态。这样一来就要在加解密中禁止抢占与中断，考虑到系统响应，禁止的粒度不能过大最小为一个分组，分组加解密前禁止抢占与中断（比如调用linux内核接口preempt_disable、local_irq_save），解除禁止（比如调用linux内核接口preempt_enable、local_irq_restore）前必须清零寄存器。在系统休眠时，禁止寄存器复制到内存，休眠恢复时在所有用户态进程恢复前执行密钥初始化，同理系统启动时的密钥初始化也得在用户态进程运行前执行。其次要防止其它用户态进程/内核线程/中断服务程序读写寄存器尤其特权寄存器（为避免用户态或内核态rootkit），所以要修改内核，过滤相关系统调用比如linux的ptrace，过滤相关内核函数比如linux的native_set_debugreg/native_get_debugreg。对于不可屏蔽的中断靠禁止是无效的，只能修改中断处理程序避免寄存器中的密钥数据被扩散到内存，比如在中断处理函数入口处清零相关寄存器。综上基于已知代码修改的防御不能防御恶意加载/修改代码之类的攻击，比如动态安装的内核模块/驱动，但可有效防御冷启动攻击、只读DMA攻击、基于cache的侧信道攻击、用户态权限的软件攻击、内核态的仅运行已有代码的软件攻击

posted @ 2023-11-09 16:39 春秋十二月阅读(4526) | 评论 (0) | 编辑收藏

Windows异常分发与子系统图表集 -- 摘自Windows内核原理与实现

posted @ 2023-10-24 15:25 春秋十二月阅读(179) | 评论 (0) | 编辑收藏

浅谈图论在寄存器分配中的应用

1. 区间图：用于局部寄存器分配，基本块内的每个活跃范围看作一个区间（最早定义位置+最新使用位置），所有活跃范围构成区间图。区间图是一种不精确的冲突图（因为高估了活跃范围的范围而导致伪冲突，比如认为一个复制操作连接的或两个源相同目标不同的复制操作产生重叠的两个活跃范围冲突，但实际没有冲突），优势在于着色是P（复杂度O(|V|)或O(|E|)）而非NP问题。llvm早期的线性扫描分配器是基于区间图在全局的扩展，比较适用于JIT编译（减少编译时间）

2. 一般图：用于全局寄存器分配，是一种精确的冲突图（由一组定义与一组使用构成的网络）。优势在于努力最小化溢出活跃范围而生成高效执行的代码，但会牺牲编译时间。llvm的greedy寄存器分配是基于一般图的代表。编译器使用的冲突图可能会将机器约束条件比如多寄存器值/调用约定编码进去而存在重复边，导致不满足图论中的简单图定义，故这里采用一般图

3. 弦图：定义详见https://oi-wiki.org/graph/chord。基于静态单赋值形式名建立的冲突图是弦图。优势在于可以做到最佳着色（复杂度O(|V|+|E|)）而非启发式（基于一般图的全局寄存器分配使用启发式），利于减少寄存器压力。劣势在于必须将指派寄存器后的仍然为静态单赋值代码转换为机器码，而这种转换可能增加寄存器压力，以及插入一些可能非必要的复制操作，若复制操作实现的数据流与ssa phi函数对应，则分配器无法合并这种复制，这将破坏弦图的性质

4. 冲突图拆分：查找其中的团分割即连通子图，移除它划分得到不相交的一些子图，这样一来，各子图可独立着色（有点类似活跃范围拆分）而利于减少寄存器压力，另外实现上还能节省下三角布尔矩阵（用于快速判断两结点是否冲突）的规模

#############################

寄存器分配与图论的染色理论相关。其它的比如常量传播与格代数及不动点相关，循环优化与多面体、矩阵相关。这三方面是我目前看到的编译器所用数学理论

posted @ 2023-10-04 13:08 春秋十二月阅读(3793) | 评论 (0) | 编辑收藏

忙表达式数据流分析示例

posted @ 2023-09-30 08:47 春秋十二月阅读(82) | 评论 (0) | 编辑收藏

基于X509证书的身份认证思考小结

有单向、双向、三向3种认证方式，前两者必须检查时间戳以防重放攻击，单向因为只有一个消息传递，如果仅靠一次性随机数是无法判断消息是否重放。双向有两个消息传递，一来一回，仅靠一次性随机数只能检测到发响应那方的重放。最后者则不必，可仅通过一次性随机数检测自己是否遭遇重放攻击，因为接收第二个消息的那方，通过判断第二个消息中随机数是否等于自己先前已发送第一个消息中的那个，若不等于则为重放，若等于则发第三个确认消息给对方，对方收到并判断确认消息中的随机数是否等于先前它已发送第二个消息中的随机数，若等于则说明第它收到的第一个消息的确是另一方发送的即非重放，否则为重放。因此三向认证可不必同步双方时钟。但正因为不强制检查时间戳而可能导致中间人攻击：假设通信双方为A、B，中间人为C，攻击步骤如下

1. C与B认证时，发送先前已截获的A到B请求消息给B

2. 截获并存储B到A的响应消息x，但不转发，开始与A认证

3. 收到A的请求消息后，解密x取出其中的随机数Rb作为响应给A消息中的随机数，用自己私钥签署整个消息后发给A

4. 收到并转发A的确认消息给B

以上完成后，C就能冒充A与B通信了。一种简单的改进方法是先用对方的公钥加密消息中的随机数，再用自己的私钥签署整个消息。关于网络协议的安全性分析，主流方法是形式化分析，可以借助相关工具来验证找出漏洞

posted @ 2023-09-30 08:00 春秋十二月阅读(401) | 评论 (0) | 编辑收藏

浅谈密码学几点安全性分析

1. 对于RSA，给定大整数n分解的一对素因子p和q，p或q是否素数决定不了安全性，但决定算法的正确性，也就是说p或q不能为合数，而安全性取决于n的位数及p、q的距离，n越大则难于素因子分解（因为素数测试是一个P问题，而因子分解是一个NP问题，其耗时是关于n的指数），|p - q|要大是为抵抗一种特殊因子分解攻击，论证如下：由(p+q)²/4 - n = (p+q)²/4 - pq = (p-q)²/4，若|p - q|小，则(p-q)²/4也小，因此(p+q)²/4稍大于n，(p+q)/2稍大于n^1/2即根号n。可得n的如下分解法：a) 先顺序检查大于n^1/2的每一整数x，直至找到一个x使得x² - n是某一整数y的平方；b) 再由x² - n = y² 得 n = (x+y)(x-y)。另外，p - 1和q - 1都应有大素因子（所有因子皆是大素数），以抵抗可能的重复加密攻击（重复加密较少步后可恢复出明文）

2. 对于DH密钥交换，通常选择阶为素数的有限循环(子)群，这时素数决定了安全性。因素数不能再因子分解，故避免了针对阶为合数的质因子分解且利用中国剩余定理求离散对数的(已知最好)攻击。具体讲就是为了防index-calculus方法求解离散对数，底层循环群G的素数模p要足够大，长度1024位可实现80位安全等级，长度3072位可实现128位安全等级；另为了防Pohlig-Hellman攻击，G的阶p-1必须不能因式分解为全部都是小整数的素数因子，且为了p-1的每个因子构成的子群防baby-step giant-step或Pollards's rho攻击，要求对80位安全等级而言，p-1的最小素因子必须至少为160位，而对128位安全等级，其至少为256位

3. 对于Hash函数，安全性要求有三点：第一是单向性，由于压缩函数理论上存在碰撞，因此单向性是指计算不可行，为什么要单向性？因为若不单向，则可从结果比如签名逆出原文消息；第二是抗弱冲突性即第1类生日攻击，计算不可行；第三是抗强冲突性即第2类生日攻击，计算不可行。这三点要求，取决于压缩函数是否能抗差分、线性等密码分析

4. 周知Shamir门限方案基于多项式的拉格朗日插值公式，普遍的设计采用GF(q)域上的多项式，秘密s为f(0)，q是一个大于n的大素数（n是s被分成的部分数）。正常来讲，参与者个数必须至少是设计时的k，才能恢复出正确的s。如果个数少于k比如k-1，则只能猜测s0=f(0)以构建第k个方程，那么恢复得到的多项式g(x)等同设计时的多项式f(x)的概率是1/q。因为g(x)的项系数可以看作关于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q为素数，故依模剩余系遍历定理，当s0取GF(q)一值时，则h(s0)唯一对应另一值。所以h(s0)等于f(0)的概率为1/q。由此可见，当q取80位以上，敌手攻击概率不大于1/2⁸⁰，这已经很低了。这种门限方案如同RSA加密，再次佐证了素数越大安全性越高

5. PGP是密码学经典应用，体现在首先支持保密与认证业务的正交，即独立或组合，且组合时按认证、压缩、加密的顺序，这个顺序是经考究有优势的；其次会话密钥是一次性的，由安全伪随机数生成器生成，且按公钥加密；最后使用自研的密钥环与信任网解决公钥管理问题。理论本质上，PGP提供的是一种保密认证业务的通用框架，因为具体的对称加密算法、随机数生成、公钥算法，都可依需要灵活选配扩展。PGP有两个问题跟组合与概率相关，一个是算密钥环N个公钥中，密钥ID(64位)至少有两个重复的概率？设所求概率为p，先算任意两个不重复的概率q，令m=2⁶⁴，则q=m!/((m-N)!*m^N)，则p=1-q，不难看出，N越小则q越大则p越小，因实际应用N<<m，故p非常小可忽略，即PGP取公钥中最低64有效位作密钥ID，是可行的。另一个是签名摘要暴露了前16位明文，对哈希函数安全的影响有多大？这问题意思应该是敌手拿到消息后但没发送方的私钥作签名，只能穷举变换原消息并求哈希值，使之与消息摘要剩余位组相等。这本质是求两类生日攻击碰撞概率大于0.5时所需的输入量。在仅认证模式中，抗弱碰撞计算量降低为原来的1/2¹⁶，抗强碰撞计算量至少降低为原来的1/2⁸。另外，考虑到这16位明文可能的特殊性，有没更快的代数攻击，需进一步研究

posted @ 2023-09-28 08:04 春秋十二月阅读(2997) | 评论 (0) | 编辑收藏

浅谈Linux共享库库函数挂钩检测

Linux共享库库函数挂钩主流两种方法。一是替换函数对应的GOT/PLT条目，GOT/PLT原理类似Windows的IAT；二是inline挂钩，即替换函数序言的几个字节（x86是5或7字节）为jmp/call，若发现稍远处有jmp或call（前提在入口基本块内，若不在入口基本块内要修改分支控制条件，这有点复杂也无必要），则其目标地址可被替换，这样就不用替换序言的几字节了。Windows的IAT挂钩检测很方便，因为dll的baseaddr及size可通过API VirtualQueryEx（https://learn.microsoft.com/zh-cn/windows/win32/api/memoryapi/nf-memoryapi-virtualqueryex）或toolhelp库的Module32First/Module32Next（https://learn.microsoft.com/zh-cn/windows/win32/api/tlhelp32/nf-tlhelp32-module32first）接口来获取。同理linux也可以拿到有两种方法，一种是读/proc/pid/maps（这里pid为实际目标进程号）获取so库代码段的baseaddr和size，另一种用dl_iterate_phdr（https://man7.org/linux/man-pages/man3/dl_iterate_phdr.3.html）拿到代码段（pt_load类型+可执行标志）的baseaddr及size。只要模块(代码段)的baseaddr及size确定了，检测方法同IAT，即看替换函数地址是否不在代码段空间内，若不在或地址不是原函数则认为被挂钩了，否则需进一步用针对inline挂钩法的检测处理，见下文描述。另外dladdr（https://man7.org/linux/man-pages/man3/dladdr.3.html）判断一个地址是否跟一个so库及符号相关，因此也可用于检测挂钩。如果是inline挂钩法，那么分析函数入口基本块内（不管替换序言几字节还是已有jmp/call目标地址，都在入口基本块）jmp/call的目标地址（最好用成熟的反汇编引擎分析，比如llvm的mc库反汇编功能，或https://salsa.debian.org/debian/distorm3），看是否超出so库的代码段空间

posted @ 2023-09-26 16:47 春秋十二月阅读(2127) | 评论 (0) | 编辑收藏

仅列出标题

常用链接

留言簿(63)

随笔分类(155)

随笔档案(156)

文章分类(30)

关注的开源项目

最新随笔

积分与排名

最新评论

阅读排行榜

评论排行榜