כוח גס

במדעי המחשב, מתמטיקה וקריפטוגרפיה, כוח גס או כוח ברוטלי מאנגלית: Brute force, או חיפוש ממצה מאנגלית: Exhaustive search, מתייחס לתהליך או אלגוריתם שפועל באופן של ניסוי וטעייה של כל האפשרויות לפתרון בעיה נתונה עד למציאת הפתרון הנכון. מקור הביטוי בעובדה שבדרך כלל שיטה ישירה שאינה מנצלת קיצורי דרך אינטליגנטיים, דורשת הפעלת כוח לא מידתי או השקעת אנרגיה רבה בתקווה שהפתרון יימצא בסופו של דבר ולכן איננה נחשבת יעילה. מקור השם במילה היוונית "ברוטוס" שפירושה גס, המוני, חסר היגיון.

חיפוש ממצה

במדעי המחשב חיפוש ממצה מתאר טכניקות גנריות לפתרון בעיות מתמטיות המסתמכות על מיפוי שיטתי של כל הפתרונות האפשריים ובדיקה האם נמצא ביניהם פתרון לבעייה נתונה. לדוגמה אלגוריתם פירוק לגורמים של מספרים שלמים בשיטת חילוק ניסיוני (trial division). בדרך כלל אלגוריתם חיפוש ממצה פשוט וקל ליישום ובסופו מובטח שיימצא הפתרון אם קיים, לכן שיטות כוח גס יכולות להיות שימושיות כאשר טווח החיפוש קטן, או כאשר קיימת היוריסטיקה המאפשרת לצמצם את טווח החיפוש לכדי גודל בר ביצוע. או כאשר יש עדיפות לשיטות פשוטות וקלות ליישום על פני מהירות ביצוע. אלגוריתם כוח גס יכול לשמש גם כאלגוריתם ייחוס לצורך השוואת ביצועים.

המושג "כוח גס" תקף גם להוכחות מתמטיות שבהן השיטה להוכחה היא ביצוע חישובים ארוכים ומייגעים, אך ישירים, של כל המקרים האפשריים, במקום לחשוב על פתרון אלגנטי יותר. ההוכחה הראשונה של משפט ארבעת הצבעים מורכבת משני צעדים: ראשית מראים שכדי להוכיח את הטענה (המתייחסת לאינסוף מצבים), מספיק לבדוק אותה ב-1,936 מקרים מסוימים; אלו נבדקים ב'כוח', במחשב.

אלא אם כן יתברר ש-P=NP מה שלא סביר שיקרה, אם כי טרם ניתנה הוכחה לכך, במקרה הגרוע בעיות NP ניתנות לפיתרון רק באמצעות חיפוש ממצה^[1].

התקפת כוח גס

התקפת כוח גס קריפטוגרפית ישימה בכמה מישורים כאשר בכולם השיטה בדרך כלל חסרת תחכום ועיקרה הוא ניסוי שיטתי של כל האפשרויות^[2].

ניחוש מידע מוצפן

מהיבט של תורת האינפורמציה צופן מושלם הוא צופן כזה שלא משנה כמה עוצמת מחשוב זמינה בידי המתקיף, הוא לעולם לא יצליח לפענח את הטקסט המוצפן כי פשוט אין בידיו המידע המינימלי הדרוש כדי לפענחו. במילים אחרות הניסיון לנחש את הטקסט הגלוי נותן מספר אפשרויות כל כך גדול שאין בו כל תועלת. אולם ביטחון מושלם אינו בר השגה מבחינה מעשית ולכן בפועל מתפשרים על ביטחון חישובי. היות שמפתח ההצפנה קטן בהשוואה לטקסט המוצפן בניסוח פורמלי $|{\mathcal {K}}|<|{\mathcal {M}}|$ , עובדה זו מדליפה מידע כלשהו שיכול לשמש את המתקיף, כי בהינתן טקסט מוצפן $c$ המתקיף יכול לנסות לפענחו עם כל המפתחות האפשריים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle k\in\mathcal{K}} ולקבל רשימה של כל הטקסטים הגלויים האפשריים. הרשימה אינה יכולה להכיל את כל המרחב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{M}} כאמור ולכן הוא יכול לנחש אחד מהם ולהצליח בהסתברות מסויימת. יתרה מזו, אם נניח שהיריב הצליח לגלות מעט טקסט מוצפן מבלי לנחש את המפתח (ייתכן שהוא השיג זאת בדרך אחרת כמו על ידי ציתות וגניבה) וכעת בידיו מספר זוגות של טקסטים מוצפנים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_1,...,c_{\ell}} וגלויים $m_{1},...,m_{\ell }$ . הוא יכול לנסות לפענח כל אחד מהטקסטים המוצפנים שבידו עם כל המפתחות האפשריים עד שנמצאת התאמה, כלומר שמתקיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle m_i=\text{Dec}_k(c_i)} עבור כל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} מ-1 עד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ell} . המפתח שיימצא יהיה ייחודי ולמעשה יהיה מפתח ההצפנה שאיתו השתמש המצפין בהסתברות גבוהה.

ניחוש מפתח הצפנה

ניחוש מפתח הצפנה^[3] הוא ניסיון לפענח טקסט מוצפן נתון באמצעות כל המפתחות האפשריים ולבדוק האם התוצאה מתאימה לטקסט גלוי מסויים. אם נמצאת התאמה המפתח שהתגלה יכול לשמש כדי לפענח את כל המסרים שהוצפנו עם מפתח זה. מהיבט מעשי, בניגוד לפנקס חד-פעמי שבו המפתח כאורך הטקסט המוצפן, השאיפה היא שיהיה אפשר להצפין מסרים ארוכים עם מפתח קצר. במצב כזה ביטחון ניתן להשגה אך ורק אם מגבילים את יכולת היריב לשבור את הצופן. או לחילופין מגבילים את זמן הריצה שלו כך שלא יהיה לו מספיק זמן כדי להשלים את ההתקפה בכוח גס. למעשה מאפשרים מצב שהיריב יוכל בהסתברות מאד מאד נמוכה לשבור את הצופן. התקפה מסוג זה היא לינארית ביחס ל- $|{\mathcal {K}}|$ וסיבוכיותה מעריכית, ככל שהמפתח גדול יותר מספר האפשרויות גדל באופן מעריכי.

לדוגמה נניח שברשות המתקיף מחשב על שמסוגל לבצע מיליון הצפנות בשנייה, אם המפתח באורך 56 סיביות כמו במקרה של DES יידרשו 2,285 שנים כדי למצוא את המפתח הנכון. לפני מספר שנים הייתה הערכה שאם יהיה אפשר לבנות מכונה ייעודית המכילה כמיליון שבבים שיכולים לבצע באופן מקבילי כמיליון הצפנות בשנייה אז ניתן יהיה לשבור את DES בכוח גס בזמן של 20 שעות לכל היותר, לעומת זאת אם המפתח באורך 64 סיביות יידרשו 214 ימים. בשנים האחרונות חלה התפתחות טכנולוגית כך שבמחיר של פחות ממיליון דולר אפשר לבנות מכונה לפיצוח DES שתמצא את המפתח בזמן של 7 שעות לכל היותר. לפי חוק מור ההערכה הכללית הייתה שכוח המחשוב יוכפל אחת לשמונה עשר חודשים, ואכן כיום קיימים בשוק שבבים ייעודיים שמסוגלים לשבור את DES בזמן מאד קצר ובעלות נמוכה בהרבה. זו למעשה הסיבה העיקרית מדוע DES הוחלף ב-AES.

אם המפתח באורך 128 סיביות מספר האפשרויות לניחושו הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{128}} שזה מספר אסטרונומי, מספר השנים שיעברו עד שהמתקיף ימצא את המפתח הנכון הוא הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10^{25}} שנים שזה גדול בהרבה מגיל היקום. ההערכה נכון לשנת 2017 היא שמפתח באורך 128 סיביות נמצא מחוץ להישג יד וחיפוש ממצה של המפתח בכוח גס אפילו בהפעלה מקבילית של מיליוני מחשבי על, אינו מעשי כלל. כמובן שיש להביא בחשבון שבכל רגע עלולה להתגלות דרך מתוחכמת יעילה יותר מכוח גס לשבירת אלגוריתם ההצפנה. מפתחי אלגוריתמים שואפים להגיע למצב שאלגוריתם ההצפנה שפיתחו יהיה ניתן לשבירה אך ורק באמצעות כוח גס כי אז אפשר לשלוט בביטחון האלגוריתם על ידי קביעת אורך מפתח הצפנה באופן כזה שהתקפת כוח גס תהיה מחוץ להישג יד. אין דרך מתמטית בדוקה להוכיח שאלגוריתם הצפנה אינו ניתן לשבירה בדרך אחרת יעילה יותר וכן לא ניתן להבטיח שלא תמצא דרך כזו בעתיד. מאידך ניסיון מחקר של שנים מאפשרים לתת אמון באלגוריתם הצפנה ככל שעובר הזמן.

ניחוש סיסמה

ניחוש סיסמת משתמש הנקראת גם התקפת מילון היא ניסיון לנחש את סיסמת המשתמש על ידי ניסוי ובדיקה של כל הסיסמאות האפשריות או הסיסמאות הסבירות או הנפוצות ביותר. אם הסיסמה מכילה שמונה תווים מתוך אלפבית בן 36 תווים (26 אותיות ועשר ספרות) והיא אקראית לחלוטין ישנם בסך הכול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 36^{8}} צירופים אפשריים. גם אם מחשב אחד מסוגל לבדוק מיליון צירופים בשנייה יידרשו 2,821,109 שניות (קצת יותר מחודש) כדי למצוא את הסיסמה הנכונה. ברוב המקרים מערכות אבטחה מציבים מכשולים נוספים כמו הגבלת מספר הניסיונות הכושלים ונעילה של המערכת לפרק זמן ממושך או האטה מכוונת של תהליך הבדיקה עצמו, באופן כזה שלמשתמש הלגיטימי ההאטה תהייה שולית ולא מורגשת ואילו עבור המתקיף היא יוצרת בעיה כיוון שזמן ההתקפה הכולל מתארך עשרת מונים. למעשה במרבית מערכות האבטחה מספר האפשרויות גדול בהרבה. ישנן מערכות שמחייבות הכללה של לפחות סימן פיסוק אחד מתוך 33 אפשריים, בנוסף ל-52 אותיות (רישיות וקטנות) ו-10 ספרות מה שנותן עבור סיסמה בת שמונה סימנים $95^{8}$ אפשרויות בקירוב.

הבעייה העיקרית היא שלמעשה מרבית המשתמשים נוטים לבחור סיסמאות שקל לזכור כמו שמות, תאריכי לידה או ביטויים נפוצים. במקרה כזה התקפת מילון נחשבת הרבה יותר יעילה מכוח גס.

ראו גם

הערות שוליים

^ Exhaustive Search
^ Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).
^ Schneier, Bruce (1996). Applied Cryptography (2nd ed.). John Wiley & Sons. pp. 366–367. ISBN 0-471-11709-9.

[1] Exhaustive Search

[2] Jonathan Katz and Yehuda Lindell (2007). Introduction to Modern Cryptography (2nd edition).

[3] Schneier, Bruce (1996). Applied Cryptography (2nd ed.). John Wiley & Sons. pp. 366–367. ISBN 0-471-11709-9.

[1]

[2]

[3]