دستیابی به کد ملی تمام ایرانیان گذشته، حال و آینده!

Vanad — Sat, 14 Aug 2021 20:13:07 +0430

داستان از اونجا شروع شد که یک متخصص امنیت و یک متخصص دیتاساینس تصمیم گرفتن آخر هفته‌ی خودشون رو با هم بگذرونند! ایده اصلی این بود که بینیم چندتا حالت محتمل برای کد ملی وجود داره و ازشون 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 رو در نظر گرفتیم. چندین تکنیک مختلف رو با ساختن جداول رنگین کمانی مقایسه کردیم تا بتونیم بهینه ترین تکنیک رو پیدا کنیم.ورود به زور با Hashcatهش‌کت ابزاریه که به ما اجازه میده به انواع الگوریتم های رمزنگاری حمله کنیم، ابتدا یک کد ملی رو بصورت رندوم از فایل 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)ساختن Rainbow Table با Cryptohazeبرای ساختن جدول ما از پروژه‌ی 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)جدول ساخته شده در کگل دردسترسه.پیدا کردن hash کدملی ها با استفاده از Google Big Queryایده‌ی خلاقانه‌ای که ما داشتیم این بود که با استفاده از Google Big Query هش ها رو کرک کنیم، با استفاده از این سرویس میشه توی دیتا با حجم های خیلی زیاد query زد (تقریبا جادو کرد!)، دیتای خروجی ما هم با حجم 11 گیگ و فرمت text به راحتی قابل سرچ نبود در نتیجه سپردیمش به گوگل. کاری که در واقع ما انجام دادیم ساختن hash ها on the fly و مقایسه اون ها با تمام کدملی های محتمل بود (دیتاست ورودی حاوی هش ها نبود، هش ها موقع سرچ ساخته می‌شد). اگر با سرویس GBQ آشنایی ندارید میتونید از اینجا شروع کنید.ابتدا فایل هامون رو به فرمت csv تبدیل می کنیم چونکه گوگل raw text قبول نمی‌کنه:تبدیل دیتاست ها به csv سپس به عنوان External resources ادش می‌کنیم، یک دیتاست جدید میسازیم و در دیتاست یک تیبل جدید:اضافه کردن datasetبرای اضافه کردن دیتاست ها به 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==')خروجی queryهمونطو که مشاهده میکنید گوگل زیر 1 دقیقه هش رو برای ما کرک کرد!بنچ مارکنیگ و آنالیزدر جدول پایین زمان اجرای تمام تکنیک ها رو با هم مقایسه می‌کنیم:bench markingهمونطور که می بیند سریع ترین تکنیک، جدول رنگین کمانی هست، بروت فورس با وردلیست به دلیل لود کردن در رم و خواندن از هارد خیلی کندتر از بروت فورس کور هست، ممکنه به دلیل نزدیک بودن زمان بروت‌فورس کور به زمان جدول این تکنیک رو کاربردی ندونید ولی در مقایسه با دیگر الگورتیم های hashing که سختی محاسباتی بیشتری دارند، پروفرومنس واقعی جداول مشخص میشه. از جدول های آماده ی آنلاین هم استفاده کردیم ولی حاوی کد ملی مدنظر ما در آزمایش نبودند. یه مورد هم نگه داشتیم برای شما، بیبیند می‌تونید هش هر کدملی به دیتاست اضافه کنید و زمان اجراش رو روی GBQ محاسبه کنید؟سخن پایانی? ما شما رو عمیقا تشویق میکنیم با این دیتاست ها کار های باحال بکنید، اگر کردید، به ما خبر بدید ما با اسم خودتون انتهای این مقاله یا در بلاگ پستی دیگر منتشر می‌کنیم :)? کانال ما در تلگرام و وحید رو در توییتر فالو کنید!? این مقاله رو با دوستانتون به اشتراک بزارید و با کامنتاتون خوشحالمون کنید ❤️

نوشته های Vanad

دستیابی به کد ملی تمام ایرانیان گذشته، حال و آینده!