پرس و جو روی داده های رمز شده

صفحه 1:
پرس و جو روی داده های رمز شده علی هادوی خرداد ۸۸ درس امنیت پایگاه داده 

صفحه 2:
مقدمه ۶ روش‌های کنترل دسترسی برای محافظت از داده ها کافی يسنن - سرقت رسانه محتوى داده - عدم اعتماد به اعمال كننده خط مشى هاى كنترل دسترسى - امكان دور زدن مكانيزم هاى كنترل دسترسى توسط مهاجمين pw 9 Database as A Service ow! ons 7 bo * ‏های کار گزار غیرقابل اعتماد‎ عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 3:
مدل پایگاه داه به عنوان خدمت * بايكاه داده به عنوان خدمت (5©15106 4 25 192188256) به عنوان رویکردی جدید در برون‌سپاری پایگاه داده‌ها * در دسترس بودن داده ها توسط کار گزار تضمین می شود. *_کلیه اعمال مدیریت داده را کا رگزار فراهم می کند. *_کارگزار از نظر نگهداری داده‌ها و عدم ارسال عمدی پاسخ اشتباه مورد اعتماد است. *_کا رگزار در مورد محرمانگی داده‌ها مورد اعتماد نیست. - کار گزار درستکار ولی کنجکاو است (کتامنتاه ‎(Honest but‏ لان اذك ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 4:
مدل پایگاه داده به عنوان خدمت * چالش اصلی در این مدل تأمین امنیت داده‌های برون‌سپاری شده است. ۶ راه حل اولیه رمزنگاری داده های برون‌سپاری شده است. * برای حفظ محرمانگی مالک داده, داده خود را رمز کرده و آن را در پایگاه داده رمز شده در سمت کار گزار ذخیره میی کند. * ریزدانگی رمزنگاری به خط مشی های محیط برای سطح دسترسی, امنیت و کارایی بستگی دارد. - بیشتر فعالیت ها ریزدانگی را در سطح چندتایی تعریف کرده اند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 5:
عناصر مدل 10845 مالک داده‌ها: فرد یا سازمان است که داده‌ها را ایجاد و آن را برون‌سپاری. می کند. کاربر: پرس‌وجوها را به سیستم ارانه م ی کند. کارخواه: پرس‌وجوهای کاربر را به پرس‌وجوهای قابل اجرا روی داده‌های رمزشده تبدیل می کند. کا رگزار: محل ذخیره‌ی داده‌های رمز شده است و پرس‌وجوهای ارسالی از سمت کارخواه را روی داده‌های رمزشده اجرا کرده و نتیجه را به کارخواه ارائه می‌دهد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 6:
سناريوى برس و جو در مدل 1045 كاربر برس و جوى © رابا توجه به اسكيماى بايكاه داده ی رمز نشده 8 از طريق كارخواه وارد می کند. ‎ -‏ برون سبارى داده مى تواند از ديد كاربر شفاف باشد. كارخواه برس و جوى كاربر را به دو بخش 09 و 00 تقسيم مى كند. 09 برس و جوى اعمال شده بو روی داده هاى رمز شده در سمت كارعزار و ©06 برس و جوى اعمال شده در سمت كارفرما بر روى ذاده هاى بركثتى از ار زره سار خواهاست: أ ارخواه ساغتار يايكاه ذاده عادى و رهز شده وا میداد کارگزار پرس و جوی 625 را روی داده رمز شده اجرا و نتایج (مجموعه ای از چندتایی های رمز شده) را به کارخواه بر میگرداند. کارخواه نتایج را رم زکشایی کرده و چندتایی های اضافی را با اعمال 006 به نتایج اولیه حذف می کند. نتايج نهابى به كارير ارائه مى شود. عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 7:
ij ۱ 0 سناریوی پرس و جو در مدل ‎DAS‏ | تم ‎a‏ ‏0 

صفحه 8:
ملاحظات رمزنگاری در برون سپاری داده روش هایی که بتوانند به طور مستقیم با داده های رمز شده کار کند باید ملاحظات زیر را درنظر بگیرند: - میزان اعتماد به کارگزار * در مدل 10۸5 امکان رمزگشایی توسط کارگزار تامطمتن وجود ندارد. - کارایی روش اجرای پرس و جو * رمزکنایی کل داده های قبل از اجرای پرس و جو کارا یست. - تم رکز اجرای اعمال در سمت کار گزار - سربار قابل قبول برای ذخیره سازی و ارتباطات بین کارفرما و کار گزار - ریزدانگی رمزنگاری * اگررمزتگاری بصورت درشت‌دانه باشد امكان بهيناسازى برس وجو كم مى شود * رمزتكارى به صورت ريز دانه نيز كارابى را كمتر و در شرايطى به ممکن است به مهاجم اجازه استتتاج از داده‌ها را يدهد. - کنترل دسترسی در سیستم های چند کاربره عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 9:
ملاحظات رمزنگاری در برون سپاری داده (۲) ۰ مقاومت در برابر حملات احمله متن رمزشده معلوم: به طور کلی فرض می‌شود که مهاجم به داده رمزشده دسترسی دارد. هدف در این حمله شکستن متن رمزشده خاص يا بيدا كردن كليد است. حمله متن اصلی معلوم: مهاجم به تعدادی متن اصلى و معادل رمزشده آن‌ها دسترسی دارد عه از آن برای به دست آوردن بقیه‌ی متون رمزشده یا پی بردن به کلید رمز استفاده م ی کند. حمله متن اصلی انتخابی: مهاجم می‌تواند معادل رمزشده متن اصلی دلخواه خود را به دست بیاورد. لین حمله, نوع قویتری نسبت به حمله‌ی متن اصلی معلوم است. حمله متن رمز شده انتخابی: مهاجم می‌تواند رمزگشایی شده معادل متن رمزشده دلخواه را بدست آورد. حملات تحلیل فرکانسی: معکن است مهاجم (50:۳05) اطلاعات اولی‌ای راجع به دامنه مقادیر و فرکانس رخداد داده‌های رمزنشده داشته باشد و از آن برای نفوذ به پایگاه داده استفاده کند. حملات مبتنی بر اندازه: ممکن است مهاجم اطلاعاتی راجع‌به ارتباط طول متن اصلی و متن رمزشده داشته باشد.بنابراین اگر مهاجم مجموعه‌ای از داده‌های اصلی و ستن رسز شده مصادل را داشته باشد می‌تواند بهپایگاه داده حمله کند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 10:
ملاحظات رمزنگاری در برون سپاری داده (۳) * پشتیبانی از انواع پرس و جو - پرس و جو روی داده های عددی * پرس و جو با شرط تساوی * پرس و جوی بازه ای - پرس و جو روی داده های رشته ای * پرس و جو با شرط تساوی * پرس و جو های تطبیق الگویی - پرس و جوهای شامل توابع تجمعی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 11:
روش های جستجو روی داده های رمز شده * جستجوی مستقیم روی داده های رمز شده * جستجوی مبتنی بر شاخص * روش های مبتنی بر حفظ ترتیب روش های مبتنی بر توابع همربخت اختفایی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 12:
جستجوی مستقیم روی داده های رمز شده * داده به گونه ای رمز می شود که جستجو بتواند دقیقاً روی همان داده رمز شده به صورت مستقیم صورت گیرد. * سانگک روشی را بر اساس این ایده برای جستجو روی داده های رشته ای ارائه داده است. ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 13:
روش 50170 - معرفی جستجوی کلمات روی اسناد رمز شده (تمر کز بر 1013 نیست) كار برد مفهوم دریچه کار گزار می‌تواند با گرفتن اطلاعات کوچکی در مورد هر کلمه (دریچه)؛ جستجو را بدون اطلاع از کلمات دیگر متن انجام دهد. توابع مبتنی بر دریچه توابعی هستند که محاسبه‌ی معکوس آنها بدون داشتن اطلاعات خاصی به نام دریچه مشکل است. در رمزنگاری مبتنی بر دریچه, رم زگشایی با داشتن دریچه امکان‌پذیر است. در این روش‌ها, به همراه هر کلمه‌ای که کارخواه جستجوی آنرا تقاضا کرده است. دریچه‌ی آن نیز ارسال می‌شود. بدین شکل کارگزار فقط می‌تواند کلمه درخواست شده را رمزکشایی عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 14:
روش ‎Song‏ - رم زگذاری متن اصلی به تعدادی ‎bw dol‏ طول یکسان ( «بیت) تقسیم می شود. اسناد اصلی پس از رمزشدن به روش شرح داده شده به سمت کا رگزار ارسال و در آنجا ذخیره می‌شوند. کار گزار با دریافت دریچه‌ای از طرف کارخواه می تواند کلمه‌ی مورد نظر کاربر را جستجو کند. پارامترهای رمزنگاری 1 : مولدلعداد شبه تسصادفی 2 ۲ 9]: تولبع‌شبه تصادفی 3 > كليد تلبع ؛ (سرلوتهام كلواتعتنئ لسك F:f , (first n-m bits of 15 )980(( ‏دریچه هر كلمه: كليد تابع‎ ۶ عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 15:
روش 50100 - رم زگذاری(۲) ‎٠»‏ رمزگذاری در دو سطح انجام می شود. - سطح اول: * هر کلمه با یکی از الگوریتم‌های رمزنگاری متقارن و کلید (16") رمز می شود. *_کارگزار در هنگام اجرای پرسوجو از کلمه‌ی درخواست شده کارخواه مطلع نمی شود. - سطح دوم: * مولد شبه تصادفیک . دنبالهای از اعداد شبه تصادفی ,5 با طول 10-190 بیت به تعداد کلمات متن اصلی ایجاد می کند. * اعداد شبه تصادفی تولید شده ,5ب استفاده از تابع "1 درهم‌سازی شده و خروجی " بیتی تولید می شود. ۰ (رمزشده‌ی لایه‌ی اول هر کلمه (19۸).برظ)) با ( ,5 و حاصل درهم‌سازی شده در مرحله ‎AJB‏ ‏0 می‌شود. * نتیجه‌ی لایه‌ی دوم رمزتگاري کلمه‌ی ,14 به عنوان امین کلمه‌ی متن رمزشده (:6) در سند. رمزشده قرار مى كيرد. ‎ ‏عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 16:
| 0 fe 8 | 3 He a] | | fe I if روش 5000- رم زگذاری(۳) 

صفحه 17:
روش ‎Song‏ - اعمال پرس و جو کارخواه برای جستجوی یک کلمه ( *) در اسناد رمزشده؛ معادل رمز شده‌ی لایه‌ی اول کلمه (360).) به همراه دريجدى آن ( (1:)34) را به کارگزار ارسال می‌کند. ۲ كارسزار با دريافت ((7.)18) كلمات تمام اسناد را با آن 26018 می‌کند. .2 اگر کلمه‌ی ام سندی با کلمه‌ی درخواست شده برابر باشد. حاصل (,1) 166013 باید ساختاری به شکل <(,5) ررم‌یم ,1۳ برگ > داشته باشد. برای بررسی وجود ساختار فوق برای کلمه‌ی مام متن رمزشده. حاصل تابع 1 روی ‎ow HIM‏ پرارزش ,1 به دست آورده می‌شود. ۶ ار مقدار به دست آمده با بیت باقی‌مانده‌ی .1 برابر باشد. ساختار برقرار بوده و کلمه‌ی ۴ام متن رمزشده به همراه سندی که به آن متعلق است در مجموعه‌ی جواب ارسالی به کارخواه قرار می گیرد. ۰ تابع "۶ یک تابع درهم‌ساز دارای برخورد است. بابراین امکان وجود اشتباه مثبت در نتایج ارسالی به کارخواه وجود دارد. ‎١‏ در سمت کارخواه يس از رمزكثايى سند مقدار اصلی کلمه‌ی پیدا شده با کلمه‌ی درخواست شده‌ی کاربر مقایسه می‌شود تا ناج درستی به کاربربرگردانده شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 18:
روش ‎٩0۳0‏ - رم ز گشایی برای رم زگشایی کلمه‌ی ام سند رمزشده (,6)» ابتدا 11-09 بیت پرارزش ,6 با » رک ۴ می‌شود و 72-70 بيت پر ارزش 5.619 به دست می آید. از مقدار فوق برای ساختن دریچه‌ی 147 استفاده می‌شود. اعمال دریچه بدست آمده و 10-۳0 بیت پر ارزش ,5به تابع «دء 7 بيت نتيجه دارد که با 08 کردن با «بیت کم ارزش 6,۰۳ بیت کم ارزش (18).رت حاصل می شود. بدي ترتیب تمام بیت‌های (5,.)۲۷ به دست میآیند. ‎E(w)‏ یم زکشایی‌شده تا مقدار اصلی ۲۶ حاصلشود. ‏1۸ عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 19:
ویژگی های روش 5070 کار گزار نمی تواند در مورد متن اصلی تنها با استفاده از متن رمز شده اطلاعاتی بدست آورد. سربار ذخیره سازی و ارتباطاتی آن کم است. نتیجه حاوی مکان هلیی از سند است که 1۷ در تن ظاهر شده است و ممکن است دارای اشتباهات مثبت باشد. اشتباهات مثبت جا مقدار ۰« مرتبط است. هر جواب اشتباه با احتمال "1/2 رخ می دهد. بنابراین برای سندی با طول 1 كلمه انتظار 1/2 جواب اشتباه وجود دارد. متن بايد تقسيم به كلماقى جا طول مساوى شود كه با توجه به ساختار زبان» روش مناسبى عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 20:
ویژگی های روش )2( ‎Song‏ امکان جستجو با هر طول دلخواه وجود ندارد. فقط می‌توان کلمات با طول 21 یا ضریبی از بیت را جستجو کرد. گروه محدودی از الگوها قابل جستجو است. - الگوهایی به شکل"[2]2-2" با تبدیل به 22 ر... رطق رططق ره قابل جستجو هستند؛ - جستجوی الگوهایی به شکل "#29" مشکل است. زیرا تعداد رشته‌های تولیدی سيار زياد خواهند شد. در الكوريتم سانگ. برای یافتن هر کلمه باید کل محتویات تمام اسناد جستجو شود. زمان جستجو نسبت به طول متن خطی است. بنابراین در قابل مقیاس بزر کك (مانند پایگاه داده) کارا نیست. - یک روش افزایش سرعت بکارگیری شاخص های از پیش تعریف شده است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 21:
جمع بندی - جستجوی مستقیم روی داده رمز شده فضای ذخیره سازی نسبت به ذخیره سازی داده اصلی تفاوت زیادی ندارد. معمولاً احتمال اجرای حملات فر کانسی نسبت به روش مبتنی بر شاخص کمتر است. - در برخى روش ها كلمه اى كه جندين بر بکاررفت؛ هر بر به شکل جدیدی رمز می شو (بسته به جايكاه کلمه در متن) بيشتر اجراى برس و جو در سمت كاركزار است. تنها رمزتكارى كلمه مورد پرس و جو در سمت کارخواه انجام می شود. نسبت به روش های مبتنی بر شاخص دارای جواب اشتباه کمتری است. پیچید کی محاسباتی بالایی دارند و زمان جستجو در آن ها خطی است. بنابراین در مقیاس بز رگ قابل استفاده نیست. این روش ها بیشتر برای ابزارهایی با جستجوی در مقیاس کوچک (مانند تلفن همراه) مناسب است. پرس و جوهای با شرایط تطبیق دقیق را پاسخ می دهند. پرس وجوی شامل شرایط بازه ای و جستجوی الگوها بر روی داده های رشته ای در این روش سخت است. پرس و جو شامل توابع تجمعی امکان پذیر نیست. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 22:
جستجوی مبتنی بر شاخص اطلاعاتی با نام شاخص همراه با داده رمز شده در سمت کار گزار ذخیره می شود. جستجوی داده با استفاده از شاخص ذخیره شده انجام می گیرد. براي هر عنصر که بخواهد جستجو بر مبنای آن انجام شود. باید یک شاخص تعریف کرد. شاخص نباید اطلاعاتی در مورد داده اصلی را فاش نماید. روش های مختلف تولید شاخص باید از یک سو کارایی پرس و جو و از سوی دیگر عدم سوءاستفاده کار گزار از مقدار شاخص در استنتاج داده اصلی را در نظر بگیرند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 23:
جستجوی مبتنی بر شاخص ‎(Ay, Aj) Aig) *‏ ,92 پایگاه داده رمز نشده به , ۰ ۰ برآ ,,1 ‎R¥, (Counter, Etuple,‏ رآ در پایگاه داده رمز شده نگاشت می شود. ‎Counter‏ کلید اصلی جدول رمز شده. 1۳00016 رمز ‎ee ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎Name ‎Ann 1980 Production 10 Bob io75 | R&D 15 Bob 1985 | Financial 10 Carol | 1980 | Production 20 Ann 1980| Financial 12 David | 1975 | R&D 15 Employeec* Counter | Etuple 1: ] 1 | 5 | 34 | 1 1 15667 + ‏م8‎ x lal? ۸ 2 &(nfeuad!= 0 6 6 2 3 973907321۳7] ‏س | د | 8 | ف‎ | ١ 4 =1vs9e8925 2 ‏ماج ده‎ 5 0 * | »| ١ | ‏1م‎ 9 6 r43arg*5)) ‏ه‎ 1 8 1 1 01 = ‎ ‎ ‎ ‎ ‎ ‎ ‏دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 24:
روش های اصلی مبتنی بر شاخص ‎Bucket Based Index *‏ ‎Hash Based Index *‏ B+ Tree Index ° 41-41 ‏درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى‎ rr 

صفحه 25:
شاخص مبتنی بر ‎dy -Bucket‏ © هاسیگموس و همکارانش مبتنتی بر افزودن شاخص مبتنی بر باکت؛ روشی برای پرس و جو روی داده رمز شده ارائه دادند. * _ردیف‌های هر جدول به طور جداگانه و به کمک یکی از الگوریتم‌های رمزنگاری متقارن. رمز می‌شوند. *_به ازای هر مشخصه که جستجو روی آن انجام می‌شود. یک مشخصه به نام شاخص به جدول اضافه مى كردد. ‎D Title “Author Year‏ ‎[tandbook of Applied Crptographs| —_Alited L Menezes 2001‏ 123 7 3 7 3 ماود عمط 9 2 7 = 86 مقت ‎“inh‏ عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 26:
نحوه تعریف شاخص در روش ‎Bucket‏ 1 برای ایجاد شاخص امن, بازه‌ی داده‌های هر مشخصه به تعدادی زیربازه تقیم می‌شود. - بازه ها نباید اشتراک داشته باشند. ۲ ایجاد بازه‌ها می‌تواند با استفاده از انواع روش‌های تقسیم‌بندی صورت گیرد. - طول رابو - تعداد اعضای برابر ۳ به ه رکدام از بازه‌ها مقداری تعلق می‌گیرد. - می توان از یک تابع تولید اعداد شبه تصادفی استفاده کرد. ب به ازای تمام داده‌هایی که در یک زیربازه قرار می‌گيرند. مقدار تعلق گرفته به زیربازه‌ی آنها در شاخص رمزشده قرار داده می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 27:
مثال - بازه بندی و اعطای شاخص id [name [ salary 3 7 a om ۳0 01010101171125 10 eae 000101101... 12 5 10 ao ‏ست د‎ 010111010... | 8_| 28 Las 110111101...|2 [7 1 emma ia Table 1.2: Encrypted salary table. ۳ 4 8 9 3 2 eo 200 400 600 300 1600 6 7 5 28 11 ‏نك ر تب .لپ تن«‎ A P K P U Z 1 6 2 10 3 salary +1 __® | 2 4, 0 ,_38 درس امنیت پایگاه داده ها - نیمسال دوم تحصیلی ۸۸-۸۷ 

صفحه 28:
پرس وجو در شاخص دهی مبتنی بر ۳001661 * برس وجو در دو مرحله صورت مى كيرد: ‎١‏ کارگزار سعی می کند تا آنجا که امکان دارد پاسخ درستی برگرداند ۲ کارخواه نتیجه‌ی ارسالی کارگزار را رمزکثایی کرده و آنرا بردازش مى كند. * در ,]500 یک پرس و جو می تواند با درخت‌های متفاوت که از نظر نتیجه یکسان هستند. نمایش داده شود. * هاسیگموس جداسازی پرس و جو را (بخشی در سمت کار گزار و بخشی در سمت کارخواه) را با استفاده از درخت پوس وجو انجام داده استد عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 29:
پرس و جو در شاخص دهی مبتنی بر ‎Bucket‏ ‏)2( در روش هاسیگموس, درخت نمايش هر پرس‌وجو به دو قسمت. تقسیم می‌شود. بخش زیر عملگر رم زگشایی: کلیه اعمالی که می تواند در سمت کارگزار انجام شود. ۲ بخش بالای عملگر رم زگشایی: اعمالی که باید در سمت کارخواه انجام شوند. آعمال جبر رابطه‌ای وقتی به زیر عمل رم زگشایی برده می‌شوند باید به آعمال جدیدی که روی داده‌های رمزشده قابل اجرا هستند. تبدیل شوند. هاسیگموس جبر رابطه‌ای جدیدی را برای اعمال روی داده‌های رمزشده تعریف کرد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 30:
بهینه سازی اجرای پرس و جو SELECT name FROM books, keeper WHERE keeper.ID = books.keeping AND Title = applied cryptography" fandbook of * فقط عملگرهایی که در زیر عملگر رم زگشایی هستند قابل اجرا در سمت كار كزار هستند * در اين اجرا هیچ عملگری قابل اجرا به روی > ۳ Oovks. keeper = (Keeper.id seed AEM * سربار ارتباطی و محاسباتی در سمت کارخواه بالا \ ‎J‏ ‏است. * براى افزايش كارآبى بايد سعى كرد تا حد امکان. ۱ عملكرهاى رابطهاى را به زير عملكر رمز كشابى منتقل Oo ‏جروج‎ as Cocks” دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 31:
اجرای بهینه پرس و جو TT. آعمال تا حد امکان باید در سمت کارگزار انجام شود. - ۳ رابطه 5151:5130 روى جدول 800166 به هی وي زير عملكر رمزكشابى برده شده است. لوصا براى بردن اين عملكر به زير عملكر رمزكشابى بايد آنرا تبدیل به 6" که در جبر جدید هاسیگموس برای < 5510۷ روی جداول رمزشده و ‎Keeper’ it‏ < تسا( مشخصه‌های شاخص تعریف شده است. تبدیل کرد. اين اجرا از برس وجو به دلیل اجرای برخی از \ ‎Lo‏ ها در سمت کارگزار اجرای کارایی است. 3 ‎ne‏ كاز اجراي راد 00 تسیا \ a) امم عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 32:
مزایا و معایب روش باکت بندی برای تولید شاخص * روش های مبتنی بر 131201601 برای اجرای شروط تساوی مناسب هستند. - ۵ - ز1 و ۷ - زنه پرس و جوهای بازه ای نیز با کمی تغییر در این روش شاخص دهی قابل اجرا است. ‎A,> v->(1, = B, or B, or ...or -‏ * مثال: - شرط 5213107<50000 در جدول صفحات قبل باید به شکل زیر تبدیل شود: ‎Salary*=2 OR Salary*=10 OR Salary*=3‏ ‎SUM. MIN. MAX. Avg wile crood ela est el oll pus *‏ - - هاسیگموس این روش را تعمیم داد و با استفاده از یک تابع همریخت اختفانی اجرای توابعی مثل جمع و ضرب را فراهم کرد. لان اذك ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 33:
مزایا و معایب روش باکت بندی برای تولید شاخص (۲) * _ وجود مقدار زیادی از داده های اضافی در نتایج کار گزار (به ویژه اگر اعمالی مانند پیوند در پرس و جو وجود داشته باشد) - روش‌هایی برای بهبود و کاهش اشتباه‌های مثبت در روش هاسیگموس ارائه شده است. * اين روش بيشتر برای داده‌های عددی کاربرد دارد و به کار گیری روش برای داده‌های رشته‌ای یا متتی که دامنه‌ی داده‌ها بزرک است. چندان مناسب نیست. - در تعریف بازه برای داده‌های رشته‌ای, ممکن است تعداد زیادی داده در یک بازه قرار گیرد که این خود به معنای ارسال تعداد زیادی داده‌ی اضافی در پاسخ به یک پرس‌وجو و در نتیجه سربار ارتباطی و محاسباتی بالا است. *_اگر بازه ها طوری ساخته شوند که مثلاً در هر بازه یک مقدار قرار بگیرد امکان تحلیل فر کانسی وجود دارد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 34:
شاخص مبتنی بر توابع درهم ساز از مفهوم توابع درهم ساز برای ساختن شاخص استفاده می شود. برای ساخت شاخص در این روش- داده‌ها توسط یک تابع درهم‌ساز دارای تصادم دسته‌بندی می‌شوند. مزیت این نوع شاخص دهی نسبت به روش باکت بندی این است. که دسته‌بندی روی داده‌های پشت سرهم انجام نمی‌شود که این می‌تواند باعث افزایش امنیت گردد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 35:
شاخص مبتنی بر توابع درهم ساز (۲) + اکر تدرابطه ای‌با اسکیمای (,ب , ۰ ۰ ۰ رون ‎(Ay,‏ ترابطه متناظر رمز شده آن باشد, برای هر صفت ‎Ay‏ در ,18 که بخواهیم برای آن شاخص تعریف کنیم. تلبع درهم ساز تعریف می شود که ور دامنه رب و 88 دامنه شاخص 1 متناظر با زب است. ‎for all x, y in Dy; if x = y then h@)= h(y)‏ + * برد «از دامنه آن کوچکتر است . - امکان برخورد وجود دارد. ۰ برای هر دو مقدار تصادفی متفاوت ولی نزد (ع۰ توزیع احتمالی (00 - (20 یکنواخت است. به هم ۲ و ودر دامته >| ۷ — ‎D, (1x‏ - تابع درهم ساز ترتیب خصیصه در دامنه را حفظ نمی کند. ‎ai‏ ل درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 

صفحه 36:
شاخص مبتنی بر توابع درهم ساز - ویژگی ها * اجرای پرس و جوهای تساوی (مانند روش های شاخص دهی مبتنی بر 001661) ممکن است. - هر شرط فا به شرط (7)[-1 که و1 شاخص متناظر با ژفظ در جدول رمز شده است: تبدیل می شود. برخورد در توابع درهم ساز باعث ارسال چندتایی های اضافی به سمت کار خواه می شود. تابع درهم ساز فاقد برخورد مشکل ارسال نتایج زیادی به کارخواه را رفع می کند ولی احتمال تحليل هاى فر كانسى را افزايش مى دهد. مشکل اصلی روش های شاخص دهی مبتنی بر تولبع درهم ساز عدم پشتیبانی از پرس و جوهای بازه ای است. - دامیانی و همکارانش برای اضافه کردن قابلیت انجام جستجوی بازه‌ای به این روش از شاخص مبتنی بر درخت 18+ در كنار اين نوع شاخص دهى استفاده کردند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 37:
شاخص مبتنی بر درخت 18+ یکی از روش های شاخص دهی استفاده از ساختار داده ای درخت 13+ است. در درخت 13+ کره های داخلی به طور مستقیم به چندتایی ها در پایگاه داده اشاره نمی کنند بلكه به سایرگره ها در ساختار اشاره می نمایند. ره های برک متقیماًبه چندتایی هایی در پایگاه داده با مقادیر مشخص برای صفت شاخص اشاره می کنند. درخت 33+ می تواند برای هر صفت رب در اسکیمای ,18 که در شروط پرس و جو ظاهر می شود, تعریف شود. شاخص توسط کارخواه روی مقادیر رمز نشده صفت ساخته شده و سپس روی کارگزار همراه با پایگاه داده رمز شده ذخیره می کردد. ساختار درخت 13+به جدهلی با دو صفت شناسه کره و محتوای ره تبدیل می شود. این جدول برای هر گره یک ردیف دارد. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 38:
Gq ay الل ‎Id | VertexContent. 101 |‏ ‎Carol, 3 1 gtem945/*e‏ ,2 1 سوه | 2 5 ‎Bob,‏ ,4 | 2 ‎David, 7 3. | ue63/)iw‏ ,6 | 3 ‎Ann, 5,1, 5 a_| 8/*5sym,p‏ | 4 ‎Bob, 6, 2.3 5 mw 39wiol‏ 5 ‎Garol, 7,4 6 | =weo2I'ps‏ |_6 ‎David, NIL, 6 7 oieb5S (ps*‏ 7 Carol Bob David Ann |- Bob { ‏ای‎ {Davia | درس امنیت پایگاه داده ها- نیمسال دوم تعصیلی ۸۸-۸۷ 

صفحه 39:
روش ارزیابی پرس و جو در درخت 18+ فرض کنید. کارخواه اجرای پرس‌وجویی با شرط ۲ < ۸ را درخواست کرده که ۲ یک مقدار ثابت است. کارخواه باید درخت 8 ذخیره شده روی کارگزار را برای یافتن محل ۷ پیمایش کند. - کارخواه درخواستی برای دریافت ریشه‌ی درخت ظ انجام می‌دهد.(ریشه‌ی درخت. ردیف با شماره‌ی ۱ است.) این ردیف به کارخواه ارسال و در آنجا رم زگشایی و پردازش می‌شود. - با توجه به مقدار ۷ گره‌ی بعدی که باید پیمایش شود انتخاب شده و درخواستی مبنی بر ارسال آن گره به کارگزار فرستاده می‌شود. این روند تا پیدا کردن برگ حاوی 7 ادامه يبدا مى کند. بس از پیدا شدن 7 تمام برگ‌های بعد از آن به سمت کارخواه ارسال می‌شوند. اين گره‌ها در سمت کارخواه رمزگشایی شده و شماره‌ی ر کوردهای مورد نظر پیدا شده به سمت کارگزار ارسال می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 40:
شاخص مبتنی بر درخت 3+ ویژگی ها ۶ درخت 18+ در پاسخ به پرس و جو چندتایی اضافی به سمت. کارخواه نمی فرستد. هزینه ارزیابی شرایط پرس و جو برای کارخواه نسست به روش های مبتنی بر باکت و توابع درهم ساز بسیار بیشتر است. - به همين دليل معمولاً درخت 33+ را در کنار یکی از روش های شاخص دهی مبتنی بر باکت یا توابع در هم ساز بكار برده و از درخت 15+ تنها در هنكام ارزيابى بازه ها در برس و جو ها استفاده مى نمايند. * با توجه به اين كه محتواى درخت 19+ در سمته کا رگزار رمزنگاری شده استه اين روش در برابر حملات استنتاجى نيز مقاوم اسهد عرس لمنيت بأيكاة ماده :طا- نينا موم تحصيلن 044:41 

صفحه 41:
جستجوی مبتنی بر شاخص در داده های رشته ای روشی مبتنی بر شاخص برای پرس و جو روی داده های رشته ای توسط ۲۱۷۵ ارائه شده است (۲۰۰۶). * با استفاده از روش وانگ. می‌توان به جستجوی الگوهای دلخواه در داده‌هایي رمزشده پرداخت. * ریزدانگی رمزنگاری در روش ۰۷۷۵10 در سطح فیلد است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 42:
مراحل رمزنگاری به هر رشته 5 که از م کاراکتر ,© طول «: بيت اختصاص داده می‌شود. (©>,ر© تشکیل شده است. مقدار شاخصی به هر رشتهى م6©... 6 © > 5 به رشته‌ی و رر5...رکرک <51 که در آن وبرنار6 استه بسط داده می‌شود. با استفاده از تابع درهم‌ساز ظ مقداری بین ۰ تال برای هر کدام از ,5 ها به دسلته مى آيد. 1 اگر مقدار (5) 12 برابر با ۶ باشد. در آن صورت بيت شماره #ام در شاخص مربوطه برابر با یک می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 43:
مثال * §1= (abcehklst) ۰ 60 ‏؟ء تابعی در هم ساز دوتایی های ۵۳0.06 .... و 51 را به عددی بین ۰ تا ۱۵ نگاشت.‎ ‏می کند.‎ S2=Index(abcehklst)= (0010100010101001), ۰ * هشت رشته ۲ تایی وجود دارد در حالیکه 1 بیت یک در 52 دیده می شود. یعنی برخی از کارا کترهای دوتایی به یک مقدار توسط « نگاشت می شوند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 44:
روش جستجو ‎0.١‏ مقدار رشته‌ای موجود در الگوی رشته ای مورد پرس و جو بسط داده می‌شود و مقادیر اختصاص داده شده توسط تابع ۶ به هر دو حرف متوالی آن به دست می‌آید. - . پرس و جو روی مقدار رشته ای به پرس و جو روی شاخص (رشته بیتی) تبدیل می شود. ۲ مقادیر به دست آمده مکان بیت‌هایی از مقادیر شاخص را كه بايد ۱ باشند تا شرط پرس وجو ارضاء شود, مشخص می کند. این مقادیر به سمت کار گزار ارسال می‌شوند. ۳ کارگزار به ازای هر مقدار شاخص, مقادیر بیت‌های آن در مکان‌های ارسال شده را بررسی می کند. اگر همه دارای مقدار ۱ بودند؛ مقدار شاخص را به عنوان یکی از جواب‌ها به سمت کارخواه برمی گرداند. ‎ -‏ در جواب های ارسال شده ممکن است نتایج اضافی وجود داشته باشد که باید توسط ‏کارخواه مجدداً پردازش شده تا جواب دقیق به دست آید. ‎ ‎ ‏عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 45:
حالت های مختلف پرس و جوی رشته ای ‎١‏ تطبیق دقیق ‎gs) attribute=value b,5‏ جدول رمز نثده تبديل مى 995 4 ~ ‎a* index (value) a*‏ مقدار رمز شده 2131190016 در سمت کارگزار است. 5 تطبیق الگویی شرط ‎Jgve so attribute LIKE value‏ )30 نشده: تشه ‎alike cOc1...ck => (€@)qo=1 AND (@)ine1)=1 AND ... AND‏ ‎reay=1)‏ ‏پرس و جوی با شرایط بولی ‎(attribute=value 1) OR (attribute=value 2), (attribute like value 1) AND (attribute like value 2), (attribute like value 1) AND NOT (attribute like value 2) ‏- از حالت اول و دوم قابل استنتاج است. ‏۱ ‏۴ درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى 41-41 ‎1 ‎5 ‎ 

صفحه 46:
مثال eid aia awe [ Sex. 021021 | Chessbasketball | 24 M 021094 | basketballcook 50 | F 021005 | Languageschat 26 | 35 021096 | programnotwork | M 1 13 ‏رد‎ aid 021021 | 100101011001001001011... ] 21121913 1 021094 | 100111100110000110101-.. |] 0 218801 0210 0 1 26 M 211929060 021006 ۱ 1100 21 1 21192011160 select eid, age from employee where did like ‘chess select * from employee" where ) ad (ig =D) ad ‏هه‎ دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 47:
تحلیل روش * در این روش, در صورتی که طول 102 بزرک انتخاب شود. حمله متن اصلی معلوم محتمل است. - هر زوج کارا کترجه مقدار یکتلیی در شاخص منتسب می شهند و امکان تحلیل فر کانسی و شکستن شاخص وجود دارد. * در صورت کوچک بودن سس تعداد زیادی داده اشتباه به سمت کارخواه ارسال خواهد شد. * در جدول رمز شده فیلد اضافه ای برای شاخص بلید در نظر گرفته شود که حجم ‎OT‏ ‏به اندازه شاخص ( «) وابسته است. - در صورتی که « فیلد نیاز به رمز شدن داشته و طول شاخص به طور متوسط «« بیت ‎ASL‏ میزان فضای اضافی مورد نیاز 100*90 بیت برای شاخص است. لان اذك 41-41 ‏درس امنيت بأيكاه داده ها- نيمسال دوم تحصيلى‎ ry oi 

صفحه 48:
جمع بندی روش ها ی مبتنی بر شاخص زیادی روی این گونه روش ها صورت گرفته و دارای زمینه تنوریک قوی می باشند. حتی دارای جبر رابطه ای مخصوص می باشند. بیشتر فرایند اجرای پرس و جو بر روی کار گزار متم رکز است. * _ هزینه ذخیره سازی تقریباً دو برابر ذخیره سازی معمولی است. زیرا غیر از مقدار رمز شده ذخیره: مقدار ز ذخیره می کردد. ‎ *‏ امکان استتتاج و افشای اطلاعات وجود دارد که میزان آن وابسته بهتعریف شاخص است. - ۰ 12۷0016000۷ و همعارانشثانکرده‌اند کسه تسقریاً تسم روش‌هایمبتن‌سر شاخموو لمسیستند بسه ود روشهاییکه در پساسخ بسه پسرس‌وجو چندتابیهعاضافیتسولید نمی‌کسندد در معرض‌تسهد بدلفثای لمطلاعاتقرار دايند * برس و جوهاى شامل بيوند در اين روش قابل اعمال است. * برس و جوهاى تساوى. و الكوبى براى داده هاى عددى و رشته اى قابل انجام است. * امكان اجراى برس و جوهاى بازه اى بسته به تعريف شاخص دارد. * امكان اجراى برس و جوهاى شامل توابع تجمعى وجود ندارد. * چون‌با تغیبر توزیع داده ها نیز به دسته بندی مجدد داده ها برای تعریف شاخص وجود دارد. این روش بشتر برای داده های فقط خواندنی مناسب است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 49:
روش های مبتنی بر کاربرد توابع همریخت اختفایی * _توابع همریخت اختفایی نوعی توابع برای رمزنگاری است. * در روش رمزنگاری همریخت اختفایی (عنطم :هط ۳۳۷۵0۲)؛ حاصل انجام یک ‎foc‏ روی داده‌های رمزشده؛ معادل رمزشده حاصل عملی دیگر روی داده‌های اصلی است. ۴((رییه) ع ( رمع ‎٠‏ - E() . E(y) = E(xty) *_بوسیله‌ی توابع رمزنگاری همریخت اختفائی می‌توان برخی از عملیات مانند جمع و ضرب را به طور مستقیم روی داده‌های رمزشده انجام داد. * فیلدهایی را که روی آنها پرس و جوی تجمعی اجرا می شود. با استفاده از رمزنگاری همریخت رمز می کنند. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 50:
روش هاسیگکموس * هاسیگموس با استفاده از یک تابع رمزنگاری همریخت اختفانی که دو خاصیت جمعی و ضربی را پثتیبانی می کند, توابع جمع و ضرب را روی داده‌های رمزشده اجرا کرد. ۶ خواص تابع رمزنگاری همومورفیسم استفاده شده: - کلید رمزنگاری (6 ,)12 که « و و به وسیله کاربر تعیین مى شوند. که به کارگزار دادم میشود ۲.6 ‎(mod p)‏ 21 دوو - ‎pp? = 1 (mod q)‏ - Dy(er.c2) = (cy mod p)qg7! + (co mod q)pp~! (mod n) دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 51:
مثال p=5,q=7 n=p.q=35 k=(5, 7) * مى خواهیم 8 < ره و 12 < ره را جمع کنیم ‎Efa,) = )3,1(‏ ‎Efa,) = (2,5)‏ ‎E (al) + E (a2) = (3+2, 1+5) = (5, 6)‏ ‎D (5, 6) = «qq? + &pp (mod 35)‏ = (5*7*3 + 6*5*3) (mod 35) =195 (mod 35) = 20 دون آعفیت پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 52:
مشکل استنتاج * _استفاده از تابع رمزنگاری همریخت اختفائی معرفی شده کاملاً امن نیست و کار گزار می‌تواند مقدار اصلی برخی از مقادیر رمزشده را به دست آورد. - فرض كنيد, » و و دو عدد باشند که به صورت ‎Wy Vy) 9 (Kp Xs)‏ 509 شده‌اند. اگر تست باشد. رابطه‌ی تکرام نیز بین مقادیر رمزشده این متفیرها وجود دارد. در چنین حالتی کاوگزار می‌تواند مقادیر اصلی این متتبرها را به دست آورد. کارگزار شروع به جمع ‎Ky OOS‏ ركة) با خودش مى كند و اين كار را آنقدر ادامه می‌دهد تا نتيجه آن با 2 رت) برابر شود. تعداد این جمع کردن‌ها باب با عدد ار است. (پشدیه) + (مشیت) < (معیع) * هاسيكموس با اضافه كردن نويز تصادفى به وتو دزی پر و ونم ‎Rep.‏ یک تابع شبه تصادفی است. * نويز در هنگام رم زکشایی از داده‌ها حذف می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 53:
روش های رمزنگاری مبتنی بر حفظ ترتیب * در روش های رمزنگاری با حفظ 5 ‎cots (Order Preserving) U4‏ هابه كونه اى رمز می شوند که ترتیب داده ها پس از رمز شدن با ترتیب داده های اصلی یکسان باشد. * این نوع رمزنگاری برای اجرای پرس و جو های بازه ای مناسب است. * آگراوال برای رمزنگاری داده های عددی و اجرای پرس و جوهای بازه ای روی آنها از این روش استفاده کرده است. *_ فرض کنید. داده‌های اصلی دارای توزیع اولیه ۸ هستند. این داده‌ها به نحوی رمز می‌شوند. که علاوه بر حفظ ترتیب از توزیع دلخواه ۸4 تبعیت کنند. - ابتدا داده‌ها به توزیع یکنواخت ۶ نگاشت شده و سپس توزیع / به توزیع هدف ۸4 نگاشت می‌شود. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 54:
مراحل رمزنگاری ۰ 028:5 در سه مرحله كار ميكد (0تأتكدعوع22 02061 ‎(Encryption Scheme‏ ‎Jue)‏ کردن: داده‌های اصلی به تعدادی دسته تقیم می‌شوند و توزیع داده‌های هر دسته مدل می‌شود. ‏روش هایی برای تعیین تعداد دسته ها و طول هر دسته وجود دارد. ‎ ‎ ‏02 افزایش دسته‌ها منجر به افزایش هزینه‌های مدل می‌شود. ۲ سطح کردن: داده‌های اصلی ۶ به داده‌های مسطح "1 به قسمی تبدیل شود که مقادیر 2 دارای توزیع یکنواخت باشند. * .در مرحل‌ی سطح کردن برای هر دسته. یک تابع تگاشت 17 ایجاد می‌شود. تابع ۸ هر دسته را به دسته‌ای با توزیع یکنواخت نگاشت می کند. ‏دو مقدار متفاوت در داده های اصلی هميشه به دو مقدار متفاوت از فضای مسطح شده تگاشت شوند. ‎ ‏اده‌های سطح "۸ به داده‌های رمزشده 6 تبدیل می‌شود, به قسمی که مقادیر 6 دارای توزیع نهایی که برای داده‌های رمزشده در نظر گرفته شده بود. باشند. ‎ ‏عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 55:
درس امنیت پایگاه داده ها- نیمسال دوم تعصیلی ۸۸-۸۷ 

صفحه 56:
ویژگی های روش رمزنگاری با حفظ ترتیب * اجرای پرس و جوها در اين روش چندتایی های اضافی جه سمت کارخواه ارسال نمی کند. * امنیت در این روش زملنی تامین می شود که کار گزار احمله کننده اطلاعاتی در مورد پایگاه داده اصلی و يا دامنه صفت ها نداشته باشد. - این روش در مقابل حمله متن اصلی معلوم آسیب پذیر است. عرس ‎cast‏ پأیگاه داده ها - نیسنان دوم تسین ۸۸-۸۷ 

صفحه 57:
پایگاه داده ها - تیمسال دوم تحصیلی ۸۸-۸۷ 

‏MCI پرس و جو روی داده های رمز شده علی هادوی خرداد 88 درس امنیت پایگاه داده مقدمه • روش‌هاي کنترل دسترسي برای محافظت از داده ها کافي نيستند – سرقت رسانه محتوی داده – عدم اعتماد به اعمال کننده خط مشی های کنترل دسترسی – امکان دور زدن مکانیزم های کنترل دسترسی توسط مهاجمین • مطرح شدن ایده Database as A Serviceو سیستم های کارگزار غیرقابل اعتماد درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مدل پایگاه داه به عنوان خدمت • پایگاه داده به عنوان خدمت ( )Database as A Serviceبه عنوان رویکردی جدید در برون‌سپاری پایگاه‌ داده‌ها • در دسترس بودن داده ها توسط کارگزار تضمین می شود. • کلیه اعمال مدیریت داده را کارگزار فراهم می کند. • کارگزار از نظر نگهداري داده‌ها و عدم ارسال عمدي پاسخ اشتباه مورد اعتماد است. • کارگزار در مورد محرمانگي داده‌ها مورد اعتماد نيست. – کارگزار درستکار ولی کنجکاو است (.)Honest but curious درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مدل پایگاه داده به عنوان خدمت • چالش اصلی در این مدل تأمین امنیت داده‌های برون‌سپاری شده است. • راه حل اولیه رمزنگاری داده های برون‌سپاری شده است. • برای حفظ محرمانگی مالک داده ،داده خود را رمز کرده و آن را در پایگاه داده رمز شده در سمت کارگزار ذخیره می کند. • ریزدانگی رمزنگاری به خط مشی های محیط برای سطح دسترسی ،امنیت و کارایی بستگی دارد. – بیشتر فعالیت ها ریزدانگی را در سطح چندتایی تعریف کرده اند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI عناصر مدل DAS .1 مالک داده‌ها :فرد يا سازمان است که داده‌ها را ايجاد و آن را برون‌سپاري مي‌کند. .2 کاربر :پرس‌وجو‌ها را به سيستم ارائه مي‌کند. .3 کارخواه :پرس‌وجوهاي کاربر را به پرس‌وجوهاي قابل اجرا روي داده‌هاي رمزشده تبديل مي‌کند. .4 کارگزار :محل ذخيره‌ي داده‌هاي رمز شده است و پرس‌وجوهاي ارسالي از سمت کارخواه را روي داده‌هاي رمزشده اجرا کرده و نتيجه را به کارخواه ارائه مي‌دهد. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI سناریوی پرس و جو در مدل DAS .1 کاربر پرس و جوی Qرا با توجه به اسکیمای پایگاه داده ی رمز نشده Bاز طریق کارخواه وارد می کند. – برون سپاری داده می تواند از دید کاربر شفاف باشد. .2 کارخواه پرس و جوی کاربر را به دو بخش Qsو Qcتقسیم می کندQs .پرس و جوی اعمال شده بر روی داده های رمز شده در سمت کارگزار و Qcپرس و جوی اعمال شده در سمت کارفرما بر روی داده های برگشتی از کارگزار به کارخواه است. • کارگزار پرس و جوی Qsرا روی داده رمز شده اجرا و نتایج (مجموعه ای از چندتایی های رمز شده) را به کارخواه بر میگرداند. • کارخواه نتایج را رمزگشایی کرده و چندتایی های اضافی را با اعمال Qcبه نتایج اولیه حذف می کند .نتایج نهایی به کاربر ارائه می شود. .1کارخواه ساختار پایگاه داده عادی و رمز شده را می داند درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI سناریوی پرس و جو در مدل DAS ‏MCI )1 )4 ‏DBK )2 ` )3 ‏DBK درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 مالحظات رمزنگاری در برون سپاری داده درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مالحظات رمزنگاری در برون سپاری داده ()2 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مالحظات رمزنگاری در برون سپاری داده ()3 • پشتیبانی از انواع پرس و جو – پرس و جو روی داده های عددی • پرس و جو با شرط تساوی • پرس و جوی بازه ای – پرس و جو روی داده های رشته ای • پرس و جو با شرط تساوی • پرس و جو های تطبیق الگویی – پرس و جوهای شامل توابع تجمعی درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش های جستجو روی داده های رمز شده • جستجوی مستقیم روی داده های رمز شده • جستجوی مبتنی بر شاخص • روش های مبتنی بر حفظ ترتیب • روش های مبتنی بر توابع همریخت اختفایی درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جستجوی مستقیم روی داده های رمز شده • داده به گونه ای رمز می شود که جستجو بتواند دقیقًا روی همان داده رمز شده به صورت مستقیم صورت گیرد. • سانگ روشی را بر اساس این ایده برای جستجو روی داده های رشته ای ارائه داده است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش - Songمعرفی • جستجوی کلمات روی اسناد رمز شده (تمرکز بر DBنیست) • کاربرد مفهوم دریچه • کارگزار می‌تواند با گرفتن اطالعات کوچکي در مورد هر کلمه (دريچه) ،جستجو را بدون اطالع از کلمات ديگر متن انجام دهد. • توابع مبتنی بر دریچه توابعی هستند که محاسبه‌ي معکوس آنها بدون داشتن اطالعات خاصی به نام دریچه مشکل است. • در رمزنگاري مبتني بر دريچه ،رمزگشايي با داشتن دريچه امکان‌پذير است. • در اين روش‌ها ،به همراه هر کلمه‌اي که کارخواه جستجوي آنرا تقاضا کرده است ،دريچه‌ي آن نيز ارسال مي‌شود .بدين شکل کارگزار فقط مي‌تواند کلمه درخواست شده را رمزگشايي کند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش - Songرمزگذاری .1 متن اصلی به تعدادی کلمه wبا طول یکسان ( nبیت) تقسیم می شود. .2 اسناد اصلی پس از رمزشدن به روش شرح داده شده ،به سمت کارگزار ارسال و در آنجا ذخیره می‌شوند. .3 کارگزار با دريافت دريچه‌اي از طرف کارخواه می تواند کلمه‌ی مورد نظر کاربر را جستجو کند. • پارامترهای رمزنگاری : S .1مولد اعداد شبه تصادفی F .2و : fتوابع شبه تصادفی :’K .3کلید تابع ( fبرای تمام کلمات متن ثابت است) .4دریچه هر کلمه :کلید تابع ))F : f k’(first n-m bits of Ek’’(wi درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش – Songرمزگذاری()2 • رمزگذاری در دو سطح انجام می شود. – سطح اول: • هر کلمه با یکی از الگوریتم‌های رمزنگاري متقارن و کلید ( )"kرمز می شود. • کارگزار در هنگام اجراي پرس‌وجو از کلمه‌ي درخواست شده کارخواه مطلع نمی شود. – سطح دوم: • مولد شب ‌ه تصادفي ، Sدنباله‌اي از اعداد شبه تصادفي siبا طول n-mبیت به تعداد کلمات متن اصلي ايجاد مي‌کند. • اعداد شبه تصادفی تولید شده siبا استفاده از تابع Fدرهم‌سازي شده و خروجی mبیتی تولید می شود. • (رمزشده‌ي الیه‌ي اول هر کلمه ( ) ))Ek"(wiبا ( siو حاصل درهم‌سازی شده‌ در مرحله قبل) XOR ،می‌شود. • نتیجه‌ی الیه‌ي دوم رمزنگارِی کلمه‌ي wiبه عنوان iامین کلمه‌ي متن رمزشده ( )ciدر سند رمزشده قرار می‌گیرد. 15 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش -Songرمزگذاری()3 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش - Songاعمال پرس و جو .1 کارخواه برای جستجوی یک کلمه ( )wدر اسناد رمزشده ،معادل رمز شده‌ي الیه‌ي اول کلمه ( ) )Ek"(wبه همراه دریچه‌ي آن ( ) )fk'(wرا به کارگزار ارسال می‌کند. .2 کارگزار با دریافت ( ) )Ek"(wکلمات تمام اسناد را با آن XORمی‌کند. .3 اگر کلمه‌ي Pام سندی با کلمه‌ي درخواست شده برابر باشد ،حاصل ) XOR (Tpباید ساختاری به شکل <) >Sp, Ff (k’(w)) (spداشته باشد .برای بررسی وجود ساختار فوق برای کلمه‌ي pام متن رمزشده ،حاصل تابع Fروی n-mبیت پرارزش Tpبه دست آورده می‌شود. .4 اگر مقدار به دست آمده با mبیت باقی‌مانده‌ي Tpبرابر باشد ،ساختار برقرار بوده و کلمه‌ي Pام متن رمزشده به همراه سندی که به آن متعلق است در مجموعه‌ي جواب ارسالی به کارخواه قرار می‌گیرد. .5 تابع Fیک تابع درهم‌ساز دارای برخورد است .بنابراین امکان وجود اشتباه مثبت در نتایج ارسالی به کارخواه وجود دارد. .1در سمت کارخواه پس از رمزگشایی سند ،مقدار اصلی کلمه‌ي پیدا شده با کلمه‌ي درخواست شده‌ي کاربر مقایسه می‌شود تا نتایج درستی به کاربر برگردانده شود. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش - Songرمزگشایی • برای رمزگشایی کلمه‌ي ُiام سند رمزشده ( ،)ciابتدا n-mبیت پرارزش ciباsi ، XOR می‌شود و n-mبیت پر ارزش ) Ek"(wiبه دست می آید. • از مقدار فوق برای ساختن دریچه‌ي wiاستفاده می‌شود. • اعمال دریچه بدست آمده و n-mبیت پر ارزش siبه تابع F ، mبیت نتیجه دارد که با XORکردن با mبیت کم ارزش ci ، mبیت کم ارزش ) Ek"(wiحاصل می شود. بدین ترتیب تمام بیت‌های ) Ek"(wiبه دست می‌آیند. • ) Ek"(wiرمزگشایی شده تا مقدار اصلی wiحاصل شود. 18 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI ویژگی های روش Song • کارگزار نمی تواند در مورد متن اصلی تنها با استفاده از متن رمز شده اطالعاتی بدست آورد. • سربار ذخیره سازی و ارتباطاتی آن کم است. • نتیجه حاوی مکان هایی از سند است که Wدر آن ظvاهر شvده اسvت و ممکن اسvت دارای اشتباهات مثبت باشد. • اشتباهات مثبت با مقدار mمرتبط است .هر جواب اشvvvتباه با احتمال 1/2mرخ می دهvvvد. بنابراین برای سندی با طول lکلمه انتظار l/2mجواب اشتباه وجود دارد. • متن باید تقسیم به کلماتی با طول مساوی شود که با توجvvvvه بvvvvه ساختار زبان ،روش مناسبی نیست. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI ویژگی های روش )Song (2 • امکان جستجو با هر طول دلخواه وجود ندارد .فقط مي‌توان کلمات با طول nيا ضريبي از nبیت را جستجو کرد. • گروه محدودي از الگو‌ها قابل جستجو است. – الگوهايي به شکل"] "ab[a-zبا تبديل به aba, abb, abc, …, abzقابل جستجو هستند؛ – جستجوي الگوهايي به شکل " ”*abمشکل است .زيرا تعداد رشته‌هاي توليدي بسیار زياد خواهند شد. • در الگوريتم سانگ ،براي يافتن هر کلمه بايد کل محتويات تمام اسناد جستجو شود .زمان جستجو نسبت به طول متن خطی است .بنابراین در قابل مقیاس بزرگ (مانند پایگاه داده) کارا نیست. – یک روش افزایش سرعت بکارگیری شاخص های از پیش تعریف شده است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جمع بندی -جستجوی مستقیم روی داده رمز شده • فضای ذخیره سازی نسبت به ذخیره سازی داده اصلی تفاوت زیادی ندارد. • معموًال احتمال اجرای حمالت فرکانسی نسبت به روش مبتنی بر شاخص کمتر است. – در برخی روش ها کلمه ای که چندین بار بکار رفته ،هر بار به شکل جدیدی رمز می شود (بسته به جایگاه کلمه در متن) • بیشتر اجرای پرس و جو در سمت کارگزار است .تنها رمزنگاری کلمه مورد پرس و جو در سمت کارخواه انجام می شود. • نسبت به روش های مبتنی بر شاخص دارای جواب اشتباه کمتری است. • پیچیدگی محاسباتی باالیی دارند و زمان جستجو در آن ها خطی است .بنابراین در مقیاس بزرگ قابل استفاده نیست. • این روش ها بیشتر برای ابزارهایی با جستجوی در مقیاس کوچک (مانند تلفن همراه) مناسب است. • پرس و جوهای با شرایط تطبیق دقیق را پاسخ می دهند. • پرس وجوی شامل شرایط بازه ای و جستجوی الگوها بر روی داده های رشته ای در این روش سخت است. • پرس و جو شامل توابع تجمعی امکان پذیر نیست. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جستجوی مبتنی بر شاخص • اطالعاتی با نام شاخص همراه با داده رمز شده در سمت کارگزار ذخیره می شود. • جستجوی داده با استفاده از شاخص ذخیره شده انجام می گیرد. • برای هر عنصر که بخواهد جستجو بر مبنای آن انجام شود ،باید یک شاخص تعریف کرد. • شاخص نباید اطالعاتی در مورد داده اصلی را فاش نماید. • روش های مختلف تولید شاخص باید از یک سو کارایی پرس و جو و از سوی دیگر عدم سوءاستفاده کارگزار از مقدار شاخص در استنتاج داده اصلی را در نظر بگیرند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جستجوی مبتنی بر شاخص • ( Ri )Ai1, Ai2, …, Ainدر پایگاه داده رمز نشده به Rki (Counter, Etuple, I1, I2, . . ., ) Inدر پایگاه داده رمز شده نگاشت می شود Counter .کلید اصلی جدول رمز شده Etuple ،رمز شده چندتایی معادل در پایگاه داده رمزنشده I1 ،تا Inشاخص های متناظر با Ai1تا Ainهستند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش های اصلی مبتنی بر شاخص • Bucket Based Index • Hash Based Index • B+ Tree Index 24 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر -Bucketمعرفی ‏MCI • هاسيگموس و همکارانش مبتنی بر افزودن شاخص مبتنی بر باکت ،روشی برای پرس و جو روی داده رمز شده ارائه دادند. • رديف‌هاي هر جدول به طور جداگانه و به کمک يکي از الگوريتم‌هاي رمزنگاري متقارن، رمز مي‌شوند. • به ازاي هر مشخصه‌ که جستجو روي آن انجام مي‌شود ،يک مشخصه به نام شاخص به جدول اضافه مي‌گردد. ‏Year ‏Author ‏Title ‏ID 2001 ‏Alfred J. Menezes ‏Handbook of Applied Criptography 123 ‏IY ‏IA ‏IT ‏IID ‏Enc_Tuple ‏Ψ ‏Φ ‏Π ‏Σ 4%n+!~kl?7klm\||fcapkmvk380($% درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 نحوه تعریف شاخص در روش ‏Bucketبندی .1 براي ايجاد شاخص امن ،بازه‌ي داده‌هاي هر مشخصه به تعدادي زيربازه تقسيم مي‌شود. – بازه ها نباید اشتراک داشته باشند. .2 ايجاد بازه‌ها مي‌تواند با استفاده از انواع روش‌هاي تقسيم‌بندي صورت گیرد. – طول برابر – تعداد اعضاي برابر .3 به هرکدام از بازه‌ها مقداري تعلق مي‌گيرد. – می توان از یک تابع توليد اعداد شبه تصادفي استفاده کرد. • به اين ترتيب به ازاي تمام داده‌هايي که در يک زيربازه قرار مي‌گيرند ،مقدار تعلق گرفته به زيربازه‌ی آنها در شاخص رمزشده قرار داده مي‌شود. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مثال – بازه بندی و اعطای شاخص درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI پرس‌وجو در شاخص دهی مبتنی بر Bucket • پرس‌وجو در دو مرحله صورت مي‌گيرد: .1 کارگزار سعي مي‌کند تا آنجا که امکان دارد پاسخ درستي برگرداند .2 کارخواه نتيجه‌ي ارسالي کارگزار را رمزگشايي کرده و آنرا پردازش مي‌کند. • در SQLیک پرس و جو می تواند با درخت‌هاي متفاوت که از نظر نتيجه يکسان هستند ،نمايش داده شود. • هاسیگموس جداسازی پرس و جو را (بخشی در سمت کارگزار و بخشی در سمت کارخواه) را با استفاده از درخت پرس‌وجو انجام داده است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI پرس و جو در شاخص دهی مبتنی بر Bucket )(2 • در روش هاسيگموس ،درخت نمايِش هر پرس‌و‌جو به دو قسمت تقسيم مي‌شود. .1 بخش زیر عملگر رمزگشایی :کلیه اعمالی که می تواند در سمت کارگزار انجام شود. .2 بخش باالی عملگر رمزگشایی :اعمالی که باید در سمت کارخواه انجام شوند. • َاعمال جبر رابطه‌اي وقتي به زير عمل رمزگشايي برده مي‌شوند ،بايد به َاعمال جديدي که روي داده‌هاي رمزشده قابل اجرا هستند ،تبديل شوند. – 29 هاسيگموس جبر رابطه‌اي جديدي را براي ِاعمال روي داده‌هاي رمزشده تعريف کرد. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI بهینه سازی اجرای پرس و جو ‏MCI ‏SELECT name FROM books, keeper ‏AND Title = "Handbook of ‏WHERE keeper.ID = books.keeping "applied cryptography ‏πname • فقط عملگر‌هایی که در زیر عملگر رمزگشایی هستند قابل اجرا در سمت کارگزار هستند • در این اجرا هیچ عملگری قابل اجرا به روی کارگزار نیست. ‏ ‏Books.keeper = Keeper.id • سربار ارتباطي و محاسباتي در سمت کارخواه باال است. • براي افزايش کارآيي بايد سعي کرد تا حد امکان، عملگرهاي رابطه‌اي را به زير عملگر رمزگشايي منتقل کرد. ‏D ‏σTitle = “Cryptography ‏KeeperS ‏D ” ‏BooksS درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 اجرای بهینه پرس و جو ‏MCI ‏πname • َاعمال تا حد امکان باید در سمت کارگزار انجام شود. • رابطه SELECTIONروي جدول Booksبه زير عملگر رمزگشايي برده شده است. • براي بردن اين عملگر به زير عملگر رمزگشايي بايد آنرا تبديل به s σکه در جبر جديد هاسيگموس براي SELECTIONروي جداول رمزشده و مشخصه‌هاي شاخص تعريف شده است ،تبديل کرد. • این اجرا از پرس‌وجو به دلیل اجرای برخی از عملگرها در سمت کارگزار اجرای کارایی است. = Λ Books.keeper ”σTitle = “Cryptography ‏D ‏keeper.id ‏ ‏Bookss.keepers = Keepers.ids 0 = σsTitle ‏BooksS درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏KeeperS مزایا و معایب روش باکت بندی برای تولید شاخص • روش های مبتنی بر Bucketبرای اجرای شروط تساوی مناسب هستند. – ‏Aij = v  Ij = β • پرس و جوهای بازه ای نیز با کمی تغییر در این روش شاخص دهی قابل اجرا است. – (Aij> v  ) Ij = β1 or β2 or …or βk • مثال: – شرط Salary>50000در جدول صفحات قبل باید به شکل زیر تبدیل شود: ‏Salarys=2 OR Salarys=10 OR Salarys=3 • عدم امکان اجرای توابع تجمعی مانند SUM، MIN، MAX، Avgو ... – هاسيگموس اين روش را تعميم داد و با استفاده از يک تابع همريخت اختفائی اجراي توابعي مثل جمع و ضرب را فراهم کرد. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مزایا و معایب روش باکت بندی برای تولید شاخص ()2 • وجود مقدار زیادی از داده های اضافی در نتایج کارگزار (به ویژه اگر اعمالی مانند پیوند در پرس و جو وجود داشته باشد) – روش‌هايي براي بهبود و کاهش اشتباه‌هاي مثبت در روش هاسيگموس ارائه شده است. • اين روش بيشتر براي داده‌هاي عددي کاربرد دارد و به کارگیری روش براي داده‌هاي رشته‌اي يا متني که دامنه‌ي داده‌ها بزرگ است ،چندان مناسب نیست. – در تعریف بازه برای داده‌های رشته‌ای ،ممکن است تعداد زیادی داد ‌ه در یک بازه قرار گیرد که این خود به معنای ارسال تعداد زیادی داده‌ي اضافی در پاسخ به يک پرس‌وجو و در نتیجه سربار ارتباطي و محاسباتي باال است. • اگر بازه ها طوری ساخته شوند که مثًال در هر بازه یک مقدار قرار بگیرد امکان تحلیل فرکانسی وجود دارد. 33 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر توابع درهم ساز • از مفهوم توابع درهم ساز برای ساختن شاخص استفاده می شود. • براي ساخِت شاخص در این روش ،داده‌ها توسط یک تابع درهم‌ساِز دارای تصادم دسته‌بندی می‌شوند. • مزيت این نوع شاخص دهی نسبت به روش باکت بندی این است که دسته‌بندي روي داده‌هاي پشت سر‌هم انجام نمي‌شود که این مي‌تواند باعث افزايش امنيت گردد. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر توابع درهم ساز ()2 • اکر riرابطه ای با اسکیمای ) Ri(Ai1, Ai2, . . . , Ainو rkiرابطه متناظر رمز شvvvده آن باشد ،برای هر صفت Aijدر Riکه بخواهیم برای آن شاخص تعریف کنیم ،تvvvابع درهم ساز یک طرفه h: Dij  Bijتعریف می شود که Dijدامنه Aijو Bijدامنه شاخص Ijمتناظر با Aijاست. )• for all x, y in Dij; if x = y then h(x)= h(y • برد hاز دامنه آن کوچکتر است . – امکان برخورد وجود دارد. • برای هر دو مقدار تصادفی متفاوت ولی نزدیک به هم xو yدر دامنه <| Dij (| x − y ) ، εتوزیع احتمالی ) h(x) − h(yیکنواخت است. – تابع درهم ساز ترتیب خصیصه در دامنه را حفظ نمی کند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر توابع درهم ساز – ویژگی ها • اجرای پرس و جوهای تساوی (مانند روش های شاخص دهی مبتنی بر )bucketممکن است. – هر شرط Aij=vبه شرط ) ،Ij=h(vکه Ijشاخص متناظر با Aijدر جدول رمز شده است، تبدیل می شود. • برخورد در توابع درهم ساز باعث ارسال چندتایی های اضافی به سمت کارخواه می شود. – تابع درهم ساز فاقد برخورد مشکل ارسال نتایج زیادی به کارخواه را رفع می کند ولی احتمال تحلیل های فرکانسی را افزایش می دهد. • مشکل اصلی روش های شاخص دهی مبتنی بر توابع درهم ساز عvvدم پشvvتیبانی از پvvرس و جوهای بازه ای است. – دامياني و همکارانش براي اضافه‌کردن قابليت انجام جستجوي بازه‌اي به این روش از شاخص مبتنی بر درخت +Bدر کنار این نوع شاخص دهی استفاده کردند. 36 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر درخت +B • یکی از روش های شاخص دهی استفاده از ساختار داده ای درخت +Bاست. • در درخت ، +Bگره های داخلی به طور مستقیم به چندتایی ها در پایگاه داده اشاره نمی کنند بلکه به سایرگره ها در ساختار اشاره می نمایند. • گره های برگ مستقیمًا به چندتایی هایی در پایگاه داده با مقادیر مشخص برای صفت شاخص اشاره می کنند • درخت +Bمی تواند برای هر صفت Aijدر اسکیمای Riکه در شروط پvvرس و جvvو ظvvاهر می شود ،تعریف شود. • شاخص توسط کارخواه روی مقادیر رمز نشده صvvفت ساخته شvvده و سپس روی کvvارگزار همراه با پایگاه داده رمز شده ذخیره می گردد. • ساختار درخت +Bبه جدولی با دو صفت شناسه گره و محتوای گره تبvvدیل می شvvود .این جدول برای هر گره یک ردیف دارد. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مثال 38 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش ارزیابی پرس و جو در درخت +B • فرض کنيد ،کارخواه اجراي پرس‌وجويي با شرط A > vرا درخواست کرده که vيک مقدار ثابت است .کارخواه بايد درخت Bذخيره شده روي کارگزار را براي يافتن محل ،v پيمايش کند. – کارخواه درخواستي براي دريافت ريشه‌ي درخت Bانجام مي‌دهد(.ريشه‌ي درخت ،رديِف با شماره‌ي 1است ).اين رديف به کارخواه ارسال و در آنجا رمزگشايي و پردازش مي‌شود. ي که بايد پيمايش شود انتخاب شده و درخواستی مبني بر ارسال آن – با توجه به مقدار ،vگره‌ي بعد ‌ گره به کارگزار فرستاده مي‌شود .اين روند تا پيدا کردن برگ حاوي vادامه پيدا مي‌کند. – پس از پيدا شدن ،vتمام برگ‌هاي بعد از آن به سمت کارخواه ارسال مي‌شوند .اين گره‌ها در سمت کارخواه رمزگشايي شده و شماره‌ي رکورد‌هاي مورد نظر پيدا شده به سمت کارگزار ارسال مي‌شود. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI شاخص مبتنی بر درخت -+Bویژگی ها • درخت +Bدر پاسخ به پرس و جو ،چندتایی اضافی به سمت کارخواه نمی فرستد. • هزینه ارزیابی شرایط پرس و جو برای کارخواه نسبت به روش های مبتنی بر باکت و توابع درهم ساز بسیار بیشتر است. – به همین دلیل معموًال درخت +Bرا در کنار یکی از روش های شاخص دهی مبتنی بر باکت یا توابع در هم ساز بکار برده و از درخت +Bتنها در هنگام ارزیابی بازه ها در پرس و جو ها استفاده می نمایند. • با توجه به این که محتوای درخت +Bدر سمت کارگزار رمزنگاری شده است ،این روش در برابر حمالت استنتاجی نیز مقاوم است. 40 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جستجوی مبتنی بر شاخص در داده های رشته ای • روشی مبتنی بر شاخص برای پرس و جو روی داده های رشته ای توسط Wang ارائه شده است (.)2004 • با استفاده از روش وانگ ،مي‌توان به جستجوي الگوهاي دلخواه در داده‌هاي رمزشده پرداخت. • ریزدانگی رمزنگاری در روش ،Wangدر سطح فیلد است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مراحل رمزنگاری .1 به هر رشته Sکه از nکاراکتر c1c2…cnتشکيل شده است ،مقدار شاخصی به .2 هر رشته‌ی S = c1c2…cnبه رشته‌ی S'= s1s2…s2n-2که در آن = si طول mبيت اختصاص داده مي‌شود. cici+1است ،بسط داده می‌شود. .3 با استفاده از تابع درهم‌ساز ،hمقداري بین 0تا mبراي هر کدام از siها به .4 اگر مقدار ) h(siبرابر با kباشد .در آن صورت بيت شماره kام در شاخص دست مي‌آيد. مربوطه برابر با يک مي‌شود. 42 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مثال ‏MCI )S1= (abcehklst • ‏m=16 • • تابعی در هم ساز دوتایی های ،... ،ab، bcو stرا به عددی بین 0تا 15نگاشت می کند. • ‏S2=Index(abcehklst)= (0010100010101001)2 • هشت رشته 2تایی وجود دارد در حالیکه 6بیت یک در S2دیده می شود .یعنی برخی از کاراکترهای دوتایی به یک مقدار توسط hنگاشت می شوند. 43 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 روش جستجو مقدار رشته‌ای موجود در الگوی رشته ای مورد پرس و جو بسط داده می‌شود و مقادیر اختصاص داده شده توسط تابع hبه هر دو حرف متوالی آن به دست می‌آید. .1 – پرس و جو روی مقدار رشته ای به پرس و جو روی شاخص (رشته بیتی) تبدیل می شود. .2 مقادیر به دست آمده ،مکان بیت‌هایی از مقادیر شاخص را که باید 1باشند تا شرط پرس‌وجو ارضاء شود ،مشخص می‌کند .این مقادیر به سمت کارگزار ارسال می‌شوند. .3 کارگزار به ازای هر مقدار شاخص ،مقادیر بیت‌های آن در مکان‌های ارسال شده را بررسی می‌کند ،اگر همه دارای مقدار 1بودند ،مقدار شاخص را به عنوان یکی از جواب‌ها به سمت کارخواه برمی گرداند. – در جواب های ارسال شده ممکن است نتایج اضافی وجود داشته باشد که باید توسط کارخواه مجددًا پردازش شده تا جواب دقیق به دست آید. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI MCI حالت های مختلف پرس و جوی رشته ای تطبیق دقیق .1 کهindex (value) aS = روی جدول رمز نشده تبدیل می شود بهattribute=value ◦ شرط . در سمت کارگزار استattribute مقدار رمز شدهaS تطبیق الگویی .2 : روی جدول رمز نشدهattribute LIKE value ◦ شرط a like c0c1…ck => ((as)H(c0c1)=1 AND (as)H(c1c2)=1 AND … AND (as)H(ck-1ck)=1) پرس و جوی با شرایط بولی (attribute=value 1) OR (attribute=value 2), (attribute like value 1) AND (attribute like value 2), (attribute like value 1) AND NOT (attribute like value 2) .– از حالت اول و دوم قابل استنتاج است 88-87 نيمسال دوم تحصيلي-درس امنيت پايگاه داده ها • MCI مثال select eid, age from employee where did like ‘chess’ Transforms to select * from employee E where (didsH(ch)=1) and (did sH(he)=1) and (did sH(es)=1) and (did sH(ss) =1) 88-87 نيمسال دوم تحصيلي-درس امنيت پايگاه داده ها 46 تحلیل روش • در این روش ،در صورتي که طول mبزرگ انتخاب شود ،حمله متن اصلی معلوم محتمل است. – هر زوج کاراکتر به مقدار یکتایی در شاخص منتسب می شوند و امکان تحليل فرکانسي و شکستن شvvاخص وجود دارد. • در صورت کوچک بودن ، mتعداد زیادی داده اشتباه به سمت کارخواه ارسال خواهد شد. • در جدول رمز شده فیلد اضافه ای برای شاخص باید در نظر گرفته شvvود کvvه حجم آن بvvه انvvدازه شاخص ( )mوابسته است. – 47 در صورتی که nفیلد نیاز به رمز شدن داشته و طول شاخص به طور متوسط mبیت باشد ،میزان فضvvای اضvvافی مورد نیاز m*nبیت برای شاخص است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI جمع بندی روش ها ی مبتنی بر شاخص • تحقیقات زیادی روی این گونه روش ها صورت گرفته و دارای زمینه تئوریvvک قvvوی می باشvvند. حتی دارای جبر رابطه ای مخصوص می باشند. • بیشتر فرایند اجرای پرس و جو بر روی کارگزار متمرکز است. • هزینه ذخیره سازی تقریبًا دو برابر ذخیره سازی معمولی است .زیرا غیر از مقدار رمز شده ذخvvیره، مقدار شاخص نیز ذخیره می گردد. • امکان استنتاج و افشای اطالعات وجود دارد که میزان آن وابسته به تعریف شاخص است. – Evdokimovو همکارانش اثبات کرده اند که تقریبًا تمام روش های مبتvvنی بvvر شvvاخص ذاتًvvا امن نیستند .به ویژه روشهایی که در پاسخ به پرس وجو چندتایی های اضvvافی تولیvvد نمی کننvvد ،در معرض تهدید افشای اطالعات قرار دارند. • پرس و جوهای شامل پیوند در این روش قابل اعمال است. • پرس و جوهای تساوی ،و الگویی برای داده های عددی و رشته ای قابل انجام است. • امکان اجرای پرس و جوهای بازه ای بسته به تعریف شاخص دارد. • امکان اجرای پرس و جوهای شامل توابع تجمعی وجود ندارد. • چون با تغییر توزیع داده ها نیاز به دسته بندی مجدد داده ها برای تعریvvف شvvاخص وجvvود دارد، این روش بیشتر برای داده های فقط خواندنی مناسب است. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش های مبتنی بر کاربرد توابع همریخت اختفایی • توابع همریخت اختفایی نوعی توابع برای رمزنگاری است. • در روش رمزنگاری همريخت اختفایی ( ،)privacy homomorphismحاصل انجام يک عمل روي داده‌هاي رمزشده ،معادل رمزشده حاصل عملي ديگر روي داده‌هاي اصلي است. • β(xE , yE) = (α(x,y))E )– E(x) . E(y) = E(x+y • بوسيله‌ي توابع رمزنگاري همريخت اختفائی مي‌توان برخي از عمليات مانند جمع و ضرب را به طور مستقيم روي داده‌هاي رمزشده انجام داد. • فیلدهایی را که روی آنها پرس و جوی تجمعی اجرا می شود ،با استفاده از رمزنگاری همریخت رمز می کنند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش هاسیگموس • هاسيگموس با استفاده از يک تابع رمزنگاري همريخت اختفائی که دو خاصيت جمعي و ضربي را پشتیبانی می کند ،توابع جمع و ضرب را روي داده‌هاي رمزشده اجرا کرد. • خواص تابع رمزنگاری همومورفیسم استفاده شده: – کلید رمزنگاری ) K=(p, qکه pو qبه وسیله کاربر تعیین می شوند. که به کارگزار داده می شود n = p.q – )– qq-1 =1 (mod p )– pp-1 = 1 (mod q )– Ek(a mod p, a mod q – درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مثال ‏MCI • p=5,q=7 )k = (5, 7 • n = p.q = 35 • می خواهیم a1 = 8و a2 = 12را جمع کنیم )• E(a1) = (3,1 )• E(a2) = (2,5 )• E (a1) + E (a2) = (3+2, 1+5) = (5, 6 )• D (5, 6) = 5*qq-1 + 6*pp-1 (mod 35 = (5*7*3 + 6*5*3) (mod 35) =195 (mod 35) = 20 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 مشکل استنتاج • استفاده از تابع رمزنگاري همريخت اختفائِی معرفي شده کامًال امن نيست و کارگزار مي‌تواند مقدار اصلي برخي از مقادير رمزشده را به دست آورد. – فرض کنيد x ،و yدو عدد باشند که به صورت ( )xp,xqو ( )yp,yqرمز شده‌اند .اگر z=x.yباشد ،رابطه‌ي ( )yp,yq(.)xp,xq(=)zp,zqنيز بين مقادير رمزشده اين متغيرها وجود دارد .در چنين حالتی کارگزار مي‌تواند مقادير اصلي اين متغيرها را به دست آورد .کارگزار شروع به جمع کردن ( )xp, xqبا خودش مي‌کند و اين کار را آنقدر ادامه مي‌دهد تا نتيجه آن با ( )zp, zqبرابر شود .تعداد اين جمع کردن‌ها برابر با عدد yاست. • هاسيگموس با اضافه کردن نويز تصادفي به مقادير رمزشده ،مشکل را حل می کندR(x) . يک تابع شبه تصادفي است. • نويز در هنگام رمزگشايي از داده‌ها حذف مي‌شود. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI روش های رمزنگاری مبتنی بر حفظ ترتیب • در روش های رمزنگاری با حفظ ترتیب ( )Order Preservingداده ها بvvه گونvvه ای رمز می شوند که ترتیب داده ها پس از رمز شدن با ترتیب داده های اصلی یکسان باشد. • این نوع رمزنگاری برای اجرای پرس و جو های بازه ای مناسب است. • آگراوال برای رمزنگاری داده های عددی و اجرای پرس و جوهای بازه ای روی آنها از این روش استفاده کرده است. • فرض کنيد ،داده‌هاي اصلي داراي توزيع اوليه Aهستند .اين داده‌ها به نحوي رمز مي‌شوند، که عالوه بر حفظ ترتيب از توزيع دلخواه 'Aتبعيت کنند. – ابتدا داده‌ها به توزيع يکنواخت fنگاشت شده و سپس توزيع fبه توزيع هدف 'Aنگاشت مي‌شود. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI مراحل رمزنگاری • OPESدر سه مرحله کار مي‌کندOrder Preserving Encryption(. )Scheme مدل کردن :داده‌هاي اصلي به تعدادي دسته تقسيم مي‌شوند و توزيع داده‌هاي هر دسته مدل مي‌شود. .1 • روش هایی برای تعیین تعداد دسته ها و طول هر دسته وجود دارد. • افزايش دسته‌ها منجر به افزايش هزينه‌هاي مدل مي‌شود. مسطح کردن :داده‌های اصلي Pبه داده‌های مسطح Fبه قسمي تبديل شود که مقادير F .2 .3 داراي توزيع يکنواخت باشند. • در مرحله‌ي مسطح کردن براي هر دسته ،يک تابع نگاشت Mايجاد مي‌شود .تابع ‌Mهر دسته را به دسته‌اي با توزيع يکنواخت نگاشت مي‌کند. • دو مقدار متفاوت در داده های اصلي هميشه به دو مقدار متفاوت از فضاي مسطح شده نگاشت شوند. تغيير :داده‌های مسطح Fبه داده‌های رمزشده Cتبديل مي‌شود ،به قسمي که مقادير C داراي توزيع نهايي که براي داده‌هاي رمزشده در نظر گرفته شده بود ،باشند. درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI MCI ‏B0c ‏B0f ‏B0f ‏B0 ‏Bm 1 ‏Bkf 1 ‏Bmf  1 ‏Bkc 1 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ویژگی های روش رمزنگاری با حفظ ترتیب • اجرای پرس و جوها در این روش چندتایی های اضvvافی بvvه سvvمت کvvارخواه ارسال نمی کند. • امنیت در این روش زمانی تامین می شود که کارگزار/حمله کننده اطالعاتی در مورد پایگاه داده اصلی و یا دامنه صفت ها نداشته باشد. – این روش در مقابل حمله متن اصلی معلوم آسیب پذیر است. 56 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87 ‏MCI MCI پایان 57 درس امنيت پايگاه داده ها -نيمسال دوم تحصيلي 88-87