常見驗證碼的弱點與驗證碼識別

科普好文：常見驗證碼的弱點與驗證碼識別實例詳細解說發(fā)表于2年前|作者:seay|分類:

科普專線,

編程開發(fā)

|孵化于:2013年06月18日|文章熱度:4,108次全屏閱讀顯示不全請點擊全屏閱讀0x00簡介驗證碼作為一種輔助安全手段在Web安全中有著特殊的地位，驗證碼安全和web應用中的眾多漏洞相比似乎微不足道，但是千里之堤毀于蟻穴，有些時候如果能繞過驗證碼，則可以把手動變?yōu)樽詣?，對于Web安全檢測有很大的幫助。全自動區(qū)分計算機和人類的圖靈測試（英語：CompletelyAutomatedPublicTuringtesttotellComputersandHumansApart，簡稱CAPTCHA），俗稱驗證碼，是一種區(qū)分用戶是計算機和人的公共全自動程序。在CAPTCHA測試中，作為服務器的計算機會自動生成一個問題由用戶來解答。這個問題可以由計算機生成并評判，但是必須只有人類才能解答。由于計算機無法解答CAPTCHA的問題，所以回答出問題的用戶就可以被認為是人類。(from

wikipedia)大部分驗證碼的設計者都不知道為什么要用到驗證碼，或者對于如何檢驗驗證碼的強度沒有任何概念。大多數驗證碼在實現的時候只是把文字印到背景稍微復雜點的圖片上就完事了，程序員沒有從根本上了解驗證碼的設計理念。驗證碼的形式多種多樣，先介紹最簡單的純文本驗證碼。純文本驗證碼純文本，輸出具有固定格式，數量有限，例如：?1+1=?

?本論壇的域名是?

?今天是星期幾?

?復雜點的數學運算

這種驗證碼并不符合驗證碼的定義，因為只有自動生成的問題才能用做驗證碼，這種文字驗證碼都是從題庫里選擇出來的，數量有限。破解方式也很簡單，多刷新幾次，建立題庫和對應的答案，用正則從網頁里抓取問題，尋找匹配的答案后破解。也有些用隨機生成的數學公式，比如隨機數[+-*/]隨機運算符隨機數=?，小學生水平的程序員也可以搞定……這種驗證碼也不是一無是處，對于很多見到表單就來一發(fā)的spambot來說，實在沒必要單獨為了一個網站下那么大功夫。對于鐵了心要在你的網站大量灌水的人，這種驗證碼和沒有一樣。下面講的是驗證碼中的重點，圖形驗證碼。圖形驗證碼先來說一下基礎：識別圖形驗證碼可以說是計算機科學里的一項重要課題，涉及到計算機圖形學，機器學習，機器視覺，人工智能等等高深領域……簡單地說，計算機圖形學的主要研究內容就是研究如何在計算機中表示圖形、以及利用計算機進行圖形的計算、處理和顯示的相關原理與算法。圖形通常由點、線、面、體等幾何元素和灰度、色彩、線型、線寬等非幾何屬性組成。計算機涉及到的幾何圖形處理一般有2維到n維圖形處理，邊界區(qū)分，面積計算，體積計算，扭曲變形校正。對于顏色則有色彩空間的計算與轉換，圖形上色，陰影，色差處理等等。在破解驗證碼中需要用到的知識一般是像素，線，面等基本2維圖形元素的處理和色差分析。常見工具為：?支持向量機(SVM)

?OpenCV

?圖像處理軟件(Photoshop,Gimp…)

?PythonImageLibrary

支持向量機SVM是一個機器學習領域里常用到的分類器，可以對圖形進行邊界區(qū)分，不過需要的背景知識太高深。OpenCV是一個很常用的計算機圖像處理和機器視覺庫，一般用于人臉識別，跟蹤移動物體等等，對這方面有興趣的可以研究一下PS,GIMP就不說了，說多了都是淚啊……PythonImageLibrary是pyhon里面帶的一個圖形處理庫，功能比較強大，是我們的首選。SVM圖像邊界區(qū)分SVM原理，把數據映射到高維空間，然后尋找能夠分割的超平面識別驗證碼需要充分利用圖片中的信息，才能把驗證碼的文字和背景部分分離，一張典型的jpeg圖片，每個像素都可以放在一個5維的空間里，這5個維度分別是，X,Y,R,G,B，也就是像素的坐標和顏色，在計算機圖形學中，有很多種色彩空間，最常用的比如RGB，印刷用的CYMK，還有比較少見的HSL或者HSV，每種色彩空間的維度都不一樣，但是可以通過公式互相轉換。RGB色彩空間構成的立方體，每個維度代表一種顏色HSL（色相飽和度）色彩空間構成的錐體，可以參考：/wiki/HSL%E5%92%8CHSV%E8%89%B2%E5%BD%A9%E7%A9%BA%E9%97%B4了解到色彩空間的原理，就可以用在該空間適用的公式來進行像素的色差判斷，比如RGB空間里判斷兩個點的色差可以用3維空間中兩坐標求距離的公式：distance=sqrt[(r1-r2)^2+(g1-g2)^2+(b1-b2)^2]更加直觀的圖片，大家感受一下：隨便把一張圖片的每個像素都映射到RGB色彩空間里就能獲得一個這樣的立方體。通過對像素顏色進行統(tǒng)計和區(qū)分，可以獲得圖片的顏色分布，在驗證碼中，一般來說使用近似顏色最多的像素都是背景，最少的一般為干擾點，干擾線和需要識別文字本身。對于在RGB空間中不好區(qū)分顏色，可以把色彩空間轉換為HSV或HSL：0x01驗證碼識別的原理和過程

第一步：

二值化所謂二值化就是把不需要的信息通通去除，比如背景，干擾線，干擾像素等等，只剩下需要識別的文字，讓圖片變成2進制點陣。第二步：文字分割為了能識別出字符，需要對要識別的文字圖圖片進行分割，把每個字符作為單獨的一個圖片看待。第三步：標準化對于部分特殊的驗證碼，需要對分割后的圖片進行標準化處理，也就是說盡量把每個相同的字符都變成一樣的格式，減少隨機的程度最簡單的比如旋轉還原，復雜點的比如扭曲還原等等第四步：識別這一步可以用很多種方法，最簡單的就是模板對比，對每個出現過的字符進行處理后把點陣變成字符串，標明是什么字符后，通過字符串對比來判斷相似度。在文章的后半部分會詳細解釋每步的各種算法二值化算法對于大部分彩色驗證碼，通過判斷色差和像素分布都能準確的把文字和背景分離出來，通過PS等工具把圖片打開，用RGB探針對文字和背景圖的顏色分別測試，在測試多張圖片后，很容易可以發(fā)現文字和背景圖的RGB差距總是大于一個固定的閾值，即使每次圖片的文字和背景顏色都會變化，比如：新浪和discuz的驗證碼通過對文字部分和干擾部分取樣可以發(fā)現，文字部分的R、G值一般在100左右，B值接近255，但是背景干擾的R、G值則大大高于文字部分，接近200，比較接近文字輪廓部分的像素的RG值也在150以上。通過程序遍歷一遍像素就可以完全去掉背景。Discuz的驗證碼同理對于一些和文字顏色相同但是較為分散和單一的干擾像素點，我們可以用判斷相鄰像素的方法，對于每個點判斷該點和相鄰8個點的色差，若色差大于某個值，則+1，如果周圍有超過6個點的色差都比較大，說明這個點是噪點。對于圖像邊界的一圈像素，周圍沒有8個像素，則統(tǒng)統(tǒng)清除，反正文字都在圖片的中間位置。如下圖：假如當前像素的坐標是x,y

圖形坐標系的原點是圖像的左上角干擾線對于識別驗證碼增加了一些難度，不過干擾線只有很小的幾率會以大角度曲線的方式出現，大部分時間還是小角度直線，去除算法可以參考/view/63bac64f2b160b4e767fcfed.html對于1個像素粗細的干擾線，在字符為2個像素以上的時候，可以用去噪點算法作為濾鏡，多執(zhí)行幾次，就可以完美的把細干擾線去掉。對于像素數比干擾點稍大的干擾色塊，可以采用的算法有：油漆桶算法（又叫種子填充算法，Floodfill）種子填充算法可以方便的計算出任意色塊的面積，對于沒有粘連字符或者粘連但是字符每個顏色不一樣的驗證碼來說，去除干擾色塊的效果很好，你只需要大概計算一下最小的和最大的字符平均占多少像素，然后把這段區(qū)間之外像素數的色塊排除掉即可。

上下左右4個方向填充還有8個方向填充的不同判斷顏色分布：對于大多數彩色驗證碼來說，文字基本在圖片中心的位置，每個字符本身的顏色是一樣的，也就是說對于文字來說，同一種顏色基本都集中在一個固定的區(qū)域范圍內，通過統(tǒng)計圖片中的像素，按近似顏色分組，同時分析每個顏色組在圖片中的分布范圍，假如說有一種顏色大部分像素都在圖片邊緣，那么這個顏色肯定不屬于要識別的字符，可以去掉。對于干擾線，并沒有一種十分有效的方式能完全去除并且不影響到文字，不過如果能夠成功分割字符的話，少量干擾線對于識別率影響不大。字符分割算法破解驗證碼的重點和難點就在于能否成功分割字符，這一點也是機器視覺里的一道難題，對物件的識別能力。對于顏色相同又完全粘連的字符，比如google的驗證碼，目前是沒法做到5%以上的識別率的。不過google的驗證碼基本上人類也只有30%的識別率對于字符之間完全沒有粘連的驗證碼，比如這個->_->

分割起來是非常的容易，用最基本的掃描線法就可以分割，比如從最左側開始從上到下（y=0—||||y=n）掃描，如果沒有遇到任何文字的像素，就則往右一個像素然后再掃描，如果遇到有文字像素存在，就記錄當前橫坐標,繼續(xù)向右掃，突然沒有文字像素的時候，就說明到了兩個字符直接的空白部分，重復這個步驟再橫向掃描就能找到每個字符最邊緣4個像素的位置，然后可以用PIL內建的crop功能把單獨的字符摳出來。對于有少許粘連但是只是在字符邊角的地方重疊幾個像素的驗證碼，可以用垂直像素直方圖的統(tǒng)計方法分割。如下圖：圖上半部分是垂直像素直方圖的一種直觀展示，假如圖片寬度為100像素，則把圖片切割為100個1像素的豎線，下面的紅色部分為當前x坐標上所有黑色像素的總和。這么一來可以很容易的通過直方圖的波峰波谷把4個字母分割開。圖片的下半部分是掃描線分隔法，因為干擾線和字符旋轉的存在，只有M和5直接才出現了連續(xù)的空白部分。除了垂直像素直方圖，還可以從不同的角度進行斜線方向的像素數投影，這種方式對于每次全體字符都隨機向一個角度旋轉的驗證碼效果很好。對于每次字符大小和數量都一樣的驗證碼還可以用平均分割法，也就是直接先把中間的文字部分整體切出來，然后按寬度平均分成幾份，這種方式對字符粘連比較多用其他方式不好分割的驗證碼很有用，之前的megaupload的3位字母驗證碼就是通過這種方式成功分割的。另外對于彩色的驗證碼，還可以用顏色分割，比如12306的：12306的驗證碼，每個字符顏色都不一樣，真是省事啊。作為驗證碼識別里的難點，分割字符還有很多種算法，包括筆畫分析曲線角度分析等等，不過即便如此，對粘連的比較厲害的字符還是很難成功的。標準化標準化的意思是指對于同一個字符，盡可能讓每次識別前的樣本都一致，以提高識別率。而驗證碼設計者則會用隨機旋轉，隨機扭曲還有隨機字體大小的方式防止字符被簡單方法識別。還原隨機旋轉的字符一般采用的是旋轉卡殼算法：此算法非常簡單，對一張圖片左右各旋轉30度的范圍，每次1度，旋轉后用掃描線法判斷字符的寬度，對于標準的長方形字體，在完全垂直的時候肯定是寬度最窄的。嗯？納尼？上面的圖是中間的最窄？好像的確是這樣，不過只要每次旋轉后的結果都一樣，對于識別率不會有影響。扭曲還原的算法比較蛋疼，效果也不怎么樣（其實我不會），不過如果識別算法好的話，對扭曲的字符只要人能認出來，識別率也可以達到接近人類的水準。還有一些常用到的算法，對于提高識別率和減少樣本數量有一定幫助：骨架細化：腐蝕算法腐蝕算法的原理有點像剝洋蔥，從最外層沿著最外面的一層像素一圈一圈的去掉，直到里面只剩下一層像素為止。腐蝕算法里面需要用到另一個算法，叫做凸包算法，用來找一堆像素點里面最外圍的一層。最后就是把字符變成統(tǒng)一大小，一般而言是把全部字符都縮到和驗證碼里出現過的最小的字符一個大小。詳情請自行google……分割算法差不多就到這里了，都是一些比較基礎的內容。下面是最終的識別。0x02識別其實到了這一步，單獨的字符已經分離出來了，可以訓練tesseractocr來識別了，樣本數量多的話，識別率也是很高的。不過在這里還是要講一下，如何自己來實現識別過程。第一步，樣本現在應該已經是一個矩陣的形式了，有像素的地方是1，背景是0，先肉眼識別一下，然后把這個矩陣轉換為字符串，建立一個鍵值對，標明這串字符串是什么字符。之后就只需要多搜集幾個同樣字符的不同字符串變形，這就是制作模板的過程，。搜集了足夠多的模板后，就可以開始識別了，最簡單的方法：漢明距離，但是如果字符有少許扭曲的話，識別率會低的離譜。對比近似字符串用的最多一般是編輯距離算法(LevenshteinDistance)，具體請自己google。兩種算法的差別在于，對同樣兩個字符串對比10010101和10101010，漢明距離是6，但是編輯距離是2。最后一種最NB的識別算法，就是神經網絡，神經網絡是一種模擬動物神經元工作模式的算法，神經網絡有多種不同的結構，但是基本架構分為輸入層，隱含層和輸出層，輸入和輸出均為二進制。對于驗證碼識別來說，輸入和輸出節(jié)點不宜過多，因為多了很慢……所以如果樣本矩陣為20×20400個像素的話，需要對應的也要有400個輸入節(jié)點，因此我們需要對整個矩陣提取特征值，比如先橫向每兩個數字XOR一下，然后再豎向每兩個數字XOR。Python有很多封裝好的神經網絡庫，你所需要的只是把特征值輸入神經網絡，再告訴他你給他的是什么（字符），這樣多喂幾次之后，也就是訓練的過程，隨著訓練的進行，神經網絡的內部結構會改變，逐漸向正確的答案靠攏。神經網絡的優(yōu)勢是，對于扭曲的字符識別成功率非常高。另外神經網絡在信息安全中還可以起到很多其他作用，比如識別惡意代碼等等。動畫驗證碼有些不甘寂寞的程序員又玩出了些新花樣，比如各種GIF甚至flv格式的動畫驗證