Poly1305

Poly1305 הוא שמו של קוד אימות מסרים קריפטוגרפי (בקיצור MAC) שפותח ב-2005 על ידי דניאל ברנשטיין^[1]. האלגוריתם נועד להבטחת שלמות ואימות מסרים והוצע בתקן של IETF בטיוטה RFC 7539 לאימות מסרים עבור פרוטוקול SSL/TLS.

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

בהצעה המקורית נקרא האלגוריתם Poly1305-AES כשהוא פועל בשילוב עם AES. הוא מפיק תג אימות באורך 16 בתים ממסר בכל אורך רצוי, תוך שימוש בשני מפתחות אחד עבור AES ואחד נוסף שניהם באורך 16 בתים (128 סיביות) וכן וקטור אתחול באורך 16 בתים. ביטחון האלגוריתם קרוב מאוד לביטחון צופן AES כאשר ההפרש הוא לכל היותר ${\displaystyle 14D\lceil L/16\rceil /2^{106}}$ עם מסר באורך של עד ${\displaystyle L}$ בתים, בהנחה שהמתקיף רואה לא יותר מ-${\displaystyle 2^{64}}$ בלוקים מאומתים עם תגי האימות שלהם ורשאי לבצע לכל היותר ${\displaystyle D}$ ניסיונות זיוף. במילים אחרות אם AES קשה לשבירה אז Poly1305 בטוח. האלגוריתם מאוד יעיל ונחשב ל'סטייט אוף דה ארט' במונחים של מהירות חישוב. פחות מ-${\displaystyle 3.1\ell +780}$ מחזורי שעון עבור מסר באורך ${\displaystyle \ell }$ בתים על מחשב אתלון. המפתח פרסם קוד מקור ממוטב לשימוש חופשי ב-C ו-C++‎^[2]. היות שהאלגוריתם מופרד מהצופן ניתן להחליף את AES בצופן אחר מהיר יותר או במידה שיתגלו בעיות אבטחה עם AES. מאוחר יותר בשל שיקולי יעילות נבחר ChaCha כצופן הבסיסי עליו קוד האימות פועל.

ב-2014 בחרה גוגל ב-Poly1305 יחד עם צופן ChaCha כתחליף ל-RC4 ב-TLS/SSL לאבטחת רשת האינטרנט^[3]. היישום הראשוני נועד לשיפור אבטחת תקשורת HTTPS בין דפדפני גוגל כרום על מערכות ההפעלה אנדרואיד לבין אתרי גוגל והוא החליף את AES-GCM^[4]. לטענת גוגל השילוב החדש מניב שיפור של פי שלושה במהירות לעומת הקודם. ב-2015 קוד אימות Poly1305 יחד עם ChaCha הפכו לתקן רשמי של IETF לאבטחת פרוטוקול TLS בטיוטה RFC 7905. כמו כן שולב גם ב-OpenSSH כאלטרנטיבה להצפנה מאומתת^[5][6].

היתרונות של קוד אימות המסרים Poly1305 הם:

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

נוסחת קוד האימות היא בעצם חישוב ישיר של פולינומים מודולו המספר הראשוני ${\displaystyle 2^{130}-5}$ (מכאן נובע השם), כאשר בתי המסר משמשים כמקדמים. עיקר התיאור מתייחס לריפוד והמרת הקלט ממחרוזת בתים למספרים שלמים באורך הרצוי והכנת המפתחות.

נתון המסר ${\displaystyle m}$ באורך ${\displaystyle \ell }$ בתים המיוצג על ידי ${\displaystyle m_{0},m_{1},...,m_{\ell -1}}$ אותו מחלקים לבלוקים בגודל ${\displaystyle q=\lceil \ell /16\rceil }$. אל ${\displaystyle c_{i}}$ הבלוקים הראשונים (השלמים) של המסר כאשר ${\displaystyle 1\leq i\leq \lfloor \ell /16\rfloor }$ מתייחסים כאל המערך ${\displaystyle c_{1},c_{2},...,c_{q-1}}$ המכיל שלמים כך שכל ${\displaystyle c_{i}\in \{1,2,...,2^{129}\}}$ מיוצג על ידי הפולינום הבא:

${\displaystyle c_{i}=m_{16i-16}+2^{8}m_{16i-15}+2^{16}m_{16i-14}+\cdots +2^{120}m_{16i-1}+2^{128}}$.

אם ${\displaystyle \ell }$ אינו כפולה של 16 אזי קיימים מספר בתים נוספים שיש להביא בחשבון לכן כוללים פולינום נוסף:

${\displaystyle c_{q}=m_{16q-16}+2^{8}m_{16q-15}+\cdots +2^{8(\ell {\text{ mod }}16)-8}m_{\ell -1}+2^{8(\ell {\text{ mod }}16)}}$

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

Poly1305 משתמש בשני מפתחות סודיים שצריכים להיות משותפים לשולח והמקבל. המפתח הראשון ${\displaystyle k}$ משמש להצפנה עם AES ואילו השני ${\displaystyle r}$ מייצג מספר באורך 128 סיביות לפי סדר בתים קטן דהיינו: ${\displaystyle r=r_{0}+2^{8}r_{1}+\cdots +2^{120}r_{15}}$. כל ${\displaystyle r_{i}}$ בגודל בית אחד. וכן חלק מסיביות ${\displaystyle r}$ צריכות להיות מאופסות. ארבע הסיביות העליונות (המשמעותיות ביותר) של הבתים ${\displaystyle r_{3},r_{7},r_{11},r_{15}}$ של ${\displaystyle r}$ צריכות להיות מאופסות (כלומר מתקבל בכל אחד מהם בנפרד מספר בטווח ${\displaystyle [0..15]}$). שתי הסיביות הנמוכות (הכי פחות משמעותיות) של הבתים ${\displaystyle r_{4},r_{8},r_{12}}$ צריכות להיות אפס (כלומר מספר בטווח ${\displaystyle [4..252]}$). לסיכום ישנם ${\displaystyle 2^{106}}$ אפשרויות עבור ${\displaystyle r}$. במילים אחרות ${\displaystyle r}$ מורכב מארבעה חלקים באורך 32 סיביות כל אחד:

${\displaystyle r_{0}+r_{1}+r_{2}+r_{3}}$

כאשר

${\displaystyle r_{0}\in \{0,1,2,...,2^{28}-1\}}$,

${\displaystyle r_{1}/2^{32}\in \{0,4,8,12,...,2^{28}-4\}}$,

${\displaystyle r_{2}/2^{64}\in \{0,4,8,12,...,2^{28}-4\}}$,

${\displaystyle r_{3}/2^{96}\in \{0,4,8,12,...,2^{28}-4\}}$.

כל מסר חייב להיות מלווה בוקטור אתחול או ערך חד פעמי כלשהו כמו נומרטור. וקטור האתחול ${\displaystyle n}$ הופך קלט לצופן הסימטרי כדי לקבל מחרוזת אקראית באורך 16 בתים.

פונקציית האימות היא:

${\displaystyle {\boldsymbol {out=\mathbf {Poly1305} _{r}(m,\mathbf {AES} _{k}(n))}}}$.

ביתר פירוט, קוד האימות של המסר ${\displaystyle m}$ עם הערך החד פעמי ${\displaystyle n}$ ועם מפתחות ההצפנה ${\displaystyle k}$ ו-${\displaystyle r}$ הוא מחרוזת של 16 בתים לפי סדר בתים קטן המחושבת על ידי:

${\displaystyle (((c_{1}r^{q}+c_{2}r^{q-1}+\cdots +c_{q}r^{1}){\text{ mod }}(2^{130}-5))+{\text{AES}}_{k}(n)){\text{ mod }}2^{128}}$.

האסטרטגיה להשגת ביצועים גבוהים כמובטח היא ניצול יכולות המעבד כמו ניצול יחידת הנקודה צפה המאפשר שימוש באוגרים גדולים במיוחד לביצוע פעולות אריתמטיות בסיסיות במהירות גבוהה בנוסף למספר אופטימיזציות הקשורות למעבד ספציפי. מסיבה זו הוצעו מספר גרסאות של קוד המקור המותאמות במיוחד לחומרות נפוצות כמו פנטיום, אתלון, SPARC פאואר פיסי וכדומה. באופן כללי, תחילה מגדירים משתנה מקומי ${\displaystyle h=0}$ ומחשבים עבור כל ${\displaystyle c_{i}}$ המתאים לבלוק אחד (כאמור לאחר הוספת 1 בראש וריפוד באפסים אם נדרש) את ${\displaystyle h\leftarrow h+c}$ ואז מחשבים את ${\displaystyle h\leftarrow h\cdot r}$ ומצמצמים מודולו ${\displaystyle 2^{130}-5}$, חוזרים על תהליך זה עד לחישוב כל הבלוקים של המסר אותו מאמתים, לבסוף מחברים ל-${\displaystyle s}$ שהוא כאמור תוצאה של הצפנת הבלוק ${\displaystyle n}$ עם המפתח הסודי ${\displaystyle k}$ והתוצאה האחרונה מודולו ${\displaystyle 2^{128}}$ היא תג האימות.

כמובן שהצופן AES כאן אינו מנדטורי וניתן להחליפו בכל צופן אחר כל עוד מתייחסים לפלט הצופן כאל מספר שלם באורך 128 סיביות. השולח והמקבל משתמשים באותה פונקציה הן כדי לחשב את תג האימות והן כדי לוודא שהתג אותנטי. כאשר תג האימות ${\displaystyle out}$ מגיע למקבל יחד עם המסר, הוא מחשב בעצמו את הפונקציה האמורה על המסר ומשווה את התוצאות.

באחריות המשתמש לוודא שהמפתחות ${\displaystyle k}$ ו-${\displaystyle r}$ סודיים ואקראיים. ההנחה היא שהם נבחרו באופן בלתי תלוי בהתפלגות אחידה בטווח של ${\displaystyle 2^{128}}$ ו-${\displaystyle 2^{106}}$ בהתאמה כך שההסתברות הכוללת לכל זוג כזה היא ${\displaystyle 2^{-234}}$ מתוך ${\displaystyle 2^{234}}$ אפשרויות.

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

קיימת הוכחה ש-Poly1305 מבטיח שהדרך היחידה שמתקיף יוכל לנחש ערכים ${\displaystyle (n,m,a)}$ כך שמתקיים ${\displaystyle a={\text{Poly1305}}_{r}(m,E_{k}(n))}$ שונים מאלו שנשלחו על ידי המקור כלומר זיוף תג האימות, היא לשבור את הצופן ${\displaystyle E}$. אם המתקיף לא מסוגל לשבור את ${\displaystyle E}$ והמקבל מקפיד להיפטר מכל הערכים ${\displaystyle (n,m,a)}$ שאינם אותנטיים כלומר ${\displaystyle a\neq {\text{Poly1305}}_{r}(m,E_{k}(n))}$ אז המקבל יכול להיות סמוך ובטוח שקיבל רק מסרים אותנטיים ולא מזויפים. כדי להעריך בכמות את הביטחון האמור, נניח שהמתקיף יכול להשיג עד ${\displaystyle C}$ מסרים מאומתים (אותנטיים) ותגי האימות שלהם יחד איתם, וכן נניח שהמתקיף רשאי לבצע לכל היותר ${\displaystyle D}$ ניסיונות זיוף של תגי האימות אותם הוא רשאי לשלוח ליעדם ולקבל בחזרה את התגובה האם התג התקבל כאותנטי או נדחה. נניח עוד שההסתברות להצלחת המתקיף בשבירת הצופן ${\displaystyle E}$ היא ${\displaystyle \epsilon }$ כלומר אחרי ${\displaystyle C+D}$ שאילתות בסיכויים של חצי ועוד ${\displaystyle \epsilon }$ הוא מסוגל להבחין בין פלט הצופן לבין מחרוזת אקראית אמיתית. אם למען הפשטות כל המסרים הם באורך ${\displaystyle L}$ הרי שבהסתברות של לפחות

${\displaystyle 1-\epsilon -{\frac {(1-C/2^{128})^{-(C+1)/2}8D\lceil L/16\rceil }{2^{106}}}}$,

כל ניסיונות הזיוף של המתקיף יתגלו ויידחו על ידי המקבל. ביתר פירוט אם ${\displaystyle C\leq 2^{64}}$ הרי שסיכויי המתקיף הם לכל היותר ${\displaystyle \epsilon +1.649\cdot 8D\lceil L/16\rceil /2^{106}<\epsilon +14D\lceil L/16\rceil /2^{106}}$. אף על פי שאין דרך להוכיח עבור צופן כמו AES למשל ש-${\displaystyle \epsilon }$ קטן אולם ברור שהשאיפה העיקרית בכל צופן סימטרי היא להגיע ל-${\displaystyle \epsilon }$ נמוך ככל האפשר, כי אחרת המשמעות היא שהמתקיף יוכל לשבור את הצופן. ההוכחה לנכונות הצהרת הביטחון שהובאה מופיעה במאמר של דניאל ברנשטיין.

הסיבה לבחירת המספר הראשוני ${\displaystyle 2^{130}-5}$ היא בשל המבנה הדליל שלו שמאפשר ביצוע מודולו מהיר גם בתוכנה וגם בחומרה. יש כמה סיבות להוספת ${\displaystyle r}$ שנקרא Nonce (ערך חד-פעמי). ראשית ביטחון גבוה יותר, לשם השוואה ביטחון פרוטוקול אימות מסרים ללא תוספת ${\displaystyle r}$ הוא מסדר גודל ${\displaystyle C(C+D)L/2^{106}}$ במקום ${\displaystyle DL/2^{106}}$. כאן ${\displaystyle C}$ הוא מספר תגי האימות האותנטיים שהמתקיף השיג ו-${\displaystyle D}$ מספר המסרים המזויפים שהמתקיף שלח לבדיקה. הביטחון הולך ונחלש ככל שנוספים מסרים ולכן אינו מומלץ לשימוש ממושך. שנית, באופן זה הפעלת AES נעשית במקביל ולא גורמת לעיכובים. שלישית, מרבית היישומים כוללים Nonce בכל מקרה, מסיבות שונות כמו מניעת שידור חוזר של מסרים. הסיבה למבנה המיוחד של ${\displaystyle r}$ נובעת מרצון לפשט ולהאיץ את יישום הפרוטוקול בקוד. אף על פי שתאורטית עדיף לא הגביל את ${\displaystyle r}$ ולאפשר ערכים מקסימליים. מצד שני ביטחון הפרוטוקול אינו נחלש במידה ניכרת כתוצאה מהמגבלה, כך שאפשר ליהנות מביצועים טובים יותר.

הפסידו קוד הבא אינו מייצג קוד שימושי ואינו ממוטב אלא נועד לצורך המחשה בלבד. הפונקציה מקבלת את הפרמטרים הבאים: המסר ${\displaystyle m}$, מפתח סודי ${\displaystyle r}$, הערך ${\displaystyle s}$ שהוא תוצאת ההצפנה של ${\displaystyle n}$ עם המפתח ${\displaystyle k}$ באמצעות האלגוריתם הסימטרי המועדף; ${\displaystyle s=E_{k}(n)}$ וכן ${\displaystyle l}$ אורך המסר בבתים ומחזירה את תג האימות ${\displaystyle out}$. כל הפרמטרים למעט האחרון מתקבלים כמערך בתים אולם עוברים המרה למספר שלם לפי סדר בתים קטן לדוגמה עבור המערך ${\displaystyle r}$ הביטוי ${\displaystyle r[j]\ll (8*j)}$ ממיר את הבית ה-${\displaystyle j}$ למספר שלם ומציב אותו במקום המתאים בתוך משתנה באורך 129 סיביות על ידי הזזה לשמאל (shift) שהיא כמו העלאה בחזקת ${\displaystyle 2^{8j}}$. יש לזכור שביישום מעשי חייבים להשתמש בספרייה אריתמטית למספרים ארוכים בשפת התכנות המועדפת כמו הספרייה GNU MP ל-C++‎ כי כאן כל המספרים השלמים גדולים מאוד.

Poly1305(out, r, s, m, l)
{
   j = 0   
   rbar = h = 0;  // big numbers
   p = (1 << 130) - 5; // big prime number

   // convert the input byte array 'r' into a big number 'rbar'
   for j = 0 to 15 do
   {
       rbar = rbar + (r[j] << (8 * j));
   }
   while(l > 0)
   {
      c = 0; // big temporary numbers
      // convert the input byte array 'm' into the big number 'c'
      for j = 0 to 15 and j < l do
      {
         c = c + (m[j] << (8 * j));
      }
      j = min(16, l);
      c = c + (1 << (8 * j)); // add 1 at the beginning
      h = ((h + c) * rbar) mod p;

      m = m + j; // point to next block
      l = l - j;

      for j = 0 to 15 do
      {
         h = h + (s[j] << (8 * j));
      }
   }
   for j = 0 to 15 do
   {
      out[j] = (h mod 256);  // extract LSB from h
      h = h >> 8;            // next byte
   }
}

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