北京建設(shè)住房和城鄉(xiāng)建設(shè)官網(wǎng),蘇州百度 seo,深圳優(yōu)定軟件網(wǎng)站建設(shè),網(wǎng)站建設(shè)方案怎么做各位同學(xué)#xff0c;大家好。今天我們將深入探討一個(gè)在高性能計(jì)算和系統(tǒng)安全領(lǐng)域都至關(guān)重要的話(huà)題#xff1a;JavaScript 集合操作中的哈希碰撞。我們將一同揭開(kāi) Map 和 Set 這些看似高效的數(shù)據(jù)結(jié)構(gòu)背后#xff0c;潛在的性能陷阱——哈希碰撞攻擊#xff0c;以及攻擊者如何…各位同學(xué)大家好。今天我們將深入探討一個(gè)在高性能計(jì)算和系統(tǒng)安全領(lǐng)域都至關(guān)重要的話(huà)題JavaScript 集合操作中的哈希碰撞。我們將一同揭開(kāi)Map和Set這些看似高效的數(shù)據(jù)結(jié)構(gòu)背后潛在的性能陷阱——哈希碰撞攻擊以及攻擊者如何利用“特殊鍵”將它們的平均 O(1) 性能降級(jí)到最壞情況下的 O(N)。這個(gè)主題不僅僅是理論探討它關(guān)系到您構(gòu)建的應(yīng)用程序的健壯性和抵抗惡意攻擊的能力。尤其是在 Node.js 環(huán)境中服務(wù)器端的性能瓶頸可能導(dǎo)致服務(wù)拒絕DoS攻擊影響用戶(hù)體驗(yàn)?zāi)酥翗I(yè)務(wù)連續(xù)性。第一章哈希表基礎(chǔ)高效的秘密在深入探討攻擊之前我們必須先理解Map和Set的核心工作原理哈希表Hash Table也稱(chēng)為散列表。正是這種數(shù)據(jù)結(jié)構(gòu)賦予了它們?cè)谄骄闆r下極高的存取效率。1.1 什么是哈希表哈希表是一種通過(guò)哈希函數(shù)將鍵key映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄的數(shù)據(jù)結(jié)構(gòu)。它直接通過(guò)索引訪(fǎng)問(wèn)數(shù)據(jù)因此查找速度非常快。一個(gè)哈希表主要由以下幾個(gè)部分組成哈希函數(shù)Hash Function將任意大小的鍵轉(zhuǎn)換為固定大小的整數(shù)這個(gè)整數(shù)就是哈希值。哈希表Table/Array一個(gè)實(shí)際存儲(chǔ)數(shù)據(jù)的數(shù)組哈希值通常被用來(lái)計(jì)算這個(gè)數(shù)組的索引桶索引。桶Bucket哈希表中的每個(gè)位置可以存儲(chǔ)一個(gè)或多個(gè)鍵值對(duì)。1.2 哈希函數(shù)的理想特性一個(gè)好的哈希函數(shù)對(duì)于哈希表的性能至關(guān)重要。它應(yīng)該具備以下特性確定性相同的鍵輸入必須始終產(chǎn)生相同的哈希值。均勻分布哈希函數(shù)應(yīng)該將不同的鍵盡可能均勻地分布到哈希表的各個(gè)桶中減少碰撞。快速計(jì)算哈希函數(shù)的計(jì)算成本應(yīng)該很低否則會(huì)抵消哈希表帶來(lái)的性能優(yōu)勢(shì)。不可逆性可選但對(duì)于安全哈希函數(shù)很重要從哈希值難以反推出原始鍵。抗碰撞性可選但對(duì)于安全哈希函數(shù)很重要難以找到兩個(gè)不同的鍵產(chǎn)生相同的哈希值。在 JavaScript 引擎中哈希函數(shù)的設(shè)計(jì)極其復(fù)雜和精妙它們不僅要滿(mǎn)足上述性能要求還要對(duì)抗?jié)撛诘墓簟?.3 碰撞與沖突解決盡管哈希函數(shù)力求均勻分布但由于鍵的數(shù)量可能遠(yuǎn)大于桶的數(shù)量或者哈希函數(shù)本身并非完美不同的鍵映射到同一個(gè)桶的情況是不可避免的這被稱(chēng)為哈希碰撞Hash Collision。處理哈希碰撞是哈希表設(shè)計(jì)的核心挑戰(zhàn)之一。常見(jiàn)的碰撞解決策略有兩種開(kāi)放尋址法Open Addressing當(dāng)發(fā)生碰撞時(shí)探測(cè)哈希表中的其他位置直到找到一個(gè)空閑位置為止。常見(jiàn)的探測(cè)方法有線(xiàn)性探測(cè)、二次探測(cè)等。鏈地址法Chaining這是 JavaScript 引擎如 V8中最常用的方法。每個(gè)桶不再直接存儲(chǔ)鍵值對(duì)而是存儲(chǔ)一個(gè)鏈表或另一個(gè)動(dòng)態(tài)數(shù)組。當(dāng)發(fā)生碰撞時(shí)新的鍵值對(duì)被添加到該桶對(duì)應(yīng)的鏈表的末尾。鏈地址法示意圖Bucket IndexContent (Linked List/Array)0[KeyA, ValueA]-[KeyX, ValueX]1[KeyB, ValueB]2[KeyC, ValueC]-[KeyY, ValueY]-[KeyZ, ValueZ]……1.4 負(fù)載因子與動(dòng)態(tài)擴(kuò)容哈希表的性能也受到其“填充程度”的影響這由負(fù)載因子Load Factor來(lái)衡量。負(fù)載因子 存儲(chǔ)的鍵值對(duì)數(shù)量 / 桶的數(shù)量負(fù)載因子過(guò)低哈希表空間利用率低浪費(fèi)內(nèi)存。負(fù)載因子過(guò)高碰撞的概率增加鏈表或探測(cè)序列變長(zhǎng)導(dǎo)致存取操作性能下降。為了維持良好的性能當(dāng)負(fù)載因子超過(guò)某個(gè)閾值時(shí)例如 0.75哈希表會(huì)觸發(fā)動(dòng)態(tài)擴(kuò)容Resizing/Rehashing。這意味著創(chuàng)建一個(gè)更大的新數(shù)組通常是原數(shù)組大小的兩倍。遍歷舊哈希表中的所有鍵值對(duì)。對(duì)每個(gè)鍵重新計(jì)算哈希值并將其放入新數(shù)組對(duì)應(yīng)的桶中。擴(kuò)容操作是一個(gè) O(N) 的操作雖然不頻繁但如果發(fā)生在關(guān)鍵路徑上可能會(huì)引入瞬時(shí)延遲。第二章JavaScript 中的Map和SetJavaScript 的Map和Set是 ES6 引入的強(qiáng)大集合類(lèi)型它們內(nèi)部就是基于哈希表實(shí)現(xiàn)的。2.1Mapvs.Object在 ES6 之前開(kāi)發(fā)者經(jīng)常使用普通Object作為哈希表但Map提供了幾個(gè)關(guān)鍵優(yōu)勢(shì)特性O(shè)bjectMap鍵類(lèi)型只能使用字符串或 Symbol非字符串鍵會(huì)被轉(zhuǎn)換為字符串可以使用任意類(lèi)型的值作為鍵對(duì)象、函數(shù)、原始值等鍵的順序不保證插入順序ES2015后非整數(shù)鍵有順序但并非嚴(yán)格插入順序保證鍵值對(duì)的插入順序大小無(wú)法直接獲取需手動(dòng)計(jì)數(shù)或遍歷.size屬性直接提供鍵值對(duì)數(shù)量迭代迭代自身屬性需Object.keys()等方法可直接迭代for...of提供keys(),values(),entries()性能對(duì)于大量動(dòng)態(tài)增刪的鍵可能不如Map優(yōu)化針對(duì)鍵值對(duì)操作進(jìn)行了高度優(yōu)化尤其是在處理非字符串鍵時(shí)原型鏈鍵可能與原型鏈上的屬性沖突不受原型鏈影響2.2SetSet是一種存儲(chǔ)唯一值的集合。它的行為類(lèi)似于Map但只存儲(chǔ)鍵值就是鍵本身。new Set([iterable])創(chuàng)建一個(gè)新的 Set 對(duì)象。set.add(value)添加一個(gè)值。set.delete(value)刪除一個(gè)值。set.has(value)檢查是否存在某個(gè)值。set.size返回 Set 中元素的數(shù)量。2.3 JavaScript 引擎如何哈希鍵這是理解哈希碰撞攻擊的關(guān)鍵。JavaScript 引擎例如 V8 引擎在 Chrome 和 Node.js 中使用對(duì)不同類(lèi)型的鍵有不同的哈希策略。由于哈希函數(shù)是引擎的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)我們無(wú)法直接訪(fǎng)問(wèn)或控制它但可以推斷其大致行為原始值Primitives字符串Strings這是最復(fù)雜也最常被攻擊的類(lèi)型。引擎通常使用一種快速的哈希算法如多項(xiàng)式滾動(dòng)哈希Polynomial Rolling Hash的變體或者結(jié)合隨機(jī)鹽值random seed來(lái)生成哈希。字符串的哈希值通常在字符串創(chuàng)建或第一次被用作哈希鍵時(shí)計(jì)算并緩存。數(shù)字Numbers整數(shù)尤其是小整數(shù)可能直接用其值或簡(jiǎn)單變換作為哈希。浮點(diǎn)數(shù)的哈希會(huì)更復(fù)雜需要考慮其二進(jìn)制表示。布爾值Booleans、null、undefined這些只有少數(shù)幾個(gè)固定值通常有固定的、預(yù)設(shè)的哈希值。SymbolSymbol 是 ES6 新增的原始類(lèi)型每個(gè) Symbol 都是獨(dú)一無(wú)二的。引擎通常會(huì)為每個(gè) Symbol 分配一個(gè)內(nèi)部的、唯一的 ID并使用這個(gè) ID 來(lái)生成哈希。對(duì)象Objects對(duì)象的哈希這是最特殊的一點(diǎn)。Map和Set使用對(duì)象的引用標(biāo)識(shí)而不是對(duì)象的內(nèi)容來(lái)作為鍵。也就是說(shuō){a: 1}和{a: 1}是兩個(gè)不同的對(duì)象即使它們看起來(lái)內(nèi)容相同它們?cè)贛ap中也會(huì)被視為不同的鍵。引擎會(huì)為每個(gè)對(duì)象分配一個(gè)內(nèi)部的、隱藏的、唯一的 ID有時(shí)被稱(chēng)為“隱藏類(lèi) ID”或“對(duì)象 ID”。這個(gè) ID 在對(duì)象的生命周期內(nèi)通常是固定的并且被用來(lái)生成哈希。這使得對(duì)象的哈希值非常穩(wěn)定且獨(dú)一無(wú)二對(duì)于不同的對(duì)象實(shí)例。2.4 鍵的比較SameValueZero算法當(dāng)兩個(gè)鍵哈希到同一個(gè)桶時(shí)引擎需要進(jìn)一步比較它們以確定它們是否是同一個(gè)鍵。JavaScript 的Map和Set使用SameValueZero算法進(jìn)行鍵的比較。SameValueZero規(guī)則如下NaN與NaN相等。0與-0相等。其他情況下與嚴(yán)格相等 () 規(guī)則相同。這個(gè)比較算法確保了即使不同的鍵哈希到同一個(gè)桶也能正確地區(qū)分它們。第三章哈希碰撞攻擊的原理與影響現(xiàn)在我們已經(jīng)了解了哈希表和 JavaScriptMap/Set的工作原理我們可以探討哈希碰撞攻擊是如何發(fā)生的以及它會(huì)造成什么影響。3.1 什么是哈希碰撞攻擊哈希碰撞攻擊Hash DoS Attack是指攻擊者通過(guò)精心構(gòu)造輸入數(shù)據(jù)使得所有或大部分?jǐn)?shù)據(jù)項(xiàng)在哈希表中產(chǎn)生相同的哈希值從而導(dǎo)致它們被存儲(chǔ)在同一個(gè)桶中。這使得哈希表的內(nèi)部鏈表變得非常長(zhǎng)將原本平均 O(1) 的存取操作降級(jí)為最壞情況下的 O(N) 操作。3.2 性能降級(jí)從 O(1) 到 O(N)平均情況 (O(1))在正常操作下哈希函數(shù)能將鍵均勻分布。查找、插入、刪除操作只需要計(jì)算哈希值并訪(fǎng)問(wèn)對(duì)應(yīng)的桶。由于每個(gè)桶中的元素?cái)?shù)量很少這些操作幾乎是常數(shù)時(shí)間。最壞情況 (O(N))當(dāng)所有鍵都哈希到同一個(gè)桶時(shí)這個(gè)桶會(huì)變成一個(gè)包含所有 N 個(gè)元素的鏈表。此時(shí)對(duì)這個(gè)鏈表進(jìn)行查找、插入、刪除操作都需要遍歷整個(gè)鏈表其時(shí)間復(fù)雜度就退化為 O(N)。3.3 攻擊目標(biāo)拒絕服務(wù) (DoS)哈希碰撞攻擊的主要目標(biāo)是拒絕服務(wù)Denial of Service, DoS。在 Node.js 服務(wù)器環(huán)境中如果一個(gè)應(yīng)用程序接收用戶(hù)輸入的字符串或?qū)ο笞鳛镸ap或Set的鍵并頻繁地進(jìn)行操作攻擊者可以利用這一漏洞攻擊者向服務(wù)器發(fā)送大量精心構(gòu)造的請(qǐng)求每個(gè)請(qǐng)求都包含一個(gè)被設(shè)計(jì)為與之前請(qǐng)求的鍵產(chǎn)生哈希碰撞的“特殊鍵”。服務(wù)器嘗試將這些鍵添加到Map或Set中。每次添加、查找或刪除操作都需要遍歷一個(gè)越來(lái)越長(zhǎng)的鏈表。最終服務(wù)器花費(fèi)大量 CPU 時(shí)間來(lái)處理這些低效的操作導(dǎo)致其響應(yīng)速度急劇下降甚至完全停止響應(yīng)合法請(qǐng)求。這使得服務(wù)器資源耗盡無(wú)法正常提供服務(wù)從而達(dá)到 DoS 的目的。即使是在客戶(hù)端瀏覽器環(huán)境長(zhǎng)時(shí)間運(yùn)行的腳本也可能導(dǎo)致頁(yè)面卡頓、無(wú)響應(yīng)影響用戶(hù)體驗(yàn)。3.4 “特殊鍵”的秘密那么攻擊者如何找到這些“特殊鍵”呢這通常依賴(lài)于對(duì)哈希函數(shù)算法的了解無(wú)論是通過(guò)逆向工程還是已知漏洞?？深A(yù)測(cè)的哈希函數(shù)在一些歷史悠久的語(yǔ)言或庫(kù)中哈希函數(shù)可能采用簡(jiǎn)單的多項(xiàng)式哈希或其他容易預(yù)測(cè)的算法。例如一個(gè)簡(jiǎn)單的字符串哈希函數(shù)可能僅僅是字符 ASCII 碼的總和。攻擊者可以輕易構(gòu)造出具有相同 ASCII 碼總和但內(nèi)容不同的字符串。字符串長(zhǎng)度攻擊某些哈希函數(shù)在處理特定長(zhǎng)度的字符串時(shí)可能表現(xiàn)出弱點(diǎn)。對(duì)象/Symbol ID 預(yù)測(cè)理論上對(duì)于對(duì)象和 Symbol如果引擎分配內(nèi)部 ID 的策略是簡(jiǎn)單遞增且可預(yù)測(cè)的并且攻擊者能控制大量對(duì)象的創(chuàng)建順序那么理論上可以嘗試預(yù)測(cè)哪些對(duì)象會(huì)獲得碰撞的 ID進(jìn)而導(dǎo)致哈希碰撞。然而現(xiàn)代 JavaScript 引擎的 ID 分配通常更加復(fù)雜并且會(huì)結(jié)合其他因素使其難以預(yù)測(cè)。關(guān)鍵點(diǎn)在于攻擊者需要能夠根據(jù)哈希函數(shù)的特性在不知道哈希表內(nèi)部狀態(tài)如鹽值、桶數(shù)量的情況下構(gòu)造出大量哈希值相同的鍵。第四章模擬哈希碰撞攻擊由于現(xiàn)代 JavaScript 引擎如 V8的哈希函數(shù)是高度優(yōu)化和私有的并且包含了隨機(jī)化等防御機(jī)制直接在真實(shí)環(huán)境中演示哈希碰撞攻擊是極其困難的。因此我們將通過(guò)一個(gè)簡(jiǎn)化的哈希表實(shí)現(xiàn)和可預(yù)測(cè)的哈希函數(shù)來(lái)模擬這種攻擊。4.1 模擬一個(gè)脆弱的哈希函數(shù)我們將創(chuàng)建一個(gè)非常簡(jiǎn)單的字符串哈希函數(shù)它僅僅基于字符串中字符的 ASCII 碼之和。這種函數(shù)非常容易產(chǎn)生碰撞。/** * 模擬一個(gè)極其脆弱的哈希函數(shù)簡(jiǎn)單地將所有字符的ASCII碼相加。 * 這種哈希函數(shù)很容易產(chǎn)生碰撞。 * param {string | number | boolean | object} key - 需要哈希的鍵 * param {number} tableSize - 哈希表的大小用于計(jì)算桶索引 * returns {number} 桶索引 */ function vulnerableHash(key, tableSize) { let hash 0; const strKey String(key); // 將所有鍵都轉(zhuǎn)換為字符串進(jìn)行哈希 for (let i 0; i strKey.length; i) { hash (hash strKey.charCodeAt(i)) % tableSize; // 簡(jiǎn)單相加并取模 } return hash; } // 示例容易產(chǎn)生碰撞的鍵 console.log(Hash for ab: ${vulnerableHash(ab, 10)}); // 97 98 195. 195 % 10 5 console.log(Hash for ba: ${vulnerableHash(ba, 10)}); // 98 97 195. 195 % 10 5 console.log(Hash for c: ${vulnerableHash(c, 10)}); // 99. 99 % 10 9 console.log(Hash for aB: ${vulnerableHash(aB, 10)}); // 97 66 163. 163 % 10 3 console.log(Hash for Bc: ${vulnerableHash(Bc, 10)}); // 66 99 165. 165 % 10 5 (又一個(gè)碰撞)在這個(gè)vulnerableHash函數(shù)中ab,ba和Bc都哈希到了桶索引 5。這意味著它們會(huì)落入同一個(gè)桶中導(dǎo)致碰撞。4.2 模擬一個(gè)簡(jiǎn)易的哈希表VulnerableMap接下來(lái)我們基于這個(gè)脆弱的哈希函數(shù)實(shí)現(xiàn)一個(gè)簡(jiǎn)易的Map類(lèi)以觀(guān)察碰撞的影響。/** * 模擬一個(gè)基于鏈地址法的簡(jiǎn)易哈希表使用脆弱的哈希函數(shù)。 */ class VulnerableMap { constructor(initialSize 10) { this.buckets Array(initialSize).fill(null).map(() []); // 每個(gè)桶是一個(gè)數(shù)組模擬鏈表 this.size 0; this.collisions 0; // 統(tǒng)計(jì)碰撞次數(shù) this.maxChainLength 0; // 統(tǒng)計(jì)最長(zhǎng)鏈的長(zhǎng)度 } /** * 獲取鍵的桶索引。 * param {*} key - 鍵 * returns {number} 桶索引 */ _getIndex(key) { // 使用我們脆弱的哈希函數(shù) return vulnerableHash(key, this.buckets.length); } /** * 設(shè)置鍵值對(duì)。 * param {*} key - 鍵 * param {*} value - 值 */ set(key, value) { const index this._getIndex(key); const bucket this.buckets[index]; // 檢查鍵是否已存在 for (let i 0; i bucket.length; i) { if (Object.is(bucket[i][0], key)) { // 使用 Object.is 模擬 SameValueZero 比較 bucket[i][1] value; // 更新值 return; } } // 鍵不存在添加到桶中 bucket.push([key, value]); this.size; // 更新碰撞統(tǒng)計(jì)和最長(zhǎng)鏈長(zhǎng)度 if (bucket.length 1) { this.collisions; } if (bucket.length this.maxChainLength) { this.maxChainLength bucket.length; } } /** * 獲取鍵對(duì)應(yīng)的值。 * param {*} key - 鍵 * returns {*} 鍵對(duì)應(yīng)的值如果不存在則返回 undefined */ get(key) { const index this._getIndex(key); const bucket this.buckets[index]; for (let i 0; i bucket.length; i) { if (Object.is(bucket[i][0], key)) { return bucket[i][1]; } } return undefined; } /** * 檢查鍵是否存在。 * param {*} key - 鍵 * returns {boolean} 鍵是否存在 */ has(key) { return this.get(key) ! undefined; } /** * 刪除鍵值對(duì)。 * param {*} key - 鍵 * returns {boolean} 是否成功刪除 */ delete(key) { const index this._getIndex(key); const bucket this.buckets[index]; for (let i 0; i bucket.length; i) { if (Object.is(bucket[i][0], key)) { bucket.splice(i, 1); // 從數(shù)組中刪除 this.size--; // 重新計(jì)算最長(zhǎng)鏈簡(jiǎn)化處理實(shí)際可能需要更復(fù)雜的邏輯 this.maxChainLength Math.max(...this.buckets.map(b b.length)); return true; } } return false; } /** * 清空哈希表。 */ clear() { this.buckets Array(this.buckets.length).fill(null).map(() []); this.size 0; this.collisions 0; this.maxChainLength 0; } }4.3 構(gòu)造碰撞鍵并演示性能降級(jí)現(xiàn)在我們將利用vulnerableHash的弱點(diǎn)構(gòu)造大量哈希值相同的鍵并觀(guān)察VulnerableMap的性能。我們將構(gòu)造一系列字符串它們由不同的字符組成但所有字符的 ASCII 碼之和都相同從而確保它們哈希到同一個(gè)桶。// 輔助函數(shù)生成特定ASCII和的字符串簡(jiǎn)化實(shí)際攻擊中需要更復(fù)雜的算法 // 這里為了演示我們假設(shè)目標(biāo)哈希值是 5 對(duì)應(yīng)桶索引 5 // 假設(shè)桶大小是 10那么我們需要的 ASCII 碼總和是 5, 15, 25, 35 ... // 我們可以通過(guò)填充字符來(lái)達(dá)到這個(gè)目的。 function generateCollidingStrings(count, targetHashSumModulo, tableSize) { const collidingKeys []; let baseAscii A.charCodeAt(0); // 從 A 開(kāi)始 let currentSum 0; let currentKey ; // 生成一個(gè)基礎(chǔ)字符串使其哈希值滿(mǎn)足 targetHashSumModulo // 假設(shè)我們想讓所有鍵都哈希到索引 5 // 簡(jiǎn)單起見(jiàn)我們直接生成一系列字符通過(guò)調(diào)整使其總和符合要求 // 例如我們希望 (char1 char2 ... ) % tableSize targetHashSumModulo for (let i 0; i count; i) { let key ; let sum 0; // 生成一個(gè)隨機(jī)長(zhǎng)度的字符串 const length Math.floor(Math.random() * 5) 3; // 長(zhǎng)度在 3 到 7 之間 for (let j 0; j length; j) { // 確保字符是可見(jiàn)的且不影響哈希值計(jì)算 let charCode 65 Math.floor(Math.random() * 26); // A-Z key String.fromCharCode(charCode); sum charCode; } // 調(diào)整字符串使其哈希值符合要求 // 這是一個(gè)簡(jiǎn)化的方法實(shí)際攻擊中需要更復(fù)雜的數(shù)學(xué)計(jì)算或查找表 // 假設(shè)我們希望哈希值為 5 let currentModulo sum % tableSize; if (currentModulo ! targetHashSumModulo) { let diff targetHashSumModulo - currentModulo; if (diff 0) diff tableSize; // 確保 diff 是正數(shù) // 嘗試通過(guò)添加一個(gè)字符來(lái)調(diào)整 // 找到一個(gè)字符使其 ASCII 碼 % tableSize 等于 diff // 例如如果 diff 是 3 tableSize 是 10 那么 C (67) % 10 7, M (77) % 10 7 // 我們可以嘗試添加 a (97) - 7, b (98) - 8, c (99) - 9, d (100) - 0, e (101) - 1, f (102) - 2, g (103) - 3 // 實(shí)際攻擊者會(huì)有一個(gè)預(yù)計(jì)算的字符表 let charToAddCode 0; for(let c 65; c 122; c){ // 尋找合適的ASCII碼 if(c % tableSize diff){ charToAddCode c; break; } } if(charToAddCode){ key String.fromCharCode(charToAddCode); } else { // 如果找不到單個(gè)字符調(diào)整就隨機(jī)生成一個(gè)新鍵直到滿(mǎn)足條件 // 這是一個(gè)簡(jiǎn)化在實(shí)際攻擊中攻擊者會(huì)更精確地生成 i--; // 重試 continue; } } // 再次驗(yàn)證哈希值 if (vulnerableHash(key, tableSize) targetHashSumModulo) { collidingKeys.push(key); } else { i--; // 重試 } } return collidingKeys; } // 設(shè)定哈希表大小和目標(biāo)碰撞桶索引 const TABLE_SIZE 1000; // 桶的數(shù)量 const TARGET_BUCKET_INDEX 50; // 攻擊目標(biāo)桶的索引 // 生成非碰撞鍵理想情況 const nonCollidingKeys Array.from({ length: TABLE_SIZE * 5 }, (_, i) key_${i}); // 生成大量碰撞鍵 const NUM_COLLIDING_KEYS TABLE_SIZE * 5; // 制造 5 倍于桶數(shù)量的碰撞鍵 const collidingKeys generateCollidingStrings(NUM_COLLIDING_KEYS, TARGET_BUCKET_INDEX, TABLE_SIZE); // ---------------------- 性能測(cè)試 ---------------------- console.log(n--- 性能測(cè)試開(kāi)始 ---); // 1. 測(cè)試?yán)硐肭闆r非碰撞鍵 console.time(VulnerableMap: Add non-colliding keys); const map1 new VulnerableMap(TABLE_SIZE); for (const key of nonCollidingKeys) { map1.set(key, Math.random()); } console.timeEnd(VulnerableMap: Add non-colliding keys); console.log(Map 1 Size: ${map1.size}, Collisions: ${map1.collisions}, Max Chain Length: ${map1.maxChainLength}); console.time(VulnerableMap: Get non-colliding keys); for (const key of nonCollidingKeys) { map1.get(key); } console.timeEnd(VulnerableMap: Get non-colliding keys); map1.clear(); // 2. 測(cè)試攻擊情況碰撞鍵 console.time(VulnerableMap: Add colliding keys); const map2 new VulnerableMap(TABLE_SIZE); for (const key of collidingKeys) { map2.set(key, Math.random()); } console.timeEnd(VulnerableMap: Add colliding keys); console.log(Map 2 Size: ${map2.size}, Collisions: ${map2.collisions}, Max Chain Length: ${map2.maxChainLength}); console.time(VulnerableMap: Get colliding keys); for (const key of collidingKeys) { map2.get(key); } console.timeEnd(VulnerableMap: Get colliding keys); map2.clear(); // 3. 對(duì)比真實(shí) Map 的性能 (通常更優(yōu)) // 注意真實(shí) Map 不會(huì)受我們模擬的脆弱哈希函數(shù)影響 console.time(Native Map: Add random keys); const nativeMap1 new Map(); for (const key of nonCollidingKeys) { nativeMap1.set(key, Math.random()); } console.timeEnd(Native Map: Add random keys); console.time(Native Map: Get random keys); for (const key of nonCollidingKeys) { nativeMap1.get(key); } console.timeEnd(Native Map: Get random keys); // 再次用碰撞鍵測(cè)試 Native Map (預(yù)期不會(huì)出現(xiàn)性能問(wèn)題) console.time(Native Map: Add colliding keys (for our vulnerable hash)); const nativeMap2 new Map(); for (const key of collidingKeys) { // 這些鍵對(duì) Native Map 而言不是碰撞鍵 nativeMap2.set(key, Math.random()); } console.timeEnd(Native Map: Add colliding keys (for our vulnerable hash)); console.time(Native Map: Get colliding keys (for our vulnerable hash)); for (const key of collidingKeys) { nativeMap2.get(key); } console.timeEnd(Native Map: Get colliding keys (for our vulnerable hash)); console.log(n--- 性能測(cè)試結(jié)束 ---); /* 預(yù)期輸出 (時(shí)間會(huì)因機(jī)器性能而異): --- 性能測(cè)試開(kāi)始 --- VulnerableMap: Add non-colliding keys: X ms Map 1 Size: 5000, Collisions: YYY, Max Chain Length: ZZZ (YYY和ZZZ相對(duì)較小) VulnerableMap: Get non-colliding keys: X ms VulnerableMap: Add colliding keys: AAAA ms (顯著長(zhǎng)于非碰撞鍵添加時(shí)間) Map 2 Size: 5000, Collisions: 4999, Max Chain Length: 5000 (幾乎所有鍵都在一個(gè)桶中) VulnerableMap: Get colliding keys: AAAA ms (顯著長(zhǎng)于非碰撞鍵獲取時(shí)間) Native Map: Add random keys: B ms (通常比 VulnerableMap 快) Native Map: Get random keys: C ms Native Map: Add colliding keys (for our vulnerable hash): D ms (與 random keys 類(lèi)似) Native Map: Get colliding keys (for our vulnerable hash): E ms (與 random keys 類(lèi)似) --- 性能測(cè)試結(jié)束 --- */分析輸出通過(guò)運(yùn)行上述代碼您會(huì)觀(guān)察到VulnerableMap在處理大量碰撞鍵時(shí)其set和get操作的時(shí)間會(huì)急劇增加遠(yuǎn)超處理非碰撞鍵的時(shí)間。這是因?yàn)樗墟I都擠在了一個(gè)桶中每次操作都需要遍歷一個(gè)長(zhǎng)度為NUM_COLLIDING_KEYS的鏈表。相反原生的Map在處理這些“碰撞鍵”時(shí)性能依然保持穩(wěn)定因?yàn)樗膬?nèi)部哈希函數(shù)能夠有效地將這些鍵分散到不同的桶中避免了我們模擬的這種極端碰撞。這個(gè)實(shí)驗(yàn)生動(dòng)地展示了哈希碰撞如何將 O(1) 操作降級(jí)為 O(N)以及這種性能降級(jí)在實(shí)際應(yīng)用中可能造成的巨大影響。第五章現(xiàn)代 JavaScript 引擎的防御機(jī)制幸運(yùn)的是JavaScript 引擎的開(kāi)發(fā)者們?cè)缇鸵庾R(shí)到了哈希碰撞攻擊的威脅并投入了大量精力來(lái)構(gòu)建健壯的防御機(jī)制。5.1 隨機(jī)化哈希Hash Salting這是最核心的防御機(jī)制之一。原理在哈希函數(shù)計(jì)算哈希值時(shí)引入一個(gè)隨機(jī)生成的“鹽值”salt。這個(gè)鹽值在每次程序啟動(dòng)時(shí)或在某些情況下甚至在運(yùn)行時(shí)都會(huì)隨機(jī)生成。效果即使攻擊者知道哈希函數(shù)的大致算法他們也無(wú)法預(yù)先計(jì)算出哪些鍵會(huì)發(fā)生碰撞因?yàn)槊看芜\(yùn)行的鹽值都不同。這意味著攻擊者構(gòu)造的“特殊鍵”在不同的程序?qū)嵗胁辉偈桥鲎叉I。挑戰(zhàn)隨機(jī)化哈希會(huì)增加一點(diǎn)計(jì)算開(kāi)銷(xiāo)因?yàn)楣Ｖ挡荒鼙缓?jiǎn)單地緩存并在所有上下文中使用。對(duì)于字符串引擎可能需要為每個(gè)進(jìn)程實(shí)例重新計(jì)算哈希值。5.2 復(fù)雜且動(dòng)態(tài)的哈希算法現(xiàn)代 JS 引擎的哈希函數(shù)遠(yuǎn)比我們模擬的簡(jiǎn)單它們可能結(jié)合多種技術(shù)多項(xiàng)式滾動(dòng)哈希一種常用的字符串哈希算法但會(huì)使用精心選擇的乘數(shù)和模數(shù)。通用哈希Universal Hashing使用一組哈希函數(shù)并在運(yùn)行時(shí)隨機(jī)選擇一個(gè)。適應(yīng)性哈希Adaptive Hashing引擎會(huì)監(jiān)控哈希表的性能。如果某個(gè)桶的鏈表過(guò)長(zhǎng)或者檢測(cè)到頻繁的碰撞引擎可能會(huì)采取措施桶內(nèi)結(jié)構(gòu)升級(jí)將過(guò)長(zhǎng)的鏈表轉(zhuǎn)換為更高效的數(shù)據(jù)結(jié)構(gòu)例如紅黑樹(shù)Red-Black Tree或跳表Skip List。這樣即使在一個(gè)桶中查找/插入/刪除操作也能維持 O(log K) 的時(shí)間復(fù)雜度K 為該桶中的元素?cái)?shù)量而不是 O(K)。重新哈希Rehashing引擎可能會(huì)觸發(fā)一次全局的重新哈希操作使用不同的鹽值或調(diào)整哈希函數(shù)參數(shù)將所有鍵重新分布。5.3 內(nèi)部對(duì)象 ID 的復(fù)雜性對(duì)于對(duì)象和 Symbol 鍵引擎分配的內(nèi)部 ID 通常不是簡(jiǎn)單遞增的。它們可能結(jié)合了內(nèi)存地址、時(shí)間戳、進(jìn)程 ID 等多種因素甚至?xí)褂酶鼜?fù)雜的隨機(jī)化算法來(lái)生成使得這些 ID 難以預(yù)測(cè)從而阻礙了基于對(duì)象 ID 的哈希碰撞攻擊。5.4 嚴(yán)格的鍵比較 (SameValueZero)雖然這不是直接的防御機(jī)制但SameValueZero確保了即使兩個(gè)不同的鍵哈希到同一個(gè)桶它們也能被正確地區(qū)分。這使得鏈地址法能夠正常工作即使在發(fā)生碰撞的情況下也能保證數(shù)據(jù)正確性只是性能會(huì)受影響。第六章開(kāi)發(fā)者如何防范盡管 JavaScript 引擎已經(jīng)內(nèi)置了強(qiáng)大的防御機(jī)制但作為應(yīng)用程序開(kāi)發(fā)者我們?nèi)匀恍枰３志璨⒉扇∽罴褜?shí)踐來(lái)進(jìn)一步加固我們的應(yīng)用。6.1 輸入驗(yàn)證與凈化這是任何處理用戶(hù)輸入的應(yīng)用程序的黃金法則。限制鍵的長(zhǎng)度和復(fù)雜度如果您的應(yīng)用程序允許用戶(hù)輸入作為Map或Set的鍵請(qǐng)限制其最大長(zhǎng)度。過(guò)長(zhǎng)的字符串不僅可能增加哈希計(jì)算時(shí)間也可能為某些哈希函數(shù)的特定弱點(diǎn)創(chuàng)造條件。不允許任意對(duì)象作為鍵如果不是業(yè)務(wù)邏輯必需避免直接將用戶(hù)提供的任意復(fù)雜對(duì)象作為Map或Set的鍵。如果需要考慮將對(duì)象序列化為 JSON 字符串并對(duì)字符串進(jìn)行驗(yàn)證。但這也會(huì)帶來(lái)新的哈希挑戰(zhàn)。白名單機(jī)制如果鍵的取值范圍有限最好使用白名單機(jī)制只允許已知的、安全的鍵。6.2 速率限制與資源監(jiān)控API 速率限制在服務(wù)器端Node.js對(duì)用戶(hù)或 IP 地址的 API 請(qǐng)求進(jìn)行速率限制。這可以防止攻擊者在短時(shí)間內(nèi)發(fā)送大量惡意請(qǐng)求從而降低 DoS 攻擊成功的概率。資源監(jiān)控持續(xù)監(jiān)控服務(wù)器的 CPU 使用率、內(nèi)存消耗和響應(yīng)時(shí)間。異常的峰值或持續(xù)的高負(fù)載可能是 DoS 攻擊的早期跡象。6.3 避免在關(guān)鍵路徑上使用大量用戶(hù)控制的鍵如果您的應(yīng)用程序需要在高性能、高并發(fā)場(chǎng)景下處理大量用戶(hù)提供的鍵并且這些鍵可能被惡意構(gòu)造那么重新評(píng)估數(shù)據(jù)結(jié)構(gòu)的選擇是明智的?？紤]替代數(shù)據(jù)結(jié)構(gòu)對(duì)于某些特定場(chǎng)景可能需要使用專(zhuān)門(mén)為抵抗哈希碰撞而設(shè)計(jì)的其他數(shù)據(jù)結(jié)構(gòu)例如布隆過(guò)濾器Bloom Filter或基于樹(shù)的數(shù)據(jù)結(jié)構(gòu)如 B-樹(shù)或跳表它們?cè)谧顗那闆r下仍能提供可預(yù)測(cè)的性能通常是 O(log N)。然而在 JavaScript 環(huán)境中直接實(shí)現(xiàn)這些復(fù)雜數(shù)據(jù)結(jié)構(gòu)并不常見(jiàn)且通常不比原生Map/Set更優(yōu)。預(yù)處理鍵在將用戶(hù)鍵添加到Map/Set之前對(duì)其進(jìn)行標(biāo)準(zhǔn)化或哈希處理。例如可以使用一個(gè)強(qiáng)大的密碼學(xué)哈希函數(shù)如 SHA-256對(duì)用戶(hù)提供的字符串進(jìn)行哈希然后將哈希值作為鍵。這樣即使原始字符串是惡意構(gòu)造的其哈希值也會(huì)被均勻分布。但請(qǐng)注意密碼學(xué)哈希計(jì)算成本較高。6.4 保持 JavaScript 運(yùn)行時(shí)環(huán)境的更新JavaScript 引擎如 V8的開(kāi)發(fā)者們不斷地發(fā)現(xiàn)和修復(fù)潛在的性能漏洞并優(yōu)化哈希算法。定期更新您的 Node.js 版本和瀏覽器可以確保您的應(yīng)用程序運(yùn)行在最安全、最高效的環(huán)境中。6.5 對(duì)性能敏感的應(yīng)用程序進(jìn)行基準(zhǔn)測(cè)試在部署之前對(duì)應(yīng)用程序進(jìn)行嚴(yán)格的性能基準(zhǔn)測(cè)試尤其是在模擬高負(fù)載和惡意輸入的情況下。了解應(yīng)用程序在不同負(fù)載下的行為可以幫助您識(shí)別潛在的瓶頸。第七章哈希 DoS 在其他語(yǔ)言中的歷史回顧哈希碰撞導(dǎo)致的 DoS 攻擊并非 JavaScript 獨(dú)有它是一個(gè)在計(jì)算機(jī)科學(xué)領(lǐng)域廣為人知的安全問(wèn)題。許多其他流行的編程語(yǔ)言和系統(tǒng)也曾面臨過(guò)類(lèi)似的挑戰(zhàn)Java在 Java 7u4 之前的版本中HashMap和Hashtable容易受到字符串哈希碰撞攻擊。攻擊者可以構(gòu)造大量字符串使它們哈希到同一個(gè)桶導(dǎo)致性能下降。Java 后來(lái)通過(guò)引入隨機(jī)化哈希和在碰撞鏈過(guò)長(zhǎng)時(shí)將鏈表轉(zhuǎn)換為紅黑樹(shù)來(lái)緩解此問(wèn)題。Python在 Python 2.7.3 和 3.2.3 之前的版本中字典dict和集合set也容易受到哈希碰撞攻擊。Python 后來(lái)默認(rèn)開(kāi)啟了隨機(jī)化哈希。RubyRuby 1.9 之前的版本也存在類(lèi)似問(wèn)題。PHPPHP 5.3.9 之前的版本中數(shù)組用作哈希表也存在哈希碰撞漏洞。PerlPerl 也曾受此問(wèn)題困擾。這些歷史事件都促使了現(xiàn)代編程語(yǔ)言運(yùn)行時(shí)環(huán)境在哈希表實(shí)現(xiàn)上引入更強(qiáng)大的安全措施例如隨機(jī)化哈希、動(dòng)態(tài)結(jié)構(gòu)升級(jí)等。這表明雖然現(xiàn)在 JavaScript 引擎的內(nèi)置防御已經(jīng)非常強(qiáng)大但理解其背后的原理和潛在威脅對(duì)于任何編程專(zhuān)家來(lái)說(shuō)都是必要的知識(shí)。結(jié)語(yǔ)哈希碰撞攻擊是一個(gè)經(jīng)典而復(fù)雜的安全問(wèn)題它揭示了數(shù)據(jù)結(jié)構(gòu)底層實(shí)現(xiàn)對(duì)應(yīng)用程序性能和安全的關(guān)鍵影響。在 JavaScript 中Map和Set憑借其哈希表實(shí)現(xiàn)在平均情況下提供了卓越的性能。然而如果哈希函數(shù)可預(yù)測(cè)且缺乏適當(dāng)?shù)姆烙鶒阂鈽?gòu)造的“特殊鍵”可以輕易地將這些操作的效率從 O(1) 降低到 O(N)從而導(dǎo)致拒絕服務(wù)?，F(xiàn)代 JavaScript 引擎如 V8已經(jīng)通過(guò)隨機(jī)化哈希、復(fù)雜算法和自適應(yīng)機(jī)制極大地增強(qiáng)了對(duì)這類(lèi)攻擊的抵抗力。作為開(kāi)發(fā)者我們應(yīng)信任這些底層優(yōu)化但同時(shí)也要保持警惕通過(guò)嚴(yán)格的輸入驗(yàn)證、速率限制和持續(xù)的性能監(jiān)控為我們的應(yīng)用程序提供額外的保護(hù)層。理解這些底層機(jī)制是我們構(gòu)建健壯、安全和高性能應(yīng)用的基礎(chǔ)。