Dalam semangat Kontes C yang curang , saya memulai Kontes Code yang curang. Tujuan dari kontes ini adalah untuk langsung menerapkan beberapa kode, sambil menyembunyikan bug jahat di dalamnya.
Kontes
Anda adalah tikus Rusia rahasia yang bekerja di departemen TI agen mata-mata Amerika. Bos Amerika Anda baru saja meminta Anda untuk menerapkan algoritma hashing kata sandi yang akan digunakan untuk mengenkripsi pesan rahasia.
Bos Anda ingin Anda menerapkan fungsi berikut:
f: String -> byte[16]
yang mengubah kata sandi menjadi kuantitas 16-byte yang cocok untuk digunakan sebagai kunci AES. Bos Anda menginginkan fungsi yang aman, yang dalam konteks ini berarti bahwa rangkaian kata sandi yang berbeda harus menghasilkan hasil yang berbeda dengan probabilitas yang luar biasa. Misalnya, mengembalikan hash md5 dari input akan menjadi implementasi sederhana f
.
Tentu saja, bos Anda yang sebenarnya di agen mata-mata Rusia ingin Anda menumbangkan proses ini. Tugas Anda adalah mengimplementasikan f
sedemikian rupa sehingga Rusia dapat mendekripsi semua pesan rahasia yang dienkripsi menggunakan kunci yang dikembalikan oleh f
.
Untuk melakukannya, Anda harus menerapkan f
sehingga hanya mengembalikan sebagian kecil dari 2 ^ 128 output yang mungkin. Khususnya, Anda f
harus mengembalikan paling banyak 2 ^ 16 hasil yang berbeda sehingga Rusia dapat melakukan pencarian dengan mudah untuk mencari kunci yang benar untuk setiap pesan terenkripsi yang ingin mereka dekripsi.
Namun perlu diingat bahwa spionase membawa hukuman mati. Agar tidak ketahuan, fungsi Anda f
harus menghasilkan setidaknya 2 ^ 8 hasil yang berbeda, sehingga inspeksi sepintas dari beberapa output f
tidak mungkin untuk mengungkapkan duplikat. Dan yang paling penting, kode yang Anda perkenalkan untuk membatasi rentang f
harus terlihat tidak disengaja, tidak disengaja. Jika Anda pernah dibawa ke ruang sidang, pasti ada keraguan yang masuk akal apakah Anda memperkenalkan bug secara sengaja atau tidak sengaja.
Menilai
Saya dan dua orang lain yang saya rekrut akan menilai entri (email saya jika Anda ingin menilai). Saya menawarkan hadiah 200 reputasi untuk entri yang menang. Kiriman harus diunggah sebelum 1 Mei.
Menilai akan mempertimbangkan kriteria berikut:
- Apakah
f
mematuhi spesifikasi, yaitu apakah itu menghasilkan antara 2 ^ 8 dan 2 ^ 16 output yang mungkin. Jangan merasa ini adalah batas yang sulit, tetapi kami akan mengurangi poin jika Anda terlalu jauh dari jangkauan. - Apakah bug itu masuk akal akibat kesalahan yang tidak disengaja?
- Apakah output
f
terlihat acak? - Semakin pendek implementasi Anda
f
, semakin baik. - Semakin jelas implementasi Anda
f
, semakin baik.
Catatan
Anda dapat menggunakan bahasa apa pun untuk menerapkan kode Anda. Anda mencoba menyembunyikan bug di depan mata, jadi kode yang dikaburkan tidak disarankan.
Anda mungkin ingin melihat beberapa pemenang kontes C sebelumnya yang curang untuk merasakan apa yang membuat pengajuan yang baik.
String input akan dapat dicetak ascii (32 hingga 126, inklusif). Anda dapat mengasumsikan panjang maksimal yang masuk akal jika Anda mau.
sumber
Jawaban:
C
2 ^ 16 kemungkinan keluaran (atau 2 ^ 8 kali jumlah karakter yang digunakan).
Menggunakan implementasi MD5 Linux, yaitu AFAIK, baik. Tapi ini memberikan hash yang sama, misalnya, untuk "40" dan "42".
EDIT: Berganti nama
bcopy
menjadimemcpy
(parameter bertukar tentu saja).EDIT: Dikonversi dari program ke fungsi, untuk memenuhi persyaratan yang lebih baik.
sumber
bcopy
langkah ... ini adalah sedikit penyesatan, karenabcopy
fungsi BSD yang sebenarnya akan berfungsi dengan baik di sini.bcopy
buggy. Saya akan mengubahnyamemcpy
, dan implementasi yang sama akan menjadi valid.C
Ini mungkin bukan entri kontes yang paling mencolok, tapi saya pikir yang berikut ini adalah jenis fungsi hash yang bisa dibuat oleh pembuat kode yang terlalu pintar untuk kebaikan mereka sendiri, dengan gagasan samar-samar tentang jenis operasi yang Anda lihat dalam fungsi hash:
Bahkan fungsi hash dapat mengembalikan tidak lebih dari L * 2048 hasil yang berbeda, di mana L adalah jumlah panjang string input yang berbeda yang dapat terjadi. Dalam prakteknya, saya menguji kode pada 1,85 juta baris input unik dari halaman manual dan dokumen html di laptop saya, dan hanya mendapatkan 85428 hash unik yang berbeda.
sumber
Scala:
Tes, jika hasilnya tidak mirip dengan input yang sama:
Kesalahan menggunakan bilangan prima hanya untuk pengkodean. Dari pada
nilai, kita akhiri dengan
karena ada 54 bilangan prima di bawah 256.
sumber
5.22e27 >> 2^16
. Tidak ada cara untuk memaksa sebanyak mungkin kemungkinan itu.