כוח גס

במדעי המחשב, מתמטיקה וקריפטוגרפיה, כוח גס או תְּקִיפָה כּוֹחָנִית (לפי האקדמיה ללשון העברית) מאנגלית: Brute force, או חיפוש ממצה מאנגלית: Exhaustive search, מתייחס לתהליך או אלגוריתם שפועל באופן של ניסוי וטעייה של כל האפשרויות לפתרון בעיה נתונה עד למציאת הפתרון הנכון. מקור הביטוי בעובדה שבדרך כלל שיטה ישירה שאינה מנצלת קיצורי דרך אינטליגנטיים, דורשת הפעלת כוח לא מידתי או השקעת אנרגיה רבה בתקווה שהפתרון יימצא בסופו של דבר ולכן איננה נחשבת יעילה.

חיפוש ממצה

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

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

במקרה הגרוע בעיות NP קשות ניתנות לפתרון רק באמצעות חיפוש ממצה, אלא אם כן יתברר ש-P=NP.

התקפת כוח גס בקריפטוגרפיה

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

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

מהיבט של תורת האינפורמציה צופן מושלם הוא צופן כזה שלא משנה כמה עוצמת מחשוב זמינה בידי המתקיף, הוא לעולם לא יצליח לפענח את הטקסט המוצפן כי פשוט אין בידיו המידע המינימלי הדרוש כדי לפענחו. במילים אחרות הניסיון לנחש את הטקסט הגלוי נותן מספר אפשרויות כל כך גדול שאין בו כל תועלת. אולם ביטחון מושלם אינו בר השגה מבחינה מעשית ולכן בפועל מתפשרים על ביטחון חישובי לפיו ביטחון האלגוריתם נמדד במונחים של הזמן הדרוש כדי לפצח אותו. בהנחה שלא קיימת דרך קצרה אלא הדרך היחידה לפרוץ את האלגוריתם היא באמצעות ניסוי כל המפתחות האפשריים כדי לגלות את המפתח בו השתמש המצפין, הרי שבעצם סיבוכיות ההתקפה נגד האלגוריתם נמדדת לפי אורך המפתח בסיביות ככל שהוא ארוך יותר כך סיבוכיות ההתקפה עולה באופן מעריכי. אילו מפתח ההצפנה היה כאורך המסר עצמו והוא נבחר באקראי מספר האפשרויות במקרה זה היה מקסימלי כמו בפנקס חד-פעמי כאמור, אולם במערכת הצפנה מודרנית בפועל מפתח ההצפנה קטן מאוד בהשוואה לטקסט המוצפן בניסוח פורמלי $|{\mathcal {K}}|<|{\mathcal {M}}|$, עובדה זו מדליפה מעט מידע שיכול לשמש את המתקיף, כי בהינתן טקסט מוצפן $c$ המתקיף יכול לנסות לפענחו עם כל המפתחות האפשריים $k\in {\mathcal {K}}$ ולקבל רשימה של כל הטקסטים הגלויים האפשריים. הרשימה אינה יכולה להכיל את כל המרחב ${\mathcal {M}}$ כיוון שמרחב המפתח עצמו קטן יותר ולכן הוא יכול לנחש את המפתח הנכון מתוך רשימת המפתחות האפשריים ולהצליח בהסתברות שהיא טובה יותר מההסתברות במקרה של פנקס חד-פעמי. יתרה מזו, אם נניח שהיריב הצליח לגלות מעט טקסט מוצפן מבלי לנחש את המפתח (ייתכן שהוא השיג זאת בדרך אחרת כמו על ידי ציתות וגנבה) וכעת בידיו מספר זוגות של טקסטים מוצפנים $c_{1},...,c_{\ell }$ וגלויים $m_{1},...,m_{\ell }$ כך שמתקיים $c_{i}={\text{Enc}}_{k}(m_{i})$ עבור כל הטקסטים מ-1 עד $\ell$. הוא יכול לנסות לפענח כל אחד מהטקסטים המוצפנים שבידו עם כל המפתחות האפשריים עד שנמצאת התאמה, כלומר שמתקיים $m_{i}={\text{Dec}}_{k}(c_{i})$ עבור כל $i$ מ-1 עד $\ell$. המפתח שיימצא יהיה ייחודי ולמעשה יהיה מפתח ההצפנה שאיתו השתמש המצפין בהסתברות גבוהה, איתו הוא יכול לפענח את יתרת הטקסט המוצפן.

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

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

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

אם המפתח באורך 128 סיביות מספר האפשרויות לניחושו הוא $2^{128}$ שזה מספר אסטרונומי, מספר השנים שיעברו עד שהמתקיף ימצא את המפתח הנכון הוא $10^{25}$ שנים שזה גדול בהרבה מגיל היקום. ההערכה נכון לשנת 2017 היא שמפתח באורך 128 סיביות נמצא מחוץ להישג יד וחיפוש ממצה של המפתח בכוח גס אפילו בהפעלה מקבילית של מיליוני מחשבי על, אינו מעשי כלל. כמובן שיש להביא בחשבון שבכל רגע עלולה להתגלות דרך מתוחכמת יעילה יותר מכוח גס לשבירת אלגוריתם ההצפנה. מפתחי אלגוריתמים שואפים להגיע למצב שאלגוריתם ההצפנה שפיתחו יהיה ניתן לשבירה אך ורק באמצעות כוח גס כי אז אפשר לשלוט בביטחון האלגוריתם על ידי קביעת אורך מפתח הצפנה באופן כזה שהתקפת כוח גס תהיה מחוץ להישג יד.

ניחוש סיסמה

ניחוש סיסמת משתמש הנקראת גם התקפת מילון היא ניסיון לנחש את סיסמת המשתמש על ידי ניסוי ובדיקה של כל הסיסמאות האפשריות או הסיסמאות הסבירות או הנפוצות ביותר. אם הסיסמה מכילה שמונה תווים מתוך אלפבית בן 36 תווים (26 אותיות ועשר ספרות) והיא אקראית לחלוטין ישנם בסך הכול $36^{8}\approx 10^{13}$ צירופים אפשריים. גם אם מחשב אחד מסוגל לבדוק מיליון צירופים בשנייה יידרשו 2,821,109 שניות (קצת יותר מחודש) כדי למצוא את הסיסמה הנכונה. ברוב המקרים מערכות אבטחה מציבים מכשולים נוספים כמו הגבלת מספר הניסיונות הכושלים ונעילה של המערכת לפרק זמן ממושך או האטה מכוונת של תהליך הבדיקה עצמו, באופן כזה שלמשתמש הלגיטימי ההאטה תהיה שולית ולא מורגשת ואילו עבור המתקיף היא יוצרת בעיה כיוון שזמן ההתקפה הכולל מתארך עשרת מונים. למעשה במרבית מערכות האבטחה מספר האפשרויות גדול בהרבה. ישנן מערכות שמחייבות הכללה של לפחות סימן פיסוק אחד מתוך 33 אפשריים, בנוסף ל-52 אותיות (רישיות וקטנות) ו-10 ספרות מה שנותן עבור סיסמה בת שמונה סימנים $95^{8}\approx 10^{16}$ אפשרויות בקירוב.

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

ראו גם

• קריפטואנליזה
• התקפת איזון זמן/זיכרון

קישורים חיצוניים

• כוח גס, באתר MathWorld (באנגלית)

Brute Force – המתקפה הכי קלה להסבר, למימוש ולהגנה, בבלוג camelCase