Leveraging a symlink attack to steal DSA keysIMPORTANTIntroductionAliceEveConclusionAssorted notesAcknowledgementsFAQContact

Author:

Version:

20110530-4

in /etc/pam.d.

If you are on RHEL/CentOS: don't worry -- they fixed this bug last year.

formatted cryptography keys can end in a line that ends in ==, and pam_env tolerates this format. This means we can steal that line to see if it provides us with enough information to reconstruct a full private key.

I've done some research, and it turns out that over a sample of 1000 freshly generated DSA keys, around 20% of those (when encoded in DER/PEM form, as is common) end in ==. Some, we still can't read because their last line

starts with a number; the pam_env issue requires an alphanumeric line (starting with a letter), ending in ==. In the end, about 10% of private DSA keys expose their last line to us this way.

Of those keys, 98% leak 16*8=128 bits of the private part (x) of a DSA key. The rest (within my sample of 1000) leak 13*8=104 bits. The private part appears to be around 160 bits long on average.

This report documents a staged attack. It should explain most of the issue.

I make the following assumptions.

Eve can obtain the public key

the private key is in the 10% that is vulnerable

there is no passphrase on the private key (perhaps she's using them for rsync backups?)

Alice has her DSA keypair she uses to log in to various places. She's silly enough to not use a passphrase:

Not everybody does this next bit but it makes this demonstration a bit simpler.

Some time later, Eve comes in with her user account on the same machine.

Eve employs the pam_env symlink trick:

Logs out, logs back in (newlines inserted for readability):

Depending on some factors, .ssh permissions may not allow reading the pub file; we're assuming that in general the public key is available.

The bSsUBZkPeLhzmQZtCB97Xg== bit is most of DSA's private part, x. The public key provides all other variables. Let's get to work (newlines inserted in numbers for readability, sshpubkey

truncated with ... for brevity):

p, q, g and y are gathered from the pubkey. Each variable is stored as a (len, i) tuple; len indicates

the number of bits actually stored -- this is mostly so we know how many leading zeroes we may have.

xtail is the tail part of x that we gathered from the last line of Alice's private key file.

Eve copies this data file to her render farm and sets it to work:

6 hours pass.

Yay! Let's use this information for good. Or for bad ;)

Reconstruct Alice's private key:

Try logging in with it:

Looks like Eve did it and Alice is in trouble.

A symlink attack in pam_env allows us to steal data if it's formatted in specific ways. About 10% of private DSA keys expose their last base64-encoded line this way. If we can obtain the public key that goes with such a key, we have about 32 bits of private

key data to guess. This turns out to be entirely feasible on modern hardware. In this specific demonstration, 24 cores of a recent CPU model needed 6 hours to reconstruct the complete private key.

network.

<dl></dl>

<dt>Q: Is this a weakness in DSA? Should I switch to RSA?</dt>

<dd>A: I cannot provide advice on the relative merits of RSA versus DSA, but this article should not be considered a reason to drop DSA.</dd>

<dt>Q: What about RSA?</dt>

<dd>A: RSA private keys contain a bunch of 'secret' variables, where DSA only has one. Also, RSA variables are longer so this attack only lifts about 1/3rd of one of those variables. My impression is that this does not reduce attack</dd>

time to be feasible. I did not verify this.

-- Peter van Dijk