正規表達式沒寫好會怎樣?淺談 ReDoS:利用 regexp 的攻擊
2023-6-12 14:10:44 Author: blog.huli.tw(查看原文) 阅读量:13 收藏

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');

一個 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

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')

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

1
2
3
4
5
6
7
8

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')

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

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

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

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

devina redos checker

不過有時候會有 false positive 就是了,它覺得有但是沒有,或也有可能真的有,但是它給的攻擊字串跑不出來。因此還是建議測完以後自己拿它給的 payload 再試一次,確認一下。

ReDoS 在攻擊上的應用

前面講的都是「regexp 已經寫好,而使用者可以控制輸入」,這時候只要找到有問題的 regexp 產生攻擊字串即可。

而有另外一種狀況是:「使用者可以控制 regexp」。舉例來說,假設有個網站提供搜尋使用者的功能,你可以傳入一個 regexp,伺服器就會回傳是否有符合此 regexp 的 username 存在。

伺服器的實作大概如下(隨意寫的,意思有到就好):

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))
})

這個危險的功能除了可以讓攻擊者把所有的 username 都拿到手以外,也會有 ReDoS 的風險在。

舉例來說,當 /((([^m]|[^m]?)+)+)+$/ 這個 regexp 碰到 "username" 時,需要花費將近 4 秒才能跑完:

1
2
3
4
console.time('test');
/((([^m]|[^m]?)+)+)+$/.test('username')
console.timeEnd('test');

只要繼續按照相同的模式把 regexp 延伸下去,就可以讓這整段程式碼執行超過 30 秒或是更久,癱瘓整個 server。

在打 CTF 時還有另一種常見的狀況是一樣可以傳入 regexp,但是伺服器不會跟你講有沒有成功,你只能根據時間差來判斷,這時候靠 ReDoS 就很有用了:

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');


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

透過傳入精心構造的 regexp,就可以利用時間差得知第一個字元是什麼。

最後簡單提一下防禦方式,最根本的解決方法就是不要寫出有缺陷的 regexp,先去學習哪一些 pattern 應該盡量少用,就能掌握到大概的方向。除此之外,似乎也有人做了一些自動化的工具幫忙掃 code 裡面出現的 regexp,這也是一種在出事前先預防的方法。

總結

我自己覺得 ReDoS 是一個滿有趣的攻擊方式,以前沒想過靠著 regexp 還可以做出這種效果。

以前第一次知道這個攻擊,似乎是還在當開發者的時候,偶爾會看到使用到的 library 有這個漏洞,不過當初沒有很在意就是了。後來在資安裡面再度碰到這東西,才覺得好像挺有趣的。

這篇比較像是我的個人筆記,只是想趁著記憶猶新的時候把一些 payload 記下來,以後比較好找。

最後附上一些參考資料以及延伸閱讀,有興趣深入了解的讀者們可以看一下:

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

文章来源: https://blog.huli.tw/2023/06/12/redos-regular-expression-denial-of-service/
如有侵权请联系:admin#unsafe.sh