deja-dup cannot decrypt my backup any more, GPG reports "bad session key"

[Jens]

Deja-dup cannot decrypt my backup any more. This seems to be a duplicate of https://bugzilla.novell.com/show_bug.cgi?id=821767.

This is the error message:
Import of duplicity.backends.sshbackend Failed: No module named paramiko
Synchronizing remote metadata to local cache...
GnuPG passphrase:
Copying duplicity-full-signatures.20130828T120049Z.sigtar.gpg to local cache.
GPGError: GPG Failed, see log below:
===== Begin GnuPG log =====
gpg: CAST5 encrypted data
gpg: encrypted with 1 passphrase
gpg: decryption failed: Bad session key
===== End GnuPG log =====

I am *sure* my password is correct. And I have also verified the keyboard mapping did not change. I also unset GPG_AGENT_INFO and killed gpg-agent (just in case).
So what can this be? Is it in fact an incorrect password or has something else gone bad?

GPG 1.4.11, duplicity 0.6.18, deja-dup 22.0

ProblemType: Bug
DistroRelease: Ubuntu 12.04
Package: deja-dup 22.0-0ubuntu4
ProcVersionSignature: Ubuntu 3.5.0-39.60~precise1-generic 3.5.7.17
Uname: Linux 3.5.0-39-generic i686
ApportVersion: 2.0.1-0ubuntu17.4
Architecture: i386
Date: Sat Aug 31 10:35:35 2013
InstallationMedia: Ubuntu 12.04.2 LTS "Precise Pangolin" - Release i386 (20130214)
MarkForUpload: True
ProcEnviron:
 PATH=(custom, no user)
 LANG=de_DE.UTF-8
 SHELL=/bin/bash
SourcePackage: deja-dup
UpgradeStatus: No upgrade log present (probably fresh install)

[Michael Terry (mterry)]

After some testing, I think I know what could cause this (now very old) bug. There was a bug in deja-dup/duplicity that allowed for an accidental change in password when making the occasional full backup checkpoint (bug 918489, fixed in deja-dup 34.3).

Here's how this would be reproduced, using deja-dup <= 34.2:
- Create a new backup with password 'a'
- Keep backing up until deja-dup decides to make a new backup. Then either have a different password saved in gnome-keyring or enter a different password when it prompts. Say, 'b'
- Now you have two backup chains with different passwords, but deja-dup will keep adding new backups.
- Until either your cache gets blown away or deja-dup decides to do its every-two-months backup-validation check. (Or heaven forbid, your hard drive gets blown away and you need to restore.)
- When either happens, duplicity will try to download the encrypted manifest files for all the backups and deja-dup will prompt you for the decryption password.
- If you enter 'a', it will choke on your second backup and show the password prompt again. If you enter 'b' it will choke on the first. Thus you get eternal backup prompts.

The only way to recover is to blow away older backups (or the whole thing) and start over. If you were trying to restore, your files can be manually recovered using duplicity though.

Anyway. That's my research into what this bug was likely about. I'll mark it as a dup of bug 918489.