Skip to content

Instantly share code, notes, and snippets.

@n-ari n-ari/solve_zer0SPN.cpp Secret
Created Dec 22, 2018

Embed
What would you like to do?
zer0SPN solver(めっちゃきたない……)
#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
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.