Transcript Diceware Passphrase Generator

Homework 7
How to generate high-quality true
randomness by hand
(Proposed by Arnold G. Reinhold)
Advisor: Prof. Jen-Chang Liu
Graduate Student: Yi-Ching Chen(陳怡靜)
92321527
Motive



Generating randomness by computer offers numerous
opportunities for error and attack.
Simple dice present an attractive alternative if used
properly.
This paper presents a number of techniques for using
dice in conjunction with modern cryptographic
software.
Random number generator
2
Introduction




PGP (Pretty Good Privacy) 提供e-mail和檔案儲存程
式的安全認證加密的服務
Many PGP users choose weak passphrases.
For the users adopting stronger passphrases, Reinhold
have developed a Diceware Passphrase Generator.
Diceware Passphrase


simple technique for creating short, memorable passphrases that are highly secure.
requiring no computer hardware or software.
Random number generator
3
Diceware Passphrase



The Diceware Passphrase Generator is a word list
indexed so that words can be randomly selected by
tossing five dice.
The list contains 7776 (= 65)short English words,
abbreviations and easy to remember character strings.
Example
16655
clause
16656
claw
16661
clay
16662
clean
16663
clear
16664
cleat
16665
cleft
16666
clerk
21111
cliche
21112
click
21113
cliff
21114
climb
Random number generator
4
Word List


16661 clay
16664 cleat
21111 cliche
21114 climb
Rolling five dice and they came up 2, 1, 1, 1, 3, your
next pass phrase word would be "cliff".
A printed copy of the word list


16655 clause 16656 claw
16662 clean 16663 clear
16665 cleft 16666 clerk
21112 click 21113 cliff
format the word list with 4 columns and 54 lines per page.
(63 = 454) You will get a neat, 36 page printout in which
the first two dice throws are constant for each page.
How long should the passphrase be?


Reinhold would recommend a five word passphrase for use
with PGP, ViaCrypt and similar encryption programs.
In general, a four ~ six word passphrase will provide
protection.
Random number generator
5
Word List


The list can also be used to generate login passwords
for multi-user computer services by just concatenating
two words
Reinhold recommend adding a random special
character between the words, for example
"dobbs(heron".
Random number generator
6
Why Diceware?

The random word selection process proposed by Peter
Kwangjun Suk.




Could be done by computer when Suk posted his word list.
The source code must undergo public review and the object
programs have to be distributed in a trustworthy way.
Most users will not bother to authenticate their copy even
though it could easily have been be doctored to produce
predictable passphrases.
Any password generating program is subject to a whole
range of electronic attacks even after a verified copy has
been installed on a user's machine.
Random number generator
7
Why Diceware?

Diceware approach

tamperproof, easy to understand, platform independent,
immune from electronic attack and cryptographically
strong.
Random number generator
8
Construction of the Diceware
Passphrase Generator




Suk's original list had 10760 entries.
Reinhold added some more 3 and 4 character
sequences that are easy-to-remember, like "300" and
"aaaa", and then trimmed the list to 7776 entries by
deleting all but about one in seven of Suk's 3796 sixcharacter words.
The list contains 7776 (= 65)short English words,
abbreviations and easy to remember character strings.
The average length of each word is about 4.2
characters. The longest words are six characters.
Random number generator
9
Construction of the Diceware
Passphrase Generator


The list was alphabetized using Microsoft Excel, which
sorts pure numbers ahead of mixed alphanumeric
strings. Numerics and special characters were moved to
the end of the list.
The index values are all the five-digit base-6 numbers,
but with the digits running from 1 to 6 to match dice
markings.
Random number generator
10
Analysis of the Diceware Passphrase
Generator’s Security

Reinhold’s word list




Selecting a word at random from the resulting list has an
entropy value of 8.96 (= log2 7776) bits.
The average length of each word is 4.239 characters.
A passphrase generated from this list will average an
entropy of 2.11 (= 12.92/4.239) bits per character, not
counting the spaces between words.
Suk's original list



9.28 bits of entropy per word
The average word length was 4.77 characters
1.95 bits of entropy per character
Random number generator
11
Tampering with the Diceware Generator



The Diceware Generator word list is inherently tamper
proof.
The possible tampering is to shorten it or to introduce
numerous duplicate entries.
Since the entries are numbered and are in alphabetical
order, it is easy to detect any such irregularities. When
you select a word, check to make sure it is in the
proper alphabetical order and is not a duplicate.
Random number generator
12
Diceware Tables for Generating
Routing Strings
Right

1 2 3 4 5 6
1 A B C D E F
2 G H I

J K L
Left
3 M N O P Q R

Table 1. Alphanumeric
characters
Rolling a pair of dice
and look up each roll in
the appropriate table.
Example
4 S T U V W X
5 Y Z 0 1 2 3

A roll where the left die
is 4 and the right die is 2
results in the letter "T".
6 4 5 6 7 8 9
Random number generator
13
Diceware Tables for Generating
Routing Strings
Right

1 2 3 4 5 6
1 0 1 2 3 4 5

Table 2. Decimal
numbers
* = roll again
2 6 7 8 9 0 1
Left
3 2 3 4 5 6 7
4 8 9 0 1 2 3
5 4 5 6 7 8 9
6 * * * * * *
Random number generator
14
Diceware Tables for Generating
Routing Strings
Right

1 2 3 4 5 6
1 0 1 2 3 4 5

Table 3. Hexadecimal
numbers
* = roll again
2 6 7 8 9 A B
Left
3 C D E F 0 1
4 2 3 4 5 6 7
5 8 9 A B C D
6 E F * * * *
Random number generator
15
Diceware Tables for Generating
Routing Strings
Middle

1 2 3 4 5 6
B
C D
F
2
J
K
L
M N
QU R
S
T
3
4
X
1
A
P
2
E
V W
3
I
4
O
G H
Z CH CR FR ND
Right
Left
1
5
NG NK NT PH PR PD
5
U
6
SH SL SP ST TH TR
6
Y
Random number generator
Table 4. Syllables
(Use three dice)
16
Diceware Tables for Generating
Routing Strings
Right
1
1
2

3
4
5
6
! @ #
$
% ^
Left
2 & *
(
)
-
_
3 + =
[
]
{
}
4 ;
:
‘
“
,
.
5 < >
/
?
` ~
6 |
Table 5. Special
characters
\ -- == .. //
Random number generator
17
Diceware Tables for Generating
Routing Strings
Right

1
2
3
4
5
6
1
1
2
3
4
5
6
2
7
8
9
10 11 12
Table 6. Random
numbers from 1 to 36
Left
If you need random numbers in
a smaller range, just roll again
when a number outside your
range comes up.
3
13 14 15 16 17 18
4
19 20 21 22 23 24
5
For numbers
25 26 27 28
29 30 in the range 1 to 216, roll three dice
6
31 32 33 34 35 36
and use this formula:
Left die + 6(Middle die - 1) + 36(Right die - 1)
Random number generator
18