#decryption-oracle

서버는 복호한 평문이 0 부터 N 사이의 어느 1/4 구간에 있는지만 알려준다. 2비트짜리 정보인데, textbook RSA 의 곱셈 준동형으로 2의 k승을 곱해 가며 물어보면 그 응답이 곧 m/N 의 2진 전개가 된다. 520번 물어보고 1024비트 평문을 그대로 복원한 과정과, 그 전에 세 번 미끄러진 자리를 정리했다.

AES의 네 연산 중 비선형인 것은 SubBytes 하나뿐이다. 그걸 빼면 남은 ShiftRows·MixColumns·AddRoundKey가 모두 GF(2) 위의 선형·아핀 연산이라 암호 전체가 M·v 더하기 상수 d 꼴로 주저앉는다. 서버는 enc(secret) 하나만 복호를 거부하지만, XOR이 enc(secret)이 되는 다른 세 블록을 대신 복호시키면 상수항이 홀수 번 남아 secret이 그대로 나온다. 복호 질의 세 번으로 끝났다.

AES에서 ShiftRows만 제거하면 남은 세 연산이 전부 컬럼 안에서 끝나기 때문에 128비트 블록이 독립적인 32비트 암호 네 개로 분해된다. 서버가 enc(secret) 자체는 복호화해 주지 않지만, 4바이트 청크 하나만 뒤집으면 "다른 암호문"이 되면서 나머지 세 청크는 secret 평문 그대로 돌아온다. 질의 두 번으로 16바이트를 전부 복구했다.