Skip to content

Instantly share code, notes, and snippets.

@n-ari

n-ari/solve_zer0SPN.cpp Secret

Created December 22, 2018 15:01
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save n-ari/9624222c1575295cb1534231ad9e4027 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save n-ari/9624222c1575295cb1534231ad9e4027 to your computer and use it in GitHub Desktop.
Download ZIP
zer0SPN solver(めっちゃきたない……)
Raw
solve_zer0SPN.cpp
#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