OCB

בקריפטוגרפיה, Offset CodeBook היא משפחה של מצבי הפעלה מקביליים עבור צופן בלוקים המספקים הצפנה מאומתת של מסרים ארוכים. OCB1 פותח ב-2003 על ידי פיליפ רוגווי, מיהיר בלייר אוניברסיטת קליפורניה בסן דייגו וג'ון בלאק מאוניברסיטת קולורדו. OCB הם מצבי הפעלה אלגנטיים, יעילים ובטוחים לפי פרדיגמה של "הצפנה ואחריה אימות" והם שיפור של מצב ההפעלה IAPM שהוצע על ידי Charanjit Jutla. בהתבסס על צופן בלוקים בטוח כמו AES ווקטור אתחול, האלגוריתם מצפין מסר שהוא מחרוזת בינארית ארוכה $M$, תוך הפעלה של צופן הבלוקים $\lceil |M|/n\rceil +2$ פעמים, כאשר $n$ הוא גודל הבלוק שהצופן מקבל (128 סיביות במקרה של AES) תוך חישובי היסט (offset) ותהליך הכנת מפתח מהירים מאוד. ומפיק טקסט מוצפן בליווי תג אימות באורך משתנה לפי הצורך כדי לאמת ולהבטיח את שלמות הטקסט המוצפן. תג האימות מבטיח מעצם ההגדרה שלא ניתן יהיה לזייף טקסט מוצפן עם תג אימות מתאים ללא ידיעת מפתח ההצפנה המשותף לשולח והמקבל, כך שהמקבל לא יבחין בכך. OCB1 הוכח כבטוח כנגד התקפות על שלב הסודיות או האימות בהנחה שצופן הבלוקים מוגדר פרמוטציה פסאודו אקראית (PRP). אולם התגלו בעיות בעמידות בפני התנגשויות, שמגבילות את כמות המידע הניתן להצפנה עם מפתח יחיד. ביישום אופטימלי OCB1 מהיר מאוד ויכול להגיע למהירות של 1.48 CPB על מעבד אינטל 64 ביט (עם AES-NI).

OCB מוגן בפטנט בארצות הברית, השימוש בו כרוך ברישיון מבוסס הרישיון הציבורי הכללי של גנו לשימוש פרטי, בתנאי שאינו משמש לצורך מסחרי או ממשלתי. ב-2013 המפתחים נתנו הסכמתם לרישיון חופשי בקוד פתוח המאושר על ידי OSI. האלגוריתם נכלל ברשימת האלגוריתמים המובילים שמנהל NIST לצורך תקן הצפנה מאומתת. כמו כן מומלץ על ידי IETF.

קובץ:OCB Scheme.png

תרשים לדוגמה של הצפנה מאומתת בשיטת OCB

הצפנה מאומתת

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

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

• אורך מינימלי של טקסט מוצפן בהתחשב באורך הטקסט המקורי. כמו כן אורך המסר לא חייב להיות כפולה של גודל הבלוק שהצופן מקבל.
• הצורך בוקטור אתחול גמיש. צריך להיות שונה בכל פעם שמצפינים מסר חדש עם אותו מפתח אך אינו חייב להיות סודי או אקראי.
• מספר הקריאות לצופן הבלוקים (כאשר המסר ארוך) הוא מינימלי, כמעט אופטימלי.
• יש צורך במפתח הצפנה סודי יחיד כאשר מפתח האימות נגזר ממנו.
• יעילות רבה בחישובי האופסט או הרצף. ההצפנה והפענוח יכולים להתבצע ללא עיכוב גם אם המסר לא הגיע בשלמותו. וכן היכולת לטפל בבלוקים קצרים ביעילות והיכולת לבצע חישוב מקבילי או לחדש תג אימות ביעילות כאשר בוצע שינוי בחלק מהמסר. זאת ללא חישובים אריתמטיים מסובכים.
• תפוקה גבוהה. בניסוי שעשו המפתחים על פנטיום 3 הוכח ש-OCB איטי רק ב-6.5% לעומת הצפנה ישירה ללא אימות. ומהיר פי 54% ממצב הצפנה CBC עם MAC כמו CCM.
• יישום מקבילי בחומרה ייעודית יכול להניב תפוקה של 10 Gbps.
• ביטחון סמנטי מוכח לפי מודל של מיקלי וגולדווסר שנקרא indistinguishability כנגד התקפת גלוי-נבחר יחד עם אימות מוכח לפי מודל של בלייר כץ ויונג. מה שמספק הגנה כנגד ההתקפה החזקה ביותר התקפת מוצפן-נבחר בקיצור CCA שמקביל גם למודל ביטחון מחמיר שנקרא אי-חשילות של דולב ואחרים. מודלים של ביטחון אילו אינם מתקיימים במצבי הפעלה סטנדרטיים כמו PCBC שייושם בפרוטוקול קרברוס.

סימנים מוסכמים

צופן בלוקים המהווה מרכיב פרימיטיבי באלגוריתם הוא פונקציה מהצורה $E:{𝒦}\times \{0,1{\}}^n\to \{0,1{\}}^n$ המסומנת בקיצור $E_K(M)$ כאשר $K$ הוא מפתח ההצפנה ו-$M$ הוא המסר. גודל בלוק שהצופן מסוגל להצפין בריצה אחת הוא $n$ שמומלץ שיהיה לפחות 128 סיביות. ואורך התג מיוצג על ידי $\tau$ ומומלץ שיהיה לפחות 32 סיביות. בפרוטוקול IPSec התקן הוא 96 סיביות.

כל הערכים הם מחרוזות בינאריות והסימן $$\begin{gathered} A \\ \Vert \\ B \end{gathered}$$ מייצג שרשור של $A$ ו-$B$ למחרוזת אחת. המרה של מחרוזת בינארית למספר שלם וההפך היא לפי סדר בתים קטן. הפונקציה $\text{ntz}(i)$ מייצגת את מספר האפסים המסיימים בייצוג הבינארי של המספר $i$ (בספרות הפחות משמעותיות של המספר) למשל $\text{ntz}(7)=0$ וכן $\text{ntz}(8)=3$. הריפוד של $A$ באפסים מיוצג על ידי $$\begin{gathered} A \\ {0}^{*} \end{gathered}$$, למשל המספר 5 בייצוג בינארי הוא $0^{*}101$ הכוכבית מתייחסת למספר האפסים הדרוש כדי להשלימו לגודל בלוק $n$, כלומר אם $n=128$ סיביות המספר 5 בייצוג בינארי מרופד ב-125 אפסים בסיביות המשמעותיות כדי להשלימו לגודל בלוק). הפעולה $A\oplus B$ נקראת XOR. הסימן $A\ll 1$ נקרא הזזה לשמאל (shift left) של סיביות המחרוזת $A$ צעד אחד, הסיבית המשמעותית ביותר נפלטת ואילו הסיבית הראשונה מתאפסת. וכן לגבי $A\gg 1$ בסדר הפוך. כאשר מחלקים את המסר $M$ לבלוקים בגודל $n$ צריך לזכור שמספר הבלוקים צריך להיות לפחות אחד, כך שהמחרוזת הריקה גודלה 1.

פעולות אריתמטיות בשדה $GF(2^n)$

כדי לחשב את האופסט להלן, רואים במחרוזות באורך $n$ הסיביות כפולינומים מעל השדה $\text{GF}(2^n)$, כך שהמקדמים של האלמנט $a(x)=a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0$ הן הסיביות של המספר $a$. למשל בשדה $GF(2^{128})$ אפשר לראות במספר 5 כמחרוזת בינארית $0^{125}101$ או הפולינום $x^2+1$. פעולת החיבור של שני אלמנטים בשדה היא חיבור המקדמים בנפרד מודולו 2 שהיא מקבילה לפעולת XOR. כדי לבצע פעולת כפל בשדה $c(x)=a(x)\cdot b(x)$, יש לבחור תחילה פולינום פרימיטיבי אי-פריק $p(x)$ ממעלה $n$ (שרצוי שיהיה עם מספר מקדמים מינימלי, דהיינו משקל בינארי נמוך) שישמש כמייצג של השדה, כך שכל פעולות הכפל בין שני אלמנטים בשדה צריכות להתבצע מודולו $p(x)$ כדי שהתוצאה תהיה אלמנט בשדה. למשל עבור השדה $\text{GF}(2^{128})$ הפולינום $x^{128}+x^7+x^2+x+1$ מתאים.

אפשר לראות שקל לבצע כפל של כל פולינום $a(x)$ בפולינום $x$ כיוון שהתוצאה

$a(x)\cdot x=a_{n-1}{x}^n+a_{n-2}{x}^{n-1}+\cdots +a_1{x}^2+a_{0}x$

שקולה בעצם להזזת המקדמים שמאלה פוזיציה אחת. כעת אם הסיבית הגבוהה ביותר היא אפס התקבל פולינום ממעלה נמוכה מ-128 והתוצאה נותרת בעצם $a\ll 1$. אך אם הסיבית המשמעותית היא 1 מתקבל פולינום ממעלה גבוהה או שווה ל-128, מה שמחייב לצמצם את הפולינום $a$ מודולו $p(x)$. דהיינו צריך למצוא פולינומים $q$ ו-$r$ המקיימים $a^{128}+a=q\cdot p+r$ ואז לקחת את השארית $r$. קל לפתור את המשוואה האחרונה כאשר $q=1$ כי אחרי העברת אגפים מתקבל $r=a^{128}+a-p$. במילים אחרות צריך לחסר את $p$ מהתוצאה ואפשר להסתפק במקדמים הנמוכים של $p$ כי הסיבית הגבוהה מתבטלת. חיסור אלמנט בשדה זה מתבצע על ידי XOR כי הוא הופכי של עצמו לכן חיבור וחיסור הן פעולות זהות. לסיכום:

$a\cdot x=\{\begin{array}{ll}a\ll 1,& \text{if the first bit of a }=0\\ a\ll 1\oplus 0^{120}10000111,& \text{if the first bit of a }=1\end{array}$

באופן דומה אפשר לבצע חילוק עם ההופכי הכפלי של

$x$

.

$a\cdot x^{-1}=\{\begin{array}{ll}a\gg 1,& \text{if the last bit of a }=0\\ a\gg 1\oplus 10^{120}1000011,& \text{if the last bit of a }=1\end{array}$

כעת אם $L\in \{0,1{\}}^n$ הוא מחרוזת בינארית (או פולינום) הביטוי $L(i)$ עבור $i\ge -1$ הוא סימון מקוצר של הפעולה $L\cdot x^i$. כלומר כפל הפולינום $L$ בחזקות של הפולינום $x$. בעזרת נוסחאות הכפל והחילוק לעיל קל לחשב מתוך $L$ את $L(i-1),L(0),L(1),...,L(\mu )$. עבור $\mu$ קטן. את $L(-1)$ מחשבים על ידי $L\cdot x^{-1}$.

לצורך האופסט בהשאלה מקוד גריי מגדירים את $$\begin{gathered} {\gamma }^l=({\gamma }_0^l \\ {\gamma }_1^l\cdots \\ {\gamma }_{2^l-1}^l) \end{gathered}$$ של מחרוזות באורך $l$ סיביות הנבדלות זו מזו רק בסיבית אחת. כאן נעשה שימוש בקוד גריי קנוני שאותו בונים על ידי חישוב $$\begin{gathered} {\gamma }^1=(0 \\ 1) \end{gathered}$$ ועבור כל $l$ הגדול מ-0:

$$\begin{gathered} {\gamma }^{l+1}=(0{\gamma }_0^l \\ 0{\gamma }_1^l\cdots \\ 0{\gamma }_{2^l-1}^{l}1{\gamma }_{2^l-1}^l \\ 1{\gamma }_{2^l-2}^l\cdots \\ 1{\gamma }_1^l \\ 1{\gamma }_0^l) \end{gathered}$$

הסיבה לבחירה זו היא שלמעשה ${\gamma }_i={\gamma }_{i-1}\oplus (0^{n-1}1\ll \text{ntz}(i))$. שזה XOR עם חזקה של 2 כאשר החזקה היא מספר האפסים המסיימים באינדקס $i$. מה שהופך את המשימה לחישוב נקודות האופסט לקלה במיוחד כי כל שנדרש הוא הזזות ו-XOR בלבד. נקודות ${\gamma }_i$ האמורות שונות זו מזו בסיבית אחת לפחות ושונות מאפס וכן ${\gamma }_i<2i$. תוך שימוש בקוד גריי, במחרוזת $L$ ובמחרוזת $R$ (שיבוארו להלן) מחשבים באופן רקורסיבי את הערכים הבאים:

$$\begin{gathered} {\gamma }_1\cdot L=L\oplus R, \\ {\gamma }_i\cdot L=({\gamma }_{i-1}\cdot L)\oplus L(\text{ntz}(i))\oplus R, \\ i\ge 2 \end{gathered}$$.

כל נקודה מחושבת על ידי XOR של הנקודה הקודמת עם $L(\text{ntz}(i))$. כדי לשלב את וקטור האתחול בתהליך ההכנה תחילה מצפינים אותו עם $L$ ומחברים את התוצאה $R$ עם כל ההיסטים ${\gamma }_i$, כאשר האופסט הראשון הוא $L\oplus R$. כך מבטיחים ייחודיות בכל הצפנה.

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

באלגוריתם הבא, מתייחסים לטקסט המיועד להצפנה כאל מחרוזת סיביות המחולקת ל-$m$ בלוקים. כאשר המסר צריך להיות לפחות $m-1$ בלוקים שלמים בגודל 128 סיביות ובלוק האחרון שיכול להיות בלוק חלקי המרופד באפסים במידת הצורך או שהוא יכול להיות ריק לגמרי. על כל פנים צריך שיהיה לפחות בלוק אחד כך שיתקיים $128m\le |M|$.

הצפנה ואימות

$\mathbf{O}\mathbf{C}\mathbf{B}\mathbf{1}\mathit{.}{\mathbf{E}}_{\mathbf{K}}\mathit{(}\mathit{N},\mathit{M}\mathit{)}$

1. $L=E_K(0^n)$
2. $R=E_K(N\oplus L)$
3. $$\begin{gathered} \text{For }i=1\text{ to }m\text{ do: } \\ Z[i]={\gamma }_i\cdot L\oplus R \end{gathered}$$
4. $$\begin{gathered} \text{For }i=1\text{ to }m-1\text{ do: } \\ C[i]=E_K(M[i]\oplus Z[i]) \end{gathered}$$
5. $X[m]=\text{len}(M[m])\oplus L\cdot x^{-1}\oplus Z[m])$
6. $Y[m]=E_K(X[m])$
7. $C[m]=Y[m]\oplus M[m]$
8. $C=C[1],...,C[m]$
9. $\text{Checksum}=M[1]\oplus \cdots \oplus M[m-1]\oplus C[m]0^{*}\oplus Y[m]$
10. $T=E_K(\text{Checksum}\oplus Z[m])[\text{first }\tau \text{ bits}]$
11. $$\begin{gathered} \text{Return }C \\ \Vert \\ T \end{gathered}$$

פענוח ואימות

$$\begin{gathered} \mathbf{O}\mathbf{C}\mathbf{B}\mathbf{1}\mathit{.}{\mathbf{D}}_{\mathbf{K}}\mathit{(}\mathit{N},\mathit{C} \\ \mathit{\Vert } \\ \mathit{T}\mathit{)} \end{gathered}$$

1. $L=E_K(0^n)$
2. $R=E_K(N\oplus L)$
3. $$\begin{gathered} \text{For }i=1\text{ to }m\text{ do: } \\ Z[i]={\gamma }_i\cdot L\oplus R \end{gathered}$$
4. $$\begin{gathered} \text{For }i=1\text{ to }m-1\text{ do: } \\ M[i]=E_K^{-1}(C[i]\oplus Z[i])\oplus Z[i] \end{gathered}$$
5. $X[m]=len(C[m])\oplus L\cdot x^{-1}\oplus Z[m]$
6. $Y[m]=E_K(X[m])$
7. $M[m]=Y[m]\oplus C[m]$
8. $M=M[1],...,M[m]$
9. $\text{Checksum}=M[1]\oplus \cdots \oplus M[m-1]\oplus C[m]0^{*}\oplus Y[m]$
10. $T^{\prime }=E_K(\text{Checksum}\oplus Z[m])[\text{first }\tau \text{ bits}]$
11. $\text{If }T=T^{\prime }\text{ Then return }M\text{ else return INVALID}$

תיאור במילים

הקלט הוא מפתח סודי $K$, וקטור האתחול $N$ והמסר $M$ אותו מחלקים ל-$m$ לבלוקים בגודל $n$ סיביות, מרפדים באפסים את הבלוק האחרון אם נדרש. לצורך הכנה, תחילה מחשבים את $L$ על ידי הצפנה של מחרוזת אפסים עם צופן הבלוקים $E$ והמפתח $K$ ואז מחשבים ומאחסנים את הסדרה $L(-1),L,L(1),L(2),...,L(\mu )$ כאשר $\mu =\lceil {\text{log}}_{2}m\rceil$. אם אורך המסר אינו ידוע מראש אפשר לחשב ולאחסן מראש את הסדרה המתוארת עד לגבול העליון של מספר הבלוקים האפשריים עבור מפתח נתון. את הסדרה מחשבים בשיטה המתוארת לעיל, רקורסיה של כפל ב-$x$ (הזזה ו-XOR מותנה). מחשבים את האופסט הראשון על ידי הצפנה של $L$ עם וקטור האתחול $E_K(N\oplus L)$ ולאחר מכן באופן רקורסיבי מחשבים את כל האופסטים באמצעות הנוסחה $\text{Offset}=\text{Offset}\oplus L(\text{ntz}(i))$ עבור $i=1,...,m-1$. באמצעות צופן בלוקים מצפינים כל בלוק כשהוא מחובר עם האופסט המתאים ב-XOR פעמיים, לפני ואחרי ההצפנה כדי לקבל את הטקסט המוצפן $C$. מחשבים את הבלוק האחרון שהוא הצפנה של אורך המסר עם האופסט המתאים, מחשבים את סכום הביקורת אותו מצפינים באמצעות צופן הבלוקים עם האופסט המתאים. מוסיפים הצפנה של הבלוק האחרון עם קידוד של אורך המסר וכן האופסט האחרון. את תג האימות מחשבים על ידי XOR של כל הבלוקים יחד עם הבלוק המוצפן האחרון והצפנתם. $\tau$ הסיביות הראשונות של תוצאת ההצפנה האחרונה הן תג האימות $T$ שמצורף ל-$C$. תיאור הפענוח דומה. תחילה מבצעים את אותם פעולות הכנה כמו בתהליך ההצפנה. מפענחים את כל הבלוקים המוצפנים כשהם מחוברים ב-XOR עם האופסט המתאים ומחשבים את הבלוק האחרון ותג האימות $T^{\prime }$ אותו משווים עם $T$ שהתקבל מהשולח. אם כל הערכים נכונים האלגוריתם מחזיר את $M$, אם אחד מהערכים שגוי האלגוריתם מחזיר $\text{INVALID}$.

ביטחון

OCB נחשב בטוח לפי הגדרות שנהגו לראשונה ב-1984 על ידי מיקלי וגולדווסר בשם ביטחון סמנטי וכן על ידי בלייר ורוגווי ב-1997 ובשנת 2000. תאורטית זיוף תג אימות באופן כללי יכול להצליח בסיבוכיות של $1/2^{\tau }$. מעבר לזה, ככל שמוצפנים בלוקים נוספים כמות המידע שעומדת לרשות התוקף גדלה באופן יחסי עד $1.5{\sigma }^2/2^n$. כאשר $\sigma$ מייצג את מספר הבלוקים. כך שאם $\sigma$ קטן OCB יהיה בטוח בהנחה שצופן הבלוקים בטוח. במילים אחרות מצב ההפעלה אינו גורע מביטחון הצופן אלא בשיעור נמוך שצפוי לפחות מכל מצב הפעלה אחר. איבוד הביטחון הנובע מהגדרה זו מביא למסקנה שצופן הבלוקים צריך להיות לפחות 128 סיביות כדי להגיע לרמת ביטחון ראויה לצורך מעשי. לצורך המחשה, אם תג האימות הוא 64 סיביות ולתוקף גישה ל-$2^{40}$ בתים מוצפנים שהוא בחר ושהוצפנו עם אותו מפתח. הסיכויים שלו להצליח לייצר מסר מזויף עם תג אימות תקף ללא ידיעת המפתח כאשר גודל הבלוק הוא 128, הם בערך $1.5(2^{40-4}{)}^2/2^{128}+2^{-64}<2^{-55}$. בניסוח פורמלי בהינתן יריב בעל עוצמת חישוב מוגבלת וכן שיש לו גישה לאורקל והוא מסוגל להגיש $q$ שאילתות שבסך הכול מסתכמות ב-$\sigma$ בלוקים ואז מנסה לזייף מסר מסוים תוך $c$ ניסיונות, יהי $\overline{\sigma }=\sigma +2q+5c+11$, ביטחון שלב האימות של האלגוריתם יהיה

$$\begin{gathered} {\text{Adv}}_{\text{OCB}[\text{Perm}(n),\tau ]}^{\text{auth}} \\ (\text{A})\le 1.5{\overline{\sigma }}^2/2^n+1/2^{\tau } \end{gathered}$$

ביטחון שלב הסודיות באלגוריתם מוגדר על ידי

$$\begin{gathered} {\text{Adv}}_{\text{OCB}[\text{Perm}(n),\tau ]}^{\text{priv}} \\ (\text{A})\le 1.5{\overline{\sigma }}^2/2^n \end{gathered}$$

$\text{Adv}$ הוא היתרון של היריב המנסה לתקוף את המערכת. $\text{Perm}$ מייצג פרמוטציה (PRP). והסימן $\text{auth}$ מייצג את חלק האימות ואילו $\text{priv}$ הוא הסודיות.

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

ב-2002 פרסם ניילס פרגוסון התקפת התנגשויות כנגד OCB המכוונת נגד שלב האימות. ההתקפה מאלצת להגביל את כמות המידע שניתן לאימות עם מפתח יחיד לרמה של 64GB. והוא ממליץ שלא להשתמש במצב הפעלה זה.

פסאודו-קוד

$\text{<mrow data-mjx-texclass="ORD">OCB<mn>1</mn><mo stretchy="false">−</mo>ENCRYPT</mrow>}\mathit{(}\mathit{K},\mathit{N},\mathit{A},\mathit{P}\mathit{)}$ $R=E_K(0^{128})$ $L=R\cdot x$ $L_0=L\cdot x$ $\text{For }i=1\text{ to }m\text{ do: }{L}_i=L_{i-1}\cdot x$ $$\begin{gathered} {m} \\ {i}{s} \\ {t}{h}{e} \\ {l}{a}{r}{g}{e}{s}{t} \\ {i}{n}{t}{e}{g}{e}{r} \\ {s}{o} \\ {t}{h}{a}{t} \\ {1}{2}{8}{m}{\le }{|}{P}{|} \end{gathered}$$ $$\begin{gathered} P=P_1 \\ \Vert \\ {P}_2 \\ \Vert \\ ... \\ \Vert \\ {P}_m \\ \Vert \\ {P}_{*} \end{gathered}$$ $$\begin{gathered} {(}{N}{o}{t}{e}{:} \\ {{P}}_{{*}} \\ {m}{a}{y} \\ {p}{o}{s}{s}{i}{b}{l}{y} \\ {b}{e} \\ {e}{m}{p}{t}{y}{)} \end{gathered}$$ $$\begin{gathered} \text{Nonce}=\text{num2str}(\text{TAGLEN mod }128,7) \\ \Vert \\ {0}^{120-|N|} \\ \Vert \\ 1 \\ \Vert \\ N \end{gathered}$$ $$\begin{gathered} \text{bottom}=\text{str2num}({\text{Nonce}}_{123 \\ \text{to} \\ 128}) \end{gathered}$$ $$\begin{gathered} \text{Ktop}=E_K({\text{Nonce}}_{1 \\ .. \\ 122}||0^6) \end{gathered}$$ $$\begin{gathered} \text{Stretch}=\text{Ktop} \\ \Vert \\ ({\text{Ktop}}_{1..64}\oplus {\text{Ktop}}_{9..72}) \end{gathered}$$ $$\begin{gathered} \text{offset}={\text{Stretch}}_{1+\text{bottom} \\ \text{to} \\ 128+\text{bottom}} \end{gathered}$$ $\text{checksum}=0$ $\text{For }i=1\text{ to }m\text{ do:}$ $\text{offset}=\text{offset}\oplus L_{\text{ntz}(i)}$ $C_i=\text{offset}\oplus E_K(P_i\oplus \text{offset})$ $\text{checksum}=\text{checksum}\oplus P_i$ $$\begin{gathered} {P}{r}{o}{c}{e}{s}{s} \\ {a}{n}{y} \\ {f}{i}{n}{a}{l} \\ {p}{a}{r}{t}{i}{a}{l} \\ {b}{l}{o}{c}{k} \\ {a}{n}{d} \\ {c}{o}{m}{p}{u}{t}{e} \\ {r}{a}{w} \\ {t}{a}{g} \end{gathered}$$ $\text{offset}=\text{offset}\oplus R$ $\text{Pad}=E_K(\text{offset})$ $$\begin{gathered} C_{*}=P_{*}\oplus {\text{Pad}}_{1 \\ \text{to} \\ |P_{*}|} \end{gathered}$$ $$\begin{gathered} \text{checksum}=\text{checksum}\oplus (P_{*} \\ \Vert \\ 1 \\ \Vert \\ {0}^{127-|P_{*}|}) \end{gathered}$$ $\text{Tag}=E_K(\text{checksum}\oplus \text{offset}\oplus L)\oplus \text{HASH}(K,A)$ $$\begin{gathered} \text{Return: }{C}_1 \\ \Vert \\ {C}_2 \\ \Vert \\ ... \\ \Vert \\ {C}_m \\ \Vert \\ {C}_{*} \\ \Vert \\ {\text{Tag}}_{1 \\ \text{to} \\ \text{TAGLEN}} \end{gathered}$$

$\text{<mrow data-mjx-texclass="ORD">hash</mrow>}\mathit{(}\mathit{A},\mathit{K}\mathit{)}$ $\text{sum}=0$ $\text{offset}=0$ $R=E_K(0^{128})$ $L=R\cdot x$ $L_0=L\cdot x$ $\text{For }i=1\text{ to }m\text{ do: }{L}_i=L_{i-1}\cdot x$ $$\begin{gathered} {m} \\ {i}{s} \\ {t}{h}{e} \\ {l}{a}{r}{g}{e}{s}{t} \\ {i}{n}{t}{e}{g}{e}{r} \\ {s}{o} \\ {t}{h}{a}{t} \\ {1}{2}{8}{m}{\le }{|}{A}{|} \end{gathered}$$ $$\begin{gathered} A=A_1 \\ \Vert \\ {A}_2 \\ \Vert \\ ... \\ \Vert \\ {A}_m \\ \Vert \\ {A}_{*} \end{gathered}$$ $$\begin{gathered} {(}{N}{o}{t}{e}{:} \\ {{A}}_{{*}} \\ {m}{a}{y} \\ {p}{o}{s}{s}{i}{b}{l}{y} \\ {b}{e} \\ {e}{m}{p}{t}{y}{)} \end{gathered}$$ $\text{For }i=1\text{ to }m\text{ do: }$ $\text{offset}=\text{offset}\oplus L_{\text{ntz}(i)}$ $\text{sum}=\text{sum}\oplus E_K(A_i\oplus \text{offset})$ $$\begin{gathered} {(}{p}{r}{o}{c}{e}{s}{s} \\ {f}{i}{n}{a}{l} \\ {p}{a}{r}{t}{i}{a}{l} \\ {b}{l}{o}{c}{k}{)} \end{gathered}$$ $\text{offset}=\text{offset}\oplus R$ $\text{sum}=\text{sum}\oplus E_K(A_{*})$ $\text{Return }sum$ ‎ ‎ ‎ $\text{<mrow data-mjx-texclass="ORD">OCB<mn>1</mn><mo stretchy="false">−</mo>DECRYPT</mrow>}(K,N,A,C)$ $$\begin{gathered} {(}{p}{r}{o}{c}{e}{s}{s} \\ {O}{C}{B}{-}{E}{N}{C}{R}{Y}{P}{T} \\ {a}{n}{d} \\ {t}{h}{e}{n}{:}{)} \end{gathered}$$ $$\begin{gathered} {\text{If Tag}}_{(1 \\ \text{to} \\ \text{TAGLEN})}=T \\ \text{then return }P \end{gathered}$$ $\text{else return }\text{<mrow data-mjx-texclass="ORD">INVALID</mrow>}$

OCB2

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

$\mathbf{O}\mathbf{C}\mathbf{B}\mathbf{2}\mathbf{.}\mathbf{E}\mathbf{n}\mathbf{c}\mathbf{r}\mathbf{y}\mathbf{p}\mathbf{t}KN\mathit{(}\mathit{M},\mathit{\tau }\mathit{)}$ $\text{Let }M=M[1],M[2],...,M[m]$ $\text{For }i\in [1..m-1]\text{ do }C[i]\leftarrow {\mathit{\pi }}_i^N(M[i])$ $\text{Pad}\leftarrow {\pi }_m^N(\text{len}(M[m]))$ $C[m]\leftarrow M[m]\oplus \text{Pad}$ $C\leftarrow C[1],C[2],...,C[m]$ $\mathrm{\Sigma }\leftarrow M[1]\oplus \cdots \oplus M[m-1]\oplus C[m]0^{*}\oplus \text{Pad}$ $\text{Tag}\leftarrow {\overline{\pi }}_m^N(\mathrm{\Sigma })$ $T\leftarrow \text{Tag}[\text{first }\tau \text{ bits}]$ $$\begin{gathered} \text{return }{𝒞}=C \\ \Vert \\ T \end{gathered}$$

$\mathbf{O}\mathbf{C}\mathbf{B}\mathbf{2}\mathbf{.}\mathbf{D}\mathbf{e}\mathbf{c}\mathbf{r}\mathbf{y}\mathbf{p}\mathbf{t}KN({𝒞},\tau )$ $\text{Let }{𝒞}=C[1],C[2],...,C[m],T$ $\text{For }i\in [1..m-1]\text{ do }M[i]\leftarrow ({\mathit{\pi }}_i^N{)}^{-1}(C[i])$ $\text{Pad}\leftarrow {\pi }_m^N(\text{len}(M[m]))$ $M[m]\leftarrow C[m]\oplus \text{Pad}$ $M\leftarrow M[1],M[2],...,M[m]$ $\mathrm{\Sigma }\leftarrow M[1]\oplus \cdots \oplus M[m-1]\oplus C[m]0^{*}\oplus \text{Pad}$ $\text{Tag}\leftarrow {\overline{\pi }}_m^N(\mathrm{\Sigma })$ $T^{\prime }\leftarrow \text{Tag}[\text{first }\tau \text{ bits}]$ $\text{if }T=T^{\prime }\text{ then return }M\text{ else return INVALID}$

$\text{OCB2}[\tilde{E},\tau ]$ עם צופן בלוקים בר התאמה $\tilde{E}:{𝒦}\times {𝒯}\times \{0,1{\}}^n\to \{0,1{\}}^n$ המקבל tweak המסומן ${𝒯}=\{0,1\}\times \{0,1{\}}^n\times [1..2^{n/2}]\times \{0,1\}$ (סיבית תחילית, ערך בטווח הרצוי וסיבית סופית) ומייצר בנוסף תג אימות באורך $\tau \in [0..n]$. למען הפשטות באלגוריתם המתואר הסימן ${\mathit{\pi }}_i^N$ (כאשר ה-$\pi$ מודגש) מייצג צופן בלוקים בר התאמה $$\begin{gathered} {\tilde{E}}_K^{1 \\ N \\ i \\ 0} \end{gathered}$$ שבו ה-tweak מורכב מטווח ערכים המיוצג על ידי $N$ בנוסף ל-'1' מוביל, המונה $i$ ו-'0' מסיים באותו אופן ${\pi }_i^N$ מתאים ל-$$\begin{gathered} {\tilde{E}}_K^{0 \\ N \\ i \\ 0} \end{gathered}$$ והאחרון ${\overline{\pi }}_i^N$ מתאים ל-$$\begin{gathered} {\tilde{E}}_K^{0 \\ N \\ i \\ 1} \end{gathered}$$. ההבדלים בין הגרסאות הם בסיבית הפותחת והמסיימת.

OCB3

בגרסאות הקודמות בוצעו $m+2$ קריאות לצופן הבלוקים כדי להצפין $m$ בלוקים עם אימות, קריאה ראשונה לייצר את האופסט הראשון מוקטור האתחול, לאחר מכן הצפנת $m$ הבלוקים ולבסוף קריאה אחרונה להצפנת התג. אפשר להיפטר מהקריאה הראשונה לצופן הבלוקים על ידי החלפה בפונקציית גיבוב XOR אוניברסלית מהירה $\mathrm{\Delta }=H_K(N)=(\text{Stretch}\ll \text{Bottom}[1..128]$ כאשר $\text{Bottom}$ הוא 6 הסיביות הפחות משמעותיות של $N$ והמחרוזת $\text{Stretch}$ נוצרת על ידי הצפנה של $N$ עם שש הסיביות הפחות משמעותיות מאופסות (הפונקציה מפורטת בהמשך). מבנה זה הוכח כפונקציית גיבוב אוניברסלית. בדרך זו מתבצעות $m+1.016$ קריאות בממוצע לצופן הבלוקים בנוסף לביצוע פונקציית הגיבוב המהירה. ב-OCB3 התג אינו תלוי בטקסט המוצפן מה שמאפשר האצה נוספת בביצועים ביישום מקבילי לעומת הגרסאות הקודמות. כמו כן מסתבר שפעולת כפל בשדה $GF(2^{128})$ סובלת מביצועים גרועים ברוב הפלטפורמות לכן הוחלט על גשה אחרת לקידום המונה מאשר בגרסאות הקודמות. כעת כל הבלוקים מטופלים באותה דרך, גם הבלוק האחרון והם נפרדים זה מזה. שיפור נוסף הוא החלפת צופן הבלוקים בצופן בלוקים בר-התאמה, בדרך זו האלגוריתם פשוט יותר וקל להוכחה.

להלן תיאור האלגוריתם בגרסת $\mathrm{\Theta }\text{OCB3}[\tilde{E},\tau ]$ מעל צופן בלוקים בר התאמה:

${\mathbf{O}\mathbf{C}\mathbf{B}\mathbf{3}\mathbf{.}\mathbf{E}\mathbf{n}\mathbf{c}\mathbf{r}\mathbf{y}\mathbf{p}\mathbf{t}}_{N,K}(M,A)$ $$\begin{gathered} \text{let }M=M_1...M_m{M}_{*}; \\ |M_i|=n, \\ |M_{*}|<n \end{gathered}$$ $$\begin{gathered} \text{Checksum}=0^n, \\ {C}_{*}=\text{empty} \end{gathered}$$ $\text{For }i=1\text{ to }m\text{ do}$ $$\begin{gathered} C_i={\tilde{E}}_K^{N \\ i}(M_i) \end{gathered}$$ $\text{Checksum}=\text{Checksum}\oplus M_i$ $\text{If }{M}_{*}=\text{empty then:}$ $$\begin{gathered} \text{Final}={\tilde{E}}_K^{N \\ m \\ \mathrm{\$}}(\text{Checksum}) \end{gathered}$$ $$\begin{gathered} \text{else Pad}={\tilde{E}}_K^{N \\ m \\ *}(0^n) \end{gathered}$$ $C_{*}=M_{*}\oplus \text{Pad}[1..|M_{*}|]$ $\text{Checksum}=\text{Checksum}\oplus M_{*}10^{*}$ $$\begin{gathered} \text{Final}={\tilde{E}}_K^{m \\ * \\ \mathrm{\$}}(\text{Checksum}) \end{gathered}$$ $\text{Auth}={\text{Hash}}_K(A)$ $\text{Tag}=\text{Final}\oplus \text{Auth}$ $T=\text{Tag}[1..\tau ]$ $$\begin{gathered} \text{Return }{C}_1...C_m{C}_{*} \\ \Vert \\ T \end{gathered}$$ ‎ ${\mathbf{H}\mathbf{a}\mathbf{s}\mathbf{h}}_K(A)$ $\text{Sum}=0^n$ $$\begin{gathered} \text{let }A=A_1...A_m{A}_{*}; \\ |A_i|=n, \\ |A_{*}|<n \end{gathered}$$ $\text{For }i=1\text{ to }m\text{ do}$ $\text{Sum}=\text{Sum}\oplus {\tilde{E}}_K^i(A_i)$ $\text{If }{A}_{*}\ne \text{empty then:}$ $$\begin{gathered} \text{Sum}=\text{Sum}\oplus {\tilde{E}}_K^{m \\ *}(A_{*}10^{*}) \end{gathered}$$ $\text{Return Sum}$

$$\begin{gathered} {\mathbf{O}\mathbf{C}\mathbf{B}\mathbf{3}\mathbf{.}\mathbf{D}\mathbf{e}\mathbf{c}\mathbf{r}\mathbf{y}\mathbf{p}\mathbf{t}}_{K,N}(C \\ \Vert \\ T,A) \end{gathered}$$ $$\begin{gathered} \text{let }C=C_1...C_m{C}_{*}; \\ |C_i|=n,|C_{*}|<n \end{gathered}$$ $\text{Checksum}=0^n,M_{*}=\text{empty}$ $\text{For }i=1\text{ do }m\text{ do}$ $$\begin{gathered} M_i={\tilde{D}}_K^{N \\ i}(C_i) \end{gathered}$$ $\text{Checksum}=\text{Checksum}\oplus M_i$ $\text{If }{C}_{*}=\text{empty then:}$ $$\begin{gathered} \text{Final}={\tilde{E}}_K^{N \\ m \\ \mathrm{\$}}(\text{Checksum}) \end{gathered}$$ $$\begin{gathered} \text{else Pad}={\tilde{E}}_K^{N \\ m \\ *}(0^n) \end{gathered}$$ $M_{*}=C_{*}\oplus \text{Pad}[1..|C_{*}|]$ $\text{Checksum}=\text{Checksum}\oplus M_{*}10^{*}$ $$\begin{gathered} \text{Final}={\tilde{E}}_K^{N \\ m \\ * \\ \mathrm{\$}}(\text{Checksum}) \end{gathered}$$ $\text{Auth}={\text{Hash}}_K(A)$ $\text{Tag}=\text{Final}\oplus \text{Auth}$ $T^{\prime }=\text{Tag}[1..\tau ]$ $\text{If }T=T^{\prime }\text{ then return }{M}_1...M_m{M}_{*}$ $\text{else return INVALID}$ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎

הסבר: צופן הבלוקים בר התאמה מסומן על ידי $\tilde{E}$ כשגודל הבלוק נקבע ל-128. הוא מקבל מפתח הצפנה, tweak וטקסט קריא ומחזיר טקסט מוצפן (להלן תיאור מפורט כיצד להפוך צופן בלוקים רגיל לצופן בלוקים בר התאמה). הסימן $\tau$ מייצג את אורך תג האימות בסיביות. בנוסף האלגוריתם מקבל את הטקסט הנלווה A. הסימנים * ו-$ מייצגים ערכי tweak שונים בהתאם להיסטים (מבוארים בהרחבה להלן). הביטוי $0^n$ פירושו מחרוזת של $n$ אפסים. בניסוי שערכו המפתחים פיליפ רוגווי וטד קרובץ לטענתם האלגוריתם מהיר הרבה יותר מ-CCM או GCM בניגוד לטענת המפתחים של האלגוריתמים הללו. ביישום ממוטב האלגוריתם יכול הגיע למהירות הצפנה של 1.5 CPB. הטכניקה להפיכת צופן הבלוקים לצופן בלוקים בר התאמה נעשית כך:

ביטוי				תיאור
$L=E_K(0^{128})$				הצפנת מחרוזת של 128 אפסים
${\lambda }_i=4a(i)$	${\lambda }_i^{*}=4a(i)+1$	${\lambda }_i^{\mathrm{\$}}=4a(i)+2$	${\lambda }_i^{*\mathrm{\$}}=4a(i)+3$	ארבעה היסטים לפי אינדקס (עם הסימנים *, $ או *$)
$$\begin{gathered} {\tilde{E}}_K^{N \\ i}(M)=E_K(M\oplus \mathrm{\Delta })\oplus \mathrm{\Delta } \end{gathered}$$			$$\begin{gathered} \mathrm{\Delta }=\text{Initial}\oplus {\lambda }_{i}L; \\ i\ge 1 \end{gathered}$$	tweak "N i"
$$\begin{gathered} {\tilde{E}}_K^{N \\ i \\ *}(M)=E_K(X\oplus \mathrm{\Delta }) \end{gathered}$$			$$\begin{gathered} \mathrm{\Delta }=\text{Initial}\oplus {\lambda }_i^{*}L; \\ i\ge 0 \end{gathered}$$	tweak "N i *"
$$\begin{gathered} {\tilde{E}}_K^{N \\ i \\ \mathrm{\$}}(M)=E_K(M\oplus \mathrm{\Delta }) \end{gathered}$$			$$\begin{gathered} \mathrm{\Delta }=\text{Initial}\oplus {\lambda }_i^{\mathrm{\$}}L; \\ i\ge 0 \end{gathered}$$	tweak "N i $"
$$\begin{gathered} {\tilde{E}}_K^{N \\ i \\ * \\ \mathrm{\$}}(M)=E_K(M\oplus \mathrm{\Delta }) \end{gathered}$$			$$\begin{gathered} \mathrm{\Delta }=\text{Initial}\oplus {\lambda }_i^{*\mathrm{\$}}L; \\ i\ge 1 \end{gathered}$$	tweak "N i * $"
${\tilde{E}}_K^i(M)=E_K(M\oplus \mathrm{\Delta })$			$$\begin{gathered} \mathrm{\Delta }={\lambda }_{i}L; \\ i\ge 1 \end{gathered}$$	tweak "i"
$$\begin{gathered} {\tilde{E}}_K^{i \\ *}(M)=E_K(M\oplus \mathrm{\Delta }) \end{gathered}$$			$$\begin{gathered} \mathrm{\Delta }={\lambda }_i^{*}L; \\ i\ge 0 \end{gathered}$$	tweak "i *"

הסבר: תחילה מצפינים מחרוזת אפסים באמצעות צופן הבלוקים עם מפתח ההצפנה המסופק על ידי המשתמש, לאחר מכן כל בלוק מסר מחובר עם tweak שונה ב-XOR לפני שהוא מוצפן. כדי לייצר את ה-tweak המתאים לכל בלוק, תחילה מייצרים אופסט $\lambda$ מתאים, אותו מכפילים ב-$L$ ומחברים ב-XOR עם תוצאת פונקציית הגיבוב האוניברסלית של המפתח (להלן). את האופסט מכינים על ידי וריאציה של קוד גריי רקורסיבי כשהביטוי $a(i-1)\oplus 2^{\text{ntz}(i)}$ פירושו שכדי לקבל את הקוד ה-$i$ ברצף מחברים ב-XOR את האלמנט הקודם בחזקה של מספר האפסים המסיימים (הפחות משמעותיים) באינדקס $i$, לדוגמה $\text{ntz}(8)=3$ וכן $\text{ntz}(7)=0$. את פונקציית הגיבוב האוניברסלית מכינים כך:

$\text{Nonce}=0^{127-|N|}1N$

$\text{Top}=\text{Nonce}\wedge 1^{122}{0}^6$

$\text{Bottom}=\text{Nonce}\wedge 0^{122}{1}^6$

$$\begin{gathered} \text{Stretch}=E_K(Top) \\ \Vert \\ (E_K(\text{Top})\oplus (E_K(\text{Top})\ll 8)) \end{gathered}$$

$\text{Initial}=(\text{Stretch}\ll \text{Bottom})[1..128]$

הסבר: ה-Nonce הוא ערך ייחודי וחד פעמי הנוצר פשוט על ידי וקטור האתחול $N$ המסופק על ידי המשתמש, כשהוא מרופד בסיבית 1 ואפסים במספר הנדרש כדי להשלימו לבלוק שלם באורך 128 סיביות. ואז מחלקים את הבלוק לשני חלקים העליון באורך 122 סיביות והתחתון באורך 6 סיביות (הסימן $\wedge$ מייצג AND המתפקד כאן כמסכת סיביות), מצפינים את העליון באמצעות צופן הבלוקים עם המפתח $K$. לאחר הזזה (shift), הצמדה ($\Vert$) והצפנה כמתואר התוצאה היא הערך Initial.

ראו גם

• CCM
• GCM
• מצב הפעלה של צופן בלוקים