iT邦幫忙

2025 iThome 鐵人賽

DAY 4
0
Software Development

深入一點點認識 Git系列 第 4

Day 4-深入一點點認識 Git:那些 Git 物件的雜湊碼是怎麼算出來的?

  • 分享至 

  • xImage
  •  

在 Day 3 的文章尾聲,我們發現:就算檔名不同,只要內容相同,就會產出一樣的雜湊碼,例如:

https://ithelp.ithome.com.tw/upload/images/20250904/20178513tB5g34kYpa.png

empty1.txtempty2.txt 都是空文字檔,產出的雜湊碼都是 e69de29...,由此我們可以發現,這雜湊碼並非隨機產生的亂碼,而是經歷一套規則產生。

安全雜湊演算法

英文全名為 Secure Hash Algorithm,簡稱 SHA,是由美國國家標準技術研究所(National Institute of Standards and Technology,簡稱 NIST)頒布的標準,這些雜湊函式共有下列五大目標:

  1. 輸入相同,則輸出也要相同:如上述範例所示,只要輸入內容一樣,跑出來的雜湊碼也要一樣,不能同樣內容進去,卻跑出不同結果。
  2. 輸出長度永遠相同:不論輸入是沒有任何內容、少少的位元資料或一筆龐大資料,最終產生的雜湊碼必為 40 位數。
  3. 雪崩效應(avalanche effect):哪怕輸入只發生了微小的改變,輸出結果也要大大不同。
  4. 無法逆向破解:不能像線性函數 y = ax + b 這樣能用 x = (y-b)/a 去反推輸入,才能確保安全性。
  5. 均勻分布、避免碰撞:若輸入相異、輸出卻相同稱為「雜湊碰撞(hash collision)」,演算法應避免這樣的碰撞產生。

要同時達成上述四條件感覺好玄,這演算法到底是有什麼神奇魔力,可以達成以上五大目標?讓我們以 git 最開始使用的 SHA-1 雜湊(SHA 的其中一種版本)流程,來看看這加密雜湊函式到底在變什麼魔法。

SHA-1 演算法流程

以上述空白檔案為例,在進入 SHA-1 演算法本體前,會變成:

<object type> <size><\0><content>

這裡建立的 <object type> 是 blob、<size> 為 0、<content> 為空,因此代換後變成:

blob 0\0

這個 blob 0\0 便是 SHA-1 函數的輸入。

值得留意的是,當中包含的資訊僅有「內容」與「內容長度」,而沒有檔案名稱等元資料,因此,文章最開始範例的 empty1.txtempty2.txt 雖然檔名不同,但因為內容一樣(皆為空檔案)、內容長度也一樣(皆為 0),兩者又都是要建立 blob 物件,因此,送進去 SHA-1 函數的輸入自然也一樣,

進入 SHA-1 演算法核心

在取得 blob 0\0 這輸入後,要先對照 ASCII 表轉換成十進制數字(\0為終止符號,因此 ASCII 碼為 0):

98 108 111 98 32 48 0

接著再將十六進制數字轉為二進制:

1100010 1101100 1101111 1100010 100000 110000 0

每個數字應有八位元,若不足八位元,則補上前導 0:

01100010 01101100 01101111 01100010 00100000 00110000 00000000

然後再把這些數字串起來:

01100010011011000110111101100010001000000011000000000000

接下來的步驟沒辦法在有限篇幅中以實例呈現,讓我們改以圖示說明觀念。

目前我們在圖示左上角的紅色星星處,後續步驟號碼可對照下方文字說明:

https://ithelp.ithome.com.tw/upload/images/20250904/20178513KBVqnPLJco.png
SHA-1 演算法流程圖解

  1. 在二進制數字最後補 1 表示終結,後面再補 0 至總長度以 512 模除會得 448 為止(也就是除以 512 後的餘數是 448,這樣再加上 64 就可以被 512 整除)。
  2. 把剛剛的二進制數字的「總長度」這個值轉為二進制,再將總長度值二進制的數字往前補 0 至總長度為 64 位元。
  3. 第 1. 步得到的長度差 64 位元可被 512 整除、第 2. 步得到的長度就是 64 位元,兩者組合成一個總長度為 512 倍數的二進制數字。
  4. 把 3. 組合出的二進制數字,以 512 位元為單位,拆成多個小塊。
  5. 把 4. 拆出來的 512 位元小塊,再個拆成 16 個長度為 32 位元的小塊。
  6. 第 5. 步拆出的 32 位元小塊經多次 XOR 位元運算後,小塊數量從 16 個變 80 個。
  7. H0 H1 H2 H3 H4 五個十六進制的數字,與 6. 產生的 80 個小塊做多輪超級複雜的位元運算,產生新的 H0 H1 H2 H3 H4
  8. 把新 H0 H1 H2 H3 H4 串在一起,就是最終的雜湊碼。

這些步驟已經讓人看得頭昏眼花,但其實以上說明還忽略了非常多細節,其中又以第 7. 步最為複雜。若對當中的詳細流程有興趣,可參考 ajalt/python-sha1 這個 GitHub 倉儲,以 Python 程式碼實現 SHA-1 的運算過程。

或者我們可以單純做個實驗觀察,透過 git clone 取得該倉儲後,以終端機指令 printf 提供 blob 0\0 的格式化標準輸出給 sha1.py 當引數,即可得空 blob 物件會產生的雜湊碼 e69de29...

https://ithelp.ithome.com.tw/upload/images/20250904/20178513aDCvIWU84f.png

SHA-1 如何達到雜湊演算法五大目標

在對 SHA-1 流程有基本認識後,我們可以用直觀的方式,大致感受這演算法如何達成上述的五大目標(嚴謹的數學證明屬於密碼學範疇,大幅超越 git 文章所要探討的難度):

  1. 輸入相同,則輸出也要相同:所有輸入都是經過「固定步驟」走到最後,只要輸入內容一樣,也都經過一樣的運算流程,則輸出結果必相同。
  2. 輸出長度永遠相同:最終輸出仰賴在第 7. 步對 H0 H1 H2 H3 H4 的大量複雜運算,但不管怎麼算,這五個數都是 8 位數,等到第 8. 步串在一起,則必為 40 位數。
  3. 雪崩效應:輸入拆成多個小塊後會加大運算量,且過程中有多個步驟依賴前面的運算結果,導致輸入的些微差距被放大再放大。
  4. 無法逆向破解:許多小步驟依賴前面的運算結果,且過程中每次的模運算都會丟失一些資訊,讓逆向推導無法達成。
  5. 均勻分布、避免碰撞:過程經過補 0、拆小塊、多重位元運算等步驟,在發明時被認為能有效避免碰撞發生。

值得留意的是,這五大目標的第 5. 點「均勻分布、避免碰撞」已隨著運算技術進步而被破解,因此 SHA-1 現在已被認為是不安全的雜湊演算法,連 git 都在其官方頁面中提及,要從 SHA-1 轉換到更安全的 SHA-256。

所以為什麼要用 SHA 碼當 Git 識別碼?

我們花了很多篇幅在講 SHA-1 是怎麼算的,但回到最根本的問題是:為什麼 git 要用雜湊碼當識別碼?難道用簡單一點的編號方式,產生每個 git 物件的識別碼不好嗎?還是有什麼資安考量?

來看看 git 官方文件怎麼說的

Git 在官方文件中提到使用雜湊碼具有以下兩優點:

  1. 檢查完整性相對容易:因為雪崩效應,哪怕只是一個位元反轉,產生的變化會非常大,因此,若資料有異動,可以很容易察覺。
  2. 尋找物件很快:在沒有雜湊衝突的情況下,一組代碼就代表唯一的物件,因此,要找到目標 git 物件非常快。

有了上述兩點特性,一組雜湊碼就能代表唯一且不可變的項目。

來聽聽 Git 發明人 Linus 怎麼說的

雖然上述 git 文件另有提及使用雜湊碼在資安上的額外好處,但在《Tech Talk: Linus Torvalds on git》這場演講中,git 的發明人 Linus Torvalds 則特別強調:使用雜湊碼不是用來處理資安議題,而是要確保資料的一致性。

這就呼應剛剛在文件裡得出的結論:一組雜湊碼就能代表唯一且不可變的項目,當多人協作或橫跨不同平臺時,我們都可以知道「這組雜湊碼對應的檔案內容就是長這樣」,哪怕數年後再把檔案放到其他地方儲存,只要雜湊碼不變,我們就能確定這份檔案(或者說 git 物件)裡面是連「一個位元都沒有被動過」。

小結

Git 使用密碼學中的 SHA 雜湊碼來當作物件的識別,並不是有特別的資安考量,而是可用來確保檔案的一致性。

參考資料

  1. 【冷知識】那個長得很像亂碼 SHA-1 是怎麼算出來的?
  2. 數論與密碼學 (Python, JavaScript)
  3. ASCII 表
  4. ajalt/python-sha1
  5. Shell printf 命令
  6. SHA-1 是什麼?為什麼不再安全?
  7. Migrate Git from SHA-1 to a stronger hash function.
  8. We have broken SHA-1 in practice.
  9. Why does Git use a cryptographic hash function?
  10. Tech Talk: Linus Torvalds on git

上一篇
Day 3-深入一點點認識 Git:什麼是 Git 物件?
下一篇
Day 5-深入一點點認識 Git:上層瓷器指令複習(本地端未開分支流程)
系列文
深入一點點認識 Git6
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言