Matasano Crypto Challenge 33: Implement Diffie-Hellman

Pada tulisan sebelumnya dibahas mengenai cara memecahkan HMAC-SHA1 dengan mengurangi jeda. Untuk tulisan hari ini akan dibahas mengenai implementasi Diffie-Hellman.

Crypto Challenge Set 5

Ini adalah set pertama dalam challenge teori bilangan kriptografi, dan juga menjelaskan mengenai otentifikasi pesan.

Set ini secara signifikan lebih sulit dibanding set sebelumnya. Konsepnya baru, dalam serangan ini tak memiliki kemiripan dengan set sebelumnya, dan … matematika.

Dengan kata lain, ini adalah kripta-analisis favorit (anda akan segera melihatnya). Matasano senang dengan set ini. Jangan menyerah disini. Kamu hampir selesai. Ini dia komposisi set ini:

  • Implement Diffie-Hellman
  • Implement a MITM key-fixing attack on Diffie-Hellman with parameter injection
  • Implement DH with negotiated groups, and break with malicious “g” parameters
  • Implement Secure Remote Password (SRP)
  • Break SRP with a zero key
  • Offline dictionary attack on simplified SRP
  • Implement RSA
  • Implement an E=3 RSA Broadcast attack

Challenge

Salah satu algoritma penting dalam latihan kriptografi ini seluruhnya tidak dapat dipecahkan dengan mudah.

Atur sebuah variabel “p” untuk 37 dan “g” untuk 5. Algoritma ini begitu mudah, Matasano tidak akan menjelaskannya. Kerjakan apa yang Matasano kerjakan.

Hasilkan “a”, sebuah nilai acak dengan mod 37. Sekarang hasilkan “A”, dimana “g” didapatkan untuk “a” dengan power mod 37 — s A = (g**a) % p.

Lakukan hal yang sama untuk “b” dan “B”.

“A” dan “B” adalah kunci publik. Hasilkan session key diantara keduanya; atur “s” untuk “B” yang didapatkan untuk “a” dengan power mod 37 — s = (B**a) % p.

Lakukan hal yang dengan A**b, cek apakah nilai sama dengan “s”.

Untuk mengembalikan “s” ke dalam sebuah kunci, anda hanya dapat melakukan hash, untuk membuat 128 bit material key (atau dengan melakukan hash SHA256 untuk nilai tersebut kemudian akan digunakan dalam membuat sebuah kunci untuk enkripsi dan kunci untuk MAC).

Oke, menyenangkan bukan, sekarang ulangi latihan ini dengan bignums seperti di dunia kripto yang sebenarnya. Ini dia parameter NIST:

p:
ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024
e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd
3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec
6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f
24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361
c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552
bb9ed529077096966d670c354e4abc9804f1746c08ca237327fff
fffffffffffff
 
g: 2

Ini sangat mudah jika dikerjakan dalam Python atau Ruby atau bahasa pemrograman tingkat tinggi lainnya yang mampu melakukan auto-promote fixnums ke bignums, dimanapun ini tidaklah sulit.

Catatan, anda akan butuh fungsi modexp sendiri (ini adalah blackboard math) karena anda akan membuat bignum anda ke dalam library yang akan mendapatkan nilai “a” menjadi 1024-bit-numberth yang kuat. Anda dapat mencari fungsi pada kode Rosetta dalam kebanyakan bahasa pemrograman.

Solved

Ini dia penampakannya :).

implement_diffie_hellman

################################################################
Implement Diffie Hellman
################################################################

----------------------------------------------------------------
[v] Result

[v] a: 
1574900286454236842217684425147503761932671354128332433896482906293253069495326849735115535267464408570411248540008485880075604839948528630988138615242348410563976888549938125318867272441321622183959751083035209596942684336198845125868948484809252696560983718227698079867725204430413079269764323719070407293298238961474514239024365534519079030164045593238093390016870836184140857862253904546474806969332749294650797146587517760154691029858495589042976419888887106

[v] A: 
1123297598999532807296044770043171036031542820073764655464469874890611614599126828076533287658614817935047652217710915917059381913177910396054732096310181388728628057009167229328504583835611737423081029409773102270505375877865032065534143575176732610277217222307232253795646553403619892432735547836054717849646721597867364989216152011931261406701048839080823053013324708438137175744402693767926737156461999583708396776287173736571019323684614600208219606330219115

[v] b: 
361998948227946602764424706574230696031300418326551296150423338463929734266775710756441391301911137906037721459367502762265233036183380489398239874086939093691184613293380205390374151851844479570487341374846661201917688124837293632371470172593127085166855601634939577408181704579827822424951289943028252246092665308045422296819597652515443912036717944066414403875304871663225554686324135917264704231806855182776506200337407880377388256819707172531101434452048585

[v] B: 
529341449793122959015115458635647923093025866715485473109242005348769946891895247139933430656355936425728634709936870622576356476129935753763166397549530288694945393645191943217145988345399527461480216756691187574184772454657621518002838939379915365982711327630032156254661925829218167912160171723023363584226084795678411869632971393235583961353380213205228705814751626564184530901851430756639320190343109139878023292672422270897150896896887584690704687041150159

[v] Joined: 
1574900286454236842217684425147503761932671354128332433896482906293253069495326849735115535267464408570411248540008485880075604839948528630988138615242348410563976888549938125318867272441321622183959751083035209596942684336198845125868948484809252696560983718227698079867725204430413079269764323719070407293298238961474514239024365534519079030164045593238093390016870836184140857862253904546474806969332749294650797146587517760154691029858495589042976419888887106 1123297598999532807296044770043171036031542820073764655464469874890611614599126828076533287658614817935047652217710915917059381913177910396054732096310181388728628057009167229328504583835611737423081029409773102270505375877865032065534143575176732610277217222307232253795646553403619892432735547836054717849646721597867364989216152011931261406701048839080823053013324708438137175744402693767926737156461999583708396776287173736571019323684614600208219606330219115 361998948227946602764424706574230696031300418326551296150423338463929734266775710756441391301911137906037721459367502762265233036183380489398239874086939093691184613293380205390374151851844479570487341374846661201917688124837293632371470172593127085166855601634939577408181704579827822424951289943028252246092665308045422296819597652515443912036717944066414403875304871663225554686324135917264704231806855182776506200337407880377388256819707172531101434452048585 529341449793122959015115458635647923093025866715485473109242005348769946891895247139933430656355936425728634709936870622576356476129935753763166397549530288694945393645191943217145988345399527461480216756691187574184772454657621518002838939379915365982711327630032156254661925829218167912160171723023363584226084795678411869632971393235583961353380213205228705814751626564184530901851430756639320190343109139878023292672422270897150896896887584690704687041150159

[v] sA: 
758103623398356284403412740527364665134761224968764596715250873744898274182311065740990189163033744223706381796559256322661995956206431910852378366106987672089406228174189658448044522092279179515555682173544012375215014868344014662661662049446375769272305933469754925171560183552555650589528821560956642458245762104139636582921924164693395905904240978910210838502922992018465470498207412564381232787512927472658645508946324604723730030643143439859601889913386767

[v] sB: 
758103623398356284403412740527364665134761224968764596715250873744898274182311065740990189163033744223706381796559256322661995956206431910852378366106987672089406228174189658448044522092279179515555682173544012375215014868344014662661662049446375769272305933469754925171560183552555650589528821560956642458245762104139636582921924164693395905904240978910210838502922992018465470498207412564381232787512927472658645508946324604723730030643143439859601889913386767
 

[v] Final: 
758103623398356284403412740527364665134761224968764596715250873744898274182311065740990189163033744223706381796559256322661995956206431910852378366106987672089406228174189658448044522092279179515555682173544012375215014868344014662661662049446375769272305933469754925171560183552555650589528821560956642458245762104139636582921924164693395905904240978910210838502922992018465470498207412564381232787512927472658645508946324604723730030643143439859601889913386767

################################################################
End of | Implement Diffie Hellman
################################################################

Mengapa hanya share screenshot saja? Alasannya bisa anda lihat pada tulisan ikhtisar MCC sebelumnya.

Sekian tulisan hari ini, semoga bermanfaat.

Keep Fun Coding 😀

[1] Unknown. (????). Implement Diffie-Hellman . Tersedia: cryptopals.com/sets/5/challenges/33/. [17 Februari 2015].

Advertisements

One thought on “Matasano Crypto Challenge 33: Implement Diffie-Hellman

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