V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
MozzieW
V2EX  ›  问与答

看到隔壁讨论密码学,乘机问一个折腾几天没看懂的问题

  •  
  •   MozzieW · 168 天前 · 2253 次点击
    这是一个创建于 168 天前的主题,其中的信息可能已经有所发展或是发生改变。

    下面是简化的代码,描述的是解密的过程,我想知道对应加密的过程是怎么样的,没看懂这种逻辑的还原原理是什么

    uint32_t descrypt(byte[] block, byte[] key) {
    	// table_s5678 都是长度为 256 的四字节数组
        unsigned long table_s5[] = {0x21aa8423, 0x2fa1892a, 0x3dbc9e31, 0x33b79338,...};
        unsigned long table_s6[] = {0x5ee7493, 0xce07f9e, 0x17f26289, 0x1efc6984,...};
        unsigned long table_s7[] = {0xb33a6e73, 0xbe336078, 0xa9287265, 0xa4217c6e,...};
        unsigned long table_s8[] = {0xb4469bf0, 0xbf4b92fe, 0xa25c89ec, 0xa95180e2, ...}
    
        uint32_t ptr1 = 0;
        uint32_t ptr2 = 0;
        uint32_t ptr3 = 0;
        uint32_t ptr4 = 0;
        uint32_t ab;
       
        // 注意这是解密的逻辑
        // block 是明文,key 是密钥,两者各个字节先异或,然后在查表转换为四个字节的值
        ptr1 = table_s5[block[3] ^ key0[3]]; 
        ptr2 = table_s6[block[2] ^ key0[2]];
        ptr3 = table_s8[block[0] ^ key0[0]];
        ptr4 = table_s7[block[1] ^ key0[1]];
        // 面就是我不懂的地方:ab 是四个 long 的异或,怎么还原回四个 ptr ,如果不还原,对应加密又是怎么处理的
        ab = ptr1 ^ ptr2 ^ ptr3 ^ ptr4;
        return ab;
    

    我对比了 AES 、DES 等算法里面关于 S 盒的实现,没有发现这么复杂的,主要就是一个自己转四个字节,四个字节转异或,怎么也没弄懂原理是什么。如果有知道的请指教。

    更多:这个代码其实是苹果 FairPlay 的一部分,完整代码可以看这里( cycle 方法): https://github.com/FDH2/UxPlay/blob/c4fb40ee31b61b1b3b5ae406900af72edac2ca47/lib/playfair/omg_hax.c

    17 条回复    2024-07-09 16:59:50 +08:00
    EndlessMemory
        1
    EndlessMemory  
       168 天前
    扔给 GPT
    0o0O0o0O0o
        2
    0o0O0o0O0o  
       168 天前
    这种项目都是逆向得来的,可能是从高度混淆的程序的反编译结果中摸索提取出来的,可能是常见算法的一个变种,可能是白盒加密,我觉得实在没有必要搞清楚它是什么。
    0o0O0o0O0o
        3
    0o0O0o0O0o  
       168 天前
    而且你看你发的这个链接里的注释...
    // This looks right to me, at least for decrypt_kernel
    // round is 0..8?
    // This COULD just be Rijndael key expansion, but with a different set of S-boxes
    // This MIGHT just be AES, or some variant thereof.
    MozzieW
        4
    MozzieW  
    OP
       168 天前
    @EndlessMemory
    这个我已经看了好几天了,不是伸手就问。
    GPT 不行,给的实现都是照炒代码,匹配不上的。
    @0o0O0o0O0o
    说实话,这些注释我实际上没看,我看到是 java 代码,今天早上想起来,为了方便用了 C 的代码。不过,这些注释对我也没有什么意义,其他部分我已经搞定了,就是 SBox 的使用,我甚至不完整地测试了,应该可以生成逆向的 SBox 。问题就是卡在 Cycle 方法这里,也就是你猜测的 AES 的地方。但我确定不是,因为我怀疑过这个使用了某个成熟的算法的相关逻辑,所以把 AES 、DES 等 SBox 相关的逻辑都过了一遍,没有对上的。

    回到问题,就是其他 SBox 的流程至少我能看懂,也不算太复杂,但这个一个字节转四个字节,四个字节做异或的我没看懂原理,找个明白的人。
    billlee
        5
    billlee  
       168 天前   ❤️ 1
    这个结构和 mix columns 看起来挺像的?
    hcocoa
        6
    hcocoa  
       168 天前
    @MozzieW #4 查表的时候把 1 个字节变成 4 个字节,然后 4 个“1 字节扩展出来的 4 字节”异或。也就是原来 4 字节,出来还是 4 字节,信息量没有丢失,当然可以还原回去。
    MozzieW
        7
    MozzieW  
    OP
       168 天前
    @hcocoa 你这个说了不是和没说一样。。。这个重点是四个未知的值异或,无法从中分离出原来的值。就像四碗不同颜色的水混一起了,水当然在,问题是颜色怎么分出来。

    @billlee mix columns 是什么,有其他关键词吗?
    billlee
        8
    billlee  
       168 天前
    @MozzieW https://en.wikipedia.org/wiki/Rijndael_MixColumns

    4 个变量混在一起在某些情况下是可以分离的,只要这个混合满足可逆线性变换的要求
    wnck
        9
    wnck  
       168 天前
    如果关心的这个 S 盒是如何设计出来,这个挺复杂的,AES 算法被“某些机构”不信任的一个点就是 S 盒的生成没讲清楚,甚至被怀疑在算法上是存在后门的(比如看似复杂和随机性的计算其实存在一个绕过复杂的简便计算解法)。如果只是理解这种加密算法,S 盒和 S 盒的逆怎么计算,可以看线性代数和简单的数论知识。
    meeop
        10
    meeop  
       167 天前
    学习密码学不能看代码,代码是经过高度优化的,而不是易于理解的

    先看数学原理,然后拿纸算一算,搞清楚原理才能去看代码,一些语法问题可以问 gpt
    nomagick
        11
    nomagick  
       167 天前
    就是带字典的异或,四个字节一个 block ,每个位置字典不一样。

    加密也是相同的异或,异或的逆运算还是异或,异或两次等于本身。
    nomagick
        12
    nomagick  
       167 天前
    顺序反过来异或
    nomagick
        13
    nomagick  
       167 天前
    哦。。我说的不算,原谅我的无知。。
    0o0O0o0O0o
        14
    0o0O0o0O0o  
       167 天前   ❤️ 1
    @MozzieW #4

    > 也就是你猜测的 AES 的地方

    我没有猜测... #3 是那个作者的注释

    > 但我确定不是,因为我怀疑过这个使用了某个成熟的算法的相关逻辑,所以把 AES 、DES 等 SBox 相关的逻辑都过了一遍,没有对上的

    DRM 中广泛应用白盒加密,例如该类技术最早被提出时的简介:"The white-box model with initial attempts of white-box DES and AES implementations were first proposed by Chow, Eisen, Johnson and van Oorshot in 2003. The designs were based on representing the cipher as a network of lookup tables and obfuscating the tables by composing them with small (4- or 8-bit) random encodings. Such protection satisfied a property that each single obfuscated table individually does not contain any information about the secret key. Therefore, a potential attacker has to combine several tables in their analysis."

    所以问题来了,如何确定这些 table 不是"混淆"后的呢?用标准的流程去对照,那肯定是很难对上的。

    > ab 是四个 long 的异或,怎么还原回四个 ptr ,如果不还原,对应加密又是怎么处理的
    > 你这个说了不是和没说一样。。。这个重点是四个未知的值异或,无法从中分离出原来的值。就像四碗不同颜色的水混一起了,水当然在,问题是颜色怎么分出来。

    例如四个有效 byte 分别为 0x11 0x22 0x33 0x44 ,那么 0x00000011 ^ 0x00002200 ^ 0x00330000 ^ 0x44000000 丢失它们了吗? 0xabcd0011 ^ 0xabcd2200 ^ 0x0033abcd ^ 0x4400abcd 丢失了吗?如果你认同这个例子,那你再看一遍 @hcocoa 说的。

    我坚持 #2 的观点,一通分析,最后代码多半还是得这么写。。。如果你真的对这种挑战感兴趣,可以看最后一个链接,至少去掉编译器、代码混淆、反汇编反编译的影响,可以直接分析源码。

    - https://eprint.iacr.org/2013/523
    - https://crypto.stackexchange.com/search?q=white-box
    - https://segmentfault.com/a/1190000041023774/en
    - https://developer.apple.com/streaming/fps/
    - https://whibox.io/
    hcocoa
        15
    hcocoa  
       167 天前
    @0o0O0o0O0o #14 就是这个意思,只不过它的查表把每 bit 打散了,不像 0x00000011 这么规整,原理是一样的。这也就是 table_s5-s8 需要特殊设计,不是随机一串数字都行的。
    sujin190
        16
    sujin190  
       167 天前
    @MozzieW #7 我猜加密的时候有个 table_s1 table_s2 table_s3 table_s4 ,ab 是 4 个字节,key 也是 4 个字节,这样就可以用 descrypt 差不多算法来加密了,估计重点估计是这个 table1-8 是怎么构造出来的,单这样看估计确实看不出啥来也不符合逻辑
    MozzieW
        17
    MozzieW  
    OP
       167 天前
    @billlee 第一下查了感觉不行,后面根据其他人的回复找到了 Mix Columns 的查找表操作感觉真的可能是。

    @0o0O0o0O0o 这个问题是,一时上头想看怎么弄出加密逻辑,其他逻辑都感觉可以解决,就是这个四个字节异或代码+原理都没有看懂,想看究竟是一个什么东西

    根据提供的关键词,我找到了 AES 白盒实现的描述( GPT ),然后通过 Google 找到了 Golang 的 AES 实现( https://github.com/golang/go/blob/87ec2c959c73e62bfae230ef7efca11ec2a90804/src/crypto/aes/const.go ),第一次看到了使用四个字节的加密算法,相关代码( block.go)的解密逻辑实现逻辑也 UxPlay 一样。

    目前看,这个代码的逻辑是 Inverse MixColumns 操作,不过把矩阵计算使用预先计算生成的查找表实现。

    感谢🙏🙏🙏
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5214 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 03:46 · PVG 11:46 · LAX 19:46 · JFK 22:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.