sq: Add command sq key adopt.

  - Add a subcommand to have a certificate adopt a key on another
    certificate.  That is, the subcommand adds a key from one
    certificate (A) to another (B) by having B create any necessary
    binding signatures.

  - The modified certificate is written to stdout.

6 files changed, 389 insertions, 4 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 1384c590..f9a6e98c 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -90,6 +90,19 @@ dependencies = [
 ]
 
 [[package]]
+name = "assert_cmd"
+version = "1.0.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "3dc1679af9a1ab4bea16f228b05d18f8363f8327b1fa8db00d2760cfafc6b61e"
+dependencies = [
+ "doc-comment",
+ "predicates",
+ "predicates-core",
+ "predicates-tree",
+ "wait-timeout",
+]
+
+[[package]]
 name = "atty"
 version = "0.2.14"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -768,6 +781,15 @@ dependencies = [
 ]
 
 [[package]]
+name = "float-cmp"
+version = "0.8.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e1267f4ac4f343772758f7b1bdcbe767c218bbab93bb432acbf5162bbf85a6c4"
+dependencies = [
+ "num-traits",
+]
+
+[[package]]
 name = "fnv"
 version = "1.0.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1394,6 +1416,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "normalize-line-endings"
+version = "0.3.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "61807f77802ff30975e01f4f071c8ba10c022052f98b3294119f3e615d13e5be"
+
+[[package]]
 name = "num-bigint-dig"
 version = "0.6.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -1614,6 +1642,35 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "925383efa346730478fb4838dbe9137d2a47675ad789c546d150a6e1dd4ab31c"
 
 [[package]]
+name = "predicates"
+version = "1.0.5"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "96bfead12e90dccead362d62bb2c90a5f6fc4584963645bc7f71a735e0b0735a"
+dependencies = [
+ "difference",
+ "float-cmp",
+ "normalize-line-endings",
+ "predicates-core",
+ "regex",
+]
+
+[[package]]
+name = "predicates-core"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "06075c3a3e92559ff8929e7a280684489ea27fe44805174c3ebd9328dcb37178"
+
+[[package]]
+name = "predicates-tree"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8e63c4859013b38a76eca2414c64911fba30def9e3202ac461a2d22831220124"
+dependencies = [
+ "predicates-core",
+ "treeline",
+]
+
+[[package]]
 name = "prettytable-rs"
 version = "0.8.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2041,11 +2098,13 @@ version = "0.22.0"
 dependencies = [
  "anyhow",
  "assert_cli",
+ "assert_cmd",
  "buffered-reader",
  "chrono",
  "clap",
  "crossterm",
  "itertools",
+ "predicates",
  "prettytable-rs",
  "rpassword",
  "sequoia-autocrypt",
@@ -2478,6 +2537,12 @@ dependencies = [
 ]
 
 [[package]]
+name = "treeline"
+version = "0.1.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "a7f741b240f1a48843f9b8e0444fb55fb2a4ff67293b50a9179dfd5ea67f8d41"
+
+[[package]]
 name = "try-lock"
 version = "0.2.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -2562,6 +2627,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "b5a972e5669d67ba988ce3dc826706fb0a8b01471c088cb0b6110b805cc36aed"
 
 [[package]]
+name = "wait-timeout"
+version = "0.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "9f200f5b12eb75f8c1ed65abd4b2db8a6e1b138a20de009dacee265a2498f3f6"
+dependencies = [
+ "libc",
+]
+
+[[package]]
 name = "want"
 version = "0.3.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/sq/Cargo.toml b/sq/Cargo.toml
index 9bc5afeb..1c79f069 100644
--- a/sq/Cargo.toml
+++ b/sq/Cargo.toml
@@ -44,6 +44,8 @@ clap = "2.33"
 
 [dev-dependencies]
 assert_cli = "0.6"
+assert_cmd = "1.0.1"
+predicates = "1.0.5"
 
 [[bin]]
 name = "sq"
diff --git a/sq/src/commands/key.rs b/sq/src/commands/key.rs
index dc1df48a..b10da74a 100644
--- a/sq/src/commands/key.rs
+++ b/sq/src/commands/key.rs
@@ -3,14 +3,21 @@ use clap::ArgMatches;
 use itertools::Itertools;
 use std::time::{SystemTime, Duration};
 
-use crate::openpgp::Result;
+use crate::openpgp::KeyHandle;
 use crate::openpgp::Packet;
-use crate::openpgp::cert::prelude::*;
-use crate::openpgp::types::KeyFlags;
+use crate::openpgp::Result;
 use crate::openpgp::armor::{Writer, Kind};
+use crate::openpgp::cert::prelude::*;
+use crate::openpgp::packet::prelude::*;
+use crate::openpgp::packet::signature::subpacket::SubpacketTag;
+use crate::openpgp::parse::Parse;
+use crate::openpgp::policy::Policy;
 use crate::openpgp::serialize::Serialize;
+use crate::openpgp::types::KeyFlags;
+use crate::openpgp::types::SignatureType;
 
 use crate::create_or_stdout;
+use crate::decrypt_key;
 
 const SECONDS_IN_DAY : u64 = 24 * 60 * 60;
 const SECONDS_IN_YEAR : u64 =
@@ -246,3 +253,194 @@ fn parse_duration(expiry: &str) -> Result<Duration> {
 
     Ok(Duration::new(count * factor, 0))
 }
+
+pub fn adopt(m: &ArgMatches, p: &dyn Policy) -> Result<()> {
+    let cert = m.value_of("certificate").unwrap();
+    let cert = Cert::from_file(cert)
+        .context(format!("Parsing {}", cert))?;
+    let mut wanted: Vec<(KeyHandle,
+                         Option<(Key<key::PublicParts, key::SubordinateRole>,
+                                 SignatureBuilder)>)>
+        = vec![];
+
+    // Gather the Key IDs / Fingerprints and make sure they are valid.
+    for id in m.values_of("key").unwrap_or_default() {
+        let h = id.parse::<KeyHandle>()?;
+        if h.is_invalid() {
+            return Err(anyhow::anyhow!(
+                "Invalid Fingerprint or KeyID ('{:?}')", id));
+        }
+        wanted.push((h, None));
+    }
+
+    // Find the corresponding keys.
+    for keyring in m.values_of("keyring").unwrap_or_default() {
+        for cert in CertParser::from_file(keyring)
+            .context(format!("Parsing: {}", keyring))?
+        {
+            let cert = cert.context(format!("Parsing {}", keyring))?;
+            let vc = match cert.with_policy(p, None) {
+                Ok(vc) => vc,
+                Err(err) => {
+                    eprintln!("Ignoring {} from '{}': {}",
+                              cert.keyid().to_hex(), keyring, err);
+                    continue;
+                }
+            };
+
+            for key in vc.keys() {
+                for (id, ref mut keyo) in wanted.iter_mut() {
+                    if id.aliases(key.key_handle()) {
+                        match keyo {
+                            Some((_, _)) =>
+                                // We already saw this key.
+                                (),
+                            None => {
+                                let sig = key.binding_signature();
+                                let builder: SignatureBuilder = match sig.typ() {
+                                    SignatureType::SubkeyBinding =>
+                                        sig.clone().into(),
+                                    SignatureType::DirectKey
+                                        | SignatureType::PositiveCertification
+                                        | SignatureType::CasualCertification
+                                        | SignatureType::PersonaCertification
+                                        | SignatureType::GenericCertification =>
+                                    {
+                                        // Convert to a binding
+                                        // signature.
+                                        let kf = sig.key_flags()
+                                            .context("Missing required \
+                                                      subpacket, KeyFlags")?;
+                                        SignatureBuilder::new(
+                                            SignatureType::SubkeyBinding)
+                                            .set_key_flags(kf)?
+                                    },
+                                    _ => panic!("Unsupported binding \
+                                                 signature: {:?}",
+                                                sig),
+                                };
+
+                                *keyo = Some(
+                                    (key.key().clone().role_into_subordinate(),
+                                     builder));
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+
+    // If we are missing any keys, stop now.
+    let missing: Vec<&KeyHandle> = wanted
+        .iter()
+        .filter_map(|(id, keyo)| {
+            match keyo {
+                Some(_) => None,
+                None => Some(id),
+            }
+        })
+        .collect();
+    if missing.len() > 0 {
+        return Err(anyhow::anyhow!(
+            "Keys not found: {}",
+            missing.iter().map(|&h| h.to_hex()).join(", ")));
+    }
+
+
+    let passwords = &mut Vec::new();
+
+    // Get a signer.
+    let pk = cert.primary_key().key();
+    let mut pk_signer =
+        decrypt_key(
+            pk.clone().parts_into_secret()?,
+            passwords)?
+        .into_keypair()?;
+
+
+    // Add the keys and signatues to cert.
+    let mut packets: Vec<Packet> = vec![];
+    for (_, ka) in wanted.into_iter() {
+        let (key, builder) = ka.expect("Checked for missing keys above.");
+        let mut builder = builder;
+
+        // If there is a valid backsig, recreate it.
+        let need_backsig = builder.key_flags()
+            .map(|kf| kf.for_signing() || kf.for_certification())
+            .expect("Missing keyflags");
+
+        if need_backsig {
+            // Derive a signer.
+            let mut subkey_signer
+                = decrypt_key(
+                    key.clone().parts_into_secret()?,
+                    passwords)?
+                .into_keypair()?;
+
+            let backsig = builder.embedded_signatures()
+                .filter(|backsig| {
+                    (*backsig).clone().verify_primary_key_binding(
+                        &cert.primary_key(),
+                        &key).is_ok()
+                })
+                .nth(0)
+                .map(|sig| SignatureBuilder::from(sig.clone()))
+                .unwrap_or_else(|| {
+                    SignatureBuilder::new(SignatureType::PrimaryKeyBinding)
+                })
+                .sign_primary_key_binding(&mut subkey_signer, pk, &key)?;
+
+            builder = builder.set_embedded_signature(backsig)?;
+        } else {
+            builder = builder.modify_hashed_area(|mut a| {
+                a.remove_all(SubpacketTag::EmbeddedSignature);
+                Ok(a)
+            })?;
+        }
+
+        let mut sig = builder.sign_subkey_binding(&mut pk_signer, pk, &key)?;
+
+        // Verify it.
+        assert!(sig.verify_subkey_binding(pk_signer.public(), pk, &key)
+                .is_ok());
+
+        packets.push(key.into());
+        packets.push(sig.into());
+    }
+
+    let cert = cert.clone().insert_packets(packets.clone())?;
+
+    cert.as_tsk().armored().serialize(&mut std::io::stdout())?;
+
+    let vc = cert.with_policy(p, None).expect("still valid");
+    for pair in packets[..].chunks(2) {
+        let newkey: &Key<key::PublicParts, key::UnspecifiedRole> = match pair[0] {
+            Packet::PublicKey(ref k) => k.into(),
+            Packet::PublicSubkey(ref k) => k.into(),
+            Packet::SecretKey(ref k) => k.into(),
+            Packet::SecretSubkey(ref k) => k.into(),
+            ref p => panic!("Expected a key, got: {:?}", p),
+        };
+        let newsig: &Signature = match pair[1] {
+            Packet::Signature(ref s) => s,
+            ref p => panic!("Expected a sig, got: {:?}", p),
+        };
+
+        let mut found = false;
+        for key in vc.keys() {
+            if key.fingerprint() == newkey.fingerprint() {
+                for sig in key.self_signatures() {
+                    if sig == newsig {
+                        found = true;
+                        break;
+                    }
+                }
+            }
+        }
+        assert!(found, "Subkey: {:?}\nSignature: {:?}", newkey, newsig);
+    }
+
+    Ok(())
+}
diff --git a/sq/src/sq-usage.rs b/sq/src/sq-usage.rs
index 28e3085a..e3d442b9 100644
--- a/sq/src/sq-usage.rs
+++ b/sq/src/sq-usage.rs
@@ -478,10 +478,31 @@
 //!     -V, --version    Prints version information
 //!
 //! SUBCOMMANDS:
+//!     adopt       Bind keys from one certificate to another.
 //!     generate    Generates a new key
 //!     help        Prints this message or the help of the given subcommand(s)
 //! ```
 //!
+//! ### Subcommand key adopt
+//!
+//! ```text
+//! Bind keys from one certificate to another.
+//!
+//! USAGE:
+//!     sq key adopt [OPTIONS] <CERT> --key <KEY>...
+//!
+//! FLAGS:
+//!     -h, --help       Prints help information
+//!     -V, --version    Prints version information
+//!
+//! OPTIONS:
+//!     -k, --key <KEY>...            Adds the specified key or subkey to the certificate.
+//!     -r, --keyring <KEYRING>...    A keyring containing the keys specified in --key.
+//!
+//! ARGS:
+//!     <CERT>    The certificate to add keys to.
+//! ```
+//!
 //! ### Subcommand key generate
 //!
 //! ```text
diff --git a/sq/src/sq.rs b/sq/src/sq.rs
index f93c0370..42fc6dc3 100644
--- a/sq/src/sq.rs
+++ b/sq/src/sq.rs
@@ -26,8 +26,10 @@ use openpgp::{
 };
 use crate::openpgp::{armor, Cert};
 use sequoia_autocrypt as autocrypt;
+use crate::openpgp::crypto::Password;
 use crate::openpgp::fmt::hex;
 use crate::openpgp::types::KeyFlags;
+use crate::openpgp::packet::prelude::*;
 use crate::openpgp::parse::Parse;
 use crate::openpgp::serialize::{Serialize, stream::{Message, Armorer}};
 use crate::openpgp::cert::prelude::*;
@@ -163,6 +165,66 @@ fn parse_armor_kind(kind: Option<&str>) -> armor::Kind {
     }
 }
 
+// Decrypts a key, if possible.
+//
+// The passwords in `passwords` are tried first.  If the key can't be
+// decrypted using those, the user is prompted.  If a valid password
+// is entered, it is added to `passwords`.
+fn decrypt_key<R>(key: Key<key::SecretParts, R>, passwords: &mut Vec<String>)
+    -> Result<Key<key::SecretParts, R>>
+    where R: key::KeyRole + Clone
+{
+    let key = key.parts_as_secret()?;
+    match key.secret() {
+        SecretKeyMaterial::Unencrypted(_) => {
+            Ok(key.clone())
+        }
+        SecretKeyMaterial::Encrypted(_) => {
+            for p in passwords.iter() {
+                if let Ok(key)
+                    = key.clone().decrypt_secret(&Password::from(&p[..]))
+                {
+                    return Ok(key);
+                }
+            }
+
+            let mut first = true;
+            loop {
+                // Prompt the user.
+                match rpassword::read_password_from_tty(
+                    Some(&format!(
+                        "{}Enter password to unlock {} (blank to skip): ",
+                        if first { "" } else { "Invalid password. " },
+                        key.keyid().to_hex())))
+                {
+                    Ok(p) => {
+                        first = false;
+                        if p == "" {
+                            // Give up.
+                            break;
+                        }
+
+                        if let Ok(key) = key
+                            .clone()
+                            .decrypt_secret(&Password::from(&p[..]))
+                        {
+                            passwords.push(p);
+                            return Ok(key);
+                        }
+                    }
+                    Err(err) => {
+                        eprintln!("While reading password: {}", err);
+                        break;
+                    }
+                }
+            }
+
+            Err(anyhow::anyhow!("Key {}: Unable to decrypt secret key material",
+                                key.keyid().to_hex()))
+        }
+    }
+}
+
 /// Prints a warning if the user supplied "help" or "-help" to an
 /// positional argument.
 ///
@@ -623,6 +685,7 @@ fn main() -> Result<()> {
         },
         ("key", Some(m)) => match m.subcommand() {
             ("generate", Some(m)) => commands::key::generate(m, force)?,
+            ("adopt", Some(m)) => commands::key::adopt(m, policy)?,
             _ => unreachable!(),
         },
         ("wkd",  Some(m)) => {
diff --git a/sq/src/sq_cli.rs b/sq/src/sq_cli.rs
index 76164989..a61a7a60 100644
--- a/sq/src/sq_cli.rs
+++ b/sq/src/sq_cli.rs
@@ -462,7 +462,34 @@ pub fn build() -> App<'static, 'static> {
                              .required_if("export", "-")
                              .help("Sets the output file for the revocation \
                                     certificate. Default is <OUTFILE>.rev, \
-                                    mandatory if OUTFILE is '-'."))))
+                                    mandatory if OUTFILE is '-'.")))
+                .subcommand(
+                    SubCommand::with_name("adopt")
+                        .about("Bind keys from one certificate to another.")
+                        .arg(Arg::with_name("keyring")
+                             .value_name("KEYRING")
+                             .long("keyring")
+                             .short("r")
+                             .multiple(true)
+                             .number_of_values(1)
+                             .takes_value(true)
+                             .help("A keyring containing the keys specified \
+                                    in --key."))
+                        .arg(Arg::with_name("key")
+                             .value_name("KEY")
+                             .long("key")
+                             .short("k")
+                             .multiple(true)
+                             .number_of_values(1)
+                             .takes_value(true)
+                             .required(true)
+                             .help("Adds the specified key or subkey to the \
+                                    certificate."))
+                        .arg(Arg::with_name("certificate")
+                             .value_name("CERT")
+                             .required(true)
+                             .help("The certificate to add keys to."))
+                ))
 
         .subcommand(SubCommand::with_name("packet")
                     .about("OpenPGP Packet manipulation")