داستان از اونجا شروع شد که یک متخصص امنیت و یک متخصص دیتاساینس تصمیم گرفتن آخر هفته‌ی خودشون رو با هم بگذرونند! ایده اصلی این بود که بینیم چندتا حالت محتمل برای کد ملی وجود داره و ازشون Rainbow Table بسازیم. اینطوری کدملی ایرانی هایی که حتی متولد هم نشدند رو میتونیم داشته باشیم و اگر کسی (خدایی نکرده!) پسوردش رو کد ملیش انتخاب کرده باشه به راحتی پسوردش شکسته میشه :)
برای قسمت اول ایده ما نیاز داشتیم نحوه تولید کدملی رو بدونیم. ظاهرا جایی به صورت رسمی الگوریتم تولید رو کدملی منتشر نکرده ولی با یک گوگل کردن ساده مشخص شد قبلا افرادی روی این مسئله کار کردند:
کد ملی شماره ای است 10 رقمی که از سمت چپ سه رقم کد شهرستان محل صدور شناسنامه ، شش رقم بعدی کد منحصر به فرد برای فرد دارنده شناسنامه در شهرستان محل صدرو و رقم آخر آن هم یک رقم کنترل است که از روی 9 رقم سمت چپ بدست می آید. برای بررسی کنترل کد کافی است مجدد از روی 9 رقم سمت چپ رقم کنترل را محاسبه کنیم.
فرض کنید کد 0932833810 رو می خواهیم بررسی کنیم:
s = (2 x 1) + (3 x 8) + (4 x 3) + (5 x 3) + (6 x 8) + (7 x 2) + (8 x 3) + (9 x 9) + (10 x 0) = 220
r = s % 11 = 0 --> r = 220 % 11 = 0
r < 2 => check-digit = r r >= 2 => check-digit = 11 - r ------------------------------------------ 20 < 2 --> check-digit = 0 ✓
بعد از به دست آوردن الگوریتم کدش رو نوشتیم:
اگر دقت کرده باشین شماره کارت بانکا و شماره سریال IMEI گوشیا هم از همین قاعده پیروی میکنن، اسم این قاعده Luhn algorithm هست، اینجا دربارش بیشتر بخونین.
مرحله‌ی دوم حاسبه‌ی تمام حالت های محتمل کدملی بود، با یک محاسبه ی سرانگشتی میشه فهمید تمام حالت هایی که باید چک بشن 10 به توان 10 حالته و پیدا کردن حالت های محتمل توی این فضای جستجو راحت و سرراست نیست! ابتدای کار ما یک اسکریپت پایتون داشتیم که خیلی بهینه نبود، توی هر 20 دقیقه فقط یک کدملی رو پیدا می کرد! تصمیم داشتیم از زبان های robust تر با کاربج کالکتور های راحت گیر تر! مثل Go و Rust استفاده کنیم ولی گفتیم ترند های دیتاساینسی رو نشکنیم! در نتیجه نهایتا دست به دامن تکنیک های Optimization شدیم. از جمله بهینه سازی ها؛ مثلا میتونیم فقط 9 رقم رو چک کنیم چون میشه از روی بقیه ارقام رقم کنترل رو ساخت یا اینکه بصورت دسته‌ای کد ملی ها رو ذخیره کنیم تا هر با flow اجرای کد بخاطر نوشتن روی هارد کند نشه و چندتا کار دیگه.
بعد از بهینه سازی ها روی کد و اجراش روی گوگل کولب، سرعت تست رسید به تقریبا 11 میلیون کدملی در دقیقه! بعد از اتمام اجرای کد ما یک میلیارد حالت داشتیم:
!cat final.txt | wc -l 100000000
با توجه به اینکه توزیع کدملی ها در فضای جستجو توزیع یکنواخته (Uniform Distribution) می فهمیم که تعداد کد ملی به دست آمده درسته. شاید با خودتون فکر کنید که ما 3 رقم شهر ها رو فراموش کردیم! اصلا! چون لیست قطعی از 3 رقم شهرها در دسترس نیست جدا حسابشون کردیم:
بعدا از اجرای این کد تعداد کد ملی های valid به ۵۹۷ میلیون عدد کاهش پیدا کرد.
!cat prefix.txt | wc -l 597000000
ما به دلیل کپچا های مکرر کولب و خطا های عجیب و غریب I/O قسمتی از محاسبات رو روی سرور های کلاستر انجام دادیم، مشخصلات سرور استفاده شده:
ما براتون تمام کد های استفاده شده در این مرحله رو روی کولب گذاشتیم، خودتون اجراشون کنید، اگر نمی دونید کولب چیه از اینجا شروع کنید.
https://colab.research.google.com/drive/1AIqGd9PIFjj_ORxEEM1g7HIP2RTbTbBD?usp=sharing
کل دیتاست ها رو هم براتون روی کگل گذاشتیم، با اونام میتونید کارای باحال بکنید (مثلا نظیر کردن آمار تولد و مرگ ایرانی ها به کدملی ها و Visualize کردنش):
https://www.kaggle.com/johntukey/iranian-national-code-dataset-1b
هشدار: تکنیک های مطرح شده در این نوشته صرفا جهت مقاصد آکادمیک می‌باشد. هر گونه عواقب قانونی ناشی از استفاده‌ی خلاف قانون بر عهده‌ی فرد خاطی است و از نویسندگان این مطلب سلب مسئولیت می‌گردد.
قدم سوم ساختن جداول رنگین‌کمانی بود، شاید باورتون نشه چه درصد زیادی از کاربران ایرانی کد ملی خودشون رو به عنوان رمز عبور اینستاگرام یا رمز وای‌فای انتخاب می‌کنند! نتیجتا تصمیم گرفتیم یک برای آنالیز آماری راحت‌تر، جداول رنگین کمانی از تمام حالت های ممکن برای کدملی را بسازیم.
بصورت خلاصه ما هش کد ملی ها رو ذخیره می کنیم تا اگر بعدا جایی بهشون بر خوردیم بتونیم بدون نیاز به BruteForce کردن و خیلی سریع مقدار اصلی پسورد رو بازیابی کنیم. ما در این تحقیق هش md5 رو در نظر گرفتیم. چندین تکنیک مختلف رو با ساختن جداول رنگین کمانی مقایسه کردیم تا بتونیم بهینه ترین تکنیک رو پیدا کنیم.
هش‌کت ابزاریه که به ما اجازه میده به انواع الگوریتم های رمزنگاری حمله کنیم، ابتدا یک کد ملی رو بصورت رندوم از فایل final.txt انتخاب می کنیم تا در تمام تست هامون استفاده کنیم:
shuf -n 1 prefix.txt 5263090897
سپس md5 :
echo -n "" | md5sum | cut -d " " -f 1 > hash.lst cat hash.lst 1c48193f26f2f5dfd2037139569b4c9c
حمله‌ی بروت فورس با ورودی فایل final.txt:
hashcat -a 0 -m 0 ./hash.lst ./final.txt --optimized-kernel-enable -w 4 -D 2 --status --potfile-disable 1c48193f26f2f5dfd2037139569b4c9c:5263090897 GPU...............:Tesla T4 Session..........: hashcat Status...........: Cracked Hash.Name........: MD5 Hash.Target......: 1c48193f26f2f5dfd2037139569b4c9c Speed.#1.........: 2447.7 kH/s (4.23ms) @ Accel:8192 Loops:1 Thr:32 Vec:1 Finished in 9m 44s (584.863s)
حمله ی بروت فورس با تمام حالت های ممکنه (10^10 حالت):
hashcat -a 3 -m 0 ./hash.lst ?d?d?d?d?d?d?d?d?d?d --optimized-kernel-enable -w 4 -D 2 --status --potfile-disable 1c48193f26f2f5dfd2037139569b4c9c:5263090897 GPU...............:Tesla T4 Session..........: hashcat Status...........: Cracked Hash.Name........: MD5 Hash.Target......: 1c48193f26f2f5dfd2037139569b4c9c Guess.Mask.......: ?d?d?d?d?d?d?d?d?d?d [10] Speed.#1.........: 10080.0 MH/s (90.52ms) @ Accel:512 Loops:1000 Thr:256 Vec:1 Finished in 0 m (14.679s)
برای ساختن جدول ما از پروژه‌ی Cryptohaze استفاده میکنیم، نقطه قوت جدول ها به fileformat خاصشونه (که بر اساس مدل Markov chain بنا شدند)، وقتی دارید جدول رو می سازید باید بهینه ترین مقدار رو برای دو پارامتر chain length و chain number پیدا کنید، میتونید از ماشین حساب هایی مثل این استفاده کنید. به صورت خلاصه هر چه طول chain ها طولانی تر باشه زمان و حافظه بیشتری برای تولید جدول نیازه و تعداد جداول بیشتری به طبع تولید میشه و زمان بیشتری برای سرچ درشون نیازه.
پارامتر های دیگه‌ای هم مثل reduction function برای تنظیم هست که میتونید برای بهینه کردنشون مقاله معروف Making a Faster Cryptanalytic Time-Memory Trade-Of رو از آقای Philippe Oechslin بخونید.
ساختن جدول:
./GRTGen-CUDA -h MD5 -c ./charsets/charsetnumeric -l 10 -i 1000 --chainlength 50000 --numchains 12640738 -t 256 -b 2048 --numtables 4
Creating table 1 of 4 Creating GRTV2 output table. Generating V2 table with 126 bits in hash. Random seed: 2449740434 Output to: parts/MD5-len10-idx1000-chr10-cl50000-sd2449740434-0-v2.part Table version: 2 Hash: MD5 GPU :Tesla T4 Password length: 10 Table index: 1000 Chain length: 50000 Num chains: 12640738 Perfect table: No Charset length: 10 Charset: 0123456789 Bits of hash: 126 Bits of pass: 34 Kernel Time: 194.990 ms Step rate: 11413.06 M/s Done: 99.65% Finished in 4m 9s (248.935)
سرچ در جدول:
./GRTCrack-CUDA -h MD5 -f ./hash.lst ./parts/* All hashes found GPU :Tesla T4 Num Hashes: 1 To regen: 1469761 Merged chains: 1469761 Chains found: 1470757 Using unindexed search! Cannot find index file. CH after merge: 47985 CH before merge: 50000 Thread 0 out of WU Num Chains: 12640738 Chain Len: 50000 Index: 1000 Pass Len: 10 Table Ver: 2 Table Info Loaded 1 hashes 1C48193F26F2F5DFD2037139569B4C9C:5263090897 Finished in 0 min (1.945s)
جدول ساخته شده در کگل دردسترسه.
ایده‌ی خلاقانه‌ای که ما داشتیم این بود که با استفاده از Google Big Query هش ها رو کرک کنیم، با استفاده از این سرویس میشه توی دیتا با حجم های خیلی زیاد query زد (تقریبا جادو کرد!)، دیتای خروجی ما هم با حجم 11 گیگ و فرمت text به راحتی قابل سرچ نبود در نتیجه سپردیمش به گوگل.
کاری که در واقع ما انجام دادیم ساختن hash ها on the fly و مقایسه اون ها با تمام کدملی های محتمل بود (دیتاست ورودی حاوی هش ها نبود، هش ها موقع سرچ ساخته می‌شد). اگر با سرویس GBQ آشنایی ندارید میتونید از اینجا شروع کنید.
ابتدا فایل هامون رو به فرمت csv تبدیل می کنیم چونکه گوگل raw text قبول نمی‌کنه:
سپس به عنوان External resources ادش میکنیم، یک دیتاست جدید میسازیم و در دیتاست یک تیبل جدید:
برای اضافه کردن دیتاست ها به gbq خودتون میتونید از این id ها استفاده کنید:
final.csv: https://drive.google.com/open?id=1YR92FkL_xfINlv8VmX8EAQ0hPtyHywnE prefix.csv: https://drive.google.com/open?id=1-0nMi2Hl0Z7B9Db9QTtUIwv_h4Mw_1XC
حالا میتونیم روی final.csv کوئری بزنیم.
برای تست هش کدملی رو میسازیم:
cat ./qby-hash.py import hashlib,base64 print(base64.b64encode(hashlib.md5(b'5263090897').digest()).decode()) python3 ./qby-hash.py HEgZPyby9d/SA3E5VptMnA==
حالا هش تولید شده رو در query جایگذاری میکنیم:
SELECT int64_field_0 FROM `onyx-yeti-226515.31337.final_csv` WHERE MD5(CAST(int64_field_0 AS STRING)) = FROM_BASE64('HEgZPyby9d/SA3E5VptMnA==')
همونطو که مشاهده میکنید گوگل زیر 1 دقیقه هش رو برای ما کرک کرد!
در جدول پایین زمان اجرای تمام تکنیک ها رو با هم مقایسه میکنیم:
همونطور که می بیند سریع ترین تکنیک، جدول رنگین کمانی هست، بروت فورس با وردلیست به دلیل لود کردن در رم و خواندن از هارد خیلی کندتر از بروت فورس کور هست، ممکنه به دلیل نزدیک بودن زمان بروت‌فورس کور به زمان جدول این تکنیک رو کاربردی ندونید ولی در مقایسه با دیگر الگورتیم های hashing که سختی محاسباتی بیشتری دارند، پروفرومنس واقعی جداول مشخص میشه. از جدول های آماده ی آنلاین هم استفاده کردیم ولی حاوی کد ملی مدنظر ما در آزمایش نبودند. یه مورد هم نگه داشتیم برای شما، بیبیند میتونید هش هر کدملی به دیتاست اضافه کنید و زمان اجراش رو روی GBQ محاسبه کنید؟
? ما شما رو عمیقا تشویق میکنیم با این دیتاست ها کار های باحال بکنید، اگر کردید، به ما خبر بدید ما با اسم خودتون انتهای این مقاله یا در بلاگ پستی دیگر منتشر میکنیم :)
? کانال ما در تلگرام و وحید رو در توییتر فالو کنید!
? این مقاله رو با دوستانتون به اشتراک بزارید و با کامنتاتون خوشحالمون کنید ❤️
