Package: apg Version: 2.2.3.dfsg.1-1 Severity: grave Tags: security Justification: user security hole
On amd64, here's the number of identical passwords generated when
generating 1000 passwords using apg:
$ (while true; do apg -a 1 -M l -n 1000 -x 8 -m 8 |sort |uniq -D |uniq |wc -l;
done) |uniq -c
8 0
1 12
4 0
1 29
2 0
1 336
4 0
1 108
1 0
1 34
1 0
1 43
1 0
1 72
2 0
1 48
1 183
(read: on the first 8 runs it generated 0 collisions, on next one 12
collisions, on the next 4 again 0 collisions, after that 29
collisions, and so on).
Given these options apg claims to generate 1000 (-n 1000) entirely
random (-a 1) passwords consisting of 8 (-x 8 -m 8) lowercase (-m l)
letters. There should be 26^8 = approx. 2.1*10^11 different such
passwords. According to the birthday paradox[1], the expected number
of collisions given 1000 entirely random passwords out of 26^8
possible should be
n-d+d*((d-1)/d)^n, n=1000, d=26^8 => 2.4*10^-6.
The high number of collisions on some runs seems to imply a bug in the
implementation.
This bug does not seem to exist on i386 and appears to only affect
totally random (i.e. not pronounceable) password generation (-a 0).
Sami
[1] http://en.wikipedia.org/wiki/Birthday_paradox#Collision_counting
-- System Information:
Debian Release: 4.0
APT prefers unstable
APT policy: (500, 'unstable')
Architecture: amd64 (x86_64)
Shell: /bin/sh linked to /bin/bash
Kernel: Linux 2.6.18-4-amd64
Locale: LANG=C, [EMAIL PROTECTED] (charmap=ISO-8859-15)
Versions of packages apg depends on:
ii libc6 2.3.6.ds1-13 GNU C Library: Shared libraries
apg recommends no packages.
-- no debconf information
signature.asc
Description: Digital signature
