تحلیل آسیب‌پذیری ۲۰ ساله‌ی الگوریتم فشرده‌سازی LZO

[بخند]

آسیب‌پذیری ۲۰ ساله موجود در الگوریتم فشرده‌سازی LZO1 که در برخی از نسخه‌های اندروید و هسته‌ی لینوکس به‌کار رفته است، بالاخره وصله شد.
کد آسیب‌پذیر در تابع کتاب‌خانه‌ی الگوریتم بیش از دو دهه است که در حال فعالیت می‌باشد، اما این تابع بارها و بارها مورد بازیابی قرار گرفته است و به همین دلیل معرفی وصله برای آن کمی دشوار بوده است. کد این الگوریتم اگرچه طی بیست سال گذشته بارها تغییر کرده است، اما  پایه‌ی اصلی هنوز همان کدی است که در سال ۱۹۹۴ توسط Markus Oberhumer به صورت متن‌باز منتشر شد.
نسخه‌ی 2.07 از این الگوریتم، بالاخره آسیب‌پذیری بیست ساله‌ی مذکور را رفع می‌کند. LZO کتاب‌خانه‌ی فشرده‌سازی داده‌ی مستقل از سکو است که ویژگی خارج کردن از حالت فشرده‌سازی درجا و امکان هم‌پوشانی فشرده‌سازی را دارد. در طی بیست سال گذشته این الگوریتم توانسته بود در بسیاری از پروژه‌های مهم مانند اندروید، OpenVPN ،MPlayer2 ،Libav و هسته‌ی لینوکس جای خود را باز کند. این الگوریتم بسیار پیش‌رفته و کارآمد است و معماری بسیار خوبی دارد که می‌تواند در حالت خارج کردن پرونده‌ها از حالت فشرده‌سازی تا ۴ یا ۵ برابر zlib و bzip سرعت داشته باشد.
الگوریتم LZO به‌قدری کارآمد بوده است که بارها در تجهیزات ناسا به‌کار رفته است و در آخرین کاربرد این الگوریتم در سفینه‌ی مریخ‌نورد  Mars Curiosity Rover به‌کار رفته است که هفته پیش سالگرد اولین حضورش در مریخ را جشن گرفت.
 
تحلیل آسیب‌پذیری
آسیب‌پذیری این الگوریتم که در تمام نسخه‌های آن دیده می‌شود مربوط به سرریز اعداد صحیح است، برای روشن شدن مطلب بهتر است نگاهی به یک نسخه از الگوریتم که در دست‌رس است داشته باشیم، برای این‌کار نسخه‌ای که در هسته‌ی لینوکس مورد استفاده قرار گرفته است و از این‌جا در دست‌رس می‌باشد انتخاب شده است:

کد: [انتخاب]

56 if (likely(state == 0)) { 
57     if (unlikely(t == 0)) { 
58         while (unlikely(*ip == 0)) { 
59             t += 255; 
60             ip++; 
61             NEED_IP(1); 
62             } 
63         t += 15 + *ip++; 
64         } 
65      t += 3;
در کد بالا آسیب‌پذیری سرریز اعداد صحیح2 مشاهده می‌شود، متغیر t، در هر بار اجرای فشرده‌سازی زمانی که متغیر فشرد‌سازی به میزان پوچ می‌رسد، به اندازه‌ی ۲۵۵ واحد افزایش پیدا می‌کند، و این مقداردهی صرف نظر از علامت‌دار بودن یا نبودن متغیر t انجام می‌شود و تنها بررسی می‌شود که بافر ورودی (IP)  شامل بایت است یا خیر، و در این حالت t تا زمانی‌که به یک مقدار صحیح بسیار بزرگ بدون علامت برسد افزایش پیدا می‌کند. اگر t یک عدد ۳۲ بیتی باشد تنها ۱۶ مگابایت صفر لازم است تا مقدار t بسیار بزرگ شود و اگرچه همین‌جا برای t سرریز رخ می‌دهد اما درواقع حملات سوء‌استفاده از این آسیب‌پذیری این‌جا رخ نمی‌دهد.
در ادامه کدی آورده شده است که متغیر t توسط الگوریتم به عنوان پارامتر اندازه استفاده می‌شود، در خط ۶۸ این کد بررسی می‌شود که آیا بافر ورودی (IP) , و بافر خروجی   (OP) به اندازه‌ای بزرگ هستند که t بایت در آن‌ها جای بگیرد یا خیر. اگرچه در نسخه‌ی هسته‌ی لینوکس از این الگوریتم مقدار ۱۵ بایت از ۱۶ بایت بررسی می‌شود که سرریز بافر رخ ندهد، اما این‌ مسئله کافی نیست.

کد: [انتخاب]

66 copy_literal_run:
67 #if defined(CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS)
68    if (likely(HAVE_IP(t + 15) && HAVE_OP(t + 15))) {
69        const unsigned char *ie = ip + t;
70        unsigned char *oe = op + t;
71        do {
72            COPY8(op, ip);
73            op += 8;
74            ip += 8;
75            COPY8(op, ip);
76            op += 8;
77            ip += 8;
78        } while (ip < ie);
79        ip = ie;
80        op = oe;
81    } else
82 #endif

 
دو تابع HAVE_IP و HAVE_OP هرچند برای بررسی اندازه‌ی بافر‌ها می‌باشند تا با اندازه t مطابقت کند، اما قبل از صدا زدن این دو تابع عبارت (t + 15) محاسبه می‌شود و اگر مقدار t به‌ اندازه کافی بزرگ باشد، سرریز عدد صحیح رخ می‌دهد و مقدار عبارت (t + 15) شامل سرریز می‌شود و  ممکن مهاجم سرریز را طوری مدیریت کند که عبارت (t + 15) مقدار صفر تا 14 را برگرداند، یعنی اگر مقدار t برابر 15- تا 1- باشد، حاصل بین صفر تا 14 می‌شود و توابع تصور می‌کنند به اندازه کافی جای دارند و از سرریز بی‌خبر هستند و مشکلات سوء‌استفاده‌های احتمالی از همین‌جا آغاز می‌شود.
 
اگرچه این مشکل تنها در کد وجود دارد، اما از کدی صحبت می‌کنیم که چندین نسخه‌ی آن در انواع پروژه‌های مهم وجود دارد و خسارات و گستردگی حملات احتمالی ممکن است بسیار زیاد باشد. انواع حملات سوء‌استفاده از این آسیب‌پذیری بسته به پروژه‌‌ای که از آن استفاده کرده است ممکن است متفاوت باشد و باید منتظر عکس‌العمل توسعه‌دهندگان بود.

منبع:
http://blog.securitymouse.com/2014/06/raising-lazarus-20-year-old-bug-that.html