Safely store data before moving to air-gapped machine This is related to an earlier question, Is it possible to use an algorithm to generate an OTP?

I have two machines: A, and B.  A is connected to the internet and files are uploaded regularly.  B is air-gapped.

When files are uploaded to A, I want to encrypt and store them in the most secure way possible.  They will then be transferred via USB to machine B, where they can be decrypted and read.  What's the most secure method of going about this?

My understanding is that this is a pretty standard encryption problem.  However, as far as I can see, the nonce for each message is transferred along with the message itself.  I would rather some method where the nonce could be generated by an algorithm that both A and B knew, with a seed that was secret shared between them.  Is this possible?
However, as far as I can see, the nonce for each message is transferred along with the message itself. 


Yes, this is typically what happens nowadays when encrypting something using symmetric encryption. 

Notice this is not necessarily the case if you're using asymmetric cryptography, since then the randomness used (which can be considered to be a "nonce") is usually encrypted along the message.

Probably the easiest way: asymmetric crypto

If you are only transferring data from one machine A to the other machine B and do not necessarily need to decrypt the data again on the first machine A, I would strongly recommend you to check out public-key encryption:


You could have a strong private key on your machine B and let machine A know the public key
Machine A could then encrypt everything you need to transmit to machine B using the public key of machine B, without leaking the secret key or anything that might allow someone to decrypt your data on machine A.
Machine B could then use its secret key to decrypt the data.


This is especially true if machine A is not air-gaped, while machine B is: you could consider machine A to be already compromised and as such all the keys, IV or passwords you might have on machine A might leak, whereas using public-key encryption, your data could not be decrypted by only looking at the secrets that went through machine A (even if the said data could be arguably already leaked while unencrypted).

(This can even work if you want machine A to be able to decrypt the data again, by encrypting the data for both the public key of machine A and B.)

About the air-gap

Notice that the air-gap in the end does not necessarily change things, as it boils down to two different scenarii:


Machine A is compromised and all the secret key, IV, nonces, and (most dramatically) messages that go through machine A can then be considered compromised
Machine A is not compromised and then we are fine


But maybe the air-gaped machine is compromised as well by a physical attacker, who knows? So there are more scenarii... 
And in the end we have the same kind of scenarii than whenever we have two machines and we want to transmit data between them.

There is nothing in crypto that can help you protect your data from a compromised machine if the plaintext is on the compromised machine...

Yet, it is not because of this dichotomy (either compromised or not) that you don't need encryption.
Indeed, encrypting your data is still useful to protect the data when: 


it's at rest, so that even if somebody access your machines and copy your data, they won't be able to read the data.
it's in transit, so that even if somebody intercepts your data, it will be encrypted and undecipherable for the attacker.


Even more so since it might be possible to recover erased data from a USB stick, or whatever transportation method you are using for your data...

And if the attach is not permanent, but occurs for example only when you're away ("evil maid attack"), then having encrypted data makes also sense.

Now, if you really want to do what you're discussing


  I would rather some method where the nonce could be generated by an
  algorithm that both A and B knew, with a seed that was secret shared
  between them. Is this possible?


Now, if you really want symmetric encryption, this is still possible and readily supported by Openssl, actually! (But not by other common tools such as GnuPG.)
If we take a look at the documentation of Openssl's enc feature, we can see the following:


  -K key
  
  The actual key to use: this must be represented as a string comprised only of hex digits. If only the key is specified, the IV
  must additionally specified using the -iv option. When both a key and
  a password are specified, the key given with the -K option will be
  used and the IV generated from the password will be taken. It does not
  make much sense to specify both key and password.
  
  -iv IV
  
  The actual IV to use: this must be represented as a string comprised only of hex digits. When only the key is specified using the
  -K option, the IV must explicitly be defined. When a password is being specified using one of the other options, the IV is generated from
  this password.
  
  -pass arg
  
  The password source. For more information about the format of arg see "Pass Phrase Options" in openssl(1).


So you could typically have a key specified using the -K argument, and derive the IV from a shared "password" file using the -pass file:pathname argument.
Notice you can choose how to derive the password, I would recommend you going with -pbkdf2 and setting a certain number of iterations:


  -iter count
  
  Use a given number of iterations on the password in deriving the encryption key. High values increase the time required to brute-force
  the resulting file. This option enables the use of PBKDF2 algorithm to
  derive the key.


BUT! 
There are a couple issue with this method: 


this will make it "easy" to reuse an IV, since if you are using the same password twice with the same number of iterations you should get the same IV, right? Well, not exactly, because Openssl got you covered. The password derivation algorithm is relying on a "salt" that gets passed on the first line of the encrypted file, just like you would usually pass the IV. I guess you could complain this is basically the same as passing the IV, but it is not, since the salt is used with a "secret" password to derive the IV.
this makes it easy to use too short keys!! This is really a problem, because if you are using a key that is not of the right size, Openssl will pad the key with zeros to achieve the right length! 
using Openssl manually on the command line is a bit painful.
it is easy to use a "bad" parameters.
and finally, and most annoyingly: this does not allow the use of authentication encryption! This is justified in the documentation as follow:



  The AEAD modes currently in common use also suffer from catastrophic failure of confidentiality and/or integrity upon reuse of key/iv/nonce, and since openssl enc places the entire burden of key/iv/nonce management upon the user, the risk of exposing AEAD modes is too great to allow. 


And this is true: key, iv and nonce management are considered difficult, and we do not recommend you to do it yourself! You can if you really want to, but it is typically not something we will tell you is "the most secure method" to do any kind of cryptography.

Notice that my last point is a problem: the lack of authentication means somebody could change your encrypted data without being detected, but you could solve it by performing a MAC after encryption, in the "Encrypt-then-MAC" style. This is possible using openssl mac or openssl dgst depending on your version.  Or you might solve it by using instead LibreSSL openssl that's including AHEAD mode in its enc command... You just need to pick an authenticated cipher.

TL;DR: don't do it.

However as you can see: the more we are digging that hole, the more we need to dig to try and have something "secure"... As such, this is typically not something you want to do "manually".

We usually recommend using symmetric or asymmetric encryption (using typically GnuPG), and not caring about managing the IV, and the "gory details" such as the need for authentication, etc. (Notice GPG --sign will use public-key signatures, so you would need to generate a key and share the public key with the other machine even if using the --symmetric mode.)

Also, if you are now considering "rolling your own" crypto, to solve your problems, you might as well try and take a look at what other have already done when facing a bit the same kind of problem as you do, there are many tools out there. 
One of the "simplest" tool is probably "Enchive" which is using an interesting shared key generation algorithm based on Diffie-Hellman, but is still quite minimalist. 

I also recommend you following the development of "Age" that has been recently designed and created by very good cryptographers, and should allow you to have high security, with good usability to do you want to do, without having to care too much about IVs, etc.

Notice how really nobody, even when "rolling their own" is letting users manage their nonces/IV, this is done for reasons... And I don't recommend you doing it neither.