2

A sad story: One of our hard drives failed. While it was failing, we managed to take a quick backup. As it is our standard practice, we encrypted the backup using GPG (by however method Duplicity uses to do that, most likely plain gpg -c). Unfortunately, we stored the wrong passphrase. (Doh!)

The backup contains some data that we would very much like to recover.

We know that the passphrase was generated by pwgen -n 16 -s command on an modern Ubuntu 32-bit server machine that is a guest in a Xen host. We may have a passphrase from the same batch of pwgen passphrases (that's the "wrong passphrase"). There are several files in the backup, each encrypted with the same passphrase.

Is it feasible to attempt to brute-force the passphrase? What tools are there for that? How to calculate the cost and time of such brute-force passphrase recovery attempt? (Assume, say, that we're willing to rent Amazon HPC GPU instances as needed, and Amazon has enough of them available.)

Given that we have 62^16 possible passwords, and decrypting the smallest file (265B) with gpg takes 0.02s on my (rather old) box, the answer looks to be "not feasible"... But it never hurts to ask.

If it is preferred by the site rules, I can rephrase this question as "how hard to break is this method of backup encryption?" :-)

Alexander Gladysh
  • 123
  • 1
  • 6

1 Answers1

4

I'm afraid there's no better than brute force. The tools you used do their job properly, or close enough.

  • Duplicity invokes gpg -c, which encrypts using CAST5 with a 128-bit key by default. There is no major attack against CAST5 that I know of.
  • gpg -c uses a key strengthening function to generate a symmetric key. It involves 216 rounds of SHA-1, and I very much doubt it's broken, so the real key has as much entropy as the password you put in (about 95 bits).
  • pwgen reads a random 32-bit number from /dev/urandom (which is crypto-quality except sometimes on a freshly installed system that hasn't had time to generate entropy — and then only if you can predict the timing of all disk operations so far, which is a tall order) and takes the remainder modulo 62. That's Not Right, because it's skewed towards the digits 0123, but the skew is negligible (about 2-30 off from a uniform distribution) for only 16 runs.
    (There's actually a major problem in pwgen: it silently defaults to a non-crypto-quality random generator if /dev/urandom isn't available. But it's very unlikely that you didn't have /dev/urandom.)

Each character that pwgen displays is generated independently, so having another password from the same batch won't help.

Brute force for 295 possible keys is out of the question. That's somewhat over a billion billion billion. You'd need to compute about 2110 SHA-1 hashes.

If the physical machine where you generated the backup is still on, there's a very tiny chance that the memory that was allocated by pwgen hasn't been reused by another process. Or the memory allocated by the terminal emulator, or a program you used to copy-paste the key, or (even harder to exploit) the memory that was allocated by gpg. Your backups may be worth someone poring over a memory dump.

Check if the pwgen output might have been logged somewhere. Is it still visible in a terminal history? Do you routinely run programs under script? Is it still in a live Screen session? Is it in a clipboard history?

I think your best bet is to attempt hardware recovery on the failed disk.

Gilles 'SO- stop being evil'
  • 50,912
  • 13
  • 120
  • 179