Posted by: Ricky aji | November 14, 2009

Linier Kriptanalisis pada SPN


  1. Ide Dasar Kriptanalisis Linear

Kriptanalisis linear yang menggunakan known plaintext attack merupakan salah satu metode kriptanalisis yang dilakukan dengan mencari hubungan linear antara sub himpunan dari bit-bit teks terang, sub himpunan dari bit-bit teks sandi serta sub himpunan dari bit-bit kunci. Dari hubungan linear tersebut akan didapat informasi mengenai bit-bit kunci. Dengan demikian untuk melakukan kriptanalisis linear dibutuhkan teks terang, teks sandi dan algoritma yang digunakan untuk mendapatkan sebagian dari kunci. Tujuan dari linear cryptanalysis adalah mencari persamaan linear yang paling efektif pada suatu algoritma blok dengan menggunakan persamaan:

Pii,i2, …in⨁Cji,j2, …jn=K(ki, k2, …kn)

dimana ii,i2, …in, ji,j2, …jndan ki, k2, …kn adalah posisi bit tetap dengan probabilitas p12 untuk teks terang P dan teks sandi C.

Prinsip Pilling Up

Kita anggap X1, X2, adalah variabel acak Bernoulli yang saling bebas. Misalkan

Pr[Xi = 0] = pi , dimana 0 pi 1 and i = 1, 2, 

sehingga

Pr[Xi = 1] = 1 – pi

Anggap i j, maka 2 variabel random yang saling bebas yaitu xi dan xj akan menyebabkan :

Pr[Xi = 0, Xj = 0] = pi pj

Pr[Xi = 0, Xj = 1] = pi (1 – pj)

Pr[Xi = 1, Xj = 0] = (1 – pi) pj

Pr[Xi = 1, Xj = 1] = (1 – pi)(1 – pj)

Anggap xi xj adalah variabel acak diskrit (xi xj = xi + xj mod 2) maka distribusi probabilitas dari xi xj adalah :

Pr[Xi Xj = 0] = pi pj + (1 – pi)(1 – pj)

Pr[Xi Xj = 1] = pi (1 – pj) + (1 – pi) pj

Distribusi probabilitas di atas dikenal dengan sebutan penyebaran bias (bias of distribution) yaitu penyebaran kemungkinan dari variabel acak yang bernilai 0 dan 1 . Bias dari xi didefinisikan sebagai i pi 12

Amati fakta berikut ini :

0 i1

Pr[Xi = 0] = ½ + i

Pr[Xi = 1] = ½ – i

Proposisi 3.1 Bias variabel acak X1 X2 is 212.

Bukti :

Pr[X1 X2 = 0] = (½ + 1) (½ + 2) + (½ – 1 )( ½ – 2) = 0.5 + 212

Lemma 3.1

Misalkanεi1, i1, …ik adalah bias dari variabel random xi1….xik maka

εi1, i1, …ik = 2 k-1 j=1kεij

B. Pendekatan Linear Terhadap S-Box SPN

S-Box yang digunakan Sir (1 i 4, 1 r 4) dan didefinisikan sebagai fungsi s:{0,1}4{0,1}4. S-Box tersebut dapat dilihat pada Tabel 3.1.

Langkah-langkah mencari pendekatan linear terhadap S-Box algoritma SPN :

1) Akan dicari semua nilai-nilai yang mungkin muncul dari variable random Xi dan Yi dimana Xi adalah input dan Yi adalah output setelah diproses kedalam S-Box. Hasilnya ditampilkan pada Tabel 2.3.

2) Dari S-Box yang ada dimana 1 a 15 dan 1 b 15 didefinisikan Sb(a, b) adalah jumlah input dari 16 kemungkinan input pada Sb, dimana nilai XOR dari bit input yang dioperasikan dengan a disamakan dengan nilai XOR dari bit output yang dioperasikan dengan b dengan rumus:

Sb( a, b ) = # {x0 x 15(⨁i=14( Xi ai)) = (⨁i=14 (Yi b))}

dimana ai{0,1}, bi{0,1}, i=1,2,3,4 , simbol adalah operasi AND pada bit dan # {x} adalah banyaknya x.

Maka akan didapat Tabel distribusi S-Box (16×16) atau Linear Approximation Table (LAT) seperti ditunjukkan pada Tabel 3.5.

tabel LAT

Konstruksi Linier Approximation SPN

Untuk melakukan attack pada SPN dengan tujuan untuk mengekstraksi bit-bit kunci, kita pertama-tama harus membuat suatu trail untuk mendapatkan suatu persamaan yang natinya digunakan untuk melakukan pendekatan linier terhadap struktur SPN. Acuan pendekatan linier ini yaitu dengan menggunakan tabel Linier Approximation (LAT) di atas. Dengan memilih output yang memiliki bias yang paling ekstrim, yakni mejauhi nol atau dengan kata lain yang memiliki probabilitas yang menjauhi setengah. Pada tulisan ini kami menggunakan pendekatan dengan input awal 1010 pada sbox ke 1. Berikut ini skema approximation yang digunakan :

approxSPN

Dari skema di atas maka kita dapatkan persamaan-persamaan dari masing-masing sbox aktif yang digunakan. Adapun sbox-sbox aktif tersebut yaitu

  1. Pada round ke-1, S1,1 , (a,b)= (a,1)
  2. Pada round ke-2, S2,4 , (a,b)= (8,f)
  3. Pada round ke-3, S3,1 , S3,2, S3,3, S3,4 (a,b) = (1,7)

Kemudian pada tiap sbox di atas diperoleh persamaan-persamaan berikut ini :

rumus1

Diasumsikan bahwa keenam persamaan di atas adalah saling bebas (independent). Maka berdasarkan Pilling-up lemma dapat dihitung nilai bias totalnya yaitu ;

rumus2

rumus3

Lalu dengan mensubstitusikan persamaan U dengan nilai (X xor K) pada round ke-1 dan (V xor K) pada round ke-2, dan round ke-3, maka didapatlah persamaan-persamaan seperti di atas. Sekarang

kita jumlahkan persamaan T di atas sehingga menjadi :

rumus4

rumus5

Berdasarkan persamaan terakhir di atas, maka kita dapat menyimpulkan bahwa :

  1. Diperoleh K5 dari hasil XOR y dengan V4
  2. V4 merupakan hasil Sbox U4
  3. Sehingga didapat asumsi 12 bit subkey, yaitu :

rumus6

Ekstraksi Kunci

Pada tahap ini, saya melakukan enkripsi 10.000 (seperti yang Matsui lakukan) plainteks dengan kunci yang sama yaitu 248 (dalam heksadesimal) . Adapun plainteks tersebut merupakan bilangan desimal mulai dari satu sampai dengan 10.000. Berikut ini adalah tabel hasilnya :

tabel-ekstrak1

dari tabel di atas dapat terlihat bahwa ternyata subkunci yang memiliki probabilitas counter terbesar adalah 248 (dalam hexa), dan ternyata ini cocok (match) tiga blok terakhir dari  subkunci kelima yang saya gunakan.

Berikut ini sourcecode yang saya gunakan :

/*

* form.java

*

* Created on Nov 6, 2009, 8:15:40 PM

*/

import javax.swing.JOptionPane;

/**

*

* @author rajip

*/

public class form extends javax.swing.JFrame {

/** Creates new form form */

public form() {

setTitle(“Linier Cryptanalysis on SPN”);

initComponents();

}

/** This method is called from within the constructor to

* initialize the form.

* WARNING: Do NOT modify this code. The content of this method is

* always regenerated by the Form Editor.

*/

@SuppressWarnings(“unchecked”)

// <editor-fold defaultstate=”collapsed” desc=”Generated Code”>//GEN-BEGIN:initComponents

private void initComponents() {

jOptionPane1 = new javax.swing.JOptionPane();

jDialog1 = new javax.swing.JDialog();

jLabel2 = new javax.swing.JLabel();

jScrollPane1 = new javax.swing.JScrollPane();

area = new javax.swing.JTextArea();

jScrollPane2 = new javax.swing.JScrollPane();

des = new javax.swing.JTextArea();

jScrollPane3 = new javax.swing.JScrollPane();

plain = new javax.swing.JTextArea();

jLabel4 = new javax.swing.JLabel();

jLabel5 = new javax.swing.JLabel();

jLabel6 = new javax.swing.JLabel();

jScrollPane4 = new javax.swing.JScrollPane();

keys = new javax.swing.JTextArea();

jScrollPane5 = new javax.swing.JScrollPane();

count = new javax.swing.JTextArea();

javax.swing.GroupLayout jDialog1Layout = new javax.swing.GroupLayout(jDialog1.getContentPane());

jDialog1.getContentPane().setLayout(jDialog1Layout);

jDialog1Layout.setHorizontalGroup(

jDialog1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGap(0, 400, Short.MAX_VALUE)

);

jDialog1Layout.setVerticalGroup(

jDialog1Layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGap(0, 300, Short.MAX_VALUE)

);

setDefaultCloseOperation(javax.swing.WindowConstants.EXIT_ON_CLOSE);

addWindowListener(new java.awt.event.WindowAdapter() {

public void windowOpened(java.awt.event.WindowEvent evt) {

formWindowOpened(evt);

}

});

jLabel2.setText(“Plain Text”);

area.setColumns(20);

area.setFont(new java.awt.Font(“Monospaced”, 0, 12));

area.setRows(5);

jScrollPane1.setViewportView(area);

des.setColumns(20);

des.setRows(5);

jScrollPane2.setViewportView(des);

plain.setColumns(20);

plain.setRows(5);

jScrollPane3.setViewportView(plain);

jLabel4.setText(“Candidate Keys”);

jLabel5.setText(“Count”);

jLabel6.setText(“Cipher”);

keys.setColumns(20);

keys.setRows(5);

jScrollPane4.setViewportView(keys);

count.setColumns(20);

count.setRows(5);

jScrollPane5.setViewportView(count);

javax.swing.GroupLayout layout = new javax.swing.GroupLayout(getContentPane());

getContentPane().setLayout(layout);

layout.setHorizontalGroup(

layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(layout.createSequentialGroup()

.addContainerGap()

.addComponent(jScrollPane3, javax.swing.GroupLayout.PREFERRED_SIZE, 69, javax.swing.GroupLayout.PREFERRED_SIZE))

.addGroup(layout.createSequentialGroup()

.addGap(20, 20, 20)

.addComponent(jLabel2)))

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup()

.addGap(94, 94, 94)

.addComponent(jLabel6)

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, 77, Short.MAX_VALUE)

.addComponent(jLabel4))

.addGroup(layout.createSequentialGroup()

.addGap(27, 27, 27)

.addComponent(jScrollPane1, javax.swing.GroupLayout.PREFERRED_SIZE, 59, javax.swing.GroupLayout.PREFERRED_SIZE)

.addGap(39, 39, 39)

.addComponent(jScrollPane2, javax.swing.GroupLayout.PREFERRED_SIZE, 73, javax.swing.GroupLayout.PREFERRED_SIZE)

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED, javax.swing.GroupLayout.DEFAULT_SIZE, Short.MAX_VALUE)

.addComponent(jScrollPane4, javax.swing.GroupLayout.PREFERRED_SIZE, 73, javax.swing.GroupLayout.PREFERRED_SIZE)))

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.TRAILING)

.addGroup(layout.createSequentialGroup()

.addComponent(jScrollPane5, javax.swing.GroupLayout.PREFERRED_SIZE, 65, javax.swing.GroupLayout.PREFERRED_SIZE)

.addGap(111, 111, 111))

.addGroup(layout.createSequentialGroup()

.addComponent(jLabel5, javax.swing.GroupLayout.PREFERRED_SIZE, 32, javax.swing.GroupLayout.PREFERRED_SIZE)

.addGap(132, 132, 132)))

.addGap(218, 218, 218))

);

layout.setVerticalGroup(

layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addGroup(javax.swing.GroupLayout.Alignment.TRAILING, layout.createSequentialGroup()

.addGap(22, 22, 22)

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.BASELINE)

.addComponent(jLabel2)

.addComponent(jLabel6)

.addComponent(jLabel4)

.addComponent(jLabel5))

.addPreferredGap(javax.swing.LayoutStyle.ComponentPlacement.RELATED)

.addGroup(layout.createParallelGroup(javax.swing.GroupLayout.Alignment.LEADING)

.addComponent(jScrollPane3, javax.swing.GroupLayout.DEFAULT_SIZE, 251, Short.MAX_VALUE)

.addComponent(jScrollPane1, javax.swing.GroupLayout.DEFAULT_SIZE, 251, Short.MAX_VALUE)

.addComponent(jScrollPane2, javax.swing.GroupLayout.DEFAULT_SIZE, 251, Short.MAX_VALUE)

.addComponent(jScrollPane4, javax.swing.GroupLayout.DEFAULT_SIZE, 251, Short.MAX_VALUE)

.addComponent(jScrollPane5, javax.swing.GroupLayout.DEFAULT_SIZE, 251, Short.MAX_VALUE))

.addContainerGap())

);

pack();

}// </editor-fold>//GEN-END:initComponents

private void formWindowOpened(java.awt.event.WindowEvent evt) {//GEN-FIRST:event_formWindowOpened

// TODO add your handling code here:

int input;

int cipher[]=new int[10001];

int []map={0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15};

int[]sbox= {0xe,0x4,0xd,0x1,0x2,0xf,0xb,0x8,0x3,0xa,0x6,0xc,0x5,0x9,0x0,0x7};

int []invsbox={0xe,0x3,0x4,0x8,0x1,0xc,0xa,0xf,0x7,0xd,0x9,0x6,0xb,0x2,0x0,0x7};

int bit[]=new int[16];

int tbit[]=new int[16];

int W[]=new int[5];

int V[]=new int[5];

int U4[]=new int[16];

int uji = 0;

int U[]=new int[5];

int []subkey=new int [5];

int masterkey=0x0248;

int candkey;

int tplain;

int []temp2=new int [4];

int temp3;

int counter []=new int[0x0fff+1];

/*Key schedule */

subkey[0]=masterkey;

for(int k=1;k<5;k++){

subkey[k]=((subkey[k-1]<<4)& 0x0fff0)|(subkey[k-1]>>12);

System.out.println(Integer.toHexString(subkey[k]));

}

input=1;

while(input<=10000){

/*inisialisasi bit input*/

int j=0;

while(j<16){

tbit[j]=input & (1<<(15-j));

if(tbit[j]!=0){

tbit[j]=1;

}

j++;

}

int temp1=input;

int round=0;

while(round<4){

//System.out.println(“Round ke”+(round +1));

// System.out.println();

if(round==3){

//key mixing

U[round]=temp1^subkey[round];

//inisialisasi bit hasil mixing

int n=0;

while(n<16){

bit[n]=U[round] & (1<<(15-n));

if(bit[n]!=0){

bit[n]=0x8;

}

n++;

}

/*Substitution Box*/

for(int m=0;m<4;m++){

temp2[m]=bit[0+4*m]|(bit[1+4*m]>>1)|(bit[2+4*m]>>2)|(bit[3+4*m]>>3);

V[m]=sbox[(int)temp2[m]];

// System.out.print(Integer.toHexString(V[m]));

}

//System.out.println();

temp3=((V[0]<<12)&0xf000)|((V[1]<<8)& 0x0f00)|((V[2]<<4 & 0x00f0))|(V[3]);

cipher[input]=temp3^subkey[4];

}else{

/* Key Mixing */

U[round]=temp1^subkey[round];

//System.out.println(Integer.toHexString(U[round]));

//inisialisasi bit hasil mixing

int n=0;

while(n<16){

bit[n]=U[round] & (1<<(15-n));

if(bit[n]!=0){

bit[n]=0x8;

}

n++;

}

/*Substitution Box*/

for(int m=0;m<4;m++){

temp2[m]=bit[0+4*m]|(bit[1+4*m]>>1)|(bit[2+4*m]>>2)|(bit[3+4*m]>>3);

V[m]=sbox[(int)temp2[m]];

}

temp3=((V[0]<<12)&0xf000)|((V[1]<<8)& 0x0f00)|((V[2]<<4 & 0x00f0))|(V[3]);

/*inisialisasi bit */

int p=0;

while(p<16){

bit[p]=temp3 & (1<<(15-p));

if(bit[p]!=0){

bit[p]=0x8;

}

p++;

}

/*permutasi bit */

for(int i=0;i<4;i++){

W[i]=bit[0+i]|(bit[4+i]>>1)|(bit[8+i]>>2)|(bit[12+i]>>3);

}

temp1=((W[0]<<12)&0xf000)|((W[1]<<8)&0x0f00)|((W[2]<<4)&0x00f0)|(W[3]);

}

round++;

}

input++;

}

for(int z=1;z<=10000;z++){

plain.append(Integer.toHexString(z)+”\n”);

area.append(Integer.toHexString(cipher[z])+”\n”);

des.append(cipher[z]+”\n”);

if(z ==10000){

JOptionPane.showMessageDialog(null,”Nah ini nih hasilnya….\n apakah hasilnya sama dengan” +Integer.toHexString(subkey[4]));

}

}

//ekstraksi kunci

candkey=0;

while(candkey <(0x0fff + 1)){

if(candkey==0x0fff){

JOptionPane.showMessageDialog(null,”Nah tuh dah muncul”);

}

keys.append(Integer.toHexString(candkey)+”\n”);

for(int t=1;t<=10000;t++){

tplain=cipher[t]^candkey;

//inisialisasi bit U4

int p=0;

while(p<16){

bit[p]=tplain & (1<<(15-p));

if(bit[p]!=0){

bit[p]=0x8;

}

p++;

}

//invers sbox

for(int m=0;m<4;m++){

temp2[m]=bit[0+4*m]|(bit[1+4*m]>>1)|(bit[2+4*m]>>2)|(bit[3+4*m]>>3);

V[m]=invsbox[(int)temp2[m]];

}

temp3=((V[0]<<12)&0xf000)|((V[1]<<8)& 0x0f00)|((V[2]<<4 & 0x00f0))|(V[3]);

/*inisialisasi bit input*/

int j=0;

while(j<16){

U4[j]=temp3 & (1<<(15-j));

if(U4[j]!=0){

U4[j]=1;

}

j++;

}

//uji persamaan T

uji=tbit[0]^tbit[2]^U4[4]^U4[5]^U4[6]^U4[7]^U4[8]^U4[9]^U4[10]^U4[11]^U4[12]^U4[13]^U4[14]^U4[15];

// uji=tbit[12]^tbit[15]^U4[1]^U4[2]^U4[3]^U4[5]^U4[6]^U4[7]^U4[9]^U4[10]^U4[11]^U4[13]^U4[14]^U4[15];

if(uji==0){

counter[candkey]++;

}

}

count.append(counter[candkey]+”\n”);

candkey++;

}

}//GEN-LAST:event_formWindowOpened

/**

* @param args the command line arguments

*/

public static void main(String args[]) {

java.awt.EventQueue.invokeLater(new Runnable() {

public void run() {

new form().setVisible(true);

}

});

}

// Variables declaration – do not modify//GEN-BEGIN:variables

private javax.swing.JTextArea area;

private javax.swing.JTextArea count;

private javax.swing.JTextArea des;

private javax.swing.JDialog jDialog1;

private javax.swing.JLabel jLabel2;

private javax.swing.JLabel jLabel4;

private javax.swing.JLabel jLabel5;

private javax.swing.JLabel jLabel6;

private javax.swing.JOptionPane jOptionPane1;

private javax.swing.JScrollPane jScrollPane1;

private javax.swing.JScrollPane jScrollPane2;

private javax.swing.JScrollPane jScrollPane3;

private javax.swing.JScrollPane jScrollPane4;

private javax.swing.JScrollPane jScrollPane5;

private javax.swing.JTextArea keys;

private javax.swing.JTextArea plain;

// End of variables declaration//GEN-END:variables

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: