dacsgrid - administer grid-based one-time passwords
[ -dec token
] [-enc challenge
] [-grid str
[ -inkeys item_type
[ -nrows num
]] [ -refresh
[-validate challenge response
[ -vfs vfs_uri
This program is part of the DACS
utility provides software-based one-time passwords for
authentication using a challenge-response architecture. It
administers accounts that are used by the local_grid_authenticate
authentication module. These accounts are completely separate from the
accounts used by local_passwd_authenticate
 or any other DACS
generates a rectangular grid of cells. Each cell consists of a
letter, followed by a digit, followed by a letter, yielding 6,760 (26*10*26)
possible three-character-long strings. The contents of each cell are generated
from cryptographically-strong pseudo-random bytes. The maximum grid size is 99
rows by 26 columns, and the minimum grid size is 3 by 3. The columns are
labelled A through Z and the rows are labelled 1 through 99. For recommended
grid sizes, it is highly likely that each grid that is generated is unique and
therefore that each user will be assigned a different grid.
Here is a 10x10 grid (the default size):
A B C D E F G H I J
1 x7m p7m k4c q9s q2k d9l s5m r8c y3v g2m
2 o0c t6h q7k l3w p8a q3e b9c l0w z8y c8v
3 v8n n1w r6i i0g e9y q1n p0g g9v x4y c5u
4 z8a o9d l1e e8n u8z h3y p2s b9z c6w d5f
5 x8y o2a y4g d9i s4p c9n c1e m5z o6j m0f
6 p2s x4c a2x p4f w7y b8k e6c q9g q5v s4z
7 b8k r4s r2p z5x v3e s0h h5l z6y e9o g6m
8 r5x m4r a1w f8c f5g l2z q7j r4m w0c x9a
9 p7s r3g i7c p8a t5x c4h h0k k9d i7k r9n
10 w4l v0a p9g i0l v2n b8h v9j s0y r3k v0m
Created: Mon Aug 14 10:25:03 2006 PDT
A cell is identified by its column label (a letter) followed by its row label (a
number); e.g., in the example above, cell F6 has the value b8k.
Each grid is assigned a random (and presumably unique) identification string
(labelled "Serial" in the example above); this string is stored on
the server with other grid account data. It can be displayed by a jurisdiction
at login time as a way of authenticating itself to a user, provided it is kept
confidential (one approach might be for each of the parties to supply a
different half of the identification string to the other).
At authentication time, the user is presented with a randomly-generated
challenge that is appropriate for the user's grid. The challenge is displayed
to the user; e.g., "A3, C9, B1, F9". The grid's serial number, or a
portion of it, might also be displayed. The user must consult his grid to
locate each of the cells for the given challenge and enter their contents as
the password. Letters are case insensitive, blanks, tabs, and commas are
ignored. For the grid and challenge above, the user would enter the following
characters as the password:
Note that a challenge may ask for the same cell more than once.
A challenge is valid for a configurable length of time after which it can no
longer be used for authentication; see AUTH_GRID_CHALLENGE_SECS
To judge how long a challenge should be, assume that user-selected passwords are
chosen randomly and uniformly from approximately 100 characters available on a
keyboard. This is a very generous assumption that is seldom realized in
practice. A grid challenge of four cells is much stronger than a user-selected
password of six characters (69604 vs. 1006) and a grid challenge of five cells
is much stronger than a user-selected password of nine characters (69605 vs.
1009). When compared to typical user passwords, however, a grid challenge of
three cells is probably about as strong as a user-chosen password of seven or
Grids are accessed through DACS's
virtual filestore using item type
auth_grid. It is assumed that file permissions on the database of grids are
such that all access is limited to the administrator and
After a run-time configurable period, a grid expires and will not be accepted
for authentication purposes by local_grid_authenticate
) or dacsgrid
The validity period of a grid might be based on several factors, such as how
often it is used at a jurisdiction, the number of cells in the grid, the
degree of security required, or how difficult or expensive it is to distribute
a grid to its user.
At the time a grid is generated, dacsgrid
can associate a randomly chosen
PIN with it. A PIN, which acts as a secondary password, consists of a sequence
of letter-digit-letter cells. The default PIN length of two cells (6
characters) can be overridden on the command line. If a user has been provided
with a PIN, it should be entered at the start of the user's response to the
challenge, immediately before the contents of the first cell of the challenge
When used properly, this authentication method can be comparatively secure. The
main challenge is that it is essential that grids and PINs are distributed to
users via a sufficiently secure method; e.g., by printing them and mailing a
hardcopy directly to the user, or by using existing secure channels. Each user
must understand that a grid is essentially a list of passwords and,
accordingly, must be kept secret during its validity period. When PINs are
used, they must be distributed using a secure channel different from the one
used to distribute grids. How this distribution is done is left to the
Information is encrypted before being written to the grid account file. By
default, the virtual filestore item type auth_grid_keys identifies the
encryption keys to use; the -inkeys
alternatives (see dacskey(1)
). File permissions must be set so that
the encryption keys are readable only by dacsgrid
. If the encryption
keys are lost, the account entries are practically unrecoverable.
Only the DACS
administrator should be able to successfully run this
program from the command line. Because DACS
keys and configuration
files, including the file used to store accounts, must be restricted to the
administrator, this will normally be the case, but a careful administrator
will set file permissions to deny access to all other users.
This authentication method has the following advantages:
•Each time a user authenticates, a
different password will be requested (with high probability)
•The password that is required is not
known prior to authentication, so a user cannot tell someone else what his
password is other than by sharing the entire grid (and the PIN, if any)
•Because the password is unlikely to be
an easily-guessed word or phrase, it should be stronger than a user-selected
•Should a key sniffer be installed on
the user's computer, a sniffed password does not do an attacker any good,
since it is highly unlikely to be reused. If the corresponding challenge can
also be obtained by an attacker, such as through a phishing attack, a portion
of the grid will be revealed
•The length of the challenge (which
determines the length of the password) is configurable by the administrator
and can be changed at will
•A user's grid can easily be changed by
an administrator as often as practical
•The method is cheaper than
hardware-based one-time passwords, provided distribution costs are low
This authentication method has the following potential disadvantages:
•The authentication method is
inherently interactive in that the password is not known a priori,
although this does not guarantee that the user is physically present
•Secure channels are needed to
distribute grids and PINs
•An authentication grid can be easily
copied and so it is best used in conjunction with PINs or at least one other
authentication method; the challenge of keeping grids secret in all situations
is the main reason why the method is not as strong as hardware token-based
methods, which are more difficult to copy and can be protected by a PIN. The
method is best employed in situations where a grid is not likely to be stolen,
easily copied, or even recognized, such as for remote access.
This authentication method falls somewhere between the "something you
know" form and the "something you have" form. One might be able
to memorize a smaller grid, putting it into the former category, but few are
capable of memorizing a large grid, which makes it necessary to have a copy in
one's possession. Using PINs provides something closer to two-factor
authentication and strengthens the method since a captured grid is not
It is possible for different users to be assigned grids of different sizes. To
prevent generation of a challenge that is impossible to satisfy, when the
challenge is requested either the corresponding grid must be of the default
size, the dimensions of the grid must be specified, or the username must be
In addition to the standard dacsoptions
, the following command
line flags are recognized:
Emit a random challenge. If username
was specified, a size-appropriate challenge will be produced; otherwise, if
grid dimensions have been specified, a suitable challenge will be produced;
otherwise, the default grid dimensions will be used when producing a
Set the challenge length to num cells.
The minimum length is 3 cells and the default length is 4 cells.
Copy the input grids to the grids specified by
vfs_uri, deleting any existing contents.
Decrypt a challenge token produced by the
-enc option and print it.
Delete the account for username.
Disable logins for username. Implies
Enable logins for username. Implies
Encrypt a challenge (typically, produced by
the -challenge option) and print it. The item type federation_keys is
used for this purpose, which means that any jurisdiction in the federation can
decrypt the challenge.
List only expired grids, relative to the grid
lifetime in effect. Implies -list.
Print a grid in a concise textual
representation that consists of three comma-separated fields: the serial
number, enabled/disabled flag (non-zero means enabled), the grid (as an
ordered sequence of space-separated rows), a PIN (or zero if there is no PIN),
and the creation date (as the number of seconds since the epoch).
Retrieve the grid for username and make
it the "current" grid for display purposes.
Make str, a grid in the flattened
representation, the "current" grid for display purposes or the
Display a help message and exit.
Emit a grid as a fragment of an HTML
Emit a grid as a fragment of an HTML document
with some CSS.
For decrypting account information, use the
store identified by item_type.
Consider the lifetime of grids to be
ndays days. Grids do not have a fixed lifetime; only their date of
creation is recorded. The default lifetime is 7 days.
List username, if given, otherwise all
Produce more detailed listing output. Implies
Set the number of grid columns to num,
which is between 3 and 26. This is used when generating grids and
Set the number of grid rows to num,
which is between 3 and 99. This is used when generating grids and
For encrypting account information, use the
store identified by item_type.
If no other operation is specified, print the
PIN, if any, for username. With the -set flag, generate a new
PIN for username. If a non-negative integer is appended to the flag
(e.g., -pin0, -pin4), the PIN length (in cell units) is set to
that number with respect to PIN generation. The default PIN length is 2 cells.
Setting the PIN length to zero turns off PIN generation.
If a username is given, generate a new
grid for that user. If no username is given, generate a new grid for
each user that already has a grid. Any existing grid immediately becomes
invalid. All of these grids will have the same dimensions. If the -grid
flag is given, it is ignored. By default, any existing PIN is retained. The
old grid's enabled/disabled status is retained. If the -pin flag is
given, a new PIN will be generated; if -pin0 is given, however, new
grids will not have a PIN.
Reserved for future use.
Reserved for future use.
Print the serial number of the current
Set or replace the grid for
Display the grid dimensions in terms of the
command line flags -ncols and -nrows. Implies
Emit a grid and a challenge, prompt from a
response, and verify the response.
Emit a pretty-printed grid.
-validate challenge response
Validate response against
Instead of using the item type auth_grid to
specify which grids to act on, use vfs_uri (see the VFS
The default action is to display the current grid. Apart from error messages,
which are printed to the standard error, all output goes to the standard
Ordinarily, a dacsoption
will be specified to select the jurisdiction on
behalf of which grids are being created.
These examples assume that the jurisdiction name to use is EXAMPLE and its
domain is example.com.
To use this authentication method, a DACS
administrator would perform the
•After reviewing the way the method
operates, decide how grids will be securely distributed to users, select the
grid parameters, decide whether PINs will be used and how they will be
securely distributed, and determine a schedule for refreshing grids (and
•Decide where the grids will be stored
and add a suitable VFS directive to dacs.conf, for example:
•Generate keys, decide where they will
be stored, and add a suitable VFS directive to dacs.conf, for example (your
user ID, groupID, and path may vary):
% cd /usr/local/dacs/federations_root/example.com/EXAMPLE
% dacskey -uj EXAMPLE -q auth_grid_keys
% chgrp www auth_grid_keys
% chmod 0640 auth_grid_keys
•Configure a suitable Auth clause in
dacs.conf, for example:
•For each user that will be capable of
authenticating using this method: a) generate a grid of the necessary
dimensions, with or without a PIN (as required); b) obtain the grid in the
most suitable format and give it to its owner; and c) if there is a PIN,
obtain the PIN and give it to its owner.
•Refresh the grid (and, optionally, the
PIN) as scheduled and give the user the replacement grid.
To create and display a grid (but not create an account):
To generate a grid of default dimensions and assign it to username bobo
(replacing any existing grid for that user):
% dacsgrid -uj EXAMPLE -set bobo
To generate a 6x6 grid and assign it to username bobo (replacing any existing
% dacsgrid -uj EXAMPLE -nrows 6 -ncols 6 -set bobo
To retrieve and print a grid (as HTML) for the username bobo:
% dacsgrid -uj EXAMPLE -get -html bobo
To display the PIN for username bobo:
% dacsgrid -uj EXAMPLE -pin bobo
The exit status will be non-zero if this user does not have a grid or if the
grid does not have a PIN.
To copy the current set of grids to the file /secure/grids:
% dacsgrid -uj EXAMPLE -copy "dacs-kwv-fs:/secure/grids"
To refresh an alternate set of grids in the file /secure/grids:
% dacsgrid -uj EXAMPLE -copy "dacs-kwv-fs:/secure/grids"
% dacsgrid -uj EXAMPLE -vfs "dacs-kwv-fs:/secure/grids" -refresh
An example shell script that generates a minimal HTML login page for grid
authentication is included in the distribution. It assumes that all grids are
the default size.
If different users may have grids of different sizes, or if a jurisdiction wants
to display a user's grid's serial number as a form of jurisdictional
authentication, then the login procedure must determine the username before it
can acquire a challenge or serial number.
The program exits 0, or 1 if an error occurred.
To help thwart automated responses, should some assurance be required that a
person rather than software is answering a challenge, the challenge might be
presented as a CAPTCHA
 or something similar.
A hardware device could be used to store and access grids, which could boost the
method's security and possibly even offer advantages over the PRNG methods
used by most commercial tokens.
Another idea is to supply users with software to run on their personal
workstations that would securely store and manage grids and, given a
challenge, display the response. This may not provide the same level of
confidence as hardware token or hard-copy based methods, however, because it
is difficult to be certain that a computer, file, or program hasn't been
compromised. If sufficiently secure, a password-protected USB flash memory
device might be acceptable for transporting and storing grids.
The login interface should consider providing a menu or image map to enter the
PIN, rather than the keyboard, to defeat keylogging spyware.
Using this authentication method makes you feel like you are a secret agent.
Consider printing grids on an edible substrate.
There should be a clean way of flipping from one set of grids to another at a
specified date and time. This can currently be done by pre-generating a set of
grids with appropriate file names (e.g., based on the date the set becomes
effective) and configuring the VFS directive for the grids to form the file
name based on the current date.
Users cannot select their own PINs. This may be a feature.
An alternate mode of operation based on strong but repeatable pseudo random
numbers described by NIST SP 800-90
 is pending. The current
implementation does not employ a reproducible sequence of pseudo random
numbers; this has advantages and disadvantages.
The account file should probably be an XML document.
Grid-based methods are also used by ciphers; e.g., the VIC cipher
Distributed Systems Software ( www.dss.ca
Copyright2003-2014 Distributed Systems Software. See the LICENSE
that accompanies the distribution for licensing information.
- NIST SP 800-90
- VIC cipher