GCM

Galois/Counter Mode הוא מצב הפעלה של צופן בלוקים שפותח ב-2005 על ידי ג'ון ויגה מחברת Secure Software ודייוויד מקגרו מסיסקו, המשלב צופן סימטרי במצב מונה ופונקציית גיבוב אוניברסלית מעל שדה סופי מורחב, כדי לייצר הצפנה מאומתת עם מידע נלווה המסומנת בקיצור AEAD לפי פרדיגמה של "הצפנה ואז אימות". השיטה מבוססת על רעיון שהוכח כבטוח על ידי בלייר, קיליאן, רוגווי ואחרים ומסתמך גם על ביטחון הצופן הסימטרי שבבסיסו, בהנחה שהוא תמורה פסאודו-אקראית (צופן AES נראה כעונה להגדרה זו, אם כי לא קיימת הוכחה פורמלית). כמו כן GCM יעיל וקל להטמעה בחומרה ומאפשר ביצועים טובים גם בתוכנה, בעיקר אם מנצלים טבלאות אחזור (lookup table). האלגוריתם מצפין את המידע ומייצר טקסט מוצפן ותג אימות מהמידע המוצפן ומידע נלווה נוסף אם קיים, כאשר תג האימות מבטיח מעצם ההגדרה שלא ניתן יהיה לזייף טקסט מוצפן ותג מתאים ללא ידיעת מפתח ההצפנה הסודי המשותף, כך שפונקציית האימות של המקבל תחזיר 'אמת'.
GCM חופשי לשימוש ואינו מעוגן בפטנט או זכויות יוצרים. והוא אומץ על ידי המכון הלאומי לתקנים וטכנולוגיה של ממשלת ארצות הברית בתקן NIST SP800-38D להצפנה מאומתת ובתקן IEEE 802.1AE. הוצע ב-RFC 5288 ונכלל בפרוטוקול SSL. הוא פופולרי בשל ביצועיו הטובים, תפוקתו מהמהירות הידועות כיום להצפנה מאומתת (בערך 3.7 cpb על מעבד אינטל 64 ביט).

פענוח ואימות

אלגוריתם הפענוח המאומת מקבל את  ומפיק את הטקסט המקורי  או סימן מיוחד "FAIL" המציין שהאימות נכשל, אם הייתה שגיאה. לפי הגדרת האלגוריתם, הפענוח המאומת יחזיר את  רק אם הערכים חושבו על ידי פונקציית ההצפנה המאומתת של GCM. במידה שאחד מהם שונה אפילו במעט, בסיכוי גבוה מאוד אלגוריתם הפענוח יחזיר הודעת שגיאה. כאשר אז המשמעות היא שאחד הערכים שגוי בגלל תקלה או בשל שינוי זדוני. המידע הנלווה  משמש כמידע תפעולי ועשוי להכיל כתובות IP, פורטים, מספרי גרסאות וכיוצא בזה. אילו בדרך כלל מהווים חלק מהכותר הנלווה למידע כדי לאפשר למערכת בצד השני לטפל בו בצורה נכונה, לכן אמור להיות במצב גלוי. הפרוטוקול מאפשר לאמת ולהבטיח את שלמות המידע הנלווה כדי להגן על סודיות המידע המוצפן מפני התקפת מוצפן-נבחר.
המטרה העיקרית של ה- שנקרא גם Nonce היא לספק ערך ייחודי וחד פעמי שנדרש בכל פעם שמפעילים את האלגוריתם עם מפתח  נתון. ה- אינו חייב להיות סודי ויכול להיות מספר אקראי או נומרטור כלשהו שצריך להיות ידוע גם לצד המקבל, המגבלה היחידה היא שלא יחזור על עצמו עם מפתח נתון. ב-GCM וקטור האתחול מאומת. אם  מכיל 0 בתים, ו- מכיל בתים כלשהם, אזי למעשה מתקבל אימות של  בלבד. והיות ש- נותר גלוי, במקרה זה GCM מתנהג כקוד אימות מסרים ללא הצפנה. זאת ללא שינוי באלגוריתם. לצורך ההבחנה מסמנים מקרה זה כ-GMAC. הערך  צריך להיות לפחות 64 כדי לקבל רמת ביטחון מינימלי של . לטענת המפתחים התקפה על GCM של חיפוש רנדומלי של תגים עד שנמצא זיוף, תצליח בהסתברות של  כאשר  הוא מספר הבלוקים שהוצפנו. לכן אפקטיבית חוזק התג הוא בסדר גודל של  סיביות. מסיבה זו לא מומלץ להצפין עם מפתח נתון יותר מ- בתים.

תיאור האלגוריתם

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

ביטחון ויעילות

GCM בנוי לפי פרדיגמה של הצפנה מאומתת שנקראת "הצפנה ואז אימות" (encrypt-then-authenticate) שידועה בביטחון שהיא מספקת, בתנאי שהמרכיבים הבסיסיים כמו הצופן הסימטרי ופונקציית הגיבוב בטוחים. ההעדפה של מצב מונה נובעת מתכונת המקביליות ומהפשטות שלו. וניצול כפל פולינומים מעל השדה המורחב  נובע גם בשל תכונת האקראיות המוכחת ובשל היעילות במימוש במיוחד בחומרה. פחות מעגלים ופחות עיכובים בצינור עיבוד נתונים. הפולינום של השדה נבחר באופן שיכיל משקל נמוך (מספר סיביות אחד נמוך) והוא נלקח מטבלה של גדיאל סרוסי מהטכניון. לצורך האלגוריתם נדרש רק מפתח הצפנה יחיד, בעוד שמפתח פונקציית האימות נגזר ממנו. השימוש בכפל פולינומים מעל שדה בינארי מורחב, הוכח כבטוח נגד התקפת גלוי-נבחר על ידי בלייר, קיליאן, רוגווי ואחרים. השימוש בפונקציית גיבוב 'אוניברסלית' להבטחת שלמות ואימות כמו בקוד אימות מסרים הוכח כבטוח על ידי ווגמן וקרטר. מצב מונה שהועלה לראשונה על ידי דיפי והלמן ב-1979 הוכח על ידם כיעיל ובטוח. לפי הצהרת המפתחים תפוקת האלגוריתם עם זיכרון של 256 בתים עומדת על כ-90 מחזורי שעון לבית בממוצע. וכן הסיכויים להתקפה מוצלחת כנגד מנגנון האימות הם בהסתברות של .
ניילס פרגוסון (ממפתחי אלגוריתם Twofish) גילה שתי חולשות במנגנון האימות של GCM כאשר משתמשים בתג אימות קצר כמו 32 או 8 סיביות, בנוסף להערות טכניות לגבי התכנון של GCM. הבעיה הראשונה שהעלה מראה שאפשר להעלות את הסיכויים לזיוף מוצלח לכדי חצי ממה שצפוי, לדוגמה עבור תג אימות בגודל 32 סיביות הסיכויים הם , שזה גבוה במידה ניכרת ממה שהצהירו המפתחים. הסיבה לבעיה אינה GHASH עצמה כיוון שהפונקציה מוכחת כחד כיוונית והתנגשויות הן בהסתברות של  עבור  בלוקים. הסיבה לנקודת התורפה נעוצה בעובדה שתוצאת GHASH מוצפנת על ידי המפתח באמצעות XOR שכידוע אינו מגן מפני מניפולציה של סיביות הפלט (כלומר קלט עם סיבית שגויה אחת ישפיע רק על הסיבית המקבילה בפלט, זוהי פרצה שמאפשרת התקפה כאשר ידוע איזו סיבית שגויה). אבל הבעיה היותר חמורה היא שבעקבות זיוף מוצלח אחד ניתן להגביר את הסיכויים לחשיפת סיביות אחרות של מפתח האימות  עד כדי חשיפת המפתח כולו אחרי מספר ניסיונות די קצר. ההמלצה שלו היא להשתמש בתג אימות באורך 128 סיביות ולא פחות או במנגנון אימות אחר. אם למשל משנים את GCM כך שלפני XOR עם המפתח מצפינים את התוצאה באמצעות צופן הבלוקים נראה שהבעיה תפתר על חשבון יעילות.
כמו כן מעלה נילס פרגוסון כמה מגבלות ראויות לציון בתכנון GCM. העובדה שאורך המסר המאומת הוגבל ל- שזה יחסית קצר וכן העובדה שהאלגוריתם אינו מגביל את אורך המסר לגבולות בתים מה שעלול ליצור בעיות תאימות וכן העובדה שבמצב אופטימלי נדרשות טבלאות גדולות כדי להגיע לביצועים גבוהים, מה שלטענתו אינו מעשי.