# 1r-AES
## 問題
- 1ラウンドのAES実装がある(S-Box等ラウンド数以外は普通の実装)
- 1ラウンド=最終ラウンドでMC処理はなし
- 暗号化オラクルが与えられ、任意の平文＆暗号分ペアが手に入る(いくつでも)
- 与えられた暗号文を復号したい

## AES概要
AESは次の4つの処理から成るラウンドを繰り返す。
1. SubBytes
各バイトは、Sボックスと呼ばれる固定テーブルを使って非線形変換される。
2. ShiftRows
ステートの各行のバイトが左にシフトされる。シフト量は行番号に依存する。
3. MixColumns
各列のバイトを線形変換して混ぜ合わせる。各列は特定の定数行列との行列積に変換。
4. AddRoundKey
ラウンドキーと呼ばれるマスターキーから生成された鍵がステートにXOR演算で加えられる。

しかし、ラウンドの開始前に、AddRoundkeyが実行され、
最終ラウンドでは3のMixColumnsがスキップされる。

## 1ラウンドAES考察
1ラウンドAESは
AddRoundKey(-1)→SubBytes→ShiftRows→AddRoundKey(0)となる。
(与えられた実装でもそうなっているように)MixColumnsがないため、
16バイトの各バイト同士のかき混ぜ処理がない。
つまり、平文と暗号文はShiftRowsに注意してバイト位置で1:1対応する。

## 方針
SubBytes, ShiftRowsは逆変換が存在する。
最初と最後のXORする鍵を特定すればよい。
前の考察からバイト毎に独立しており、
最後のXORを決めれば最初のXORは自動的に決まる。

1つの平文暗号文ペアでは鍵候補がバイトごとに256通りあるが、
2つの平文暗号文ペアでは2通り、3つの平文暗号文ペアでは1通りに絞れる。
なので適当に3回問い合わせて鍵の内部状態を復元する。

## コード

from pwn import *
from Crypto.Util.number import *
import aes

FILE_NAME = 'server.py'
HOST = '34.170.146.252'
PORT = int(45518)
if len(sys.argv) > 1 and sys.argv[1] == 'r':
    conn = remote(HOST, PORT)
else:
    conn = process(['python3', FILE_NAME])

conn.recvuntil(b": ")
la = int(conn.recvline().strip(), 16).to_bytes(16, 'big')
print("la:",la)

conn.recvuntil(b"> ")
conn.sendline(b"00000000000000000000000000000000")
conn.recvuntil(b": ")
enc_msg1 = aes.bytes2matrix(int(conn.recvline().strip(), 16).to_bytes(16, 'big'))
print("enc_msg1:", enc_msg1)

conn.recvuntil(b"> ")
conn.sendline(b"11111111111111111111111111111111")
conn.recvuntil(b": ")
enc_msg2 = aes.bytes2matrix(int(conn.recvline().strip(), 16).to_bytes(16, 'big'))
print("enc_msg2:",enc_msg2)

conn.recvuntil(b"> ")
conn.sendline(b"22222222222222222222222222222222")
conn.recvuntil(b": ")
enc_msg3 = aes.bytes2matrix(int(conn.recvline().strip(), 16).to_bytes(16, 'big'))
print("enc_msg3:",enc_msg3)

key_pair1 = [[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()]] 
for key1 in range(0x100):
    tmp = [[0]*4,[0]*4,[0]*4,[0]*4]
    for i in range(4):
        for j in range(4):
            tmp[i][j] = enc_msg1[i][j] ^ key1
    aes.inv_shift_rows(tmp)
    aes.inv_sub_bytes(tmp)
    for i in range(4):
        for j in range(4):
            key_pair1[i][j].add((tmp[i][j] ^ 0x00, key1))

key_pair2 = [[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()]] 
for key1 in range(0x100):
    tmp = [[0]*4,[0]*4,[0]*4,[0]*4]
    for i in range(4):
        for j in range(4):
            tmp[i][j] = enc_msg2[i][j] ^ key1
    aes.inv_shift_rows(tmp)
    aes.inv_sub_bytes(tmp)
    for i in range(4):
        for j in range(4):
            key_pair2[i][j].add((tmp[i][j] ^ 0x11, key1))

key_pair3 = [[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()],[set(), set(), set(), set()]] 
for key1 in range(0x100):
    tmp = [[0]*4,[0]*4,[0]*4,[0]*4]
    for i in range(4):
        for j in range(4):
            tmp[i][j] = enc_msg3[i][j] ^ key1
    aes.inv_shift_rows(tmp)
    aes.inv_sub_bytes(tmp)
    for i in range(4):
        for j in range(4):
            key_pair3[i][j].add((tmp[i][j] ^ 0x22, key1))

key1 = [[0]*4,[0]*4,[0]*4,[0]*4]
key2 = [[0]*4,[0]*4,[0]*4,[0]*4]
for i in range(4):
    for j in range(4):
        key1[i][j] , key2[i][j] = list(key_pair1[i][j] & key_pair2[i][j] & key_pair3[i][j])[0]


key = os.getenv("KEY", "*** REDACTED ***").encode()
assert len(key) == 16

cipher = aes.AES(key)
cipher._key_matrices[0] = key1
aes.shift_rows(key2)
cipher._key_matrices[-1] = key2

print(cipher.decrypt_block(la))

## 感想
解いた後に他の方のWriteupを見たところ、z3を使った方法が多いようでした。
(非線形で使えると思って無かった)
ググってみると一つの平文暗号文ペアで解くような方法もあったりしたのでそのうち出題されそうだななんて思ったり。
https://eprint.iacr.org/2010/041.pdf