1
کدهای احراز تمامیت پیام و توابع درهم ساز
پیش در آمد
در این فصل روشهای حفظ پیام در برابر تغییرات ناخواسته و شناسایی صحت محتوای پیامها مطالعه میشوند.
ابزارها:
کدهای احراز هویت پیام
توابع درهم ساز
چهارچوب مطالعاتی رمزنگاری کلید خصوصی میباشد.
فهرست مطالب
مفاهیم اولیه
رمزنگاری کلید خصوصی و کدهای تشخیص خطا
کد های احراز تمامیت پیام
اصول توابع درهم ساز
توابع درهم ساز مهم
HMAC
احراز تمامیت پیام چیست؟
اطمینان از:
تمامیت پیام؛ یعنی پیام دریافتی دستکاری نشده است:
بدون تصحیح،
بدون درج،
بدون حذف
پیام از جانب فرستنده ادعا شده ارسال شده است
Alice
Bob
0 1 1 0 1 …
Adversary EVE
Shared Network
محرمانگی
تمامیت پیام
اهمیت تمامیت پیام
در بسیاری از کاربرد ها، مثلاً تراکنشهای بانکی، اینکه ارتباطات مخفیانه باشند اهمیت زیادی ندارد ولی اینکه محتوای آنها قابل اعتماد باشند از اهمیت بسیار بالاتری بر خوردار است.
یک نکته
رمزنگاری مرسوم (کلید خصوصی):
کدهای احراز تمامیت پیام
احراز تمامیت پیام
رمزنگاری کلید عمومی:
امضای دیجیتال
احراز تمامیت پیام
عدم انکار
موضوع این فصل
ایده اساسی
طرفین یک کلید مخفی به اشتراک بگذارند.
ارسال هر پیام، به همراه یک برچسب که تابعی است از:
کلید مخفی و متقارن
پیام
به طوری که:
بدون دانستن کلید تولید این برچسب نا ممکن باشد.
با تغییر پیام، برچسب کاملاً تغییر کند.
راه کارهای احراز تمامیت پیام
رمزنگاری کلید خصوصی
استفاده از توابع درهم ساز برای احراز تمامیت پیام
کد احراز تمامیت پیام
همه میتوانند پیام را بخوانند، ولی تنها صاحب کلید مخفی میتواند تمامیت آن را بررسی کند.
رمزنگاری کلید خصوصی برای احراز تمامیت پیام
فرستنده پیام را رمز میکند.
اگر متن رمز شده دستکاری شود هنگام رمز گشایی به متن واضح نامفهوم (درهم و برهم) میرسیم.
گیرنده، بعد از رمز گشایی چک میکند که آیا پیام مفهوم است یا نه؟
مشکلات رمزنگاری
بررسی مفهوم بودن محتوی همواره آسان نیست:
در حالت کلی نوعی افزونگی یا ساختار درونی مورد انتظار را جستجو میکنند.
بررسی قواعد زبان (فارسی، انگلیسی،… )
دشواری خودکارسازی فرآیند چک کردن ….
هنگام ارسال داده
اگر داده ها خود تصادفی به نظر برسند، یعنی از ساختار درونی خاصی تبعیت ننمایند، بررسی محتوی تقریباً ناممکن است
راه حل: استفاده از کدهای تشخیص خطا
مثال: یک بیت به انتهای پیام اضافه نماییم، به گونه ایی که تعداد بیتهای یک زوج شود.
یک کد متداول CRC
کدهای تشخیص خطا
تابع F یک کد تشخیص خطا است
اضافه نمودن “ دنباله بررسی قالب ”، FCS، توسط تابع F
یک مثال از تابع F ، کد CRC می باشد.
گیرنده، بعد از رمز گشایی چک میکند که آیا “ دنباله بررسی قالب “ محاسبه شده توسط F با برچسب پیام مطابقت دارد یا نه؟
نا امن بودن کدهای تشخیص خطا-1
کدهای تشخیص خطا مانند CRC برای تشخیص خطای حاصل از نویز در کاربردهای مخابراتی طراحی شده اند.
نویز:
تغییرات غیر هوشمندانه و غیر عمدی
دشمن:
تغییرات هوشمندانه و عمدی
حملات موفقی به الگوریتمهایی که از کدهای تشخیص خطا استفاده میکردند، صورت پذیرفته است.
مثال: پروتکل IEEE 802.11
پروتکلIEEE 802.11
برای امنیت مخابرات سیار
الگوریتم رمزنگاری دنباله ایی RC4 و کد تشخیص CRC
ضعف پروتکلIEEE 802.11
برای امنیت مخابرات سیار
الگو ریتم رمزنگاری RC4 و کد تشخیص CRC
CRC یک الگو ریتم خطی است:
CRC(X Y) = CRC(X) CRC(Y)
RC4 نیز خاصیت زیر را دارد:
RC4(k,X Y) = RC4(k,X) Y
حمله:
RC4(k,CRC(XY)) = RC4(k,CRC(X)) CRC(Y)
تصحیح غیر مجاز بسته
010000000000……………………………………
00110…………
RC4k(CRC(XY)) = RC4K(CRC(X)) CRC(Y)
نتیجه گیری
کد تشخیص خطا نمیتواند در حالت کلی از دستکاری بسته ها جلوگیری کند.
راه حل: کد های احراز تمامیت پیام
کد های احراز تمامیت پیام
تولید یک برچسب با طول ثابت:
وابسته به پیام
لزوماً برگشت پذیر نیست
نیازمند یک کلید مخفی مشترک بین طرفین
آنرا به اختصار MAC مینامند. نام دیگر “Cryptographic Checksum”
این برچسب را به پیام اضافه میکنند
گیرنده خود برچسب پیام را محاسبه نموده و با برچسب ارسالی مقایسه میکند.
از تمامیت پیام و هویت فرستنده اطمینان حاصل میشود.
کد های احراز تمامیت پیام
تمامیت
کد های احراز تمامیت پیام
محرمانگی و تمامیت
FAQ-MAC!
آیا MAC همانند امضا غیر قابل انکار است؟
خیر
امضا با یک کلید عمومی ثبت شده بررسی میشود ولی کلید MAC خصوصی و مخفی است
بر خلاف امضاء، دو طرف قادر به ایجاد MAC میباشند.
امنیت MAC
MAC همواره پیامها را به یک طول ثابت می نگارد.
یک به یک نیست
پیامهای متفاوت MAC یکسان دارند.
برای حمله میتوان پیام های متمایزی یافت که برچسب یکسان داشته باشند.
تصادم:
دو پیام با MAC یکسان
ویژگیهای MAC
ویژگیهای یک MAC مناسب :
با دانستن یک پیام و بر چسب آن، یافتن پیام متفاوتی با برچسب یکسان از لحاظ محاسباتی ناممکن باشد.
توزیع خروجی MAC باید یکنواخت باشد تا احتمال اینکه دو پیام تصادفی MAC یکسان داشته باشند، کمینه شود.
نکته: طول برچسب همانند طول کلید در امنیت MAC تاثیر دارد. (بنا به حمله روز تولد)
کداحراز تمامیت پیام DAA
DAA (Data Authentication Algorithm)
استاندارد NIST و ANSI X9.17
بر اساس رمز قطعه ایی DES و مد کاری CBC
همانند رمز نگاری CBC، پیام را پردازش کرده و تنها آخرین قطعه را به عنوان برچسب استفاده میکنیم.
DAA
متن واضح (تقسیم شده به قطعات)
توابع درهم ساز
تابع یک طرفه،
طول ورودی متغیر
طول خروجی ثابت (نگاشت از فضای بزرگتر به فضای کوچکتر)
در حالت کلی، کلیدی در کار نیست!
امنیت توابع درهم ساز-ایده کلی
نگاشت پیامهای طولانی به رشته های کوتاه به گونه ایی که:
یافتن پیامهای متفاوتی که به یک رشته یکسان نگاشته شوند دشوار باشد.
به این رشته عصاره یا چکیده پیام میگوییم.
امنیت توابع درهم ساز
توابع درهم ساز باید یک طرفه باشند.
برای یک h داده شده، باید یافتن x به گونه ایی که h = H(x) از لحاظ محاسباتی ناممکن باشد.
مقاومت در برابر تصادم (ضعیف)
برای یک x داده شده، باید یافتن y به گونه ایی که H(y) = H(x) از لحاظ محاسباتی ناممکن باشد.
مقاومت در برابر تصادم (قوی)
یافتن x و y به گونه ایی که H(y) = H(x) از لحاظ محاسباتی ناممکن باشد
مقایسه تصادم قوی و ضعیف
ممکن است ساختار تابع H طوری باشد که :
بتوان تعداد محدودی x و y یافت به گونه ای که مقادیر تابع تصادم پیدا کنند.(تصادم قوی)
ولی برای یک x داده شده همواره نتوان یک y پیدا کرد بطوریکه H(y) = H(x) (تصادم ضعیف)
ارضاشدن شرط تصادم قوی برای یک تابع دشوار تر از ارضاشدن شرط تصادم ضعیف میباشد.
توابعی که در برابر تصادم قوی مقاومت کنند امنیت بالاتری دارند
امنیت توابع درهم ساز: پیچیدگی حمله
توابع درهم ساز باید یک طرفه باشند.
پیچیدگی جستجوی کامل (آزمون جامع) 2n میباشد، که n طول خروجی تابع است.
مقاومت در برابر تصادم (ضعیف)
پیچیدگی جستجوی کامل (آزمون جامع) 2nمیباشد
مقاومت در برابر تصادم (قوی)
پیچیدگی جستجوی کامل (آزمون جامع) 20.5*nمیباشد
دقت کنید آزمون جامع بیانگر حداکثر امنیت ممکن برای تابع است زیرا ممکن است به دلیل ضعف طراحی، حملات موثرتری نیز امکان پذیر باشد.
با کمک حمله روز تولد
توابع درهم ساز و رمز نگاری متقارن: تمامیت
اگر پیام M’ را بتوان یافت بطوریکه H(M) = H(M’) (تصادم ضعیف)
M را میتوان توسط M’ جعل نمود
خطر
توابع درهم ساز و رمز نگاری متقارن: محرمانگی و تمامیت
توابع درهم ساز و رمز نگاری نا متقارن: امضاء
روشهای دیگر احراز تمامیت پیام
طرفین راز s را مخفیانه به اشتراک گذاشته اند.
بدون استفاده از رمزنگاری
کاربرد عملی زیاد
روشهای دیگر احراز تمامیت پیام
روش قبل + محرمانگی
رمزنگاری صرفاً برای محرمانگی است.
ساختار درونی تابع درهم ساز: ایده اساسی
اعمال مکرر یک تابع فشرده ساز (Ralph Merkle)
اگر تابع فشرده ساز مقاوم در برابر تصادم باشد، تابع درهم ساز نیز همین گونه خواهد بود.
توابع معروفی مانند
5 MD5: Message Digest
SHA-1: Secure Hash Algorithm -1
از همین ایده استفاده میکنند.
ساختار درونی توابع درهم ساز-2
پیام به قطعات Yi تقسیم شده است.
IV یک رشته ثابت میباشد.
CV0=IV
CVi= f(CVi-1,Yi-1)
Hash = CVL
پیام
توجه
برای مطالعه جزییات ساختار توابع به پیوست ها مراجعه فرمایید.
MD5
SHA-1
RIPMED
توابع درهم ساز مهم: MD5
MD5: Message Digest 5
طراحی 1992 توسط “ران ریوست”، یکی از سه طراح RSA
استفاده گسترده در گذشته، اما از کاربرد آن کاسته شده است.
ویژگیها:
پیام به قطعات 512 بیتی تقسیم میشود
خروجی 128 بیتی
امنیت MD5
مقاومت در برابر تصادم (قوی) تحت حمله آزمون جامع: 264
امروزه امن محسوب نمیشود.
حملات کارگر به این الگوریتم یافت شده اند:
Berson سال 1992: حمله تفاضلی به یک دور الگوریتم
Boer وBosselaers سال 93: یافتن تصادم های مجازی
Dobbertin سال 96: تصادم در تابع فشرده ساز
توابع درهم ساز مهم: SHA-1
SHA-1: Secure Hash Algorithm – 1
استاندارد NIST، 1995
طول ورودی < 264 بیت
طول خروجی 160 بیت
استفاده شده در استاندارد امضای دیجیتال DSS
امنیت:
مقاومت در برابر تصادم (قوی) تحت حمله آزمون جامع: 280
امن محسوب میشود
در برابر حملات شناخته شده مقاومت بالایی دارد
گونه های SHA-1
برای سازگاری با AES نسخه های زیر نیز استاندارد شده اند:
SHA-512، SHA-256 و SHA -384
توابع درهم ساز مهم: RIPEMD
طراحی در اروپا در سال 1997
مشخصات همانند SHA-1
قابل مقایسه با SHA-1 از لحاظ امنیت و سرعت
سرعت هر دو تقریباً نصف MD5
مقایسه MD5،SHA-1، RIPEMD-1
HMAC-1
HMAC یک الگوریتم احراز هویت پیام است
HMAC اساساً روشی برای ترکیب کردن کلید مخفی با الگوریتمهای درهم ساز فعلی میباشد.
برای تولید چکیده پیغام، از توابع درهم استفاده شده است
در مقابل استفاده از رمزهای قطعه ای
بدلیل مزایای عملی توابع درهم ساز
HMAC-2
HMAC جزو ملزومات پیاده سازی IPSec میباشد.
HMAC به طور گسترده استفاده میشود (مثلاً SSL)
HMAC: اهداف طراحی
استفاده از توابع درهم ساز بدون تغییر آنها
پشتیبانی از توابع درهم ساز متنوع
حفظ کارایی و سرعت تابع درهم ساز به کار گرفته شده
استفاده ساده از کلید
طراحی روشن و بدون ابهام
HMAC: الگوریتم
H : تابع درهم ساز به کار گرفته شده
:M پیام ورودی
K: کلید مخفی
K+ : کلید مخفی که یک دنباله صفر به آن اضافه شده است
ipad : تکرار رشته 00110110
opad : تکرار رشته 01011010
HMACK = H[(K+ opad) || H[(K+ ipad) || M ]]
پیام
H[(K+ ipad) || M ]
H[(K+ opad) || H[(K+ ipad) || M ]]
HMAC: امنیت
ارتباط دقیق بین امنیت تابع در هم ساز با امنیت HMAC اثبات شده است.
مقاومت HMAC در برابر حمله روز تولد از تابع در هم ساز به کار گرفته شده، بیشتر است.
استفاده از MD5 در هنگام نیاز به سرعت بیشتر مجاز است.
پیوست ها
پارادکس روز تولد
حداقل مقدار k چقدر است به نحوی که در یک گروه k نفری احتمال اینکه دو نفر در یک روز به دنیا آمده باشند بیش از 0.5 باشد؟
پارادکس روز تولد
تعداد حالات ممکن به نحوی که k نفر روز تولد متقاوت داشته باشند:
365*364*… *(365-k+1) = 365!/(365-k)!
احتمال اینکه هر k نفر در یک جمع k نفره دارای روز تولد متفاوت باشند:
P = (365!/(365-k)!)/(365)k
احتمال اینکه حداقل دو نفر در یک جمع k نفره دارای روز تولد یکسان باشند:
1-P = 1- 365!/((365-k)!)*(365)k )
پارادکس روز تولد
پارادکس روز تولد
در میان 23 نفر، احتمال یافتن دو نفر که در یک روز متولد شده اند بیش از 50% میباشد.
پارادکس روز تولد
تعمیم مسئله: حداقل k چقدر است به نحوی که با احتمال بیش از 0.5 یک تکرار در k عنصر داشته باشیم به نحوی که هر عنصر مقادیری در بازه 1 تا n بتواند اختیار کند؟
با تعمیم حل قبلی می توان به دست آورد که:
k=1.18 * n0.5 = n0.5
n= 365 k=23
پارادکس روز تولد
مبنای ریاضی
تابع H با خروجی ممکن را در نظر بگیرید(خروجی m بیتی) H را به k ورودی تصادفی اعمال کنیم و خروجی را مجموعه X در نظر می گیریم. به همین ترتیب مجموعه Y را تشکیل می دهیم. اگر k بزرگتر از باشد، احتمال حداقل یک تصادم در بین اعضای دو مجموعه X و Y بیش از ½ می باشد
حمله روز تولد
ممکن است تصور کنید یک MAC یا Hash 64 بیتی امن است اما…
با حمله روز تولد امنیت از بین میرود:
مهاجم تتت پیام معتبر که اساساً هم معنا هستند تولید میکند. m طول خروجی Hash است.
مهاجم همین تعداد پیامهای دلخواه خود را تولید میکند. ( که معنای ساختگی دارند)
دو دسته پیام مقایسه میشوند تا زوجی یافت شود که Hash یکسان داشته باشند.
از کاربر میخواهیم تا پیام معتبر زوج را امضا نماید، و سپس پیام دلخواه دشمن را جایگزین میکنیم.
مثالی از حمله (نمونه معتبر)
Dear Dean Smith,
This [ letter | message ] is to give my [ honest | frank ] opinion of Prof Tom Wilson, who is [ a candidate | up ] for tenure [ now | this year ]. I have [ known | worked with ] Prof Wilson for [ about | almost ] six years. He is an [ outstanding | excellent ] researcher of great [talent | ability ] known [ worldwide | internationally ] for his [ brilliant | creative ] insights into [ many | a wide variety of ] [difficult | challenging ] problems.
مثالی از حمله (پیام دشمن)
Dear Dean Smith,
This [ letter | message ] is to give my [ honest | frank ] opinion of Prof Tom Wilson, who is [ a candidate | up ] for tenure [ now | this year ]. I have [ known | worked with ] Prof Wilson for [ about | almost ] six years. He is an [ poor | weak ] researcher not well known in his [ field | area ]. His research [ hardly ever | rarely ] shows [ insight in | understanding of ] the [ key | major ] problems of [the | our ] day.
ساختار داخلی توابع درهم ساز
MD5
MD5 Logic
Step 1.Appending padding bits
Congruent to 448 modulo 512
Step 2.Appending length
Length modulo 64
L * 512-bit, N * 32 bit
M[i] : ith word
Step 3.Initialize MD buffer
Four 32-bit register (A B C D), little endian
A = 67482301
B = EFCDAB89
C = 98BADCFE
D = 10325476
MD5 Logic
Step 4.Process message in 512-bit blocks
Four rounds
Each round has a different primitive function, F, G, H and I
Use one-fourth of T[i]
T[i] = 232 * abs(sin(i))
تابع بولی gدر MD5
MD5 Logic
Step 5. Output
MD5 Compression Function
X[i] is used once, during one step
ρ2(i) = (1 + 5i) mod 16
Ρ3(i) = (5 + 3i) mod 16
Ρ4(i) = 7i mod 16
Each step, only 4 bytes is updated
SHA-1
SHA-1 Logic
Step 1. Appending padding bits
Step 2. Append length
Step 3. Initialize MD buffer
Five 32-bit registers, E = C3D2E1F0
Big-endian
SHA-1 Logic
Step 4. Process message in 512-bit blocks
Four rounds of 20 steps
Step 5. Output
SHA-1 Compression Function
Kt is a additive constant varying across rounds
SHA-1 Compression Function
Wt = S1(Wt-16 + Wt-14 + Wt-8 + Wt-3)
RIPEMD
RIPEMD-160 Logic
Step 1. Appending padding bits
Step 2. Append length
Step 3. Initialize MD buffer
Same value is used in SHA-1
Little-endian
RIPEMD-160 Logic
Step4. Processing message
10 rounds of 16 steps
Five primitive functions
f1, f2, f3, f4, f5
Nine additive constant
Addition is involves a rotation
Step5 .Output
RIPEMD Compression function
π (i) = 9i + 5 (mod 16)
RIPEMD Design decision
Two parallel lines are used
Increase complexity of finding collisions between rounds
Two lines use same logic
Simplicity
Difference
Additive constants
Order of primitive functions
Order of processing of message block
Use five words, and rotation of the C word
RIPEMD Design decision
Permutations
Effect that two word that are close in one round are relatively far apart in the next
Circular left
Range from 5 to 15
Different amounts for the five rounds
Not have special pattern (not be divisible by 32)
Not too many shift should be divisible by 4