Cylabus

Cylabus

Eksploitasi Cryptography: MD5 Collision Attack

Mempelajari kerentanan MD5 hash melalui studi kasus pemakaian digital signature berbasis Schnorr Signature yang salah.

Testimonial 01

Nicholas R. Putra

Co-Founder

banner

Dalam dunia digital yang semakin kompleks, keamanan informasi menjadi aspek yang tidak bisa diabaikan. Salah satu topik penting dalam bidang ini adalah keamanan kriptografi, yang menjadi tulang punggung perlindungan data. Artikel ini akan membahas tentang salah satu aspek krusial dalam kriptografi: dampak dari MD5 Collision.

Untuk memahami dampak ini secara mendalam, kita akan melakukan studi kasus pada salah satu soal dari Cyber Apocalypse CTF 2023. Soal tersebut menghadirkan sebuah implementasi digital signature berbasis Schnorr Algorithm dengan modifikasi tertentu, di mana generasi nonce didasarkan pada hash MD5. Kita akan menjelajahi bagaimana MD5 Collision dapat memicu nonce reuse attack, sebuah kerentanan serius yang mengancam integritas dan keaslian dari tanda tangan digital.

Nonce reuse attack merupakan masalah yang sering diabaikan namun memiliki konsekuensi yang signifikan, terutama dalam konteks digital signature berbasis Schnorr, yang dikenal karena efisiensinya dan keamanannya. Analisis ini akan membawa kita ke dalam pemahaman mendalam tentang bagaimana nonce reuse attack terjadi, implikasinya terhadap keamanan data, dan pentingnya memilih algoritma hash yang tepat dalam penerapan kriptografi. Pembahasan ini penting tidak hanya untuk ahli kriptografi, tetapi juga untuk siapa saja yang bergantung pada keamanan digital dalam aktivitas sehari-hari mereka.

Overview

Untuk tantangan ini, kami diberikan sebuah file bernama server.py. Berikut adalah kodenya:

server.py

#!/usr/bin/env python3
import signal
from secrets import randbelow
from hashlib import md5
from Crypto.Util.number import isPrime, getPrime, long_to_bytes, bytes_to_long
FLAG = "HTB{???????????????????????????}"
class MD5chnorr:
def __init__(self):
# while True:
# self.q = getPrime(128)
# self.p = 2*self.q + 1
# if isPrime(self.p):
# break
self.p = 0x16dd987483c08aefa88f28147702e51eb
self.q = (self.p - 1) // 2
self.g = 3
self.x = randbelow(self.q)
self.y = pow(self.g, self.x, self.p)
def H(self, msg):
return bytes_to_long(md5(msg).digest()) % self.q
def sign(self, msg):
k = self.H(msg + long_to_bytes(self.x))
print(f'{k = }')
r = pow(self.g, k, self.p) % self.q
e = self.H(long_to_bytes(r) + msg)
s = (k - self.x * e) % self.q
return (s, e)
def verify(self, msg, sig):
s, e = sig
if not (0 < s < self.q):
return False
if not (0 < e < self.q):
return False
rv = pow(self.g, s, self.p) * pow(self.y, e, self.p) % self.p % self.q
ev = self.H(long_to_bytes(rv) + msg)
return ev == e
def menu():
print('[S]ign a message')
print('[V]erify a signature')
return input('> ').upper()[0]
def main():
md5chnorr = MD5chnorr()
print('g:', md5chnorr.g)
print('y:', md5chnorr.y)
print('p:', md5chnorr.p)
for _ in range(3):
choice = menu()
if choice == 'S':
msg = bytes.fromhex(input('Enter message> '))
if b'I am the left hand' in msg:
print('No!')
else:
sig = md5chnorr.sign(msg)
print('Signature:', sig)
elif choice == 'V':
msg = bytes.fromhex(input('Enter message> '))
s = int(input('Enter s> '))
e = int(input('Enter e> '))
if md5chnorr.verify(msg, (s, e)):
if msg == b'I am the left hand':
print(FLAG)
else:
print('Valid signature!')
else:
print('Invalid signature!')
else:
print('Invalid choice...')
if __name__ == '__main__':
signal.alarm(30)
main()

Jadi, kami diberikan sebuah server yang mengimplementasikan skema digital signature berbasis Schnorr Algorithm Signature. Detail dari algoritma ini dapat dibaca di Wikipedia. Tantangan ini membagikan public key dari skema digital signature (g, y, dan p), dan memberikan kita tiga kesempatan untuk menggunakan menu yang tersedia:

  • S, yang merupakan menu untuk menandatangani pesan apa pun yang kita berikan.
    • Ada pembatasan yang melarang pesan mengandung string I am the left hand.
    • Kita mendapatkan nilai s dan e juga, yang merupakan bagian dari signature.
  • V, yang merupakan menu untuk memvalidasi digital signature kita dari pesan.
    • Jika signature valid dan pesannya adalah I am the left hand, itu akan mencetak flag.

Oleh karena itu, tujuan dari tantangan ini adalah untuk mengambil private key dengan dua signature yang kita dapatkan dari server sehingga kita dapat menandatangani pesan I am the left hand secara mandiri, mengirimkannya ke server, dan mengambil flag.

Kesalahan Implementasi

Penting untuk diperhatikan bahwa dalam jenis skema digital signature ini, kerentanan seringkali terletak pada cara penghasilan nilai k (nonce). Generasi k tidak boleh lemah karena dapat dieksploitasi untuk mengambil private key (x).

Seperti yang disebutkan di halaman Wikipedia yang saya bagikan sebelumnya, penggunaan nonce yang sama lebih dari sekali tidak diperbolehkan dalam jenis skema digital signature ini. Alasannya adalah kita dapat memulihkan private key (x) jika menggunakan k yang sama saat menandatangani dua pesan berbeda. Mari kita lihat persamaan penandatanganan di bawah ini untuk memahami mengapa kita dapat memulihkan k jika digunakan kembali untuk menandatangani pesan yang berbeda:

s1=(k−xe1)mod  qs2=(k−xe2)mod  q\begin{align} s_1 = (k - xe_1) \mod q \\ s_2 = (k - xe_2) \mod q \\ \end{align}

Dengan mengurangkan kedua persamaan di atas, mengambil nilai xx menjadi sangat mudah karena kita mengetahui nilai s1s_1, s2s_2, e1e_1, e2e_2, dan qq. Kita dapat mengatur ulang kedua persamaan tersebut untuk mendapatkan xx.

(s1−s2)=k−k−x(e1e2)mod  qx=−(s1−s2)(e1e2)−1mod  q\begin{align} (s_1 - s_2) = k - k - x(e_1e_2) \mod q \\ x = -(s_1 - s_2)(e_1e_2)^{-1} \mod q \\ \end{align}

Jadi, jika kita menandatangani dua pesan yang berbeda dengan k yang sama, kita akan dapat memulihkan x dan menandatangani pesan yang diperlukan.

Sekarang kita tahu bahwa kita perlu menandatangani dua pesan yang berbeda dengan nilai k yang sama, mari kita lihat bagaimana k dihasilkan.

server.py

def H(self, msg):
return bytes_to_long(md5(msg).digest()) % self.q
def sign(self, msg):
k = self.H(msg + long_to_bytes(self.x))
print(f'{k = }')
r = pow(self.g, k, self.p) % self.q
e = self.H(long_to_bytes(r) + msg)
s = (k - self.x * e) % self.q
return (s, e)

Perhatikan bahwa generasi k (nonce) pada dasarnya hanya md5(msg || x). Seperti yang disebutkan dalam banyak artikel, menghasilkan collision hash dengan md5 itu mudah. Ini adalah kelemahan dalam implementasinya. Karena kemudahan dalam menghasilkan collision hash md5, sangat mungkin kita dapat menandatangani dua pesan yang berbeda dengan k (nonce) yang sama, yang mengarah pada ekstraksi private key.

Eksploitasi

Membaca artikel ini membantu saya memahami mengapa cara tantangan ini menghasilkan k itu lemah. Mudah untuk menghasilkan collision hash md5, yang berarti kita dapat menandatangani dua pesan yang berbeda dengan nilai k yang sama karena collision tersebut.

Setelah membaca artikel tersebut, saya menyadari bahwa cukup sederhana untuk mengeksploitasi kelemahan md5. Kita hanya perlu mengambil dua string yang memiliki collision hash md5 dan menggunakan itu sebagai pesan kita untuk ditandatangani. Namun, kita perlu berhati-hati karena msg yang kita kirim akan ditambahkan dengan x juga. Oleh karena itu, kita tidak dapat mengirimkan msg mentah ke server. Seperti yang disebutkan dalam artikel sebelumnya, md5 akan melakukan padding terhadap msg terlebih dahulu dengan beberapa byte saat hashing. Jadi, kita perlu mengirimkan pesan yang sudah dipadding ke server. Ini memastikan bahwa sebelum proses md5 menambahkan byte x, kedua pesan yang kita kirim akan memiliki state md5 yang sama. Jadi, ketika algoritma md5 mencoba memproses blok x yang ditambahkan, state akan sama, yang berarti akan menghasilkan hash yang sama.

Setelah kita berhasil menghasilkan collision md5, kita dapat mengambil kembali private key x berdasarkan persamaan sebelumnya yang telah saya jelaskan karena nilai k digunakan kembali.

Berikut adalah script yang kami gunakan untuk mengeksploitasi kerentanan diatas.

solve.sage

from pwn import *
from hashlib import md5
from Crypto.Util.number import *
# Use two strings that has md5 collisions
m1 = bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa200a8284bf36e8e4b55b35f427593d849676da0d1555d8360fb5f07fea2')
m2 = bytes.fromhex('4dc968ff0ee35c209572d4777b721587d36fa7b21bdc56b74a3dc0783e7b9518afbfa202a8284bf36e8e4b55b35f427593d849676da0d1d55d8360fb5f07fea2')
assert m1 != m2
'''
After we properly padding the above string to follow the specification of MD5,
(64-bytes per block), both of the string will produce the same state.
So, if you append any same string, the produced hash will still be the same.
#
In this case, k = HASH(m11 || x) == HASH(m22 || x) will be the same.
But, HASH(r || m11) != HASH(r || m22), because the 64-bytes block are different
#
So, if we sign this two message, it is basically the same case as re-used nonce k,
which is vulnerable. Notice this.
s2-s1 = k2-k1 - x(e2-e1)
If k2 == k1, that means:
x = -1 * (s2 - s1) * (e2-e1)^-1
'''
m11 = m1 + b"\x80" + b"\x00" * 55 + p64(0x200)
m22 = m2 + b"\x80" + b"\x00" * 55 + p64(0x200)
io = remote(b'142.93.35.133', int(31079))
io.recvuntil(b': ')
# Retrieve the public key
g = int(io.recvline())
io.recvuntil(b': ')
y = int(io.recvline())
io.recvuntil(b': ')
p = int(io.recvline())
q = int((p-1)//2)
# Sign the padded messages
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', m11.hex().encode())
io.recvuntil(b': ')
s1, e1 = eval(io.recvline())
io.sendlineafter(b'> ', b'S')
io.sendlineafter(b'> ', m22.hex().encode())
io.recvuntil(b': ')
s2, e2 = eval(io.recvline())
# Recover x
x = (((s2-s1) * inverse_mod(e2-e1, q)) * -1) % q
print(f'recovered x = {x}')
# Sign the required message and send it to the server
msg = b'I am the left hand'
def H(msg):
return bytes_to_long(md5(msg).digest()) % q
k = H(msg + long_to_bytes(x))
r = pow(int(g), int(k), int(p)) % q
e = H(long_to_bytes(r) + msg)
s = (k - x * e) % q
io.sendlineafter(b'> ', b'V')
io.sendlineafter(b'> ', msg.hex().encode())
io.sendlineafter(b'> ', str(s).encode())
io.sendlineafter(b'> ', str(e).encode())
io.interactive()

Dapat dilihat pada gambar dibawah bahwa script kita berhasil mendapatkan digital signature yang tepat untuk string 'I am the left hand', sehingga server mengembalikan flag yang seharusnya tidak boleh kita dapatkan.

Kesimpulan

Tantangan ini membuka mata kita terhadap pentingnya pemilihan algoritma hash yang kuat dalam skema digital signature. Dengan mengeksplorasi kelemahan md5 dan bagaimana collision hash dapat dieksploitasi, kita dapat melihat betapa mudahnya mengambil kembali private key dalam skema yang menggunakan Schnorr Signature Algorithm dengan nonce yang lemah. Ini menunjukkan bahwa dalam dunia kriptografi, keamanan tidak hanya terletak pada algoritma itu sendiri, tetapi juga pada bagaimana komponen-komponennya, seperti nonce, diimplementasikan. Pemahaman mendalam mengenai topik ini penting tidak hanya bagi para ahli keamanan, tetapi juga bagi siapa saja yang berkecimpung dalam teknologi digital.

Di Cylabus, kami berdedikasi untuk memberikan wawasan dan solusi terbaru dalam bidang keamanan digital dan kriptografi. Jika Anda membutuhkan konsultasi atau layanan terkait keamanan siber, blockchain, atau kriptografi, tim ahli kami di Cylabus siap membantu. Hubungi kami untuk memastikan bahwa infrastruktur digital Anda aman dari ancaman terkini. Melalui kerja keras dan inovasi terus-menerus, Cylabus berkomitmen untuk memajukan keamanan digital dan membantu menciptakan dunia digital yang lebih aman untuk semua.

Baca Artikel Kami Yang Lain

banner

Hati-hati, Screenshot HP Kamu Bisa Bocorin Rahasia!

Demonstrasi Kerentanan Screenshot (CVE-2023-21036) di kehidupan sehari-hari dan simulasinya dalam CTF Digial Forensic

banner

Eksploitasi JS Engine: Bahaya Image WebP

Mengungkap seni eksploitasi QuickJS Engine melalui studi kasus CVE-2023-4863 terkait bahaya gambar dengan format WebP.

banner

Eksploitasi macOS: Tantangan BabyIOKit Driver

Memahami seluk-beluk eksploitasi macOS melalui analisis mendetail terhadap IOKit driver yang rentan.