January 30, 2015

用 Entropy 分析 Chunking Password 強度

本文為 MOOC 學習筆記。

課程為 University of Maryland 在 Coursera 開的 Usable Security

相關連結:


目錄


( C ) Credit

This article is base on the discussion:

Week 1, Chunking. “08#11#71Lg12#11#81kd” is not a “super secure password”

by Jeffrey Goldberg on the Coursera forum.


(一) Chunking 組合密碼

在 Usable Security 的第一周的課程講義提到了用 Chunking 產生密碼,講者認為這樣能有效提高密碼的安全度,同時也不會太難記憶。針對這個主題,討論區有人提出更深入的討論

在看討論前,先來複習一下何謂 Chunking。

課程中,講師挑選:

  • 兩個日期 (081171,121181)
  • 兩個英文字組(原文稱為 “Initial”),例如人名縮寫 (Lg,kd)
  • 中間交叉插入特殊符號 (#)

作為其密碼生產系統的參數,產生的密碼為 08#11#71Lg12#11#81kd

這組密碼看起來夠複雜;且其具有特殊意義(日期、人名),密碼持有者也容易記憶,看起來是個好記又難破解的”好”密碼。


(二) 密碼的強度與產生密碼的系統息息相關

If you use a system for creating passwords, then the strength of the password created by that system depends on how many different passwords that system can produce. – Better Master Passwords: The geek edition.

舉例來說,F9GndpVkfB44VdvwfUgTxGH7A8trE67AjbDCUotaju9H49sMFgYszA 這兩個密碼長度都不短,且混砸了數字及大小寫英文,看似極為複雜。

但假設用來產生這個密碼的系統如下:投擲一個硬幣,出現正面的話就產生F9GndpVkfB44VdvwfUgTxGH7A8t,反面則產生 rE67AjbDCUotaju9H49sMFgYszA

在這個例子中,密碼本身看似複雜,產生密碼的系統卻十分簡陋,整體而言依然是個不安全(較易被破解)的選擇。這個例子告訴我們,密碼的強度與產生密碼的系統息息相關


(三) 用 Entropy 分析課程中”用來產生密碼的系統”的強度

Entropy 這詞常見於眾多科學領域,包括用來證明熱力學定律、衡量編碼效能、分析字串複雜度、甚至可以拿來解釋魔法少女循環法則(已被證明錯誤的)。

但是在這裡,我們只需關注如何用 Entropy 來量化密碼強度即可。

- 以 2 為底取 log

在算 Entropy 時常常需要做 以 2 為底取 log 的動作。但有些計算機(例如 Google 計算機)不支援這個動作,此時可以用換底公式達到一樣的效果。

舉例來說:

以 2 為底對 8 取 log,用換底公式 log8 / log2 = 3 即可算出。

0. 講義中的密碼產生系統

課程中,我們挑選以下資訊作為其密碼生產系統的參數,產生的密碼為 08#11#71Lg12#11#81kd

  • 兩個日期 (081171,121181)
  • 兩個英文字組(原文稱為 “Initial”),例如人名縮寫 (Lg,kd)
  • 中間交叉插入特殊符號 (#)

接下來以 Entropy 的概念分析此系統產生的密碼強度。

1. 日期

一個日期 (081171) 包含 6 個數字,如果這 6 個數字都是 random number 的話,大約需要 2 的 20 次方來表示,也就是 20 bits。

如果這 6 個數字被限定為日期的話,那麼從 1950 到 2020 間,一共 365*70 = 25550 天,以 2 為底對 25550 取 Log 的話得到 14.64,也就是約需 14 bits 即可表示範圍內的所有組合。而一個人有意義的日期是有限的(生日、結婚紀念日等等),在 targeting attack 前提下,日期的強度可被縮小到剩 8 bits

※假設日期選擇為 70 年內,且每日的機率相等。

2. 插入符號

假設常用的插入符號有 10 種 (!@#$%^&*+-),且每個插入點都插入相同的符號的,則強度為 log10/log2 = 3 bits。

3. 分析英文字組(“Initial”)

密碼持有者通常會選擇對其有特殊意義的英文字組,因此可針對其姓名縮寫、孩子姓名縮寫、父母姓名縮寫等等做 targeting attack,若英文字組為 2~3 個字元且其中一個字元為大寫,則強度約估為 10 bits

4. 總結

將上述所有分析做個總結,則產生08#11#71Lg12#11#81kd這個密碼的系統強度約為:

8 + 8 + 3 + 10 + 10 = 39 bits

對於一個方便記憶的密碼而言,擁有 39 bits 的強度(min-entropy)相當不錯。但用 three words chosen completely at random from the Diceware list 也能達到一樣的效果,詳情可參考這篇文章 Toward Better Master Passwords


(四) 補充說明

  • 根據 Kerckhoffs’s principle,我們在設計密碼系統時,要假設 Your attacker knows what password creation scheme you use。

  • 密碼組合不要使用 ASCII 以外的字元

I tend to advise against using things other than US ASCII in passwords. Even if the specific system handles it fine, there will be problems with different encodings. For example, ü may be represented differently depending on whether one is typing it on a German keyboard or on a US keyboard.


(五) 我的想法:以不同語言互相混和產生密碼

對私人密碼而言,”安全”是第一原則,”好記”是第二原則。

從這篇文章分析的觀點來說,加強 Initial隨機程度密碼長度都能有效提升安全性。

另外我覺得以不同語言輸入法互相混和也是個相當不錯的密碼產生方式,舉例來說:

某個密碼為 “ji3yjo494eattebasaki”,看起來相當複雜,但其實只是”我最愛吃雞翅”的中英日混和:

  • 我最愛吃雞翅
  • 我最愛eatてばさき
  • ji3yjo494eattebasaki

這個方法能避免掉本篇提及的問題,且長度更長,本質與 Diceware 類似但更方便記憶。

- 延伸範例

我老婆系列:

  • 我老婆花澤香菜
  • mywife花澤かな
  • maiwaifucj8yk6kana

決鬥系列:

  • 初音只是個軟體
  • 初音はただのsoftware
  • tjuphatadanosoftware

陳菊.avi:

  • 陳菊在我床上
  • 陳菊在僕のbed
  • tp6rm6.avi@bokunobed

ね、簡単でしょう?

VoiceTube 看影片學英文