Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I noticed most DSA private keys often start with the same few characters, MIIBvAIBAAKBgQD .

For example, generate a private key on Ubuntu, by running:

ssh-keygen -t dsa -N '' -f /tmp/id_dsa

This results in a private key file that begins with something like:

-----BEGIN DSA PRIVATE KEY-----
MIIBvAIBAAKBgQD...

The first 16 characters are suspiciously similar.
I expect ssh-keygen is using a random nonce before beginning encipherment. Assuming ssh-keygen is using a random nonce, why are the first few characters of the DSA Private Key files similar?


Using a script, I found that uniqueness ("randomness", good entropy, etc.) begins at the 17th character.

leading char count  1 - unique combinations   1 among 100 generated keys
leading char count  2 - unique combinations   1 among 100 generated keys
leading char count  3 - unique combinations   1 among 100 generated keys
leading char count  4 - unique combinations   1 among 100 generated keys
leading char count  5 - unique combinations   2 among 100 generated keys
leading char count  6 - unique combinations   4 among 100 generated keys
leading char count  7 - unique combinations   6 among 100 generated keys
leading char count  8 - unique combinations   5 among 100 generated keys
leading char count  9 - unique combinations   4 among 100 generated keys
leading char count 10 - unique combinations   4 among 100 generated keys
leading char count 11 - unique combinations   4 among 100 generated keys
leading char count 12 - unique combinations   4 among 100 generated keys
leading char count 13 - unique combinations   4 among 100 generated keys
leading char count 14 - unique combinations   4 among 100 generated keys
leading char count 15 - unique combinations   7 among 100 generated keys
leading char count 16 - unique combinations  87 among 100 generated keys
leading char count 17 - unique combinations 100 among 100 generated keys
leading char count 18 - unique combinations 100 among 100 generated keys
leading char count 19 - unique combinations 100 among 100 generated keys
leading char count 20 - unique combinations 100 among 100 generated keys
leading char count 21 - unique combinations 100 among 100 generated keys
...

I used the following bash code to determine this

keyf=/tmp/id_dsa-${RANDOM}
for upto in {1..35} ; do
    keys="${keyf}-${upto}"
    rm -f "${keys}" &>/dev/null
    for i in {0..99} ; do
        rm "${keyf}" &>/dev/null
        ssh-keygen -t dsa -N '' -f "${keyf}" &>/dev/null
        sed '2q;d' "${keyf}" | cut -b 1-"${upto}" >> "${keys}"
    done
    keys_count_all=$(cat "${keys}" | wc -l)
    keys_count_uniq=$(sort -u "${keys}" | wc -l)
    printf "leading char count %2d - unique combinations %3d among %3d generated keys\n" ${upto} ${keys_count_uniq} ${keys_count_all}
done
rm "${keyf}" 
share|improve this question

2 Answers 2

up vote 5 down vote accepted

The DSA private key file has a structure to it, it's not simply a random number (or two). Within the PEM encoded data (base64 + delimiters) is a DER encoded ASN.1 binary structure. ASN.1 is a system independent way to encode data (think of it like a "binary XML"). Strictly, only the first two bytes of a DSA key encoded this way are fixed, but for a given key size more can be said. Note there are no "magic numbers" in the underlying data structure.

A DSA key pair has 5 distinct components: P, Q, G, public key part, private key part. Digging into the source of OpenSSL (used by OpenSSH for this) crypto/dsa/dsa_asn1.c:

ASN1_SEQUENCE_cb(DSAPrivateKey, dsa_cb) = {
    ASN1_SIMPLE(DSA, version, LONG),
    ASN1_SIMPLE(DSA, p, BIGNUM),
    ASN1_SIMPLE(DSA, q, BIGNUM),
    ASN1_SIMPLE(DSA, g, BIGNUM),
    ASN1_SIMPLE(DSA, pub_key, BIGNUM),
    ASN1_SIMPLE(DSA, priv_key, BIGNUM)
} ASN1_SEQUENCE_END_cb(DSA, DSAPrivateKey)

Which corresponds with what you'll see with openssl asn1parse -in id_dsa (though note if you use openssl dsa -in id_dsa -noout -text the version field is omitted, and the order is changed to priv, pub, P, Q, G).

Taking a look at the parsed ASN.1 output:

0:d=0  hl=4 l= 830 cons: SEQUENCE          
4:d=1  hl=2 l=   1 prim: INTEGER           :00
7:d=1  hl=4 l= 257 prim: INTEGER           :DFA34F1D[...]

In the DER form of ASN.1 each item of data is a (type tag,length,data) triple. In the above asn1parse output the leading columns indicate the offset, d= depth, hl=header length (size of type tag and length fields), and l= data length. (In non-DER forms it can be a little more complicated, but we don't need to worry about that here.)

If we unwrap the base64 we can see the DER binary format:

$ openssl dsa -in id_dsa -outform DER | hexdump -C | head -1

00000000  30 82 03 3e 02 01 00 02  82 01 01 00 df a3 4f 1d  |0..>........ߣO.|
                                            ^^ ^^ ^^ ^^ ^^ 

You can expect the leading bytes to be reasonably static (SEQUENCE "container" + version=0), though the sequence size will be dependent on the DSA key size. The DSA "P" (^^) is the long prime (1024, 2048 or 3072 bits) is next, so for a given fixed key size its header of 4 bytes will also be reasonably static. This gives a total of 11 reasonably static bytes for a defined key size (technically sizes, e.g. 2048,256 for p,q). A complication here is minor variations in the size of encoded integers: an extra 0-byte padding will be added to ensure positive integers (leading bit must be 0).

You analysed the base64 encoded data, those 11 reasonably static bytes become encoded in the leading 15 characters of base64 output (11*8/6 =14.66) with two bits of the random P also found in the 15th character (given the padding condition, those two bits will be zero about 75% of the time anyway). I believe this agrees with your data.

Note the minor increase in variation around the 5th/6th base64 encoded character: this corresponds with the low-octet of the total structure size (4th DER byte), the size has minor variations for fixed key sizes due to the 50% chance of leading 0-padding on each of the 5 encoded DSA integers.

An alternate format for keys is PKCS#8, this omits the public key part, but it adds the dsaEncryption OID so at least the structure is a little less enigmatic:

$ openssl pkcs8 -in id_dsa -topk8 -nocrypt | openssl asn1parse
    0:d=0  hl=4 l= 589 cons: SEQUENCE          
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=4 l= 558 cons: SEQUENCE          
   11:d=2  hl=2 l=   7 prim: OBJECT            :dsaEncryption
   20:d=2  hl=4 l= 545 cons: SEQUENCE          
   24:d=3  hl=4 l= 257 prim: INTEGER           :DFA34F[...]
share|improve this answer

Your DSA key is stored as a DER-encoded data structure which is in turn base64-encoded. The first 16 bytes are basically the encoding of a description of what's in the file; the rest of the file is the key itself.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.