`b28665aebb4c1b07a57890eb59551bc51d0acf37`

Author: Roman Perepelitsa <roman.perepelitsa@gmail.com>
Committer: GitHub <noreply@github.com>
Date: 2020-12-16 15:57 UTC

Message

fix(genpass): improve performance and usability and fix bugs (#9520)

*Bugs*

The following bugs have been fixed:

- All generators ignored errors from external commands. For example,
  if `/usr/share/dict/words` was unreadable, `genpass-xkcd` would
  print "0-" as a password and return success.
- All generators silently ignored the argument if it wasn't a number.
  For example, `genpass-apple -2` was generating one password and
  not printing any errors.
- All generators silently ignored extra arguments. For example,
  `genpass-apple -n 2` was generating one password and not printing
  any errors.
- `genpass-xkcd` was generating passwords with less than 128 bits of
  security margin in contradiction to documentation. The smaller the
  dictionary size, the weaker the passwords it was generating. For a
  dictionary with 27 words, `genpass-xkcd` was generating passwords
  with 93 bits of security margin (`log2(27!)`).
- The source of random data used by `genpass-xkcd` was not
  cryptographically secure in contradiction to documentation. See:
  https://www.gnu.org/software/coreutils/manual/html_node/Random-sources.html
- `genpass-apple` could generate a password with non-ascii characters
  depending on user locale. For example, passwords could contain 'İ'
  for users with Turkish locale.
- `genpass-apple` didn't work with `ksh_arrays` shell option.
- `genpass-xkcd` was printing spurious errors with `ksh_arrays` shell
  option.
- `genpass-xkcd` was producing too short (weak) or too strong (long)
  and/or printing errors when `IFS` was set to non-default value.
- All generators were printing fewer passwords than requested and
  returning success when passed a very large number as an argument.

*Usability*

Generators are now implemented as self-contained executable files.
They can be invoked from scripts with no additional setup.

Generators no longer depend on external commands. The only dependencies
are `/dev/urandom` and, for `genpass-xkcd`, `/usr/share/dict/words`.

All generators used to silently ignore all arguments after the first
and the first argument if it wasn't a number. For example, both
`genpass-apple -2` and `genpass-apple -n 2` were generating one password
and not printing any errors. Now these print an error and fail.

*Performance*

The time it takes to load the plugin has been greatly reduced. This
translates into faster zsh startup when the plugin is enabled.

Incidentally, two generators out of three have been sped up to a large
degree while one generator (`genpass-xkcd`) has gotten slower. This is
unlikely to matter one way or another unless generating a very large
number of passwords. In the latter case `genpass-xkcd` is now also
faster than it used to be.

The following table shows benchmark results from Linux x86-64 on i9-7900X.
The numbers in the second and third columns show how many times a given
command could be executed per second. Higher numbers are better.

command                     | before (Hz) | after (Hz) | speedup |
----------------------------|------------:|-----------:|--------:|
`source genpass.plugin.zsh` |        4810 |      68700 |  +1326% |
`genpass-apple`             |        30.3 |        893 |  +2846% |
`genpass-monkey`            |         203 |       5290 |  +2504% |
`genpass-xkcd`              |        34.4 |       14.5 |    -58% |
`genpass-xkcd 1000`         |       0.145 |      0.804 |   +454% |

Diff

This diff is truncated to protect this page.

  1diff --git a/plugins/genpass/README.md b/plugins/genpass/README.md
  2index e6e7a513825f6c0802024a1de5a819928e6df073..a5ff4a876008e503c7d9fcdc935863cfe26c72ab 100644
  3--- a/plugins/genpass/README.md
  4+++ b/plugins/genpass/README.md
  5@@ -5,21 +5,22 @@ has at least a 128-bit security margin and generates passwords from the
  6 cryptographically secure `/dev/urandom`. Each generator can also take an
  7 optional numeric argument to generate multiple passwords.
  8 
  9-Requirements:
 10+To use it from an interactive ZSH, add `genpass` to the plugins array in your
 11+zshrc file:
 12 
 13-* `grep(1)`
 14-* GNU coreutils (or appropriate for your system)
 15-* Word list providing `/usr/share/dict/words`
 16+    plugins=(... genpass)
 17 
 18-To use it, add `genpass` to the plugins array in your zshrc file:
 19+You can also invoke password generators directly (they are implemented as
 20+standalone executable files), which can be handy when you need to generate
 21+passwords in a script:
 22 
 23-    plugins=(... genpass)
 24+    ~/.oh-my-zsh/plugins/genpass/genpass-apple 3
 25 
 26 ## genpass-apple
 27 
 28 Generates a pronounceable pseudoword passphrase of the "cvccvc" consonant/vowel
 29 syntax, inspired by [Apple's iCloud Keychain password generator][1]. Each
 30-pseudoword has exactly 1 digit placed at the edge of a "word" and exactly 1
 31+password has exactly 1 digit placed at the edge of a "word" and exactly 1
 32 capital letter to satisfy most password security requirements.
 33 
 34     % genpass-apple
 35diff --git a/plugins/genpass/genpass-apple b/plugins/genpass/genpass-apple
 36new file mode 100755
 37index 0000000000000000000000000000000000000000..963ab644723ed5b492d5fa1a645ee38b10142e9e
 38--- /dev/null
 39+++ b/plugins/genpass/genpass-apple
 40@@ -0,0 +1,79 @@
 41+#!/usr/bin/env zsh
 42+#
 43+# Usage: genpass-apple [NUM]
 44+#
 45+# Generate a password made of 6 pseudowords of 6 characters each
 46+# with the security margin of at least 128 bits.
 47+#
 48+# Example password: xudmec-4ambyj-tavric-mumpub-mydVop-bypjyp
 49+#
 50+# If given a numerical argument, generate that many passwords.
 51+
 52+emulate -L zsh -o no_unset -o warn_create_global -o warn_nested_var
 53+
 54+if [[ ARGC -gt 1 || ${1-1} != ${~:-<1-$((16#7FFFFFFF))>} ]]; then
 55+  print -ru2 -- "usage: $0 [NUM]"
 56+  return 1
 57+fi
 58+
 59+zmodload zsh/system zsh/mathfunc || return
 60+
 61+{
 62+  local -r vowels=aeiouy
 63+  local -r consonants=bcdfghjklmnpqrstvwxz
 64+  local -r digits=0123456789
 65+
 66+  # Sets REPLY to a uniformly distributed random number in [1, $1].
 67+  # Requires: $1 <= 256.
 68+  function -$0-rand() {
 69+    local c
 70+    while true; do
 71+      sysread -s1 c || return
 72+      # Avoid bias towards smaller numbers.
 73+      (( #c < 256 / $1 * $1 )) && break
 74+    done
 75+    typeset -g REPLY=$((#c % $1 + 1))
 76+  }
 77+
 78+  local REPLY chars
 79+
 80+  repeat ${1-1}; do
 81+    # Generate 6 pseudowords of the form cvccvc where c and v
 82+    # denote random consonants and vowels respectively.
 83+    local words=()
 84+    repeat 6; do
 85+      words+=('')
 86+      repeat 2; do
 87+        for chars in $consonants $vowels $consonants; do
 88+          -$0-rand $#chars || return
 89+          words[-1]+=$chars[REPLY]
 90+        done
 91+      done
 92+    done
 93+
 94+    local pwd=${(j:-:)words}
 95+
 96+    # Replace either the first or the last character in one of
 97+    # the words with a random digit.
 98+    -$0-rand $#digits || return
 99+    local digit=$digits[REPLY]
100+    -$0-rand $((2 * $#words)) || return
101+    pwd[REPLY/2*7+2*(REPLY%2)-1]=$digit
102+
103+    # Convert one lower-case character to upper case.
104+    while true; do
105+      -$0-rand $#pwd || return
106+      [[ $vowels$consonants == *$pwd[REPLY]* ]] && break
107+    done
108+    # NOTE: We aren't using ${(U)c} here because its results are
109+    # locale-dependent. For example, when upper-casing 'i' in Turkish
110+    # locale we would get 'İ', a.k.a. latin capital letter i with dot
111+    # above. We could set LC_CTYPE=C locally but then we would run afoul
112+    # of this zsh bug: https://www.zsh.org/mla/workers/2020/msg00588.html.
113+    local c=$pwd[REPLY]
114+    printf -v c '%o' $((#c - 32))
115+    printf "%s\\$c%s\\n" "$pwd[1,REPLY-1]" "$pwd[REPLY+1,-1]" || return
116+  done
117+} always {
118+  unfunction -m -- "-${(b)0}-*"
119+} </dev/urandom
120diff --git a/plugins/genpass/genpass-monkey b/plugins/genpass/genpass-monkey
121new file mode 100755
122index 0000000000000000000000000000000000000000..94ff5e13123ccec1e32a6a0a070478f6fa1ec3f6
123--- /dev/null
124+++ b/plugins/genpass/genpass-monkey
125@@ -0,0 +1,32 @@
126+#!/usr/bin/env zsh
127+#
128+# Usage: genpass-monkey [NUM]
129+#
130+# Generate a password made of 26 alphanumeric characters
131+# with the security margin of at least 128 bits.
132+#
133+# Example password: nz5ej2kypkvcw0rn5cvhs6qxtm
134+#
135+# If given a numerical argument, generate that many passwords.
136+
137+emulate -L zsh -o no_unset -o warn_create_global -o warn_nested_var
138+
139+if [[ ARGC -gt 1 || ${1-1} != ${~:-<1-$((16#7FFFFFFF))>} ]]; then
140+  print -ru2 -- "usage: $0 [NUM]"
141+  return 1
142+fi
143+
144+zmodload zsh/system || return
145+
146+{
147+  local -r chars=abcdefghjkmnpqrstvwxyz0123456789
148+  local c
149+  repeat ${1-1}; do
150+    repeat 26; do
151+      sysread -s1 c || return
152+      # There is uniform because $#chars divides 256.
153+      print -rn -- $chars[#c%$#chars+1]
154+    done
155+    print
156+  done
157+} </dev/urandom
158diff --git a/plugins/genpass/genpass-xkcd b/plugins/genpass/genpass-xkcd
159new file mode 100755
160index 0000000000000000000000000000000000000000..a486ccb40e2057593bb997c46d162362ccaa375d
161--- /dev/null
162+++ b/plugins/genpass/genpass-xkcd
163@@ -0,0 +1,68 @@
164+#!/usr/bin/env zsh
165+#
166+# Usage: genpass-xkcd [NUM]
167+#
168+# Generate a password made of words from /usr/share/dict/words
169+# with the security margin of at least 128 bits.
170+#
171+# Example password: 9-mien-flood-Patti-buxom-dozes-ickier-pay-ailed-Foster
172+#
173+# If given a numerical argument, generate that many passwords.
174+#
175+# The name of this utility is a reference to https://xkcd.com/936/.
176+
177+emulate -L zsh -o no_unset -o warn_create_global -o warn_nested_var -o extended_glob
178+
179+if [[ ARGC -gt 1 || ${1-1} != ${~:-<1-$((16#7FFFFFFF))>} ]]; then
180+  print -ru2 -- "usage: $0 [NUM]"
181+  return 1
182+fi
183+
184+zmodload zsh/system zsh/mathfunc || return
185+
186+local -r dict=/usr/share/dict/words
187+
188+if [[ ! -e $dict ]]; then
189+  print -ru2 -- "$0: file not found: $dict"
190+  return 1
191+fi
192+
193+# Read all dictionary words and leave only those made of 1-6 characters.
194+local -a words
195+words=(${(M)${(f)"$(<$dict)"}:#[a-zA-Z](#c1,6)}) || return
196+
197+if (( $#words < 2 )); then
198+  print -ru2 -- "$0: not enough suitable words in $dict"
199+  return 1
200+fi
201+
202+if (( $#words > 16#7FFFFFFF )); then
203+  print -ru2 -- "$0: too many words in $dict"
204+  return 1
205+fi
206+
207+# Figure out how many words we need for 128 bits of security margin.
208+# Each word adds log2($#words) bits.
209+local -i n=$((ceil(128. / log2($#words))))
210+
211+{
212+  local c
213+  repeat ${1-1}; do
214+    print -rn -- $n
215+    repeat $n; do
216+      while true; do
217+        # Generate a random number in [0, 2**31).
218+        local -i rnd=0
219+        repeat 4; do
220+          sysread -s1 c || return
221+          (( rnd = (~(1 << 23) & rnd) << 8 | #c ))
222+        done
223+        # Avoid bias towards words in the beginning of the list.
224+        (( rnd < 16#7FFFFFFF / $#words * $#words )) || continue
225+        print -rn -- -$words[rnd%$#words+1]
226+        break
227+      done
228+    done
229+    print
230+  done
231+} </dev/urandom
232diff --git a/plugins/genpass/genpass.plugin.zsh b/plugins/genpass/genpass.plugin.zsh
233index e6a1cef348ff2611fcfa4c207b638d6521358357..a0ea841cdc46983f60bfa2d25c03562cf34f698c 100644
234--- a/plugins/genpass/genpass.plugin.zsh
235+++ b/plugins/genpass/genpass.plugin.zsh
236@@ -1,106 +1 @@
237-autoload -U regexp-replace
238-zmodload zsh/mathfunc
239-
240-genpass-apple() {
241-  # Generates a 128-bit password of 6 pseudowords of 6 characters each
242-  # EG, xudmec-4ambyj-tavric-mumpub-mydVop-bypjyp
243-  # Can take a numerical argument for generating extra passwords
244-  local -i i j num
245-
246-  [[ $1 =~ '^[0-9]+$' ]] && num=$1 || num=1
247-
248-  local consonants="$(LC_ALL=C tr -cd b-df-hj-np-tv-xz < /dev/urandom \
249-    | head -c $((24*$num)))"
250-  local vowels="$(LC_ALL=C tr -cd aeiouy < /dev/urandom | head -c $((12*$num)))"
251-  local digits="$(LC_ALL=C tr -cd 0-9 < /dev/urandom | head -c $num)"
252-
253-  # The digit is placed on a pseudoword edge using $base36. IE, Dvccvc or cvccvD
254-  local position="$(LC_ALL=C tr -cd 056bchinotuz < /dev/urandom | head -c $num)"
255-  local -A base36=(0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 a 10 b 11 c 12 d 13 \
256-    e 14 f 15 g 16 h 17 i 18 j 19 k 20 l 21 m 22 n 23 o 24 p 25 q 26 r 27 s 28 \
257-    t 29 u 30 v 31 w 32 x 33 y 34 z 35)
258-
259-  for i in {1..$num}; do
260-    local pseudo=""
261-
262-    for j in {1..12}; do
263-      # Uniformly iterate through $consonants and $vowels for each $i and $j
264-      # Creates cvccvccvccvccvccvccvccvccvccvccvccvc for each $num
265-      pseudo="${pseudo}${consonants:$((24*$i+2*${j}-26)):1}"
266-      pseudo="${pseudo}${vowels:$((12*$i+${j}-13)):1}"
267-      pseudo="${pseudo}${consonants:$((24*$i+2*${j}-25)):1}"
268-    done
269-
270-    local -i digit_pos=${base36[${position[$i]}]}
271-    local -i char_pos=$digit_pos
272-
273-    # The digit and uppercase character must be in different locations
274-    while [[ $digit_pos == $char_pos ]]; do
275-      char_pos=$base36[$(LC_ALL=C tr -cd 0-9a-z < /dev/urandom | head -c 1)]
276-    done
277-
278-    # Places the digit on a pseudoword edge
279-    regexp-replace pseudo "^(.{$digit_pos}).(.*)$" \
280-      '${match[1]}${digits[$i]}${match[2]}'
281-
282-    # Uppercase a random character (that is not a digit)
283-    regexp-replace pseudo "^(.{$char_pos})(.)(.*)$" \
284-      '${match[1]}${(U)match[2]}${match[3]}'
285-
286-    # Hyphenate each 6-character pseudoword
287-    regexp-replace pseudo '^(.{6})(.{6})(.{6})(.{6})(.{6})(.{6})$' \
288-      '${match[1]}-${match[2]}-${match[3]}-${match[4]}-${match[5]}-${match[6]}'
289-
290-    printf "${pseudo}\n"
291-  done
292-}
293-
294-genpass-monkey() {
295-  # Generates a 128-bit base32 password as if monkeys banged the keyboard
296-  # EG, nz5ej2kypkvcw0rn5cvhs6qxtm
297-  # Can take a numerical argument for generating extra passwords
298-  local -i i num
299-
300-  [[ $1 =~ '^[0-9]+$' ]] && num=$1 || num=1
301-
302-  local pass=$(LC_ALL=C tr -cd '0-9a-hjkmnp-tv-z' < /dev/urandom \
303-    | head -c $((26*$num)))
304-
305-  for i in {1..$num}; do
306-    printf "${pass:$((26*($i-1))):26}\n"
307-  done
308-}
309-
310-genpass-xkcd() {
311-  # Generates a 128-bit XKCD-style passphrase
312-  # e.g, 9-mien-flood-Patti-buxom-dozes-ickier-pay-ailed-Foster
313-  # Can take a numerical argument for generating extra passwords
314-
315-  if (( ! $+commands[shuf] )); then
316-    echo >&2 "$0: \`shuf\` command not found. Install coreutils (\`brew install coreutils\` on macOS)."
317-    return 1
318-  fi
319-
320-  if [[ ! -e /usr/share/dict/words ]]; then
321-    echo >&2 "$0: no wordlist found in \`/usr/share/dict/words\`. Install one first."
322-    return 1
323-  fi
324-
325-  local -i i num
326-
327-  [[ $1 =~ '^[0-9]+$' ]] && num=$1 || num=1
328-
329-  # Get all alphabetic words of at most 6 characters in length
330-  local dict=$(LC_ALL=C grep -E '^[a-zA-Z]{1,6}$' /usr/share/dict/words)
331-
332-  # Calculate the base-2 entropy of each word in $dict
333-  # Entropy is e = L * log2(C), where L is the length of the password (here,
334-  # in words) and C the size of the character set (here, words in $dict).
335-  # Solve for e = 128 bits of entropy. Recall: log2(n) = log(n)/log(2).