לדלג לתוכן

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[1] פותחה על ידי Jean-Philippe Aumasson,‏ Luca Henzen,‏ Willi Meier ו-Raphael C.-W. Phan. בתחילה נקראה BLAKE-xx כאשר xx הוא 28, 32, 48 או 64. ב-2010 שונה השם לקראת ההגשה לתחרות כדי להבדילו מהגרסה המקורית. BLAKE2[2] שהוצעה בטיוטה RFC 7693 פותחה בדצמבר 2012 על ידי Jean-Philippe Aumasson,‏ Samuel Neves,‏ Zooko Wilcox-O’Hearn, ו-Christian Winnerlein.

שתיהן חופשיות לשימוש ואינן מוגנות בפטנט. לא ידוע על קריפטואנליזה מוצלחת שלהן והן נחשבות לבטוחות. כמו כן פורסמו מספר גרסאות מוחלשות של מועמד SHA-3 הנקראות "גרסאות צעצוע" לצורך קריפטואנליזה (BLOKE,‏ FLAKE,‏ BLAZE ו-BRAKE). קיימים מימושים חופשיים של הפונקציות השונות בשפת C,‏ C++‎ ו-C#‎ בין היתר אפשר למצוא ב-GitHub[3][4] וכן מימוש לשפת VHDL[5].

תיאור הפונקציה הפנימית של BLAKE שהיא וריאציה של צופן הזרם ChaCha. הפונקציה מקבלת ארבע מילים ומחזירה ארבע מילים לאחר עיבוד מקבילי עם שילוב של שלוש פעולות אריתמטיות: חיבור, הזזה מעגלית ו-XOR הידוע בקיצור "ARX". שילוב זה הוכח כבטוח הן מפני קריפטואנליזה דיפרנציאלית והן מפני התקפות ערוץ צדדי.

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

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

[עריכת קוד מקור | עריכה]

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

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

עקרונות הפיתוח והתכנון של פונקציית הגיבוב BLAKE הם:

  • פשטות ומהירות הן בחומרה והן בתוכנה.
  • פרמטרים דומים ל-SHA-2.
  • אורך מסר מקסימלי סיביות.
  • תמיכה בתוספת גיוון (Salt) לאקראיות.
  • תמיכה במקביליות.
  • איזון גמיש בין תפוקה לדרישות זיכרון.
  • התאמה לסביבה מוגבלת במשאבים.
  • עמידות נגד "מציאת מקור נוסף" (Second preimage resistance).
  • עמידות נגד התקפת ערוץ צדדי.

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

תיאור כללי

[עריכת קוד מקור | עריכה]

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

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

הערכים ההתחלתיים של BLAKE לקוחים מתקן SHA-2:

,
,
,
,

ב-BLAKE-256 יש 16 קבועים שהם ספרות פאי בנקודה כלשהי:

, , ,
, , ,
, , ,
, ,

בנוסף כל פונקציות משפחת BLAKE משתמשות בטבלת התמורות הבאה:

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

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

פונקציית דחיסה

[עריכת קוד מקור | עריכה]
תיאור סדר הפעולות של הפונקציה הפנימית

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

  • ערך ביניים שהוא מערך של 8 מילים .
  • קלט המכיל 16 מילים .
  • גיוון המכיל 4 מילים .
  • מונה המכיל שתי מילים .

בסך הכול מונים הפרמטרים 30 מילים (120 בתים). פלט הפונקציה הוא ערך ביניים חדש המכיל 8 מילים, כלומר:

.

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

[עריכת קוד מקור | עריכה]

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

פונקציית הסבב

[עריכת קוד מקור | עריכה]

פונקציית הדחיסה מבצעת 14 סבבים בהם היא מעבדת את המצב לפי הפירוט הבא:

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

בכל סבב הקריאה לפונקציה מבצעת את החישוב הבא:

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

ערך הביניים מועבר מסבב לסבב והוא מחולץ מהמצב הפנימי ונדחס ל-8 מילים כך:

אם נתון הקלט באורך סיביות, הקלט תחילה מרופד לפי כלל הריפוד של HAIFA. תחילה מוודים שאורכו יהיה שקול ל-447 מודולו 512. תחילה מוסיפים '1' בסוף ומשלימים באפסים כמידת הצורך. לכל היותר נוספים 512 סיביות. לאחר מכן מוסיפים סיבית '1' נוספת ואחריה מספר שלם באורך 64 סיביות המייצג את . לסיכום:

.

כך מובטח שאורך הקלט בסיביות יהיה כפולה של 512.

גיבוב המסר

[עריכת קוד מקור | עריכה]

הקלט המרופד מחולק ל- בלוקים באורך 16 מילים כל אחד . ויהי מערך שלמים המייצגים את מספר סיביות המצטבר של הקלט לא כולל הריפוד. למשל אם המסר המקורי הוא באורך 600 סיביות, יתקבלו שני בלוקים כאשר הבלוק הראשון באורך 512 לכן הבלוק הנותר חלקי ואורכו הוא רק 88 סיביות לכן . אם המסר הוא כפולה של 512 או שהבלוק האחרון גדול מ-447 סיביות, יש צורך להוסיף בלוק ריק לצורך הריפוד והמספר המייצג את אורך המסר, לכן יוצא שהשלם האחרון הוא . כלומר הבלוק האחרון אינו כולל סיביות מהמסר כלל אלא רק ריפוד וקידוד האורך. ה-Salt הוא אופציונלי ואם אין שימוש בו . גיבוב המסר מתבצע כך:

תמצית המסר היא שהוא ערך הביניים האחרון.

BLAKE-512 דומה ל-BLAKE-256 למעט השינויים הבאים. הערכים ההתחלתיים הם מתוך SHA-512:

הקבועים הם:

,
,
,
,
,
,
,
,

פונקציית הדחיסה היא בסגנון פונקציית Quarter Round של צופן ChaCha אך בתוספת קבועים לפי הטבלה כדלהלן:

טבלת התמורה ופונקציות הסבב זהים ל-BLAKE-256. ההבדל היחידי הוא באורך המשתנים ומספר הסבבים. ב-BLAKE-512 מתבצעים 16 סבבים והמשתנים כולם באורך 64 סיביות. הכנת המסר היא לפי כלל ריפוד דומה. אורכו הכולל צריך להיות שקול ל-895 סיביות מודולו 1024, מוסיפים '1' בסוף המסר ואפסים לפי הצורך ולבסוף מוסיפים '1' נוסף ואחריו את אורך המסר המקודד כמספר שלם באורך 128 סיביות לפי סדר בתים גדול. כך שלבסוף יתקבל קלט באורך שהוא כפולה של 1024.

BLAKE-224 זהה ל-BLAKE-256 למעט שני שינויים. הערכים ההתחלתיים הם:

משמיטים את ה-'1' הנוסף בריפוד המסר לפני קידוד האורך:

.

BLAKE-384 מתאים ל-BLAKE-512 למעט השינויים הבאים. הערכים ההתחלתיים הם:

,
,
,
,

וכן בריפוד המסר משמיטים את ה-'1' הנוסף. כלומר:

.

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

[עריכת קוד מקור | עריכה]

מספר הפעולות של 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 ובצפנים אחרים והוכח שהוא בטוח נגד קריפטאנליזה דיפרנציאלית[6] וכן נגד התקפות ערוץ צדדי[7][8].

HAIFA הוא מבנה משופר גנרי לפונקציית גיבוב הפועל כמו מבנה מרקל דמגרד אך עם Salt ומונה והוכח כבטוח יותר. המבנה מציע עמידות נגד התקפות ידועות על פונקציות גיבוב. מציאת התנגשויות, מציאת מקור שני, התקפת יום-הולדת, הטכניקה של Joux למציאת התנגשויות מרובות[9][10].

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

[עריכת קוד מקור | עריכה]

אפשר לשלב את BLAKE בקוד אימות מסרים כמו ב-HMAC או UMAC. למשל:

.

שימוש דומה ניתן לעשות ב-BLAKE כדי לבנות פונקציה פסאודו אקראית או מחולל פסאודו אקראי, לדוגמה:

או

כאשר הוא מונה כלשהו המקודד בדרך מוסכמת ומשורשר למסר.

אף על פי שפונקציית הגיבוב SHA-3 התקנית טובה היא אינה נותנת מענה לכל לצרכים. לפעמים יש צורך בפונקציית גיבוב מהירה בתוכנה לבדיקת שלמות וסינון כפילויות במערכת קבצים ואחסון ענן, מערכת איתור פריצות, ניהול גרסאות או שיטות אתחול (Boot) בטוח. יישומים אילו לרוב מגבבים קבצים קטנים מאוד בכמות רבה, מה שהתקן אינו מביא בחשבון ועשוי להשפיע על ביצועי המערכת וחוויית המשתמש. מסיבה זו מערכות רבות עדיין משתמשות באלגוריתמים ישנים ולא מומלצים כמו MD5 שהוא מהיר כמעט פי שלושה מ-SHA-2 אך ידוע כפגיע להתקפת התנגשויות[11] והוצא משימוש כל התקנים לצורך קריפטוגרפי. למרות זאת בגלל שיקולי יעילות מערכות ידועות עדיין משתמשות בו לבדיקת שלמות. דוגמאות הן: מערכת הקבצים ZFS של אורקל, OpenStack, ניהול גרסאות Perforce ואפילו מערכות חדשות כמו מערכת אחסון אובייקטים של AOL. כדי לתת מענה לבעיה זו פותחה BLAKE2 שהיא גרסה רזה וקלילה של BLAKE ממנה הוסרו מספר אלמנטים המכבידים על יעילותה ואין הוכחה שקיומם מחזק את ביטחון האלגוריתם. לפי בוחן ביצועים של eBACS[12] באופן כללי BLAKE מהירה יותר מ-SHA-3 אך איטית בהשוואה ל-MD5. החידוש ב-BLAKE2 הוא המהירות הרבה אף יותר מ-MD5 בעוד שהיא אינה נופלת בביטחונה מ-SHA3 (לפי הצהרת המפתחים). למשל בביצועי תוכנה על מעבד Sandy Bridge 3.1GHz של אינטל ישראל, BLAKE2 מצליחה לגבב 890 מגה בית לשנייה לעומת רק 144 מגה לשנייה עם SHA3-512.

להלן תקציר החידושים והשיפורים ב-BLAKE2 לעומת הפונקציות הקודמות באותה משפחה:

  • מהירות גבוהה על פלטפורמת 64 ביט (אף יותר מ-MD5).
  • מקביליות גבוהה יותר על מעבדים מרובי ליבות תוך ניצול סט פקודות SIMD חדשות.
  • גיבוב בתצורת עץ לאימות קבצים גדולים.
  • PrefixMAC שהוא קוד אימות מסרים מבוסס BLAKE2 המהיר מ-HMAC.
  • פרסונליזציה. לצורך מתן ייחודיות ברמת משתמש.
  • ריפוד מינימלי.

BLAKE2 מגיע בשתי גרסאות:

  • BLAKE2b אופטימלי למעבדי 64 ביט ומעבדי ARM המייצר תמצית באורך של עד 64 בתים.
  • BLAKE2s אופטימלי למעבדי 8 או 32 ביט המייצר תמצית באורך של עד 32 בתים.

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

ההבדלים בין BLAKE2 ל-BLAKE

[עריכת קוד מקור | עריכה]
  1. פחות סבבים. הפונקציה הפנימית של BLAKE2s מבצועת רק 10 פעמים והפונקציה הפנימית של BLAKE2b מבוצעת רק 12 פעמים. הסיבה שבגרסאות הקודמות הוצע מספר סבבים גדול יותר (14 ו-16 בהתאמה) נבע רק מהרצון להיות שמרניים ולספק שולי ביטחון גבוהים ולא בגלל קריפטואנליזה מוצקה. השינוי הזה מהותי ומניב שיפור של בין 25 ל-29 אחוז בביצועים בעיקר על קלטים ארוכים לעומת הגרסאות הקודמות ואין סימנים המעידים שביטחון הפונקציה נחלש עקב כך.
  2. הזזות אופטימליות לצורך מהירות. הפונקציה הפנימית מבצעת הזזה מעגלית לשמאל בהיסטים הקבועים: 24, 11, 63. השינוי של ההזזה הראשונה מ-25 ל-24 נובע מסיבות טכניות כי נדרשות פחות הוראות מעבד. השינוי מ-64 ל-63 מוסיף גם הוא במהירות במיוחד שאפשר לראות בהזזה זו כהזזה אחת ימינה במקום 63 שמאלה שהן למעשה שקולות על משתנה 64 סיביות ולכן עשויה להיות מהירה יותר.
  3. ריפוד מינימלי. הריפוד שונה כך שרק אם יש צורך מוסיפים בתים ריקים לסוף המסר. אם אורך הקלט מתחלק באורך הבלוק, לא מבוצע ריפוד כלל. כדי למנוע נקודות תורפה בעקבות השינוי (כי כעת אפשר לבצע התקפות מסוימות שמנצלות את העובדה שהמסר יכול להיות חלק ממסר אחר ארוך יותר), מוחלף כלל הריפוד בשני "דגלי סיום" ו- הנמצאים בבלוק הראשון. כאשר עבור כל הבלוקים למעט האחרון שאז . הדגל נועד לאותת על הצומת האחרון בעץ הגיבוב במקרה של גיבוב בצורת עץ, כאשר מגיעים לבלוק האחרון .
  4. פחות קבועים. BLAKE2 עושה שימוש בשמונה קבועים בלבד. שינוי זה חוסך ב-128 בתים הן ב-RAM והן ב-ROM ב-BLAKE2b ו-64 בתים ב-BLAKE2s.
  5. סדר בתים קטן. BLAKE2 מפרשת את הקלט לפי סדר בתים קטן כמו MD5 ולא כמו ב-SHA-3 זאת מפני שפלטפורמות רבות פועלות לפי סדר בתים קטן, בעיקר AMD ואינטל.
  6. מונה בתים ולא סיביות. המונה סופר את בתי המסר ולא סיביות המסר, הסיבה לכך טכנית היא מפשטת את היישום ומונעת באגים.
  7. הגיוון מעובד רק פעם אחת. בניגוד לקודמה BLAKE2 טוענת את ה-Salt רק פעם אחת בתחילת הגיבוב כמו וקטור אתחול במקום כקלט לפונקציית הדחיסה בכל סבב. עובדה שחוסכת מעט פעולות ומעט זיכרון. פונקציית דחיסה נטולת Salt מפחיתה בביטחון האלגוריתם באופן שולי.
  8. תוספת בלוק פרמטרים. כדי להתאים את BLAKE2 לשימוש ב-Salt מבלי הצורך להכניסו לפונקציית הדחיסה, נוסף "בלוק פרמטרים" או "בלוק קונפיגורציה" שמחובר תחילה ב-XOR עם ה-IV ומעובד ראשון. בתוך בלוק הפרמטרים מקודדים את כל הפרמטרים החיוניים לפעולת הפונקציה בתצורה הנדרשת; כגון Salt, מפתח הצפנה אם קיים, תמיכה בתצורת גיבוב עץ, אורך תמצית המסר, פרסונליזציה וכדומה.

אתחול פונקציית הדחיסה שונה בהתאם:

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

הפונקציה הפנימית של BLAKE2b (משמאל) ו-BLAKE2s מוצגת להלן:

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

בלוק פרמטרים

[עריכת קוד מקור | עריכה]

בלוק הפרמטרים מכיל 32 בתים עבור BLAKE2s ו-50 בתים עבור BLAKE2b המחולקים למקטעים המייצגים את הנתונים הבאים:

  • אורך התמצית בבתים (עד 32 בתים במקרה של BLAKE2s ועד 64 בתים במקרה של BLAKE2b).
  • אורך מפתח הצפנה בבתים. בית אחד בטווח (נקבע ל-0 אם אין מפתח).
  • Salt. מערך של 8 בתים אקראיים עבור BLAKE2s ו-16 בתים עבור BLAKE2b.
  • פרסונליזציה. 8 או 16 בתים בהתאמה של פרטים ייחודיים למשתמש (יכול להיות ריק).

פרמטרים המתאימים לשימוש בתצורת עץ (אם לא משתמשים במצב עץ מאפסים את כל השדות):

  • דרגת העץ (Fanout). בית אחד בטווח (הערך 0 מייצג רוחב בלתי מוגבל).
  • עומק העץ. בית אחד בטווח . (הערך 255 מייצג עומק בלתי מוגבל).
  • אורך עלה בבתים. 4 בתים המייצגים מספר שלם בטווח .
  • אופסט הצומת. 6 או 8 בתים המייצגים מספר שלם בטווח או במקרה של BLAKE2b. נקבע ל-0 במקרים הבאים: בעלים, בצומת הראשון, בצומת השמאלי ביותר או במצב סדרתי (לא בתצורת עץ).
  • גובה הצומת. בית אחד המייצג מספר שלם בטווח . רלוונטי רק בתצורת עץ ושווה 0 בעלים.
  • אורך הגיבוב הפנימי בבתים. בית שלם המייצג מספר בטווח או בהתאמה.

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

טבלת חלוקת בתים בבלוק הקונפיגורציה של BLAKE2b:

אופסט בבתים 0 1 2 3
0 אורך התמצית אורך המפתח רוחב העץ עומק העץ
4 אורך עלה
8...12 אופסט צומת
16 עומק הצומת אורך פנימי שמור לשימוש עתידי
20 ... 28 שמור לשימוש עתידי
32 ... 44 Salt
48 ... 60 פרסונליזציה

טבלת חלוקת בתים בבלוק הקונפיגורציה של BLAKE2s:

אופסט בבתים 0 1 2 3
0 אורך התמצית אורך המפתח רוחב העץ עומק העץ
4 אורך עלה
8 אופסט צומת
12 אופסט צומת (המשך) עומק הצומת אורך פנימי
16 ... 20 Salt
24 ... 28 פרסונליזציה

למשל אם הקונפיגורציה כוללת אורך תמצית 64 בתים (40 בייצוג הקסדצימלי) והיא כוללת מפתח הצפנה באורך 32 בתים (20 בייצוג הקסדיצמלי), גיוון (Salt) - מחרוזת המכילה את הספרה "5" בסך הכול 32 פעמים ופרסונליזציה המכילה את האות "e" בסך הכול 32 פעמים. כאמור היות שהתצורה אינה במבנה עץ רוחב ועומק שווים 1 וכל יתר הפרמטרים 0. הבלוק ייראה כך:

40200101 00000000 00000000 00000000 00000000 00000000 00000000 00000000
55555555 55555555 55555555 55555555 eeeeeeee eeeeeeee eeeeeeee eeeeeeee

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

[עריכת קוד מקור | עריכה]

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

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

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

קוד לדוגמה

[עריכת קוד מקור | עריכה]

להלן קוד שלם בשפת C#‎ של פונקציית הגיבוב BLAKE2B-512 בתצורה רגילה לפי המלצת המפתחים בעמוד הבית של BLAKE[13]. לאחר מימוש המחלקה יש להשתמש בשלוש הפונקציות 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

הערות שוליים

[עריכת קוד מקור | עריכה]
  1. ^ SHA-3 proposal BLAKE
  2. ^ BLAKE2 - fast secure hashing
  3. ^ Reference implementation of the SHA-3 finalist BLAKE
  4. ^ Reference source code package of BLAKE2
  5. ^ HLS-ready C Source Code for the SHA-3 Round 3 Candidates - ARC 2015 Conference Release, April 2015
  6. ^ Jean-Philippe Aumasson, Simon Fischer, Shahram Khazaei, Willi Meier, and Christian Rechberger. New features of Latin dances: analysis of Salsa, ChaCha, and Rumba. In FSE, 2008
  7. ^ Thomas Peyrin. Security analysis of extended sponge functions. Talk at the workshop Hash functions in cryptology: theory and practice, 2008
  8. ^ Erik Zenner. Cache timing analysis of HC-256. In SASC 2008 – The State of the Art of Stream Ciphers. ECRYPT, 2008
  9. ^ Antoine Joux. Multicollisions in iterated hash functions. application to cascaded constructions. In CRYPTO, 2004.
  10. ^ Jean-Philippe Aumasson. Faster multicollisions. In INDOCRYPT 2008, 2008.
  11. ^ Stevens, M., Sotirov, A., Appelbaum, J., Lenstra, A.K., Molnar, D., Osvik, D.A., de Weger, B.: Short chosen-prefix collisions for MD5 and the creation of a rogue CA certificate. In Halevi, S., ed.: CRYPTO. Volume 5677 of LNCS., Springer (2009)
  12. ^ Implementation comparison BLAKE2b
  13. ^ BLAKE2b