perché i primi caratteri di una chiave privata DSA sono simili?

1

Ho notato che la maggior parte delle chiavi private DSA inizia spesso con gli stessi pochi caratteri, MIIBvAIBAAKBgQD .

Ad esempio, genera una chiave privata su Ubuntu eseguendo:

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

Questo risulta in un file di chiave privata che inizia con qualcosa di simile:

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

I primi 16 personaggi sono sospettosamente simili.
Prevedo che ssh-keygen stia usando un nonce casuale prima di iniziare la cifratura. Supponendo che ssh-keygen utilizzi un nonce casuale, perché i primi caratteri dei file di chiavi private DSA sono simili?

Usando uno script, ho scoperto che l'unicità ("casualità", buona entropia, ecc.) inizia al diciassettesimo personaggio.

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
...

Ho usato il seguente codice bash per determinare questo

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}" 
    
posta JamesThomasMoon1979 30.01.2014 - 08:04
fonte

2 risposte

5

Il file di chiavi private DSA ha una struttura , non è semplicemente un numero casuale (o due). All'interno dei dati codificati PEM (base64 + delimitatori) c'è una struttura binaria ASN.1 codificata DER. ASN.1 è un modo indipendente dal sistema di codificare i dati (pensateci come un "XML binario"). Rigorosamente, solo i primi due byte di una chiave DSA codificata in questo modo sono corretti, ma per una dimensione della chiave data si può dire di più. Nota che non ci sono "numeri magici" nella struttura dati sottostante.

Una coppia di chiavi DSA ha 5 componenti distinti: P, Q, G, parte chiave pubblica, parte chiave privata. Scavando nell'origine di OpenSSL (utilizzato da OpenSSH per questo) 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)

Che corrisponde a quello che vedrai con openssl asn1parse -in id_dsa (sebbene si noti che se si usa openssl dsa -in id_dsa -noout -text il campo della versione viene omesso e l'ordine è cambiato in privato, pub, P, Q , G).

Dai un'occhiata all'output ASN.1 analizzato:

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[...]

Nel modulo DER di ASN.1 ogni elemento di dati è un (type tag,length,data) triplo. Nell'output asn1parse sopra le colonne principali indicano offset, d= depth, hl= intestazione length (dimensione del tag type e lunghezza dei campi) e l= data length. (Nelle forme non DER può essere un po 'più complicato, ma non dobbiamo preoccuparci di questo qui.)

Se scartiamo la base64 possiamo vedere il formato binario DER:

$ 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.|
                                            ^^ ^^ ^^ ^^ ^^ 

È possibile che i byte iniziali siano ragionevolmente statici ("contenitore" SEQUENCE + versione = 0), sebbene la dimensione della sequenza dipenda dalla dimensione della chiave DSA. Il DSA "P" ( ^^ ) è il long prime (1024, 2048 o 3072 bit) è il prossimo, quindi per una data dimensione della chiave fissa la sua intestazione di 4 byte sarà anche ragionevolmente statica. Ciò fornisce un totale di 11 byte ragionevolmente statici per una dimensione definita della chiave (tecnicamente dimensioni , ad esempio 2048,256 per p, q). Una complicazione in questo caso è rappresentata da piccole variazioni nella dimensione degli interi codificati: verrà aggiunto un padding di 0 byte aggiuntivo per garantire gli interi positivi (il bit iniziale deve essere 0).

Hai analizzato i dati base64 codificati , quegli 11 byte ragionevolmente statici diventano codificati nei 15 caratteri principali dell'output di base64 ( 11 * 8/6 = 14.66) con due bit della P casuale trovati anche nel carattere 15 (data la condizione di riempimento, quei due bit saranno comunque circa il 75% del tempo). Credo che questo sia d'accordo con i tuoi dati.

Notare l'aumento minore nella variazione attorno al 5 ° / 6 ° carattere codificato in base64: questo corrisponde al basso ottetto della dimensione totale della struttura (4 byte DER), la dimensione ha variazioni minori per le dimensioni della chiave fisse a causa del 50% possibilità di portare 0-padding su ciascuno dei 5 numeri interi DSA codificati.

Un formato alternativo per le chiavi è PKCS # 8 , questo omette la parte della chiave pubblica, ma aggiunge dsaEncryption OID quindi almeno la struttura è un po 'meno enigmatica:

$ 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[...]
    
risposta data 30.01.2014 - 14:45
fonte
1

La tua chiave DSA è memorizzata come DER - struttura dati codificata che a sua volta è base64 -encoded. I primi 16 byte sono fondamentalmente la codifica di una descrizione di cosa c'è nel file; il resto del file è la chiave stessa.

    
risposta data 30.01.2014 - 10:44
fonte

Leggi altre domande sui tag