Rating: 4.0
# Day 10 - ChristmaSSE KeyGen - rev, math
> I ran this program but it never finished... maybe my computer is too slow. Maybe yours is faster?
Download: [326c15f8884fcc13d18a60e2fb933b0e35060efa8a44214e06d589e4e235fe34](https://advent2019.s3.amazonaws.com/326c15f8884fcc13d18a60e2fb933b0e35060efa8a44214e06d589e4e235fe34)
Mirror: [326c15f8884fcc13d18a60e2fb933b0e35060efa8a44214e06d589e4e235fe34](./images/326c15f8884fcc13d18a60e2fb933b0e35060efa8a44214e06d589e4e235fe34)
# Initial Analysis
This problem is an x86 reversing challenge. Opening up the binary in your favorite decompiler you'll see that the main function uses a lot of packed dword instructions. The main function is short enough, so I've included it below (output from `objdump`)
```
0000000000400570 <main>:
400570: 66 0f 6f 05 08 0b 20 movdqa 0x200b08(%rip),%xmm0 # 601080 <data+0x40>
400577: 00
400578: 66 0f 70 d8 54 pshufd $0x54,%xmm0,%xmm3
40057d: 66 0f 70 d0 51 pshufd $0x51,%xmm0,%xmm2
400582: 66 0f 70 c8 45 pshufd $0x45,%xmm0,%xmm1
400587: 66 0f 70 c0 15 pshufd $0x15,%xmm0,%xmm0
40058c: 31 c0 xor %eax,%eax
40058e: 48 b9 15 81 e9 7d f4 movabs $0x112210f47de98115,%rcx
400595: 10 22 11
400598: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
40059f: 00
4005a0: 0f ae f8 sfence
4005a3: 66 44 0f 6f 0d 94 0a movdqa 0x200a94(%rip),%xmm9 # 601040 <data>
4005aa: 20 00
4005ac: 66 41 0f 70 f1 00 pshufd $0x0,%xmm9,%xmm6
4005b2: 66 0f 38 40 f3 pmulld %xmm3,%xmm6
4005b7: 66 45 0f 70 e1 55 pshufd $0x55,%xmm9,%xmm12
4005bd: 66 44 0f 38 40 e2 pmulld %xmm2,%xmm12
4005c3: 66 44 0f fe e6 paddd %xmm6,%xmm12
4005c8: 66 44 0f 6f 15 7f 0a movdqa 0x200a7f(%rip),%xmm10 # 601050 <data+0x10>
4005cf: 20 00
4005d1: 66 45 0f 70 c2 00 pshufd $0x0,%xmm10,%xmm8
4005d7: 66 44 0f 38 40 c3 pmulld %xmm3,%xmm8
4005dd: 66 44 0f 6f 2d 7a 0a movdqa 0x200a7a(%rip),%xmm13 # 601060 <data+0x20>
4005e4: 20 00
4005e6: 66 45 0f 70 dd 00 pshufd $0x0,%xmm13,%xmm11
4005ec: 66 44 0f 38 40 db pmulld %xmm3,%xmm11
4005f2: 66 44 0f 6f 3d 75 0a movdqa 0x200a75(%rip),%xmm15 # 601070 <data+0x30>
4005f9: 20 00
4005fb: 66 45 0f 70 f7 00 pshufd $0x0,%xmm15,%xmm14
400601: 66 44 0f 38 40 f3 pmulld %xmm3,%xmm14
400607: 66 41 0f 70 e9 aa pshufd $0xaa,%xmm9,%xmm5
40060d: 66 0f 38 40 e9 pmulld %xmm1,%xmm5
400612: 66 41 0f 70 d9 ff pshufd $0xff,%xmm9,%xmm3
400618: 66 0f 38 40 d8 pmulld %xmm0,%xmm3
40061d: 66 0f fe dd paddd %xmm5,%xmm3
400621: 66 41 0f fe dc paddd %xmm12,%xmm3
400626: 66 41 0f 70 ea 55 pshufd $0x55,%xmm10,%xmm5
40062c: 66 0f 38 40 ea pmulld %xmm2,%xmm5
400631: 66 41 0f fe e8 paddd %xmm8,%xmm5
400636: 66 41 0f 70 fd 55 pshufd $0x55,%xmm13,%xmm7
40063c: 66 0f 38 40 fa pmulld %xmm2,%xmm7
400641: 66 41 0f 70 e7 55 pshufd $0x55,%xmm15,%xmm4
400647: 66 0f 38 40 e2 pmulld %xmm2,%xmm4
40064c: 66 41 0f 70 f2 aa pshufd $0xaa,%xmm10,%xmm6
400652: 66 0f 38 40 f1 pmulld %xmm1,%xmm6
400657: 66 41 0f 70 d2 ff pshufd $0xff,%xmm10,%xmm2
40065d: 66 0f 38 40 d0 pmulld %xmm0,%xmm2
400662: 66 0f fe d6 paddd %xmm6,%xmm2
400666: 66 0f fe d5 paddd %xmm5,%xmm2
40066a: 66 41 0f fe fb paddd %xmm11,%xmm7
40066f: 66 41 0f 70 ed aa pshufd $0xaa,%xmm13,%xmm5
400675: 66 0f 38 40 e9 pmulld %xmm1,%xmm5
40067a: 66 41 0f 70 f7 aa pshufd $0xaa,%xmm15,%xmm6
400680: 66 0f 38 40 f1 pmulld %xmm1,%xmm6
400685: 66 41 0f 70 cd ff pshufd $0xff,%xmm13,%xmm1
40068b: 66 0f 38 40 c8 pmulld %xmm0,%xmm1
400690: 66 0f fe cd paddd %xmm5,%xmm1
400694: 66 0f fe cf paddd %xmm7,%xmm1
400698: 66 41 0f fe e6 paddd %xmm14,%xmm4
40069d: 66 41 0f 70 ff ff pshufd $0xff,%xmm15,%xmm7
4006a3: 66 0f 38 40 f8 pmulld %xmm0,%xmm7
4006a8: 66 0f fe fe paddd %xmm6,%xmm7
4006ac: 66 0f fe fc paddd %xmm4,%xmm7
4006b0: 66 0f 6f 05 c8 09 20 movdqa 0x2009c8(%rip),%xmm0 # 601080 <data+0x40>
4006b7: 00
4006b8: 66 0f 70 e0 aa pshufd $0xaa,%xmm0,%xmm4
4006bd: 66 0f 70 e8 00 pshufd $0x0,%xmm0,%xmm5
4006c2: ba e8 03 00 00 mov $0x3e8,%edx
4006c7: 66 0f 6f c7 movdqa %xmm7,%xmm0
4006cb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
4006d0: 66 0f 6f f4 movdqa %xmm4,%xmm6
4006d4: 66 0f 66 f3 pcmpgtd %xmm3,%xmm6
4006d8: 66 0f fe f5 paddd %xmm5,%xmm6
4006dc: 66 0f 38 40 f4 pmulld %xmm4,%xmm6
4006e1: 66 0f fa de psubd %xmm6,%xmm3
4006e5: 66 0f 6f f4 movdqa %xmm4,%xmm6
4006e9: 66 0f 66 f2 pcmpgtd %xmm2,%xmm6
4006ed: 66 0f fe f5 paddd %xmm5,%xmm6
4006f1: 66 0f 38 40 f4 pmulld %xmm4,%xmm6
4006f6: 66 0f fa d6 psubd %xmm6,%xmm2
4006fa: 66 0f 6f f4 movdqa %xmm4,%xmm6
4006fe: 66 0f 66 f1 pcmpgtd %xmm1,%xmm6
400702: 66 0f fe f5 paddd %xmm5,%xmm6
400706: 66 0f 38 40 f4 pmulld %xmm4,%xmm6
40070b: 66 0f fa ce psubd %xmm6,%xmm1
40070f: 66 0f 6f f4 movdqa %xmm4,%xmm6
400713: 66 0f 66 f0 pcmpgtd %xmm0,%xmm6
400717: 66 0f fe f5 paddd %xmm5,%xmm6
40071b: 66 0f 38 40 f4 pmulld %xmm4,%xmm6
400720: 66 0f fa c6 psubd %xmm6,%xmm0
400724: 83 c2 ff add $0xffffffff,%edx
400727: 75 a7 jne 4006d0 <main+0x160>
400729: 48 83 c0 01 add $0x1,%rax
40072d: 48 39 c8 cmp %rcx,%rax
400730: 0f 85 6a fe ff ff jne 4005a0 <main+0x30>
400736: 48 83 ec 18 sub $0x18,%rsp
40073a: 66 0f 7f 1c 24 movdqa %xmm3,(%rsp)
40073f: 66 0f 7f 54 24 10 movdqa %xmm2,0x10(%rsp)
400745: 66 0f 7f 4c 24 20 movdqa %xmm1,0x20(%rsp)
40074b: 66 0f 7f 44 24 30 movdqa %xmm0,0x30(%rsp)
400751: 31 c0 xor %eax,%eax
400753: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40075a: 00 00 00
40075d: 0f 1f 00 nopl (%rax)
400760: 0f b6 0c 44 movzbl (%rsp,%rax,2),%ecx
400764: 30 88 90 10 60 00 xor %cl,0x601090(%rax)
40076a: 0f b6 4c 44 01 movzbl 0x1(%rsp,%rax,2),%ecx
40076f: 30 88 91 10 60 00 xor %cl,0x601091(%rax)
400775: 48 83 c0 02 add $0x2,%rax
400779: 48 83 f8 20 cmp $0x20,%rax
40077d: 75 e1 jne 400760 <main+0x1f0>
40077f: be 54 08 40 00 mov $0x400854,%esi
400784: bf 01 00 00 00 mov $0x1,%edi
400789: ba 05 00 00 00 mov $0x5,%edx
40078e: 31 c0 xor %eax,%eax
400790: e8 cb fc ff ff callq 400460 <write@plt>
400795: be 90 10 60 00 mov $0x601090,%esi
40079a: bf 01 00 00 00 mov $0x1,%edi
40079f: ba 20 00 00 00 mov $0x20,%edx
4007a4: 31 c0 xor %eax,%eax
4007a6: e8 b5 fc ff ff callq 400460 <write@plt>
4007ab: be 5a 08 40 00 mov $0x40085a,%esi
4007b0: bf 01 00 00 00 mov $0x1,%edi
4007b5: ba 02 00 00 00 mov $0x2,%edx
4007ba: 31 c0 xor %eax,%eax
4007bc: e8 9f fc ff ff callq 400460 <write@plt>
4007c1: 31 ff xor %edi,%edi
4007c3: e8 a8 fc ff ff callq 400470 <exit@plt>
4007c8: 0f 1f 84 00 00 00 00 nopl 0x0(%rax,%rax,1)
4007cf: 00
```
The packed dword instructions (`pshufd`, `pmulld`, `paddd`, `psubd`) all perform their respective operaions on the DWORD (4-byte) components of each `xmm` register. For example, `paddd` is effectively doing four add operations - one each on the 4-byte chunks of the `xmm` registters. For our purposes, I treated each `xmm` as a 4-long integer array when doing my disassembly.
Speaking of, here is roughly the pseudocode I came up with for the main() function:
```
xmm0 = (0,0,0,1)
xmm1 = (0,0,1,0)
xmm2 = (0,1,0,0)
xmm3 = (1,0,0,0)
for i = 0..1234567890123456789
// these are done concurrently, not consecutively
xmm0 := xmm0 * (10,10,10,10) + xmm1 * (f,f,f,f) + xmm2 * (e,e,e,e) + xmm3 * (d,d,d,d)
xmm1 := xmm0 * (c,c,c,c) + xmm1 * (b,b,b,b) + xmm2 * (a,a,a,a) + xmm3 * (9,9,9,9)
xmm2 := xmm0 * (8,8,8,8) + xmm1 * (7,7,7,7) + xmm2 * (6,6,6,6) + xmm3 * (5,5,5,5)
xmm3 := xmm0 * (4,4,4,4) + xmm1 * (3,3,3,3) + xmm2 * (2,2,2,2) + xmm3 * (1,1,1,1)
// reduces to modular arithmetic
for j = 0..1000
if xmm0 > 0x0096433D
xmm0 -= 0x0096433D
if xmm1 > 0x0096433D
xmm1 -= 0x0096433D
if xmm2 > 0x0096433D
xmm2 -= 0x0096433D
if xmm3 > 0x0096433D
xmm3 -= 0x0096433D
```
The final state of these four registers is then XORed with data within the binary to give a flag.
## Matrix Multiplication
Simplifying the instructions above a bit, we can treat each register as one row in a 4x4 matrix. Furthermore, since we're just doing repeated multiplications, we're effectively raising the matrix to the 1234567890123456789th power. One technique for speeding up large exponentiation modulo a number is the [square-and-multiply method](https://en.wikipedia.org/wiki/Exponentiation_by_squaring). I wrote [a short script](./solutions/day10_solver.py) which gives the answer in a second or two instead of the long running time of the original program. This result is the inner portion of the `AOTW{..}` flag.
```
$ ./solver.py
b'M4tr1x_3xp0n3nti4t1on_5728391723'
```
