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

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

ביטחון

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

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

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

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

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

היסטוריה

רעיון אימות מסרים עלה לראשונה ב-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 בטוחה.

CMAC/OMAC

דרך אחרת שפותרת מהצורך להוסיף 'בלוק-דמה', נקראת OMAC קיצור של One key MAC או CMAC (קיצור של Cipher based MAC). היא מבוססת על CBC-MAC, פועלת עם שלושה מפתחות ומתחלקת לשני סוגים OMAC1 ו-OMAC2. תחילה מצפינים את כל הבלוקים עם המפתח הראשון בשיטת CBC, בסוף התהליך אם אורך המסר הוא כפולה של גודל הבלוק מצפינים את התוצאה האחרונה עם המפתח השני, אם לא, מצפינים עם המפתח השלישי והתוצאה של ההצפנה האחרונה תהיה התג (ראה תרשים). כאן שני המפתחות הנוספים הם פונקציה של המפתח הראשון (שהיא פונקציה אקראית 'אוניברסלית' באמצעות חישוב כפל מודולרי בפולינומים). בגרסת OMAC1 תחילה מחשבים את , דהיינו הצפנה של מחרוזת אפסים באורך  באמצעות המפתח הראשון ואז המפתח השני הוא  (הסימן  הוא הזזה לשמאל של כל הסיביות פוזיציה אחת, כשהסיבית השמאלית ביותר נפלטת) ואם הסיבית הגבוהה (MSB) של המפתח היא '1' מחסרים מהתוצאה באמצעות XOR את הקבוע  (התחילית  מייצגת בסיס הקסדצימלי כנהוג בשפת C). באופן דומה מחשבים את המפתח השלישי: , ושוב אם הסיבית הגבוהה היא '1' מבצעים XOR עם אותו קבוע. גרסת OMAC2 שונה במעט, המפתח השלישי הוא  והוא מחושב על ידי הזזה לימין במקום לשמאל וחיבור XOR מותנה עם הפולינום הקבוע .
אלגוריתם CMAC שנקרא בתחילה XCBC, פותח על ידי בלאק ורוגווי (Black & Rogaway) במיוחד כדי להתגבר על החסרון העיקרי באלגוריתם אימות מסרים מבוסס CBC-MAC (הבטוח לשימוש רק עבור מסרים באורך קבוע). אלגוריתם זה הומלץ על ידי NIST כתקן אימות מסרים SP800-38B במאי 2005.

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

הפעולה המתוארת היא כפל פולינומים מעל שדה בינארי מורחב  כלומר הערך  הוא פולינום עם מקדמים בינאריים (המכיל 128 אפסים למעט 'אחד' בפוזיציה השנייה, או  בייצוג הקסדצימלי). לפי חוקי הכפל בפולינומים הפעולה  מקבילה לכפל ב-2 שזה מסתכם בפעולת הזזה בסיביות שמאלה צעד אחד (Shift left). אם הסיבית הגבוהה של התוצאה היא '1' מתקבל ערך שחורג מהשדה ולכן יש צורך לבצע צמצום מודולרי על ידי חילוק בפולינום אי פריק המייצג את השדה שזהו הקבוע  ונטילת השארית. בגלל הכפל ב-2 הגלישה אינה גדולה לכן אפשר להסתפק בפעולת חיסור אחת שמבוצעת באמצעות XOR אחד בלבד. אפשר להתעלם מהסיבית המשמעותית, כלומר הקבוע  בייצוג הקדסצימלי. באותה דרך מחשבים את  שקול להזזה בסיביות לימין צעד אחד וחיסור מותנה ב-XOR עם הקבוע .

PMAC

גרסת MAC מקבילית שנקראת PMAC (קיצור של Parallelizable MAC) פותחה על ידי בלאק ורוגווי ב-2002 כדי להתגבר על בעיה בקוד אימות CBC שהוא סדרתי באופיו לכן במקרה של צורך בשינוי בלוק אחד, צריך לבצע את כל תהליך החתימה מהתחלה. בנוסף לא ניתן לחלק את הביצוע בין מספר מעבדים באופן מקבילי. PMAC מבצע (ראה תרשים) הצפנה בנפרד של כל בלוק עם המפתח הסודי  בנוסף ל-XOR עם ערך נוסף שהוא פונקציה בשדה סופי המחושבת באופן רקורסיבי כדלהלן: תחילה  (כלומר הצפנת מחרוזת אפסים עם צופן הבלוקים והמפתח הסודי ) ואז בכל שלב  והמפתח להצפנת כל הבלוקים של המסר למעט הבלוק האחרון  הוא  המחושב רקורסיבית:  כאשר . הפונקציה  מייצגת את מספר האפסים המסיימים בערך , לדוגמה  וכן . כל הבלוקים המוצפנים מחוברים ב-XOR ומתקבל . את הבלוק האחרון  מצפינים בדרך שונה התלויה במצב הריפוד, כלומר אם אורך המסר אינו כפולה של גודל הבלוק בדיוק שאז נדרש ריפוד (בשיטה המתוארת לעיל), מתבצע XOR של הבלוק האחרון עם . אם הבלוק האחרון שלם ולא נדרש ריפוד, מבצעים XOR נוסף עם הערך . התג יהיה חלק מתוצאת ההצפנה של .
לצורך מקביליות חלק המערכים שאינם תלויים במסר ניתנים לחישוב מראש. למעט השלב האחרון, כל בלוק מוצפן באופן עצמאי כך שניתן לחלק את העבודה בין מספר יחידות חישוב במקביל.