-
-
Save n-ari/9624222c1575295cb1534231ad9e4027 to your computer and use it in GitHub Desktop.
zer0SPN solver(めっちゃきたない……)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
#define REP(i,n) for(int i=0;i<(int)(n);i++) | |
string to_string(int v){ | |
if(v==0)return "0"; | |
string ret = ""; | |
while(v>0){ | |
ret = string(1,'0'+(v%10)) + ret; | |
v /= 10; | |
} | |
return ret; | |
} | |
int sbox[256] = { | |
62, 117, 195, 179, 20, 210, 41, 66, 116, 178, 152, 143, 75, 105, 254, 1, | |
158, 95, 101, 175, 191, 166, 36, 24, 50, 39, 190, 120, 52, 242, 182, 185, | |
61, 225, 140, 38, 150, 80, 19, 109, 246, 252, 40, 13, 65, 236, 124, 186, | |
214, 86, 235, 100, 97, 49, 197, 154, 176, 199, 253, 69, 88, 112, 139, 77, | |
184, 45, 133, 104, 15, 54, 177, 244, 160, 169, 82, 148, 73, 30, 229, 35, | |
79, 137, 157, 180, 248, 163, 241, 231, 81, 94, 165, 9, 162, 233, 18, 85, | |
217, 84, 7, 55, 63, 171, 56, 118, 237, 132, 136, 22, 90, 221, 103, 161, | |
205, 11, 255, 14, 122, 47, 71, 201, 99, 220, 83, 74, 173, 76, 144, 16, | |
155, 126, 60, 96, 44, 234, 17, 215, 107, 138, 159, 183, 251, 3, 198, 0, | |
89, 170, 131, 151, 219, 29, 230, 32, 187, 125, 134, 64, 12, 202, 164, 247, | |
25, 223, 222, 119, 174, 67, 147, 146, 206, 51, 243, 53, 121, 239, 68, 130, | |
70, 203, 211, 111, 108, 113, 8, 106, 57, 240, 21, 93, 142, 238, 167, 5, | |
128, 72, 189, 192, 193, 92, 10, 204, 87, 145, 188, 172, 224, 226, 207, 27, | |
218, 48, 33, 28, 123, 6, 37, 59, 4, 102, 114, 91, 23, 209, 34, 42, | |
2, 196, 141, 208, 181, 245, 43, 78, 213, 216, 232, 46, 98, 26, 212, 58, | |
115, 194, 200, 129, 227, 249, 127, 149, 135, 228, 31, 153, 250, 156, 168, 110 | |
}; | |
int ptable[64] = { | |
0, 8, 16, 24, 32, 40, 48, 56, | |
1, 9, 17, 25, 33, 41, 49, 57, | |
2, 10, 18, 26, 34, 42, 50, 58, | |
3, 11, 19, 27, 35, 43, 51, 59, | |
4, 12, 20, 28, 36, 44, 52, 60, | |
5, 13, 21, 29, 37, 45, 53, 61, | |
6, 14, 22, 30, 38, 46, 54, 62, | |
7, 15, 23, 31, 39, 47, 55, 63 | |
}; | |
int bitparity[256]; | |
int counts[256][256]; | |
struct state{ | |
int roundNum; | |
int activePosNum; | |
int activePos[16]; // active s-box <= 2 | |
int sboxLin[24]; | |
double bias; | |
state(){ | |
roundNum = 0; | |
activePosNum = 0; | |
bias = 0.5; | |
fill(sboxLin, sboxLin+24, -1); | |
} | |
void push(int p){ | |
assert(activePosNum < 16); | |
activePos[activePosNum++] = p; | |
} | |
void usesbox(int pos, int inmask, int outmask){ | |
sboxLin[8*roundNum+pos] = inmask*1000 + outmask; | |
} | |
bool getActiveSbox(int &a, int &b){ | |
a = b = -1; | |
REP(i,activePosNum){ | |
int p = activePos[i]/8; | |
if(a==-1 || a==p){ | |
a = p; | |
}else if(b==-1 || b==p){ | |
b = p; | |
}else{ | |
return false; | |
} | |
} | |
return true; | |
} | |
bool operator<(const state &that) const { | |
if(bias != that.bias) return bias > that.bias; | |
if(activePosNum != that.activePosNum) return activePosNum > that.activePosNum; | |
REP(i,activePosNum)if(activePos[i] != that.activePos[i]){ | |
return activePos[i] > that.activePos[i]; | |
} | |
return false; | |
} | |
}; | |
int main(){ | |
REP(i,256)bitparity[i] = __builtin_popcount(i)&1; | |
// bias table | |
REP(inmask,256)REP(outmask,256){ | |
counts[inmask][outmask] = 0; | |
REP(in,256){ | |
int out = sbox[in]; | |
if(bitparity[in&inmask]==bitparity[out&outmask]){ | |
counts[inmask][outmask]++; | |
} | |
} | |
} | |
double needBias = 0.0066; | |
// 1 bit start, 3 round trail | |
if(true)REP(startPos,64){ | |
state initial; | |
initial.roundNum = -1; | |
initial.push(startPos); | |
vector<state> currentQueue; | |
currentQueue.push_back(initial); | |
const int BEAM_WIDTH = 50; | |
REP(round,3){ | |
priority_queue<state> nextQueue; | |
for(state S : currentQueue){ | |
int pos, pos2; | |
S.getActiveSbox(pos, pos2); | |
if(pos2 == -1){ | |
// single sbox | |
int inmask = 0; | |
REP(i,S.activePosNum){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
}else{ | |
// double sbox | |
int inmask = 0, inmask2 = 0; | |
REP(i,S.activePosNum){ | |
if(S.activePos[i]/8 == pos){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
}else{ | |
inmask2 |= 1<<(7-S.activePos[i]%8); | |
} | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
REP(outmask2,256){ | |
if(round<2 && __builtin_popcount(outmask2)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
nextS.bias = nextS.bias * 2.0 * (counts[inmask2][outmask2]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
nextS.usesbox(pos2,inmask2,outmask2); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
REP(i,8)if(outmask2>>i&1){ | |
int bitpos = 8*pos2 + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
} | |
} | |
} | |
currentQueue.clear(); | |
while(nextQueue.size()){ | |
currentQueue.push_back(nextQueue.top()); | |
nextQueue.pop(); | |
} | |
} | |
state best = currentQueue.back(); | |
if(best.bias < 0.00390625)continue; | |
printf("%d -> ",startPos); | |
REP(i,best.activePosNum)printf("%d,",best.activePos[i]); | |
printf("\n"); | |
printf("bias: %.8f\n",best.bias); | |
printf("active sbox: "); | |
REP(i,24)if(best.sboxLin[i]>=0){ | |
printf("(%d,%d,%x->%x),",i/8,i%8,best.sboxLin[i]/1000,best.sboxLin[i]%1000); | |
} | |
printf("\n"); | |
} | |
needBias = 0.008; | |
// 1 block start, 3 round trail | |
// 1, 2, 6 is known | |
if(true)REP(use,256){ | |
int target = -1; | |
REP(i,8){ | |
if(i==1)continue; | |
if(i==2)continue; | |
if(i==6)continue; | |
if(use>>i&1){ | |
if(target==-1){ | |
target = i; | |
}else{ | |
target = -1;break; | |
} | |
} | |
} | |
if(target==-1)continue; | |
REP(off,8){ | |
state initial; | |
initial.roundNum = -1; | |
REP(i,8)if(use>>i&1){ | |
initial.push(ptable[8*i+off]); | |
} | |
vector<state> currentQueue; | |
currentQueue.push_back(initial); | |
const int BEAM_WIDTH = 1000; | |
REP(round,3){ | |
priority_queue<state> nextQueue; | |
for(state S : currentQueue){ | |
int pos, pos2; | |
S.getActiveSbox(pos, pos2); | |
if(pos2 == -1){ | |
// single sbox | |
int inmask = 0; | |
REP(i,S.activePosNum){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
}else{ | |
// double sbox | |
int inmask = 0, inmask2 = 0; | |
REP(i,S.activePosNum){ | |
if(S.activePos[i]/8 == pos){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
}else{ | |
inmask2 |= 1<<(7-S.activePos[i]%8); | |
} | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
REP(outmask2,256){ | |
if(round<2 && __builtin_popcount(outmask2)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
nextS.bias = nextS.bias * 2.0 * (counts[inmask2][outmask2]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
nextS.usesbox(pos2,inmask2,outmask2); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
REP(i,8)if(outmask2>>i&1){ | |
int bitpos = 8*pos2 + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
} | |
} | |
} | |
currentQueue.clear(); | |
while(nextQueue.size()){ | |
currentQueue.push_back(nextQueue.top()); | |
nextQueue.pop(); | |
} | |
} | |
if(currentQueue.size()==0)continue; | |
state best = currentQueue.back(); | |
if(best.bias < needBias)continue; | |
REP(i,8)if(use>>i&1){ | |
printf("%d,",ptable[8*i+off]); | |
} | |
printf(" -> "); | |
REP(i,best.activePosNum)printf("%d,",best.activePos[i]); | |
printf("\n"); | |
printf("bias: %.8f\n",best.bias); | |
printf("active sbox: "); | |
REP(i,24)if(best.sboxLin[i]>=0){ | |
printf("(%d,%d,%x->%x),",i/8,i%8,best.sboxLin[i]/1000,best.sboxLin[i]%1000); | |
} | |
printf("\n"); | |
} | |
} | |
needBias = 0.019; | |
// 1 block start, 3 round trail | |
// 1, 2, 6, 0, 5, 7 is known | |
if(true)REP(use,256){ | |
int target = -1; | |
REP(i,8){ | |
if(i==1)continue; | |
if(i==2)continue; | |
if(i==6)continue; | |
if(i==0)continue; | |
if(i==5)continue; | |
if(i==7)continue; | |
if(use>>i&1){ | |
if(target==-1){ | |
target = i; | |
}else{ | |
target = -1;break; | |
} | |
} | |
} | |
if(target==-1)continue; | |
REP(off,8){ | |
state initial; | |
initial.roundNum = -1; | |
REP(i,8)if(use>>i&1){ | |
initial.push(ptable[8*i+off]); | |
} | |
vector<state> currentQueue; | |
currentQueue.push_back(initial); | |
const int BEAM_WIDTH = 1000; | |
REP(round,3){ | |
priority_queue<state> nextQueue; | |
for(state S : currentQueue){ | |
int pos, pos2; | |
S.getActiveSbox(pos, pos2); | |
if(pos2 == -1){ | |
// single sbox | |
int inmask = 0; | |
REP(i,S.activePosNum){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
}else{ | |
// double sbox | |
int inmask = 0, inmask2 = 0; | |
REP(i,S.activePosNum){ | |
if(S.activePos[i]/8 == pos){ | |
inmask |= 1<<(7-S.activePos[i]%8); | |
}else{ | |
inmask2 |= 1<<(7-S.activePos[i]%8); | |
} | |
} | |
REP(outmask,256){ | |
if(round<2 && __builtin_popcount(outmask)>2)continue; | |
REP(outmask2,256){ | |
if(round<2 && __builtin_popcount(outmask2)>2)continue; | |
state nextS; | |
nextS.roundNum = S.roundNum + 1; | |
nextS.bias = S.bias * 2.0 * (counts[inmask][outmask]-128)/256.0; | |
nextS.bias = nextS.bias * 2.0 * (counts[inmask2][outmask2]-128)/256.0; | |
if(abs(nextS.bias) < needBias)continue; | |
REP(i,24)nextS.sboxLin[i] = S.sboxLin[i]; | |
nextS.usesbox(pos, inmask, outmask); | |
nextS.usesbox(pos2,inmask2,outmask2); | |
REP(i,8)if(outmask>>i&1){ | |
int bitpos = 8*pos + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
REP(i,8)if(outmask2>>i&1){ | |
int bitpos = 8*pos2 + (7-i); | |
nextS.push(round<2 ? ptable[bitpos] : bitpos); | |
} | |
int a,b; | |
if(round<2 && !nextS.getActiveSbox(a,b))continue; | |
nextQueue.push(nextS); | |
if(nextQueue.size() > BEAM_WIDTH){ | |
nextQueue.pop(); | |
} | |
} | |
} | |
} | |
} | |
currentQueue.clear(); | |
while(nextQueue.size()){ | |
currentQueue.push_back(nextQueue.top()); | |
nextQueue.pop(); | |
} | |
} | |
if(currentQueue.size()==0)continue; | |
state best = currentQueue.back(); | |
if(best.bias < needBias)continue; | |
REP(i,8)if(use>>i&1){ | |
printf("%d,",ptable[8*i+off]); | |
} | |
printf(" -> "); | |
REP(i,best.activePosNum)printf("%d,",best.activePos[i]); | |
printf("\n"); | |
printf("bias: %.8f\n",best.bias); | |
printf("active sbox: "); | |
REP(i,24)if(best.sboxLin[i]>=0){ | |
printf("(%d,%d,%x->%x),",i/8,i%8,best.sboxLin[i]/1000,best.sboxLin[i]%1000); | |
} | |
printf("\n"); | |
} | |
} | |
// recover key | |
// bias need 2^(-8) = 0.00390625 | |
vector<vector<int>> trailIn, trailOut; | |
vector<int> targetKeyId; | |
// bias: 0.01149997, key block: 1 | |
trailIn.push_back(vector<int>({1})); | |
trailOut.push_back(vector<int>({62,60,56,30,28,24})); | |
targetKeyId.push_back(1); | |
// bias: 0.01796870, key block: 1 | |
trailIn.push_back(vector<int>({9})); | |
trailOut.push_back(vector<int>({54,52,48,6,4,0})); | |
targetKeyId.push_back(1); | |
// bias: 0.00667572, key block: 2 | |
trailIn.push_back(vector<int>({18})); | |
trailOut.push_back(vector<int>({14,8})); | |
targetKeyId.push_back(2); | |
// bias: 0.01796870, key block: 2 | |
trailIn.push_back(vector<int>({10})); | |
trailOut.push_back(vector<int>({54,48,6,0})); | |
targetKeyId.push_back(2); | |
// bias: 0.00807762, key block: 6 | |
trailIn.push_back(vector<int>({54})); | |
trailOut.push_back(vector<int>({14,8})); | |
targetKeyId.push_back(6); | |
// bias: 0.01124442, key block: 6 | |
trailIn.push_back(vector<int>({6})); | |
trailOut.push_back(vector<int>({62,56,30,24})); | |
targetKeyId.push_back(6); | |
// bias: 0.02129555, key block: 0, 1, 6 | |
trailIn.push_back(vector<int>({48,49,54})); | |
trailOut.push_back(vector<int>({14,11,10,8})); | |
targetKeyId.push_back(0); | |
// bias: 0.03705546, key block: 0, 1, 6 | |
trailIn.push_back(vector<int>({8,9,14})); | |
trailOut.push_back(vector<int>({54,51,50,48,6,3,2,0})); | |
targetKeyId.push_back(0); | |
// bias: 0.00801921, key block: 1, 5 | |
trailIn.push_back(vector<int>({1,5})); | |
trailOut.push_back(vector<int>({63,62,61,60,59,31,30,29,28,27})); | |
targetKeyId.push_back(5); | |
// bias: 0.01233965, key block: 5, 6 | |
trailIn.push_back(vector<int>({13,14})); | |
trailOut.push_back(vector<int>({55,53,52,51,49,7,5,4,3,1})); | |
targetKeyId.push_back(5); | |
// bias: 0.01986027, key block: 2, 6, 7 | |
trailIn.push_back(vector<int>({10,14,15})); | |
trailOut.push_back(vector<int>({53,52,51,5,4,3})); | |
targetKeyId.push_back(7); | |
// bias: 0.02373923, key block: 1, 2, 6, 7 | |
trailIn.push_back(vector<int>({9,10,14,15})); | |
trailOut.push_back(vector<int>({54,53,51,48,6,5,3,0})); | |
targetKeyId.push_back(7); | |
// bias: 0.01925732 | |
trailIn.push_back(vector<int>({8,10,12,14,15})); | |
trailOut.push_back(vector<int>({54,53,52,6,5,4})); | |
targetKeyId.push_back(4); | |
// bias: 0.02028296 | |
trailIn.push_back(vector<int>({8,9,10,12,14,15})); | |
trailOut.push_back(vector<int>({53,48,5,0})); | |
targetKeyId.push_back(4); | |
// bias: 0.01951218 | |
trailIn.push_back(vector<int>({48,51,53,54})); | |
trailOut.push_back(vector<int>({15,14,13,12,11})); | |
targetKeyId.push_back(3); | |
// bias: 0.02405763 | |
trailIn.push_back(vector<int>({0,3,5,6})); | |
trailOut.push_back(vector<int>({63,62,61,60,59,31,30,29,28,27})); | |
targetKeyId.push_back(3); | |
unsigned char anskey[8] = {}; | |
ifstream fin("dataSPN", ios::in | ios::binary); | |
REP(trailId, trailIn.size()){ | |
vector<int> in = trailIn[trailId]; | |
vector<int> out = trailOut[trailId]; | |
int target = targetKeyId[trailId]; | |
vector<bool> inuse(64,false); | |
for(int p: in)REP(i,64)if(ptable[i]==p){ | |
inuse[i] = true; | |
break; | |
} | |
vector<pair<double,int>> cands; | |
REP(key,256){ | |
anskey[target] = key; | |
int count = 0; | |
REP(pid,65536){ | |
unsigned char rawpt[8], rawct[8]; | |
fin.read((char*)rawpt, 8); | |
fin.read((char*)rawct, 8); | |
int v = 0; | |
REP(i,8)rawpt[i] ^= anskey[i]; | |
REP(i,8)rawpt[i] = sbox[rawpt[i]]; | |
REP(i,64)if(inuse[i]){ | |
v ^= (rawpt[i/8]>>(7-i%8))&1; | |
} | |
for(int o: out){ | |
int x = o/8; | |
int y = 7-o%8; | |
v ^= (rawct[x]>>y)&1; | |
} | |
if(v==0)count++; | |
} | |
// end | |
fin.clear(); | |
fin.seekg(0,ios_base::beg); | |
// update | |
double bias = abs(count - 32768) / 65536.0; | |
cands.push_back(make_pair(bias, key)); | |
} | |
sort(cands.begin(), cands.end()); | |
reverse(cands.begin(), cands.end()); | |
printf("blockId=%d, ", target); | |
REP(i,5)printf("#%d:%02x(%.8f), ",i+1,cands[i].second,cands[i].first); | |
printf("\n"); | |
anskey[target] = cands[0].second; | |
} | |
fin.close(); | |
printf("key : "); | |
REP(i,8)printf("%02x",anskey[i]); | |
printf("\n"); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment