by redmail.netbsd.org with SMTP; 30 Jan 2000 19:26:35 -0000
	by noc.untraceable.net (8.10.0.Beta12/8.10.0.Beta12/bonk!) id e0UJNlL20874;
	Sun, 30 Jan 2000 14:23:47 -0500 (EST)
Date: Sun, 30 Jan 2000 14:23:47 -0500
From: Andrew Brown <atatat@atatdot.net>
To: Robert Elz <kre@munnari.OZ.AU>
Cc: NetBSD Security Technical Discussion List <tech-security@netbsd.org>
Subject: Re: [harikiri@ATTRITION.ORG: S/Key & OPIE Database Vulnerability]
Message-ID: <20000130142347.A20452@noc.untraceable.net>
Reply-To: Andrew Brown <atatat@atatdot.net>
References: <m12EylK-000g6HC@most.weird.com> <10352.949256944@munnari.OZ.AU>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
In-Reply-To: <10352.949256944@munnari.OZ.AU>; from kre@munnari.OZ.AU on Mon, Jan 31, 2000 at 05:29:04AM +1100
Return-Receipt-To: receipts@daemon.org

>  | I'm also now confused as to how it's not possible for someone to
>  | determine the next appropriate challenge (and thus calculate the
>  | appropriate response) if the /etc/skeykeys file is publicly readable.
>  | Obviously if this is true there must be some cryptographically secure
>  | algorithm that can combine the seed and the secret to generate a new and
>  | hopefully unique challenge.  Unfortunately the documentation is
>  | completely silent about the algorithms involved.
>
>Is it?   Maybe I read about it elsewhere.
>
>Its a simple one time hash on the seed and the secret, performed
>N times.   Each time it is used the result replaces the known hash
>(in skeykeys) and N-1 is used next time.   This relies upon the
>uninvertability (if there is such a work) of the hash.  MD5 (or sometimes
>MD4) is used as the hash function - it is believed to be hard to invert.
>That is, it is easy to go from secret to hash(secret)^N, but very
>hard to get from hash(secret)^N to hash(secret)^(N-1).

actually, the original s/key from bellcore (from which ours is derived
(or copied?)) used md4.  ours still does.

   % cd /usr/src/lib/libskey
   % grep MD *.c
   skeysubr.c: * concatenate the seed and the password, run through MD4 and
   skeysubr.c:     MD4_CTX md;
   skeysubr.c:     /* Crunch the key through MD4 */
   skeysubr.c:     MD4Init(&md);
   skeysubr.c:     MD4Update(&md, (unsigned char *) buf, buflen);
   skeysubr.c:     MD4Final((unsigned char *) hash, &md);
   skeysubr.c:     MD4_CTX md;
   skeysubr.c:     MD4Init(&md);
   skeysubr.c:     MD4Update(&md, (unsigned char *) x, 8);
   skeysubr.c:     MD4Final((unsigned char *) hash, &md);

bsdi has added (and uses by default) md5 (so if you're trying to use
the skey calculator on bsdi, you need to specify -4).  opie, i
believe, adds md5 and possibly sha1 as algorithmic choices.

i've got backwards compatible patches to libskey that make it able to
use md5.  sha1 ought not to be that difficult to add.

>  | I worry about this
>  | because in other implementations of challenge/response systems, such as
>  | "CryptoCard(tm)", it's possible to compute the challenge response if one
>  | knows RNG seed (and the calculator PIN?).
>
>As it is here - but the seed is the secret, only you know that (in theory).
>The skeykeys file is just like the traditional unix passwd file, and only
>stores the hashed value (the N times hasshed value, then after that is
>used once, the N-1 times hashed value).

yep.  the file has your hash for the count of n and asks you for the
has of n-1.  then it computes (via one round in md4) the hash that it
currently has stored, and if they match it writes the new n-1 value
and lets you in.

>  | Thanks for verifying.  I thought it might be but I've been unable to
>  | boot a newer sparc release on my spare ss1 and have no non-i386 -current
>  | machines to test on.
>
>It was fixed before 1.4.1, maybe even before 1.4 (might have been as
>early as 1.3.2 - though I remember being annoyed it wasn't fixed in 1.3.1)

i remember first seeing this problem on the alpha in late '95 or early
'96 (i was trying to use the skey calculator to log into a i386
machine and failing) and sending in patches to fix the problem.

>  | 'md5 -x' (a test I'd forgotten completely about) seems to match on all
>  | the different machines I've got....
>
>The problem was a mismatch in the theory as to who was supposed to byte
>swap the md5 output - it some early version, the md5 results it that were
>used produced an endian dependent result, so the skey mainline compensated.
>Someone fixed md5 (or switched to a new version) but didn't undo the
>skey hack around the bug.

i believe the md* routines as defined in rfc 1319, 1320, and 1321 all
assume little endian-ness.  here's a nice piece from 1320 on md4.

   2. Terminology and Notation

      In this document a "word" is a 32-bit quantity and a "byte" is an
      eight-bit quantity. A sequence of bits can be interpreted in a
      natural manner as a sequence of bytes, where each consecutive group
      of eight bits is interpreted as a byte with the high-order (most
      significant) bit of each byte listed first. Similarly, a sequence of
      bytes can be interpreted as a sequence of 32-bit words, where each
      consecutive group of four bytes is interpreted as a word with the
      low-order (least significant) byte given first.
 
-- 
|-----< "CODE WARRIOR" >-----|
codewarrior@daemon.org             * "ah!  i see you have the internet
twofsonet@graffiti.com (Andrew Brown)                that goes *ping*!"
andrew@crossbar.com       * "information is power -- share the wealth."