[FR] Verifying SSH signature of a file without loading the entire file into memory

[legeana]

Currently PublicKey::verify requires the entire message to be passed as a &[u8] from RAM. I was wondering if it would be feasible to support a version of verify that would take a file (or better std::io::Read) instead?

The use case I have in mind is verifying signatures for files of unknown size.

Thank you for your time.

P.S. ssh-keygen -Y verify also loads the entire message in memory.

[tarcieri]

It's a little bit tricky because signature verification is backed by many different algorithms, and the ability to do this depends on the algorithm used. DSA, RSA, and ECDSA are the only ones that make this relatively straightforward.

To avoid these algorithm-specific implementation details, you could instead compute a digest over a file, then sign the digest.

[legeana]

It's a little bit tricky because signature verification is backed by many different algorithms, and the ability to do this depends on the algorithm used. DSA, RSA, and ECDSA are the only ones that make this relatively straightforward.

That make sense, thank you for clarification.

To avoid these algorithm-specific implementation details, you could instead compute a digest over a file, then sign the digest.

Yea I was considering this as a workaround. However I found it quite convenient to just use ssh-keygen -Y sign on a file, and interestingly sign doesn't have to load the entire file into memory. So I thought it would be a potentially nice improvement for verification.

However since the issue is that not every algorithm supports streaming implementation then it makes total sense to err on the side of the most compatible API.

[tarcieri]

However I found it quite convenient to just use ssh-keygen -Y sign on a file, and interestingly sign doesn't have to load the entire file into memory

Does that work for ed25519? That's the trickiest one.

It's possible to do that sort of incremental signing but it requires two passes over the input.

[legeana]

Does that work for ed25519? That's the trickiest one.

To be honest I am not 100% sure. I am doing the following experiment to verify, which can be a data point.

1. I have a 8G RAM virtual machine.
2. I create a new tmux tab for the experiment.
3. I create a new file called 30G via $ dd if=/dev/random of=30G bs=1M count=30000. This file will not fit into RAM. I use /dev/random instead of /dev/zero to avoid some accidental clever sparse file optimisations.
4. I have a ssh-ed25519 key loaded into my ssh agent: ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIDDShKKJSxIoOefearxLMuKT+Y4TkyypOTU4weoatzvJ.
5. I run ssh-keygen -Y sign -n file -f (echo ssh-ed25519 AAAAC3NzaC1lZDI1NTE5AAAAIDDShKKJSxIoOefearxLMuKT+Y4TkyypOTU4weoatzvJ | psub) 30G in my shell. The command takes a while. Once I my ssh-agent that runs locally prompts me to confirm my presence the signature is written. I can only assume that the fact that the agent is prompted at the very end is a sign that the file was pre-processed before signing. Maybe digest? I am not familiar with the ssh internals.
6. Now I run $ cat 30G | ssh-keygen -Y verify -I legeana@liri.ie -n 'file' -f ~/.gitconfig.keys/allowed-signers -s 30G.sig to verify the signature. The output is Good "file" signature for legeana@liri.ie with ED25519 key SHA256:EA+zWl4jdLDZFnELh6zt1E3H34UQAfKAg33a4Xz+Uzk.

It's interesting that ssh-keygen in this experiment succeeded. Maybe I did the previous experiment wrong? I am unsure, sorry.
I tried monitoring the RAM usage through both command executions via htop and it stayed consistently at ~50%, so ssh-keygen didn't consume any noticeable amount of RAM.

So the conclusion of my experiment is that both sign and verify don't need to load the entire message into RAM, possibly because ssh implements some sort of digest itself?

Following the source code from https://aur.archlinux.org/packages/openssh-git: git://anongit.mindrot.org/openssh.git:

1. ssh-keygen.c: main initialises sign_op if -Y is used.
2. Depending on the sign_op value either sig_sign or sig_verify is called.
3. sig_verify calls sshsig_verify_fd(sigbuf, STDIN_FILENO, sig_namespace, &sign_key, &sig_details).
4. sshsig_verify_fd is defined in sshsig.c.
5. sshsig_verify_fd queries sshsig_peek_hashalg from the signature.
6. HASHALG_DEFAULT is "sha512" and HASHALG_ALLOWED is "sha256,sha512".

Based on the above I see that ssh-keygen creates a sha512 digest and signs that. Given that I was able to verify signatures generates by ssh-keygen as is, I think RustCrypto/SSH has to calculate a message digest internally as well. And if so it would be feasible to provide a streaming API.

Now looking at sshsig.rs I see that SshSig includes hash_alg: HashAlg. The digest implementation is provided here:

SSH/ssh-key/src/algorithm.rs

Lines 440 to 445 in ee835e3

	pub fn digest(self, msg: &[u8]) -> Vec<u8> {
	match self {
	HashAlg::Sha256 => Sha256::digest(msg).to_vec(),
	HashAlg::Sha512 => Sha512::digest(msg).to_vec(),
	}
	}

What do you think @tarcieri? Would it be possible to provide a wrapped digest object that a user could feed the data to, and then provide that object by value to the PublicKey::verify?

For example:

// ssh-key
pub struct Digest(PrivateDigestImpl);

impl Digest {
  // Same as digest::Digest.
  pub fn update(&mut self, chunk: impl AsRef<[u8]>) {...}
  // Used internally by PublicKey only.
  fn finalize(self) -> ... {}
}

// user code
let digest = ssh_key::Digest::new();
digest.update(...);
digest.update(...);
digest.update(...);
let pkey = PublicKey::from_openssh(...);
pkey.verify("file", digest, ".... ssh-sig ...");

[tarcieri]

Sounds like it might be using the two-pass method then.

We could potentially add a method for computing signatures over files. It really would need to be a std::fs::File though to support the two-pass signing Ed25519 requires.

As I mentioned earlier, DSA, RSA, and ECDSA are all compatible with prehashing as you suggest. That doesn’t work with Ed25519 however, again because it needs to do two separate passes over the file that compute different digests (they include different data at the beginning of the hash).

[legeana]

I don't think I agree based on my understanding of the source code. Let me demonstrate.

Verify

The method I am suggesting to change is PublicKey::verify.

SSH/ssh-key/src/public.rs

Lines 234 to 244 in ee835e3

	pub fn verify(&self, namespace: &str, msg: &[u8], signature: &SshSig) -> Result<()> {
	if self.key_data() != signature.public_key() {
	return Err(Error::PublicKey);
	}
	if namespace != signature.namespace() {
	return Err(Error::Namespace);
	}
	signature.verify(msg)
	}

In this method the only usage of msg is signature.verify(msg).

Let's look at SshSig::verify.

SSH/ssh-key/src/sshsig.rs

Lines 156 to 166 in ee835e3

	pub(crate) fn verify(&self, msg: &[u8]) -> Result<()> {
	let signed_data = SignedData {
	namespace: self.namespace.as_str(),
	reserved: self.reserved.as_slice(),
	hash_alg: self.hash_alg,
	hash: self.hash_alg.digest(msg).as_slice(),
	}
	.to_bytes()?;
	Ok(self.public_key.verify(&signed_data, &self.signature)?)
	}

msg is only used to compute digest and initialise signed_data.hash. This can be computed via a streaming API. And this works for all types of keys.

Sign

I haven't tried using signing API since personally I'm relying on ssh-agent, but here goes.

If I understand ssh_key library correctly the intended way to sign a message is to use PrivateKey::sign. Let's take a look at the implementation:

SSH/ssh-key/src/private.rs

Lines 343 to 345 in ee835e3

	pub fn sign(&self, namespace: &str, hash_alg: HashAlg, msg: &[u8]) -> Result<SshSig> {
	SshSig::sign(self, namespace, hash_alg, msg)
	}

Here msg is simply passed to SshSig::sign. Let's dig deeper:

SSH/ssh-key/src/sshsig.rs

Lines 104 to 126 in ee835e3

	pub fn sign<S: SigningKey>(
	signing_key: &S,
	namespace: &str,
	hash_alg: HashAlg,
	msg: &[u8],
	) -> Result<Self> {
	if namespace.is_empty() {
	return Err(Error::Namespace);
	}
	if signing_key.public_key().is_sk_ed25519() {
	return Err(Algorithm::SkEd25519.unsupported_error());
	}
	#[cfg(feature = "ecdsa")]
	if signing_key.public_key().is_sk_ecdsa_p256() {
	return Err(Algorithm::SkEcdsaSha2NistP256.unsupported_error());
	}
	let signed_data = Self::signed_data(namespace, hash_alg, msg)?;
	let signature = signing_key.try_sign(&signed_data)?;
	Self::new(signing_key.public_key(), namespace, hash_alg, signature)
	}

msg is used once in let signed_data = Self::signed_data(namespace, hash_alg, msg). Let's take a look at that:

SSH/ssh-key/src/sshsig.rs

Lines 137 to 149 in ee835e3

	pub fn signed_data(namespace: &str, hash_alg: HashAlg, msg: &[u8]) -> Result<Vec<u8>> {
	if namespace.is_empty() {
	return Err(Error::Namespace);
	}
	SignedData {
	namespace,
	reserved: &[],
	hash_alg,
	hash: hash_alg.digest(msg).as_slice(),
	}
	.to_bytes()
	}

msg is used once to initialise hash: hash: hash_alg.digest(msg).as_slice().

I notice however that certain signing algorithms are not yet implemented. So I looked at the sshsig.c source code. Tracking down ssh-keygen I see this:

https://github.com/openssh/openssh-portable/blob/5f761cdb2331a12318bde24db5ca84ee144a51d1/sshsig.c#L575-L600

The file is first hashed, and then sshsig_wrap_sign is called. The fd parameter is the file opened for read, or STDIN. Later the output buffer &b is passed to sshsig_wrap_sign, but not fd. hash_file reads the input file only once:

https://github.com/openssh/openssh-portable/blob/5f761cdb2331a12318bde24db5ca84ee144a51d1/sshsig.c#L527-L545

Summary

In both cases message was only used once to generate signed_data.hash via hash_alg.digest(msg).
While I have no strong objections over using File API, 2nd pass is unnecessary. The digest is computed once in both cases.
Plus, if I understand the code correctly, what I showed above is independent from the key type.

I am not familiar with cryptography intricacies of ssh, so Ed25519 might require something special. But I wonder if the two-pass signing you are talking about applies to the digest returned by the hash_alg, and not the raw input data?

Please let me know if I got this wrong. I greatly appreciate your time looking into my suggestion.

[tarcieri]

Oh right, sorry yes, sshsig already incorporates an envelope. Will take another look when I’m at a computer.

[tarcieri]

#384 adds basic support for signing/verifying prehashed messages with SshSig.

I plan on adding a few more helpers for working directly with Digests.