צופן בלוקים

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בקריפטוגרפיה, צופן בלוקים (block cipher) הוא צופן סימטרי איטרטיבי דטרמיניסטי הפועל על מחרוזת סיביות באורך קבוע הנקראת בלוק באמצעות טרנספורמציה קבועה. צופן בלוקים מקבל בלוק של סיביות טקסט-גלוי (plaintext) ומפתח הצפנה סודי ומפיק בלוק טקסט-מוצפן (ciphertext). כאשר אופן פעולת הטרנספורמציה נשלט על ידי מפתח ההצפנה. פענוח מתבצע באופן דומה, אלגוריתם הפענוח מקבל בלוק סיביות טקסט-מוצפן והמפתח שאיתו הוצפן ומחזיר את בלוק הסיביות המקורי. צופן בלוקים מתאים להצפנה מאסיבית ובדרך כלל יעיל למימוש כחלק מחומרה ייעודית או בתוכנה.

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

DES שפותח על ידי IBM בשיתוף עם NSA ופורסם ב-1977 הוא דוגמה לאחד מצפני הבלוקים הראשונים והמשפיעים ביותר במאה הקודמת, הצופן התבסס על טכניקות שפיתח מהנדס יבם, האמריקאי-גרמני הורסט פייסטל, שאותם יישם תחילה בצופן שלו לוציפר. ממשיכו של DES הקרוי AES שאומץ כתקן הצפנה רשמי ב-2001, נמצא כיום בשימוש מאסיבי ומהווה מרכיב בסיסי וחשוב בכמעט כל מערכת אבטחת מידע מודרנית.

הגדרה פורמלית[עריכת קוד מקור | עריכה]

צופן בלוקים מוגדר פורמלית על ידי פונקציה מהצורה‏[1]:

E(K,P):\{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n

שהיא פרמוטציה פסאודו-אקראית בקיצור PRP המקבלת את הפרמטרים: מחרוזת בינארית K בגודל k סיביות ומחרוזת בינארית P בגודל n סיביות ומפיקה מחרוזת C בגודל n סיביות והפעולה ההופכית שלה מקבלת את C ומחזירה את P. אפשר לסמן זאת בקיצור:

C=E_K(P)
P=D_K(C)

פונקציית הפענוח D היא הפונקציה ההופכית E^{-1}. לצורך הפורמליות הפונקציה המתוארת הפיכה אם עבור כל טקסט קריא P ומפתח K נתונים מתקיים D_K(E_K(P))=P. כדי למנוע התנפחות לא רצויה מקובל שגודל הבלוק המוצפן C יהיה כגודל הבלוק המקורי P. וכן משיקולי יעילות רצוי שלא יהיה הבדל גדול בין פונקציות ההצפנה והפענוח, כך שניתן יהיה ליישמן באותה חומרה או תוכנה. דרך אחרת לייצג צופן בלוקים היא על ידי שלישיית האלגוריתמים:

\mathcal{SE}=\{\mathcal{K}_e,\mathcal{E},\mathcal{D}\}

כאשר \mathcal{K}_e הוא אלגוריתם הכנה המשתמש במפתח הסודי המסופק על ידי המשתמש כדי לייצר מפתח הצפנה מתאים לצורך ההצפנה. \mathcal{E} היא פונקציית הצפנה - encryption ו-\mathcal{D} היא פונקציית פענוח - decryption שהיא הפונקציה ההופכית. תאורטית רצוי שעבור כל מפתח K\in\mathcal{K} הפונקציה E_K תהיה פרמוטציה (או פונקציה חד-חד-ערכית ועל) אקראית מעל 2^n! הבלוקים האפשריים בגודל n סיביות. במקרה כזה אפשר להגיע לצופן מושלם שאינו ניתן לשבירה אפילו ליריב בעל עוצמת חישוב בלתי מוגבלת. אולם הבעיה היא שמרחב המפתח חייב להכיל לפחות 2^n! מפתחות אפשריים מה שאומר שגודל המפתח אפקטיבית חייב להיות בערך \mbox{log}_2(2^n!) \approx (n-1.44)2^n סיביות. זה לא מעשי במיוחד כש-n גדול. לכן מקובל שפונקציית הצפנה "תראה" מבחינה חישובית כאקראית מה שמספק ביטחון חישובי, שמותאם ליריב בעל עוצמת חישוב מוגבלת בזמן ומקום. מקובל שהמפתח K המסופק על ידי המשתמש יהיה קצר ובאמצעות פרוצדורת 'הרחבת מפתח' מתאימה נמתח לאורך הרצוי. המפתח מורחב באופן שאינו מאפשר תאורטית (או בכל אופן קשה מאוד מבחינה חישובית) לנחשו ללא ידיעת K.

היסטוריה והתפתחות[עריכת קוד מקור | עריכה]

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

את היסודות לצופן בלוקים המודרני הניח קלוד שאנון אבי תורת האינפורמציה שבמאמר חשוב‏[2] מ-1949, הסביר את עקרונות השיטה מהיבט של תורת האינפורמציה. הוא סיפק הוכחות מתמטיות והגה לראשונה את רעיון ההרכבה של צופן החלפה (שיכול) עם צופן העתקה (טרנספוזיציה), כדי לקבל פונקציית הצפנה חזקה. הוא כינה זאת שילוב של פיזור (diffusion) וערבוב (confusion), הפיזור נועד להבטיח שהמפתח והטקסט הקריא ישפיעו על כל סיביות הצופן במידה שווה וערבוב נועד לגרום לקשר בין הצופן למקור או המפתח להיות רחוק ככל האפשר. וכן הגה את רעיון האיטרציה, כלומר מפעילים פונקציה פנימית כלשהי במספר חזרות, כאשר פלט סבב אחד הופך קלט לסבב הבא וכן הלאה. האיטרציה מחזקת את הצופן גם במקרה שהפונקציה הפנימית חלשה. מֵפַתֵח הצופן קובע את מספר הסבבים כדי להגיע לרמת ביטחון רצויה. אפשר ליצור צופן חזק יותר על ידי ביצוע מספר גדול מאוד של סבבים, אולם יעילותו תפגע.

נהוג לקרוא לפונקציה הפנימית פונקציית סבב (round function) וכן נהוג לסמנה F-Box או בקיצור F. הפונקציה הפנימית מקבלת כפרמטר מלבד את הבלוק הנוכחי, קטע מתאים ממפתח ההצפנה, אותו מפיקים באמצעות פרוצדורת ההכנה. בדרך כלל נוספת פעולת 'הלבנה' (whitening), שהיא חיבור עם חלק ממפתח ההצפנה באמצעות פעולת XOR (שמיוצג כאן על ידי הסמל \oplus) לפני הסבב הראשון ולאחר הסבב האחרון.

להלן מבנה טיפוסי של צופן בלוקים:

שלד בסיסי של צופן בלוקים
M_0=M\oplus K_0
\text{For }i=1\text{ to }r\text{ do: }M_i=F_{K_i}(M_{i-1})
C=M_r \oplus K_{r+1}

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

גודל הבלוק[עריכת קוד מקור | עריכה]

גודל הבלוק n הוא בדרך כלל 128 סיביות. בלוקים קטנים מאוד חושפים את האלגוריתם להתקפות סטטיסטיות וככל שהבלוק גדול יותר כך סיבוכיות ההתקפה על הצופן תגדל מעריכית, אולם יעילותו תרד בהתאם. האיזון בין יעילות לביטחון הוא גורם מכריע בקביעת גודל הבלוק. קיימים צפנים שלהם בלוק בגודל 64 סיביות כמו DES או IDEA, גודל זה היה נפוץ בסוף שנות ה-90 של המאה הקודמת והתאים ליכולת הטכנולוגית דאז. נכון לשנת 2014 פחות מ-128 סיביות נחשב לצופן חלש. המשמעות של גודל בלוק מהיבט של קריפטואנליזה הוא סיבוכיות מקום. ישנן התקפות כוח גס שעושות שימוש בזיכרון כדי לקצר את זמן החישוב. כדי לשבור צופן עם בלוק בגודל 128 סיביות בדרך זו , יש צורך באיחסון סדר גודל של 2^{128} בלוקים, זהו מספר אסטרונומי שכמעט ואינו ניתן ליישום בטכנולוגיה הנוכחית. גם אם מסתמכים על עיקרון פרדוקס יום ההולדת, כמות המידע שצריך לאחסן עצומה.

גודל המפתח[עריכת קוד מקור | עריכה]

גודל מפתח הצפנה נקבע בדרך כלל לפי היכולת הטכנולוגית וסיבוכיות מיטב ההתקפות הידועות. מפתח ההצפנה של DES היה 64 סיביות שמתוכן רק 56 סיביות שימשו להצפנה והיתר שימשו לבדיקת זוגיות. מסיבה זו התקפת כוח גס (דהיינו ניסוי כל המפתחות האפשריים) כנגד DES ברת-ביצוע בזמן סביר. קיימת חומרה ייעודית שמסוגלת לשבור את DES באמצעות כוח גס בפחות משעה ובעלות סבירה. מסיבה זו DES אינו מומלץ לשימוש כיום. כדי שגודל המפתח האפקטיבי יהיה מרבי, יש לבחור את המפתח באופן אקראי מתוך מרחב המפתחות המקסימלי כך שכל מפתח יכול להיבחר בהסתברות שווה או לפחות כמעט בהסתברות שווה. מסיבה זו אומרים שגודל המפתח האפקטיבי של DES הוא רק 56 סיביות מכיוון שלא כל הסיביות נוצלו. ההנחה הרווחת נכון לשנת 2014 שמפתח הצפנה בגודל 128 סיביות מספק ביטחון סביר לכל צורך מעשי אך יש כאלו שממליצים לעבור ל-256 סיביות.

תכונות[עריכת קוד מקור | עריכה]

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

  • גודל מפתח וגודל בלוק. ערכים אילו קובעים בדרך כלל את הגבול העליון של הביטחון המשוער של הצופן. באופן כללי אורך מפתח משפיע על סיבוכיות זמן ואורך הבלוק על סיבוכיות מקום.
  • ביטחון. הערכת ביטחון המסתמכת על ניסיונות אינטנסיביים מצד אנליסטים רבים לתקוף את הצופן עם מיטב ההתקפות הקריפטוגרפיות הידועות. בראשן קריפטואנליזה דיפרנציאלית, קריפטואנליזה לינארית, התקפת ערוץ צדדי ועוד.
  • יעילות בתוכנה. סיבוכיות יישום הצופן בתוכנה, יעילות ומורכבות הקוד, צריכת זיכרון, שימוש בתת-בלוקים המתאימים לגודל מילה במעבד, סיבוכיות פעולות אלגבריות וכדומה.
  • יעילות בחומרה. יצרנים שואפים להטמיע צופן בלוקים בחומרה ייעודית כדי לשפר ביצועים. יכולת הטמעה בחומרה נמדדת במספר המעגלים המינימלי הדרוש ליישומו, אפשרות למקביליות, צריכת זיכרון, מורכבות קוד ופשטות פעולות האלגוריתם.
  • ביצועים. תפוקת האלגוריתם נמדדת במספר הבתים שניתן להצפין בשנייה על מגוון פלטפורמות, כמו מעבד 64 סיביות או 8 סיביות. השאיפה כיום היא להגיע למהירויות של 10Gbps.
מראה רשת פייסטל בסיסית. הסימן \oplus מייצג XOR ו-F היא טרנספורמציה כלשהי שהיא הליבה של הצופן, שילוב של מספר פעולות אלגבריות ופעולות אי-לינאריות
  • גמישות. גמישות נמדדת ביכולת להתאימו למגוון רמות של ביטחון או מגוון אופני שימוש. כמו שימוש במפתח הצפנה קטן יותר, או הרתמתו לצורך פונקציית גיבוב או קוד אימות מסרים.
  • פשטות וקלות ניתוח. האלגוריתם צריך להיות פשוט וקל להבנה באופן שמאפשר ניתוח ובדיקה על ידי מיטב המומחים. למשל אחת הטכניקות הידועות לניתוח צופן בלוקים היא בדיקה של מידת הביטחון שלו עם מספר מצומצם של סבבים, פחות ממה שהצהירו המפתחים. בדרך זו קל יותר לאמוד את חוסנו כמו גם לגלות פרצות ונקודות חולשה.
  • זכויות יוצרים ופטנטים. זכויות יוצרים לעתים מעכבים או מונעים תיקנון הצופן בקנה מידה גדול. גופי תקינה מעדיפים בדרך כלל אלגוריתמים חופשיים.

רשת פייסטל[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – רשת פייסטל

רשת פייסטל היא מבנה בסיסי של צופן בלוקים הקרוי על שם ממציאו הורסט פייסטל. זהו מבנה חסכוני שממיר טרנספורמציה F כלשהי שאינה בהכרח הפיכה, או סט של טרנספורמציות המאוגדים יחד בכינוי F-box לפרמוטציה. כלומר שההצפנה תהיה הפיכה ופענוח יתאפשר בהפעלת אותה פונקציה בשינוי סדר הבתים במפתח בלבד ולא יהיה צורך בפונקציית פענוח נפרדת. רשת פייסטל מחלקת את בלוק הטקסט הקריא לשני חצאים, מפעילה את הפונקציה F על מחצית אחת ואז שתי המחציות מחליפות מקומות, דהיינו פלט צד ימין הופך לקלט צד שמאל וחוזר חלילה, עד להשלמת כל הסבבים. רשת פייסטל נמצאת בשימוש בצפני בלוקים אחדים, ביניהם DES, Twofish, MARS והיא פופולרית בשל הפשטות וקלות היישום.

קיימות מספר וריאציות של רשת פייסטל, ביניהן כאלו שמבוצעות עם ארבעה או יותר חלקים, כאשר בכל סבב חלקם עוברים טרנספורמציה בהתאם לאחרים ולאחר מכן מחליפים מקומות בסדר מסוים (כמו בצופן MARS). רשת פייסטל הבסיסית (כמתואר בתרשים) היא; בהינתן פונקציה F ומפתח הצפנה מחולק לתת-מפתחות K_0,K_1,...,K_n, בלוק הקלט המיועד להצפנה M מחולק לשני חצאים L_0,R_0 ואז:

L_{i+1}=R_i
R_{i+1}=L_i\oplus F_{K_i}(R_i)
מראה רשת החלפה תמורה, S_i מייצגים תיבות החלפה (מפורטים בהמשך), P היא תיבת תמורה (permutation)

פלט הצופן יהיה L_{n+1},R_{n+1} והפענוח מתבצע בסדר הפוך הקלט הוא L_{n+1},R_{n+1} והפונקציה מתחילה מ-i=n ויורדת עד i=0 כשבכל שלב:

R_i=L_{i+1}
L_{i}=R_{i+1}\oplus F_{K_i}(L_{i+1})

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

רשת החלפה תמורה[עריכת קוד מקור | עריכה]

רשת החלפה-תמורה (substitution-permutation networks) היא מבנה בסיסי של צופן בלוקים (כמו ב-AES). בניגוד לרשת פייסטל, הפונקציה הפנימית מבוצעת על כל סיביות הקלט באופן אחיד וכן היא חייבת להיות הפיכה כדי שהפענוח יתאפשר. רשת החלפה-תמורה בקיצור SPN מקבלת בלוק מידע וחלק ממפתח ההצפנה ומבצעת מספר טרנספורמציות על סיביות הבלוק שנקראות 'מצב' (state) במספר סבבים. שילוב פונקציה אי-לינארית חיוני במבנה כזה, היות שהפונקציה הפנימית הפיכה. מלבד זאת צריך להשקיע מחשבה בתכנון הפונקציה האי-לינארית כדי שתהדוף התקפה דיפרנציאלית. הטרנספורמציות כוללות בדרך כלל שכבות של פונקציות החלפה, פונקציות תמורה, פונקציות אי-לינאריות ופונקציית חיבור מפתח.

רשת אינוולוציה[עריכת קוד מקור | עריכה]

מבנה רשת אינוולוציה של צופן IDEA כאשר MA הוא קיצור של Multiplication-Addition זהו ליבת הצופן המורכבת שילוב פעולות כפל וחיבור בשדות אלגבריים שונים

רשת אינוולוציה שנקראת גם 'מבנה ליי מסי' על שם מפתחי צופן IDEA היא רשת הצפנה הדומה לרשת פייסטל. הקלט מחולק לשני חצאים ובכל סבב לאחר הפעלת הפונקציה הפנימית שנקראת כאן בקיצור MA הצדדים מחליפים מקומות. הפונקציה MA (כמתואר בתרשים) שהוא שילוב של פעולות בחבורות אלגבריות שונות, שאין ביניהן דיסטריבוטיביות או אסוציאטיביות. הפעולות הן כפל מודולו 2^{16}+1 המסומן בקיצור \odot וחיבור בשלמים מודולו 2^{16} המסומן בקיצור \boxplus בשילוב עם XOR המסומן ב-\oplus. למשל אפשר לראות שאם מציבים a=b=c=1 בשתי המשוואות הבאות החוקים האמורים אינם מתקיימים:

a\boxplus (b \odot c)\ne (a\boxplus b)\odot (a\boxplus c)
a\boxplus (b \oplus c) \ne (a\boxplus b)\oplus c

שילוב נפוץ אחר של פעולות אלגבריות בשדות סופיים ייושם בצופן Salsa20 והוא שילוב של שלושת הפעולות; חיבור מודולו שלם כלשהו, הזזה מעגלית (cyclic shift) ו-XOR, המבוצעות לפי סדר הנקרא בקיצור ARX דהיינו "או-מוציא של חיבור לאחר הזזה מעגלית". מבנה זה הוכח כבטוח כנגד התקפה דיפרנציאלית וכן עמיד כנגד התקפת תזמון.

תיבות החלפה[עריכת קוד מקור | עריכה]

תיבות החלפה (substitution box) בקיצור s-box הן אוסף של פונקציות אי-לינאריות שתפקידן לפי התאוריה של שאנון להוסיף ערבוב (confusion), כך שהקשר בין המפתח לבין הטקסט המוצפן יהיה קלוש ככל האפשר. תיבות ההחלפה ניתנות ליישום בטבלאות בדרך כלל קבועות כמו ב-DES כלומר שערכיהן מקודדים מראש, אך יכולות להיות דינאמיות כמו בצופן Blowfish. תיבות החלפה מופיעות כמעט בכל צופן מודרני והן מהוות מרכיב אי-לינארי חשוב שמחזק את הצופן, למשל לולא תיבות ההחלפה היה ניתן לפרוץ את DES בקלות.

בחירת ערכי תיבות ההחלפה היא נושא מורכב. אין שיטה מוכחת לבחירת ערכים אופטימליים המניבים אי-לינאריות מקסימלית ובדרך כלל הערכים נבחרים אמפירית (ראו סרפנט). ידוע שבפיתוח DES נעשו על ידי NSA שינויים בערכי תיבות ההחלפה מסיבות לא ידועות. על כל פנים יש עדויות שמפתחי DES היו מודעים לקריפטואנלטיזה דיפרנציאלית שהייתה באותה עת סוד לאומי ויש אף כאלו שטוענים שהשינויים שנעשו בתיבות ההחלפה של DES נועדו להחלישו במכוון.

תיבות ההחלפה הן מערך חד-ממדי או דו-ממדי של מספרים שלמים בגודל מסוים, הגודל בסיביות נקבע בשלב התכנון. בהינתן הקלט x בגודל המתאים ההחלפה מתבצעת פשוט על ידי החזרת הערך המצוי בכניסה x בטבלה, כלומר הקלט עצמו משמש אינדקס לערך המתאים בטבלה. במקרה של טבלה דו-ממדית m\times n החיפוש מתבצע על ידי שני ערכים i,j כאשר אחד מייצג את מספר העמודה והשני את מספר השורה. תיבת ההחלפה נקראת גם טבלת חיפוש (lookup table), למרות השימוש במילה חיפוש, איחזור ערך מהטבלה מתבצע בזמן קבוע והוא יעיל במונחי מחשוב.

דוגמה לפעולת החלפה עם חלק מתיבות ההחלפה של AES

לדוגמה צופן ריינדל משתמש בטבלת החלפה בגודל 16\times 16 כניסות, כל כניסה מכילה בית אחד (שהוא ערך בטווח 0-255). למען הנוחות הבתים מיוצגים בבסיס הקסדצימלי, כך ששני הניבלים (חצאי בתים) בכל כניסה מיוצגים על ידי שתי ספרות הקסדצימליות. לביצוע ההחלפה הקלט שהוא בגודל בית אחד מחולק לשני חצאים, הניבל המשמעותי (הגבוה) משמש כאינדקס לשורה והשני לעמודה. בתרשים מופיע חלק מטבלת ההחלפה של AES. אם למשל הקלט הוא \text{0x31} הפלט יהיה הערך שבשורה 3 בעמודה 1 שהוא \text{0xc7}. אפשר להציג זאת כפונקציה S(\text{0x31})=\text{0xc7} או b_{i,j}=S(a_{i,j}) כאשר i,j הם האינדקסים לשורה והעמודה בהתאמה.

תיבות תמורה[עריכת קוד מקור | עריכה]

תיבות תמורה (permutation box) בקיצור p-box, דומות לתיבות החלפה ובדרך כלל משמשות ככלי עזר להן ומטרתן השגת פיזור (diffusion). הן למעשה אוסף של פרמוטציות שתפקידן לפזר את סיביות הקלט על פני כל תיבות ההחלפה במידה שווה ככל האפשר. כאשר מספר סיביות הקלט גדול או נמוך ממספר סיביות הפלט, לתיבות התמורה תכונה נוספת כמרחיבות ומכווצות את הקלט. מסיבה זו הן נקראות לעתים גם compression-box.

מצבי הפעלה[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – מצב הפעלה של צופן בלוקים

צופן בלוקים בהגדרה נועד להבטחת סודיות של בלוק בגודל קבוע. אך בדרך כלל המידע המיועד להצפנה עולה עשרת מונים על גודל הבלוק. לכן יש צורך לחלקו לבלוקים בגודל המתאים והלצפינם בזה אחר זה. היות שצופן בלוקים דטרמיניסטי באופיו במובן שהפעלת פונקציית ההצפנה על בלוק נתון פעם נוספת עם מפתח זהה תניב בלוק צופן זהה. במקרים מסוימים עובדה זו עלולה להוות נקודת תורפה, כיוון שמידע על שכיחות בלוקים זהים עשוי לעזור למתקיף הצופן בחשיפת מידע אודות המערכת. כדי להתגבר על חיסרון זה מיישמים את הצופן במה שקרוי סגנון הפעלה (Modes of operation) בטוח. השיטה הפשוטה ביותר היא פיצול מסר גדול לחלקים נפרדים, כל אחד בגודל הבלוק והצפנתם בנפרד ללא תלות זה בזה. שיטה זו נקראת electronic codebook. למעט מקרים ספציפיים היא אינה מומלצת לשימוש כיוון שניתן להבחין בבלוקים זהים. צופן זרם אינו סובל מבעיה זו כיוון שהוא מכיל 'זיכרון', כלומר כל יחידת מידע מוצפנת בהיתבסס על מצב פנימי המורכב מתוצאה של הצפנת יחידה קודמת. אפשר לדמות התנהגות צופן זרם גם בצופן בלוקים כך שכל בלוק מוצפן עם מפתח אחר, גם אם יוצפנו שני בלוקים זהים התוצאה תהיה שונה. בשילוב עם וקטור אתחול אפשר להצפין כמויות גדולות של מידע באופן כזה שלעולם לא יוצפנו שני בלוקים זהים עם מפתח זהה, תופעה זו נקראת הצפנה היסתברותית. השיטות הבסיסיות שעונות להגדרה זו כוללות את CBC ,CFB ,OFB ו-CTR. בשיטות אילו שמים דגש בעיקר על ביטחון ההצפנה והתאוששות במצב של שגיאת שידור אך אינן מספקות הגנה מפני שינוי זדוני מה שקרוי אימות והבטחת שלמות. קיימות שיטות המספקות גם הבטחת שלמות בשילוב קוד אימות מסרים ביניהן ניתן למנות את: OCB,EAX,CWC וכן CCM ו-GCM.

קריפטואנליזה[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – קריפטואנליזה

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

  • קריפטאנליזה דיפרנציאלית היא שיטת אנליזה שעוסקת בניתוח ההשפעה של שינויים בקלט פונקציה קריפטוגרפית על הפלט שלה. מטרתה היא למצוא היכן הצופן מתנהג בצורה שאינה אקראית וכך לגלות את המפתח. הקריפטואנליזה הדיפרנציאלית פותחה ב-1993 על ידי אלי ביהם ועדי שמיר[4]. צפנים מודרניים בדרך כלל עמידים כנגד התקפה זו, בשלבי הפיתוח מוודים שהצופן לא מכיל מה שקרוי דפירנציאלים בעלי הסתברות גבוהה.
  • קריפטואנליזה אינטגרלית היא התקפה שמתאימה במיוחד כנגד צופן בלוקים במבנה רשת החלפה-תמורה, בדומה לקריפטואנליזה דיפרנציאלית בשיטה זו בוחנים את תוצאת חיבור XOR של קבוצות של טקסטים גלויים כאשר חלקם קבועים וחלקם משתנים רק בבתים מסוימים שנקראים 'בתים פעילים'. השיטה יושמה לראשונה על ידי לרס קנודסן בהתקפה שנכללה בתיאור הצופן SQUARE‏[5] שמהווה בסיס לצופן AES. וכן יושמה בוריאציות שונות כנגד צפנים אחרים כמו Twofish.
  • slide attack שפותחה ב-1999 על ידי אלקס בריוקוב[6] ויושמה נגד Blowfish. ההתקפה מתמקדת במפתח ההצפנה ומאתגרת את ההנחה שכל צופן חלש ניתן לחיזוק על ידי מספר מרובה של סבבים.
  • התקפת בומרנג היא התקפה שמבוססת על אנליזה דיפרנציאלית שפותחה ב-1999 על ידי דויד וגנר[7]. ההתקפה סותרת את ההנחה שאם הצופן אינו מכיל דיפרנציאלים בעלי הסתברות גבוהה הוא בטוח לפחות כנגד התקפה דיפרנציאלית. וראציות של ההתקפה נוסו בהצלחה על צפנים שונים. בכל אופן חמשת האלגוריתמים שעברו את מבחן תקן ההצפנה החדש אינם מושפעים באופן משמעותי מהתקפה זו.

ביטחון[עריכת קוד מקור | עריכה]

בעקרון קשה לתת הגדרה פורמלית לביטחון צופן בלוקים. המודל המקובל של ביטחון מוכח נקרא ביטחון סמנטי והוא משתמש במושג שנקרא 'אי-יכולת הבחנה', דהיינו צופן הבלוקים יהיה בטוח אם היריב לא יוכל להבחין בהסתברות גבוהה מחצי, בין תוצאת הצפנה עם מפתח הצפנה סודי כלשהו לבין פרמוטציה אקראית אמיתית, במקרה כזה הצופן ייקרא PRP-בטוח (קיצור של pseudo-random permutaion). ההנחה היא שהטקסט המוצפן אקראי וכן המפתח נבחר באקראי מתוך מרחב המפתחות המקסימלי בהסתברות שווה, או לפחות נראה כאקראי מבחינה חישובית מה שקרוי פסאודו-אקראי. אפשר להציג זאת באמצעות משחק כדלהלן, נניח ש-E הוא צופן בלוקים שאת ביטחונו אנחנו מעוניינים לבדוק. לצורך המשחק נתון אורקל שמסוגל לבחור מפתח הצפנה אקראי כלשהו ולהצפין כל מסר שיתבקש, הוא יכול לשדר את תוצאת ההצפנה אך אסור לו לחשוף את המפתח. היריב שולח מסר כלשהו m לאורקל שפועל כדלהלן; מטיל מטבע ובמקרה שמתקבל עץ, מחזיר ליריב את תוצאת ההצפנה של m באמצעות E עם מפתח אקראי כלשהו שהוא בחר. אם מתקבל פלי הוא מחזיר תמורה אקראית כלשהי. תפקידו של היריב היא לנחש האם הערך שקיבל מהאורקל הוא תוצאה של הצפנת m ששלח קודם לכן או מספר אקראי לא מעניין. במילים אחרות עליו לנחש מה הייתה תוצאת הטלת המטבע. היריב יצליח בהתקפה אם ינחש נכונה בשיעור העולה על 50% במידה ניכרת או כפי שמקובל לקרוא לזה בשיעור 'בלתי זניח' לפי פונקציית זניחות כלשהי שנהוג לסמנה \epsilon. קיימים מספר מודלים של ביטחון המבוססים על עיקרון זה. במודלים מסוימים מוקנה ליריב כוח רב יותר, כאשר באפשרותו לבחור את הטקסטים אותם הוא מעוניין להצפין, במילים אחרות בידיו זוגות של טקסט-מקורי וטקסט-מוצפן מתאים ומשימתו לגלות את מפתח ההצפנה. בגרסאות חלשות יותר ההתקפה נקראת פסיבית במובן שהתוקף יכול רק לראות טקסט מוצפן אך לא את מקורו.

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

Tweakable Block Cipher[עריכת קוד מקור | עריכה]

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

דוגמאות[עריכת קוד מקור | עריכה]

במרוצת השנים פותחו צפני בלוקים רבים, מהם בטוחים יותר מהם פחות. ראוי לציין את DES שהוא אבן דרך ונקודת ציון חשובה בהתפתחות צופן הבלוקים המודרני. למרות שאינו בטוח כיום לשימוש בשל מפתח ההצפנה הקצר, הצופן היה בשימוש מאסיבי ועדיין קיים בשימוש מוגבל בגרסת DES משולש וכן היה לתקן ההצפנה הרשמי הראשון של ממשלת ארצות הברית עד שנת 2001. מספר ניסיונות נעשו כדי להחליפו בהם אפשר למנות את IDEA שפותח ב-1991, RC5 של רונלד ריבסט ו-Blowfish של ברוס שנייר. תקן ההצפנה המתקדם שהחליף את DES הפך לצופן הפופולרי ביותר כיום והוא בשימוש במרבית מערכות האבטחה המודרניות. למעשה יתר המועמדים המובילים לתקן המתקדם (סרפנט, MARS, Twofish ו-RC6) שלא נבחרו לבסוף, הוערכו כבטוחים לשימוש.

שימושים[עריכת קוד מקור | עריכה]

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

  • צופן זרם. מצבי הפעלה שונים של צופן בלוקים מדמים צופן זרם כמו OCB או CBC. יתרה מזו צופן בלוקים יכול לשמש מרכיב בסיסי בצופן זרם כמו צופן סרפנט שמהווה מחלק אינטגרלי מ-SOSEMANUK.
  • פונקציית גיבוב קריפטוגרפית. ישנן דרכים בטוחות להפיכת צופן בלוקים לפונקציית גיבוב קריפטוגרפית תחת הנחות סטנדרטיות בשל התכונה המובנית של צופן בלוקים שהוא חד-כיווני. בהינתן טקסט מוצפן קשה לנחש את הטקסט המקורי או את המפתח. אולם צופן בלוקים הוא רק חצי חד-כיווני כיוון שאם ידוע המפתח אפשר לשחזר את הטקסט המקורי. מה שדורש פעולות נוספות כדי להבטיח חד-כיווניות מלאה. מסיבה זו ניצול צופן בלוקים לצורך פונקציית גיבוב איטי בהשוואה לפונקציית גיבוב ייעודית.
  • מחולל פסאודו-אקראי קריפטוגרפי. באופן דומה אפשר להכין מחולל פסאודו-אקראי המייצר מספרים פסאודו-אקראיים לכל מטרה, בין היתר לצורך מפתחות הצפנה. תקן NIST הנקרא SP800-90A מפרט דרך בטוחה לשימוש בצופן בלוקים במצב מונה כדי לחולל מספרים אקראיים‏[8].
  • קוד אימות מסרים. צופן בלוקים מהווה מרכיב בסיסי במספר אלגוריתמים לקוד אימות מסרים. למשל בהצפנה במצב שרשור כמו CBC אפשר להצפין את המסר כולו והתוצאה האחרונה או חלק ממנה מהווה תג אימות. תג האימות מתאים באופן חד חד-ערכי לטקסט המקור, כך שכל שינוי בטקסט המקורי יגרום בסבירות גובהה לשינוי בתג האימות ועל כן יתגלה.
  • הצפנה מאומתת. הצפנה מאומתת מבצעת הצפנה של המסר באמצעות צופן בלוקים בד בבד עם ייצור תג אימות להבטחת שלמותו ואימות מקורו. ההצפנה והאימות מבוצעים באמצעות צופן בלוקים עם מפתחות שונים.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Handbook of applied cryptography
  2. ^ Claud shannon
  3. ^ Matsui, M. and Yamagishi, A. "A new method for known plaintext attack of FEAL cipher". Advances in Cryptology - EUROCRYPT 1992
  4. ^ Eli Biham, Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993
  5. ^ SQUARE
  6. ^ Alex Biryukov and David Wagner (March 1999). "Slide Attacks"
  7. ^ Boomerang
  8. ^ SP800-90A