BLAKE

BLAKE היא משפחה של פונקציות גיבוב קריפטוגרפיות שהראשונה שבהן פותחה ב-2008 והייתה מועמדת לתחרות הגיבוב עבור תקן SHA-3 שאורגנה על ידי NIST ובסופה זכה Keccak. בהתאם לדרישות התקן האלגוריתם כולל ארבע פונקציות: BLAKE-224,‏ BLAKE-256,‏ BLAKE-384 ו-BLAKE-512 כשהמספר אחרי השם מייצג את גודל הפלט בסיביות. הן מחולקות לשתי קטגוריות; הראשונה BLAKE-256 מיועדת לפלטפורמת 32 סיביות או פחות, ממנה נגזרת BLAKE-224 הנבדלת ממנה בערכים ההתחלתיים וגודל הפלט וכן לגבי BLAKE-512 והפונקציה הנגזרת ממנה המיועדות לסביבת 64 סיביות. אף על פי ש-BLAKE לא זכתה בסופו של דבר, לפי הצהרת מארגני התחרות לאחר קריפטואנליזה מעמיקה, BLAKE כמו יתר האלגוריתמים שעלו לגמר בטוחה לשימוש ולא התגלו בה פגמים או בעיות רציניות. BLAKE2 פותחה בעקבות הלקחים והניסיון שהצטברו מקודמה. היא מהירה מאוד ונחשבת ל-'סטייט אוף דה ארט' בתפוקתה. היא מהירה פי שלושה בערך מ-SHA-3 ולטענת המפתחים עם ביטחון זהה. היא מגיעה בשתי גרסאות BLAKE2s עבור חומרה מוגבלת משאבים ו-BLAKE2b הפועלת על פלטפורמת 64 סיביות ונועדה לביצועים גבוהים.
BLAKE פותחה על ידי Jean-Philippe Aumasson,‏ Luca Henzen,‏ Willi Meier ו-Raphael C.-W. Phan. בתחילה נקראה BLAKE-xx כאשר xx הוא 28, 32, 48 או 64. ב-2010 שונה השם לקראת ההגשה לתחרות כדי להבדילו מהגרסה המקורית. BLAKE2 שהוצעה בטיוטה RFC 7693 פותחה בדצמבר 2012 על ידי Jean-Philippe Aumasson,‏ Samuel Neves,‏ Zooko Wilcox-O’Hearn, ו-Christian Winnerlein.
שתיהן חופשיות לשימוש ואינן מוגנות בפטנט. לא ידוע על קריפטואנליזה מוצלחת שלהן והן נחשבות לבטוחות. כמו כן פורסמו מספר גרסאות מוחלשות של מועמד SHA-3 הנקראות "גרסאות צעצוע" לצורך קריפטואנליזה (BLOKE,‏ FLAKE,‏ BLAZE ו-BRAKE). קיימים מימושים חופשיים של הפונקציות השונות בשפת C,‏ C++‎ ו-C#‎ בין היתר אפשר למצוא ב-GitHub וכן מימוש לשפת VHDL.

BLAKE

פונקציית הגיבוב BLAKE מבוססת על מספר מרכיבים ידועים בביטחונם. היא דור המשך של פונקציית הגיבוב LAKE המכילה מצב פנימי רחב (Wide pipe), פונקציית הדחיסה הפנימית היא וריאציה של צופן הזרם ChaCha והיא מגוונת באמצעות Salt שהוא ערך אקראי חד-פעמי שאינו סודי המתפקד כמו וקטור אתחול והאיטרציה הפנימית פועלת לפי מבנה HAIFA שהוא גרסה משופרת של מבנה מרקל-דמגרד. הגיוון הוא אופציונלי וכאשר הוא קיים הפונקציה נקראת פונקציית גיבוב אקראית.

פונקציית גיבוב אקראית

פונקציית גיבוב אקראית היא פונקציית גיבוב המשלבת בנוסף לקלט הרגיל "גיוון" אקראי הנקרא Salt. מהיבט תאורטי המטרה של ה-Salt היא לאפשר הסתמכות על פונקציית גיבוב בעלת ביטחון חלש ממה שהוצהר. הרעיון הוצע במקור על ידי שי הלוי והוגו קרווציק לחיזוק אלגוריתם חתימה דיגיטלית DSA, המשלב בין היתר פונקציית גיבוב. השאיפה היא שאלגוריתם החתימה יישאר בטוח אפילו אם פונקציית הגיבוב בה הוא משתמש אינה טובה לגמרי, כלומר ביטחונה התרופף בעקבות קריפטואנליזה חדשה, בדיוק כמו שקרה עם MD5. אפשר להפוך פונקציית גיבוב דטרמיניסטית לאקראית על ידי ערבוב הקלט עם ערך אקראי לפי שמעבירים בפונקציית הגיבוב. למשל פונקציית הגיבוב מהצורה  נקראת פונקציית גיבוב אקראית, כאשר  היא פונקציית גיבוב רגילה כמו SHA-2 ו- יכול להיות ערך אקראי אפילו קצר ואינו נחשב למפתח הצפנה לכן אין צורך להסתירו. מבנה כזה יעיל ומבטיח קושי רב יותר במציאת התנגשויות כלומר למצוא  המקיים  מאשר במודל הסטנדרטי של פונקציות גיבוב. כאן התקפת יום הולדת אינה ישימה כיוון שהיא לא יכולה להיות אוף ליין, כלומר התוקף חייב לקבל בנוסף לתמצית הקלט את ה-Salt שמיוצר באופן אקראי עבור כל מסר, לכן אפשר להסתפק בפונקציית גיבוב הנקראת Target Collision Resistance (בקיצור TCR) שהיא גרסה חלשה יותר מפונקציה חסינת התנגשויות מלאה.
באופן כללי מומחים ממליצים כיום היכן שהדבר אפשרי לעבור לאלגוריתם גיבוב אקראי כי הוא מספק "רשת ביטחון", אם וכאשר יתגלו בפונקציית הגיבוב עצמה חולשות.

תיאור כללי

הזיכרון הפנימי (Internal state) של פונקציית הגיבוב מיוצג על ידי מטריצה של 4x4 מילים באורך 32 סיביות כל אחד. הקלט נטען לתוך המצב הפנימי המורחב לפי התיאור בהמשך. הפונקציה הפנימית מורכבת מסדרה של שלוש פעולות פשוטות XOR, חיבור והזזה מעגלית. הפונקציה מופעלת על מילות המצב 14 פעמים במקרה של BLAKE-256 או 16 פעמים במקרה של BLAKE-512 ובכל סבב מעבדת את כניסות המטריצה תחילה בעמודות ולאחר מכן באלכסונים ומוסיפה ערכים קבועים שונים לפי טבלה בהתאם למספר הסבב. לאחר מכן המצב הפנימי נדחס לחצי מאורכו והפלט מופק יחד עם הגיוון (Salt).
BLAKE פועלת ברמה של מילים באורך 32 סיביות (או 64 סיביות במקרה של BLAKE-512). הסימונים המוסכמים הם: הקלט  באורך כלשהו מחולק ל- בלוקים באורך 16 מילים כל אחד: . המילים מייצגים מספרים שלמים בלתי מסומנים כאשר ההמרה מבתים למילים היא לפי סדר בתים גדול. הביטוי  מתייחס לבלוק ה- של  ואילו הביטוי  מתייחס למילה ה- של בלוק כלשהו, לכן  מייצג את המילה ה- של הבלוק  של . המילים בבלוק הראשון מיוצגות על ידי: , בבלוק הבא המספר העילי מתחלף ל-1 וכן הלאה.

אתחול המצב הפנימי

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

היבטי יישום וביטחון

מספר הפעולות של BLAKE-256 הן 672 פעולות חיבור, 700 פעולות XOR ו-448 הזזות, בסך הכול 1,820 פעולות בסיסיות. לא כולל תקורה נוספת הנובעת מריפוד והכנת המסר. צריכת הזיכרון היא 144 בתים ב-ROM ו-184 בתים ב-RAM לא כולל תקורה נוספת הנובעת מטיפול במצביעים. BLAKE-512 מבצע בסך הכול 2,076 פעולות.
דרך אחרת יעילה יותר לבצע את הפעולה הפנימית של פונקציית הדחיסה היא תחילה לעבד את העמודות ולאחר מכן לסובב (Rotate) בהזזה מעגלית ברמה של מילים את מילות המצב לפי הכלל הבא: עבור העמודה ה- מסובבים  פעמים. ואז מחשבים את שורות המטריצה (במקום אלכסונים). מיטוב דומה בוצע ב-Salsa20, המטרה היא ליהנות מביצוע מקבילי מהיר באמצעות פקודות SIMD על וקטורים הנתמכות במעבדים המודרניים.
ביישום מקבילי אפשר לבצע את שמונה הפונקציות הפנימיות במספר ענפים מקבילים בכך משיגים שיפור בפקטור של 2 או יותר במהירות.
פונקציית הגיבוב BLAKE על גרסאותיה נוסתה על מספר פלטפורמות כמו מעבדי 64 ביט, 32 ביט, מיקרו בקר 8 ביט ו-FPGA. והיא הציגה ביצועים טובים בהשוואה למתחרים.
הפעולות האריתמטיות של הפונקציה הפנימית מסודרות לפי "ARX" שזה חיבור, הזזה ו-XOR לפי סדר מסוים. השילוב הזה נחקר היטב בצופן הזרם Salsa20 ובצפנים אחרים והוכח שהוא בטוח נגד קריפטאנליזה דיפרנציאלית וכן נגד התקפות ערוץ צדדי.
HAIFA הוא מבנה משופר גנרי לפונקציית גיבוב הפועל כמו מבנה מרקל דמגרד אך עם Salt ומונה והוכח כבטוח יותר. המבנה מציע עמידות נגד התקפות ידועות על פונקציות גיבוב. מציאת התנגשויות, מציאת מקור שני, התקפת יום-הולדת, הטכניקה של Joux למציאת התנגשויות מרובות.

גיבוב עם מפתח או PRF

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

עץ גיבוב

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

קוד לדוגמה

להלן קוד שלם בשפת C#‎ של פונקציית הגיבוב BLAKE2B-512 בתצורה רגילה לפי המלצת המפתחים בעמוד הבית של BLAKE. לאחר מימוש המחלקה יש להשתמש בשלוש הפונקציות Initialize,‏ HashCore ו-HashFinal. תחילה קוראים לפונקציה Initialize שצריכה לקבל כארגומנט את בלוק הפרמטרים המתואר לעיל שהוא מערך של 8 מילים באורך 64 ביט. הפונקציה המייצרת את בלוק הקונפיגורציה לא הובאה כאן מפאת חוסר מקום. לצורך הבדיקה אפשר להשתמש בערך ברירת המחדל שהוא  בכניסה הראשונה, כל היתר אפסים. הפונקציה HashCore מקבלת את המידע לגיבוב ו-HashFinal מחזירה את תמצית המידע.
class Blake2B{
   ulong _counter0;
   ulong _counter1;
   ulong _finalizationFlag0;
   ulong _finalizationFlag1;
   int _bufferFilled = 0;
   byte[] _buf = new byte[128];
   ulong[] _m = new ulong[16];
   ulong[] _h = new ulong[8];
   ulong[] _v = new ulong[16];

   const ulong IV0 = 0x6A09E667F3BCC908UL;
   const ulong IV1 = 0xBB67AE8584CAA73BUL;
   const ulong IV2 = 0x3C6EF372FE94F82BUL;
   const ulong IV3 = 0xA54FF53A5F1D36F1UL;
   const ulong IV4 = 0x510E527FADE682D1UL;
   const ulong IV5 = 0x9B05688C2B3E6C1FUL;
   const ulong IV6 = 0x1F83D9ABFB41BD6BUL;
   const ulong IV7 = 0x5BE0CD19137E2179UL;

   private static readonly int[] Sigma = new int[192] {
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
   14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3,
   11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4,
   7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8,
   9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13,
   2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9,
   12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11,
   13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10,
   6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5,
   10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0,
   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
   14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3
   };

   ulong BytesToUInt64(byte[] buf, int offset)
   {
     return
       ((ulong)buf[offset + 7] << 7 * 8 | ((ulong)buf[offset + 6] << 6 * 8) |
       ((ulong)buf[offset + 5] << 5 * 8) | ((ulong)buf[offset + 4] << 4 * 8) |
       ((ulong)buf[offset + 3] << 3 * 8) | ((ulong)buf[offset + 2] << 2 * 8) |
       ((ulong)buf[offset + 1] << 1 * 8) | ((ulong)buf[offset]));
   }

   void UInt64ToBytes(ulong value, byte[] buf, int offset)
   {
     buf[offset + 7] = (byte)(value >> 7 * 8);
     buf[offset + 6] = (byte)(value >> 6 * 8);
     buf[offset + 5] = (byte)(value >> 5 * 8);
     buf[offset + 4] = (byte)(value >> 4 * 8);
     buf[offset + 3] = (byte)(value >> 3 * 8);
     buf[offset + 2] = (byte)(value >> 2 * 8);
     buf[offset + 1] = (byte)(value >> 1 * 8);
     buf[offset] = (byte)value;
   }

   ulong RotateRight(ulong value, int nBits)
   {
     return (value >> nBits) | (value << (64 - nBits));
   }
 
   void G(int a, int b, int c, int d, int r, int i)
   {
     int p = (r << 4) + i;
     int p0 = Sigma[p];
     int p1 = Sigma[p + 1];
     var v = _v;
     var m = _m;
  
     v[a] += v[b] + m[p0];
     v[d] = RotateRight(v[d] ^ v[a], 32);
     v[c] += v[d];
     v[b] = RotateRight(v[b] ^ v[c], 24);
     v[a] += v[b] + m[p1];
     v[d] = RotateRight(v[d] ^ v[a], 16);
     v[c] += v[d];
     v[b] = RotateRight(v[b] ^ v[c], 63);
   }

   void Compress(byte[] block, int start)
   {
     var v = _v;
     var h = _h;
     var m = _m;

     for (int i = 0; i < 16; ++i)
       m[i] = BytesToUInt64(block, start + (i << 3));

     v[0] = h[0]; v[1] = h[1];
     v[2] = h[2]; v[3] = h[3];
     v[4] = h[4]; v[5] = h[5];
     v[6] = h[6]; v[7] = h[7];

     v[8] = IV0; v[9] = IV1;
     v[10] = IV2; v[11] = IV3;
     v[12] = IV4 ^ _counter0;
     v[13] = IV5 ^ _counter1;
     v[14] = IV6 ^ _finalizationFlag0;
     v[15] = IV7 ^ _finalizationFlag1;

     for (int r = 0; r < 12; ++r)
     {
       G(0, 4, 8, 12, r, 0);
       G(1, 5, 9, 13, r, 2);
       G(2, 6, 10, 14, r, 4);
       G(3, 7, 11, 15, r, 6);
       G(3, 4, 9, 14, r, 14);
       G(2, 7, 8, 13, r, 12);
       G(0, 5, 10, 15, r, 8);
       G(1, 6, 11, 12, r, 10);
     }

     for (int i = 0; i < 8; ++i)
       h[i] ^= v[i] ^ v[i + 8];
   }

   public void Initialize(ulong[] config)
   {
     _h[0] = IV0; _h[1] = IV1;
     _h[2] = IV2; _h[3] = IV3;
     _h[4] = IV4; _h[5] = IV5;
     _h[6] = IV6; _h[7] = IV7;

     _counter0 = 0;
     _counter1 = 0;
     _finalizationFlag0 = 0;
     _finalizationFlag1 = 0;

     _bufferFilled = 0;

     Array.Clear(_buf, 0, _buf.Length);

     for (int i = 0; i < 8; i++)
       _h[i] ^= config[i];
   }

   public void HashCore(byte[] array, int start, int count)
   {
     int offset = start;
     int bufferRemaining = 128 - _bufferFilled;

     if ((_bufferFilled > 0) && (count > bufferRemaining))
     {
        Array.Copy(array, offset, _buf, _bufferFilled, bufferRemaining);
       _counter0 += 128;
       if (_counter0 == 0) _counter1++;
       Compress(_buf, 0);
       offset += bufferRemaining;
       count -= bufferRemaining;
       _bufferFilled = 0;
     }

     while (count > 128)
     {
       _counter0 += 128;
       if (_counter0 == 0) _counter1++;
       Compress(array, offset);
       offset += 128;
       count -= 128;
     }

     if (count > 0)
     {
       Array.Copy(array, offset, _buf, _bufferFilled, count);
       _bufferFilled += count;
     }
   }

   public byte[] HashFinal()
   {
     _counter0 += (uint)_bufferFilled;
     _finalizationFlag0 = ulong.MaxValue;
     for (int i = _bufferFilled; i < _buf.Length; i++)
       _buf[i] = 0;
     Compress(_buf, 0);

     byte[] hash = new byte[64];
     for (int i = 0; i < 8; ++i)
       UInt64ToBytes(_h[i], hash, i << 3);
     return hash;
   }}

וקטור בדיקה

BLAKE2b-512("abc") = BA 80 A5 3F 98 1C 4D 0D 6A 27 97 B6 9F 12 F6 E9
                     4C 21 2F 14 68 5A C4 B7 4B 12 BB 6F DB FF A2 D1
                     7D 87 C5 39 2A AB 79 2D C2 52 D5 DE 45 33 CC 95
                     18 D3 8A A8 DB F1 92 5A B9 23 86 ED D4 00 99 23