From: Anonymous <nobody@replay.com>
Date: Mon, 12 Oct 1998 12:59:28 +0800
To: cypherpunks@cyberpass.net
Subject: Re: Hidden WebTV signatures
Message-ID: <199810120441.GAA12553@replay.com>
MIME-Version: 1.0
Content-Type: text/plain



Phelix writes:
> Here ya go.  313 webtv sigs

Thanks.  Each of these decodes to a pair of integer values, as described
by Peter Gutmann.  Here is a histogram of the high order hex digit:

# Values    Digit
   54         0
   35         1
   56         2
   49         3
   43         4
   50         5
   47         6
   57         7
   45         8
   43         9
   49         a
   54         b
   44         c
    0         d
    0         e
    0         f
   
It cuts off at "c" and is pretty uniform up to then so it does indicate
that the values are uniformly distributed modulo a common 64 bit value.
The last few values, numerically, are:

cac1cb18c3d20ca400db3a1458128bea3f696edf
cae7ea1cff68371b6541a829d6a5327bf77b8ba4
cb6449fb156e3b7a0f9577a9163dab099540360d
cb9e0b23cdfebac34c38a933fcf303a5ecac64eb
cba8abfa8cdcfa7a7f91e3563b3d7fa24511ab6c
cc1a7a3ac5107a17fd7d0957223a189ac9b692b7
cc4d60e041b32e85d8148a2a340f3ae6c2a6f02c
cc9d2ed06373569225844c8b0bd2e7c55537ab71
cd53fb5bc7699730b39d42b99782fecfdfe52a5a

This suggests that the "q" value is probably a 160 bit value starting
with 0xcd.

We can't tell whether there is a common key or whether every unit has a
different key.  In either case it is likely that p, q and g will be shared
among all units.  The individual part is the secret x value and the
public y = g^x mod p.  Probably there is no way to find these from
the signatures.

For reference, here is the 20 minute program which produced this output:


/* Decode webtv signatures */
#include <stdio.h>
#include <ctype.h>

#define TAG_INTEGER     2
#define TAG_SEQUENCE    16


static
unsigned char asctobin[] =
{
    0200, 0200, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0200, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0200, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0200, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0200, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0200, 0200, 0076, 0200, 0200, 0200, 0077,
    0064, 0065, 0066, 0067, 0070, 0071, 0072, 0073,
    0074, 0075, 0200, 0200, 0200, 0200, 0200, 0200,
    0200, 0000, 0001, 0002, 0003, 0004, 0005, 0006,
    0007, 0010, 0011, 0012, 0013, 0014, 0015, 0016,
    0017, 0020, 0021, 0022, 0023, 0024, 0025, 0026,
    0027, 0030, 0031, 0200, 0200, 0200, 0200, 0200,
    0200, 0032, 0033, 0034, 0035, 0036, 0037, 0040,
    0041, 0042, 0043, 0044, 0045, 0046, 0047, 0050,
    0051, 0052, 0053, 0054, 0055, 0056, 0057, 0060,
    0061, 0062, 0063, 0200, 0200, 0200, 0200, 0200
};



/* Do base64 decoding */
/* Return number of chars output */
static int
decode64 (const unsigned char *inbuf, unsigned char *outbuf)
{
    int w = 0;
    int cnt = 0;
    int ci, co;
    unsigned char *op = outbuf;

    for ( ; ; ) {
        ci = (*inbuf++);
        if (ci & 0x80)
            break;
        co = asctobin[ci];
        if (co & 0x80)
            break;
        w = (w << 6) | co;
        if (++cnt == 4) {
            *op++ = (w >> 16) & 0xff;
            *op++ = (w >>  8) & 0xff;
            *op++ = (w >>  0) & 0xff;
            cnt = 0;
            w = 0;
        }
    }
    if (cnt == 1) {
        fprintf (stderr, "Bad base64 input\n");
        exit (1);
    } else if (cnt == 2) {
        *op++ = (w >>  4) & 0xff;
    } else if (cnt == 3) {
        *op++ = (w >> 10) & 0xff;
        *op++ = (w >>  2) & 0xff;
    }
    return op - outbuf;
}

/* Print out a nominally 20 byte value */
static void
hexdump20 (unsigned char *data, size_t datalen)
{
    if (datalen > 20) {
        int cnt = datalen - 20;
        while (cnt--) {
            if (*data++ != 0) {
                fprintf (stderr, "Error, more than 20 byte output\n");
                return;
            }
        }
        datalen = 20;
    }
    if (datalen < 20) {
        int cnt = 20 - datalen;
        while (cnt--)
            printf ("00");
    }
    while (datalen--) {
        printf ("%02x", *data++);
    }
    putchar ('\n');
}


/* Read start of an X.509 object */
static int
decodetag(unsigned char **buf, int *length)
{
    unsigned char tag = *(*buf)++ & 0x1f;
    int len = *(*buf)++;
    if (len & 0x80) {
        int lenlen = len & 0x7f;
        len = 0;
        while (lenlen--) {
            len <<= 8;
            len |= *(*buf)++;
        }
    }
    *length = len;
    return tag;
}


main ()
{
    unsigned char buf[1024];
    unsigned char *bp;
    unsigned char outbuf[1024];
    unsigned char *op;
    int outlen;
    int len;
    int tag;

    while (fgets(buf, sizeof(buf), stdin)) {
        bp = buf;
        while (isspace(*bp))
            ++bp;

        outlen = decode64 (bp, outbuf);

        if (outbuf[0] != 0x11) {
            fprintf (stderr,
                "First char of output not 0x11, unexpected!\n");
        }
        op = outbuf + 1;
        tag = decodetag (&op, &len);
        if (tag != TAG_SEQUENCE) {
            fprintf (stderr, "Output is not a SEQUENCE, skipping\n");
            continue;
        }
        tag = decodetag (&op, &len);
        if (tag != TAG_INTEGER) {
            fprintf (stderr, "First value is not an INTEGER, skipping\n");
            continue;
        }
        hexdump20 (op, len);
        op += len;
        tag = decodetag (&op, &len);
        if (tag != TAG_INTEGER) {
            fprintf (stderr, "Second value is not an INTEGER, skipping\n");
            continue;
        }
        hexdump20 (op, len);
    }
    exit (0);
}