הצפנה מאומתת

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

הצורך בהצפנה מאומתת עולה באופן טבעי לאור העובדה שבדרך כלל צופן בלוקים כמו AES אינו מספק שלמות כלל ומפתחי מערכות נטו בעבר לפתור בעיה זו בדרך של הוספת יתירות כלשהי כמו ריפוד במספר אקראי. התקפות אינטרנט רבות ניצלו את הפרצה הזו כדי לשבור מערכות הצפנה כאלה בקלות, למרות שהצופן הסימטרי היה בטוח. הניסיון מלמד ששילוב הצפנה עם אימות מורכב ומועד לשגיאות. הפרדיגמה המקובלת כיום כדי להבטיח שלמות יחד עם סודיות בדרך נכונה, היא לקחת צופן סימטרי בטוח המספק סודיות בלבד ולשלבו במצב הפעלה CBC או CTR (מונה), עם אלגוריתם אימות מסרים בטוח המספק אימות בלבד. השילוב הזה נחשב בטוח, בוצע בסכמות רבות בין היתר HMAC, UMAC או CBC-MAC והוא בשימוש מעשי נרחב.

קיימות כיום מספר שיטות תיקניות חדשות להצפנה מאומתת ביניהן: OCB 2.0, CCM, EAX, GCM שהוצעו ונבחנו על ידי מומחים ואושרו בתקן איזו ובארגוני תקינה נוספים. וכן IACBC, OCB, XCBC, Helix, CWC. נכון לשנת 2014 מרבית מערכות ההצפנה המודרניות מיישמות הצפנה מאומתת בדרך תיקנית בטוחה להבטחת סודיות ושלמות כאשר הדבר דרוש.

הרכבה גנרית

רעיון אימות מסרים הועלה לראשונה על ידי בלייר ורוגווי ב-1994. המושג מתייחס להבטחת שלמות טקסט-קריא (מסומן INT-PTXT קיצור integrity of plaintext) או שלמות טקסט-מוצפן (שנקרא INT-CTXT קיצור של integrity of ciphertext). בשונה מרעיון הבטחת סודיות בצופן סימטרי, כאן בהגדרה המסר יכול להשאר גלוי ואין כל סודיות. אולם לצורך השוואה מקובל שהגדרה זו מקבילה לרעיון החלש יותר של הבטחת סודיות שנקרא עמידות בפני התקפת גלוי-נבחר המסומנת בקיצור (IND-CPA) הקיצור IND פירושו אי-הבחנה. את הבטחת השלמות דהיינו שהאלגוריתם 'לא ניתן לזיוף' (unforgeable) תחת התקפת מסר-נבחר (CMA) אפשר להגדיר בשני אופנים, ההגדרה החלשה מסומנת WUF-CMA (קיצור של weakly unforgeable) שבה בהינתן הצמד מסר ותג מתאים יהיה קשה מבחינה חישובית למצוא מסר אחר שהתג יהיה תקף עבורו גם אחרי התקפה שבה ביכולתו של התוקף לבקש תגים מתאימים עבור מספר גדול של מסרים כלשהם לפי בחירתו. או בהגדרה החזקה יותר הנקראת SUF-CMA כאשר SUF פירושו strongly unforgeable, שבה באותה התקפה, יהיה קשה מבחינה חישובית ליריב למצוא כל זוג 'מסר/תג' כך שהתג יהיה תקף עבור המסר (גם אם המסר אינו בעל משמעות או שייכות כלשהי, כל עוד התג לא יוצר במקור מאותו מסר). הוכח שכל פונקציה פסאודו-רנדומלית בטוחה יכולה להיות MAC בהגדרה החזקה.

הצפנה מאומתת 'גנרית' פירושה הרכבה של הצפנה סימטרית כקופסה שחורה עם רעיון האימות. כלומר קיימת הפרדה בין האימות להצפנה כך שניתן להשתמש בכל צופן סימטרי בטוח כנגד IND-CPA שהיא הגדרה חלשה יותר לעומת IND-CCA (קיצור של התקפת מוצפן-נבחר), באופן כללי מרבית האלגוריתמים הבטוחים עומדים בהגדרה זו. נניח שפונקציית ההצפנה של הצופן הסימטרי נקראת $E$ והפענוח $D$, פונקציית יצירת תג האימות $T$, פונקציית בדיקת התג $V$ והמסר $M$. מפתח ההצפנה נקרא $K_{e}$ ומפתח האימות נקרא $K_{m}$. ניתן להרכיב הצפנה מאומתת בשלושה האופנים הבאים:

• הצפנה ואימות (Encrypt and MAC): מייצרים תג אימות מהמסר, מצפינים את המסר ומצרפים אליו את התג. לפענוח+אימות, תחילה מפענחים את הטקסט המוצפן, ואז מאמתים את התג. פרוטוקול SSH אימץ גרסה דומה לזו.

בניסוח פורמלי: $E(K_{e},M)\ \|\ T(K_{m},M)$. הסימן $\|$ נקרא 'שרשור' כלומר הדבקת שתי מחרוזות למחרוזת אחת גדולה.

• אימות ולאחריו הצפנה (MAC then Encrypt): תחילה מייצרים תג אימות מהמסר הקריא, מצרפים את תג האימות למסר ומצפינים הכול יחד. לפענוח+אימות, תחילה מפענחים את הטקסט מוצפן ותג האימות ואז מאמתים את התג. פרוטוקול SSL משתמש בוריאציה כזו.

הנוסחה היא: $E(K_{e},M\ \|\ T(K_{m},M))$.

• הצפנה ולאחריה אימות (Encrypt then MAC): מצפינים את המסר, מייצרים תג אימות מהטקסט המוצפן ומצרפים אותו לטקסט המוצפן. לפענוח+אימות, תחילה מאמתים את התג ואז מפענחים. פרוטוקול IPSec משתמש בגרסה כזו.

הנוסחה היא תחילה: $C=E(K_{e},M)$ ואז מחשבים את $C\ \|\ T(K_{m},C)$.

כל אחת מהשיטות מניבה ביטחון שונה בהתאם למודלים של ביטחון שונים. הנחת הבסיס היא שהצופן הסימטרי בטוח לפחות כנגד התקפת גלוי-נבחר בקיצור (CPA) ואלגוריתם האימות אינו ניתן לזיוף לפחות תחת CMA - התקפת מסר-נבחר. הטבלה הבאה פורסמה ב-2007 על ידי Mihir Bellare מאוניברסיטת קליפורניה שנחשב לאחד מהוגי הרעיון ו-Chanathip Namprempre באוניברסיטת תאמאסאט בתאילנד והיא מציגה את הקשר בין הגדרות הבטחת סודיות והבטחת אימות בהתאם למודלים שונים של בטחון. בשתי הטבלאות הבאות "כן" מתייחס לכך שהמבנה הוכח כבטוח תחת ההנחות המתוארות. ו"לא" פירושו שקיים מבנה כזה שאינו עונה על כל הגדרות הבטחון - במקרים מסויימים (לא בכל המקרים).

שיטה || פרטיות || שלמות IND-CPA || IND-CCA || NM-CPA || INT-PTXT || IND-CTXT הצפנה ואימות || לא || לא || לא || כן || לא אימות ואז הצפנה || כן || לא || לא || כן || לא הצפנה ואז אימות || כן || לא || לא || כן || לא

שיטה || פרטיות || שלמות IND-CPA || IND-CCA || NM-CPA || INT-PTXT || IND-CTXT הצפנה ואימות || לא || לא || לא || כן || לא אימות ואז הצפנה || כן || לא || לא || כן || לא הצפנה ואז אימות || כן || כן || כן || כן || כן

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

הרחבות

רוגווי הרחיב את המושג הצפנה מאומתת להגדרה של הצפנה מאומתת עם מידע נלווה (בקיצור AEAD). במודל זה המידע המוצפן מחולק לשני חלקים טקסט-גלוי וכותר (header). השלמות במקרה זה מחוייבת לגבי כל חלקי המידע אך הסודיות לא. מצב כזה מתעורר בעיקר בפרוטוקול העברת מפתח. והבעיה שרוגווי מעלה היא בעיית עטיפת המפתח. כלומר מציאת מנגנון בטוח להעברת המפתח והמידע הנלווה אליו בצורה בטוחה ומאומתת לצד השני. ושהחלק הגלוי במידע לא יסכן את סודיות הפרוטוקול או שלמותו. דרך אחרת להשגת אימות או הבטחת שלימות היא "הצפנה עם יתירות". כלומר ניסיון להשיג אימות על ידי קידוד המידע בדרך כלשהי כמו ריפוד במספר אקראי לפני ההצפנה. על כל פנים מתוך הטבלה עולה שהשיטה שאומצה בפרוטוקול SSH פחות בטוחה מהאחרות.

בטחון

הגדרה קונקרטית של ביטחון סמנטי של הצפנה מאומתת היא על ידי מה שקרוי 'משחק' ו"יתרון" של "יריב" כאשר המושג "בטוח" אינו מוגדר פורמלית בהקשר זה, אלא פירושו שהיתרון של יריב מוגבל במקום ובזמן "זניח" בהתאם לפרמטר כלשהו שנתון לדיון. בצפנים סימטריים כמו AES למשל לא קיימת הגדרה פורמלית. באופן כללי בהקשר של ביטחון סמנטי של צופן סימטרי או אסימטרי המשחק מנוהל בצורה כזו שהיריב מגיש בפני האורקל או מציב האתגר, שאילתות עם זוגות מסרים $M_{0},M_{1}$ באורך שווה ומקבל בחזרה הצפנה של אחד מהמסרים באופן אקראי $M_{b}$ ($b$ הוא תוצאה של הטלת מטבע חדשה בכל שאילתא) ועליו לנחש בעזרת הטקסט המוצפן שקיבל בכל שאילתא, איזה מביניהם הוצפן כלומר: $b$ שווה "0" או "1" (אמת או שקר). היריב יחשב כמנצח אם יצליח בהסתברות גבוהה מחצי באחוז מסויים "שאינו זניח" לנחש נכונה בכל הניסויים שביצע. בניסוח פורמלי ההגדרה תחת מודל CCA או CPA היא:

${\mbox{Adv}}_{SE}^{\mbox{ind-cpa}}(A)=2\cdot \Pr[IND-CPA_{SE}^{A}\Rightarrow 1]-1$

או

${\mbox{Adv}}_{SE}^{\mbox{ind-cca}}(A)=2\cdot \Pr[IND-CCA_{SE}^{A}\Rightarrow 1]-1$

בהקשר של הצפנה מאומתת את רעיון השלמות או האימות אפשר להגדיר בדרך דומה:

${\mbox{Adv}}_{SE}^{\mbox{int-ptxt}}(A)=\Pr[INT-PTXT_{SE}^{A}\Rightarrow 1]$

וכן

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "http://localhost:6011/he.wikipedia.org/v1/":): {\displaystyle \mbox{Adv}_{SE}^{\mbox{int-ctxt}}(A)=\Pr [INT-CTXT_{SE}^A \Rightarrow 1]}

הרעיון של 'אי-זיוף' מוגדר באופן דומה:

${\mbox{Adv}}_{MA}^{\mbox{wuf-cma}}(F)=\Pr[WUF-CMA_{MA}^{F}\Rightarrow 1]$

וכן

${\mbox{Adv}}_{MA}^{\mbox{suf-cma}}(F)=\Pr[SUF-CMA_{MA}^{F}\Rightarrow 1]$

קודי אימות מסרים תיקניים כמו אילו המתוארים לעיל כמו HMAC ,PMAC או UMAC ודומיהם מוגדרים בטוחים SUF-CMA שהיא ההגדרה המחמירה שכוללת גם את WUF-CMA. כמו כן ההגדרה של INT-PTXT חלשה מ-INT-CTXT.

לקריאה נוספת

• Bellare, M.; Namprempre, C. (2000), T. Okamoto (ed.), "Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm", Extended abstract in Advances in Cryptology: Asiacrypt 2000 Proceedings, Lecture Notes in Computer Science, Springer-Verlag, 1976: 531, doi:10.1007/3-540-44448-3_41, ISBN 978-3-540-41404-9