Iznogood
Un algorithme de chiffrement est donné par cette classe Python
class IZNOGOOD:
def __init__(self, k):
self.k = self._b2n(k)
self.nr = 8
self.S = [12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2]
self.pi = [
[0x2,0x4,0x3,0xf,0x6,0xa,0x8,0x8,0x8,0x5,0xa,0x3,0x0,0x8,0xd,0x3,
0x1,0x3,0x1,0x9,0x8,0xa,0x2,0xe,0x0,0x3,0x7,0x0,0x7,0x3,0x4,0x4],
[0xa,0x4,0x0,0x9,0x3,0x8,0x2,0x2,0x2,0x9,0x9,0xf,0x3,0x1,0xd,0x0,
0x0,0x8,0x2,0xe,0xf,0xa,0x9,0x8,0xe,0xc,0x4,0xe,0x6,0xc,0x8,0x9],
[0x4,0x5,0x2,0x8,0x2,0x1,0xe,0x6,0x3,0x8,0xd,0x0,0x1,0x3,0x7,0x7,
0xb,0xe,0x5,0x4,0x6,0x6,0xc,0xf,0x3,0x4,0xe,0x9,0x0,0xc,0x6,0xc],
[0xc,0x0,0xa,0xc,0x2,0x9,0xb,0x7,0xc,0x9,0x7,0xc,0x5,0x0,0xd,0xd,
0x3,0xf,0x8,0x4,0xd,0x5,0xb,0x5,0xb,0x5,0x4,0x7,0x0,0x9,0x1,0x7],
[0x9,0x2,0x1,0x6,0xd,0x5,0xd,0x9,0x8,0x9,0x7,0x9,0xf,0xb,0x1,0xb,
0xd,0x1,0x3,0x1,0x0,0xb,0xa,0x6,0x9,0x8,0xd,0xf,0xb,0x5,0xa,0xc],
[0x2,0xf,0xf,0xd,0x7,0x2,0xd,0xb,0xd,0x0,0x1,0xa,0xd,0xf,0xb,0x7,
0xb,0x8,0xe,0x1,0xa,0xf,0xe,0xd,0x6,0xa,0x2,0x6,0x7,0xe,0x9,0x6],
[0xb,0xa,0x7,0xc,0x9,0x0,0x4,0x5,0xf,0x1,0x2,0xc,0x7,0xf,0x9,0x9,
0x2,0x4,0xa,0x1,0x9,0x9,0x4,0x7,0xb,0x3,0x9,0x1,0x6,0xc,0xf,0x7],
[0x0,0x8,0x0,0x1,0xf,0x2,0xe,0x2,0x8,0x5,0x8,0xe,0xf,0xc,0x1,0x6,
0x6,0x3,0x6,0x9,0x2,0x0,0xd,0x8,0x7,0x1,0x5,0x7,0x4,0xe,0x6,0x9],
[0xa,0x4,0x5,0x8,0xf,0xe,0xa,0x3,0xf,0x4,0x9,0x3,0x3,0xd,0x7,0xe,
0x0,0xd,0x9,0x5,0x7,0x4,0x8,0xf,0x7,0x2,0x8,0xe,0xb,0x6,0x5,0x8],
]
self.rk = self.pi
for r in range(self.nr + 1):
for i in range(32):
self.rk[r][i] ^= self.k[i]
def _S(self, s):
return [ self.S[x] for x in s ]
def _P(self, s):
r = []
for j in range(32):
b = 0
for i, x in enumerate(s):
if i == j: continue
b ^= x
r.append(b)
return r
def _addKey(self, a, r):
return [ x ^ y for x, y in zip(a, self.rk[r]) ]
def _n2b(self, v):
L = []
for i in range (0, len(v), 2):
a, b = v[i], v[i + 1]
L.append( b ^ (a << 4) )
return bytes(L)
def _b2n(self, v):
L = []
for x in v:
L.append( (x >> 4) & 0xf )
L.append( x & 0xf )
return L
def encrypt(self, m):
s = self._b2n(m)
for i in range (self.nr - 1):
s = self._addKey(s, i)
s = self._S(s)
s = self._P(s)
s = self._addKey(s, self.nr - 1)
s = self._S(s)
s = self._addKey(s, self.nr)
return self._n2b(s)
if __name__ == "__main__":
KP = 1
flag = open("flag.txt", "rb").read()
k = os.urandom(16)
E = IZNOGOOD(k)
P = [ flag[i:i+16] for i in range(0, len(flag), 16) ]
C = [ E.encrypt(p) for p in P ]
for i in range(len(P)):
if i < KP: print(P[i].hex(), C[i].hex())
else: print("?" * 32, C[i].hex())
On nous donne également une paire clair/chiffré:
464353437b6661343232653333393434 07b0d32c8a6a25dc782d2ee20acd53f3
???????????????????????????????? ba596368fc650d3d08ffbfb2bda27f28
???????????????????????????????? 68be7f31b109babfb667aabb92a119cd
???????????????????????????????? acf46fe7220bf34cb2fe740c5773b354
Il faut déchiffrer l’ensemble du message.
L’algorithme est composé (à la manière d’AES):
- d’un XOR avec une clé (en plusieurs rounds)
- d’une boîte de substitution
- d’une phase de “mélange”
En regardant de plus près, la phase de mélange peut se réécrire. Chaque élément est remplacé par le XOR des autres, donc c’est équivalent à le XOR-er avec le XOR de tout le vecteur:
def _P(self, s):
sum = s[0] ^ s[1] ^ ... ^ s[32]
for i in range(len(s)):
s[i] ^= sum
On voit alors que si un oracle nous donnait la valeur de sum pour chacun des rounds, chaque élément de sortie ne dépendrait que de l’élément d’entrée au même indice dans le tableau et dans les clés. On peut alors chercher les clés possibles éléments par éléments (on doit explorer 16 possibilités, 32 fois, et non pas 2^128 clés).
Comme les éléments sont sur 4 bits et qu’il y a 7 rounds de mélange, il n’y a que 2^28 possibilités pour ces 7 sommes: il suffit alors de toutes les essayer, et de revalider les clés trouvées:
- pour chaque combinaison de sommes
- pour chacun des 32 indices du tableau, chercher les valeurs possibles de key[i]
- tester les différentes combinaisons de clés entières correspondant aux possibilités de key[i]
On trouve que les sommes sont e, 9, 5, 4, 5, a, f (en hexadécimal) et plusieurs clés possibles parmi les 573 millions de possibilités pour ces sommes. Pour les autres choix de sommes, il y a très peu de clés à essayer.
L’ensemble tourne en quelques minutes sur un CPU ordinaire.
package main
import (
"fmt"
"math/bits"
)
func main() {
oracleStart := uint(0)
var sIn [8]uint16
var sOut [8]uint16
var output [][8]uint16
//in := "464353437b6661343232653333393434"
//out := "07b0d32c8a6a25dc782d2ee20acd53f3"
sIn = [8]uint16{
0x3464, 0x3435, 0x66b7, 0x4316,
0x2323, 0x3356, 0x9333, 0x4343,
}
sOut = [8]uint16{
0x0b70, 0xc23d, 0xa6a8, 0xcd52,
0xd287, 0x2ee2, 0xdca0, 0x3f35,
}
output = [][8]uint16{
sOut,
// ba59 6368 fc65 0d3d 08ff bfb2 bda2 7f28
{0x95ab, 0x8636, 0x56cf, 0xd3d0, 0xff80, 0x2bfb, 0x2adb, 0x82f7},
// 68be 7f31 b109 babf b667 aabb 92a1 19cd
{0xeb86, 0x13f7, 0x901b, 0xfbab, 0x766b, 0xbbaa, 0x1a29, 0xdc91},
// acf4 6fe7 220b f34c b2fe 740c 5773 b354
{0x4fca, 0x7ef6, 0xb022, 0xc43f, 0xef2b, 0xc047, 0x3775, 0x453b},
}
for oracle := oracleStart; oracle < 1<<28; oracle++ {
if oracle%(1<<20) == 0 {
println("oracle", oracle>>20, "<< 20")
}
keys := guessKey(sIn, sOut, oracle)
for _, k := range keys {
fmt.Printf("trying key %x\n", k)
var iz IZ
iz.Init(k)
for _, o := range output {
dec := iz.Decrypt(o)
fmt.Printf("%x => %x\n", o, dec)
}
}
}
}
const ROUNDS = 8
func guessKey(in, out [8]uint16, oracle uint) [][8]uint16 {
s1, s2, s3, s4 := unpack16(uint16(oracle))
s5, s6, s7, _ := unpack16(uint16(oracle >> 16))
sums := [7]uint16{s1, s2, s3, s4, s5, s6, s7}
// Bitmask of possible values
var keys [32]uint16
for i := uint(0); i < 32; i++ {
i1, i2 := i/4, i%4
xin := (in[i1] >> (4 * i2)) & 0xf
xout := (out[i1] >> (4 * i2)) & 0xf
//println("looking for",xin, "=>",xout)
var rk [9]uint16
for j := range rk {
rk[j] = PI[j][i]
}
for k := uint(0); k < 16; k++ {
x := xin
for round := 0; round < ROUNDS-1; round++ {
x ^= rk[round] ^ uint16(k)
x = S[x]
x ^= sums[round]
}
x ^= rk[ROUNDS-1] ^ uint16(k)
x = S[x]
x ^= rk[ROUNDS] ^ uint16(k)
if x == xout {
keys[i] |= (1 << k)
}
}
if keys[i] == 0 {
return nil
}
}
choices := uint64(1)
for _, k := range keys {
choices *= uint64(bits.OnesCount16(k))
}
fmt.Printf("sum %07x => try %d keys\n", oracle, choices)
ks := tryKeys(in, out, keys)
fmt.Println("done")
return ks
}
func tryKeys(in, out [8]uint16, keys [32]uint16) (result [][8]uint16) {
var key [8]uint16
var do func(uint)
do = func(idx uint) {
if idx == 32 {
var enc IZ
enc.Init(key)
if enc.Encrypt(in) == out {
fmt.Printf("FOUND %x\n", key)
result = append(result, key)
}
} else {
k := keys[idx]
for i := 0; i < 16; i++ {
if (k>>i)&1 == 1 {
key[idx/4] &^= 0xf << (4 * (idx % 4))
key[idx/4] |= uint16(i) << (4 * (idx % 4))
do(idx + 1)
}
}
}
}
do(0)
return
}
var S = [16]uint16{12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2}
var Sinv [16]uint16
func init() {
for i, j := range S {
Sinv[j] = uint16(i)
}
}
var PI = [9][32]uint16{
{0x2, 0x4, 0x3, 0xf, 0x6, 0xa, 0x8, 0x8, 0x8, 0x5, 0xa, 0x3, 0x0, 0x8, 0xd, 0x3,
0x1, 0x3, 0x1, 0x9, 0x8, 0xa, 0x2, 0xe, 0x0, 0x3, 0x7, 0x0, 0x7, 0x3, 0x4, 0x4},
{0xa, 0x4, 0x0, 0x9, 0x3, 0x8, 0x2, 0x2, 0x2, 0x9, 0x9, 0xf, 0x3, 0x1, 0xd, 0x0,
0x0, 0x8, 0x2, 0xe, 0xf, 0xa, 0x9, 0x8, 0xe, 0xc, 0x4, 0xe, 0x6, 0xc, 0x8, 0x9},
{0x4, 0x5, 0x2, 0x8, 0x2, 0x1, 0xe, 0x6, 0x3, 0x8, 0xd, 0x0, 0x1, 0x3, 0x7, 0x7,
0xb, 0xe, 0x5, 0x4, 0x6, 0x6, 0xc, 0xf, 0x3, 0x4, 0xe, 0x9, 0x0, 0xc, 0x6, 0xc},
{0xc, 0x0, 0xa, 0xc, 0x2, 0x9, 0xb, 0x7, 0xc, 0x9, 0x7, 0xc, 0x5, 0x0, 0xd, 0xd,
0x3, 0xf, 0x8, 0x4, 0xd, 0x5, 0xb, 0x5, 0xb, 0x5, 0x4, 0x7, 0x0, 0x9, 0x1, 0x7},
{0x9, 0x2, 0x1, 0x6, 0xd, 0x5, 0xd, 0x9, 0x8, 0x9, 0x7, 0x9, 0xf, 0xb, 0x1, 0xb,
0xd, 0x1, 0x3, 0x1, 0x0, 0xb, 0xa, 0x6, 0x9, 0x8, 0xd, 0xf, 0xb, 0x5, 0xa, 0xc},
{0x2, 0xf, 0xf, 0xd, 0x7, 0x2, 0xd, 0xb, 0xd, 0x0, 0x1, 0xa, 0xd, 0xf, 0xb, 0x7,
0xb, 0x8, 0xe, 0x1, 0xa, 0xf, 0xe, 0xd, 0x6, 0xa, 0x2, 0x6, 0x7, 0xe, 0x9, 0x6},
{0xb, 0xa, 0x7, 0xc, 0x9, 0x0, 0x4, 0x5, 0xf, 0x1, 0x2, 0xc, 0x7, 0xf, 0x9, 0x9,
0x2, 0x4, 0xa, 0x1, 0x9, 0x9, 0x4, 0x7, 0xb, 0x3, 0x9, 0x1, 0x6, 0xc, 0xf, 0x7},
{0x0, 0x8, 0x0, 0x1, 0xf, 0x2, 0xe, 0x2, 0x8, 0x5, 0x8, 0xe, 0xf, 0xc, 0x1, 0x6,
0x6, 0x3, 0x6, 0x9, 0x2, 0x0, 0xd, 0x8, 0x7, 0x1, 0x5, 0x7, 0x4, 0xe, 0x6, 0x9},
{0xa, 0x4, 0x5, 0x8, 0xf, 0xe, 0xa, 0x3, 0xf, 0x4, 0x9, 0x3, 0x3, 0xd, 0x7, 0xe,
0x0, 0xd, 0x9, 0x5, 0x7, 0x4, 0x8, 0xf, 0x7, 0x2, 0x8, 0xe, 0xb, 0x6, 0x5, 0x8},
}
func unpack16(n uint16) (a, b, c, d uint16) {
return n & 0xf, (n >> 4) & 0xf, (n >> 8) & 0xf, (n >> 12) & 0xf
}
func pack16(a, b, c, d uint16) uint16 {
return a | b<<4 | c<<8 | d<<12
}
type IZ struct {
rk [9][8]uint16
s [8]uint16
}
func (z *IZ) Init(key [8]uint16) {
for i := range PI {
for j := range key {
z.rk[i][j] = key[j] ^ pack16(
PI[i][4*j],
PI[i][4*j+1],
PI[i][4*j+2],
PI[i][4*j+3])
}
}
}
func (z *IZ) Encrypt(m [8]uint16) [8]uint16 {
z.s = m
for i := uint(0); i < ROUNDS-1; i++ {
z.XOR(i)
z.S()
z.P()
}
z.XOR(ROUNDS - 1)
z.S()
z.XOR(ROUNDS)
return z.s
}
func (z *IZ) Decrypt(m [8]uint16) [8]uint16 {
z.s = m
z.XOR(ROUNDS)
z.Sinv()
z.XOR(ROUNDS - 1)
for i := ROUNDS - 2; i >= 0; i-- {
z.P()
z.Sinv()
z.XOR(uint(i))
}
return z.s
}
func (z *IZ) XOR(round uint) {
for j := range z.s {
z.s[j] ^= z.rk[round][j]
}
}
func (z *IZ) S() {
for i, x := range z.s {
a, b, c, d := unpack16(x)
z.s[i] = pack16(S[a], S[b], S[c], S[d])
}
}
func (z *IZ) Sinv() {
for i, x := range z.s {
a, b, c, d := unpack16(x)
z.s[i] = pack16(Sinv[a], Sinv[b], Sinv[c], Sinv[d])
}
}
func (z *IZ) P() {
s := z.s[0] ^ z.s[1] ^ z.s[2] ^ z.s[3]
s ^= z.s[4] ^ z.s[5] ^ z.s[6] ^ z.s[7]
sum := s ^ (s >> 8)
sum = sum ^ (sum >> 4)
sum &= 0xf
//println(sum)
z._P(sum)
}
func (z *IZ) _P(sum uint16) {
mask := pack16(sum, sum, sum, sum)
for i := range z.s {
z.s[i] ^= mask
}
}