正規表達式沒寫好會怎樣？淺談 ReDoS：利用 regexp 的攻擊

Regular expression，中文又翻作「正規表達式」或是「正規表示式」等等（以下簡稱 regexp），主要是用來做字串的配對，寫好一個模式之後，就可以拿來配對到符合規則的文字。

無論是電話號碼、Email 或是身分證字號等等，都可以運用 regexp 來完成初步的格式驗證，確保字串的格式與特定規則相符合。

Regexp 雖然方便，但沒寫好的話有可能導致一些輸入的驗證被繞過，演變成資安問題；而除了這個之外，還有另外一種也會造成問題，就是這篇要來講的 ReDoS，全名為：Regular expression Denial-of-Service，因為正規表達式所引起的阻斷服務攻擊。

在講 ReDoS 之前，先來提一下什麼是 DoS。

舉例來說，假設假設某個網站框架對於 HTTP 請求的解析沒有做好，只要碰到特殊字元就會壞掉，造成伺服器重啟，而這時攻擊者就可以不斷送出這種會讓網站壞掉的請求，造成伺服器一直重啟，這就是一種 DoS。

如果要分更細的話，還可以分成攻擊的是哪一層，例如說是網路層還是應用層等等，這篇講的都是針對應用層的攻擊。

大家平常在網路新聞看到的攻擊，比較多應該是屬於 DDoS，前面多了一個 D，意思是 distributed，分散式的，而且都是針對網路層的攻擊居多。前面我們舉的 DoS 例子可以看出基本上都是網站本身有問題，例如說沒有考慮到特殊狀況等等，才會讓攻擊者可以利用，而 DDoS 比較像是：「不管你有沒有問題，我找一堆人把你塞爆」

以現實生活來舉例，你開了一間小吃店，賣一些常見的東西像是乾麵啦，燙青菜啦等等，因為每次要看客人的菜單點了什麼很花時間，又覺得用手機點餐很沒有人情味，因此訂製了一個「讀菜單機器人」，來幫你看客人的點菜單。

這時候我故意在點菜單上面鬼畫符，但有些地方看似正常，讓菜單看起來很吃力，機器人的辨識功能沒有做好，沒辦法解讀，於是就停擺了，這就叫做 DoS，以一己之力耗盡資源。

我找一百個人去你那邊，每個人都畫一堆空白菜單丟給機器人，讓機器人應接不暇，沒辦法處理其他客人的菜單，這就叫做 DDoS。

簡單來說呢，DoS 通常是「以少量的資源就能造成服務中斷」，而 DDoS 則是「用比超級多的資源直接把你服務打掛」。

好，讓我們講回 DoS，從前面的例子可以看出來，當你的程式本身就有一些問題的時候，是最容易出事的。符合了這個前提，就很容易以一人之力，用簡單的方式把你的服務弄掛。

而 ReDoS 就是靠著沒寫好的 regular expression 來達成這件事。

話不多說，直接舉例

直接看範例最快：

1
2
3
4

console.time('test');
/(a|a?)+$/.test('a'.repeat(25) +'b');
console.timeEnd('test');
// test: 2128.498046875 ms

一個 26 個字的字串，需要 2 秒鐘才能配對完畢。順帶一提，這個 regexp 所需要的時間是以倍數計算的，再多一個字需要 4 秒，然後 8 秒，16 秒，以此類推。

那為什麼這個 regexp 需要這麼久的時間呢？

這跟 regexp 引擎的實作以及原理有關，細節我也還沒研究清楚就不誤導大眾了，但簡單來說就是 regexp 引擎必須要遍歷所有的可能性以後才能發現字串不符合，所以花了這麼久的時間。

總而言之，如果 regexp 沒寫好，會造成使用的時候消耗大量時間。

實際案例

你可能會想說，regexp 有這麼容易寫壞嗎？

還真的有，一大堆的 library 都出現過 ReDoS 的漏洞，還有人整理出一個詳細的列表：Awesome ReDoS Security

舉例來說，CKEditor 以前有一個偵測是否是圖片網址的 regexp，傳入精心構造的字串後需要 6 秒才會執行完畢：

1
2
3
4
5
6
7
8

// from: https://github.com/ckeditor/ckeditor5/commit/e36175e86b7f5ca597b39df6e47112b91ab4e0a0
const IMAGE_URL_REGEXP = new RegExp( String( /^(http(s)?:\/\/)?[\w-]+(\.[\w-]+)+[\w._~:/?#[\]@!$&'()*+,;=%-]+/.source +
    /\.(jpg|jpeg|png|gif|ico|webp|JPG|JPEG|PNG|GIF|ICO|WEBP)\??[\w._~:/#[\]@!$&'()*+,;=%-]*$/.source ) );

console.time('test');
IMAGE_URL_REGEXP.test('a.' + 'a'.repeat(100000))
console.timeLog('test')
// test: 6231.137939453125 ms

雖然說字串長度有 10 萬，但如果改成沒問題的版本，不到 1 毫秒就能跑出結果：

1
2
3
4
5
6
7
8

// from: https://github.com/ckeditor/ckeditor5/commit/e36175e86b7f5ca597b39df6e47112b91ab4e0a0
const IMAGE_URL_REGEXP = new RegExp( String( /^(http(s)?:\/\/)?[\w-]+\.[\w._~:/?#[\]@!$&'()*+,;=%-]+/.source +
    /\.(jpg|jpeg|png|gif|ico|webp|JPG|JPEG|PNG|GIF|ICO|WEBP)(\?[\w._~:/#[\]@!$&'()*+,;=%-]*)?$/.source ) );

console.time('test');
IMAGE_URL_REGEXP.test('a.' + 'a'.repeat(100000))
console.timeLog('test')
// test: 0.570068359375 ms

以 JavaScript 來說，這些配對的程式碼都是跑在 main thread，如果是網頁的話會直接畫面凍結，直接卡死，如果是以 Node.js 來執行的伺服器也會卡住，無法處理其他請求。

該怎麼知道有沒有 ReDoS 的風險？

有一些現成的工具可以幫忙，我自己最常用的是這個：https://devina.io/redos-checker

只要把 regexp 丟進去，就可以跟你說有沒有問題，有的話還會附上測試的字串，讓你可以自己再測試一遍。

1
2
3
4
5

app.get('/search', (req, res) => {
    const q = req.query.q
    return users
        .filter(user => new RegExp(q).test(user.username))
})

1
2
3
4

console.time('test');
/((([^m]|[^m]?)+)+)+$/.test('username')
console.timeEnd('test');
// test: 3728.89990234375 ms

1
2
3
4
5
6
7
8
9

console.time('CTF{a');
console.log(/CTF{[a](((((.*)*)*)*)*)!/.test('CTF{this_is_flag}'))
console.timeEnd('CTF{a');
// CTF{a: 0.071ms

console.time('CTF{t');
console.log(/CTF{[t](((((.*)*)*)*)*)!/.test('CTF{this_is_flag}'))
console.timeEnd('CTF{t');
// CTF{t: 24.577s

1. HackTricks – Regular expression Denial of Service – ReDoS
2. OWASP: Regular expression Denial of Service – ReDoS
3. snyk: ReDoS

原文始发于Huli’s blog：正規表達式沒寫好會怎樣？淺談 ReDoS：利用 regexp 的攻擊