קוד אימות מסרים

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

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

מבוא והגדרה

תיאור כללי של אלגוריתם אימות מסרים

קוד אימות מסרים נועד לאפשר לשני משתתפים אליס ובוב להתקשר ביניהם בצורה מאומתת. תחילה הם משתפים ביניהם מראש מפתח סודי $k$. כאשר אליס רוצה לשלוח לבוב מסר מאומת $m$ היא מחשבת את "תג האימות" $t$ של המסר $m$ יחד עם המפתח $k$ באמצעות אלגוריתם להכנת תג-אימות הנקרא בקיצור MAC ושולחת לבוב את $m$ ואת $t$. שימו לב ש-$m$ יכול להישלח גלוי או מוצפן. כאשר בוב מקבל את $(m,t)$ הוא משתמש במפתח הסודי המשותף $k$ ואלגוריתם האימות הנקרא כאן בקיצור VERIFY כדי לבדוק האם המסר אותנטי. לסיכום קוד אימות מסרים כולל את השלישייה GEN,‏ MAC,‏ VERIFY לפי הפירוט הבא:

1. הפונקציה GEN מקבלת פרמטר ביטחון $n$ ומפיקה מפתח סודי $k$ כאשר $|k|\geq n$. כמו בהצפנה סימטרית הכוונה כאן שהמפתח $k$ נבחר בהתפלגות אחידה מתוך הטווח המקסימלי, בסימון מקוצר: $k\leftarrow \{0,1\}^{n}$. וכן המפתח צריך להיות משותף לשולח והמקבל, לכן הם צריכים למצוא דרך בטוחה להעבירו מאחד לשני.
2. האלגוריתם MAC מייצר את תג האימות מהמסר והמפתח. הוא מקבל מסר באורך כלשהו $m\in \{0,1\}^{*}$ ואת $k$ ומחזיר את $t\leftarrow {\text{MAC}}_{k}(m)$. כמובן ייתכן שהאלגוריתם הסתברותי. כך שאפילו עבור מסר זהה ומפתח קבוע בכל פעם שמייצרים תג אימות הוא יכול להיות שונה.
3. אלגוריתם האימות VERIFY הוא אלגוריתם דטרמיניסטי שמקבל את $k$, $m$ ואת $t$ ומחזיר את הסיבית $b$ כך: $b={\text{VERIFY}}_{k}(m,t)$. כאשר אם $b=1$ משמעות הדבר שהמסר מאומת כהלכה והוא תקין ואילו אם $b=0$ משמעות הדבר שהמסר אינו תקין וכנראה שונה במהלך ההעברה. לכן יש לדחות אותו ולהפיק הודעת שגיאה מתאימה.

למען השלמות נדרש שיתקיים תמיד ${\text{VERIFY}}_{k}(m,{\text{MAC}}_{k}(m))=1$. וכן אם האלגוריתם מסוגל לאמת רק מסרים באורך נניח $m\in \{0,1\}^{\ell (n)}$ כאשר $\ell (n)$ היא פונקציה של אורך הקלט, אז הוא נקרא קוד אימות מסרים באורך קבוע.

ביטחון

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

התקפת מסר נבחר

הגדרה חזקה יותר של ביטחון אימות מסרים נקראת מודל התקפת מסר-נבחר. במודל זה ההנחה היא שליריב יכולת במידה מוגבלת להשפיע על תוכן המסרים הנשלחים, אם ישירות או בעקיפין. במילים אחרות, מאפשרים לו כביכול לבקש תגי אימות עבור מסרים כלשהם לפי בחירתו. מצב כזה אפשרי לפעמים בעולם האמיתי כגון אם המתקיף הצליח להשיג גישה למדיית האחסון של הקורבן שבתוכה היו קבצים גלויים ותגי אימות מתאימים או למשל במקרה שלמתקיף גישה לשרת אחסון קבצים. מצב זה בא לידי ביטוי באופן תאורטי על ידי "אורקל אימות" שאפשר לחשוב עליו כעל קופסה שחורה. היריב יכול לשלוח לאורקל מסר כלשהו $m$ ולקבל את תג האימות המתאים $t$ אך הוא אינו רשאי לראות את המפתח $k$. תאורטית, שבירה של אלגוריתם האימות היא מצב שבו היריב הצליח להפיק מסר כלשהו $m$ לא בהכרח בעל משמעות כלשהי יחד עם תג האימות המתאים לו, כך שמתקיים ${\text{VERIFY}}_{k}(m,t)=1$, זאת בתנאי שהיריב לא קיבל או ראה קודם לכן את תג האימות של $m$ אחרת ההתקפה תהיה טריוויאלית, כי תמיד היריב יכול להעתיק מסרים ותגי אימות ישנים.

עמידות מפני זיוף קיומי

להלן ניסוי תאורטי שנקרא כאן ${\text{MAC-Forge}}$ המנסח באופן תמציתי את הגדרת עמידות מפני זיוף קיומי תחת מודל התקפת מסר נבחר המתוארת. נתון אלגוריתם לאימות מסרים הכולל את השלישייה $\Pi =({\text{GEN}},{\text{MAC}},{\text{VERIFY}})$ והיריב ${\mathcal {A}}$ שהוא אלגוריתם פולינומי הסתברותי. הניסוי מתבצע כך:

1. תחילה האורקל מריץ את GEN ובוחר מפתח סודי $k$ בהתפלגות אחידה.
2. היריב ${\mathcal {A}}$ רשאי להגיש לאורקל לכל היותר $Q$ שאילתות שבסופן הוא אמור להפיק את הזוג $(m,t)$.
3. תוצאת הניסוי תוגדר כהצלחה אם ${\text{VERIFY}}_{k}(m,t)=1$ וכן $m\notin Q$.

עם הניסוי המתואר אפשר לנסח בצורה רשמית את ההגדרה של ביטחון קוד אימות מסרים. בהינתן השלישייה $\Pi =({\text{GEN}},{\text{MAC}},{\text{VERIFY}})$ האלגוריתם ייקרא בטוח מפני זיוף קיומי תחת מודל מסר-נבחר אם עבור כל אלגוריתם פולינומי הסתברותי ${\mathcal {A}}$ קיימת פונקציית זניחות ${\text{negl}}$ כך שמתקיים:

$\Pr[{\text{MAC-Forge}}_{{\mathcal {A}},\Pi }(n)=1]\leq {\text{negl}}(n)$.

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

אורך התג בסיביות חייב להיות גדול מספיק כדי למנוע ניחוש. אם התג קטן מאוד, תוקף פוטנציאלי יכול לנסות לנחש את התג בכוח גס, ניסוי כל האפשרויות עד שנמצא תג מתאים למסר שהוא מעוניין לזייף, מבלי לדעת את המפתח. בהערכה גסה, אורך התג צריך להיות לפחות 64 סיביות. כך שניחוש באמצעות כוח גס יהיה בסיבוכיות $2^{64}$ ומעלה. פרוטוקול TLS, חלק מאבטחת שכבת התעבורה של האינטרנט, מיישם סכמות אימות מסרים באמצעות מספר פרימיטיבים קריפטוגרפיים (כמו MD5,‏ SHA-1 ו-SHA-2) כדי לייצר תגי אימות באורכים של 32, 64, 96 או 128 סיביות.

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

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

שימושים אפשריים

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

הצפנה מאומתת

ערך מורחב – הצפנה מאומתת

כיוון שצופן בלוקים סימטרי בדרך כלל אינו מספק אימות והבטחת שלמות, פרוטוקולי אבטחה רבים משלבים פונקציית MAC יחד עם אלגוריתם סימטרי כדי ליהנות מיתרונות שניהם. שילוב בין אימות מסרים להצפנה נקרא הצפנה מאומתת (Authenticated encryption) בקיצור AE והיא מקובלת במערכות הצפנה מודרניות. אופן השילוב אפשרי בכמה וריאציות. פרוטוקול TLS משלב אימות עם הצפנה בשיטה שנקראת "אימות והצפנה", תחילה מייצרים תג אימות מהמסר, לאחר מכן משרשרים את התג לטקסט הקריא ומצפינים הכול ביחד ומשדרים במצב מוצפן. פרוטוקול IPSec משלב בשיטה הפוכה כלומר "הצפנה ואימות", תחילה מצפינים את המסר, לאחר מכן מייצרים תג אימות מהטקסט המוצפן, אותו משדרים בגלוי יחד עם הטקסט המוצפן. SSH משתמש בטכניקה אחרת, מייצרים תג אימות מהטקסט הקריא, מצפינים את הטקסט הקריא בלבד ושולחים את הטקסט המוצפן עם התג באופן גלוי. השיטה האחרונה אינה מומלצת.

היסטוריה

רעיון אימות מסרים עלה לראשונה ב-1977 כאשר הציע קמפבל (Campbell) להשתמש ב-DES כבסיס לאלגוריתם אימות מסרים. השם הכולל MAC ניתן בסביבות 1979 במהלך פיתוח תקן ANSI X9.9. אלגוריתמי MAC מיושמים בדרך כלל עם שיטות סימטריות או מפרימיטיבים קריפטוגרפיים אחרים כמו פונקציית גיבוב. קיימים גם אלגוריתמים ייעודיים, ביניהם Message Authenticator Algorithm בקיצור MAA שפותח בשנת 1983 על ידי דוויס וקליידן (Davis & Clayden) לבקשת שירותי הבנק האוטומטיים בבריטניה כחלק מתקן ISO. לאחר שהתגלו בו ליקויים אינו מומלץ כיום. וכן CRC-MAC שהוא אלגוריתם MAC המשתמש בצופן זרם ומבוסס גם על CRC. רעיון השימוש ב-CRC נולד בעקבות רעיון של ווגמן וקרטר (Wegman & Carter) לשלב פנקס חד פעמי ופונקציית גיבוב אקראית 'אוניברסלית' ליצירת אלגוריתם אימות מסרים. שיטה זו מספקת ביטחון מוכח בהנחה שקיימת פונקציית PRF בטוחה.

אלגוריתמים

כל פונקציה פסבדו-אקראית קריפטוגרפית (PRF) מתאימה למימוש אלגוריתם MAC. בניסוח פורמלי אם נתונה פונקציית PRF מסוג $F:K\times X\to Y$, אפשר לבנות סכמת אימות מסרים עם פונקציית החתימה הפועלת כך; $t=F(K,M)$ ופונקציית האימות תהיה זהה כלומר תחזיר אמת רק אם $t=F(K,M)$. אם הפונקציה הפסאודו-אקראית בטוחה, אזי סכמת האימות הזו תהיה בטוחה. למעשה אפשר לבנות קוד אימות מסרים באמצעות כל צופן בלוקים בטוח כמו AES, או פונקציית גיבוב קריפטוגרפית. קיימות שתי שיטות עיקריות:

• קוד אימות מבוסס צופן בלוקים סימטרי (כמו וריאציות של CBC-MAC). נפוץ בעיקר בשימוש בנקאי. נתמך בתקנים X9.9 ו-X9.19 וכן FIPS 186-3.
• קוד אימות מבוסס פונקציית גיבוב קריפטוגרפית (כמו וריאציות של HMAC). נפוץ ביישומי אבטחת אינטרנט כמוTLS, IPSec, SSH וכדומה.

CBC-MAC

תיאור סכמת CBC הסימן $\oplus$ מייצג XOR ו-$E$ היא פונקציית הצפנה מוסכמת כמו AES.

CBC-MAC בגרסה הבסיסית דומה למצב הפעלה CBC של צופן בלוקים (קיצור של Cipher Block Chaining). הרעיון הכללי הוא כדלהלן: נתונה פונקציית הצפנה סימטרית $\ E$ עם מפתח סודי $\ K$ והמסר $\ M$ כשהוא מחולק ל-$t$ בלוקים בגודל קבוע $\ m_{1},m_{2},...,m_{t}$, חישוב התג (כאן $\ H$) נעשה כדלהלן, תחילה: $H_{1}=E_{K}(m_{1})$ ואז עבור $\ 2\leq i\leq t$ מחשבים $\ H_{i}=E_{K}(m_{i}\oplus H_{i-1})$ (אורך בלוק נקבע לפי הצופן שבשימוש, במקרה של AES הוא 128 סיביות). הסימן $\oplus$ מייצג XOR. ותג האימות הוא $H_{t}$. אם אורך המסר לא מתחלק בגודל הבלוק מרפדים באפסים לפי הצורך.

השיטה המתוארת נקראת "raw CBC" והיא אינה בטוחה אם המסרים לחתימה אינם באורך קבוע וידוע מראש. בגלל התקפה שנקראת Extension Attack הרעיון הבסיסי הוא כדלהלן: התוקף משיג מסר $m$ ותג $t$ מתאים כך שמתקיים $E_{k}(m)=t$ ואז טוען שהתג $t$ מתאים למסר $(m\ \|\ t\oplus m)$ והטענה נכונה בשל הזהות הבאה:

$E_{K}(m\ \rVert \ t\oplus m)=E_{K}(E_{K}(m)\oplus (t\oplus m))=E_{K}(t\oplus t\oplus m)=t$,

אפשר לשים לב שכיוון ש-XOR הופכי של עצמו, הופעת $t$ פעמיים מבטלת אחת את השנייה ונותר רק $m$, שעבורו התג תקף. כלומר התוקף הצליח לייצר מסר אחר שהתג $t$ תקף גם עבורו וזה בניגוד להגדרת MAC. (הסימן $\rVert$ מייצג שרשור, כלומר צירוף שתי מחרוזות למחרוזת אחת גדולה). אפשר לפתור את הבעיה על ידי הוספת בלוק המכיל את אורך המסר, את בלוק האורך יש להוסיף בתחילת המסר ולא בסופו ולכן עובדה זו יכולה להוות בעיה מסיבות של יעילות (כאשר אורך המסר אינו ידוע מראש). גרסה אחרת יותר בטוחה נקראת ECBC והיא (כמתואר בתרשים) תוספת הצפנה של התוצאה בסוף התהליך עם מפתח סודי אחר. תוצאת ה-MAC תהיה תוצאת ההצפנה האחרונה, או רק קטע ממנה. הוכח שאם פונקציית ההצפנה היא PRF כך גם חלק ממנה, כל עוד אינו ניתן לניחוש בכוח גס.

הגדרת הביטחון של קוד אימות ECBC המבוסס על פונקציה פסאודו-אקראית היא:

${\mbox{Adv}}[A,F_{\mbox{CBC}}]\leq {\mbox{Adv}}[B,F]+2q^{2}/|X|$

Adv הוא כינוי ל"יתרון", ל-A נתונה פונקציית PRF, ול-$B$ הפונקציה $F$ אקראית אמיתית. $|X|$ מייצג את אורך בלוק בסיביות, $q$ מייצג את מספר השאילתות (או מספר הבלוקים החתומים). הביטוי אומר שה"יתרון" של A לא יהיה גדול משמעותית מהיתרון של B (פלוס טווח שגיאה $2q^{2}/|X|$). בגלל פרדוקס יום הולדת הפונקציה תהיה בטוחה רק אם $q\ll |X|^{1/2}$ במקרה של AES זה אומר שהיא תהיה בטוחה אם $q<2^{64}$, כלומר שלא בוצעה חתימה על $2^{64}$ מסרים עם אותו מפתח.

NMAC

תיאור סכמת NMAC. לאחר שהמסר מחולק ומרופד בהתאם, מצפינים את הבלוקים כך שכל בלוק מוצפן עם מפתח שהוא הטקסט המוצפן שנוצר מהצפנת בלוק קודם (הראשון מוצפן עם המפתח הסודי $K_{1}$). תג האימות יהיה הצפנה של התוצאה האחרונה עם המפתח השני.

הבסיס לקוד אימות HMAC (להלן) נקרא קסקדה (Cascade) או NMAC (קיצור של Nested MAC), פותח ב-1996 על ידי בלייר רן קנטי וקרוציק והוכח כבטוח. הרעיון של NMAC הוא לעשות שימוש בפונקציה חד-כיוונית כמו פונקציית גיבוב עם מפתח או צופן בלוקים כקופסה שחורה באופן שמוליד קוד אימות בטוח. יתרון אחד של שיטה זו שאין תלות בפונקציה ספציפית וניתן להחליפה בכל פונקציה מתאימה אחרת. פונקציית גיבוב בדרך כלל מהירה יותר לכן עדיפה, אולם אינה פועלת עם מפתח, דרך אחת להפוך אותה לפונקציית הצפנה עם מפתח היא להחליף את וקטור האתחול הקבוע בדרך כלל במפתח ההצפנה סודי המשותף לשולח והמקבל. המבנה של NMAC הוא כדלהלן. בהינתן הפונקציה $F_{K}(m)$ ושני מפתחות הצפנה $K_{1},K_{2}$ תג האימות מחושב על ידי:

$tag=F_{K_{2}}(F_{K_{1}}(m))$

הפונקציה הפנימית מיושמת על כל הבלוקים $m_{i}$ בזה אחר זה. כל בלוק מוצפן עם מפתח $k_{i}$ שהוא תוצאה של הצפנת הבלוק הקודם, כאשר $k_{0}$ הוא המפתח הסודי המסופק על ידי המשתמש ו-$k_{i}=F_{k_{i-1}}(m_{i})$. אפשר להחליף את פונקציית הגיבוב בצופן בלוקים $E$ כמתואר בתרשים. תוצאת הפונקציה האחרונה או חלק ממנה היא תג האימות. גם במקרה זה אופן הריפוד זהה וכן כדי שהשיטה תהיה בטוחה ההצפנה האחרונה צריכה להיות עם מפתח אחר, אחרת הסכמה תהיה פגיעה להתקפה המתוארת לעיל. לביטחון נוסף יש המשרשרים ערך ריפוד קבוע כלשהו לפני ההצפנה האחרונה כך: $tag=F_{K_{2}}(F_{K_{1}}(m)\ \|\ pad)$. ביטחון המבנה המתואר נשען על ביטחון הפונקציה הפנימית. ככל שהיא בטוחה, מבנה NMAC בטוח גם הוא, תחת מודלים קריפטוגרפיים סטנדרטיים. כלומר בהתקפת כוח גס ניסיון לזייף את התג שקולה לניסיון לפרוץ צופן הבלוקים או פונקציית הגיבוב שבשימוש. התקפת יום הולדת כנגד פונקציית גיבוב, פחות מעשית במקרה זה כי התג תלוי במפתח סודי.

CMAC/OMAC

תיאור סכמת CMAC הסימן $\oplus$ מייצג XOR ו-$E$ היא פונקציית הצפנה מוסכמת כמו AES.

דרך אחרת שפותרת מהצורך להוסיף 'בלוק-דמה', נקראת OMAC קיצור של One key MAC או CMAC (קיצור של Cipher based MAC). היא מבוססת על CBC-MAC, פועלת עם שלושה מפתחות ומתחלקת לשני סוגים OMAC1 ו-OMAC2. תחילה מצפינים את כל הבלוקים עם המפתח הראשון בשיטת CBC, בסוף התהליך אם אורך המסר הוא כפולה של גודל הבלוק מצפינים את התוצאה האחרונה עם המפתח השני, אם לא, מצפינים עם המפתח השלישי והתוצאה של ההצפנה האחרונה תהיה התג (ראו תרשים). כאן שני המפתחות הנוספים הם פונקציה של המפתח הראשון (שהיא פונקציה אקראית 'אוניברסלית' באמצעות חישוב כפל מודולרי בפולינומים). בגרסת OMAC1 תחילה מחשבים את $L=E_{k}(0^{n})$, דהיינו הצפנה של מחרוזת אפסים באורך $n$ באמצעות המפתח הראשון ואז המפתח השני הוא $L\cdot u=L\ \ll \ 1$ (הסימן $\ll$ הוא הזזה לשמאל של כל הסיביות פוזיציה אחת, כשהסיבית השמאלית ביותר נפלטת) ואם הסיבית הגבוהה (MSB) של המפתח היא '1' מחסרים מהתוצאה באמצעות XOR את הקבוע ${\mbox{0x0...87}}$ (התחילית ${\mbox{0x}}$ מייצגת בסיס הקסדצימלי כנהוג בשפת C). באופן דומה מחשבים את המפתח השלישי: $L\cdot u^{2}=(L\cdot u)\ \ll \ 1$, ושוב אם הסיבית הגבוהה היא '1' מבצעים XOR עם אותו קבוע. גרסת OMAC2 שונה במעט, המפתח השלישי הוא $L\cdot u^{-1}$ והוא מחושב על ידי הזזה לימין במקום לשמאל וחיבור XOR מותנה עם הפולינום הקבוע ${\mbox{0x80...43}}$.

אלגוריתם CMAC שנקרא בתחילה XCBC, פותח על ידי בלאק ורוגווי (Black & Rogaway) במיוחד כדי להתגבר על החיסרון העיקרי באלגוריתם אימות מסרים מבוסס CBC-MAC (הבטוח לשימוש רק עבור מסרים באורך קבוע). אלגוריתם זה הומלץ על ידי NIST כתקן אימות מסרים SP800-38B במאי 2005.

כפל בפולינומים מעל שדה סופי

הפעולה המתוארת היא כפל פולינומים מעל שדה בינארי מורחב $F_{2^{n}}$ כלומר הערך $x$ הוא פולינום עם מקדמים בינאריים (המכיל 128 אפסים למעט 'אחד' בפוזיציה השנייה, או ${\mbox{0x02}}$ בייצוג הקסדצימלי). לפי חוקי הכפל בפולינומים הפעולה $L\cdot x$ מקבילה לכפל ב-2 שזה מסתכם בפעולת הזזה בסיביות שמאלה צעד אחד (Shift left). אם הסיבית הגבוהה של התוצאה היא '1' מתקבל ערך שחורג מהשדה ולכן יש צורך לבצע צמצום מודולרי על ידי חילוק בפולינום אי פריק המייצג את השדה שזהו הקבוע $x^{128}+x^{7}+x^{2}+x+1$ ונטילת השארית. בגלל הכפל ב-2 הגלישה אינה גדולה לכן אפשר להסתפק בפעולת חיסור אחת שמבוצעת באמצעות XOR אחד בלבד. אפשר להתעלם מהסיבית המשמעותית, כלומר הקבוע ${\mbox{0x00..87}}$ בייצוג הקסדצימלי. באותה דרך מחשבים את $L\cdot x^{-1}$ שקול להזזה בסיביות לימין צעד אחד וחיסור מותנה ב-XOR עם הקבוע $x^{127}+x^{5}+x^{3}+x+1$.

PMAC

תיאור סכמת PMAC, הסימן $\oplus$ מייצג XOR ו-$E$ היא פונקציית הצפנה מוסכמת.

גרסת MAC מקבילית שנקראת PMAC (קיצור של Parallelizable MAC) פותחה על ידי בלאק ורוגווי ב-2002 כדי להתגבר על בעיה בקוד אימות CBC שהוא סדרתי באופיו לכן במקרה של צורך בשינוי בלוק אחד, צריך לבצע את כל תהליך החתימה מהתחלה. בנוסף לא ניתן לחלק את הביצוע בין מספר מעבדים באופן מקבילי. PMAC מבצע (ראו תרשים) הצפנה בנפרד של כל בלוק עם המפתח הסודי $K$ בנוסף ל-XOR עם ערך נוסף שהוא פונקציה בשדה סופי המחושבת באופן רקורסיבי כדלהלן: תחילה $L_{0}=E_{K}(0^{n})$ (כלומר הצפנת מחרוזת אפסים עם צופן הבלוקים והמפתח הסודי $K$) ואז בכל שלב $L_{i}=L_{i-1}\cdot x$ והמפתח להצפנת כל הבלוקים של המסר למעט הבלוק האחרון $m_{t}$ הוא $\gamma _{i}\cdot L$ המחושב רקורסיבית: $\gamma _{i}\cdot L=(\gamma _{i-1}\cdot L)\oplus L({\mbox{ntz}}(i))$ כאשר $\gamma _{1}=1$. הפונקציה ${\mbox{ntz}}(i)$ מייצגת את מספר האפסים המסיימים בערך $i$, לדוגמה ${\mbox{ntz}}(7)=0$ וכן ${\mbox{ntz}}(8)=3$. כל הבלוקים המוצפנים מחוברים ב-XOR ומתקבל $\Sigma$. את הבלוק האחרון $m_{t}$ מצפינים בדרך שונה התלויה במצב הריפוד, כלומר אם אורך המסר אינו כפולה של גודל הבלוק בדיוק שאז נדרש ריפוד (בשיטה המתוארת לעיל), מתבצע XOR של הבלוק האחרון עם $\Sigma$. אם הבלוק האחרון שלם ולא נדרש ריפוד, מבצעים XOR נוסף עם הערך $L\cdot x^{-1}$. התג יהיה חלק מתוצאת ההצפנה של $\Sigma$.

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

HMAC

סכמת HMAC

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

$tag=H(K\oplus \ {\mbox{opad}}\ \rVert \ H(K\oplus {\mbox{ipad}}\ \rVert \ M))$

$K$ הוא המפתח הסודי ו-$M$ הוא המסר לאימות, $H$ היא פונקציית הגיבוב המועדפת, הערכים ${\text{ipad}}$ ו-${\text{opad}}$ הם קבועים מוסכמים שאינם סודיים, הנקראים כך בשל אופן שימוש בהם, 'פד פנימי' ו'פד חיצוני' בהתאמה. והסימן $\|$ מייצג שרשור, ביתר פירוט:

1. תחילה מרפדים את המפתח באפסים עד שמקבלים $B$ בתים (64 בתים בדרך כלל).
2. מבצעים חיבור בינארי XOR עם ${\mbox{ipad}}={\mbox{0x363636...}}$ (בגודל $B$ בתים).
3. משרשרים את התוצאה ל-$M$.
4. מחשבים את ערך הגיבוב $H$ של התוצאה משלב 3.
5. מבצעים חיבור בינארי של הבתים משלב 2 עם ${\mbox{opad}}={\mbox{0x5C5C5C...}}$ (באורך $B$ בתים).
6. משרשרים את התוצאה האחרונה עם הערך שהתקבל משלב 4.
7. מחשבים את ערך הגיבוב של התוצאה האחרונה.
8. התג $t$ יהיה חלק מהסיביות של תוצאת הגיבוב האחרונה לפי האורך הרצוי.

UMAC

תיאור הפונקציה הפנימית NH של UMAC בגרסה UMAC-STD-30 ו-UMAC-STD-60

אלגוריתם אימות מסרים UMAC (קיצור של Universal MAC) פותח על ידי בלאק, הלוי, קרייצ'יק, קרובץ ורוגאווי ב-1999 והורחב בשנת 2000. הוא בנוי על פרימיטיבים קריפטוגרפיים ידועים ונחשב לבטוח ומהיר מקודמיו כמו כן האלגוריתם אינו מוגן בזכויות יוצרים כלשהם. אלגוריתם UMAC הוא קוד אימות מסרים בסגנון וואגמן וקרטר המבוסס על משפחת פונקציות הגיבוב NH שהן עצמן פישוט של הפונקציות MMH ו-NMH של הלוי וקרייצ'יק מ-1997. אילו הן פונקציות גיבוב אוניברסליות. פונקציית גיבוב תקרא $\epsilon$-אוניברסלית אם עבור כל זוג מסרים שונים ההסתברות שהגיבוב שלהם יתנגש (שיופק אותו ערך גיבוב עבור שניהם) הוא לכל היותר $\epsilon$. כשההסתברות היא מעל בחירה אקראית של פונקציה מהמשפחה. פונקציית הגיבוב NH בבסיס האלגוריתם פועלת כדלהלן: מתייחסים למסר $M$ כאל רצף של $\ell$ מספרים שלמים, $M=(m_{1},m_{2},...,m_{\ell })$ כאשר כל $m_{i}\in \{0,...,2^{w}-1\}$ מתאים למילה באורך $w$ סיביות (מסיבות של יעילות רצוי ש-$w$ יתאים לגבולות מילה של המעבד, כגון $w=16$ או $w=32$). פונקציה ספציפית היא רצף של $n\geq \ell$ שלמים $K=(k_{1},k_{2},...,k_{n})$ באורך $w$. מחשבים את ${\text{NH}}_{K}(M)$ כך:

$\left(\sum _{i-1}^{\ell /2}((m_{2i-1}+k_{2i-1}){\text{ mod }}2^{w})\cdot ((m_{2i}+k_{2i}){\text{ mod }}2^{w}))\right){\text{ mod }}2^{2w}$

כל החישובים האריתמטיים מותאמים וממוטבים למחשב. הגבול התחתון למציאת התנגשות בפונקציה זו הוא מסדר גודל של $2^{w}$. וכן אין להשתמש ב-$K$ פעמים נוספות.

VMAC

VMAC הוא קוד אימות מסרים מבוסס צופן בלוקים שהוצע ב-2007 על ידי Ted Krovetz ו-Wei Dai. האלגוריתם משתמש בגרסה של פונקציית גיבוב אוניברסלית ועוצב במיוחד לביצועים גבוהים על מעבדי 32 ו-64 ביט. למשל בארכיטקטורת 64 ביט האלגוריתם צורך חצי מחזור שעון לבית קלט אחד (0.5 cpb). פחות מ-5 מחזורי שעון בארכיטקטורת 32 ביט וכ-10 מחזורי שעון לבית במערכות משובצות.

VMAC הוא קוד אימות מסרים סימטרי בסגנון ווגמן וקרטר. הוא משתמש בפונקציית גיבוב אוניברסלית מהירה על קלט $M$ בכל אורך רצוי ומפיק ערך גיבוב קצר ${\text{Tag}}$ שיכול להיות באורך בין 64 סיביות ועד כפולה כלשהי של בלוק הצופן שבשימוש, אותו הוא מצפין על ידי חיבור עם פד פסאודו-אקראי לקבלת תג אימות הסופי של VMAC. השולח והמקבל חייבים לשתף מראש פונקציית גיבוב אקראית סודית $H$ ומחרוזת פסאודו-אקראית אותה מפיקים באמצעות פונקציה פסאודו-אקראית $F$. את התג מחשבים באופן פורמלי על ידי:

${\text{Tag}}=H_{K_{1}}(M)+F_{K_{2}}({\text{nonce}})$.

כאשר המפתחות $K_{1}$ ו-$K_{2}$ הם מפתחות סודיים אקראיים המשותפים לשולח והמקבל. Nonce הוא ערך חד-פעמי (כמו מספר סידורי) לא סודי שחייב גם הוא להגיע לידיעת המקבל. הפונקציה $F$ היא בעצם צופן הבלוקים AES ועבור הפונקציה $H$ האלגוריתם משתמש בווריאציה של פונקציית גיבוב עם מפתח הנקראת VHASH.

ראו גם

• Poly1305
• SipHash

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

• Handbook of Applied Cryptography
• אלגוריתם UMAC
• אימות מסרים עם בטיחות מוכחת