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

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

בסיום השיעור נכסה:

• מהן פונקציות גיבוב קריפטוגרפיות
• דוגמאות קוד Python המדגימות שימוש בפונקציות גיבוב
• סקירת יישומים של גיבוב קריפטוגרפי
• אבטחת גיבוב קריפטוגרפי
• איומים על אלגוריתמים אלה ממחשבים קלאסיים וקוונטומיים

מבוא לגיבוב קריפטוגרפי

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

הרציונל הבסיסי ועיצוב פונקציות גיבוב

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

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

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

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

1. אחידות: התמציות שמייצרת CHF צריכות להיות מפוזרות באופן אחיד ולהיראות אקראיות. המטרה היא להבטיח שהפלט לא יחשוף מידע על הקלט.
2. דטרמיניזם: עבור קלט נתון, CHF חייבת תמיד לייצר את אותה תמצית, כלומר היא חייבת להיות דטרמיניסטית.
3. בלתי הפיכות: CHF היא פונקציה חד-כיוונית במובן שגם כשנתונה תמצית, צריך להיות בלתי אפשרי מעשית להפוך את הגיבוב ולקבל את הקלט.
4. חד-חד-ערכיות משוערת: בעוד ש-CHFs הן פונקציות רבות-לאחת, הן צריכות להיראות כפונקציות אחת-לאחת. זה מושג על ידי שילוב של מרחב פלט עצום בגודלו עם אפקט המפולת שבו שינויים קטנים בקלט מובילים לתמציות שונות בתכלית. תכונה זו ידועה כחד-חד-ערכיות משוערת.

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

• אם שתי התמציות תואמות, ניתן להיות בטוחים בהסתברות גבוהה שהנתונים זהים למקור.
• אם התמציות שונות, ניתן להיות בטוחים שהנתונים נחבלו או שאינם מקוריים.

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

Mathematical description

ניתן להגדיר פונקציית גיבוב $H$ כ:

$H : Σ^* \rightarrow \{0,1\}^n$

כאשר $Σ^*$ הוא קבוצת כל המחרוזות האפשריות שניתן לראות אותן כמחרוזות בינאריות באורך כלשהו.

העובדה שגודל תחום הקלט $Σ^*$ של $H$ אינו חסום בעוד שזה של הקו-תחום $\{0,1\}^n$ חסום פירושה ש-$H$ הינה בהכרח מיפוי רבות-לאחת הממפה אינסוף קלטים לכל מחרוזת n-ביט נתונה.

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

דוגמה לגיבוב קריפטוגרפי ב-Python עם SHA-256

דוגמה פשוטה זו מדגימה גיבוב קריפטוגרפי באמצעות האלגוריתם הפופולרי SHA-256 כפי שמסופק על ידי ספריית cryptography של Python. ראשית נראה כיצד הבדל קטן בטקסטים פשוטים מוביל להבדל גדול מאוד בתמציות הגיבוב.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

שתי ההודעות שונות בדיוק בתו אחד.

לאחר מכן, אנו מייצרים אובייקטי hash כדי לאפשר את תהליך הגיבוב, הכולל קריאות לשתי מתודות: update ו-finalize.

אנו רואים שבשל אפקט המפולת ב-CHF של SHA-256, הבדל של תו אחד בהודעות קלט מניב שתי תמציות שונות מאוד.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

יישומים של גיבוב קריפטוגרפי

המאפיינים הייחודיים של CHFs הופכים אותן מתאימות למגוון רחב של יישומים:

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

איור 1. גיבוב מאובטח לשלמות נתונים

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

איור 2. חתימות דיגיטליות

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

אבטחת גיבוב קריפטוגרפי

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

עמידות לטרום-תמונה

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

זה קשור לתכונה החד-כיוונית של CHFs.

CHF טובה מתוכננת באופן שצד המעוניין לבצע התקפת טרום-תמונה אין לו ברירה טובה יותר מגישה בכוח גס, שיש לה מורכבות זמן של $2^n$.

mathematical details

בהינתן CHF $H$ ותמצית $g$, צריך להיות בלתי אפשרי חישובית למצוא כל קלט $m$ מטרום-התמונה של $g$ כאשר $H(m) = g$.

עמידות להתנגשות

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

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

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

mathematical details of hash collisions

$m_1, m_2$ ניתנים למציאה כך ש-$H(m_1) = H(m_2)$.

אורך גיבוב

עמידות להתנגשות היא דרישה קשה יותר מעמידות לטרום-תמונה ומחייבת אורכי פלט כפולים מאלה הנחוצים לעמידות לטרום-תמונה. הסיבה לכך היא שהתקפת כוח גס הידועה כהתקפת יום הולדת, שניתן להשתמש בה לזיהוי התנגשויות גיבוב, יש לה מורכבות זמן של $2^{n/2}$.

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

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

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

פונקציית גיבוב	אורך פלט (ביטים)	יישומים נפוצים
MD5	128	בדיקת שלמות קבצים, מערכות ישנות, שימושים שאינם קריפטוגרפיים
SHA-1	160	מערכות legacy, Git לניהול גרסאות
SHA-256	256	מטבע קריפטוגרפי (Bitcoin), חתימות דיגיטליות, אישורים
SHA-3	משתנה (עד 512)	יישומים קריפטוגרפיים שונים, יורש SHA-2
Blake2	משתנה (עד 512)	קריפטוגרפיה, מחליף MD5/SHA-1 בחלק מהמערכות
Blake3	משתנה (עד 256)	קריפטוגרפיה, גיבוב קבצים, שלמות נתונים

• MD5 ו-SHA-1, אמנם עדיין נראים ביישומים פחות רגישים, נחשבים מיושנים מבחינת עמידות להתנגשות ואינם מומלצים למערכות חדשות. SHA-256, חלק ממשפחת SHA-2, נמצא בשימוש נרחב ומאובטח כיום עבור רוב היישומים.
• SHA-3 הוא תקן חדש יותר שנבחר על ידי NIST ב-2015 כזוכה בתחרות פונקציות הגיבוב של NIST. הוא מיועד להוות תחליף ישיר ל-SHA-2, אך יש לו גם כמה מאפיינים פנימיים שונים והוא עמיד לסוגים מסוימים של התקפות שעשויות להיות יעילות נגד SHA-2.
• Blake2 ו-Blake3 הן פונקציות גיבוב קריפטוגרפיות מהירות יותר מ-MD5, SHA-1, SHA-2 ו-SHA-3, אך לפחות מאובטחות כמו התקן האחרון, SHA-3. הן נמצאות בשימוש גובר במערכות חדשות, בפרט כאשר מהירות חשובה.

סיכוני קוונטום לגיבוב קריפטוגרפי מסורתי

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

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

עם $n$ ביטים בקלט, ישנם $2^n$ ערכים אפשריים. לכן, התוקף צריך לנסות כ-$2^{n-1}$ קלטים כדי שיהיה לו סיכוי של יותר מ-50% להצליח.

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

עבור הקשר חיפוש לא מובנה כזה, אלגוריתם גרובר יכול לספק האצה ריבועית באמצעות טכניקה הידועה כהגברת אמפליטודה קוונטומית, תוך הפחתת מורכבות הזמן של התקפת טרום-תמונה ל-$2^{n/2}$.

מעשית, פירוש הדבר הוא שCHF בת 256 ביט, הנחשבת כיום מאובטחת נגד התקפות טרום-תמונה על ידי מחשבים קלאסיים, תספק את אותה רמת אבטחה כמו CHF בת 128 ביט מול תוקף קוונטומי המשתמש באלגוריתם גרובר.

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

לדוגמה, במקרה של SHA-256, ביצוע בסדר של $2^{128}$ פעולות לביצוע התקפת טרום-תמונה בסיוע גרובר עדיין יהיה בלתי אפשרי מעשית בעתיד הנראה לעין.

אלגוריתם BHT

אלגוריתם קוונטומי המשלב היבטים של התקפת יום הולדת עם חיפוש גרובר הוצע ב-1997 על ידי Brassard, Høyer ו-Tapp (BHT) ומאפשר סיבוכיות תיאורטית של $O(2^{n/3})$ למציאת התנגשויות גיבוב. עם זאת, סיבוכיות משופרת זו מותנית בקיום טכנולוגיית זיכרון גישה אקראית קוונטומי QRAM, שכרגע אינה קיימת.

ללא QRAM, הסיבוכיות הניתנת למימוש היא $\tilde{O}(2^{2n/5})$ ועבור אורכי גיבוב הנמצאים כיום בשימוש, שיפור שולי זה ביכולת מציאת התנגשויות ביחס להתקפת יום הולדת אינו מהווה איום קריטי.

סיכום

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

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

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

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